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

Как создать двусвязный список? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.88
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 03:11     Как создать двусвязный список? #1
Собственно... не шарю, как сделать двусвязный! односвязный вроде как получается. Двусвязный как-то и не очень
Конструктор:
C++
1
2
3
4
5
    list() {
        head = NULL;
        count = 0;
        go_first();
    }
Метод класса:
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
void list::insert() {
    nodes* new_node = new nodes;
    char space[2] = " "; 
 
    el.InElement();
 
    strcpy(new_node->data, el.artist); strcat(new_node->data, space);
    strcat(new_node->data, el.name); strcat(new_node->data, space);
    strcat(new_node->data, el.year); strcat(new_node->data, space);
    strcat(new_node->data, el.price); strcat(new_node->data, space);
 
    if(position != NULL) {
        if(count == 1) 
            positionPrev = head;
        new_node->next = position->next;
        position->next = new_node;
        new_node->prev = position->prev;
        go_next();
    } else {
        position = head = new_node;
        positionPrev = position->prev;
        
    }
 
    count++;
}
что не так? делаю?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
19.05.2011, 03:56     Как создать двусвязный список? #2
C++
1
2
3
4
strcpy(new_node->data, el.artist); strcat(new_node->data, space);
        strcat(new_node->data, el.name); strcat(new_node->data, space);
        strcat(new_node->data, el.year); strcat(new_node->data, space);
        strcat(new_node->data, el.price); strcat(new_node->data, space);
C++
1
2
    sprintf(new_node->data, "%s %s %s %s ",
            el.artist, el.name, el.year, el.price);
C++
1
2
    head->prev = NULL;
    tail->next = NULL;
нужно сделать, чтобы первый узел, который появляется в списке, сразу имел prev и next равные нулю
а последующие узлы просто берут уже из имеющихся узлов нужные указатели
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 04:07  [ТС]     Как создать двусвязный список? #3
первые две вставки это совет мне, как лучше сделать?
да спасибо, вспомнил это функцию.

а вот третья... что конкретно делаем? забыл сказать, что список еще и кольцевой
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
19.05.2011, 04:53     Как создать двусвязный список? #4
тогда только head
при добавлении первого элемента его prev и next должны указывать на него же
при добавлении последующих отсчёт идёт от head

когда элемент добавляется, указателем на предыдущий является адрес элемента, за которым он вставляется
указателем на следующий элемент является адрес элемента, который следовал после элемента, за которым вставляется новый
в старых элементах тоже нужно поменять указатели
next на новый и prev на новый
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 05:26  [ТС]     Как создать двусвязный список? #5
Цитата Сообщение от accept Посмотреть сообщение
указателем на следующий элемент является адрес элемента, который следовал после элемента, за которым вставляется новый
на что должен указывать указатель ->prev? для второго head О.К.
для третьего? для 4го? для 100го?
C++
1
position->prev
= ?
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
19.05.2011, 06:35     Как создать двусвязный список? #6
A <-> B <-> C

элемент D вставляется за B

D->prev = B
D->next = D->prev->next
D->next->prev = D

A <-> B <-> D <-> C

а вместо head тогда curr
JmBeats
0 / 0 / 0
Регистрация: 17.05.2011
Сообщений: 10
19.05.2011, 08:15     Как создать двусвязный список? #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void List::addToList(string data)   //реализация функции добавления
{
    Element *temp = new Element;        //создается временный элемент
    if(pHead == NULL)           //если это первый элемент, то
    {
temp->pred = NULL;      //обнуляем указатель на предшествующий 
//элемент т.к. его нет
        temp->next = NULL;      //то же самое с последующим элементом
                pHead = temp;       //"голова" указывает на созданный элемент
    }
else                    //если не первый, то
                pPrev->next = temp;     //предыдущий указывает на него
 
    temp->data = data;          //копируем данные
    temp->next = NULL;  //последующего элемента нет (добавляем же в конец)
    temp->pred = pPrev;     //указываем на предыдущий элемент, на который «нацелен» pPrev
    pPrev = temp;     //а теперь хвостовой элемент указывает на последний (добавленный)
    countElem++;      //увеличиваем счетчик элементов в списке
}
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
void List::printList()              //реализация функции вывода на экран списка
{
    Element *pTemp = pHead;     //создается временный элемент
 
    if (pHead == NULL)          //если список пуст, то 
    {
        cout << "Spisok pust";  //выводим соответствующее сообщение
    }
    else                    //если все такие он не пуст, то
    {
        cout << "Spisok ->: ";      
        while(pTemp != NULL)    //пока врем. элем. не будет указывать на хвост
        {
            cout << pTemp->data + ' ';  //выводим данные элемента
            pTemp = pTemp->next;    //и переходим на следующий за ним элем.
        }
    cout << endl;
}
 
 
void List::printElement(int numb)           //реализация функции вывода на экран списка
{
 
Element *pTemp = pHead;     //создаем временный элемент
 
if ((numb>countElem) || (numb<1))    //если указанный элемент не существует, то
        cout << "Takogo elementa net" << endl;  //выводим предупреждение на экран
    else
    {
        for(int i=1; i!=numb; i++)  //иначе, переходим до этого элемента
        {
            pTemp = pTemp->next;
        }
cout << "Element " << numb << " :" << pTemp->data << endl;
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
19.05.2011, 10:54     Как создать двусвязный список? #8
C++
1
temp->next = NULL;  //последующего элемента нет (добавляем же в конец)
для кольцевого списка это не подходит
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 15:30  [ТС]     Как создать двусвязный список? #9
Цитата Сообщение от accept Посмотреть сообщение
A <-> B <-> C

элемент D вставляется за B

D->prev = B
D->next = D->prev->next
D->next->prev = D

A <-> B <-> D <-> C

а вместо head тогда curr
это вообще к чему?
ребят понимаете... программирование такая штука... )) каждый видит все по своему))
я понимаю что список должен выглядеть так, как вы показали.
Но не напишешь же буквы от А до Я и для каждой A ->prev = Я, B->prev = A!!! и т.д.
нужна формула что ли какая-то
как написать конструктор для двусвязного колцевого списка и как написать метод добавления элемента в список после текущего.

