链表专题复习
数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个元素大小的数组，有时需要5 0个数组元素的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。
我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。
链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面只介绍单向链表。 7.4.1 单链表
图7 - 3是单链表的结构。
单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。
图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。 看一下链表节点的数据结构定义： struct node {
int num;
struct node *p; } ;
在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。
在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。
? 单链表的创建过程有以下几步： 1 ) 定义链表的数据结构。 2 ) 创建一个空表。
3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。
1
4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新
节点接到表尾。
5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束。 ? 单链表的输出过程有以下几步 1) 找到表头。
2) 若是非空表，输出节点的值成员，是空表则退出。 3 ) 跟踪链表的增长，即找到下一个节点的地址。 4) 转到2 )。
下列是用尾插法创建链表 新开辟的节点总是插在表末 [例7-5] 创建一个存放正整数（输入负数时做结束标志）的单链表，并打印输出。 #include
struct node /*链表节点的结构* / {
int num;
struct node *next; } ; m a i n ( ) {
struct node *creat(); / *函数声明* / void print();
struct node *head; / * 定义头指针* / head=NULL;/*建一个空表*/
head=creat(head);/*创建单链表*/ print(head);/*打印单链表*/ }
/******************************************/
struct node*creat(structnode*head)函/数*返回的是与节点相同类型的指针*/ {
struct node*p1,*p2;
p1=p2=(structnode*)malloc(sizeof(structnode));申请/*新节点*/ scanf(\输入节点的值*/ p1->next=NULL;/*将新节点的指针置为空*/ while(p1->num>0)/*输入节点的数值大于0*/ {
if(head==NULL)head=p1;/*空表，接入表头*/ elsep2->next=p1;/*非空表，接到表尾*/ p2=p1;
p1=(structnode*)malloc(sizeof(structnode));申/请*下一个新节点*/ scanf(\输入节点的值*/ }
return head;/*返回链表的头指针*/ }
/*******************************************/
void print(struct node*head)输/*出以head为头的链表各节点的值*/
2
{
struct node *temp;
temp=head;/*取得链表的头指针*/ while(temp!=NULL)/*只要是非空表*/ {
printf(\输出链表节点的值*/ temp=temp->next;/*跟踪链表增长*/ } }
在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。
下列是用头插法创建链表
新开辟的结点总是作为表头结点 程序清单位：
#include
struct node *next; };
struct node *creat(struct node *head)
{ struct node *top; /*top为新开辟的结点*/ top=(struct node *)malloc(sizeof(struct node)); scanf(“%d”,&top->num); while(top->num>=0) ｛
top->next=head; /*原来的第一个结点接在新开辟的结点后面*/
3