Форум программистов, компьютерный форум CyberForum.ru

Немного о списках - C++

Восстановить пароль Регистрация
 
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 190
08.12.2012, 19:09     Немного о списках #1
Помогите разобраться со списками(хотя бы односвязными) Подскажите пример простого кода, где реализован список как можно проще.
Вот пока что я сам сделал по лекциям:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "stdafx.h"
Elem* Add(int,Elem*)//Добавляет элемент в список
int main()
{
    struct Elem 
    {
        int Data;
        Elem* Next;
    };
}
Elem* Add(pElem l, A data, bool addend)
{
    if ( !l )
    {
        pElem newel = new Elem;
        newel->Data = data;
        newel->Next = NULL;
        newel->Prev = NULL;
        return newel;
    }
    else
    {
        if (!addend)
        {
            pElem newel = new Elem;
            newel->Data = data;
            newel->Next = l;
            newel->Prev = NULL;
            l->Prev = newel;
            return newel;
        }
        else
        {
            pElem fel = l;
            while (l->Next) l = l->Next;
            pElem newel = new Elem;
            newel->Data = data;
            newel->Next = NULL;
            newel->Prev = l;
            l->Next = newel;
            return fel;
        }
    }
}
На данный момент научите передавать список в функцию, объясните ф-ю, которую я показал(это из лекции) может есть попроще вариант.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
08.12.2012, 19:16     Немного о списках #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
 
struct list
{
         int data;
         list* next;
}*first;
 
void add(int x) //добавление в список
{
      list* cur = new list;
      cur->data=x;
      cur->next=first;
      first=cur;
}
 
void show() //вывод на экран
{
      list* f = first;
      while (f)
      {
              std::cout<<f->data<<'\t';
              f = f->next;
     }
}
 
int main()
{
     for (int i=0; i<10; i++)
          add(i); //добавляем в цикле
     show();  //выводим
     return 0;
}
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 190
08.12.2012, 19:26  [ТС]     Немного о списках #3
А вот можно ли всё-таки передавать список в ф-ю?
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
08.12.2012, 19:31     Немного о списках #4
FireProoF, как указатель на указатель, например:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
 
struct list
{
         int data;
         list* next;
};
 
void add(int x, list** first) //äîáГ*âëåГ*ГЁГҐ Гў ñïèñîê
{
      list* cur = new list;
      cur->data=x;
      cur->next=*first;
      *first=cur;
}
 
void show(list* first) //âûâîä Г*Г* ГЅГЄГ°Г*Г*
{
      list* f = first;
      while (f)
      {
              std::cout<<f->data<<'\t';
              f = f->next;
     }
}
 
int main()
{
     list* first = new list();
     first=NULL;
     for (int i=0; i<10; i++)
          add(i,&first); //äîáГ*âëÿåì Гў öèêëå
     show(first);  //âûâîäèì
     return 0;
}
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 190
08.12.2012, 19:50  [ТС]     Немного о списках #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct Elem 
{
        int Data;
        Elem* Next;
}*first;
void Print(int***,int);//Печатает поле с заданным размером.
void add(int, Elem* first);//Добавляет элемент в список
void show();//вывод списка
Elem* first = new Elem();
     first=NULL;
    //
    for (int i=0; i<5; i++)     add(i, first); //добавляем в цикле
    show();
void add(int x, Elem* first) //добавление в список
{
      Elem* cur = new Elem;
      cur->Data=x;
      cur->Next=first;
      first=cur;
}
 
void show() //вывод на экран
{
      Elem* f = first;
      while (f)
      {
              cout<<f->Data<<endl;
              f = f->Next;
     }
}
Ошибка: не печатает список
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
08.12.2012, 20:32     Немного о списках #6
Такое чувство, что на мой пример Вы и не опирались.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
struct Elem 
{
        int Data;
        Elem* Next;
};
void Print(int***,int);//ГЏГҐГ·Г*ГІГ*ГҐГІ ïîëå Г± Г§Г*Г¤Г*Г*Г*ûì Г°Г*çìåðîì.
void add(int, Elem** first);//ÄîáГ*âëÿåò ýëåìåГ*ГІ Гў ñïèñîê
void show(Elem*);//âûâîä Г±ГЇГЁГ±ГЄГ*
 
int main()
{
    Elem* first = new Elem();
     first=NULL;
    //
    for (int i=0; i<5; i++)     add(i, &first); //äîáГ*âëÿåì Гў öèêëå
    show(first);
}
void add(int x, Elem** first) //äîáГ*âëåГ*ГЁГҐ Гў ñïèñîê
{
      Elem* cur = new Elem;
      cur->Data=x;
      cur->Next=*first;
      *first=cur;
}
 
