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

двунаправленные списки С++ - C++

Восстановить пароль Регистрация
 
Fiks19
1 / 1 / 0
Регистрация: 07.01.2012
Сообщений: 44
13.01.2013, 11:41     двунаправленные списки С++ #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
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
#include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;
 
struct list
{
int key;//адресное поле
list *next;//указатель на следующий элемент
list *pred;//указатель на предыдущий элемент
};
 
 
list* make_point()
//создание одного элемента
{
 list *p=new(list);//выделяем память под первый элемент
 p->next=0;//обнуляем адресное поле
 p->pred=0;
 cout<<"\n1";
 cin >> p->key;//вводим значение информационного поля
 
 
 return p;//определили конец списка путем присвоению указателю p занчение 0(указатель beg)
}
 
 
list* make_list(int n)
//создание списка
{
list *p,*beg;
beg=make_point();//создаем первый элемент
for(int i=1;i<n;i++)
{
p=make_point();//создаем один элемент
//добавление элемента в начало списка
p->next=beg;//связываем р с первым элементом
beg->pred=p;//связываем первый элемент с p
beg=p;// p становится первым элементом списка
}
return beg;
}
 
void print_list(list *beg,list *p){
 
 
 
 while(beg!=0){
  cout<<beg->key<<"\t";
  beg=beg->pred;
 
 }
 
 
}
 
