7.2　链式表

单链表是一种简单的链表，也叫做线性链表。用它来表示线性表时，用指针表示结点间的逻辑关系。因此单链表的一个存储结点包含两部分内容，如图7-2所示。

图7-2　单链表结点

data部分称为数据域，用于存储线性表的一个数据元素;next部分称为指针域，用于存放一个指针，该指针指向该链表下一个结点的开始存储地址，如图7-3所示。

图7-3　单链表

单链表的结点的地址通过前驱结点的next域找到，链表的最后一个结点没有后继，则在next域放一个空指针NULL，图中用“∧”表示。

线性表中的数据元素的顺序与其链表表示中的物理顺序可能不一致，一般通过单链表的指针将各个数据元素按照线性表的逻辑顺序链接起来。

7.2.1　内存动态分配

C语言的函数malloc()可以在每一次调用时，在内存中开辟一块存储空间，使用格式如下所示:

void*malloc(int size);

参数size表示所需的内存空间大小，单位是字节。如果分配size大小的存储空间，函数将返回第一个字节的指针。因为函数返回类型是void*，所以需要转换为符合分配要求的数据类型，用法如下:

p=(数据类型*)malloc(sizeof(数据类型));

需要注意的是，如果内存空间不足，函数malloc()将因为分配空间失败，返回一个空指针，所以在调用该函数后，检测返回指针是否为空。

例如:

函数malloc()向系统要求的内存空间，需要在使用完后调用free()函数释放给系统，格式如下:

7.2.2　链表结点的创建

链表是一种动态的数据结构，在程序中需要使用malloc()和free()函数创建链表结点。为了有效地存储结点数据，并且实现链表的链式功能，我们建立linknode结构体，代码如下:

运行上面的结构的声明后，linknode就成为一个动态指针结构。建立了结点的结构后，接下来定义一个结构体指针变量，该指针变量使用前必须分配存储空间，然后以用户键入值初始化结点数据，同时初始化该结点指向的下一个结点为空。

现在我们就可以输入数据结点了，如下所示:

按照上面的方法，可以循环依次建立多个结点，每个结点的next指针指向下一个结点，从而构成链式表结构。

如何创建链表呢?函数CreatLinkNode实现了创建链表，首先分配头结点内存空间并创建结点内容，再循环创建4个结点，每次创建完结点需要检查内存空间是否分配成功。函数PrintNode遍历链表并输出结点数据。代码如下:

函数PrintNode的参数ptr是指向链表的头结点的指针。

7.2.3　链表结点的遍历

链表的遍历和数组的遍历非常相似，数组是使用下标，而链表是通过指针处理每一个结点的遍历。不同的是，数组可以随机的访问元素，而链表结构一定要用遍历的方式访问其结点，所以如果要访问第n个结点的内容，就一定需要遍历到第n－1个结点才能够知道结果在哪里。

代码如下:

函数FindNode的参数head是指向链表的头结点的指针，参数num是待查找的结点数据。

7.2.4　链表结点的插入

链表插入结点，因为结点的位置不同，有三种情况。

(1)将结点插在链表第一个结点之前，只要将新创建的结点的指针指向链表的第一个结点，接着新结点指针便成为此链表的开始，如图7-4所示。

图7-4　链表结点插入情况1

(2)将结点插在链表的最后一个结点的后面，只需将原来链表最后一个结点指针指向新创建的结点，然后将新结点的指针指向NULL，如图7-5所示。

图7-5　链表结点插入情况2

(3)将结点插在链表的中间位置，如果结点是插在p和q结点之间，而且p是q的前一个结点，此时插入的情况如图7-6所示。

图7-6　链表结点插入情况3

链表插入结点代码如下:

函数InsertNode的参数head是指向链表的头结点的指针，参数p指向待插入结点的前驱，参数vlaue是待插入的结点数据。

7.2.5　链表结点的删除

在链表内删除结点时，有以下3种不同的情况。

(1)删除链表的第一个结点，只需要将链表指针指向下一个结点，如图7-7所示。

图7-7　链表结点删除情况1

(2)删除链表的最后一个结点，只需要将最后一个结点的前驱结点的指针域指向NULL，如图7-8所示。

图7-8　链表结点删除情况2

(3)删除链表中间结点，只需将要删除结点的前驱结点的指针域指向要删除结点的下一个结点，如图7-9所示。

图7-9　链表结点删除情况3

从动态内存的操作理论来说，应该在删除第一个结点后，立即将删除的结点内存释放给系统，如果p是指向删除结点的指针，那么释放命令如下:

free(p);

如果是整个链表结构，除了使用上述命令，还需要借助于链表的遍历方法。

链表结点删除代码如下:

函数DeleteNode的参数head是指向链表的头结点的指针，参数p是待删除结点的指针。

释放整个链表代码如下:

7.2.6　链表结点的反转

基本链表结构是一种具有方向性的数据结构。从头至尾的输出链表结点很简单，因为每一个结点都知道下一个结点的位置，但是对前一个结点就毫无头绪了，那么想把链表从尾至头反向输出该怎么办呢?如图7-10～图7-13所示。

图7-10　链表结点的反转第一步

图7-11　链表结点的反转第二步

图7-12　链表结点的反转第三步

图7-13　链表结点的反转第四步

链表结点反转代码如下:

函数InvertNode的参数head是指向链表的头结点的指针。