文章目录
线性表的链式表示
知识总览
1.单链表的定义
1.1单链表
2.单链表上基本操作的实现
2.1单链表的初始化
2.2求表长操作
2.3按序号查找结点
2.4按值查找表结点
2.5插入结点操作
扩展:对某一结点进行前插操作。
2.6删除结点操作
扩展:删除结点*p。
2.7采用头插法建立单链表
2.8采用尾插法建立单链表
知识回顾与重要考点
线性表的链式表示知识总览顺序表的存储位置可以用一个简单直观的公式表示,它可以随机存取表中任一元素,但插入和删除操作需要移动大量元素。
链式存储线性表时,不需要使用地址连续的存储单元,即不要求逻辑上相邻的元素在物理位置上也相邻,它通过“链”建立元素之间的逻辑关系,因此插入和删除操作不需要移动元素,而只需修改指针,但也会失去顺序表可随机存取的优点。
1.单链表的定义1.1单链表线性表的链式存储又称单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素。
为了建立数据元素之间的线性关系,对每个链表结点,除存放元素自身的信息之外,还需要存放一个指向其后继的指针。
单链表中结点类型的描述如下:
typdfstructINod{//定义单链表结点类型ElmTypdata;//数据域structLNod*nxt;//指针域}LNod,*LinkList;
利用单链表可以解决顺序表需要大量连续存储单元的缺点,但附加的指针域,也存在浪费存储空间的缺点。
由于单链表的元素离散地分布在存储空间中,因此是非随机存取的存储结构,即不能直接找到表中某个特定结点。查找特定结点时,需要从表头开始遍历,依次查找。
2.单链表上基本操作的实现2.1单链表的初始化带头结点和不带头结点的单链表的初始化操作是不同的。
带头结点的单链表初始化时,需要创建一个头结点,并让头指针指向头结点,头结点的nxt域初始化为NULL
boolInitList(LinkListL){//带头结点的单链表的初始化L=(LNod*)malloc(sizof(LNod));//创建头结点L-nxt=NULL;//头结点之后暂时还没有元素结点rturntru;}
不带头结点的单链表初始化时,只需将头指针工初始化为NULL。
boolInitList(LinkListL){//不带头结点的单链表的初始化L=NULL;rturntru;}
注意:
设p为指向链表结点的结构体指针,则*p表示结点本身,因此可用p-data或(*p).data访问*p这个结点的数据域,二者完全等价。
成员运算符(.)左边是一个普通的结构体变量,而指向运算符(-)左边是一个结构体指针。
通过(*p).nxt可以得到指向下一个结点的指针,因此(*(*p).nxt).data就是下一个结点中存放的数据,或者直接用p-nxt-data。
2.2求表长操作求表长操作是计算单链表中数据结点的个数,需要从第一个结点开始依次访问表中每个结点,为此需设置一个计数变量,每访问一个结点,其值加1,直到访问到空结点为止。
intLngth(LinkListL){intln=0;//计数变量,初始为0LNod*p=L;whil(p-nxt!=NULL){p=p-nxt;ln++;//每访问一个结点,计数加1}rturnln;}
求表长操作的时间复杂度为O(n)。另需注意的是,因为单链表的长度是不包括头结点的,因此不带头结点和带头结点的单链表在求表长操作上会略有不同。
2.3按序号查找结点从单链表的第一个结点开始,沿着nxt域从前往后依次搜索,直到找到第i个结点为止,则返回该结点的指针;若i小于单链表的表长,则返回NULL。
LNod*GtElm(LinklistL,inti){LNod*p=L;//指针p指向当前扫描到的结点intj=0;//记录当前结点的位序,头结点是第0个结点whil(p!=NULLji){//循环找到第i个结点p=p-nxt;j++;}rturnp;//返回第i个结点的指针或NULL}
按序号查找操作的时间复杂度为O(n)。
2.4按值查找表结点从单链表的第一个结点开始,从前往后依次比较表中各结点的数据域,若某结点的data域等于给定值,则返回该结点的指针;若整个单链表中没有这样的结点,则返回NULL。
LNod*LocatElm(LinkListL,ElmTyp){LNod*p=-nxt;whil(p!=NULLp-data!=)//从第一个结点开始査找数据域为的结点p=p-nxt;rturnp;//找到后返回该结点指针,否则返回NULL}
按值查找操作的时间复杂度为O(n)。
2.5插入结点操作插入结点操作将值为x的新结点插入到单链表的第i个位置。
先检查插入位置的合法性,然后找到待插入位置的前驱,即第i-1个结点,再在其后插入。
首先査找第i-1个结点,假设第i-1个结点为*p,然后令新结点*s的指针域指向*p的后继,再令结点*p的指针域指向新插入的结点*s。
boolListInsrt(linklistL,inti,ElmTyp)LNod*p=L;//指针p指向当前扫描到的结点intj=0;//记录当前结点的位序,头结点是第0个结点whil(p!=NULLji-1){//循环找到第i-1个结点p=p-nxt;j++;}if(p==NULL)//i值不合法rturnfals;LNod*s=(LNod*)malloc(sizof(LNod));s-data=;s-nxt=p-nxt;//①p-nxt=s;//②rturntru;}
插入时,①和②的顺序不能颠倒,否则,先执行p-nxt=s后,指向其原后继的指针就不存在了,再执行s-nxt=p-nxt时,相当于执行了s-nxt=s,显然有误。
本算法主要的时间开销在于查找第i-1个元素,时间复杂度为O(n)。
若在指定结点后插入新结点,则时间复杂度仅为O(1)。
需注意的是,当链表不带头结点时,需要判断插入位置i是否为1,若是,则要做特殊处理,将头指针工指向新的首结点。
当链表带头结点时,插入位置i为1时不用做特殊处理。
扩展:对某一结点进行前插操作。前插操作是指在某结点的前面插入一个新结点,后插操作的定义刚好与之相反。
在单链表插入算法中,通常都采用后插操作。以上面的算法为例,先找到第i-1个结点,即插入结点的前驱,再对其执行后插操作。由此可知,对结点的前插操作均可转化为后插操作,前提是从单链表的头结点开始顺序查找到其前驱结点,时间复杂度为O(n)。
此外,可采用另一种方式将其转化为后插操作来实现,设待插入结点为*s,将*s插入到*p的前面。我们仍然将*s插入到*p的后面,然后将p-data与s-data交换,这样做既满足逻辑关系,又能使得时间复杂度为O(1)。该方法的主要代码片段如下:
s-nxt=p-nxt;//修改指针域,不能颠倒p-nxt=s;tmp=p-data;//交换数据域部分p-data=s-data;s-data=tmp;2.6删除结点操作
删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性,然后查找表中第i-1个结点,即被删结点的前驱,再删除第i个结点。
boolListDlt(linkListL,inti,Elmryp){LNod*p=L;//指针p指向当前扫描到的结点intj=0;//记录当前结点的位序,头结点是第0个结点whil(p!=NULLji-1){//循环找到第i-1个结点p=p-nxt;j++;}if(p==NULLIIp-nxt==NULL)//i值不合法rturnfals;//令g指向被删除结点LNod*q=p-nxt;=q-data;//用返回元素的值p-nxt=q-nxt;//将*q结点从链中“断开”fr(q);//释放结点的存储空间rturntru;}
同插入算法一样,该算法的主要时间也耗费在查找操作上,时间复杂度为O(n)。
当链表不带头结点时,需要判断被删结点是否为首结点,若是,则要做特殊处理,将头指针工指向新的首结点。当链表带头结点时,删除首结点和删除其他结点的操作是相同的。
扩展:删除结点*p。要删除某个给定结点*p,通常的做法是先从链表的头结点开始顺序找到其前驱,然后执行删除操作。其实,删除结点*p的操作可用删除*p的后继来实现,实质就是将其后继的值赋予其自身,然后再删除后继,也能使得时间复杂度为O(1)。该方法的主要代码片段如下:
q=p-nxt;//令q指向*p的后继结点p-data=p-nxt-data;//用后继结点的数据域覆盖p-nxt=q-nxt;//将*q结点从链中“断开’fr(q);//释放后继结点的存储空间2.7采用头插法建立单链表
该方法从一个空表开始,生成新结点,并将读取到的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头,即头结点之后,算法实现如下:
LinkListList_HadInsrt(LinklistL){//逆向建立单链表LNod*s;intx;//设元素类型为整型L=(LNod*)malloc(sizof(LNod));//创建头结点L-nxt=NULL;//初始为空链表scanf("%d",x);//输入结点的值whil(x!=){//输入表示结束s=(LNod*)malloc(sizof(LNod));//创建新结点s-data-x;s-nxt=L-nxt;L-nxt=s;//将新结点插入表中,工为头指针scanf("%d",x);}rturnL;}
采用头插法建立单链表时,读入数据的顺序与生成的链表中元素的顺序是相反的,可用来实现链表的逆置。每个结点插入的时间为O(1),设单链表长为n,则总时间复杂度为O(n)。
2.8采用尾插法建立单链表头插法建立单链表的算法虽然简单,但生成的链表中结点的次序和输入数据的顺序不一致。
若希望两者次序一致,则可采用尾插法。该方法将新结点插入到当前链表的表尾,为此必须增加一个尾指针,使其始终指向当前链表的尾结点,算法实现如下:
LinkLististTailInsrt(LinklistL){//正向建立单链表intx;//设元素类型为整型L=(LNod*)malloc(sizof(LNod));//创建头结点LNod*s,*r=L;//r为表尾指针scanf("%d",x);//输入结点的值whil(x!=){//输入表示结束s=(LNod*)malloc(sizof(LNod));s-data-x;r-nxt=s;r=S;//r指向新的表尾结点scanf("%d",x);}r-nxt=NULL;//尾结点指针置空rturn;}
因为附设了一个指向表尾结点的指针,所以时间复杂度和头插法的相同。
注意:
单链表是整个链表的基础,读者一定要熟练掌握单链表的基本操作算法。在设计算法时建议先通过画图的方法理清算法的思路,然后进行算法的编写。
知识回顾与重要考点