单链表的插入
按位序插入（带头结点）：在表L中的第i个位置上插入指定元素e（最好O(1),最坏O(n),平均O(n)）
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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LNode{ //LNode:结点
int data; //数据域：每个结点存放一个数据元素
struct LNode *next; //指针域：指针指向下一个结点
}LNode,*LinkList; //typedef struct LNode *LinkList; 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
(*L)=(LNode *)malloc(sizeof(LNode)); //分配一个头结点,并使得头指针*L指向这个头结点
if((*L) == NULL){ //内存不足，分配失败
return false;
}
(*L)->data=0; //头结点不存储数据
(*L)->next=NULL; //头结点之后暂时还没有结点
return true;
}
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList *L,int i,int e){
if(i<1){
return false;
}
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=*L; //L指向头结点，头结点是第0个结点(不存数据)
while(p != NULL && j<i-1){ //循环找到第i-1个结点
p=p->next;
j++;
}
if(p == NULL){ //i值不合法
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next; //这行代码跟下一行代码顺序不能调换
p->next=s; //将结点s连到p之后
return true; //插入成功
}
int main(){
LinkList L; //等价于LNode *L; 声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
InitList(&L); //初始化一个空表
//...后续代码
if(ListInsert(&L, 2, 3)){ //在第2个位置插入元素3
printf("插入成功");
}
else{
printf("插入失败");
}
}
|
按位序插入(不带头结点)：因为不存在“第0个”结点，因此i=1时需要特殊处理
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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LNode{ //LNode:结点
int data; //数据域：每个结点存放一个数据元素
struct LNode *next; //指针域：指针指向下一个结点
}LNode,*LinkList; //typedef struct LNode *LinkList; 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始化一个空的链表(不带头结点)
bool InitList(LinkList *L){
(*L)=NULL; //空表，暂时还没有任何结点，防止脏数据
return true;
}
//在第i个位置插入元素e(不带头结点)
bool ListInsert(LinkList *L,int i,int e){
if(i<1){
return false;
}
//如果不带头结点，则插入、删除第1个元素时，需要更改头指针L
if(i == 1){ //插入第1个结点的操作与其他结点操作不同
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=*L;
*L=s; //头指针指向新结点
return true;
}
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=*L; //L指向头结点，头结点是第0个结点(不存数据)
while(p != NULL && j<i-1){ //循环找到第i-1个结点
p=p->next;
j++;
}
if(p == NULL){ //i值不合法
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next; //这行代码跟下一行代码顺序不能调换
p->next=s; //将结点s连到p之后
return true; //插入成功
}
int main(){
LinkList L; //等价于LNode *L; 声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
InitList(&L); //初始化一个空表
//...后续代码
if(ListInsert(&L, 2, 3)){ //在第2个位置插入元素3
printf("插入成功");
}
else{
printf("插入失败");
}
}
|
指定结点的后插操作（O(1)）：
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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LNode{ //LNode:结点
int data; //数据域：每个结点存放一个数据元素
struct LNode *next; //指针域：指针指向下一个结点
}LNode,*LinkList; //typedef struct LNode *LinkList; 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
(*L)=(LNode *)malloc(sizeof(LNode)); //分配一个头结点,并使得头指针*L指向这个头结点
if((*L) == NULL){ //内存不足，分配失败
return false;
}
(*L)->data=0; //头结点不存储数据
(*L)->next=NULL; //头结点之后暂时还没有结点
return true;
}
//后插操作：在p结点之后插入元素e(带头结点)
bool InsertNextNode(LNode *p,int e){
if(p == NULL){ //i值不合法
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s == NULL){ //内存分配失败，某些情况下有可能分配失败（如内存不足）
return false;
}
s->data=e; //用结点s保存数据元素e
s->next=p->next; //这行代码跟下一行代码顺序不能调换
p->next=s; //将结点s连到p之后
return true; //插入成功
}
int main(){
LinkList L; //等价于LNode *L; 声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
InitList(&L); //初始化一个空表
//...后续代码
if(InsertNextNode(L, 3)){ //在p结点位置后插入元素3
printf("插入成功");
}
else{
printf("插入失败");
}
}
|
指定结点的前插操作：在p结点之前插入元素e（O(1)）
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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LNode{ //LNode:结点
int data; //数据域：每个结点存放一个数据元素
struct LNode *next; //指针域：指针指向下一个结点
}LNode,*LinkList; //typedef struct LNode *LinkList; 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
(*L)=(LNode *)malloc(sizeof(LNode)); //分配一个头结点,并使得头指针*L指向这个头结点
if((*L) == NULL){ //内存不足，分配失败
return false;
}
(*L)->data=0; //头结点不存储数据
(*L)->next=NULL; //头结点之后暂时还没有结点
return true;
}
//前插操作：在p结点之前插入元素e(带头结点)
bool InsertPriorNode(LNode *p,int e){
if(p == NULL){ //i值不合法
return false;
}
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s == NULL){ //内存分配失败，某些情况下有可能分配失败（如内存不足）
return false;
}
s->next=p->next;
p->next=s; //新结点s连到p之后
s->data=p->data; //将p中元素复制到s中
p->data=e; //p中元素覆盖为e
return true; //插入成功
}
int main(){
LinkList L; //等价于LNode *L; 声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
InitList(&L); //初始化一个空表
//...后续代码
if(InsertPriorNode(L, 3)){ //在p结点位置前插入元素3
printf("插入成功");
}
else{
printf("插入失败");
}
}
|
单链表的删除
按位序删除(带头结点，最坏、平均O(n),最好O(1))：删除表L中第i个位置的元素，并用e返回删除元素的值（找到第i-1个结点，并将其指针指向第i+1个结点，并释放第i个结点）
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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LNode{ //LNode:结点
int data; //数据域：每个结点存放一个数据元素
struct LNode *next; //指针域：指针指向下一个结点
}LNode,*LinkList; //typedef struct LNode *LinkList; 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
(*L)=(LNode *)malloc(sizeof(LNode)); //分配一个头结点,并使得头指针*L指向这个头结点
if((*L) == NULL){ //内存不足，分配失败
return false;
}
(*L)->data=0; //头结点不存储数据
(*L)->next=NULL; //头结点之后暂时还没有结点
return true;
}
//按位序删除(带头结点)
bool ListDelete(LinkList *L,int i,int *e){
if(i<1){
return false;
}
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p=*L; //L指向头结点，头结点是第0个结点(不存数据)
while(p != NULL && j<i-1){ //循环找到第i-1个结点
p=p->next;
j++;
}
if(p == NULL){ //i值不合法
return false;
}
if(p->next == NULL){ //在第i-1个结点之后已无其他结点
return false;
}
LNode *q=p->next; //令q指向被删除结点
*e=q->data; //用e返回元素的值
p->next=q->next; //将*q结点从链中断开
free(q); //释放结点的存储空间
return true; //删除成功
}
int main(){
LinkList L; //等价于LNode *L; 声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
InitList(&L); //初始化一个空表
//...后续代码
int e=-1; //用变量e把删除的元素“带回来”
if(ListDelete(&L, 2, &e)){
printf("已删除第2个元素，删除元素值为%d\n",e);
}
else{
printf("删除失败\n");
}
}
|
指定结点的删除（O(1)）：
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
| #include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
typedef struct LNode{ //LNode:结点
int data; //数据域：每个结点存放一个数据元素
struct LNode *next; //指针域：指针指向下一个结点
}LNode,*LinkList; //typedef struct LNode *LinkList; 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点
//初始化一个单链表(带头结点)
bool InitList(LinkList *L){
(*L)=(LNode *)malloc(sizeof(LNode)); //分配一个头结点,并使得头指针*L指向这个头结点
if((*L) == NULL){ //内存不足，分配失败
return false;
}
(*L)->data=0; //头结点不存储数据
(*L)->next=NULL; //头结点之后暂时还没有结点
return true;
}
//删除指定结点p(带头结点)
//如果p是最后一个结点，这段代码就有点问题了，解决办法只能从表头开始依次寻找p的前驱，时间复杂度为O(n)
//单链表的局限性：无法逆向检索，有时候不太方便
bool DeleteNode(LNode *p){
if(p == NULL){
return false;
}
LNode *q=p->next; //令q指向*p的后继结点
p->data=p->next->data; //和后继结点交换数据域
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放后继结点的存储空间
return true; //删除成功
}
int main(){
LinkList L; //等价于LNode *L; 声明一个指向单链表的第一个结点的指针，注意此处并没有创建一个结点
InitList(&L); //初始化一个空表
//...后续代码
if(DeleteNode(L)){
printf("删除成功\n");
}
else{
printf("删除失败\n");
}
}
|
