单链表基本操作_递归实现单链表的基本操作头歌

作者：我家自动化 | 2024-05-07 11:54:46

踩

递归实现单链表的基本操作头歌

单链表

一、链表是什么？
二、链表的分类
三、单链表的实现
总结
- 完整代码

一、链表是什么？

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
在这里插入图片描述

二、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.单向和双向
在这里插入图片描述
2.带头或不带头

3. 循环或者非循环

在这里插入图片描述

三、单链表的实现

动态申请一个节点

ListNode* ListCreate(LTDataType x)
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == head)
	{
		assert(0);
		return NULL;
	}
	head->data = x;
	head->next = NULL;
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12

单链表的尾插

void ListPushBack(ListNode** pHead, LTDataType x)
{
	assert(pHead);
	if (*pHead == NULL)
	{
		*pHead = ListCreate(x);
		return;
	}
	else
	{
		ListNode* cur = *pHead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = ListCreate(x);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

单链表的尾删

void ListPopBack(ListNode** pHead)
{
	assert(pHead);
	if (NULL == *pHead)
	{
		return;
	}
	else if (NULL == (*pHead)->next)
	{
		free(*pHead);
		*pHead== NULL;
	}
	else
	{
		ListNode* cur = *pHead;
		ListNode* pre = NULL;
		while (cur->next)
		{
			pre = cur;
			cur = cur->next;
		}
		pre->next = NULL;
		free(cur);
	}
}
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

单链表的头插

void ListPushFront(ListNode** pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = ListCreate(x);
	newnode->next = *pHead;
	*pHead = newnode;
}
1
2
3
4
5
6
7

单链表的头删

void ListPopFront(ListNode** pHead)
{
	assert(pHead);
	if (NULL == *pHead)
	{
		return;
	}
	else
	{
		ListNode *delNode = *pHead;
		*pHead = (delNode)->next;
		free(delNode);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

单链表查找

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	if (NULL == pHead)
	{
		return;
	}
	ListNode* cur = pHead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	printf("没有这个元素\n");
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在pos之后插入节点x

因为无法对pos之前的节点进行操作，所以在pos之后插入新节点。

void ListInsert(ListNode* pos, LTDataType x)
{
	if (NULL == pos)
	{
		return;
	}
	ListNode* newNode = ListCreate(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
1
2
3
4
5
6
7
8
9
10

删除pos之后位置的元素

void ListErase(ListNode* pos)
{
	if (NULL == pos || NULL == pos->next)
	{
		return;
	}
	ListNode* delNode = pos->next;
	pos->next = delNode->next;
	free(delNode);
}
1
2
3
4
5
6
7
8
9
10

逆序打印链表

此为递归做法。

void ListReversePrint(ListNode* pHead)
{
	if (NULL != pHead)
	{
		ListReversePrint(pHead->next);
		printf("%d ", pHead->data);
	}
}
1
2
3
4
5
6
7
8

测试函数

void TestList()
{
	ListNode* pHead = NULL;
	ListPushBack(&pHead, 1);
	ListPushBack(&pHead, 2);
	ListPushBack(&pHead, 3);
	ListPushBack(&pHead, 4);
	ListPushBack(&pHead, 5);

	ListPrint(pHead);
	ListPushFront(&pHead, 0);
	ListPrint(pHead);

	ListPopFront(&pHead);
	ListPrint(pHead);

	ListInsert(ListFind(pHead, 3),9);
	ListPrint(pHead);

	ListErase(ListFind(pHead, 3));
	ListPrint(pHead);

	ListReversePrint(pHead);
	
	ListDestory(&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

总结

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

完整代码

ListNode.h

#pragma once

#include<malloc.h>
#include<assert.h>
#include<stdio.h>
#include<Windows.h>

// 单链表增删查改实现
typedef int LTDataType;

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

//动态申请一个节点
ListNode* ListCreate(LTDataType);
//删除
void ListDestory(ListNode** pHead);
//单链表打印
void ListPrint(ListNode* pHead);
//单链表尾插
void ListPushBack(ListNode** pHead, LTDataType x);
//单链表尾删
void ListPopBack(ListNode** pHead);
//单链表头插
void ListPushFront(ListNode** pHead, LTDataType x);
//单链表头删
void ListPopFront(ListNode** pHead);
//单链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
//在pos插入元素
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置元素
void ListErase(ListNode* pos);

//逆置链表
void ListReversePrint(ListNode* plist);

void TestList();
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

ListNode.c

#include"ListNode.h"


//申请一个节点
ListNode* ListCreate(LTDataType x)
{
	ListNode* head = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == head)
	{
		assert(0);
		return NULL;
	}
	head->data = x;
	head->next = NULL;
	return head;
}

//销毁单链表
void ListDestory(ListNode** pHead)
{
	assert(pHead);
	ListNode* cur = *pHead;
	while (cur)
	{
		*pHead = cur->next;
		free(cur);
		cur = *pHead;
	}
	*pHead = NULL;
}

//打印单链表
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead;
	while (cur)
	{
		printf("%d-->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//单链表的尾插
void ListPushBack(ListNode** pHead, LTDataType x)
{
	assert(pHead);
	if (*pHead == NULL)
	{
		*pHead = ListCreate(x);
		return;
	}
	else
	{
		ListNode* cur = *pHead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = ListCreate(x);
	}
}

//单链表的尾删
void ListPopBack(ListNode** pHead)
{
	assert(pHead);
	if (NULL == *pHead)
	{
		return;
	}
	else if (NULL == (*pHead)->next)
	{
		free(*pHead);
		*pHead== NULL;
	}
	else
	{
		ListNode* cur = *pHead;
		ListNode* pre = NULL;
		while (cur->next)
		{
			pre = cur;
			cur = cur->next;
		}
		pre->next = NULL;
		free(cur);
	}
}

//单链表的头插
void ListPushFront(ListNode** pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = ListCreate(x);
	newnode->next = *pHead;
	*pHead = newnode;
}

//单链表的头删
void ListPopFront(ListNode** pHead)
{
	assert(pHead);
	if (NULL == *pHead)
	{
		return;
	}
	else
	{
		ListNode *delNode = *pHead;
		*pHead = (delNode)->next;
		free(delNode);
	}
}

//单链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	if (NULL == pHead)
	{
		return;
	}
	ListNode* cur = pHead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	printf("没有这个元素\n");
	return NULL;
}

//在pos之后插入元素x
void ListInsert(ListNode* pos, LTDataType x)
{
	if (NULL == pos)
	{
		return;
	}
	ListNode* newNode = ListCreate(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

//删除pos之后位置的元素
void ListErase(ListNode* pos)
{
	if (NULL == pos || NULL == pos->next)
	{
		return;
	}
	ListNode* delNode = pos->next;
	pos->next = delNode->next;
	free(delNode);
}

//逆置链表
void ListReversePrint(ListNode* pHead)
{
	if (NULL != pHead)
	{
		ListReversePrint(pHead->next);
		printf("%d ", pHead->data);
	}
}
void TestList()
{
	ListNode* pHead = NULL;
	ListPushBack(&pHead, 1);
	ListPushBack(&pHead, 2);
	ListPushBack(&pHead, 3);
	ListPushBack(&pHead, 4);
	ListPushBack(&pHead, 5);

	ListPrint(pHead);
	ListPushFront(&pHead, 0);
	ListPrint(pHead);

	ListPopFront(&pHead);
	ListPrint(pHead);

	ListInsert(ListFind(pHead, 3),9);
	ListPrint(pHead);

	ListErase(ListFind(pHead, 3));
	ListPrint(pHead);

	ListReversePrint(pHead);
	
	ListDestory(&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
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

main.c

#include"ListNode.h"

int main()
{
	TestList();
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/549090