25 / 25 / 7
Регистрация: 02.12.2010
Сообщений: 824
1

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

19.05.2011, 03:11. Показов 3603. Ответов 16
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Собственно... не шарю, как сделать двусвязный! односвязный вроде как получается. Двусвязный как-то и не очень
Конструктор:
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++;
}
что не так? делаю?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.05.2011, 03:11
Ответы с готовыми решениями:

Как создать двусвязный линейный список?
Люди добрые, помогите с лабораторной работой! Нужно выполнить следующее: 3) Двусвязный линейный...

Создать двусвязный список групп факультета, где каждая группа представляет собой односвязный список студентов
Задание: создайте двусвязный список групп факультета. Каждая группа представляет собой односвязный...

Создать двусвязный список
Не могу разобраться с двусвязным списком. Вот код списка: #pragma once #include "ClassPhoto.h"...

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

16
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
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 равные нулю
а последующие узлы просто берут уже из имеющихся узлов нужные указатели
0
25 / 25 / 7
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 04:07  [ТС] 3
первые две вставки это совет мне, как лучше сделать?
да спасибо, вспомнил это функцию.

а вот третья... что конкретно делаем? забыл сказать, что список еще и кольцевой
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
19.05.2011, 04:53 4
тогда только head
при добавлении первого элемента его prev и next должны указывать на него же
при добавлении последующих отсчёт идёт от head

когда элемент добавляется, указателем на предыдущий является адрес элемента, за которым он вставляется
указателем на следующий элемент является адрес элемента, который следовал после элемента, за которым вставляется новый
в старых элементах тоже нужно поменять указатели
next на новый и prev на новый
1
25 / 25 / 7
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 05:26  [ТС] 5
Цитата Сообщение от accept Посмотреть сообщение
указателем на следующий элемент является адрес элемента, который следовал после элемента, за которым вставляется новый
на что должен указывать указатель ->prev? для второго head О.К.
для третьего? для 4го? для 100го?
C++
1
position->prev
= ?
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
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
0
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;
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
19.05.2011, 10:54 8
C++
1
temp->next = NULL;  //последующего элемента нет (добавляем же в конец)
для кольцевого списка это не подходит
0
25 / 25 / 7
Регистрация: 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
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
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() какой-то (нужно просто указатель переставлять)
0
25 / 25 / 7
Регистрация: 02.12.2010
Сообщений: 824
20.05.2011, 03:16  [ТС] 11
C++
1
D->next = D->prev->next
зачем эта строка?
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
20.05.2011, 03:22 12
когда вставляем элемент D после B, B указывает на C
но после вставки B будет указывать на D
а как же тогда получить доступ к C ?
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
20.05.2011, 03:23 13
duplicate
0
25 / 25 / 7
Регистрация: 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
получилось неверно
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
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;
а это что ?
0
25 / 25 / 7
Регистрация: 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
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
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
https://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. кольцевой список
0
21.05.2011, 06:27
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.05.2011, 06:27
Помогаю со студенческими работами здесь

Создать двусвязный список с простыми числами
Помогите, пожалуйста, с лабораторной. Задача: Создать двусвязный список с простыми числами....

Создать двусвязный список согласно условию
Не могли бы вы мне помочь с двусвязными списками. Я тут немного написала, но это всего малая часть....

Создать двусвязный список и найти в нем максимум
прошу напишите пожалуйста прогу, которая создаст двусвязный список и найдёт в нем максимум

Создать двусвязный список состоящий из вещественных чисел
Необходимо создать двусвязный список состоящий из вещественных чисел в интервале от +39,99 до...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru