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

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

Войти
Регистрация
Восстановить пароль
 
Fiks19
1 / 1 / 0
Регистрация: 07.01.2012
Сообщений: 44
#1

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

13.01.2013, 11:41. Просмотров 914. Ответов 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();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2013, 11:41     Разобрать устройство двусвязного списка
Посмотрите здесь:

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

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

Арифметика Класса Двусвязного списка - C++
Всем привет. тут такая проблема есть у меня программа создание двусвязного циклического списка и действия над ним. и надо создать...

Сериализация и десериализация двусвязного списка - C++
Всем доброго времени суток! Ребят помогите реализовать функции сериализации и десериализации двусвязного списка. Заранее спасибо

Добавление в конец двусвязного списка - C++
Помогите найти ошибку в коде: не работает добавление в конец. Список формируется добавлением в начало! Функция добавления: ...

Удаление структуры из двусвязного списка - C++
Доброго времени суток! Пытаюсь создать функцию удаления из списка структуры, не выполняется цикл while в функции del() в чем я не прав? ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nixy
ComfyMobile
400 / 281 / 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
Модератор
Эксперт CЭксперт С++
13052 / 7315 / 814
Регистрация: 27.09.2012
Сообщений: 18,052
Записей в блоге: 3
Завершенные тесты: 1
14.01.2013, 23:00     Разобрать устройство двусвязного списка #4
Цитата Сообщение от Fiks19 Посмотреть сообщение
Посоветуйте где прочитать чтобы понять.
Нарисуйте на бумаге двусвязный список и попробуйте нарисовать операции, которые необходимо выполнить.

Как вариант, можно изобразить удаление элемента из списка:
Разобрать устройство двусвязного списка
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.01.2013, 10:26     Разобрать устройство двусвязного списка
Еще ссылки по теме:

Сортировка двусвязного списка вставками - C++
Добрый день, есть готовый двусвязный список. Нужно было реализовать сортировку вставками любых чисел. В комментариях main() оставил...

Функция удаления из двусвязного списка - C++
Создал двусвязный список на основе класса, работают ввод элементов в список и вывод всего списка. Помогите пожалуйста с функцией удаления...

Шейкерная сортировка двусвязного списка - C++
Здравствуйте! У меня возникла проблема с сортировкой двусвязного списка. Получилось реализовать двусвязный список и отдельно...

Удаление элемента из двусвязного списка - C++
Надо удалить элемент из двусвязного списка, если выполняется условие (2013-(current-&gt;god)&lt;3). Я пытаюсь как могу, но что то все равно...

Удаление из двусвязного циклического списка - C++
Начал реализовывать структуру данных - Фибоначчиевы кучи. Столкнулся с проблемой при написании функции удаления минимального элемента....

Удаление элемента из двусвязного списка - C++
Собственно, в коде все рабочее, кроме удаления. После ввода элемента выдает ошибку 0xC0000005. Где-то напутал с выделением памяти? ...


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

Или воспользуйтесь поиском по форуму:
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     Разобрать устройство двусвязного списка
Ответ Создать тему
Опции темы

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