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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 193
#1

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

08.12.2012, 19:09. Просмотров 315. Ответов 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
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;
        }
    }
}
На данный момент научите передавать список в функцию, объясните ф-ю, которую я показал(это из лекции) может есть попроще вариант.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2012, 19:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Немного о списках (C++):

Очередь в списках - C++
нужно в данную очередь вставить структуру. структуру-то я написала, а дальше не могу разобраться, подскажите, что делать, пожалуйста! ...

Ошибка в списках - C++
#include <iostream> #include <list> using namespace std; void main() { list<int> L, L1, L2; L.push_front(10); ...

Ошибка в списках - C++
В функции сравнения Compare не инициализируется переменная y. Зато такая же переменная h инициализируется. В чем ошибка подскажите. ...

Литература о Связаные списках - C++
Здравствуйте, кто знает какую нить литературу по которой можно понять связаные списки. И зачем нужны связаные списки.

Освобождение памяти в списках - C++
#pragma once class Node { public: int value; Node * next; Node(int data); ~Node(); };

Конструкторы в списках и конфликт имён - C++
Здравтсвуйте, уважаемые программисты, меня волнуют следующие вопросы: 1) Мне нужны примеры применения конструкторов в списках. Я нашёл в...

9
BumerangSP
4286 / 1408 / 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;
}
1
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 193
08.12.2012, 19:26  [ТС] #3
А вот можно ли всё-таки передавать список в ф-ю?
0
BumerangSP
4286 / 1408 / 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;
}
1
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 193
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;
     }
}
Ошибка: не печатает список
0
BumerangSP
4286 / 1408 / 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;
     }
}
1
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 193
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. можно ли "вручную" перемещаться по списку как по массиву? то есть перематывать указатель.
0
BumerangSP
4286 / 1408 / 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) в списке за один раз можно получить только следующий или (если двунаправленный) предыдущий. На то он и список.
1
FireProoF
17 / 17 / 1
Регистрация: 28.10.2012
Сообщений: 193
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;
}
0
BumerangSP
4286 / 1408 / 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;
      }
}
В обратном нужно где-нибудь уточнить.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.12.2012, 14:33
Привет! Вот еще темы с ответами:

Нужно найти ошибку в списках - C++
#include &lt;iostream&gt; #include &lt;conio.h&gt; using std::cout; using std::cin; using std::endl; //структуры struct Abc ...

Сравнение множеств (реализованых на односвязных списках) - C++
Требуется найти алгоритм, который без труда сможет сравнивать множества, содержащие большое количество элементов(~100000 элементов...:) )....

Вопрос: что такое ключ в списках? - C++
Вопрос: что такое ключ в списках? Код из литературы: Функции вставки и удаления элемента в односвязном списке. /*Функция вставки...

Ошибка в удалении повторяющихся данных в списках - C++
Добрый вечер. Не удаляются повторяющиеся данные в программе с использованием списков (функция Delete_double()) Спасибо за помощь. ...


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

Или воспользуйтесь поиском по форуму:
10
Yandex
Объявления
09.12.2012, 14:33
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru