小码农教你双链表 双链表

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

双链表

双链表结构图

image-20211028225455233

双链表节点

1
2
3
4
5
6
7
8
c复制代码typedef int LTDataType;  //C++中的双链表是用list表示的

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

双链表初始化函数ListInit

1
2
3
4
5
6
7
8
9
c复制代码//双链表初始化函数
LTNode* ListNodeInit()
{
	//创建一个双链表哨兵位头结点  不存储有效数据  循环
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

image-20211028230625085

双链表尾插函数ListPushBack

image-20211029001350843 

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码//双链表尾插函数
void ListNodePushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//实际上phead永远也不可能是NULL
	LTNode* tail = phead->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

双链表打印函数ListPrint

image-20211029070928255 

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码//双链表打印函数
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

双链表尾删函数ListPopBack

image-20211029072838324 

1
2
3
4
5
6
7
8
9
10
11
c复制代码//双链表尾删函数
void ListPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* cur = phead->prev;
	tail = tail->prev;
	tail->next = phead;
	phead->prev = tail;
	free(cur);
}

双链表头插函数ListPushFront

image-20211029080341212 

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码//双链表头插函数
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;//在next和phead中间插一个节点
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}

既然我们头插尾插都遇到了添加节点，所以我们把添加节点的部分抽离出来重新封装一下

获得双链表节点函数BuyListNode

image-20211029191337400 

1
2
3
4
5
6
7
8
9
c复制代码//获得双链表节点函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

双链表头删函数ListPopFront

image-20211029193358759 

1
2
3
4
5
6
7
8
9
c复制代码//双链表头删函数
void ListPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
}

双链表查找函数ListFind

这个一般是和插入，删除配合使用

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码//双链表查找函数
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

双链表插入函数ListInsert（pos之前插入因为c++中就是之前插入的）

image-20211029204212625 

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码//双链表插入函数
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}

双链表删除函数ListErase（删除pos）

image-20211029205627363 

1
2
3
4
5
6
7
8
9
10
c复制代码//双链表删除函数
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}

双链表销毁函数ListDestroy(实际上我在这里写报错了，前面一个函数有bug，但是找到了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码//双链表销毁函数
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while (tail != phead)
	{
		LTNode* tailprev = tail->next;
		free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}

代码

DoubleList.h

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
c复制代码#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;  //C++中的双链表是用list表示的

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

//双链表初始化函数
extern LTNode* ListInit();
//双链表销毁函数
extern void ListDestroy(LTNode* phead);
//双链表尾插函数
extern void ListPushBack(LTNode* phead, LTDataType x);
//双链表打印函数
extern void ListPrint(LTNode* phead);
//双链表尾删函数
extern void ListPopBack(LTNode* phead);
//获得双链表节点函数
extern LTNode* BuyListNode(LTDataType x);
//双链表头插函数
extern void ListPushFront(LTNode* phead, LTDataType x);
//双链表头删函数
extern void ListPopFront(LTNode* phead);
//双链表查找函数
extern LTNode* ListFind(LTNode* phead, LTDataType x);
//双链表插入函数
extern void ListInsert(LTNode* pos, LTDataType x);
//双链表删除函数
extern void ListErase(LTNode* pos);

DoubleList.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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
c复制代码#define _CRT_SECURE_NO_WARNINGS 1

#include "DoubleList.h"

//双链表初始化函数
LTNode* ListInit()
{
	//创建一个双链表哨兵位头结点  不存储有效数据  循环
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//获得双链表节点函数
LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//双链表尾插函数
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//实际上phead永远也不可能是NULL
	LTNode* tail = phead->prev;
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
//双链表打印函数
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//双链表尾删函数
void ListPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* cur = phead->prev;
	tail = tail->prev;
	tail->next = phead;
	phead->prev = tail;
	free(cur);
}

//双链表头插函数
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* next = phead->next;//在next和phead中间插一个节点
	/*LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;*/
	LTNode* newnode = BuyListNode(x);
	newnode->next = next;
	next->prev = newnode;
	phead->next = newnode;
}

//双链表头删函数
void ListPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
}

//双链表查找函数
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
//双链表插入函数
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;
	newnode->data = x;
	pos->prev = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	posprev->next = newnode;
}
//双链表删除函数
void ListErase(LTNode* pos)
{
	assert(pos && pos->next);
	LTNode* posnext = pos->next;
	LTNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
}
//双链表销毁函数
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* tail = phead->prev;
	while (tail != phead)
	{
		LTNode* tailprev = tail->next;
		free(tail);
		tail = tailprev;
	}
	free(phead);
	phead = NULL;
}

test.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
c复制代码#define _CRT_SECURE_NO_WARNINGS 1
#include "DoubleList.h"
void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPrint(plist);
	LTNode* p1 = ListFind(plist, 10);
	if (p1)
	{
		ListInsert(p1, 100);
	}
	ListPrint(plist);
	LTNode* p2 = ListFind(plist, 20);
	if (p2)
	{
		ListErase(p2);
	}
	ListPrint(plist);
	ListDestroy(plist);
	plist = NULL;
}


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

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%