1.结构体中含有可以指向本结构体的指针成员
前面已知结构体中的成员可以是各种类型的指针变量。当一个结构体中有一个或多个成员的基类型就是本结构体类型时，称这种结构体为可以“引用自身的结构体”。例如：
在这里，next是一个可以指向struct node类型变量的指针成员。因此，a.next=&a是合法的表达式，由此构成的存储结构如图7-4所示。
图7-4 引用自身的结构体
2.链表的概念
通过前面的学习我们了解到，数组属于静态数据结构（数据组织形式），在编译时，一次性地分配所申请的存储空间。而实际使用的存储空间经常小于所申请的空间，因此静态数据结构存在空间浪费现象；而且数组元素在内存中是连续存放的，当插入或删除一个数据元素时，需要移动大量其他元素。链表这种动态数据结构就没有这些缺点。
C语言中可利用指针来建立动态数据结构。即数据元素在内存中不需要连续存放，而是通过指针将各元素链接起来，就像一条“链子”一样，称之为链表。
例7-4 一个简单的链表示例。
此程序中所定义的结构体类型NODETYPE共有两个成员：成员data是整型；成员next是指针类型，其基类型为NODETYPE类型。
main函数中定义的变量a、b、c都是结构体变量，它们都含有data和next两个成员；变量head、p是指向NODETYPE结构体类型的指针变量，它们与结构体变量a、b、c中的成员变量next类型相同。
运行程序中的赋值语句后，形成如图7-5所示的存储结构。这样就把同一类型的结构体变量a、b、c“链接”到一起，形成了链表，结构体变量a、b、c，称为链表的结点。
图7-5 链表存储结构示意图
在此例中，链接到一起的每个结点都是通过定义，由系统在内存中开辟了固定，但不一定连续的存储单元，在程序执行过程中，不可能人为地再产生新的存储单元，也不可能人为地使已经开辟的存储单元消失。从这一角度出发，可称这种链表为“静态链表”。但是在实际中，广泛使用的是另一种“动态链表”。
程序运行的结果如图7-6所示。
图7-6 程序运行结果
3.动态链表的概念
每次为一个结构动态分配的内存空间称之为一个结点。链表中的结点包含数据域和指针域两个部分。数据域可以存放任何类型的数据，指针域用于存放指向下一个结点的地址，以便通过这些指针把各个结点连接起来，形成链表。由于链表中的每个存储单元都由动态分配获得，故称这样的链表为“动态链表”，简称链表。
在链表中，根据每个结点中指针域的个数，分为单向链表和双向链表。本书主要介绍单向链表，简称单链表。
在单链表中，一般设置头指针（head），用于指向链表中的第一个结点。有时为了简化操作，在第一个结点之前附加一个结点，称为头结点。
例如：
这里的next是成员名，它是指针类型的，指向struct student类型数据。
例如：用链表结构组织学生数据的存储。如图7-7所示。
图7-7 链表结构示意图
在此链表的示意图中，每个结点都分为两个域，一个是数据域，存放各种实际的数据，如学号num，姓名name，性别sex和成绩score等。另一个是指针域，存放下一个结点的首地址。其中第0个结点称为头结点，它存放有第一个结点的首地址，它没有数据，只是一个指针变量。最后一个结点因没有后续结点，它的数据域存放最后一个学生的实际数据，而指针域置成‘\0’（NULL）值，在图中用“^”表示。
4.创建动态链表所需的函数
前面讲过，链表结构可进行动态地分配存储空间，即在需要时才开辟一个结点的存储单元，不需要时，就释放这个存储单元。
ANSI C标准为动态分配系统定义了malloc、calloc、free和realloc四个库函数。使用它们时，必须在程序开头包含头文件stdlib.h。
（1）malloc函数。
函数原型：
功能：在内存的动态存储区申请分配大小为size字节的连续空间，并将该区域的起始地址作为函数值返回。malloc（）函数的返回值为指向void类型的指针。
其中“void*”是一种指针类型，可用于说明一个指针变量，但不指定它指向哪一种类型数据。当把void类型的指针值赋给其他类型的指针变量时，应进行强制类型转换。例如：
用malloc（8）申请一个长度为8字节的内存空间，一个指向long型的指针变量p，指向这段空间的首地址。
当内存没有足够大的空间进行分配时，malloc函数值为NULL“空指针”，即地址为0，所以程序中的malloc函数，在调用后应检查其返回值是否为空指针。
（2）calloc函数。
函数原型：
功能：在内存的动态存储区申请分配num个大小为size字节的连续空间，函数返回值为该空间的首地址。如果分配不成功，返回NULL。例如：
用“calloc（5，10）；”可申请5个大小为10字节的空间，即总长为50字节。
（3）free函数。
函数原型：
功能：把以前分配的由p指向的存储空间释放，归还给系统。该函数返回值为空。p是最近一次由malloc函数和calloc函数返回的地址。例如：
用“free（p）；”可把前面已申请的指向long型的指针变量p所指的8个字节的空间释放。
（4）realloc函数。
函数原型：
功能：将p所指存储空间的大小改为size个字节，即扩大或缩小原来的存储空间。如果分配不成功，则返回NULL。例如：
用“realloc（p，100）；”可将p指向的已分配的动态空间修改为100字节。
5.链表的操作(www.xing528.com)
对链表的主要操作有建立链表、结构的查找与输出、结点数据的删除和结点数据的插入等。假设链表结点的类型定义如下：
（1）动态链表的建立。
动态链表的创建有两种方式。
●先进先出单链表。在建立单链表时，将每次生成的新结点总是插入到当前链表的表尾作为尾结点。
●后进先出单链表。在建立单链表时，将每次生成的新结点总是插入到当前链表的表头结点之后作为当前链表的首结点。
这两种方法大同小异，主要区别在于对插入结点的前一结点跟踪及对应指针域的处理。在建立链表时，一般选择先进先出单链表的创建方式。
具体创建步骤：
第一步，创建空表，定义头结点指针域为空。
第二步，准备建表，定义两个指针p和q，约定p恒指向链表末尾结点，q恒指向待插入结点。
第三步，申请新结点，作为待插入结点。
第四步，插入新结点，将新结点插入到链表的末尾，作为当前末尾结点。
第五步，只要待插入结点个数小于链表中预定结点个数，则转到第三步继续插入。
例7-5 编写函数creact_slist，建立带头结点的单向链表。结点数据域中的数据从键盘输入。以-1作为输入的结束标志。链表的头结点的地址由函数返回。
参考函数：
调用链表建立函数时，若一开始就输入-1，控制流程不会进入while循环，而直接执行循环之后的p->next='\0'；语句，这时建立一个空链表。
由此可见，判断此链表是否为空链表，可用条件：p->next=='\0'。
（2）顺序访问单链表中各结点的数据域（查找与输出）。
利用一个工作指针p，从头到尾依次指向链表中的每一个结点；当指针指向某一个结点时，就输出该结点数据域中的内容，直到遇到链表的结束标志为止。如果是空链表，就只输出有关信息并返回调用函数。
链表的输出过程有以下几步：
第一步，确定表头，并约定指针p恒指向待输出结点。
第二步，若待输出结点非空，则输出结点数据域的值；若为空，则退出。
第三步，跟踪链表地址域，找到下一个待输出结点。
第四步，转到第二步，继续输出。
例如：
下面的程序段是利用前面的SLIST结构类型构成的链表，输出每个结点数据域中的值。
（3）单链表的删除。
为了删除单向链表中的某个结点，首先要找到待删除结点的前趋结点，然后将此前趋结点的指针域去指向待删除结点的后续结点（p->next=q->next），最后释放被删除结点所占存储空间（free（q））即可。
例如：
则将q所指结点从链表中删除，同时要保持链表的连续，即q->next中存放的是r所指结点的首地址，如果将r所指结点的首地址存于p->next中，就可以删除q所指结点，并保持链表的连续（即p所指结点与r所指结点相连）。
在有n个结点的单链表中，删除第i个结点的操作如图7-8所示。
图7-8 删除单链表的第i个结点示意图
在图7-8中：
①指针P指向待删第i个结点的前1个结点（第i-1个结点）。
②指针q指向待删的第i个结点（q=p->next）。
③切断第i个结点与其前后两个结点的链接（p->next=q->next）并释放第i个结点所占的内存空间（free（q））。
（4）单链表的插入。
在单向链表中插入结点，首先要确定插入的位置。当待插结点插在指针p所指结点之前称为前插；待插结点插在指针p所指结点之后称为后插。
当进行前插操作时，需要三个工作指针p、q、s，通常用s指向新开辟的结点；用p指向插入的位置；q指向p的前趋结点，在第i个结点进行前插操作，如图7-9所示。
图7-9 在单链表的第i个位置插入结点示意图
在图7-9中：
①表示将新结点的指针指向第i个结点（s.next=p）。
②表示将第i-1个结点的指针指向新结点（q.next=s）。
例7-6 编写函数insert_snode，其功能是：在带头结点单链表中的值为x的结点前，插入值为y的结点，若值为x的结点不存在，则插在链表尾。
参考函数：
函数insert_snode中，综合运用了查找和前插的算法。在进行插入操作的过程中，可能遇到以下3种情况。
①链表非空，值为x的结点存在，新结点应插在x结点之前。
②链表非空，但值为x的结点不存在，按要求新结点应插在链表尾。
③链表为空，这种情况相当x的结点不存在，新结点应插在链表尾，即插在头结点之后，作为链表的第一个结点。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
