C语言：数据结构（双向链表）

1、双向链表的结构

注意：这⾥的“带头“跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“放哨的”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。
“哨兵位”存在的意义：遍历循环链表避免死循环。

2、顺序表和双向链表的优缺点分析

3、双向链表的实现

ListNode.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义双向链表节点的结构
typedef int Ltdatatype;
typedef struct ListNode
{
	Ltdatatype data;
	struct ListNode* prev;//指向前一个节点的指针
	struct ListNode* next;//指向后一个节点的指针
}ListNode;
//双向链表的初始化
ListNode* LtInit();
//尾插
//不改变哨兵位的地址，所以传一级即可
void LtPushBack(ListNode* phead, Ltdatatype x);//插入数据之前，链表必须初始化到只有一个头结点的情况
//打印链表
void LtPrint(ListNode* phead);
//头插
void LtPushFront(ListNode* phead, Ltdatatype x);
//尾删
LtPopBack(ListNode* phead);
//头删
LtPopFront(ListNode* phead);
//查找
ListNode* LtFind(ListNode* phead, Ltdatatype x);
//指定位置前插入
void LtInsert(ListNode* pos, Ltdatatype x);
//删除pos位置
void LtErase(ListNode* pos);
//销毁链表
void LtDestroy(ListNode* 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

ListNode.c

#define _CRT_SECURE_NO_WARNINGS
#include "ListNode.h"
//申请节点
ListNode* LtBuyNode(Ltdatatype x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	//申请成功
	node->data = x;
	node->next = node->prev = node;
	return node;
}
//双向链表的初始化
ListNode* LtInit()
{
	ListNode*phead = LtBuyNode(-1);
	return phead;
}
//尾插
void LtPushBack(ListNode* phead, Ltdatatype x)
{
	assert(phead);
	ListNode* newnode = LtBuyNode(x);
	//改变新节点的指向
	newnode->prev = phead->prev;
	newnode->next = phead;
	//改变尾节点和哨兵位的指向
	phead->prev->next = newnode;
	phead->prev = newnode;
}
//打印链表
void LtPrint(ListNode* phead)
{
	ListNode* pcur = phead->next;
	//遍历链表
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
//头插
void LtPushFront(ListNode* phead,Ltdatatype x)
{
	assert(phead);
	ListNode* newnode = LtBuyNode(x);
	newnode->prev = phead;
	newnode->next = phead->next;
	//修改哨兵位和第一个有效节点的指向
	phead->next->prev = newnode;
	phead->next = newnode;
}
//尾删
LtPopBack(ListNode* phead)
{
	//链表必须有效且链表不能为空（只有一个哨兵位）
	assert(phead && phead->next != phead);
	ListNode* Del = phead->prev;//尾节点
	ListNode* DelPrev = Del->prev;//尾节点的前一个节点
	phead->prev = DelPrev;
	DelPrev->next = phead;
	free(Del);//删除Del节点
	Del = NULL;
}
//头删
LtPopFront(ListNode* phead)
{
	//判断链表是否有效和链表是否为空
	assert(phead && phead->next != phead);
	ListNode* Del = phead->next;//第一个有效节点
	ListNode* DelNext = Del->next;//有效节点的下一个节点
	phead->next = DelNext;
	DelNext->prev = phead;
	free(Del);//删除Del节点
	Del = NULL;
}
//查找
ListNode* LtFind(ListNode* phead, Ltdatatype x)
{
	ListNode* pcur = phead->next;
	//遍历链表
	while (pcur != phead)
	{
		if (pcur->data == x)
			return pcur;
		pcur = pcur->next;//继续让pcur往下遍历
	}
	return NULL;//没有找到
}
//在pos位置之前插入数据
void LtInsert(ListNode* pos,Ltdatatype x)
{
	ListNode* newnode = LtBuyNode(x);
	newnode->prev = pos->prev;
	newnode->next = pos;
	pos->prev->next = newnode;
	pos->prev = newnode;
}
//删除pos位置
void LtErase(ListNode* pos)
{
	assert(pos);
	ListNode* PosPrev = pos->prev;//pos的前一个节点
	ListNode* PosNext = pos->next;//pos的后一个节点
	PosPrev->next = PosNext;
	PosNext->prev = PosPrev;
	free(pos);
	//pos = NULL;这里就算置空了，也不会影响实参
}
//销毁链表
void LtDestroy(ListNode* phead)
{
	ListNode* pcur = phead->next;
	//边遍历边释放节点
	while (pcur != phead)
	{
		ListNode* Next = pcur->next;//保存要释放掉节点的下一个地址
		free(pcur);
		pcur = Next;
	}
	//此时pcur指向phead，而phead还没有被销毁
	free(phead);
	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

text.c

#define _CRT_SECURE_NO_WARNINGS
#include "ListNode.h"
void LtnodeTest()
{
	//测试初始化
	ListNode* plist = LtInit();
	//测试尾插
	LtPushBack(plist,1);
	LtPushBack(plist,2);
	LtPushBack(plist,3);
	//测试打印
	LtPrint(plist);
	//测试头插
	//LtPushFront(plist,4);
	//LtPushFront(plist,5);
	//LtPushFront(plist,6);
	//LtPrint(plist);
	//测试尾删
	LtPopBack(plist);
	LtPrint(plist);
	//测试头删
	//LtPopFront(plist);
	//LtPrint(plist);
	//测试查找
	//ListNode*find = LtFind(plist,2);
	//if (find)
	//	printf("找到了！\n");
	//else
	//	printf("没找到！\n");
	//测试在pos位置之前插入数据
	//LtInsert(find,88);
	//LtPrint(plist);
	//测试删除pos位置
	//LtErase(find);
	//find = NULL;//形参的改变不会影响实参，所以要在函数调用结束之后置为空
	//LtPrint(plist);
	//测试销毁链表
	//LtDestroy(plist);
	//plist = NULL;
}
int main()
{
	LtnodeTest();
	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

如果对你有所帮助的话，别忘了一键三连哟，谢谢宝子们