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

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

Войти
Регистрация
Восстановить пароль
 
septe-mber
0 / 0 / 0
Регистрация: 02.01.2013
Сообщений: 123
#1

Как работает вставка в двусвязном списке? - C++

30.07.2013, 22:33. Просмотров 391. Ответов 3
Метки нет (Все метки)

Привет всем! я не понимаю как работает вставка в двусвязном списке, а точне не понимаю зачем писать нужно вот такую строку cur->next->prev = tmp; в функции insert() ? почему если написать такую строку pm_tail->next->prev = tmp; в функции push_back() , то вставка в конец списка не работает, и наоборот если эту строчку cur->next->prev = tmp; не написать в функции insert(), будет вставлять значение только по указатель next. что это строчка означает ?
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
#include <iostream>
 
using namespace std;
 
class List
{
public:
    List() = default;
 
    void push_back(const int value)
    {
        Node* tmp = new Node;
        tmp->data = value;
        tmp->next = nullptr;
        tmp->prev = nullptr;
 
        if(pm_head == nullptr)
            pm_head = pm_tail = tmp;
        else
        {
            tmp->next = pm_tail->next;
            tmp->prev = pm_tail;
            //pm_tail->next->prev = tmp;
            pm_tail->next = tmp;
            pm_tail = tmp;
        }
    }
 
    void insert(const int index, const int value)
    {
        Node* tmp = new Node;
        tmp->data = value;
        tmp->next = nullptr;
        tmp->prev = nullptr;
 
        Node* cur = pm_head;
        for(int i = 1; i < index - 1 && cur->next != nullptr; i++)
            cur = cur->next;
 
        tmp->next = cur->next;
        tmp->prev = cur;
        cur->next->prev = tmp; //вот эта строчка
        cur->next = tmp;
    }
 
    void show() const
    {
        cout<<"next"<<endl;
        Node* tmp = pm_head;
        while(tmp)
        {
            cout<<tmp->data<<'\t';
            tmp = tmp->next;
        }
        cout<<endl<<endl;
        cout<<"prev"<<endl;
        tmp = pm_tail;
        while(tmp)
        {
            cout<<tmp->data<<'\t';
            tmp = tmp->prev;
        }
        cout<<endl<<endl;
    }
 
    ~List()
    {
        Node* tmp = pm_head;
        while(tmp)
        {
            tmp = tmp->next;
            delete pm_head;
            pm_head = tmp;
        }
    }
 
private:
    struct Node
    {
        int data;
        Node* prev, *next;
    };
    Node* pm_head = nullptr;
    Node* pm_tail = nullptr;
};
 
int main()
{
    List l;
    l.push_back(54);
    l.push_back(12);
    l.push_back(8);
    l.push_back(78);
    l.push_back(23);
    l.insert(3, 555);
    l.insert(6, 111);
    l.show();
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2013, 22:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как работает вставка в двусвязном списке? (C++):

Как организовать поиск в двусвязном списке? - C++
Есть класс двусвязный список где каждый элемент имеет большое количество полей (Имя, Фамилия, Отчество, номер телефона, дата рождения ) ,...

Как найти k-ый элемент в двусвязном списке? - C++
Задание состоит в том, чтобы найти m-ый элемент в двусвязном списке и вывести его на экран.вот моя попытка void Spisok:: find() { ...

Как в двусвязном списке сделать перегрузку оператора присваивание - C++
Добрый день. Мне нужно перегрузить оператор =, так чтобы один объект класса &quot;Двусвязный список&quot; присваивался другом объекту. class...

Ошибка в двусвязном списке - C++
Задача - сделать очередь с приоритетным исключением на основе двухсвязного списка. Проблема в том, что элементы не всегда становяться по...

Поиск в двусвязном списке - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;cstring&gt; #include &lt;windows.h&gt; using namespace std; struct element{ ...

Сортировка в двусвязном списке - C++
Здравствуйте! Есть класс List, в него вложен класс Node, в Node в качестве данных используется класс Circle Задание: Написать для...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
30.07.2013, 22:56 #2
могу посоветовать нарисовать на бумажке учавствующие во вставке узлы со стрелочками , указывающими кто на что указывает до вставки и потом каждое действие из строчек 21-25 прорисовывать на бумажке. тогда может быть ясно станет что происходит при вставке.
2
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
30.07.2013, 22:58 #3
двусвязной список
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6467 / 3115 / 306
Регистрация: 04.12.2011
Сообщений: 8,590
Записей в блоге: 4
30.07.2013, 23:01 #4
Послушайте совета DU, ведь ошибок многовато. Вот фрагмент из push_back:
Цитата Сообщение от septe-mber Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
else //список не пуст
{ 
tmp->next = pm_tail->next;//зачем? pm_tail->next установлен в 0 (должен быть), а tmp->next Вы установили до входа в блок if
tmp->prev = pm_tail;// это нормально 
//pm_tail->next->prev = tmp;//это не нужно:
 pm_tail->next=tmp;//это нормально: новый элемент связывается с  pm_tail
 pm_tail = tmp; //это нормально: tmp стал замыкающим.
}
Не компилировал, но вроде похоже.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2013, 23:01
Привет! Вот еще темы с ответами:

Поиск в двусвязном списке - C++
Доброго времени суток. Помогите написать код, который ищет в двусвязном списке елемент по его значению. Тоесть идёт запрос в консоле...

Использование итератора в двусвязном списке - C++
Всем добрый день/вечер. Я сегодня уже обращался к форумчанам за помощью, и мне помогли, но видать я совсем тупой :( Мне помогли через...

Нахождение элемента в двусвязном списке - C++
Суть в том, что у меня есть двусвязный список, в котором нужно выяснить есть ли в нём тот или иной элемент. #include &lt;iostream&gt; ...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.07.2013, 23:01
Ответ Создать тему
Опции темы

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