数据结构ppt课件2-线性表.ppt
- 文档编号:17173182
- 上传时间:2023-07-22
- 格式:PPT
- 页数:42
- 大小:352.50KB
数据结构ppt课件2-线性表.ppt
《数据结构ppt课件2-线性表.ppt》由会员分享,可在线阅读,更多相关《数据结构ppt课件2-线性表.ppt(42页珍藏版)》请在冰点文库上搜索。
第二章线性表,线性表是n个类型相同数据元素的有限序列,通常记作(a1,a2,a3,an)。
2.1线性表的类型定义,例1、数学中的数列(11,13,15,17,19,21)例2、英文字母表(A,B,C,D,EZ)。
例3、某单位的电话号码簿。
一线性表的逻辑结构,电话号码簿是数据元素(记录)的有限序列,每一数据元素包括两个数据项,一个是用户姓名,一个是对应的电话号码。
大量记录的线性表为文件,说明:
设A=(a1,a2,.,ai-1,ai,ai+1,an)是一线性表1)线性表的数据元素可以是各种各样的,但同一线性表中的元素必须是同一类型的;2)在表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前趋,ai+1是ai的直接后继;3)在线性表中,除第一个元素和最后一个元素之外,其他元素都有且仅有一个直接前趋,有且仅有一个直接后继,具有这种结构特征的数据结构称为线性结构。
线性表是一种线性数据结构;4)线性表中元素的个数n称为线性表的长度,n=0时称为空表;5)ai是线性表的第i个元素,称i为数据元素ai的序号,每一个元素在线性表中的位置,仅取决于它的序号;,2.1线性表的类型定义,如何在计算机中存储线性表?
如何在计算机中实现线性表的基本操作?
?
为了存储线性表,至少要保存两类信息:
1)线性表中的数据元素;2)线性表中数据元素的顺序关系;,2.2线性表的顺序存储和实现,在计算机内部可以采用不同的方式来存储一个线性表,其中最简单的方式就是本节要讲的线性表的顺序存储结构。
线性表的顺序存储结构,就是用一组连续的内存单元依次存放线性表的数据元素。
线性表(a1,a2,a3,.an),2.2线性表的顺序存储和实现,一线性表的顺序存储结构顺序表,1线性表的顺序存储结构,1000,1001,1000+i-1,1000+i,1000+n,高级语言中反映线性表存储顺序的常用方法就是数组,存储地址,内存状态,2.2线性表的顺序存储和实现,顺序表图示,存放线性表元素的一维数组,设A=(a1,a2,a3,.an)是一线性表,L是SqList类型的结构变量,用于存放线性表A,则L在内存中的状态如图所示:
2.2线性表的顺序存储和实现,二、顺序表的基本操作算法现在,我们已为线性表设计好了一种存储结构,下面将看到用这种存储方式存储线性表时,线性表的各种基本操作算法。
1)初始化操作InitList_Sq(SqList/InitList_Sq,2.2线性表的顺序存储和实现,L.length,L.listsize,L.elem,0LIST_INIT_SIZE,2插入操作ListInsert_Sq(,2.2线性表的顺序存储和实现,插入操作示意图:
2.2线性表的顺序存储和实现,3删除操作ListDelete_sq(SqList&L,inti,ElemType&e)功能:
删除顺序表L的第i个元素,并用e返回删除操作图示,n-1,n-2,2.2线性表的顺序存储和实现,例:
将两个有序线性表归并成一个有序线性表;设线性表A、B分别用La、Lb的两个顺序表存储,两顺序表中元素按非递减顺序排列,编写算法:
将La、Lb归并得到顺序表Lc,Lc中的元素也按值非递减顺序排列。
三、利用基本操作实现线性表的其他操作现在来回答2.1中提到的问题,如何利用已有基本操作实现线性表的其他操作。
请看下例。
2.2线性表的顺序存储和实现,顺序表的归并图示(算法2.7a),0199,2356889,100,建空表Lc,0,La,Lb归并,7,2.3线性表的链式存储和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。
为了表示线性表中元素的先后关系,每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。
用顺序表存储线性表时,线性表的插入删除操作要移动大量的元素,平均的来看要移动线性表中一半的元素,因此对于应用经常要进行进行插入,删除操作的线性表,一般不使用顺序表存储,下面我们来看线性表的另一种存储结构链式存储结构。
一线性链表的概念1线性链表,2.3.1线性链表,用一组任意的存储单元存储线性表中的数据元素,对每个数据元素除了保存自身信息外,还保存了直接后继元素的存储位置。
2.3.1线性链表,2线性链表图示一般来说,我们并不需要写出直接后继的实际地址,为直观起见,通常用如下所示的图表示链表,其中,箭头表示相应单元中保存的是它所指向结点的存储地址。
结点:
数据元素及直接后继的存储位置(地址)组成一个数据元素的存储结构,称为一个结点;结点的数据域:
结点中用于保存数据元素的部分;结点的指针域:
结点中用于保存数据元素直接后继存储地址的部分;,3线性链表有关术语,2.3.1线性链表,存储数据元素,存储后继结点存储地址,2.3.1线性链表,头指针:
用于存放线性链表中第一个结点的存储地址;空指针:
不指向任何结点,线性链表最后一个结点的指针通常是指针;头结点:
线性链表的第一元素结点前面的一个附加结点,称为头结点;带头结点的线性链表:
第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表;,L是头指针,头结点,空指针,L,线性链表的每个结点中只有一个指针域故也称为单链表,2.3.1线性链表,怎样在计算机上实现线性链表?
?
2.3.1线性链表,结点变量图示,typedefstructLNodeElemTypedata;StructLNode*next;LNode,*LinkList;,LNode:
结构类型名;LNode类型结构变量有两个域:
data:
用于存放线性表的数据元素,next:
用于存放元素直接后继结点的地址;该类型结构变量用于表示线性链表中的一个结点;LinkList:
指针类型名;LinkList类型指针变量用于存放LNode类型结构变量的地址;,datanext,Lnode类型结构变量,LinkList类型指针变量L,4线性链表的结点类型定义,2.3.1线性链表,以L为头指针的线性链表称为线性链表L,二线性链表基本操作的算法假设线性表用带头结点的线性链表L的存储。
下面讨论在这种存储方式下,线性表各种基本操作的算法。
当线性表用线性链表存储时,对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作。
2.3.1线性链表,L,算法:
StatusInitList_L(LinkList/InitList_L,1)初始化操作InitList_L(LinkList&L)功能:
建空线性链表L参数:
L为线性链表的头指针主要步骤:
调用malloc()分配一结点的空间,并将其地址赋值给L;,?
LinkList,2.3.1线性链表,2取元素操作GetElem_L(LinkListL,inti,ElemType,2.3.1线性链表,取元素操作算法:
StatusGetElem_L(LinkListL,intI,ElemType/GetElem_L算法2.8,2.3.1线性链表,例,取第i=3个元素。
e=p-data=Sun,3插入操作ListInsert_L(LinkList&L,inti,ElemTypee)功能:
在线性链表L的第i个元素结点之前插入一个新元素结点;插入操作图示:
2.3.1线性链表,插入前,插入后,2.3.1线性链表,插入操作主要步骤:
1)查找链表L的第i-1个元素结点;2)为新元素建立结点;3)修改第i-1个元素结点的指针和新元素结点指针完成插入;,ai-1,ai,生成一个数据域为e的结点。
p,e,s,data,next,3.插入运算,用C语句描述为:
s=(LinkList)malloc(sizeof(LNode);s-data=e;,ai-1,ai,将数据元素x插在a和b元素之间。
p,data,next,s,用C语言描述为:
s-next=p-next;p-next=s;,4删除操作ListDelete_L(LinkList&L,inti,ElemType&e)功能:
在线性链表L中删除第i个元素,并且用e返回其值,2.3.1线性链表,删除操作主要步骤:
1)查找链表的第i-1个元素结点;2)修改第i-1个元素结点指针,删除第i个元素结点;3)将第i个元素结点中的数据元素赋值给e;4)回收被删除结点空间;,2.3.1线性链表,a,b,p,c,data,next,b,用C语言语句描述为:
p-next=p-next-next;,2.3.1线性链表,a,b,p,c,data,next,b,步骤1:
用循环找到被删除节点i的前驱即:
p=p-next;,2.3.1线性链表,a,b,p,c,data,next,b,步骤2:
将b的地址记录下来即:
q=p-next;,q,2.3.1线性链表,a,b,p,c,data,next,b,步骤3:
让p-next指向b后第一个结点即:
p-next=q-next;,q,2.3.1线性链表,a,b,p,c,data,next,b,q,步骤4:
释放b结点即:
free(q),23线性表的链式存储和实现,单线性链表的缺点之一,是无法从指定的某结点到达该结点的前趋结点,这可能会给某些应用带来一些不便,下面介绍线性表的另外两种链式存储结构循环链表和双向链表。
1循环链表的概念循环链表是线性表的另一种链式存储结构,它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点(头节点)2循环链表图示,2.3.2循环链表,(a)非空表(b)空表,1双向链表的概念,2.3.3双向链表,(a)结点图示,存储数据元素,存储后继结点的地址,存储前趋结点的地址,双向链表中,每个结点有两个指针域,一个指向直接后继元素结点,另一个指向直接前趋元素结点。
typedefstructDulNodeElemTypedata;structDulNode*prior;structDulNode*next;DulNode,*DuLinkList;,双向链表的存储类型描述,2.3.3双向链表,2双向循环链表图示,(c)非空的双向循环链表,(b)空的双向循环链表,在双向链表中删除结点时指针变化情况,在双向链表中插入一个结点时指针的变化情况,2.3.3双向链表,3、双向链表的基本操作算法,S,2.3.3双向链表,2)删除操作算法StatusListDelete_DuL(DuLinkList/LinstDelete_DuL算法2.19,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 ppt 课件 线性