Двунаправленный (двусвязанный) список

@Boogie Woogie · Регистрация: 20.07.2016

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

Приветы!

В общем, нужна программа, которая:

Из
-двунаправленного списка
-ищет вещественное число

и выполняет следующие действия:
Находит вещественное число по числу, введенному с клавиатуры,и после него добавить новое число.

Я так и не понял, как работают списки. Нет, суть я понял, в теории я понимаю что они такое и для чего нужны, но когда время приходит к делу, то не могу понять, как его хотя бы создавать.

В общем, нужна помощь.

@Mathist · 13.11.2016, 04:34

Boogie Woogie, если ты понимаешь как устроены списки, давай попробуем разобраться что же тебе непонятно в реализации. Для хранения в памяти двунаправленного списка используется следующая структура:

C
1
2
3
4
5
struct DList {
    double data;
    struct DList *next;
    struct DList *prev;
};

Data это наши вещественые числа. Next указатель на следующий элемент, Prev указатель на предыдущий элемент. Далее создаем список:

C
1
2
3
    DList list;
    list.next = NULL;
    list.prev = NULL;

Указателям присваиваем Null, чтобы было понятно, что в списке один элемент. Для добавления элемента нужно выделить память функцией malloc. После выделения обязательно настраиваем связи как у двунаправленного списка.

C
1
2
3
4
5
    list.next = (DList *) malloc(sizeof(DList));
 
    list.next->data = 20;
    list.next->next = NULL;
    list.next->prev = &list;

Таким образом мы добавили элемент в список и у нас получился список из двух элементов. Движение по списку осуществляется с помощью отдельного указателя. Объявляем указатель на список и присваиваем ему адрес списка, а затем идем по списку присваивая в цикле адрес следующего элемента, вот так:

C
1
2
3
4
5
    DList *walk = &list;
    while (walk) {
        printf("%4.2f ", walk->data);
        walk = walk->next;
    }

Это выводит на экран все элементы в списке. Предлагаю тебе самому подумать над функциями добавления, поиска, вставки и удаления всех элементов всписка. Очистка памяти осуществляется с помощью функции free(). Главное с чем может возникнуть проблема это настройка связей списка. И внимательно при удалении всех элементов, чтобы не получилось утечки памяти. Если что-то будет непонятно под спойлером будет ответ. Надеюсь ты постараешься все сделать сам.

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

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
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
 
struct DList {
    double data;
    struct DList *next;
    struct DList *prev;
};
 
int Add(DList *pL, double data) {
    if (pL != NULL) {
 
        while (pL->next) {
            pL = pL->next;
        }
        pL->next = (DList *) malloc(sizeof(DList));
 
        pL->next->prev = pL;
        pL = pL->next;
        pL->data = data;
        pL->next = NULL;
    } else
        return -1;
    return 0;
}
 
DList *Find(DList *pL, double data) {
 
    DList *result = NULL;
    if (pL) {
        while (pL->next && !result) {
            if (pL->data == data) {
                result = pL;
            } else {
                pL = pL->next;
            }
        }
    }
    return result;
}
int InsertBefore(DList *pL, double data) {
    if (pL) {
        DList *node = (DList *) malloc(sizeof(DList));
        node->data = data;
        node->next = pL;
 
        if (pL->prev) {
            node->prev = pL->prev;
            pL->prev->next = node;
        } else {
            node->prev = NULL;
        }
        pL->prev = node;
    }
    return 0;
}
 
int InsertAfter(DList *pL, double data) {
    if (pL) {
        DList *node = (DList *) malloc(sizeof(DList));
        node->data = data;
        if (pL->next) {
            node->next = pL->next;
            pL->next->prev = node;
        } else {
            node->next = NULL;
        }
        pL->next = node;
        node->prev = pL;
    }
    return 0;
}
 
void Erase(DList *pL) {
    if (pL) {
        while (pL->next) {
            pL = pL->next;
            free(pL->prev);
        }
        free(pL);
    }
}
 
int main() {
    setbuf(stdin, 0);
    setbuf(stdout, 0);
 
    DList list;
    list.next = NULL;
    list.prev = NULL;
 
    Add(&list, 1);
    Add(&list, 2);
    Add(&list, 3);
    Add(&list, 4);
    Add(&list, 5);
 
    InsertAfter(Find(&list, 3), 999.1);
 
    DList *walk = &list;
    DList *last = &list;
    while (walk) {
        printf("%4.2f ", walk->data);
        last = walk;
        walk = walk->next;
    }
    printf("\n");
    while (last) {
        printf("%4.2f ", last->data);
        last = last->prev;
    }
    Erase(&list);
    return 0;
}

@Boogie Woogie · 13.11.2016, 21:24 **[ТС]**

Mathist,
Привет!

Спасибо за попытку объяснить.
В общем, я немного понял как создаются списки и у меня кажется получилось сделать алгоритм, который выполняет мою программу, но я не знаю, как сделать так, чтобы оно скомпилировалась в полноценном коде.

Сам алгоритм:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void numb_after (struct lst_List* lst, struct lst_Link* w, struct lst_Link* q) {
    
    if(lst->last == w) {
    
        
        lst->last = q;
        q->next = 0;
        
    } else {
        
        q->next = w->next;
    }
    
    w->next = q;
    
    q->prev = w;
 
    ++lst->size;
}

это верно?

вставляет число q после w в списке.

@Mathist · 13.11.2016, 22:09

Boogie Woogie, На сколько я понял (не вижу описание структуры lst_List) элемент last указывает на последний элемент в списке. В случае если вставляем не после последнего элемента ( ... else { ...), то делаем присваивание q->next = w->next (это у вас есть), также надо у следующего элемента настроить связь предыдущий элемент, т.е.:

C
1
2
3
4
5
 } else {
        
        q->next = w->next;
        w->next->prev = q;
    }

На рисунке эта связь показана красной стрелкой. В вашей программе для работы функции нужен указатель на список (lst), указатель на элемент после которого вставляем (w), и указатель на элемент который вставляем (q). Для того чтобы получить элемент w, нужно его найти в списке. Для этого нужна другая функция, которая будет идти по списку и сравнивать данные переданные в функцию с данными в каждом элементе списка.

@Boogie Woogie · 22.11.2016, 14:31 **[ТС]**

Mathist,
Привет!

Была небольшая пауза

В общем, с помощью различных шаблонов, справочников, создал что-то похожее на код, но, правда, не совсем понимаю как это запустить

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
#include <stdio.h>
#include <stdlib.h>
 
 
 
 
struct lst_List {
    struct lst_Link* first;
    struct lst_Link* last;
    unsigned int size;
};
 
struct lst_Link {
    struct lst_Link* prev;
    struct lst_Link* next;
};
 
struct lst_Value {
    struct lst_Link lnk;
    
    char* p;
};
 
 
struct lst_List* lst_create();
 
// вставляет элемент q после элемента w в lst
void lst_insert_after(struct lst_List* lst, struct lst_Link* p, struct lst_Link* q);
 
 
/*/////////////////////////////////////////////////////////////////////////////////////////////*/
 
void lst_init(struct lst_List* lst) {
    lst->first = lst->last = 0;
    lst->size = 0;
}
 
struct lst_List* lst_create() {
    struct lst_List* lst = (struct lst_List*)malloc(sizeof(struct lst_List));
    lst_init(lst);
    return lst;
}
 
 
void lst_insert_after(struct lst_List* lst, struct lst_Link* p, struct lst_Link* q) {
    
    if(lst->last == p) {
        
        
        lst->last = q;
        q->next = 0;
        
    } else {
 
        q->next = p->next;
        w->next->prev = q;
    }
    
    p->next = q;
    
    q->prev = p;
 
    ++lst->size;
}
 