Добавлено через 1 минуту
Не не. Я не прошу написать мне кодом. Сам хочу попытаться понять!
Но пока тут и не пахнет какими-то общими формулами! А именно они и нужны для того чтобы понять просто.

Я понимаю как сделать первый элемент.
Не понимаю как сделать 2 3 4 5 и 199 и 289
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.05.2011, 02:40     Как создать двусвязный список? #10
Цитата Сообщение от VladSharikov
это вообще к чему?
Цитата Сообщение от VladSharikov
Но не напишешь же буквы от А до Я и для каждой A ->prev = Я, B->prev = A!!! и т.д.
это описание того, что должно быть в методе вставки

вместо вот этого
C++
1
2
3
4
5
6
7
8
9
10
11
12
if(position != NULL) {
                if(count == 1) 
                        positionPrev = head;
                new_node->next = position->next;
                position->next = new_node;
                new_node->prev = position->prev;
                go_next();
        } else {
                position = head = new_node;
                positionPrev = position->prev;
                
        }
у тебя тут какие-то лишние указатели: head, positionPrev
go_next() какой-то (нужно просто указатель переставлять)
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
20.05.2011, 03:16  [ТС]     Как создать двусвязный список? #11
C++
1
D->next = D->prev->next
зачем эта строка?
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.05.2011, 03:22     Как создать двусвязный список? #12
когда вставляем элемент D после B, B указывает на C
но после вставки B будет указывать на D
а как же тогда получить доступ к C ?
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.05.2011, 03:23     Как создать двусвязный список? #13
duplicate
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
20.05.2011, 04:05  [ТС]     Как создать двусвязный список? #14
C++
1
2
3
4
5
6
7
8
9
10
11
    if(position != NULL) {
        new_node->next = position->next;
        position->next = new_node;
        new_node->prev = position->prev;
        position->prev = position;
        go_next();
    } else {
        new_node->next = new_node; 
        new_node->prev = head;
        position = head = new_node;
    }
в общем... таким образом если сделать, то список выводится вперед.. но назад выводит последний добавленный и первый первый первый.

вот так вот..

acess я не понимаю что этим кодом вы мне хотите сказать

Добавлено через 3 минуты
в шапке темы посмотрите как я сделал основу списка. вас это устраивает??
быть может вы говорите как сделать для другой основы

Добавлено через 35 секунд
то что вы отписал и
D-next = B
получилось неверно
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.05.2011, 10:47     Как создать двусвязный список? #15
Цитата Сообщение от VladSharikov
то что вы отписал и
D-next = B
получилось неверно
а что получилось ?

Цитата Сообщение от VladSharikov
acess я не понимаю что этим кодом вы мне хотите сказать
прежде чем писать код, нужно представить, что он будет делать

Цитата Сообщение от VladSharikov
C++
1
2
3
new_node->next = new_node; 
new_node->prev = head;
position = head = new_node;
какова роль указателя head ? для чего он сделан ?
список кольцевой - должен быть либо head, либо position

Цитата Сообщение от VladSharikov
C++
1
new_node->prev = position->prev;
а это что ?
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
20.05.2011, 16:02  [ТС]     Как создать двусвязный список? #16
тэкс....
я и пытаюсь себе представить что делает ваш код. но вы же не напишите D и B прямо в коде так?
мы вставляем D(новый эл.) после B(текущ. позиция), так?
я заменил B на position, D на new_node.
C++
1
new_node->prev = position->prev;
значится что? мы должны указателю new_node->next присвоить position->next.

а что получилось ?
список создался. выводит не то.
обратный вывод такой. 1 3 1(список из 3х эл) или 3 1 3. прямой вывод такой.... 1 1 3.

какова роль указателя head ? для чего он сделан ?
список кольцевой - должен быть либо head, либо position
head - начало списка. этим кодом мы ставим posisition в начало списка и присваиваем ему new_node
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.05.2011, 06:27     Как создать двусвязный список?
Еще ссылки по теме:

C++ Создать двусвязный список с простыми числами
C++ Создать двусвязный список
Создать динамический односвязный или двусвязный список C++

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

Или воспользуйтесь поиском по форуму:
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
21.05.2011, 06:27     Как создать двусвязный список? #17
Цитата Сообщение от VladSharikov
список создался. выводит не то.
Код
A <-> B <-> C

элемент D вставляется за B

D->prev = B
D->next = D->prev->next
D->next->prev = D

A <-> B <-> D <-> C
тебе вот это вот ещё объяснить ?
A <-> B - узел A указывает на узел B, узел B указывает на узел A
http://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix}A->next == B\\B->prev == A<br />
 \end{matrix}\right.
элемент D, который вставляется, естественно создаётся
тут показано, как у него указатели выставить

Цитата Сообщение от VladSharikov
head - начало списка. этим кодом мы ставим posisition в начало списка и присваиваем ему new_node
где начало у кольцевого списка ?

Цитата Сообщение от VladSharikov
мы вставляем D(новый эл.) после B(текущ. позиция), так?
какая текущая позиция ? зачем она нужна ?

wiki. кольцевой список
Yandex
Объявления
21.05.2011, 06:27     Как создать двусвязный список?
Ответ Создать тему
Опции темы

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