数据结构论坛

首页 » 分类 » 定义 » 数据结构复习指导之线性表的链式表示单链
TUhjnbcbe - 2025/1/9 21:01:00

文章目录

线性表的链式表示

知识总览

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;}

因为附设了一个指向表尾结点的指针,所以时间复杂度和头插法的相同。

注意:

单链表是整个链表的基础,读者一定要熟练掌握单链表的基本操作算法。在设计算法时建议先通过画图的方法理清算法的思路,然后进行算法的编写。

知识回顾与重要考点
1
查看完整版本: 数据结构复习指导之线性表的链式表示单链