struct lst_Value* make_name(char* n) {
    struct lst_Value* p = (struct lst_Value*)malloc(sizeof(struct lst_Value));
    p->p = n;
    
    return p;
}
 
struct lst_Link* lst_find(struct lst_List* lst, char* n) {
    struct lst_Link* get_link = lst->first;
 
    while(get_link) {
 
        if(((struct lst_Value*)get_link)->p == n) {
            return get_link;
        }
 
        get_link = get_link->next; 
    }
 
    return 0;
}

@Boogie Woogie · 03.12.2016, 01:16 **[ТС]**

Mathist,

Вот
#include "stdafx.h"
#include <iostream>

using namespace std;

struct tlist
{
tlist *next;
tlist *prev;
double value;
};

void create(tlist *el)
{
int size = 0;
el->prev = NULL;
tlist *temp = new tlist;
tlist *temp2 = new tlist;
cout « "Enter size of list:";
cin » size;
cout « "\nEnter 0 element:";
cin » el->value;
el->next = temp;
temp->prev = el;
for (int i = 1; i < size; i++)
{
cout « "\nEnter " « i « " element:";
cin » temp->value;
temp2 = new tlist;
temp->next = temp2;
temp2->prev = temp;
temp = temp2;
temp->next = NULL;
}

}

void print(tlist *el)
{
tlist* temp = el;
while (temp->next != NULL)
{
cout « temp->value « " ";
temp = temp->next;
}
cout « endl;
}

void add(tlist *el, double a)
{
if (el->next == NULL) //last
{
tlist *temp = new tlist;
el->next = temp;
temp->prev = el;
temp->value = a;
}
else
{
tlist *inserted = new tlist;
inserted->value = a;
tlist *temp = el->next;
el->next = inserted;
inserted->prev = el;
inserted->next = temp;
temp->prev = inserted;
}
}

void find(tlist *el, double num, double adding)
{
tlist *temp = el;
while (temp->next != NULL)
{
if (temp->value == num) add(temp, adding);
temp = temp->next;
}
}

int main()
{
tlist *a = new tlist;
create(a);
find(a, 2.0, 5.0); //1 число - то, что ищем, 2 - что вставляем, можно вставить рандомные переменные
cout « "ascending order\n";
print(a);
while(a->next->next != NULL)
{
a = a->next;
}
cout « "descending order\n";
while (a != NULL)
{
cout « a->value « " ";
a = a->prev;
}
system("pause");
return 0;
}

Единственное непонятно, как сделать тоже самое, только чтобы цифры, которые мы меняем, могли вводить вручную

@Mathist · 03.12.2016, 18:01

Boogie Woogie, Приведенный вами код написан на с++. Не совсем понял о каких цифрах идет речь, но если нужно вводить число для поиска и число, которое будет вставлено, то вместо:

C++
1
    find(a, 2.0, 5.0); //1 число - то, что ищем, 2 - что вставляем, можно вставить рандомные переменные

вставьте

C++
1
2
3
4
5
6
    double first, second;
    cout << "\nEnter number to find: ";
    cin >> first;
    cout << "Enter number to insert: ";
    cin >> second;
    find(a, first, second); //1 число - то, что ищем, 2 - что вставляем, можно вставить рандомные переменные

@Boogie Woogie · 04.12.2016, 00:58 **[ТС]**

Mathist,
Да, на С++ мне было проще реализовать это все.

А вот Ваш кусочек кода не работает. Программа компилируется, но ввод поиска/вставки осуществить нельзя

@Mathist · 04.12.2016, 16:54

Boogie Woogie, почему нельзя? кто мешает?)
Функция мэйн:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
    tlist *a = new tlist;
    create(a);
    double first, second;
    cout << "\nEnter number to find: ";
    cin >> first;
    cout << "Enter number to insert: ";
    cin >> second;
    find(a, first, second); //1 число - то, что ищем, 2 - что вставляем, можно вставить рандомные переменные
    cout << "ascending order\n";
    print(a);
    while (a->next->next != NULL) {
        a = a->next;
    }
    cout << "descending order\n";
    while (a != NULL) {
        cout << a->value << " ";
        a = a->prev;
    }
