链表
链，是一种什么样的东西呢？现实生活中我们都见过铁链金链和银链，它们都有一个特点，是一个环节一个环节环环相扣连接在一起的。而链表，则是一种具有相似结构的数据结构。
在链表中，每一个环节，即链结，都需要负责实现两个功能：
- 记录某些数值；
- 指向下一链结。
一般而言，链表可以分为两种，一种头链结为空仅指向第二个链结，另一种头链结不为空。这里我们只介绍前面一种。
定义结构体
在此之前我们已经达成了对于链结功能的共识，为了方便我们将每一个小的链结都定义成一个结构体，即：
1
2
3
4
5
| struct listnode
{
int element;
struct listnode* next;
};
|
在这个结构体中，我们定义了两个成员整型变量element和结构体指针变量next。其中，element负责执行第一个功能，记录某些数值，而next负责指向下一个链结。
初始化
网上很多教程在初始化时会提前预想可能的链结个数，本教程奉行即插即建即用原则，在初始化时仅对头链结进行进行初始化。和顺序表一样，我们可以用typedef函数将结构体指针重命名以便于后续操作，即：
1
2
3
4
5
6
7
| typedef struct listnode* Node;
void setuphead(Node headnode)
{
headnode=malloc(sizeof(struct listnode));
headnode->next=NULL;
}
|
在这个代码中，我们用malloc()函数为头链结申请了一块空间，接着保证不指向其他链结。
判空
有时我们需要判断一个链表是否为空，根据链表的性质，我们只需要判断头链结是否指向其他链结即可，即：
1
2
3
4
5
6
| int emptylist(Node headnode)
{
if(headnode->next)
return 1;
return 0;
}
|
插入
和链子一样，链表的插入只需要将插入项与理论上的下一链结连接，再将原来连接这一链结的前一链结链接插入项即可。
这个过程描述起来有些抽象，其实很多人对链表这个概念到现在都很模糊，无妨，且看下面的流程图：
在上述流程图中，我们我们表明了链结的序号，其中，序号0即为头链结。
至此我们已经知道了链表插入的操作流程，接下来我们就可以写程序来实现这个功能了，即：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int insertlist(Node head, int element, int index)
{
if(index<1)
return 0;
while(--index)
{
head=head->next;
if(head==NULL)
return 0;
}
Node node=malloc(sizeof(struct listnode));
if(node==NULL)
return 0;
node->element=element;
node->next=head->next;
head->next=node;
return 1;
}
|
删除
与插入相似的，从链表中删除一个元素只需要断开该元素与指向这个元素的链结之间的联系，并且将指向该元素的链结指向该元素指向的链结。
乍一听可能有些抽象，这里我们同样用一个流程图来表述：
通过该流程图，我们可以很好地理解删除的全过程，即：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int deletelist(Node head, int index)
{
if(index<1)
return 0;
while(--index)
{
head=head->next;
if(head==NULL)
return 0;
}
if(head->next==NULL)
return 0;
Node tmp=head->next;
head->next=head->next->next;
free(tmp);
tmp=NULL;
return 1;
}
|
查找长度
和顺序表不一样的是，我们在构建链表结构体时并没有引入一个变量来表示链表的长度，但是根据链表的定义，我们可以很容易地知道，一个链表的最后一个链结并不指向其他链结，所以我们只需要从头开始遍历整个链表，找到那个特殊的链结即可，即：
1
2
3
4
5
6
7
8
9
10
| int sizelist(Node head)
{
int i=1;
while(head)
{
head=head->next;
i++;
}
return i;
}
|
查找元素
在查找元素这个操作中，我们可以很容易采取遍历查找的方式来实现，即：
1
2
3
4
5
6
7
8
9
10
11
12
13
| int findlist(Node head, int element)
{
head=head->next;
int i=1;
while(head)
{
if(head->element==element)
return i;
head=head->next;
i++;
}
return 0;
}
|
查找索引
和顺序表不一样的是，我们在定义链表结构体时并没有引入索引这一变量，这也就导致了我们在查找索引时必须要从表头开始查找，因而在执行查找索引这一操作上链表的效率低于顺序表。
我们可以很容易地用遍历的方法来实现查找索引的功能，即：
1
2
3
4
5
6
7
8
9
10
11
12
13
| int* getlist(Node head, int index)
{
if(index<1)
return 0;
do
{
head=head->next;
if(head==NULL)
return 0;
}
while(--index);
return &head->element;
}
|
打印
当我们想要实现打印链表功能时，我们只需要从头开始边遍历整个链表边打印元素直至链结不再指向下一链结为止，即：
1
2
3
4
5
6
7
8
9
| void printlist(Node head)
{
while(head->next)
{
head=head->next;
printf("%d ",head->element);
}
printf("\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
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
| #include<stdio.h>
#include<stdlib.h>
struct listnode
{
int element;
struct listnode* next;
};
typedef struct listnode* Node;
void setuphead(Node headnode)
{
headnode=malloc(sizeof(struct listnode));
headnode->next=NULL;
}
int emptylist(Node headnode)
{
if(headnode->next)
return 1;
return 0;
}
int insertlist(Node head, int element, int index)
{
if(index<1)
return 0;
while(--index)
{
head=head->next;
if(head==NULL)
return 0;
}
Node node=malloc(sizeof(struct listnode));
if(node==NULL)
return 0;
node->element=element;
node->next=head->next;
head->next=node;
return 1;
}
int deletelist(Node head, int index)
{
if(index<1)
return 0;
while(--index)
{
head=head->next;
if(head==NULL)
return 0;
}
if(head->next==NULL)
return 0;
Node tmp=head->next;
head->next=head->next->next;
free(tmp);
tmp=NULL;
return 1;
}
int sizelist(Node head)
{
int i=1;
while(head)
{
head=head->next;
i++;
}
return i;
}
int findlist(Node head, int element)
{
head=head->next;
int i=1;
while(head)
{
if(head->element==element)
return i;
head=head->next;
i++;
}
return 0;
}
int* getlist(Node head, int index)
{
if(index<1)
return 0;
do
{
head=head->next;
if(head==NULL)
return 0;
}
while(--index);
return &head->element;
}
void printlist(Node head)
{
while(head->next)
{
head=head->next;
printf("%d ",head->element);
}
printf("\n");
}
int main()
{
...
}
|
参考资料
本教程参考资料如下：
返回目录
你可以点击此处返回或查看目录。
