Обмен технологиями

[Структура данных] Двусвязный список

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Привет~! Это маленькая овечка, которая борется. Для меня большая честь, что вы можете прочитать мою статью. Пожалуйста, прокомментируйте и дайте мне совет. Добро пожаловать~~.
💥💥个人主页：Борющийся ягненок
💥💥所属专栏：язык Си

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

Оглавление

Предисловие

Односвязный список может получить доступ к данным только в одном направлении через адрес определенного узла, тогда как двусвязный список может получить доступ к данным в обоих направлениях через адрес узла. Эффективность добавления, удаления, проверки и изменения выше. но реализация кода проще, чем у односвязного списка. С точки зрения , преимущества двусвязных списков более очевидны.

1. Классификация связанных списков

Связанные списки делятся на восемь типов: с заголовком, без заголовка, односторонние, двусторонние, циклические и нециклические. Мы изучаем только общие.Односторонний нециклический связанный список без лидераиДвусторонний круговой связанный список с заголовком, то естьЕдиный списокиДвусвязный список。
Двусвязный список:
Вставьте сюда описание изображения
На самом деле, в прошлой статье мы назвали первый узел односвязного списка головным узлом, что неточно. Причина, по которой он так называется, — для облегчения понимания, потому что односвязный список не имеет головного узла. только двусвязный список имеет головной узел.Позиция дозорного。

  • В головном узле двусвязного списка не хранятся действительные данные, но есть недействительные данные.
  • Положение дозорного изменить нельзя, можно изменить только его направление.

2. Реализация двусвязного списка.

2.1 Узлы двусвязного списка

Узлы двусвязного списка должны хранить данные, а также адреса предыдущего и следующего узлов. Следовательно, узлами двусвязного списка являются:

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
	dlist_data_type data;
	struct dlist* next
	struct dlist* prev;
}dlist;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

2.2 Подать заявку на узел

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

Применяемый узел изначально имеет два указателя, указывающих на себя.。

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
	dlist* newdlist = (dlist*)malloc(sizeof(dlist));
	if (newdlist == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newdlist->data = x;
	newdlist->next = newdlist;
	newdlist->prev = newdlist;
	return newdlist;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

Существует два способа инициализации сигнального бита:
Возвращается в качестве параметров:

void dlist_init(dlist** pphead)
{
	assert(pphead);
	*pphead = dlist_buy(-1);
}

  • 1
  • 2
  • 3
  • 4
  • 5

Этот метод требует использования вторичных указателей.
Возвращается как возвращаемое значение:

dlist* dlist_init()
{
	dlist* phead = dlist_buy(-1);
	return phead;
}

  • 1
  • 2
  • 3
  • 4
  • 5

Этот метод проще и понятнее.

2.3 Печать и поиск данных

Печать и поиск данных мало чем отличаются от односвязного списка, поэтому не буду вдаваться в подробности.
Единственное, что требует внимания, — это условие завершения цикла. Цикл заканчивается, когда указатель указывает на контрольный бит, а не когда указатель указывает на контрольный бит.NULL。

//打印数据
void dlist_print(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULLn");
}
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

  • 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

2.4 Головная и хвостовая заглушки

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

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新尾节点
	newdlist->prev = phead->prev;
	newdlist->next = phead;

	//旧尾节点
	phead->prev->next = newdlist;

	//头节点（哨兵位）
	phead->prev = newdlist;
}
//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新节点
	newdlist->prev = phead;
	newdlist->next = phead->next;

	//旧节点
	phead->next->prev = newdlist;

	//哨兵位
	phead->next = newdlist;
}

  • 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

2.5 Удаление головы и удаление хвоста

Обязательным условием для операции удаления является то, что узлов не может быть (Позиция дозорного не учитывается), перед удалением все равно сохраните адрес узла, снова присоединитесь к двусвязному списку, а затем освободите узел.

//尾删
void dlist_pop_back(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);//双向链表不能为空
	dlist* del = phead->prev;
	//新尾节点
	del->prev->next = phead;
	//哨兵位
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void dlist_pop_front(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);
	dlist* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

  • 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

2.6 Вставка и удаление данных в указанном месте

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
	assert(pos);
	dlist* newdlist = dlist_buy(x);
	newdlist->prev = pos;
	newdlist->next = pos->next;

	pos->next->prev = newdlist;
	pos->next = newdlist;
}
//删除指定位置的节点
void dlist_erase(dlist* pos)
{
	assert(pos);
	dlist* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

После удаления данных в указанном месте,Поскольку эта функция вызывается по значению, после освобождения узла в указанной позиции мы просто устанавливаем указатель формального параметра наNULL, и фактический указатель параметра по-прежнему указывает на это место, поэтому после завершения вызова функции необходимо установить фактический указатель параметраNULL。

2.7 Уничтожить двусвязный список

Конечным условием уничтожения двусвязного списка является выход из цикла, когда указатель обхода указывает на головной узел.Наконец, позиция дозорного должна быть освобождена отдельно., после завершения вызова функции уничтожения двусвязного списка также должен быть установлен указатель, указывающий на дозорный бит.NULL。

//销毁
void dlist_destroy(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		dlist* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

3. Полный код двусвязного списка.

dlist.h:

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
	dlist_data_type data;
	struct dlist* next;
	struct dlist* prev;
}dlist;

//初始化
//插入数据之前，双向链表必须初始化到只有一个头节点（哨兵位）
//void dlist_init(dlist** pphead);//以参数的形式返回
dlist* dlist_init();//以返回值的形式返回

//打印数据
void dlist_print(dlist* phead);
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x);
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x);
//头插
void dlist_push_front(dlist* phead, dlist_data_type x);
//尾删
void dlist_pop_back(dlist* phead);
//头删
void dlist_pop_front(dlist* phead);
//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x);
//删除指定位置的节点
void dlist_erase(dlist* pos);
//销毁
void dlist_destroy(dlist* phead);

  • 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

dlist.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
	dlist* newdlist = (dlist*)malloc(sizeof(dlist));
	if (newdlist == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newdlist->data = x;
	newdlist->next = newdlist;
	newdlist->prev = newdlist;
	return newdlist;
}

//初始化
//void dlist_init(dlist** pphead)
//{
//	assert(pphead);
//	*pphead = dlist_buy(-1);
//}

dlist* dlist_init()
{
	dlist* phead = dlist_buy(-1);
	return phead;
}

//打印数据
void dlist_print(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULLn");
}

//查找
dlist* dlist_find(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新尾节点
	newdlist->prev = phead->prev;
	newdlist->next = phead;

	//旧尾节点
	phead->prev->next = newdlist;

	//头节点（哨兵位）
	phead->prev = newdlist;
}

//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新节点
	newdlist->prev = phead;
	newdlist->next = phead->next;

	//旧节点
	phead->next->prev = newdlist;

	//哨兵位
	phead->next = newdlist;
}

//尾删
void dlist_pop_back(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);//双向链表不能为空
	dlist* del = phead->prev;
	//新尾节点
	del->prev->next = phead;
	//哨兵位
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void dlist_pop_front(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);
	dlist* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
	assert(pos);
	dlist* newdlist = dlist_buy(x);
	newdlist->prev = pos;
	newdlist->next = pos->next;

	pos->next->prev = newdlist;
	pos->next = newdlist;
}

//删除指定位置的节点
void dlist_erase(dlist* pos)
{
	assert(pos);
	dlist* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//销毁
void dlist_destroy(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		dlist* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}

  • 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
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159

test.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

void test()
{
	//dlist* plist = NULL;
	//dlist_init(&plist);

	dlist* plist = dlist_init();

	//尾插
	dlist_push_back(plist, 1);
	dlist_push_back(plist, 2);
	dlist_push_back(plist, 3);
	dlist_print(plist);
	
	//头插
	//dlist_push_front(plist, 1);
	//dlist_push_front(plist, 2);
	//dlist_push_front(plist, 3);
	//dlist_print(plist);

	//尾删
	//dlist_pop_back(plist);
	//dlist_pop_back(plist);
	//dlist_pop_back(plist);
	//dlist_print(plist);

	//头删
	//dlist_pop_front(plist);
	//dlist_print(plist);
	//dlist_pop_front(plist);
	//dlist_print(plist);
	//dlist_pop_front(plist);
	//dlist_print(plist);

	//dlist* find = dlist_find(plist, 2);
	//dlist_insert_back(find, 4);
	//dlist_print(plist);

	//dlist* find = dlist_find(plist, 2);
	//dlist_erase(find);
	//find = NULL;
	//dlist_print(plist);

	dlist_destroy(plist);
	plist = NULL;//手动置空
}

int main()
{
	test();
	return 0;
}

  • 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

4. Сравнение списка последовательностей и связанного списка.

Таблица последовательностиСвязанный список (двойной связанный список)
На складском местелогически и физически непрерывныЛогически непрерывный, не обязательно физически непрерывный
произвольный доступСложность О(1)Сложность O(N)
Вставка или удаление данных в любом местеДанные необходимо переместить, сложность O(N)Просто измените указатель на
вставлятьТаблицу динамической последовательности можно расширить, когда места недостаточно. Само расширение потребляется, и пространство легко потерять.Нет понятия мощности
Сценарии примененияЭффективное хранение данных + частый доступЧасто вставляйте и удаляйте данные в любом месте
использование кэшавысокийНизкий

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

Подведем итог

  • Если сценарий приложения требует частых операций поиска и удаления и допускает большее потребление памяти, более подходящим может оказаться двусвязный список.
  • Если память ограничена или эффективность операций поиска и удаления невысока, более подходящим может оказаться односвязный список.

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта