1. 首页
  2. 文章中心
  3. 链表

C语言实现单链表知识点总结

128 阅读 0 评论
我是靠谱客的博主 靓丽柜子，这篇文章主要介绍C语言实现单链表知识点总结，现在分享给大家，希望可以做个参考。

1..注意事项

1.链表的实际结构

要注意边界条件，如头尾，空与非空，一个节点

与顺序表对比，可以发现在顺序表创立了一个结构体，成员有数组，容量，数组的元素个数，但是单链表只是单纯的定义了一个结构体指针。这是因为如果结构体指针为空就是说这个链表中一个数据也没有。

插：

插入要考虑两种情况：头指针为空，头指针不为空。

插入一定不要忘记一开始头节点可能为NULL，要单独讨论

插入函数的参数，传二级指针

对指针的断言要记得，因为都是二级指针所以可以全部断言，保不齐还会有人直接传个NULL进来如：SLNPushBack(NULL)。

实际上只有头节点为空的时候需要二级指针，因为要改变指针，就要传指针的地址也就是二级指针；在其他的情况下并不需要改变指针，而是要改变指针指向的内容，这是纯粹一个指针就可以做到，一级指针就可以；这里选择所有函数全是二级指针的样子是因为为了保持接口的一致性。

请思考以下代码为什么无法完成尾插功能

复制代码
1
2
3
4
5
6
	SLN* tail = *pphead;
while (tail != NULL)
{
tail = tail->next;
}
tail = newnode;

tail虽然指向了newnode,但是newnode没有与链表链接，而且tail是临时变量存在栈区，出了这个函数就被销毁了，而malloc出来的newnode还存在着(mallco出来的存在堆区)，但是没有人能找到他这还会导致内存泄漏，内存泄漏是个大问题。

正确写法： 

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SLNPushBack(SLN** pphead,SLDataType x)
{
assert(pphead);
SLN* newnode = BuyANode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLN* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}

此时也不用在最后tail = newnode,因为tail是临时变量，出了函数就销毁了，找尾还要重新找。

二级指针解引用（*）和->是有优先级的所以记得(*pphead)->head要把(*pphead)括起来。

删：

删除的时候要考虑三种情况为空，一个节点，两个以上节点。

什么情况下需要二级指针？改变头节点的地址的时候，如果可能会改变头节点的地址就要二级指针。如：把链表删完的时候。

请思考以下代码的错误：

//大于等于两个节点的情况下：

SLN* tail = *pphead;
    while (tail->next)
    {
        
        tail = tail->next;
    }
    free(tail);
    tail = 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
void SLNPopBack(SLN** pphead)
{
assert(pphead);
//为空 直接暴力断言
assert(*pphead);
//或者温柔一点
/*if (*pphead == NULL)
{
return NULL;
}*/
//一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//找尾,把尾free掉，前一个和NULL相连
SLN* tail = *pphead;
SLN* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}

可以明显感受到单链表的头插头删很简单，在创立尾指针后尾插也方便了，而尾删和在为任意位置插入删除最为复杂，

因为要找到尾的前一个，就算创立一个尾指针也只是方便了尾插，尾删还是很麻烦；

单链表与无法按需创建空间、尾删尾插方便的顺序表各有优劣。

2.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
typedef int SLDataType;
typedef struct SListNode
{
SLDataType data;
struct SListNode* next;
}SLN;
//对于简单的单链表并不需要像顺序表一样对其进行初始化,顺序表一定会存在一个结构体 ,
//而单链表只定义了一个头指针，这个指针给上NULL即可
//打印
void SLNPrint(SLN** pphead);
//增加
void SLNPushBack(SLN** pphead);
void SLNPushFront(SLN** pphead);
//删除
void SLNPopBack(SLN** pphead);
void SLNPopFront(SLN** pphead);
//查找
SLN* SLNFind(SLN** pphead,SLDataType x);
//在pos之前插入
void SLNInsert(SLN** pphead, SLN* pos, SLDataType x);
//在pos之后插入
void SLNInsertAftert (SLN* pos, SLDataType x);
//删除pos位置
void SLNErase(SLN** pphead, SLN* pos);
//删除x之后的节点
void SLNEraseAfter(SLN** pphead);
//销毁
void SLNDestory(SLN** pphead);
复制代码
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
197
198
199
200
201
202
#include "SL.h"
//打印
void SLNPrint(SLN** pphead)
{
assert(pphead);
SLN* cur = *pphead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULLn");
}
SLN* BuyANode(SLDataType x)
{
SLN* newnode = (SLN*)malloc(sizeof(SLN));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//增加
//尾插
void SLNPushBack(SLN** pphead,SLDataType x)
{
assert(pphead);
SLN* newnode = BuyANode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLN* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//头插
void SLNPushFront(SLN** pphead,SLDataType x)
{
assert(pphead);
SLN* newnode = BuyANode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//删除
//尾删
void SLNPopBack(SLN** pphead)
{
assert(pphead);
//为空 直接暴力断言
assert(*pphead);
//或者温柔一点
/*if (*pphead == NULL)
{
return NULL;
}*/
//一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//找尾,把尾free掉，前一个和NULL相连
SLN* tail = *pphead;
SLN* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
//头删
void SLNPopFront(SLN** pphead)
{
//为空
assert(pphead);
//一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//多个节点
else
{
SLN* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
//查找
SLN* SLNFind(SLN** pphead, SLDataType x)
{
assert(pphead);
SLN* cur = *pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
if (cur == NULL)
return NULL;
}
//删除x之后的节点
void SLNEraseAfter(SLN*pos)
{
//要删除的节点不能是最后一个
assert(pos->next);
SLN* next = pos->next->next;
pos->next = next;
}
//在pos之前插入
void SLNInsert(SLN** pphead, SLN* pos, SLDataType x)
{
assert(pphead && pos);
SLN* newndoe = BuyANode(x);
if (*pphead == pos)
{
//SLNPushFront(pphead,x);
newndoe->next = pos;
*pphead = newndoe;
}
else
{
SLN* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
prev->next = newndoe;
newndoe->next = pos;
}
}
//在pos之后插入
void SLNInsertAftert(SLN* pos, SLDataType x)
{
assert(pos);
SLN* newnode = BuyANode(x);
SLN* next = pos->next;
pos->next = newnode;
newnode->next = next;
}
//删除pos位置
void SLNErase(SLN** pphead, SLN* pos)
{
assert(pphead&&pos);
//在头的时候
if (*pphead == pos)
{
SLNPopFront(pphead);
}
//一般情况
else
{
SLN* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLN* next = pos->next;
free(pos);
pos = NULL;//可以不置空，因为pos只是外面pos的拷贝，无法影响外面的pos
prev->next = next;
}
}
void SLNEraseAfter(SLN* pos)
{
assert(pos);
//pos如果是最后一个就没法删除他的下一个
assert(pos->next);
SLN* next = pos->next->next;
free(pos->next);
pos->next = next;
}
void SLNDestory(SLN** pphead)
{
assert(pphead);
SLN* cur = *pphead;
while (cur)
{
SLN* next = cur->next;
free(cur);
cur = next;
}
*pphead = 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
#include "SL.h"
int main()
{
SLN* head = NULL;
//尾插
for (int i = 0; i < 5; i++)
{
SLNPushBack(&head, i);
}
SLNPrint(&head);
//头删
SLNPopFront(&head);
SLNPopFront(&head);
SLNPrint(&head);
SLNPopFront(&head);
SLNPopFront(&head);
SLNPopFront(&head);
SLNPrint(&head);
//头插
for (int i = 0; i < 5; i++)
{
SLNPushFront(&head, i);
}
SLNPrint(&head);
//头删
SLNPopFront(&head);
SLNPopFront(&head);
SLNPopFront(&head);
SLNPopFront(&head);
SLNPopFront(&head);
//SLNPopFront(&head);
SLNPrint(&head);
for (int i = 0; i < 5; i++)
{
SLNPushBack(&head, i);
}
SLNPrint(&head);
//查找
SLN* pos = SLNFind(&head, 3);
if (pos)
{
printf("地址是:%pn", pos);
}
else
{
printf("没找到n");
}
//修改数据
pos->data *= 10;
SLNPrint(&head);
SLNInsert(&head, pos, 50);
SLNPrint(&head);
SLNInsertAftert(pos, 32);
SLNPrint(&head);
pos = SLNFind(&head, 0);
if (pos)
{
printf("地址是:%pn", pos);
}
else
{
printf("没找到n");
}
SLNErase(&head, pos);
SLNPrint(&head);
return 0;
}

最后

以上就是靓丽柜子最近收集整理的关于C语言实现单链表知识点总结的全部内容，更多相关C语言实现单链表知识点总结内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(85)

相关文章

C语言学习笔记-知识点随记3
C语言学习笔记-知识点随记3
C语言知识点总结（一）
C语言知识点总结（一）
C语言链表（linked list）基础知识总结一、链表二、链表的使用三、链表综合运用小程序
C语言链表（linked list）基础知识总结一、链表二、链表的使用三、链表综合运用小程序
C++后端知识库
C++后端知识库
C语言实现单链表知识点总结
C语言实现单链表知识点总结
c语言 单链表基础知识,C语言基础——链表详解！
c语言 单链表基础知识,C语言基础——链表详解！
长度最多为6个汉字或12个字母数字JS验证
长度最多为6个汉字或12个字母数字JS验证
PLSQL崩溃后的窗口恢复问题
PLSQL崩溃后的窗口恢复问题

评论列表共有 0 条评论

立即
投稿
返回
顶部