//  system("pause");
    return 0;
}

Вывод:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Enter size of list: 3
 
Enter 0 element:1
 
Enter 1 element:2
 
Enter 2 element:3
 
Enter number to find: 2
Enter number to insert: 6.66
ascending order
1 2 6.66 3 
descending order
3 6.66 2 1

@Boogie Woogie · 04.12.2016, 21:49 **[ТС]**

Mathist, Да, блин, я понял.

Этот Visual Studio какой-то ад.

Спасибо, все работает!

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Boogie Woogie 0 / 0 / 1 Регистрация: 20.07.2016 Сообщений: 108

	Двунаправленный (двусвязанный) список 12.11.2016, 23:14. Показов 4452. Ответов 9 Метки нет (Все метки) Приветы! В общем, нужна программа, которая: Из -двунаправленного списка -ищет вещественное число и выполняет следующие действия: Находит вещественное число по числу, введенному с клавиатуры,и после него добавить новое число. Я так и не понял, как работают списки. Нет, суть я понял, в теории я понимаю что они такое и для чего нужны, но когда время приходит к делу, то не могу понять, как его хотя бы создавать. В общем, нужна помощь. 0

@Boogie Woogie 0 / 0 / 1 Регистрация: 20.07.2016 Сообщений: 108
	03.12.2016, 01:16 [ТС]
	Mathist, Вот #include "stdafx.h" #include <iostream> using namespace std; struct tlist { tlist next; tlist prev; double value; }; void create(tlist el) { int size = 0; el->prev = NULL; tlist temp = new tlist; tlist temp2 = new tlist; cout « "Enter size of list:"; cin » size; cout « "\nEnter 0 element:"; cin » el->value; el->next = temp; temp->prev = el; for (int i = 1; i < size; i++) { cout « "\nEnter " « i « " element:"; cin » temp->value; temp2 = new tlist; temp->next = temp2; temp2->prev = temp; temp = temp2; temp->next = NULL; } } void print(tlist el) { tlist* temp = el; while (temp->next != NULL) { cout « temp->value « " "; temp = temp->next; } cout « endl; } void add(tlist el, double a) { if (el->next == NULL) //last { tlist temp = new tlist; el->next = temp; temp->prev = el; temp->value = a; } else { tlist inserted = new tlist; inserted->value = a; tlist temp = el->next; el->next = inserted; inserted->prev = el; inserted->next = temp; temp->prev = inserted; } } void find(tlist el, double num, double adding) { tlist temp = el; while (temp->next != NULL) { if (temp->value == num) add(temp, adding); temp = temp->next; } } int main() { tlist *a = new tlist; create(a); find(a, 2.0, 5.0); //1 число - то, что ищем, 2 - что вставляем, можно вставить рандомные переменные cout « "ascending order\n"; print(a); while(a->next->next != NULL) { a = a->next; } cout « "descending order\n"; while (a != NULL) { cout « a->value « " "; a = a->prev; } system("pause"); return 0; } Единственное непонятно, как сделать тоже самое, только чтобы цифры, которые мы меняем, могли вводить вручную 0

@Boogie Woogie 0 / 0 / 1 Регистрация: 20.07.2016 Сообщений: 108
	04.12.2016, 00:58 [ТС]
	Mathist, Да, на С++ мне было проще реализовать это все. А вот Ваш кусочек кода не работает. Программа компилируется, но ввод поиска/вставки осуществить нельзя 0

@Boogie Woogie 0 / 0 / 1 Регистрация: 20.07.2016 Сообщений: 108
	04.12.2016, 21:49 [ТС]
	Mathist, Да, блин, я понял. Этот Visual Studio какой-то ад. Спасибо, все работает! 0