int main(){
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 
 
 int c;
 cin>>c;
 
   list*lp=make_list(c);
   cout<<"\n";
   print_list(lp,lp);
     getch();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2013, 11:41     двунаправленные списки С++
Посмотрите здесь:

C++ Двунаправленные списки
C++ Списки
работа со списками(двунаправленные списки) C++
Списки C++
C++ ООП. Вложенные структуры. Двунаправленные списки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 8
Регистрация: 24.07.2012
Сообщений: 916
13.01.2013, 11:56     двунаправленные списки С++ #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
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
#include <iostream>
using namespace std;
 
struct Elem
{
    Elem *prev, *next;
    char *data;
};
 
typedef Elem* List;
 
List create() //создать список
{
    List l=new Elem; //выделяем память для списка
    l->data=""; //делаем пустую строку
    l->next=0; //указатель на следующий нулевой
    l->prev=0; //указатель на предыдущий - нулевой
    return l;
    /*сформировали заглавное звено списка*/
}
 
void add(List l, char* _data) //добавить елем
{
    if (!l->next) //если список пуст
        l->next->next=l->next->prev=l->next=new Elem; //создаем элемент и сразу зацикливаем его сам на себя (присваивание справа на лево)
    else
    {
        Elem* old_tail=l->next->prev; //сохраняем старый
        l->next->prev=l->next->prev->next=new Elem; //выделяем память (это будет новый хвост),хвост привязываем к последнему элементу, а потом к первому
        old_tail->next->prev=old_tail; //привязываем старый хвост к новому
        l->next->prev->next=l->next; //привязываем голову к хвосту
    }
    l->next->prev->data=_data; //заполняем хвост (выполняется в любом случае)
}
 
bool is_empty(List l) //пустой?
{
    return !l->next; //ну тут ясно. если указатель на следующий нулевой, вернем правду иначе ложь
}
 
int  how_many_with_equal_neighbours(List l) //сколько эл-тов с одинаковыми соседями?
{
    if (!l->next) return 0;
    Elem* tail=l->next->prev;//сохранили хвост
    int i=0;
    do {
     l=l->next;
     i+=(strcmp(l->next->data , l->prev->data)?0:1);
    }
    while ((l!=tail));
    /* эквивалентно:
    while (l!=tail)
    {
        if (!strcmp(l->next->data, l->prev->data) i++;
        l=l->next;
    }*/
    return i;
}
 
bool equal_to_next_exists(List l) //существует ли элемент равный следующему?
{
    if (!l->next) return false;
    Elem* tail=l->next->prev;
    while ((l=l->next) && strcmp(l->data,l->next->data) && l!=tail);
    /*эквивалентно:
    while (l!=tail)
    {
        l=l->next;
        if (!strcmp(l->data,l->next->data)) break;
    }*/
    return l!=tail || strcmp(l->data,l->next->data); //если не дошли до конца, или же если дошли, но последний равен первому
}
 
void inverse_between(List l, char* el) //переставить в обратном порядке между первым и последним вхождениями
{
    if (l->next==l->next->prev) return; //если список зациклен сам на себе, то там один элемент. если список пуст то оба указателя равны нулю
    Elem *first=0, *last=0, *tail=l->next->prev;
    while (l!=tail)
    //нахождение первого и последнего вхождения:
    {
        l=l->next; //переходим к след. элементу
        if (!strcmp(l->data,el)) //если нашли строку
            if (!first) first=l; //если первое вхождение не найдено, то первое вхождение = этому звену
            else last=l; //иначе последнее вхождение = этому звену
    }
    if (!last) return; //если нету последнего вхождения, то елемент встречается один раз, так что выходим
    char* temp;
    while (first!=last && first->next!=last) //1е условие - если у нас нечетное кол-во эл-тов между first и last, 2е условие - если четное.
    {
        //передвигаем указатели навстречу друг другу
        first=first->next;
        last=last->prev;
        //меняем элементы местами
        temp=first->data;
        first->data=last->data;
        last->data=temp;
    }
}
 
void write(List l, std::ostream& out) //написать в поток (cout по умолчанию, но можно использовать файловые потоки)
{
    Elem* tail=l->next->prev;
    while (l!=tail)
    {
        l=l->next;
        out<<l->data<<'\n';
    }
}
 
int main()
{
    printf("Fill the list with 10 elements:\n");
    List list=create();
    add(list,"mm");
    for (int i=1; i<=4; i++)
    {
        char* el=new char[255];
        //если объявим снаружи цикла, адрес строки будет всегда один и тот же, и все элементы списка будут одинаковыми
        scanf("%s",el); //читаем с консоли
        add(list,el); //добавляем в список
    }
    printf("\nYour list:\n");
    write(list,cout); //выводим список в консоль
    if (!is_empty(list))
    {
        printf("Count of elements with equal neighbours: %d\n", how_many_with_equal_neighbours(list));
        printf("Element that equals to his right neighbour "+(equal_to_next_exists(list))?"exists":"does not exist\n");
        printf("Input string: ");
        char* str=new char[255];
        scanf("%s",str);
        inverse_between(list,str);
        printf("\n\nIf at least two \"%s\" are in list, the elements between first and last \"%s\" will be inverted",str,str);
        write(list,cout);
    }
    else printf("The list is empty");
    system("pause");
}
Fiks19
1 / 1 / 0
Регистрация: 07.01.2012
Сообщений: 44
14.01.2013, 19:19  [ТС]     двунаправленные списки С++ #3
просьба показать на моем примере как устроен двусвязный список.
хочу понять как он заносит указатели след элемента и предыдущего, с первого взгляда кажется легко но я не могу уловить сути присвоения.
Посоветуйте где прочитать чтобы понять.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11800 / 6779 / 765
Регистрация: 27.09.2012
Сообщений: 16,829
Записей в блоге: 2
Завершенные тесты: 1
14.01.2013, 23:00     двунаправленные списки С++ #4
Цитата Сообщение от Fiks19 Посмотреть сообщение
Посоветуйте где прочитать чтобы понять.
Нарисуйте на бумаге двусвязный список и попробуйте нарисовать операции, которые необходимо выполнить.

Как вариант, можно изобразить удаление элемента из списка:
двунаправленные списки С++
Fiks19
1 / 1 / 0
Регистрация: 07.01.2012
Сообщений: 44
19.01.2013, 10:26  [ТС]     двунаправленные списки С++ #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
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;
 
 
struct list
{
int key;//адресное поле
list *next;//указатель на следующий элемент
list *prev;//указатель на предыдущий элемент
};
 
list *p=NULL;
list *beg=NULL;
list *head=NULL;
list *last=NULL;
list *temp,*temp1;
int x=0;
int numb=0;
 
list* make_point()
//создание одного элемента
{
 
 list *beg=new(list);//выделяем память под первый элемент
 cout<<x<<" Элемент ";
 cin >> beg->key;//вводим значение информационного поля
 
 
 return beg;//определили конец списка путем присвоению указателю p занчение 0(указатель beg)
}
 
 
void make_list(int n)
//создание списка
{
 
    beg=make_point();//создаем первый элемент
    beg->next=NULL;//следующ обнуляем
    beg->prev=NULL;//пред обнуляем
    head=beg;// присваиваем в head - beg
    p=beg;// присваиваем в p beg
    last=head;//в last присваиваем head;
    x++;
for(int i=1;i<n;i++)
{
    beg=make_point();//создаем один элемент
    beg->next=NULL;//следующ обнуляем
    beg->prev=p; // указваем что предудыщий будет p(beg)
    p->next=beg;//p указваем что следующий элемент будет beg
    last=beg; //в last присваиваем beg
    p=beg;  //в p присваиваем beg
    x++;
 
}
 
}
 
void print_list(void){
 
    temp=head;
    while(temp){
    cout<<temp->key<<"\t";
    temp=temp->next;
    }
    cout << "\n";
}
 
void print_list_1(void){
    temp1=last;
    while(temp1){
    cout << temp1->key<<"\t";
    temp1=temp1->prev;
     }
  cout << "\n";
 }
 
 
 
 
void  del_list_task(int key){
 
 
 
    beg=head;
    while(beg){
        if(beg->key==key && key%2==0)
        {     numb++;
                if(beg==head){
                    head=head->next;
                    if(beg)
                        head->prev=NULL;
                    else
                        last=NULL;
                    if(p==beg)
                        p=head;
                    delete beg;
                    break;
                }
                if (beg==last){
                    last=last->prev;
                    if(last)
                        last->next=NULL;
                    if(p==beg)
                        p=last;
                    delete beg;
                    break;
                }
                beg->prev->next=beg->next;
                beg->next->prev=beg->prev;
                p=beg->prev;//Или next
            delete beg;
            break;
        }
          beg=beg->next;
 
    }
}
 
 
 
int main(){
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 int a, c;
 
 cout << "\t\tЛабораторная работа 8 - Задание 16 - Подзадание 2\n";
 do
        {
        cout<<"\n1. Укажите количество элементов:\n";
        cout<<"2. Ввести данные:\n";
        cout<<"3. Вывод на экран\n";
        cout<<"4. Вывод на экран в обратном порядке\n";
        cout<<"5. Удалить указанный в задании элемент\n";
        cout<<"0. Выход\n";
        cout << "\n\nВведите действие:" ;
        cin>>a;
        switch (a)
                    {
                    case 1:
                         cout <<"Кол-во = " ;
                         x=1;
                         cin>>c;break;
                    case 2:
                         if (x!=0) {
                         make_list(c);}
                         else {cout << "\nERROR:Выполните "<< x+1 << " действие\n ";}
                         break;
                    case 3:
                        if (x!=0 && x>1) {
                         print_list();}
                         else {cout << "\nERROR:Выполните "<< x+1 << " действие\n ";}
                         break;
                    case 4:
                        if (x!=0 && x>1) {
                         print_list_1();}
                         else {cout << "\nERROR:Выполните "<< x+1 << " действие\n ";}
                         break;
                    case 5:
                        if (x!=0 && x>1) {
                          for (int i = 0; i < 50; i++) {
                             if (i%2==0 && numb==0) {
                                  
                                  del_list_task(i);
                                  
                             }
                          }
                         }
                         else {cout << "\nERROR:Выполните "<< x+1 << " действие\n ";}
                         break;
                    }
                    }
 while(a!=0);
 cout << "\n";
 cout << "Завершение!";
 
 
getch();
}
в общем получилось кому надо копи паст
Yandex
Объявления
19.01.2013, 10:26     двунаправленные списки С++
Ответ Создать тему
Опции темы

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