void show(Elem* first) //âûâîä Г*Г* ГЅГЄГ°Г*Г*
{
      Elem* f = first;
      while (f)
      {
              std::cout<<f->Data<<std::endl;
              f = f->Next;
     }
}
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 190
08.12.2012, 22:04  [ТС]     Немного о списках #7
Я стараюсь переделать код под свои нужды. Так лучше запоминается
Вопщем нужно, что бы выводил список задом наперёд.

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
// ConsoleApplication1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include  <stdio.h>
#include  <stdlib.h>
#include  <errno.h>
using namespace std;
struct Open_list //open list
{
        int Field;
        Open_list* Next;
}*first;
void Print(int***,int);//Печатает поле с заданным размером.
void add(int***, Open_list** first,int,int,int);//Добавляет элемент в список
void show(Open_list*);//вывод списка
int main()
{
    cout<<"Hello! Print size of the square map (size*size)"<<endl;
    int size;
    cin>>size;
    //создание 3d-поля
    int ***Map;
    Map=new int**[size];
    for(int i=0;i<size;i++) Map[i]=new int*[size];
    for(int i=0;i<size;i++)     
    {
        for(int j=0;j<size;j++)
        {
            Map[i][j]=new int[3];
        }
    }
    //Заполнение поля
    /*cout<<"What type of map you want to choose?"<<endl
        <<"1. Present(1 map)"<<endl
        <<"2. Random filling maps"<<endl
        <<"3. Manual filling maps"<<endl;*/
#if 1
    //Random
    int i,j,k=0;
    srand(time(0));
    //создание стен
for(i=0;;)
    {
        for(j=0;j<size;j++)
        {
            Map[i][j][k]=0;
        }
        break;
    }
for(i=size-1;;)
    {
        for(j=0;j<size;j++)
        {
            Map[i][j][k]=0;
        }
        break;
    }
for(j=0;;)
    {
        for(i=0;i<size;i++)
        {
            Map[i][j][k]=0;
        }
        break;
    }
for(j=size-1;;)
    {
        for(i=0;i<size;i++)
        {
            Map[i][j][k]=0;
        }
        break;
    }
#endif
    //заполнение поля
    for(i=1;i<size-1;i++)
    {
        cout<<endl;
        for(j=1;j<size-1;j++)
        {
            Map[i][j][k]=rand()%2;
        }
    }
    //
    Print(Map,size);//Вывод карты
    //0-свободное поле, 1-препятствие, 2-точка старта, 3-точка финиша,4-путь
    //создание точек старта и финиша
    cout<<endl;
    system("pause");
    int i_s,j_s,i_f,j_f;
    cout<<"Print [i][j] of start-point ";
    cin >>i_s
        >>j_s;
    cout<<"Print [i][j] of finish-point ";
    cin >>i_f
        >>j_f;
    //пометим эти точки и снова напечатаем
    Map[i_s][j_s][0]=2;
    Map[i_f][j_f][0]=3;
    Print(Map,size);//Вывод карты
    //создание списков
    //Открытый и закрытый список созданы
    //
    //добавляем в open_list стартовую точку и её окрестность
    k=0;//так как работаем с первым слоем
    add(Map,&first,i_s,j_s,k);
    for(i=i_s-1;i<=i_s+1;i++)
    {
        for(j=j_s-1;j<=j_s+1;j++)
        {
            if(i!=i_s || j!=j_s)    add(Map,&first,i,j,k); 
        }
    }
    show(first);
    //
    cout<<endl;
    system("pause");
    return 0;
}
 
void Print(int*** Arr,int size)
{
    int i,j,k=0;
    for(i=0;i<size;i++)
    {
        cout<<endl;
        for(j=0;j<size;j++)
        {
            cout<<Arr[i][j][k]<<" ";
        }
    }
}
 
void add(int*** x, Open_list** first,int i,int j, int k) //добавление в список
{
      Open_list* cur = new Open_list;
      cur->Field=x[i][j][k];
      cur->Next=*first;
      *first=cur;
}
 
void show(Open_list* first) //вывод на экран
{
      Open_list* f = first;
      while (f)
      {
              cout<<f->Field<<endl;
              f = f->Next;
     }
}


Добавлено через 17 минут
Я пересмотрел планы. Вот несколько вопросов:
1. Сложно ли переделать список в двунаправленный?
2. можно ли "вручную" перемещаться по списку как по массиву? то есть перематывать указатель.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
08.12.2012, 23:43     Немного о списках #8
Не стал разбирать, сделал на моем примере выше добавление наоборот.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
struct Elem 
{
        int Data;
        Elem* Next;
};
//void Print(int***,int);//ГЏГҐГ·Г*ГІГ*ГҐГІ ïîëå Г± Г§Г*Г¤Г*Г*Г*ûì Г°Г*çìåðîì.
void add(int, Elem** first);//ÄîáГ*âëÿåò ýëåìåГ*ГІ Гў ñïèñîê
void show(Elem*);//âûâîä Г±ГЇГЁГ±ГЄГ*
 
int main()
{
    Elem* first = new Elem();
    first=NULL;
    //
    for (int i=0; i<5; i++)     add(i, &first); //äîáГ*âëÿåì Гў öèêëå
    show(first);
}
void add(int x, Elem** first) //äîáГ*âëåГ*ГЁГҐ Гў ñïèñîê
{
      Elem* cur;
      Elem* f = *first;
     if (!*first)
     {
         cur = new Elem();
          cur->Data=x;
          cur->Next=*first;
          *first=cur;
      }
      else
      {
            cur=f;
            while (cur->Next)
             cur=cur->Next;
            cur->Next = new Elem();
            cur=cur->Next;
            cur->Data=x;
     }
     cur->Next=NULL;
     f=cur;
}
 
void show(Elem* first) //âûâîä Г*Г* ГЅГЄГ°Г*Г*
{
      Elem* f = first;
      while (f)
      {
              std::cout<<f->Data<<std::endl;
              f = f->Next;
     }
}
1) в двунаправленный не очень сложно, нужно в структуру добавить еще один указатель на предыдущий элемент и в функции add каждый раз его запоминать.
2) в списке за один раз можно получить только следующий или (если двунаправленный) предыдущий. На то он и список.
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 190
09.12.2012, 13:49  [ТС]     Немного о списках #9
Подскажите как переделать в двухсвязный список...

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*Здесь объявление ф-й*/
struct Open_list //open list
{
        int Field;
        int i;//положение текущей точки в 3d массиве
        int j;
        int k;
        int F;//Стоимость точки
        int G;
        int H;
        int i_p;//положение родительской точки
        int j_p;
        int k_p;
        Open_list* Next;//указатель на следующий элемент
}*pOpn_lst;
int main()
{
/*здесь код*/
add(Map,&pOpn_lst,i_s,j_s,k);
}
 
void add(int*** x, Open_list** pOpn_lst,int i,int j, int k,int F,int G,int H,int i_p,int j_p,int k_p) //добавление в список
{
      Open_list* cur = new Open_list;
      cur->Field=x[i][j][k];
      cur->Next=*pOpn_lst;
      *pOpn_lst=cur;
}

Если непонятно, то
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*Здесь объявление ф-й*/
struct Open_list //open list
{
        int Field;
        Open_list* Next;//указатель на следующий элемент
}*pOpn_lst;
 
int main()
{
/*здесь код*/
i=5;
add(i,&pOpn_lst);
}
 
void add(int x, Open_list** pOpn_lst) //добавление в список
{
      Open_list* cur = new Open_list;
      cur->Field=x;
      cur->Next=*pOpn_lst;
      *pOpn_lst=cur;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.12.2012, 14:33     Немного о списках
Еще ссылки по теме:

C++ Ошибка в списках
C++ Сравнение множеств (реализованых на односвязных списках)
Освобождение памяти в списках C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
09.12.2012, 14:33     Немного о списках #10
На примере функции добавления в прямом порядке:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
 
using namespace std;
 
struct Open_list //open list
{
        int Field;
        Open_list* Next;
        Open_list* Prev;
}*pOpn_lst=NULL;
 
void add(int, Open_list**);
void show(Open_list*);
 
int main()
{
 for (int i=0; i<10; i++)
      add(i,&pOpn_lst);
 show(pOpn_lst);
}
 
void add(int x, Open_list** pOpn_lst)
{
      Open_list* cur;
      Open_list* f = *pOpn_lst;
     if (!*pOpn_lst)
     {
         cur = new Open_list();
          cur->Field=x;
          cur->Next=*pOpn_lst;
          *pOpn_lst=cur;
          cur->Prev=cur;
      }
      else
      {
            cur=f;
            while (cur->Next)
             cur=cur->Next;
            Open_list* cur1=cur;
                cur->Next = new Open_list();         
            cur=cur->Next;
            cur->Prev=cur1; 
            cur->Field=x;
     }
     cur->Next=NULL;
     f=cur;
}
 
void show ( Open_list* pOpn_lst)
{
       Open_list* f = pOpn_lst;
      while (f)
      {
              std::cout<<f->Field<<" Preview: "<<f->Prev->Field<<std::endl;
              f = f->Next;
      }
}
В обратном нужно где-нибудь уточнить.
Yandex
Объявления
09.12.2012, 14:33     Немного о списках
Ответ Создать тему
Опции темы

Текущее время: 16:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru