Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Правила Карта Блоги Социальные группы Поиск Сообщения за день  
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
1 / 1 / 1
Регистрация: 07.01.2012
Сообщений: 44
1

Разобрать устройство двусвязного списка

13.01.2013, 11:41. Просмотров 1103. Ответов 4
Метки нет (Все метки)
Ребят помогите понять как это устроено, общий смысл я понял.
Не могу разобраться как выводить по указателям. У меня выводит с конца в начало как вывести наоборот.
Как вообще правильнее оперировать этими указателями.

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();
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 13.01.2013, 11:41
Ответы с готовыми решениями:

Даны числа D1 и D2 и указатель P0 на один из элементов непустого двусвязного списка. Добавить в начало списка новый
Даны числа D1 и D2 и указатель P0 на один из элементов непустого двусвязного списка. Добавить в...

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка
Здравствуйте! Возникла проблема с программой. Тема: &quot;Сортировка двусвязного списка путем исключения...

Элемент двусвязного списка содержит указатель на строку. Вставить строку в конец списка
Элемент двусвязного списка содержит указатель на строку. Вставить строку в конец списка. В список...

Cортировка двусвязного списка
Ну, в общем задание в названии. Нужно отсортировать двусвязный список, методом пузырька....

4
ComfyMobile
400 / 281 / 34
Регистрация: 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");
}
0
1 / 1 / 1
Регистрация: 07.01.2012
Сообщений: 44
14.01.2013, 19:19  [ТС] 3
просьба показать на моем примере как устроен двусвязный список.
хочу понять как он заносит указатели след элемента и предыдущего, с первого взгляда кажется легко но я не могу уловить сути присвоения.
Посоветуйте где прочитать чтобы понять.
0
Don't worry, be happy
16958 / 9837 / 1895
Регистрация: 27.09.2012
Сообщений: 24,392
Записей в блоге: 2
14.01.2013, 23:00 4
Цитата Сообщение от Fiks19 Посмотреть сообщение
Посоветуйте где прочитать чтобы понять.
Нарисуйте на бумаге двусвязный список и попробуйте нарисовать операции, которые необходимо выполнить.

Как вариант, можно изобразить удаление элемента из списка:
Разобрать устройство двусвязного списка
0
1 / 1 / 1
Регистрация: 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();
}
в общем получилось кому надо копи паст
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 19.01.2013, 10:26

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Реализация двусвязного списка
Реализовать двусвязный список. Над списками нужно выполнять следующие операции: - начальное...

Реверс двусвязного списка
Столкнулся с задачей написать функцию реверса двусвязного списка. Часа 3 сушил себе мозг с копиями...

Методы двусвязного списка
В cpp-файле в методах: Add(47-51); Remove(97 - 102); Insert(142-146), не понятно что происходит в...

Реализация двусвязного списка
Нужно реализовать двусвязный список(с комментариями для чайника ) Добавлено через 13 минут...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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