Двусвязные списки без ООП

@Vlast001 · Регистрация: 08.01.2019

Студворк — интернет-сервис помощи студентам

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

C++
1
2
3
4
5
6
struct *Node{
    unsigned int size;
    char* data;
    Node* next;
    Node* prev;
};

В конец я запутался когда нашел сайт(версия двусвязного списка на си) где помимо структуры узла заводят структуру для самого списка тогда как я понял должно быть так:

C++
1
2
3
4
5
6
7
8
9
10
struct *Node{
    char* data;
    Node* next;
    Node* prev;
};
struct Dblist{
    unsigned int size;
    Node* head;
    Node* tail;
};

Есть особая разница в том так или так?
Точно понятно что список нужно вывести. А остальное я не понимаю, все что-то пишут на сайтах не дает вообще никакого понятия как работают списки чем больше читаю тем больше вхожу в заблуждение.
Чтобы реализовать двусвязный список нужно написать функции: добавление элемента в конец, в начало списка, так же нужно написать удаление всего списка, а это значит что нужно кроме как завести память под элемент(узел) списка прежде чем его куда-то добавлять нужно было еще в начале завести память под весь список, верно? хоть какие то мои предположения верны?Еще создание нового элемента и добавление его в список это одно и тоже?
Помогите, пожалуйста с этим делом

P.S. Хватит с меня ссылок. Нужен человек который напишет код и все объяснит по нему ИЛИ(и) человек готовый разжевать все до мелочей. Крч суть в том, что те добрые люди который откликнуться должны быть готовы ответь на мои тупые вопросы которые будут возникать по ходу понимания как работает эта структура данных

@Vlast001 · 02.10.2019, 14:33 **[ТС]**

Я сделал такую штуку в int main(int argc, char** argv)

C++
1
2
3
4
5
6
7
8
9
10
11
12
while (!feof(stdin)) 
    {
        fgets(str, 4096, stdin);
        list = push_back(*list,i++,str);
    }
    print(list);
    // тут должен быть вызов функции pop_back? 
    // а вообще возможно объединить функции clearlist и pop_back в одну функцию? Понимаю, что возможно но это же 
//не значит просто перетащить тело одной функции в другую?))
 
    clearlist(*&list); // проблема в этом, я не пойму почему ошибка при компиляции, я пробовал все: (*list), (&list), (list)
так не понял почему ошибка

@oleg-m1973 · 02.10.2019, 14:35

Сообщение от Vlast001

Я сделал такую штуку в int main(int argc, char** argv)

Покажи весь код

@Vlast001 · 02.10.2019, 14:36 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(int argc, char** argv){
    List* list = NULL;
    char str[4096];
    int i = 1;
    while (!feof(stdin)) 
    {
        fgets(str, 4096, stdin);
        list = push_back(*list,i++,str);
    }
    print(list);
    
    clearlist(*&list);
    return 0;
}

или вообще весь?

@oleg-m1973 · 02.10.2019, 14:38

Сообщение от Vlast001

или вообще весь?

Вообще весь.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(int argc, char** argv){
    List list;
    char str[4096];
    int i = 1;
    while (!feof(stdin)) 
    {
        fgets(str, 4096, stdin);
        push_back(list, i++, str);
    }
    print(list);
    
    clearlist(list);
    return 0;
}

@Vlast001 · 02.10.2019, 14:44 **[ТС]**

Кликните здесь для просмотра всего текста

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
100
101
102
103
104
105
106
107
#include <iostream>
#include <cstring>
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <crtdbg.h>
using namespace std;
typedef unsigned int uint;
struct Node
{
    uint size;
    char* data;
    Node* next;
    Node* prev;
}; 
 
struct List
{
    Node *head = NULL;
    Node *tail = NULL;
};
 
void push_front(List& list, int size, char* data){
    Node* node = new Node;
    node->size = size;
    node->data = data;
    node->next = list.head;
    node->prev = NULL;
    
    if(!list.head){
        list.tail = node;
    }
    
    list.head = node;
}
 
List* push_back(List& list, int size, char* data){
    Node* node = new Node;
    node->size = size;
    node->data = data;
    node->prev = list.tail;
    node->next = NULL;
    
    if(!list.tail){
        list.tail = list.head = node;        // Åñëè ñïèñîê ïóñòîé, òî ãîëîâà è õâîñò óêàçûâàþò íà íîâûé ýëåìåíò
    }
    else{
        list.tail->next = list.tail = node; // Åñëè íå ïóñòîé, òî ïåðåìåùàåì õâîñò
    }
}
 
void pop_front(List &list){
    if(!list.head)
        return;
 
    Node* node = list.head;
    list.head = list.head->next;
    if (list.head)
        list.head->prev = NULL;
    else
        list.tail = NULL;
    
    delete node;
}
 
void pop_back(List &list){
    if(!list.tail)
        return;
    Node* node = list.tail;
    list.tail = list.tail->prev;
    if(list.tail)
        list.tail->next = NULL;
    else
        list.head = NULL;
    delete node;
    return;
}
 
