我是靠谱客的博主 称心小懒猪,这篇文章主要介绍【数据结构与算法】单链表的增删查改(代码+图解)顺序表和链表的特点:分析:尾删完整代码:,现在分享给大家,希望可以做个参考。

目录

顺序表和链表的特点:

时间复杂度:

分析:

单链表结构体和数据类型:

开辟一个节点和存储数据:

打印

尾插

         尾删

头插

头删:

查找单链表中的元素

在pos后插入x

在pos前插入x

删除pos后的一个元素:

删除pos位置的元素:

摧毁单链表:

完整代码:


80f3084b30fd4543b4719418da39509b.png

顺序表和链表的特点:

 顺序表使用数组存储线形的元素,其特点是可以随机存取,但是,因为逻辑上相邻的元素物理上也相邻,所以插入删除需要移动元素.

链表使用指针链表示线形表元素的逻辑关系,插入和删除只需修改指针,不能随机存取.

单向链表增加删除节点简单。 遍历时候不会死循环;

时间复杂度:

链表中数据元素之间的逻辑关系靠的是节点之间的指针,当需要在链表中某处插入或删除节点时,只需改变相应节点的指针指向即可,无需大量移动元素,因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)

顺序表中,插入、删除和移动数据可能会牵涉到大量元素的整体移动,因此时间复杂度至少为 O(n);

链表存储数据一次只开辟存储一个节点的物理空间,如果后期不够还可以再申请。

分析:

单链表结构体和数据类型:

复制代码
1
2
3
4
5
6
7
typedef int SLTDataType; typedef struct SLlistNode { SLTDataType data; struct SListNode* next; }SLTNode;

 

开辟一个节点和存储数据:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }

malloc函数开辟一个大小为sizeof(SLTNode)字节即一个结构体大小的空间,原本malloc返回值是void类型的指针,但是代码里面的(SLTNode*)将malloc的返回值强制类型转换为SLTNode类型,这样方便了后面数据的存储;

打印

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULLn"); }

调用SLTPrint()函数使,用*phead接收传进来的参数

尾插

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SLTPushBack(SLTNode** phead,SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*phead == NULL) { *phead = newnode; } else { SLTNode* ptail = *phead; while (ptail->next) //找尾 { ptail = ptail->next; } ptail->next = newnode; } }

图解:

66eba0284d364d38b8a51ccb6ee89624.png

首先用ptail记住链表头部的位置,再ptail=ptail->next寻找最后一个节点 

尾删

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void SLTPopBack(SLTNode** phead) { assert(*phead); //只有一个指针 if ((*phead)->next==NULL) { free(*phead); *phead = NULL; } else { SLTNode* pre = NULL; //记录倒数第二个指针, SLTNode* ptail = *phead; while (ptail->next) { pre = ptail; ptail = ptail->next; } free(ptail); pre->next = NULL; //将被释放的那个指针置空,避免出现野指针 } }

 assert(*phead)实现对*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
//单指针传参交换指针指向的值 void Swap1(int *p1,int *p2) { int tmp= *p1; //这里p1解引用之后就是p1指针指向的值 *P1 = *p2; *p2= tmp; } //双指针传参交换指针 void Swap2(int ** pp1,int **pp2) { int *tmp=*pp1; *pp1 = *pp2; *pp2 = tmp; } int main() { int a=0,b=1; Swap1(&a,&b); int *ptr1 = &a,ptr2 = &b; Swap2(&ptr1,&ptr2); }

Swap2(&ptr1,&ptr2)通过交换a、b的地址来交换值,而Swap1通过改变指针指向的值来交换值;

总结:1、改变int,传递int *给形参,*形参进行交换改变

           2、改变int*,传递int**给形参,*形参进行交换改变

头插

复制代码
1
2
3
4
5
6
7
void SLTPushFront(SLTNode** phead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *phead; // *phead = newnode; //换头 }

33881d44edb9473aa8caab5882b2a364.png

先将newnode->next指向phead(头节点),再phead=newnode; 

头删:

复制代码
1
2
3
4
5
6
7
8
9
void SLTPopFront(SLTNode** phead) { assert(*phead); SLTNode* newnode = NULL; newnode = (*phead)->next; //存储第二个指针 free(*phead); //释放第一个指针空间 *phead = newnode; //换头 }

查找单链表中的元素

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }

在pos后插入x

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SLTInsertAfter(SLTNode** phead, SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* cur = *phead; while (cur != pos) { cur = cur->next; } SLTNode* newnode = BuySLTNode(x); newnode->next = cur->next; cur->next = newnode; }

在pos前插入x

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x) { assert(pos); if (*phead == pos) { SLTPushFront(phead,x); //头插 } else { SLTNode* pre = *phead; while (pre->next != pos) { pre = pre->next; } SLTNode* newnode = BuySLTNode(x); pre->next = newnode; newnode->next = pos; } }

删除pos后的一个元素:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SLTEraseAfter(SLTNode* pos) { assert(pos); if (pos->next = NULL) { return; } else { SLTNode* next = pos->next; pos->next = next->next; free(next); } }

图解: 

f9164a69043f4ba59d4d05166642001b.png

删除pos位置的元素:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void SLTErase(SLTNode** phead, SLTNode* pos) { assert(pos); assert(*phead); if (*phead == pos) { SLTPopFront(phead); //这里不用*phead,因为传过去的是**phead;解引用的时候改变的是*phead; } else { SLTNode* pre = *phead; while (pre->next != pos) { pre = pre->next; } pre->next = pos->next; free(pos); } }

摧毁单链表:

复制代码
1
2
3
4
5
6
7
8
9
10
11
void SLTDestroy(SLTNode** phead) { SLTNode* cur = *phead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *phead = NULL; }

完整代码:

我用SList.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
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; typedef struct SLlistNode { SLTDataType data; struct SListNode* next; }SLTNode; SLTNode* BuySLTNode(SLTDataType x); SLTNode* CreateSList(int n); void SLTPrint(SLTNode* phead); void SLTPushBack(SLTNode** phead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPushFront(SLTNode** phead, SLTDataType x); void SLTPopFront(SLTNode** phead); SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 查找链表中的元素 void SLTInsertAfter(SLTNode**phead,SLTNode* pos,SLTDataType x);//在pos位置之后插入x void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);//在pos位置前面插入x void SLTEraseAfter(SLTNode* pos);//删除pos后面的一个元素 void SLTErase(SLTNode** phead, SLTNode* pos);//删除pos位置的元素 void SLTDestroy(SLTNode** phead);

用SList.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
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
#define _CRT_SECURE_NO_WARNI #include"SList.h" SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } //SLTNode* CreateSList(int n) //{ // SLTNode* phead = NULL; // SLTNode* ptail = NULL; // int x; // for (int i = 0; i < n; i++) // { // SLTNode* newnode = BuySLTNode(i); // if (phead == NULL) // { // ptail = phead = newnode; // } // else // { // ptail->next = newnode; // ptail = newnode; // } // } // return phead; //} void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULLn"); } void SLTPushBack(SLTNode** phead,SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*phead == NULL) { *phead = newnode; } else { SLTNode* ptail = *phead; while (ptail->next) //找尾 { ptail = ptail->next; } ptail->next = newnode; } } void SLTPopBack(SLTNode** phead) { assert(*phead); //只有一个指针 if ((*phead)->next==NULL) { free(*phead); *phead = NULL; } else { SLTNode* pre = NULL; //记录倒数第二个指针, SLTNode* ptail = *phead; while (ptail->next) { pre = ptail; ptail = ptail->next; } free(ptail); pre->next = NULL; //将被释放的那个指针置空,避免出现野指针 } } void SLTPushFront(SLTNode** phead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *phead; // *phead = newnode; //换头 } void SLTPopFront(SLTNode** phead) { assert(*phead); SLTNode* newnode = NULL; newnode = (*phead)->next; //存储第二个指针 free(*phead); //释放第一个指针空间 *phead = newnode; //换头 } SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SLTInsertAfter(SLTNode** phead, SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* cur = *phead; while (cur != pos) { cur = cur->next; } SLTNode* newnode = BuySLTNode(x); newnode->next = cur->next; cur->next = newnode; } void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x) { assert(pos); if (*phead == pos) { SLTPushFront(phead,x); //头插 } else { SLTNode* pre = *phead; while (pre->next != pos) { pre = pre->next; } SLTNode* newnode = BuySLTNode(x); pre->next = newnode; newnode->next = pos; } } void SLTEraseAfter(SLTNode* pos) { assert(pos); if (pos->next = NULL) { return; } else { SLTNode* next = pos->next; pos->next = next->next; free(next); } } void SLTErase(SLTNode** phead, SLTNode* pos) { assert(pos); assert(*phead); if (*phead == pos) { SLTPopFront(phead); //这里不用*phead,因为传过去的是**phead;解引用的时候改变的是*phead; } else { SLTNode* pre = *phead; while (pre->next != pos) { pre = pre->next; } pre->next = pos->next; free(pos); } } void SLTDestroy(SLTNode** phead) { SLTNode* cur = *phead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *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
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
#define _CRT_SECURE_NO_WARNINGS #include"SList.h" //void test1() //{ // SLTNode* plist = NULL; // plist=CreateSList(3); // SLTPrint(plist); //} // //void testSLTNode2() //{ // SLTNode* plist = NULL; // SLTPushBack(&plist, 1); // SLTPushBack(&plist, 2); // SLTPushBack(&plist, 3); // SLTPushBack(&plist, 4); // // SLTPopBack(&plist); // // SLTPrint(plist); //} // //void testSTLNode3() //{ // SLTNode* plist = NULL; // SLTPushFront(&plist,1); // SLTPushFront(&plist,2); // SLTPushFront(&plist,3); // SLTPushFront(&plist,4); // SLTPushFront(&plist,5); // // SLTPrint(plist); // // SLTPopFront(&plist); // SLTPopFront(&plist); // // printf("n"); // SLTPrint(plist); //} //void testSLTNode4() //{ // SLTNode* plist = NULL; // SLTPushFront(&plist, 2); // SLTPushFront(&plist, 3); // SLTPushFront(&plist, 5); // // SLTNode *p = SLTFind(plist, 5); // SLTInsertAfter(p, 99); // // SLTPrint(plist); //} //void testSLTNode5() //{ // SLTNode* plist = NULL; // SLTPushBack(&plist, 1); // SLTPushBack(&plist, 2); // SLTPushBack(&plist, 5); // // SLTNode* p = SLTFind(plist, 1); // SLTInsertAfter(&plist,p , 6); // // SLTPrint(plist); //} void testSLTNode6() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushFront(&plist, 4); SLTPushFront(&plist, 5); SLTPushFront(&plist, 6); SLTNode* p = SLTFind(plist, 4); SLTInsert(&plist,p, 100); SLTPrint(plist); p = SLTFind(plist, 5); SLTInsertAfter(&plist,p, 200); SLTPrint(plist); p = SLTFind(plist, 100); SLTErase(&plist, p); SLTPrint(plist); p = NULL; SLTDestroy(&plist); SLTPrint(plist); } int main() { //test1(); //testSLTNode2(); //testSTLNode3(); //testSLTNode4(); //testSLTNode5(); testSLTNode6(); return 0; }

707ac00b85a147ffa61c5dc06a2fe02f.png

 运行结果:

261e991e051e47cc9825ea58ce16e0f7.png

最后

以上就是称心小懒猪最近收集整理的关于【数据结构与算法】单链表的增删查改(代码+图解)顺序表和链表的特点:分析:尾删完整代码:的全部内容,更多相关【数据结构与算法】单链表内容请搜索靠谱客的其他文章。

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

评论列表共有 0 条评论

立即
投稿
返回
顶部