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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.88
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
#1

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

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

Собственно... не шарю, как сделать двусвязный! односвязный вроде как получается. Двусвязный как-то и не очень
Конструктор:
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++;
}
что не так? делаю?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.05.2011, 03:11     Как создать двусвязный список?
Посмотрите здесь:

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

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

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

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

Создать динамический односвязный или двусвязный список - C++
Помогите, как создать динамический односвязный или двусвязный список(Описать структуру). Я не могу понять, чем он отличается от обычного...

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

Создать, отсортировать, записать в файл двусвязный список чисел - C++
Создать двусвязный список чисел. Отсортировать его путем обмена значений элементов списка. Результаты сортировки записать в файл.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
accept
4820 / 3240 / 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
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 04:07  [ТС]     Как создать двусвязный список? #3
первые две вставки это совет мне, как лучше сделать?
да спасибо, вспомнил это функцию.

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

когда элемент добавляется, указателем на предыдущий является адрес элемента, за которым он вставляется
указателем на следующий элемент является адрес элемента, который следовал после элемента, за которым вставляется новый
в старых элементах тоже нужно поменять указатели
next на новый и prev на новый
VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
19.05.2011, 05:26  [ТС]     Как создать двусвязный список? #5
Цитата Сообщение от accept Посмотреть сообщение
указателем на следующий элемент является адрес элемента, который следовал после элемента, за которым вставляется новый
на что должен указывать указатель ->prev? для второго head О.К.
для третьего? для 4го? для 100го?
C++
1
position->prev
= ?
accept
4820 / 3240 / 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
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
19.05.2011, 10:54     Как создать двусвязный список? #8
C++
1
temp->next = NULL;  //последующего элемента нет (добавляем же в конец)
для кольцевого списка это не подходит
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
4820 / 3240 / 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
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
20.05.2011, 03:16  [ТС]     Как создать двусвязный список? #11
C++
1
D->next = D->prev->next
зачем эта строка?
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.05.2011, 03:22     Как создать двусвязный список? #12
когда вставляем элемент D после B, B указывает на C
но после вставки B будет указывать на D
а как же тогда получить доступ к C ?
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.05.2011, 03:23     Как создать двусвязный список? #13
duplicate
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
4820 / 3240 / 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
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++
Подскажите пожалуйста! Задание на курсовой было такое &quot;Разработать абстрактный тип данных двусвязный список с методами&quot;. Один из методов -...

Как переделать двусвязный список в циклический c++ - C++
Как переделать двусвязный список в циклический c++

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


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

Или воспользуйтесь поиском по форуму:
accept
4820 / 3240 / 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     Как создать двусвязный список?
Ответ Создать тему
Опции темы

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