List* clearlist(List &list){
    while(list.head){
        pop_front(list);
    }
}
 
void print(List *list)
{
    
    for (Node *node = list->head; node; node = node->next)
        //std::cout << node->data << std::endl;
        printf("%5d %s ", node->size, node->data);
}
 
int main(int argc, char** argv){
    List* list = NULL;
    char str[4096];
    int i = 1;
    while (!feof(stdin)) 
    {
        fgets(str, 4096, stdin);
        list = push_back(*list,i++,str);
    }
    print(list);
    
    clearlist(*&list);
    return 0;
}

@oleg-m1973 · 02.10.2019, 15:34

C++
1
2
3
4
5
6
7
void print(const List &list)
{
    
    for (const Node *node = list.head; node; node = node->next)
        //std::cout << node->data << std::endl;
        printf("%5d %s ", node->size, node->data);
}

Добавлено через 43 секунды

C++
1
2
3
4
5
6
7
struct Node
{
    uint size;
    std::string data;
    Node* next;
    Node* prev;
};

@Vlast001 · 02.10.2019, 15:38 **[ТС]**

const, я кстати тоже дописал, я еще в мейне после принта вызвал pop_back(list), а потом clearlist(list)...ну у них одинаковая ошибка: [Error] invalid initialization of reference of type 'List&' from expression of type 'List*'
поп_бэк без изменений,а клирлист сейчас такой:

C++
1
2
3
4
5
void clearlist(List &list){
    while(list.tail){
        pop_back(list);
    }
}

Добавлено через 40 секунд

Сообщение от oleg-m1973

string data;

стринг?

@oleg-m1973 · 02.10.2019, 15:41

Сообщение от Vlast001

const, я кстати тоже дописал, я еще в мейне после принта вызвал pop_back(list), а потом clearlist(list)...ну у них одинаковая ошибка: [Error] invalid initialization of reference of type 'List&' from expression of type 'List*'

Я ж вроде тебе написал выше функцию main

Сообщение от Vlast001

стринг?

Конечно. Либо массив

C++
1
2
3
4
5
6
7
struct Node
{
    uint size;
    char data[256];
    Node* next;
    Node* prev;
};

@Vlast001 · 02.10.2019, 15:52 **[ТС]**

И раз clearlist(List &list) очищает весь список при помощи pop_back, стоит ли вообще в мейне вызывать pop_back?

Добавлено через 6 минут

Сообщение от oleg-m1973

Я ж вроде тебе написал выше функцию main

А только щас заметил, чем она отличается от моего мейна, с ней все скомпилировалось) Спасибо. Но не много не понимаю почему List list вместо List* list?

Добавлено через 3 минуты
У меня в текстовом файле три строки:
123
weqrqre
44ff4
Почему мой вывод такой:
"1 44ff4
2 44ff4
3 44ff4" ? Где я прокололся?

@oleg-m1973 · 02.10.2019, 15:53

Сообщение от Vlast001

3 44ff4" ? Где я прокололся?

Именно там, где я тебе написал

@Vlast001 · 02.10.2019, 16:04 **[ТС]**

Сообщение от oleg-m1973

Именно там, где я тебе написал

ты про

Сообщение от oleg-m1973

C++Выделить код
1
2
3
4
5
6
7
void print(const List &list)
{
for (const Node *node = list.head; node; node = node->next)
* * * * //std::cout << node->data << std::endl;
* * * * printf("%5d %s ", node->size, node->data);
}
Добавлено через 43 секунды
C++Выделить код
1
2
3
4
5
6
7
struct Node
{
* * uint size;
* * std::string data;
* * Node* next;
* * Node* prev;
};

??? Если да, то мой компилятор ругается на node->data, если напишу node.data, то он говорит может вы имели ввиду "->".

@oleg-m1973 · 02.10.2019, 16:08

Сообщение от Vlast001

??? Если да, то мой компилятор ругается на node->data, если напишу node.data, то он говорит может вы имели ввиду "->".

C++
1
printf("%5d %s ", node->size, node->data.c_str());

@Vlast001 · 02.10.2019, 16:15 **[ТС]**

Сообщение от oleg-m1973

data.c_str())

Вот именно по этому я избигаю стрингов))

Я после %s написал \n и получилось такое

Кликните здесь для просмотра всего текста

3 44ff4
2 weqrqre

1 123

Ну, я поменял на хвост, но я не об этом. Между строкой 1 и 2 пустая строка печатается, как я догадываюсь причина в том, что fgets читает символ новой строки, как мне вывести нормально?)

@Vlast001 · 03.10.2019, 16:46 **[ТС]**

oleg-m1973, Снова здраствуйте, можете еще чуток помочь по списку, пожалуйста

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node
{
    uint size;
    string data;
    Node* next;
    Node* prev;
}; 
 
struct List
{
    Node *head = NULL;
    Node *tail = NULL;
};

Такие структуры.

Кликните здесь для просмотра всего текста

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
void push_front(List& list, int size, char* data){
    Node* node = new Node;
    node->size = size;
    node->data = data;
    node->next = list.head;
    node->prev = NULL;
    
    if(!list.head){
        list.tail = node;
    }
    
    list.head = node;
}
void pop_front(List &list){
    if(!list.head)
        return;
 
    Node* node = list.head;
    list.head = list.head->next;
    if (list.head)
        list.head->prev = NULL;
    else
        list.tail = NULL;
    
    delete node;
}
void clearlist(List &list){
    while(list.tail){
        pop_back(list);
    }
}

Функции добавления и удаления

Вот такие вывод и мейн:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void print(const List &list)
{
    for (const Node *node = list.head; node; node = node->next)
        printf("%5d. %s", node->size, node->data.c_str());
}
int main(int argc, char** argv){
    List list;
    char str[4096];
    int i = 1;
    while (!feof(stdin)) 
    {
        fgets(str, 4096, stdin);
        push_front(list, i++, str);
    }
    print(list);
    
    clearlist(list);
    return 0;
}

Проблема собственно в том, что у меня в файле три строки
123
weqrqre
44ff4
А вывод в консоле такой:
4. 44ff4
3. 44ff4
2. weqrqre
1. 123
Во первых должно на единицу начинаться, а не заканчиваться, во-вторых откуда берется еще одна строка?!

@oleg-m1973 · 03.10.2019, 16:52

Сообщение от Vlast001

Во первых должно на единицу начинаться, а не заканчиваться,

Это потому что ты в голову добавляешь. Добавляй в хвост

Добавлено через 2 минуты

Сообщение от Vlast001

во-вторых откуда берется еще одна строка?!

Неправильно начитываешь файл.
Наверное, надо проверять, что возвращает fgets или что-то типа того

@Vlast001 · 03.10.2019, 17:00 **[ТС]**

Сообщение от oleg-m1973

Это потому что ты в голову добавляешь. Добавляй в ховст

Спасибо, все стало на места, а чего-то подумал раз вывод с головы, то и добавлять надо с головы

Нужно то в хвост, еще раз спасиб)
Вы случайно не знаете чем может быть вызвано, то что последняя строка выводится дважды это касается списка или того как я читаю файл своим fgets ?

@oleg-m1973 · 03.10.2019, 17:03

Сообщение от Vlast001

Вы случайно не знаете чем может быть вызвано, то что последняя строка выводится дважды это касается списка или того как я читаю файл своим fgets ?

Попробуй

C++
1
2
3
4
5
6
7
    for(;;)
    {
        fgets(str, 4096, stdin);
        if (feof(stdin))
           break;
        push_front(list, i++, str);
    }

@Vlast001 · 03.10.2019, 18:18 **[ТС]**

Сообщение от oleg-m1973

Наверное, надо проверять, что возвращает fgets или что-то типа того

Ясно, пойду читать за fgets. Или может лучше перейти на fstream, если в нем конечно предусмотрен: >a.exe <a.txt ?

Добавлено через 2 минуты

Сообщение от oleg-m1973

for(;

* * {
* * * * fgets(str, 4096, stdin);
* * * * if (feof(stdin))
* * * * * *break;
* * * * push_front(list, i++, str);
* * }

Помогло...теперь точно документацию перечитаю

Добавлено через 1 час 10 минут
oleg-m1973, Извиняюсь за вопрос не по теме, просто подскажите в правильном ли направлении я мыслю.
Если я захочу поменять местами две разные data, то есть просто их свапнуть то мне нужно пройтись по всем узлам в поисках data1 и присвоить ей временную переменную, а потом тоже самое повторить с data2 и после этого сделать что-то типом temp=data1; data1=data2; data2=temp; ?

@oleg-m1973 · 03.10.2019, 20:08

Сообщение от Vlast001

oleg-m1973, Извиняюсь за вопрос не по теме, просто подскажите в правильном ли направлении я мыслю.
Если я захочу поменять местами две разные data, то есть просто их свапнуть то мне нужно пройтись по всем узлам в поисках data1 и присвоить ей временную переменную, а потом тоже самое повторить с data2 и после этого сделать что-то типом temp=data1; data1=data2; data2=temp; ?

Нифига не понял, что ты пытаешься сделать.
Могу только сказать, что в двусвязном списке обычно дешевле поменять местами ноды, чем обменивать их значения

@Vlast001 · 03.10.2019, 20:25 **[ТС]**

Сообщение от oleg-m1973

Нифига не понял, что ты пытаешься сделать.

Я пытаюсь реализовать функцию, которая меняет местами два указанных нода в линейном двусвязном списке.

Сообщение от oleg-m1973

обычно дешевле поменять местами ноды, чем обменивать их значения

Что значит дешевле?)

Новые блоги и статьи Все статьи Все блоги /
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .