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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .