相比起数组,链表解决了数组不方便移动,插入,删除元素的弊端,但相应的,链表付出了更加大的内存牺牲换来的这些功能的实现。
链表概述包含单链表,双链表,循环单链表,实际应用中的功能不同,但实现方式都差不多。
- 单链表就像是美国男篮,一代一代往下传;
- 双链表像是中国男足,你传球给我,我传球给你,最终传给了守门员;
- 循环链表就像是中国男篮,火炬从姚明传给王治郅,王治郅传给易建联,现在易建联伤了,又传给了姚明
单链表是一种链式存取的数据结构,链表中的数据是以结点来表示的,每个结点由元素和指针构成。
元素表示数据元素的映象,就是存储数据的存储单元;指针指示出后继元素存储位置,就是连接每个结点的地址数据。
以结点的序列表示的线性表称作线性链表,也就是单链表,单链表是链式存取的结构。
对于链表的每一个结点,我们使用结构体进行设计,其主要内容有:
其中,DATA数据元素,可以为你想要储存的任何数据格式,可以是数组,可以是int,甚至可以是结构体(这就是传说中的结构体套结构体)
NEXT为一个指针,其代表了一个可以指向的区域,通常是用来指向下一个结点,链表的尾部NEXT指向NULL(空),因为尾部没有任何可以指向的空间了
故,对于一个单链表的结点定义,可以代码描述成:
//定义结点类型
typedefstructNode{
intdata;//数据类型,你可以把int型的data换成任意数据类型,包括结构体struct等复合类型
structNode*next;//单链表的指针域
}Node,*LinkedList;
//Node表示结点的类型,LinkedList表示指向Node结点类型的指针类型
链表的初始化
初始化主要完成以下工作:创建一个单链表的前置节点并向后逐步添加节点,一般指的是申请结点的空间,同时对一个结点赋空值(NULL),其代码可以表示为:
LinkedListlistinit(){
Node*L;
L=(Node*)malloc(sizeof(Node));//开辟空间
if(L==NULL){//判断是否开辟空间失败,这一步很有必要
printf("申请空间失败");
//exit(0);//开辟空间失败可以考虑直接结束程序
}
L->next=NULL;//指针指向空
}
注意:一定要判断是否开辟空间失败,否则生产中由于未知的情况造成空间开辟失败,仍然在继续执行代码,后果将不堪设想啦,因此养成这样的判断是很有必要的。
头插入法创建单链表利用指针指向下一个结点元素的方式进行逐个创建,使用头插入法最终得到的结果是逆序的。如图所示:
从一个空表开始,生成新结点,并将读取到的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头,即头结点之后。
//头插法建立单链表
LinkedListLinkedListCreatH(){
Node*L;
L=(Node*)malloc(sizeof(Node));//申请头结点空间
L->next=NULL;//初始化一个空链表
intx;//x为链表数据域中的数据
while(scanf("%d",&x)!=EOF){
Node*p;
p=(Node*)malloc(sizeof(Node));//申请新的结点
p->data=x;//结点数据域赋值
p->next=L->next;//将结点插入到表头L-->|2|-->|1|-->NULL
L->next=p;
}
returnL;
}
尾插入法创建单链表
如图所示为尾插入法的创建过程。