链表的建立、插入和删除（一）

数组作为存储相似数据的集合，在编程上给我们带来了很多方便和灵活性。但是数组也有一些缺点。比如数组的大小要在定义的时候预先指定，在程序中是无法调整的。因此，在程序设计中，对于不同的问题，有时需要3 0个数组，有时需要5 0个数组。
很难统一。我们只能根据可能的需求来定义数组，这往往会导致存储的浪费空。
我们希望构造一个动态数组，可以随时调整数组的大小，满足不同问题的需要。链表就是我们需要的动态数组。它适用于程序执行过程中有数据存储时系统进行存储空，绝不会构成存储区域的浪费。
链表是一种复杂的数据结构。其数据之间的关系使得链表分为单链表、循环链表、双链表三种，下面将一一介绍。
7.4.1单链表
图7-3是单链表的结构。

单个链表有一个h e a d节点H E A D，指向内存中链表的第一个地址。链表中每个节点的数据类型都是结构类型，节点有两个成员:整数成员(实际要保存的数据)和指向下一个结构类型节点的指针，也就是下一个节点的地址(其实这个单链表就是一个存储整数数据的动态数组)。按照这种结构，对链表中每个节点的访问都需要从链表的头开始，后续节点的地址由当前节点给出。无论访问表中的哪个节点，都需要从链表的头开始，按顺序向后搜索。链表的尾节点没有后续节点，它的指针字段是空，写成N U L L
图7-3也说明了这样一层意思。链表中每个节点在内存中的存储地址不是连续的，每个节点的地址都是在需要的时候向系统申请分配的。系统可以根据存储器的当前情况连续或跳跃式地分配地址。
看一下链表节点的数据结构定义:
struct node
{
intnum；
结构节点* p；
}；
在链表节点的定义中，除了整数成员之外，成员p是与节点完全相同类型的指针。
在链表节点的数据结构中，很特别的一点是，结构中指针字段的数据类型使用了未定义的数据类型。这是一种可以先使用，再在c中定义的数据结构。
& # 8226；创建单链表的过程包括以下步骤:
1)定义链表的数据结构。
2)创建空表。
3)使用m a l o c()函数向系统申请分配一个节点。
4)将新节点的指针成员赋给空。如果是空表，将新节点连接到表头；如果不是空表，将新的
节点连接到表的末尾。
5)判断是否有后续节点访问链表，如果有，则转到3)，否则结束。
& # 8226；单链表的输出过程包括以下步骤
1)查找表头。
2)如果不是空表，则输出节点的值成员，如果是空表，则退出。
3)跟踪链表的增长，即找到下一个节点的地址。
4)转到2)。
[例7-5]创建一个存储正整数的单链表(输入-9 9 9作为结束标记)并打印出来。
#include/package *头文件包含ma l l o c()*/
# include
struct node/*链表节点的结构*/
{
int num；
struct node * next；
}；
m a I n()
{
struct node * creat()；/*函数声明*/
void print()；
结构节点*头；/*定义头指针*/
head = NULL；/*构建一个空表*/
head = creat(head)；/*创建单链表*/
print(head)；/*打印单链表*/
}