Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Создать двусвязный список, содержащий целые числа. Удалить все максимальные элементы - C++
Создать двусвязный список, содержащий целые числа. Удалить все максималь* ные элементы. Например, для списка 5 2 9 1 3 7 9 2 9, результат...


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

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

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