建立动态链表是指在程序执行过程中，一个一个地开辟结点并输入各结点的数据，从无到有地建立起前后相链的关系，形成一个链表。

C语言利用malloc （）和free （）这两个函数以及sizeof运算符可动态分配和释放内存空间。malloc （）和free （）这两个函数所需的信息在头文件“stdlib.h”中。

例10.8 建立一个如图10-2所示的动态链表并输出，它由3个学生数据的结点组成。每个学生的数据包括学生学号、姓名和成绩。

解题思路：

（1）定义3个指针变量：head， pn和pt，它们都指向struct student结构体类型。head是链表的头指针，指向链表的第一个结点，pn指向新开辟的结点。pt指向当前链表的最后一个结点。

（2）建立第一个结点a，如图10-3所示。用pn指向用malloc （）函数申请的新空间，然后让头指针head也指向它，并输入第一个学生的数据，它就是链表的第一个结点。该结点也是当前链表的最后一个结点pt，所以该结点中用于存储下一个结点地址的指针成员为NULL。

（3）链入其他结点，如图10-4所示。用pn指向malloc （）函数申请的新空间，输入这个学生结点的数据，执行“pt-＞next = pn ； ”，可将该结点链入到链表上。通过执行“pt=pn；”，则pt指向结点b。此时，链表的最后一个结点为结点b。

图10-3　建立第一个结点a

图10-4　建立第二个结点b

（4）重复第（3）步，将结点c链入到链表上。

建立动态链表的流程图，如图10-5所示。

(www.daowen.com)

图10-5　建立动态链表的流程图

编写程序：

创建一个名为“eg10_8.c”的新文件，在编辑窗口中输入下面的程序代码。

运行结果：

程序说明：

creat（）函数用于建立一个有n个结点的链表，其返回值为指向链表中结点类型的指针，将链表的头指针head返回。使用for循环链入其他结点，直到最后一个结点。

在for循环中，用pn指向用malloc （）函数申请的新空间并输入这个结点的数据，其next成员的值赋为NULL作为当前的最后结点；执行“pt-＞next = pn；”将新结点链到链表上；执行“pt = pn；”调整链表尾指针pt重新指向链表的最后一个结点pn，准备下一次循环。

creat（）函数的形参n，表示新建链表的结点数，作为for语句的循环次数。

print（）函数用于输出链表。头指针head从实参接收链表的第一个结点的起始地址，把它赋给p，于是p指向第一个结点。若p不为空，输出第一个结点的数据。然后执行“p=p-＞next ； ”，使得p指向下一个结点。如果下一个结点不为空，则输出这个结点的数据。同理，依次输出其他结点的数据。若p指向的下一个结点为空，则退出print（）函数。

链表是一个比较深入的内容，对初学者来说有一定的难度。计算机专业人员应该掌握，非计算机专业人员对此仅作一定的了解即可。