2.1 最简单的结构：线性表
从本节开始将讲解各种常用的数据结构，首先介绍的是线性表。线性表是一种典型的线性结构，也是最简单、应用十分广泛的数据结构，它是其他数据结构的基础。本节介绍线性表的两种形式：顺序线性表和链式线性表。
2.1.1 线性表的概念
由若干个数据组成的集合可看做一个线性表。线性表中的数据元素之间的关系是一对一，即除了第一个和最后一个元素外，其他元素都是首尾相接。例如，某班学生学号组成的数据就是一个线性表，如图2-1a所示。在该图中每一个学号为一个数据元素。
再看看更复杂的情况，可以将一组数据看做一个单独的数据元素，如图2-1b所示，将每个学生的信息作为一个数据元素，则所有学生的信息就组成一个线性表（每个学生的信息为一行，看做一个数据元素，从上向下就组成了一个线性表）。
图2-1 线性表
由图2-1所示的数据可看出，线性表是一个线性结构，它是一个含有n个节点（数据元素）的有限序列。
注意 不同线性表的数据元素可以不同，但对于同一线性表，各数据元素必须具有相同的数据类型，即同一线性表中各数据元素具有相同的类型，每个数据元素的长度相同。
线性表数据结构具有以下特征：
·有且只有一个“首元素”，它没有直接前驱，只有一个直接后继；
·有且只有一个“末元素”，它没有直接后继，只有一个直接前驱；
·其他元素均有一个直接前驱和直接后继；
·元素之间为一对一的线性关系
在计算机中保存线性表时，一般可用顺序存储结构和链式存储结构两种方法。顺序存储结构的线性表称为顺序表，链式存储的线性表称为链表。
对于线性表，主要可进行以下操作：
·添加节点；
·插入节点；
·删除节点；
·查找节点；
·遍历节点；
·统计节点数。
下面将分别介绍在顺序表和链表中实现这些操作的代码。
提示 队列、栈是线性表的特殊情况，本章后面也将介绍这两种线性表的操作。
2.1.2 操作顺序表
采用顺序存储方式的线性表称为顺序表。顺序表是线性表的一种最简单和最常用的方式，这种方式用一组地址连续的存储单元依次保存线性表中的数据元素，如图2-2所示。
图2-2 顺序表的存储示意图
顺序结构是将表中的元素一个接一个地存入一组连续的存储单元中。由于顺序表是依次存放的，因此只要知道该顺序表的首地址及每个数据元素所占用的存储长度，就很容易计算出任何一个数据元素的位置，也可以很方便地将数据元素添加到顺序表中。
要访问第i个数据元素，可使用以下公式计算出第i个元素的存储位置L：
L = (i-1)*数据元素长度
例如，若数据元素长度为4字节，则第5个元素的存储位置（相对位置）为：
L = (5-1)*4 L = 16
即，保存第5个数据元素的地址相对于线性表的首位置偏移16个字节，从这里开始保存第5个数据元素。
了解顺序表的存储结构后，就可编写代码来操作顺序表了。
在编写具体的C语言代码之前，首先说一下代码组织的约定，为了让操作这些数据结构的代码具有一定的通用性，每种数据结构使用3个文件来保存，分别是：
·头文件：用来保存数据结构的定义、操作函数的原型声明等。程序员可以修改其中的数据结构定义，以适应不同的需要。
·作函数文件：用来保存操作数据结构的相关函数，这个文件的内容应该固定，程序员一般不能对其进行修改，只是直接调用其中的函数即可（最好将其编译为一个库文件）。该文件中不应有main函数。
·试文件（调用文件）：在该文件中应包含上面所列的两个文件，然后编写代码实现对数据的操作。在该文件中编写main函数。
1．定义顺序表的结构
由于C语言中的数组也是采用顺序存储的方式，因此，可使用数组来模拟顺序表的保存形式。在顺序表中还需定义一个变量，用来保存顺序表中已有元素的数量，因此，可使用以下结构来定义顺序表结构。
提示 操作顺序表的代码较长，为了讲解方便，将只显示需要的代码，对同一个源文件，行号的编写是连续的，以便于在文字中参照引用。完整的代码可参见源代码中对应章节的相应文件。
【程序2-1】操作顺序表的头文件“2-1 SeqList.h”
1 #include <stdio.h>
2 #include <string.h>
3 #define MAXSIZE 100 //定义顺序表的最大长度
4
5 typedef struct //定义顺序表结构
6 {
7 DATA ListData[MAXSIZE+1]; //保存顺序表的数组
8 int ListLen; //顺序表已存节点的数量
9 }SeqListType;
【程序说明】
·第3行定义了顺序表能保存的最大节点数，即顺序表的最大长度。
·第5~9行定义顺序表的结构，其中字段ListData为顺序表中的数据，是一个一维数组，为了方便操作，设置该数组序号为0的序号不使用，因此定义的数组大小须比MAXSIZE大1；字段ListLen保存顺序表中实际保存的节点数量。
提示 在很多介绍数据结构的书籍中都只是使用简单数据类型（如int、double等）来演示线性表的操作，其代码比较简单。本例中使用一个复杂的数据类型DATA（由结构体定义的多种数据）作为节点，这种线性表的操作更具有实际意义。
2．定义顺序表的操作
接着，在操作顺序表的头文件中定义操作顺序表的函数原型，具体代码如下：
10 void SeqListInit(SeqListType *SL); //初始化顺序表 11 int SeqListLength(SeqListType *SL); //返回顺序表的元素数量 12 int SeqListAdd(SeqListType *SL,DATA data); //向顺序表中添加元素 13 int SeqListInsert(SeqListType *SL,int n,DATA data); //向顺序表中插入元素 14 int SeqListDelete(SeqListType *SL,int n); //删除顺序表中的数据元素 15 DATA *SeqListFindByNum(SeqListType *SL,int n); //根据序号返回元素 16 int SeqListFindByCont(SeqListType *SL,char *key); //按关键字查找 17 int SeqListAll(SeqListType *SL); //遍历顺序表中的内容
各函数的作用参见右侧的注释。
3．初始化顺序表
接下来就需要编写操作顺序表的各函数，这些函数的代码保存在名为“2-2 SeqList.c”的文件中。首先介绍初始化顺序表，要初始化顺序表，只需要设置该顺序表的元素长度为0即可，以后添加元素到顺序表时就从第1个位置开始。
提示 如果顺序表中原来已有数据，也会被覆盖。
顺序表初始化具体代码如下：
【程序2-2】操作顺序表的函数文件“2-2 SeqList.c”
1 void SeqListInit(SeqListType *SL) //初始化顺序表
2 {
3 SL->ListLen=0; //初始化时, 设置顺序表长度为0
4 }
4．顺序表的长度
在顺序表结构中，字段ListLen中保存着顺序表中节点的数量，要获得顺序表的长度，只需返回该字段中的值即可。具体代码如下：
5 int SeqListLength(SeqListType *SL) //返回顺序表的元素数量
6 {
7 return (SL->ListLen);
8 }
5．添加节点
添加节点的操作是在顺序表的最后位置添加一个节点数据。在添加节点时，首先要判断顺序表中的空间是否已使用完，未满再将传入的数据保存到顺序表的下一位置即可。具体代码如下：
9 int SeqListAdd(SeqListType *SL,DATA data) //增加节点到顺序表尾部
10 {
11 if(SL->ListLen>=MAXSIZE) //顺序表已满
12 {
13 printf("顺序表已满, 不能再添加节点了!\n");
14 return 0;
15 }
16 SL->ListData[++SL->ListLen]=data; //保存数据到顺序表尾部
17 return 1;
18 }
【程序说明】
·该函数使用了两个参数，其中SL是指向顺序表的指针（即需要添加节点的顺序表），而data则是需要添加到顺序表中的数据。
·第16行将传入的数据复制到顺序表中，并将保存顺序表节点数量的变量ListLen增加1。
编程陷阱 在添加节点时，首先要判断顺序表中的空间是否已使用完，若不进行判断，则可能会将数据添加到不可预知的内存空间，从而得不到正确的结果，造成不可预知的错误。
6．插入节点
在顺序表中插入节点的操作比较麻烦，因为顺序表中的所有节点都是按序号紧邻存放的，如果要在其中插入一个节点，则需要将插入点后面的节点数据向后移动一个位置，以便在空出的位置保存插入节点的数据，如图2-3所示。
提示 在新节点插入时，需要移动大量的元素，并且还需要修改顺序表的长度，即元素数量加1。
图2-3 插入节点
插入节点的代码如下：
19 int SeqListInsert(SeqListType *SL,int n,DATA data) //向顺序表中插入元素
20 {
21 int i;
22 if(SL->ListLen>=MAXSIZE) //顺序表节点数量已超过最大数量
23 {
24 printf("顺序表已满, 不能插入节点!\n");
25 return 0; //返回0表示插入不成功
26 }
27 if(n<1 || n>SL->ListLen-1) //插入节点序号不正确
28 {
29 printf("插入节点序号错误, 不能插入元素!\n");
30 return 0; //返回0, 表示插入不成功
31 }
32 for(i=SL->ListLen;i>=n;i--) //将顺序表中的数据向后移动
33 SL->ListData[i+1]=SL->ListData[i];
34 SL->ListData[n]=data; //插入节点
35 SL->ListLen++; //顺序表节点数量增加1
36 return 1; //返回1,表示成功插入
37 }
【程序说明】
·该函数使用了3个参数，其中SL是指向顺序表的指针（即需要插入节点的顺序表），而参数n指定要插入的序号，data则是需要插入到顺序表中的数据。
·第22~26行判断顺序表的节点数量是否超过最大值。
·第27~31行判断插入的序号是否正确。
·第32、33行从顺序表的表尾开始，将元素逐个向后移动，将第n个节点移向第n+1个节点位置。
·第34行将插入的数据data复制到第n个节点位置。
·第35行将顺序表节点数量的变量ListLen增加1。
提示 如果在第1个元素处插入新节点，则需要将顺序表中的所有节点都移动一次，因此，在顺序表中插入节点操作的效率是非常低的。
7．删除节点
与插入节点的操作类似，删除节点也需要大量移动数据，若需删除序号为n的节点，则要将序号n+1至尾节点的所有节点都向前移动，将节点移动之后，还需要修改顺序表元素数量（减1）。具体代码如下：
38 int SeqListDelete(SeqListType *SL,int n) //删除顺序表中的数据元素
39 {
40 int i;
41 if(n<1 || n>SL->ListLen+1) //删除节点序号不正确
42 {
43 printf("删除节点序号错误, 不能删除节点!\n");
44 return 0; //返回0, 表示删除不成功
45 }
46 for(i=n;i<SL->ListLen;i++) //将顺序表中的数据向前移动
47 SL->ListData[i]=SL->ListData[i+1];
48 SL->ListLen--; //顺序表元素数量减1
49 return 1; //返回1，表示成功删除
50 }
【程序说明】
·该函数使用了两个参数，其中SL是指向顺序表的指针（即需要删除节点的顺序表），而参数n指定删除节点的序号。
·第46、47行将n+1后面的所有节点数据向前移动，完成删除操作。第48行将节点数量减1，表示删除节点后的节点总数。
编程陷阱 在删除节点时，首先要判断要删除的节点序号是否在指定范围之内，若不进行判断，则可能会将错误的数据移到顺序表中。
8．按序号查找节点
创建好顺序表之后，最常用的操作就是在顺序表中进行查找，以获取相应节点的数据。按序号查找节点就是返回指定序号的节点数据，其代码如下：
51 DATA *SeqListFindByNum(SeqListType *SL,int n) //根据序号返回数据元素
52 {
53 if(n<1 || n>SL->ListLen+1) //元素序号不正确
54 {
55 printf("节点序号错误, 不能返回节点!\n");
56 return NULL; //返回NULL, 表示不成功
57 }
58 return &(SL->ListData[n]); //返回找到节点的指针
59 }
【程序说明】
·该函数使用了两个参数，其中SL是指向顺序表的指针（即需要查找节点的顺序表），而参数n指定要查找节点的序号。
·第58行返回序号为n的节点指针。
提示 该函数的返回值是一个指向节点数据类型的指针，通过该指针就可以访问到所查找序号的节点数据。
9．按关键字查找节点
在实际的查找操作中，可能更多的是按关键字查找。例如，在保存学生信息的顺序表中，按学号查询是比较常用的。因此，在定义顺序表的查找操作时，应提供按关键字查找的功能。具体代码如下：
60 int SeqListFindByCont(SeqListType *SL,char *key) //按关键字查询结点
61 {
62 int i;
63 for(i=1;i<=SL->ListLen;i++)
64 if(strcmp(SL->ListData[i].key,key)==0) //如果找到所需节点
65 return i; //返回节点序号
66 return 0; //遍历后仍没有找到, 则返回0
67 }
【程序说明】
·该函数使用了两个参数，其中SL是指向顺序表的指针（即需要查找节点的顺序表），而参数key是要查找节点的关键字。
·第63~65行遍历顺序表，逐个比较关键字。若节点的关键字与查找关键字相同，则返回节点的序号；若遍历后未找到指定关键字的节点，则返回0。
提示 该函数的返回值是节点的序号，而不是一个指向节点的指针。因为已经有按序号返回节点指针的函数，所以这里返回序号即可。设置为返回序号，还可方便插入操作，如需要将新增节点插入某个节点处，则可先按关键字查询返回序号，再调用SeqListInsert函数即可。
10．测试顺序表操作
定义好顺序表的操作函数后，接下来编写测试这些功能的程序。具体代码如下：
【程序2-3】测试顺序表操作的程序“2-3 SeqListTest.c”
1 #include <stdio.h>
2 typedef struct
3 {
4 char key[15]; //节点的关键字
5 char name[20];
6 int age;
7 } DATA; //定义节点类型
8 #include "2-1 SeqList.h" //引入自定义的头文件
9 #include "2-2 SeqList.c" //引入自定义的作函数文件
10 int SeqListAll(SeqListType *SL) //遍历顺序表中的节点
11 {
12 int i;
13 for(i=1;i<=SL->ListLen;i++)
14 rintf("(%s,%s,%d)\n",SL->ListData[i].key,SL->ListData[i].name,SL->ListData[i].age);
15 }
【程序说明】
·第2~7行定义节点的数据类型，除了保存常用数据外，还增加了一个关键字字段，方便对节点的内容进行查询。对于关键字段，这里采用一个字符串来保存，因为这样具有更大的灵活性，既可以保存数字，也可以保存字符。
·第8、9行包含操作顺序表的头文件和函数。
·第10~15行为遍历顺序表各节点的函数。
技巧 由于DATA类型的定义不同，需要修改本函数第14行中输出的内容，因此将该函数编写在测试文件中，这样可保证操作函数的文件“2-2 SeqList.c”不被修改。
提示 以上代码中，第8~9行又是一个包含文件的指令，看起来有点另类。也可将以上内容单独保存，作为测试文件的头文件。
接下来就是测试操作顺序表的主函数main的代码：
16 int main()
17 {
18 int i;
19 SeqListType SL; //定义顺序表变量
20 DATA data,*data1; //定义节点保存数据类型变量和指针变量
21 char key[15]; //保存关键字
22
23 SeqListInit(&SL); //初始化顺序表
24
25 do { //循环添加节点数据
26 printf("输入添加的节点(学号 姓名 年龄):");
27 fflush(stdin); //清空输入缓冲区
28 scanf("%s%s%d",&data.key,&data.name,&data.age);
29 if(data.age) //若年龄不为0
30 {
31 if(!SeqListAdd(&SL,data))//若添加节点失败
32 break; //退出死循环
33 }else //若年龄为0
34 break; //退出死循环
35 }while(1);
36 printf("\n顺序表中的节点顺序为:\n");
37 SeqListAll(&SL); //显示所有节点数据
38
39 fflush(stdin); //清空输入缓冲区
40 printf("\n要取出节点的序号:");
41 scanf("%d",&i); //输入节点序号
42 data1=SeqListFindByNum(&SL,i); //按序号查找节点
43 if(data1) //若返回的节点指针不为NULL
44 printf("第%d个节点为:(%s,%s,%d)\n",i,data1->key,data1->name,data1->age);
45
46 fflush(stdin); //清空输入缓冲区
47 printf("\n要查找节点的关键字:");
48 scanf("%s",key); //输入关键字
49 i=SeqListFindByCont(&SL,key); //按关键字查找, 返回节点序号
50 data1=SeqListFindByNum(&SL,i); //按序号查询, 返回节点指针
51 if(data1) //若节点指针不为NULL
52 printf("第%d个节点为:(%s,%s,%d)\n",i,data1->key,data1->name,data1->age);
53 getch();
54 return 0;
55 }
程序的代码很简单，关键部分都添加了注释，就不再一一解释了。
提示 由于本书篇幅所限，顺序表中其他各操作函数未在上面的例子中进行测试，读者可将相关测试功能添加到上面的代码中。
编译执行以上代码，将首先显示输入数据的提示，按要求输入相应的数据后，即可显示、查询顺序表中各节点的数据，具体过程如图2-4所示。
图2-4 【程序2-3】执行结果
在图2-4中共输入了5个节点数据，最后输入三个0结束输入（从main函数中第29~34行的代码可看出，只需要第3个数据为0即可退出输入状态），接着在下方将显示所输入节点的所有数据，然后要求用户输入一个序号，即可显示该序号对应节点的数据，最后要求用户输入关键字，即可显示关键字所对应的节点数据。
2.1.3 操作链表
顺序表是将数据按顺序保存到内存中，因此在顺序表中存取数据很方便，但同时也带来一些问题，例如，向顺序表中插入元素时，需要移动大量的数据。最坏的情况下，如果每次都是要在顺序表的首位置插入元素，则需要将顺序表中所有元素都向后移，效率非常低。
编程经验 对于需要经常插入元素的线性表，可采用链式存储的链表。链表是采用动态存储分配的一种结构。可以根据需要申请内存单元。
链表的结构如图2-5所示，链表中每个节点都应包括两个部分：一部分是实际数据，另一部分是下一个节点的地址。操作链表时，需定义一个“头指针”变量（一般以head表示），该指针变量指向链表的第一个节点，第一个节点又指向第二个节点，直到最后一个节点。最后一个节点不再指向其他节点，称为“表尾”，在表尾的地址部分放一个“NULL”（∧），表示“空地址”，链表到此结束。
图2-5 链表结构
图2-5所示的链表中，每个节点中只包含一个指针，一般称为单向链表。若每个节点包含两个指针，一个指向下一个节点，另一个指向上一个节点，称为双向链表。
在链表中，逻辑上相邻的节点在内存中并不一定相邻，逻辑相邻关系通过指针来实现。由于节点之间不要求连续存放，就可以通过malloc函数动态分配节点的存储空间。
编程陷阱 由于C语言程序不能自动回收动态分配的空间，因此，当删除某个节点时，应该使用free函数释放其占用的内存空间。
对于链表的访问只能从表头逐个查找，即通过head头指针找到第一个节点，再从第一个节点中的地址找到第二个节点……这样逐个比较，一直到找到需要的节点为止，而不能像顺序表那样进行随机访问，因此在链表中查找获取某个节点的数据时需要较长的过程。
下面介绍在C语言中操作单链表的代码。
1．定义链表的结构
图2-5所示的节点可使用以下结构来定义。
提示 操作链表的代码较长，为了讲解方便，将只显示需要的代码，对同一个源文件，行号的编写是连续的，以便于在文字中参照引用。完整的代码可参见源代码中对应章节的相应文件。
【程序2-4】操作链表的头文件“2-4 ChainList.h”
1 #include <stdlib.h> //引入内存分配头文件
2 typedef struct Node //定义链表节点结构
3 {
4 DATA data; //节点数据
5 struct Node *next; //节点指针
6 }ChainListType;
7 ChainListType *ChainListAddEnd(ChainListType *head,DATA data);
//添加节点到链表末尾
8 ChainListType *ChainListAddFirst(ChainListType *head,DATA data);
//添加节点到链表首部
9 ChainListType *ChainListFind(ChainListType *head,char *key);
//按关键字在链表中查找内容
10 ChainListType *ChainListInsert(ChainListType *head,char *findkey,DATA data);
//插入节点到链表指定位置
11 int ChainListDelete(ChainListType *head,char *key);
//删除指定关键字的节点
12 int ChainListLength(ChainListType *head);
//获取链表节点数量
【程序说明】
·因为要使用动态分配内存的函数malloc，因此在第1行包含头文件stdlib.h。
·第3~6行定义一个结构体作为链表节点的数据类型，节点的具体数据保存在一个结构DATA中，而指针next用来指向下一个节点。只有一个指向下一节点的指针，因此，这是一个单向链表，如果构建双向链表，则还需要增加一个指针，用来指向上一个节点。
·第7~12行为操作链表的函数原型。
提示 在定义链表的结构体中使用了一个名为DATA的类型，为了使操作链表的头文件和函数文件在使用时不进行修改，因此需将DATA类型定义在测试文件中。
2．添加节点至尾部
向链表添加节点有3种方式，分别为：
·在链表的后面（最后一个节点）添加一个节点；
·在链表的前面（第一个节点）添加一个节点；
·在链表中间指定处（可指定关键字）添加一个节点。
当需要在链表末尾增加节点时，由于一般情况下，链表只有一个头指针head，要在末尾添加节点就需要从头指针head开始逐个检查，直到找到最后一个节点（即表尾）。表尾节点的地址部分原来保存的是NULL，此时需将其设置为新增节点的地址（即原表尾节点指向新增节点），然后将新增节点的地址部分设置为NULL，即新增节点成为表尾。例如，在图2-5所示的链表末尾添加节点的过程如图2-6所示。
图2-6 在表尾添加节点
链表操作函数都保存在文件“2-5 ChainList.c”中，下面首先列出在链表末尾添加节点的操作代码：
【程序2-5】操作链表的函数文件“2-5 ChainList.c”
1 #include <string.h>
2 ChainListType *ChainListAddEnd(ChainListType *head,DATA data) //添加节点到链表结尾
3 {
4 ChainListType *node,*h;
5 if(!(node=(ChainListType *)malloc(sizeof(ChainListType)))) //为链表分配内存空间
6 {
7 printf("为保存节点数据申请内存失败!\n");
8 return NULL; //分配内存失败
9 }
10 node->data=data; //保存数据
11 node->next=NULL; //设置节点指针为空, 即为表尾
12 if(head==NULL) //是头指针
13 {
14 head=node; //链表头指针指向当前节点
15 return head; //返回头指针
16 }
17 h=head; //保存头指针
18 while(h->next!=NULL) //当指向下一节点的地址不为NULL时
19 h=h->next ; //指向下一个节点
20 h->next=node; //原末节点地址指向新增节点
21 return head; //返回头指针
22 }
【程序说明】
·该函数共有两个参数，其中head为链表头指针，data为节点保存的数据。
·第5~9行使用malloc函数申请保存节点数据的内存空间，如果分配内存成功，node中将保存指向该内存区域的指针。
·第10、11行将传入的data保存到申请的内存区域，并设置该节点中指向下一节点的指针值为NULL。
·第12~16行判断链表的头指针head是否为空，如为空，则使头指针指向当前节点。
·若头指针head不为NULL，则执行第17~19行，从第一个节点开始向后查找，直至找到最后一个节点，第20行使最后一个节点指向新增的节点即可。
提示 将节点添加到链表尾部时，如果只知道链表的头指针head，则需要执行上面程序中的第18、19行查找链表尾部。如果需要经常进行这种操作，可定义一个尾指针，指向链表尾部。这样，在进行尾部添加节点操作时，就可以省去第18、19行的查找过程，直接针对尾指针操作即可。
3．添加节点至首部
在链表首部添加节点的操作过程如图2-7所示。由于数据结构中定义了头指针head，因此，只需使新增节点指向头指针head所指向的节点，然后使头指针head指向新增节点即可。
在链表首部添加节点的操作代码如下：
23 ChainListType *ChainListAddFirst(ChainListType *head,DATA data)//添加结点到链表首部
24 {
25 ChainListType *node,*h;
26 if(!(node=(ChainListType *)malloc(sizeof(ChainListType)))) //为链表分配内存空间
27 {
28 printf("为保存节点数据申请内存失败!\n");
29 return NULL; //分配内存失败
30 }
31 node->data=data; //保存数据
32 node->next=head; //指向头指针所指节点
33 head=node; //头指针指向新增节点
34 return head;
35 }
图2-7 在表首添加节点
【程序说明】
·该函数共有两个参数，其中head为链表头指针，data为节点保存的数据。
·第26~30行使用malloc函数申请保存节点数据的内存空间，如果分配内存成功，node中将保存指向该内存区域的指针。
·第31~33行将传入的data保存到申请的内存区域，并使新增节点指向头指针head所指向的节点，然后设置头指针head指向新增节点。
提示 在第26行使用malloc函数申请内存时，如果内存分配失败，没有地方保存节点数据，只有退出该函数，并返回一个错误信息（本函数中返回NULL）给调用函数。
4．插入节点
插入节点就是在链表的中间部分增加节点，这时首先需要找到要插入的位置（这里是指逻辑位置，而不是物理位置），然后修改插入位置节点的指针，使其指向新增节点，而使新增节点指向原插入位置所指向的节点，具体过程如图2-8所示。
图2-8 插入节点到链表
插入节点到链表的操作代码如下：
36 ChainListType *ChainListInsert(ChainListType *head,char *findkey,DATA data)
//插入结点到链表指定位置
37 {
38 ChainListType *node,*node1;
39 if(!(node=(ChainListType *)malloc(sizeof(ChainListType)))) //申请保存节点的内存
40 {
41 printf("为保存节点数据申请内存失败!\n");
42 return 0; //分配内存失败
43 }
44 node->data=data; //保存节点中的数据
45 node1=ChainListFind(head,findkey);
46 if(node1) //若找到要插入的节点
47 {
48 node->next=node1->next; //新插入节点指向关键节点的下一节点
49 node1->next=node; //设置关键节点指向新插入节点
50 }else{
51 free(node); //释放内存
52 printf("未找到插入位置!\n");
53 }
54 return head; //返回头指针
55 }
【程序说明】
·该函数共有3个参数，其中head为链表头指针，参数findkey是用来在链表中进行查找的节点关键字，找到该节点后将在该节点后面添加节点数据，data为新增节点的数据。
·第39~43行使用malloc函数申请保存节点数据的内存空间，如果分配内存成功，node中将保存指向该内存区域的指针。
·第45行调用函数ChainListFind查找指定关键字的节点，并返回节点的指针（暂称其为目标节点），如果找到的节点有效，执行第48~49行，设置新增节点指向目标节点所指向的节点（这里读起来很绕口，可参见图2-8所示），再使目标节点指向新增节点。如果未找到目标节点，将不执行插入操作，执行第51行释放申请的内存空间。
5．查找节点
在链表中访问节点不如顺序表方便。对于保存在链表中的数据，可通过关键字进行查询，找到关键字相同的节点后，返回该节点的指针，方便调用程序处理。
提示 在上面的插入节点函数的第45行调用过查找节点函数ChainListFind，以找到需要添加节点的位置。
按关键字在链表中查找内容的代码如下：
56 ChainListType *ChainListFind(ChainListType *head,char *key) //按关键字在链表中查找内容
57 {
58 ChainListType *h;
59 h=head; //保存链表头指针
60 while(h) //若节点有效, 则进行查找
61 {
62 if(strcmp(h->data.key,key)==0) //若节点关键字与传入关键字相同
63 return h; //返回该节点指针
64 h=h->next; //处理下一节点
65 }
66 return NULL; //返回空指针
67 }
【程序说明】
·该函数共有两个参数，其中head为链表头指针，参数key是用来在链表中进行查找的节点关键字。
·第60~65行完成查找操作。首先从链表头指针开始，如果指针h的值不为NULL（即未到链表结尾），则执行第62行判断节点关键字与传入的关键字是否相等，若相等，则表示找到目标节点了，第63行返回该节点的指针；若关键字不相等，则使指针指向当前节点的下一节点，继续进行比较。
提示 因为关键字使用的是字符串，因此比较大小时调用字符串比较函数strcmp。
6．删除节点
在设计删除节点时，首先想到的是使用前面编写的ChainListFind函数找到要删除的节点，然后释放该节点所占用的内存空间即可。但是这样操作是有问题的，因为链表需要通过指针来进行链接，如果直接删除其中的某一个节点，则该节点的后续节点将丢失，导致无法进行操作。因此，删除节点不能只使用查找节点的方法来获取要删除的节点，还需要知道被删除节点的上一个节点，然后使被删除节点的上一个节点指向被删除节点的下一个节点。
也就是说，在查找需要删除的节点时，还需定义一个指针来指向前一节点。如图2-9所示，若需要删除指针h所指向的节点，可设置node指针所指节点的地址部分，使其指向h指针所指节点的下一节点，也就是使node指向的节点的地址部分指向指针h的下一节点（文字读起来很绕口，看图更清楚）。
图2-9 删除节点
删除节点的代码如下：
68 int ChainListDelete(ChainListType *head,char *key) //删除指定关键字的结点
69 {
70 ChainListType *node,*h; //node保存删除节点的前一节点
71 node=h=head;
72 while(h)
73 {
74 if(strcmp(h->data.key,key)==0) //找到关键字, 执行删除操作
75 {
76 node->next=h->next; //使前一节点指向当前节点的下一节点
77 free(h); //释放内存
78 return 1;
79 }else{
80 node=h; //指向当前节点
81 h=h->next; //指向下一节点
82 }
83 }
84 return 0; //未删除
85 }
【程序说明】
·该函数共有2个参数，其中head为链表头指针，参数key表示一个关键字，是链表中需要删除节点的关键字。
·第72~83行为一个循环，按关键字在整个链表中查找要删除的节点，若找到被删除节点，则执行第76行，设置上一节点（node指针所指节点）指向当前节点（h指针所指节点）的下一节点，即可完成链表中节点的逻辑删除，但这时被删除节点仍然保存在内存中，还需执行第77行的free函数，用来释放被删除节点所占用的内存空间。
·若当前节点不是要删除的节点，则执行第80行保存当前节点指针在node变量中，而让h指针指向下一节点，这样，在下一次循环时，h指针指向的节点就变为了当前节点，而node指针所指向的节点就成了上一节点。
提示 与查找函数ChainListFind相同，因关键字设置为字符串类型（即char数组），因此调用字符串比较函数strcmp来判断关键字是否相等。
7．链表的长度
与顺序表不同，链表在物理结构上没有相邻的要求，因此不能方便地得到其长度。要得到链表的长度，就必须遍历链表，逐个统计节点的个数。下面的代码可完成该功能：
86 int ChainListLength(ChainListType *head) //获取链表结点数量
87 {
88 ChainListType *h;
89 int i=0;
90 h=head;
91 while(h) //遍历整个链表
92 {
93 i++; //累加节点数量
94 h=h->next; //处理下一节点
95 }
96 return i; //返回节点数量
97 }
【程序说明】
·该函数只有一个参数head，表示链表的头指针。
·第91~95行统计节点的数量，第94行使指针h指向下一个节点。
8．测试链表操作
定义好链表的操作函数后，接下来编写测试这些功能的程序。具体代码如下。
【程序2-6】测试链表操作的程序“2-6 ChainListTest.c”
1 #include <stdio.h>
2 typedef struct //定义数据结构体
3 {
4 char key[15]; //关键字
5 char name[20];
6 int age;
7 }DATA; //数据节点类型
8 #include "2-4 ChainList.h" //引入自定义的头文件
9 #include "2-5 ChainList.c" //引入自定义的作函数文件
10 void ChainListAll(ChainListType *head) //遍历链表
11 {
12 ChainListType *h;
13 DATA data;
14 h=head;
15 printf("链表所有数据如下:\n");
16 while(h) //循环处理链表每个节点
17 {
18 data=h->data; //获取节点数据
19 printf("(%s,%s,%d)\n",data.key,data.name,data.age);
20 h=h->next; //处理下一节点
21 }
22 return;
23 }
【程序说明】
·第2~7行定义链表中的数据类型DATA，在该结构体中必须包含一个字符串类型的key，用来作为查询节点的依据，而结构体中的其他字段可根据需要进行设置。
·第8、9行包含操作链表的头文件和函数。
·第10~23行为遍历链表各节点的函数。
技巧 由于DATA类型的定义不同，需要修改本函数第19行中输出的内容，因此将该函数编写在测试文件中，这样可保证操作函数的文件“2-5 ChainList.c”不被修改。
提示 以上代码中，第8~9行又是一个包含文件的指令，看起来有点另类。也可将以上内容单独保存，作为测试文件的头文件。
接下来就是测试操作链表的主函数main的代码。
24 int main()
25 {
26 ChainListType *node, *head=NULL;
27 DATA data;
28 char key[15],findkey[15];
29
30 printf("输入链表中的数据, 包括关键字、姓名、年龄, 关键字输入0, 则退出:\n");
31 do{
32 fflush(stdin); //清空输入缓冲区
33 scanf("%s",data.key);
34 if(strcmp(data.key,"0")==0) break; //若输入0, 则退出
35 scanf("%s%d",data.name,&data.age);
36 head=ChainListAddEnd(head,data); //在链表尾部添加节点数据
37 }while(1);
38
39 printf("该链表共有%d个节点。\n",ChainListLength(head)); //返回节点数量
40 ChainListAll(head); //显示所有节点
41
42 printf("\n插入节点, 输入插入位置的关键字:") ;
43 scanf("%s",&findkey);//输入插入位置关键字
44 printf("输入插入节点的数据(关键字 姓名 年龄):");
45 scanf("%s%s%d",data.key,data.name,&data.age); //输入插入节点数据
46 head=ChainListInsert(head,findkey,data); //调用插入函数
47
48 ChainListAll(head); //显示所有节点
49
50 printf("\n在链表中查找, 输入查找关键字:");
51 fflush(stdin); //清空输入缓冲区
52 scanf("%s",key); //输入查找关键字
53 node=ChainListFind(head,key); //调用查找函数, 返回节点指针
54 if(node) //若返回节点指针有效
55 {
56 data=node->data; //获取节点的数据
57 printf("关键字%s对应的节点数据为(%s,%s,%d)\n" ,key,data.key,data.name,data.age);
58 }else //若节点指针无效
59 printf("在链表中未找到关键字为%s的节点!\n",key);
60
61 printf("\n在链表中删除节点, 输入要删除的关键字:");
62 fflush(stdin); //清空输入缓冲区
63 scanf("%s",key); //输入删除节点关键字
64 ChainListDelete(head,key); //调用删除节点函数
65 ChainListAll(head); //显示所有节点
66 getch();
67 return 0;
68 }
程序的代码很简单，关键部分都添加了注释，就不再一一解释了。
提示 由于本书篇幅所限，链表中其他各操作函数未在上面的例子中进行测试，读者可将相关测试功能添加到上面的代码中。
编译执行以上代码，将首先显示输入数据的提示，按要求输入相应的数据后，即可显示出添加到链表中的各节点的数据，具体过程如图2-10所示。
图2-10 【程序2-4】执行结果
在图2-10中分别进行了以下4个操作：
（1）输入了5个节点数据，接着在下方显示所输入节点的所有数据；
（2）要求用户插入节点的关键字，再接收用户输入的节点数据，下方即可看到插入节点后的所有数据；
（3）要求用户输入查找关键字，下方即可显示该关键字所对应的节点数据；
（4）最后要求输入删除节点的关键字，删除该节点后将显示链表中的所有数据。
2.1.4 实例：用链表制作通讯录
前面介绍了操作链表的相关函数，下面使用这些函数编写一个简单的通讯录管理程序。
【程序分析】
通常，在一个通讯录中可管理多人的联系信息，由于不能预知系统中需要管理多少联系人信息，因此使用链表来保存联系人将是一种好的方案。由于本书篇幅所限，本例只编写通讯录管理的主要代码。制作如图2-11所示的4个模块功能，包括增加联系人、查找联系人、删除联系人、显示联系人这4个模块。
图2-11 程序模块
为了使主函数简洁，将只在主函数中编写调用4个模块的代码，而4个模块分别使用4个函数来完成。下面列出通讯录程序的代码。
1．定义通讯录结构
【程序2-7】通讯录程序“2-7 AddressList.c”
在程序的首部定义通讯录的数据结构如下：
1 typedef struct //定义通信录结构体
2 {
3 char key[15]; //关键字(设置姓名为关键字)
4 char addr[20];
5 char telephone[15];
6 char mobile[12];
7 }DATA; //数据节点类型
8 #include <stdio.h>
9 #include "2-4 ChainList.h" //引入自定义头文件
10 #include "2-5 ChainList.c" //引入自定义的作函数文件
【程序说明】
·在第1~7行的DATA结构中，必须定义一个名为key的字符串，作为查找的关键字，其他字段可根据需要进行增减，如可增加QQ、E-mail地址等联系信息。
·第9、10行包含操作链表的头文件和函数文件。
2．编写显示联系人信息模块
要显示所有联系人的信息，其实就是遍历链表，逐个显示各节点的数据。因此，编写以下函数，以显示链表中所有联系人的信息。
11 void ChainListAll(ChainListType *head) //遍历链表
12 {
13 ChainListType *h;
14 DATA data;
15 h=head;
16 printf("链表所有数据如下:\n");
17 while(h) //循环处理链表每个节点
18 {
19 data=h->data; //获取节点数据
20 printf("姓名:%s\n",data.key);
21 printf("地址:%s\n",data.addr);
22 printf("电话:%s\n",data.telephone);
23 printf("手机:%s\n",data.mobile);
24 h=h->next; //处理下一节点
25 }
26 return;
27 }
以上代码将遍历链表，并显示每一个节点（联系人）的相关信息。
3．编写添加联系人模块
添加联系人就是向链表中添加节点的过程，最简单的方式就是将新联系人（新节点）直接添加到链表的头部。当在主函数中选择“输入联系人”时，将调用以下函数，用来向链表中添加新的联系人信息。
28 ChainListType *input(ChainListType *head) //向通讯录中输入的信息
29 {
30 DATA data;
31 printf("请输入联系人信息\n");
32 printf("姓名:");
33 scanf("%s",data.key);
34 printf("地址:");
35 scanf("%s",data.addr);
36 printf("电话:");
37 scanf("%s",data.telephone);
38 printf("手机:");
39 scanf("%s",data.mobile);
40 return ChainListAddFirst(head,data); //调用添加函数
41 }
【程序说明】
以上代码首先在第31~39行要求用户输入联系人的相关信息，然后执行第40行调用Chain-ListAddFirst函数将输入的信息添加到链表的首部。
提示 也可调用ChainListAddEnd函数将输入的联系人信息添加到链表的尾部。
4.编写查找联系人模块
查找联系人的过程可遍历链表，并逐个比较关键字，当找到符合要求的节点时，结束遍历过程。当在主函数中选择“查找联系人”时，将调用以下函数，让用户输入联系人姓名进行查找，然后显示出查找到的联系人信息，具体代码如下：
42 void find(ChainListType *head) //查找联系人
43 {
44 ChainListType *h;
45 DATA data;
46 char name[15];
47 printf("请输入查找姓名:");
48 scanf("%s",name);
49 h=ChainListFind(head,name); //调用查找函数
50 if(h) //查找节点指针有效
51 {
52 data=h->data; //获取节点数据
53 printf("姓名:%s\n",data.key);
54 printf("地址:%s\n",data.addr);
55 printf("电话:%s\n",data.telephone);
56 printf("手机:%s\n",data.mobile);
57 }
58 }
【程序说明】
以上代码第48行让用户输入查找联系人的姓名，第49行调用ChainListFind函数查找该联系人的姓名，若找到该联系人，则显示该联系人的信息。
5．编写删除联系人模块
删除联系人的过程就是删除链表中节点的过程。当在主函数中选择“删除联系人”时，将调用以下函数，让用户输入联系人姓名进行删除，具体代码如下：
59 void delete(ChainListType *head) //删除联系人
60 {
61 ChainListType *h=head;
62 char name[15];
63 printf("请输入要删除的姓名:");
64 scanf("%s",name);
65 ChainListDelete(head,name);
66 }
【程序说明】
以上代码第64行接收用户输入的联系人姓名，第65行调用ChainListDelete函数删除该联系人的信息。
6．编写主模块
将各子模块代码编写完成后，接着编写主模块main函数。在main函数中，主要用来显示菜单供用户进行选择，具体代码如下：
67 int main()
68 {
69 ChainListType *head=NULL;
70 int select; //选择菜单的序号
71 do{
72 printf("\n_____________________\n");
73 printf("1.添加联系人\n");
74 printf("2.查找联系人\n");
75 printf("3.删除联系人\n");
76 printf("4.显示所有联系人\n");
77 printf("0.退出\n");
78 printf("_____________________\n");
79 select=getch(); //把程序暂停下来，等待用户的输入
80 switch(select)
81 {
82 case '1':
83 printf("\n添加联系人\n");
84 head=input(head);
85 break;
86 case '2':
87 printf("\n查找联系人\n");
88 find(head);
89 break;
90 case '3':
91 printf("\n删除联系人\n");
92 delete(head);
93 break;
94 case '4':
95 printf("\n显示联系人\n");
96 ChainListAll(head);
97 break;
98 case '0':
99 return 0;
100 }
101 }while(select != '0');
102 }
【程序说明】
·以上代码中，第69行定义一个链表头指针，首先初始化为NULL。
·第71~101行为一个循环，用来显示菜单，并根据用户选择的菜单调用相应的函数进行处理。第72~78行显示系统菜单，第79行接收用户选择的菜单序号，第80~100行根据用户选择的菜单分别调用不同的子模块。
由于本书篇幅所限，这里不列出程序的运行效果，读者可上机运行。
提示 作为实际应用的程序，应该将数据保存到磁盘文件中，供用户随时使用。有关文件操作方面的代码，读者可在本程序的基础上进行扩展。