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

 来源：

数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要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 ( )函数向系统申请分配一个节点。
4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新
节点接到表尾。
5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束。
• 单链表的输出过程有以下几步
1) 找到表头。
2) 若是非空表，输出节点的值成员，是空表则退出。
3 ) 跟踪链表的增长，即找到下一个节点的地址。
4) 转到2 )。
[例7-5] 创建一个存放正整数（输入- 9 9 9做结束标志）的单链表，并打印输出。
#include /包*含ma l l o c ( ) 的头文件*/
#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("%d",&p1->num);/*输入节点的值*/
p1->next=NULL;/*将新节点的指针置为空*/
while(p1->num>0)/*输入节点的数值大于0*/
{
if(head==NULL)head=p1;/*空表，接入表头*/
elsep2->next=p1;/*非空表，接到表尾*/
p2=p1;
p1=(structnode*)malloc(sizeof(structnode));申/请*下一个新节点*/
scanf("%d",&p1->num);/*输入节点的值*/
}
return head;/*返回链表的头指针*/
}
/*******************************************/
void print(struct node*head)输/*出以head为头的链表各节点的值*/
{
struct node *temp;
temp=head;/*取得链表的头指针*/
while(temp!=NULL)/*只要是非空表*/
{
printf("%6d",temp->num);/*输出链表节点的值*/
temp=temp->next;/*跟踪链表增长*/
}
}
在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。

7.4.2 单链表的插入与删除
在链表这种特殊的数据结构中，链表的长短需要根据具体情况来设定，当需要保存数据时向系统申请存储空间，并将数据接入链表中。对链表而言，表中的数据可以依此接到表尾或连结到表头，也可以视情况插入表中；对不再需要的数据，将其从表中删除并释放其所占空间，但不能破坏链表的结构。这就是下面将介绍的链表的插入与删除。
1. 链表的删除
在链表中删除一个节点，用图7 - 4描述如下：
[例7-6] 创建一个学生学号及姓名的单链表，即节点包括学生学号、姓名及指向下一个节点的指针，链表按学生的学号排列。再从键盘输入某一学生姓名，将其从链表中删除。
首先定义链表的结构：
struct
从图7 - 4中看到，从链表中删除一个节点有三种情况，即删除链表头节点、删除链表的中
间节点、删除链表的尾节点。题目给出的是学生姓名，则应在链表中从头到尾依此各节
点，并与各节点的学生姓名比较，若相同，则成功，否则，找不到节点。由于删除的节
点可能在链表的头，会对链表的头指针造成丢失，所以定义删除节点的函数的返回值定义为
返回结构体类型的指针。
struct node *delet(head,pstr)以/*he a d 为头指针，删除ps t r 所在节点*/
struct node *head;
char *pstr;
{
struct node *temp,*p;
t e m p = h e a d ; / * 链表的头指针* /
if (head==NULL) / *链表为空* /
printf("\nList is null!\n");
else /*非空表* /
{
t e m p = h e a d ;
while (strcmp(temp->str,pstr)!=0&&temp->next!=NULL)
/ * 若节点的字符串与输入字符串不同，并且未到链表尾* /
{
p = t e m p ;
t e m p = t e m p - > n e x t ; / * 跟踪链表的增长，即指针后移* /
}
if(strcmp(temp->str,pstr)==0 ) / *找到字符串* /
{
if(temp==head) { / * 表头节点* /
printf("delete string :%s\n",temp->str);
h e a d = h e a d - > n e x t ;
f r e e ( t e m p ) ; / *释放被删节点* /
}
e l s e
{
p->next=temp->next; /表*中节点*/
printf("delete string :%s\n",temp->str);
f r e e ( t e m p ) ;
}
}
else printf("\nno find string!\n");没/找* 到要删除的字符串*/
}
r e t u r n ( h e a d ) ; / *返回表头指针* /
}
2. 链表的插入
首先定义链表的结构：
struct
{
int num; /*学生学号* /
char str[20]; /*姓名* /
struct node *next;
} ;
在建立的单链表中，插入节点有三种情况，如图7 - 5所示。

插入的节点可以在表头、表中或表尾。假定我们按照以学号为顺序建立链表，则插入的节点依次与表中节点相比较，找到插入位置。由于插入的节点可能在链表的头，会对链表的头指针造成修改，所以定义插入节点的函数的返回值定义为返回结构体类型的指针。节点的
插入函数如下：
struct node *insert(head,pstr,n) / *插入学号为n、姓名为p s t r 的节点* /
struct node *head; / *链表的头指针* /
char *pstr;
int n;
{
struct node *p1,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node))分;配/*一个新节点*/
s t r c p y ( p 1 - > s t r , p s t r ) ; / * 写入节点的姓名字串* /
p 1 - > n u m = n ; / * 学号* /
p 2 = h e a d ;
if (head==NULL) / * 空表* /
{
head=p1; p1->next=NULL;/ *新节点插入表头* /
}
e l s e
{ /*非空表* /
while(n>p2->num&&p2->next!=NULL)
/ *输入的学号小于节点的学号，并且未到表尾* /
{
p 3 = p 2 ;
p 2 = p 2 - > n e x t ; / * 跟踪链表增长* /
}
if (n<=p2->num) / *找到插入位置* /
if (head==p2) / * 插入位置在表头* /
{
h e a d = p 1 ;
p 1 - > n e x t = p 2 ;
}
e l s e
{ /*插入位置在表中* /
p 3 - > n e x t = p 1 ;
p 1 - > n e x t = p 2 ;
}
e l s e
{ /*插入位置在表尾* /
p 2 - > n e x t = p 1 ;
p 1 - > n e x t = N U L L ;
}
}
r e t u r n ( h e a d ) ; / * 返回链表的头指针* /
}
3. 实例[例7 - 7 ]
创建包含学号、姓名节点的单链表。其节点数任意个，表以学号为序，低学号的在前，高学号的在后，以输入姓名为空作结束。在此链表中，要求删除一个给定姓名的节点，并插入一个给定学号和姓名的节点。
# include "stdlib.h"
# include "malloc. h"
struct node /*节点的数据结构* /
{
int num;
char str[20];
struct node *next;
} ;
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
main( )
{
/ *函数声明* /
struct node *creat();
struct node *insert();
struct node *delet();
void print( );
struct node *head;
char str[20];
int n;
head