链表的建立、插入和删除

时间:2010-05-04 19:24:32  来源:第二电脑网  作者:第二电脑网

  第二电脑网导读:,难于统一。我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费。我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间,决不构成对存储区的浪费。链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表、循环链表...
  正文:

数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要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;/*跟踪链表增长*/
}
}
在链表的创建过程中,链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始,所以链表创建成功后,要返回一个链表头节点的地址,即头指针。

7.4.2 单链表的插入与删除
在链表这种特殊的数据结构中,链表的长短需要根据具体情况来设定,当需要保存数据时向系统申请存储空间,并将数据接入链表中。对链表而言,表中的数据可以依此接到表尾或连结到表头,也可以视情况插入表中;对不再需要的数据,将其从表中删除并释放其所占空间,但不能破坏链表的结构。这就是下面将介绍的链表的插入与删除。
"链表的建立、插入和删除"由第二电脑网原创提供,转载请注明:http://www.002pc.com/master/College/Language/VC/2010-05-04/13836.html


关键字:

关于《链表的建立、插入和删除》文章的评论

站内搜索: 高级搜索

热门搜索: Windows style 系统 tr IP QQ CPU 安装 function 注册 if td