C语言程序设计(第7章结构体与共用体)4

7.4链表
数组的建立、插入和删除，作为存储相似数据的集合，给我们编程带来了很多方便，增加了灵活性。但是数组也有一些缺点。例如，数组的大小应该预先定义，并且不能在程序中调整。因此，在程序设计中，针对不同的问题，很难统一3 0数组和5 0数组的大小。我们只能根据可能的需求来定义数组，这往往会导致存储的浪费空。
我们希望构造一个动态数组，可以随时调整数组的大小，满足不同问题的需要。链表就是我们需要的动态数组。它适用于程序执行过程中有数据存储时系统进行存储空，绝不会构成存储区域的浪费。
链表是一种复杂的数据结构。其数据之间的关系使得链表分为单链表、循环链表、双链表三种，下面将一一介绍。
7.4.1单链表
单链表有一个头节点，指向链表在内存中的第一个地址。链表中每个节点的数据类型都是结构类型，节点有两个成员:整数成员(实际要保存的数据)和指向下一个结构类型节点的指针，也就是下一个节点的地址(其实这个单链表就是一个存储整数数据的动态数组)。按照这种结构，对链表中每个节点的访问都需要从链表的头开始，后续节点的地址由当前节点给出。无论访问表中的哪个节点，都需要从链表的头开始，按顺序向后搜索。链表的尾节点没有后续节点，其指针字段为空，写为NULL。
图7-3也展示了这样一层意思。链表中每个节点在内存中的存储地址不是连续的，每个节点的地址都是在需要的时候向系统申请分配的。系统可以根据存储器的当前情况连续或跳跃式地分配地址。
看看链表节点的数据结构定义:
struct node
{
intnum；
结构节点* p；
}；
在链表节点的定义中，除了整数成员之外，成员p是与节点完全相同类型的指针。在链表节点的数据结构中，很特别的一点是结构中指针字段的数据类型使用了未定义的成功数据类型。这是一种可以先使用，再在c中定义的数据结构。
& # 8226；创建单链表的过程包括以下步骤:
1)定义链表的数据结构。
2)创建空表。
3)使用malloc()函数向系统申请分配一个节点。

4)将新节点的指针成员赋给空。如果是空表，将新节点连接到表头；如果不是空表，将新的
节点连接到表的末尾。
5)判断是否有后续节点访问链表，如果有，则转到3)，否则结束。
& # 8226；单链表的输出过程包括以下步骤
1)查找表头。
2)如果不是空表，则输出节点的值成员，如果是空表，则退出。
3)跟踪链表的增长，即找到下一个节点的地址。
4)转到2)。

【例7-5】创建一个存储正整数的单链表(输入-9 9 9作为结束符号)并打印出来。
#include /*头文件包含malloc()*/
# include
struct node/*链表节点的结构*/
{
int num；
struct node * next；
}；
main()
{
struct node * creat()；/*函数声明*/
void print()；
结构节点*头；/*定义头指针*/
head = NULL；/*构建一个空表*/
head = creat(head)；/*创建单链表*/
print(head)；/*打印单链表*/
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
P1 = p2 =(struct node *)malloc(sizeof(struct node))；/*申请新节点*/
scanf("%d "，& P1-> num)；/*输入节点的值*/
P1-> next = NULL；/*将新节点的指针设置为空*/
while(P1-> num > 0)/*输入节点的值大于0 */
{
if(head = = null)head = P1；/* 空表，访问头*/
else p2-> next = P1；/* Not 空表，连接到表的末尾*/
p2 = P1；
p1=(结构节点*)malloc(sizeof(结构节点))；/*申请下一个新节点*/
scanf("%d "，& P1-> num)；/*输入节点的值*/
}
返回头；/*返回链表的头指针*/
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
temp = head；/*获取链表的头指针*/
while (temp！=NULL)/*只要是非空表*/
{
printf ("%6d "，temp-> num)；/*输出链表节点的值*/