链表的成立、插入和删除
副标题#e#
数组作为存放同类数据的荟萃，给我们在措施设计时带来许多的利便，增加了机动性。但数组也同样存在一些弊病。如数组的巨细在界说时要事先划定，不能在措施中举办调解，这样一来，在措施设计中针对差异问题有时需要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 <stdlib.h> /包*含ma l l o c ( ) 的头文件*/
#include <stdio.h>
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;/*跟踪链表增长*/
}
}
在链表的建设进程中，链表的头指针长短常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表建设乐成后，要返回一个链表头节点的地点，即头指针。
#p#副标题#e#
#p#分页标题#e#
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=NULL; /*做空表* /
head=creat (head); / *挪用函数建设以head 为头的链表* /
p r i n t ( h e a d ) ；/ *挪用函数输出节点* /
printf("\n input inserted num,name:\n");
gets(str); /*输入学号* /
n=atoi (str);
gets(str); /*输入姓名* /
head=insert (head, str, n); 将/*节点插入链表*/
print (head)； / *挪用函数输出节点*/
printf("\n input deleted name:\n");
gets(str); /*输入被删姓名* /
head=delet(head,str); /调*用函数删除节点*/
print (head); /*挪用函数输出节点* /
r e t u r n ;
}
/ * * * * * * * * * * * * * * * * * * * * * * /
/ * * * 建设链表* * * * * * * * * * * * /
struct node *creat(struct node *head)
{
char temp[30];
struct node *pl,*p2;
pl=p2=(struct node*) malloc(sizeof(struct node));
printf ("input num, name: \n;")
printf("exit:double times Enter!\n");
g e t s ( t e m p ) ;
gets (p1->str);
pl->num=atoi (temp);
p l – > n e x t = N U L L ;
while (strlen (pl->str)>0
{
if (head==NULL) head=pl；
else p2->next=p1;
P 2 = p l ；
pl=(struct node *)malloc(sizeof(struct node));
printf ("input num, name: \n");
printf("exit:double times Enter!\n");
g e t s ( t e m p ) ;
gets(pl ->str);
p1->num=atoi (temp);
P 1 – > n e x t = N U L L ;
}
return head;
}
/ * * * * * * * * * * * * * * * * * * * * /
/ * * * * * * * * * * 插入节点* * * * * * * * * * /
struct node *insert (head, pstr,n);
struct node *head;
char *pstr;
int n;
{
struct node *pl,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));
strcpy (p1->str, pstr);
p 1 – > n u m = n ;
p 2 = h e a d ;
i f ( h e a d = = N U L L )
{
h e a d = p l ; p l – > n e x t = N U L L ;
}
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 l ;
p l – > n e x t = p 2 ;
}
else
{
p 3 – > n e x t = p l ;
p l – > n e x t = p 2 ;
}
else
{
p 2 – > n e x t = p l ;
p l – > n e x t = N U L L ;
}
}
r e t u r n ( h e a d ) ;
}
/ * * * * * * * * * * * * * * * * * * * * * * * * * /
/ * * * * * 删除节点* * * * * * * * * * * * * /
struct node *delet (head, pstr)
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)!=O&&temp->next!=NULL)
{
p = t e m p ;
t e m p = t e m p – > n e x t ,
}
i f ( s t r c m p ( t e m p – > s t r , p s t r ) = = 0 )
{
if (temp== head)
{
h e a d = h e a d – > n e x t ;
f r e e ( t e m p ) ;
}
else
{
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");
}
return(head);
}
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
/ * * * * * * * * * * 链表各节点的输出* * * * * * * * * * /
void print (struct node *head)
{
struct node *temp;
t e m p = h e a d ;
printf("\n output strings:\n");
while (temp!=NULL)
{
p r i n t f ( " \ n % d – – – – % s \ n " , t e m p – > n u m ，t e m p – > s t r ) ；
t e m p = t e m p – > n e x t ；
}
r e t u r n ;
}
