![点击分享此内容可以赚币 分享](/master/images/share_but.png)
第二章-线性表11(数据结构word版课件).doc
《第二章-线性表11(数据结构word版课件).doc》由会员分享,可在线阅读,更多相关《第二章-线性表11(数据结构word版课件).doc(38页珍藏版)》请在咨信网上搜索。
1、第二章 线性表、堆栈和队列2.1 线性表的定义和基本操作定义2.1 一个线性表是由零个或多个具有相同类型的结点组成的有序集合。我们用(a0,a1,an-1)来表示一个线性表,n为一个自然数。当n = 0时,线性表中无结点(或曰包含零个结点),这样的线性表被称为空表;当n 1时,称a0为线性表的表头(head),称an-1为线性表的表尾(tail),称ai为ai+1的前驱结点,称ai+1为ai的后继结点,其中0 i n-1;当n =1时,线性表中仅有一个结点,该结点既是表头,又是表尾。2.2 线性表的顺序存储结构按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的内存单元中的这样一种存储方式
2、被称为线性表的顺序存储方式。按顺序存储方式存储的线性表具有顺序存储结构,一般称之为顺序表。换言之,在程序中采用定长的一维数组,按照顺序存储方式存储的线性表,被称为顺序表。若顺序表中元素按其值整序,则称其为有序顺序表。若存储线性表的一个结点需要在内存中占据c个连续字节,则有Loc (ai) = Loc (ai-1) +c进而有Loc (ai) = Loc (a0) + ic【插入算法】:要求在顺序表A中下标为k的结点后插入字段值为item的结点。该插入操作较容易实现,只需从后向前将A中下标大于等于k+1的元素均后移一个位置,但前提是必须保证表未满(lengthMaxSize),且插入位置合法。插
3、入算法描述如下:算法 Insert (A, k, item) / 在顺序表A中下标为 k 的结点后插入值为 item 的结点,length系指顺序表的当前长度I1. 插入合法? / 三种情况不能插入IF ( k length-1 OR length = MaxSize) THEN (PRINT“插入不合法”. RETURN.)I2.插入/从后向前将下标大于等于k+1的元素均后移一个位置FOR i =length-1 TO k+1 STEP -1 DO Ai+1Ai. Ak+1 item. length length+1. / A的当前长度增1 【删除算法】:要求在顺序表A中删除下标为k的结点。
4、在保证顺序表非空且删除位置合法的前提下,实现该删除操作只需从前向后将顺序表中下标大于k的结点均前移一个位置。算法 Delete(A, k) /*删除顺序表A中下标为 k 的结点 */D1.删除合法?IF (k length -1 OR length = 0) THEN ( PRINT “删除不合法”. RETURN.)D2.删除FOR i =k+1 TO length DO Ai-1Ai. / 从前向后将下标大于k的结点均前移一个位置length length -1. / A的当前长度减1 2.3 线性表的链接存储结构用链接存储方式存储的线性表被称为链表。链表中的结点用存储单元(若干个连续字节
5、)来存放,存储单元之间既可以是(存储空间上)连续的,也可以是不连续的,甚至可以零散地分布在存储空间中的任何位置。换言之,链表中结点的逻辑次序和物理次序之间并无必然联系。为了能正确表示结点之间的逻辑关系,一个存储单元(假定每个结点需要一个存储单元)除了存放结点的数据字段的值,还必须存放其逻辑相邻结点(前驱结点或者后继结点)的地址信息,这个地址信息被称为指针。2.3.1 单链表一个单链表结点由两个域构成:指针域数据域 data next其中数据域data存放该结点的数据域的值,指针域next存放该结点的后继结点的地址信息。我们考虑一个由n个元素d1、d2、dn组成的线性表,若采用链接存储方式,则其
6、存储结构如图2.3所示: 结点结点结点d1dnd2headtailNULL图2.3 单链表链表的第一个结点被称为头结点(也称为表头),指向头结点的指针被称为头指针(head). 链表的最后一个结点被称为尾结点(也称为表尾),指向尾结点的指针被称为尾指针(tail),验证一个结点是否是表尾,只须考察该结点的next域值是否为NULL .单链表上的操作:插入:InsertAfter函数 在当前结点this之后插入结点P .算法InsertAfter(this ,P) IA1 将当前结点this的next域值赋给P的next域next(P) next(this).IA2 将P赋给当前结点的next域
7、next(this) P 删除:DeleteAfter函数 删除当前结点this的后继结点,并返回指向被删除结点的指针tempptr。算法DeleteAfter(this . tempptr)/ 删除当前结点的后继结点,并令指针tempptr指向被删除结点;DA1 this的next域值 = NULL?IF next(this)= NULL THEN tempptr NULL. ELSE(tempptr next(this). next(this) next(tempptr) ). 构造链表(1) 生成节点:结点生成函数GetNode:创建一个data域值为item、next域值为nextpt
8、r的结点,并用指针newNode指向该新节点。算法GetNode(item ,nextptr . newNode) / 结点生成算法GN1 为新结点申请空间newNode AVAIL . / NewNode表示指向新创建结点的指针GN2 为结点诸域赋值data(newNode) item. next(newNode) nextptr. (2) 表头插入结点:在头指针为head的链表中,插入一个data域值为item的新结点作为该链表的表头结点,并修改相关指针。算法InsertFront(head , item)IF1 调用函数GetNodeGetNode(item,head. newNode)
9、. IF2 head指向新结点head newNode. 不难看出,通过不断生成结点,并将它们依次插入表头,就可形成一个链表。(3)遍历链表所谓遍历一个结构,是指按一定的次序访问结构中的所有结点,且每个结点恰被访问一次。遍历链表,就是按一定次序访问链表的所有结点。我们知道,一条链必然有链头,抓住链头就意味着抓住了整条链。对于链表而言,头指针就相当于链表的链头,要想遍历整个链表,必须从头指针开始。算法PrintList(head)/ 输出头指针为head的链表PL 1 取表头,计数器初始化currptr head . PL 2 遍历并输出链表结点的data值WHILE(currptr NULL)
10、 DO(PRINT( data(currptr) ). currptr next(currptr). )(4)表尾插入结点我们知道,通过向表头插入结点可以构造链表。另一种构造链表的方法是将结点链接到表的尾部,这种方法被称为表尾插入。要想进行表尾插入,必须先测试一下链表是否为空表。对于一个空链表,向表尾插入一个结点和向表头插入一个结点,得到的是相同的链表,故利用InsertFront就可实现对空链表的表尾插入。对于非空链表,要实施表尾插入操作必须先确定表尾结点,这一步要通过扫描整个链表来实现。currptrheaditem新结点算法InsertRear( head ,item )/ 在头指针为h
11、ead的链表尾部插入data域值为item的结点;IR1 取头指针currptr head .IR2 currptr = NULL?IF currptr = NULL THEN InsertFront(head ,item) ELSE( WHILE(next(currptr) NULL) DO currptr next(currptr). GetNode(item,NULL . newNode). InsertAfter(currptr ,newNode) )我们知道,无论以何种存储方式实现线性表,都要支持线性表的基本操作。但是,对图2.3所示的单链表,如果要执行删除操作,且被删除的结点是头结
12、点,则必须修改头指针,令其指向新的头结点(原头结点的后继结点),插入操作也会遇到类似问题。解决办法就是在表的前端增加一个特殊的表头结点,称其为哨位结点,如图2.4 .NULL结点dn哨位结点结点d1tailhead图2.4 增加哨位结点的单链表哨位结点的结构与其它表结点相同,也是由数据域和指针域构成的,但数据域没有被赋值,指针域则存储指向第一个真正表结点的指针。要说明的是,哨位结点不被看作表中的实际结点,本书在讨论链表中第k个结点时均指第k个实际的表结点,在讨论表的长度时,将非哨位结点的个数称为链表的长度;若表中只有哨位结点,则称其为空链表,即表长度为0 .从图2.4可以看出,与顺序表不同,单
13、链表无法直接访问指定位置的结点,而是需要从哨位结点head开始,沿着next指针逐个结点计数,直至到达指定位置。【存取算法】:要求将链表中第k个结点的数据域值赋给item. 该操作很容易实现,只需在保证k合法的前提下,从表头开始逐一访问链表结点,直至找到第k个结点为止。算法 Find ( k, item) / 将链表中第k个结点的字段值赋给item F1. k合法? / IF ( k 1) THEN (PRINT“存取位置不合法”. RETURN.)F2. 初始化 phead . i0. /令指针p指向哨位结点,计数器初始值为0F3. 找第k个结点WHILE (pNULL AND ik) DO
14、( pnext(p) . ii+1. ) / 若找到第k个结点或已到达表尾,则循环终止IF p = NULL THEN ( PRINT“无此结点”. RETURN. )itemdata(p). 下面讨论存取算法的时间复杂度,为方便计,设表的长度为n .对于算法Find,最好情况下的时间复杂度为O(1);最坏情况下的时间复杂度为O(n);平均情况下,假设kn的概率相同,即每种情况的发生概率为1/(n+2) ,则WHILE循环的执行次数平均为因此存取算法的时间复杂度为O(n).【查找算法】:要求在链表head中查找字段值为item的结点并返回其在表中的位置。同存取算法类似,查找算法也需要从表头开始
15、逐一访问链表结点,并比较每个结点的字段值是否为item,直至找到该结点或已遍历至表尾仍未找到(算法终止)。算法 int Search (item .i) / 在链表中查找字段值为item的结点并返回其在表中的位置i(从1开始编号),如果item不在表中,则返回-1。S1. 初始化 pnext(head) . i1. / 令指针p指向哨位结点的后继结点,计数器初始值为1S2. 逐点访问 WHILE (p NULL AND data(p) item) DO( pnext(p) . ii+1. ) / 令指针p指向下一个结点,且计数器加1IF pNULL THEN RETURN i .PRINT “
16、无此结点”. RETURN -1. 容易看出,Search算法最好情况下的时间复杂度为O(1),最坏情况和平均情况下的时间复杂度皆为O(n). 单链表的插入和删除算法比顺序表要简单得多,它无需改变一系列存储单元的存储值,仅仅需要修改一下相关结点的next指针。插入和删除涉及到新结点存储空间的申请和无用结点存储空间的释放,在ADL语言中,申请新存储空间的操作用语句“xAVAIL”来描述,释放不用的空间则用语句“AVAIL x”来描述,其中AVAIL是一个可利用空间表。【删除算法】:要求删除链表中第k个结点并将其字段值赋给item . 该算法首先需要找到第k-1个结点,并存取其后继结点(第k个结点
17、)的字段值,其实现过程与存取算法Find类似;然后修改第k-1个结点的next指针使其指向第k+1结点。需要注意的是,在此过程中应该用一个临时指针指向被删除结点,并最终释放该结点所占用的存储空间,否则该部分空间将成为存储空间中无法利用的垃圾。单链表删除算法如图2.5所示,要删除链表中结点p与q之间的结点s,只需修改结点p的next指针,使其指向结点q. 删除前datadatanextdatasqp删除后datadatanextdataspq图2.5 单链表的删除算法删除算法的ADL描述如下:算法Delete ( k . item ) / 删除链表中第k个结点并将其字段值赋给item D1. k
18、合法?IF ( k 1) THEN (PRINT“删除不合法”. RETURN.)D2. 初始化 phead . i0. / 令指针p指向哨位结点,计数器初始值为0D3. 找第k-1结点/用p指向第k-1结点,q指向第k结点WHILE (pNULL AND ik -1) DO( pnext(p) . ii+1. ) IF p = NULL THEN ( PRINT “无此结点”. RETURN. )D4. 删除qnext(p). next(p) next(q). / 修改p的next指针itemdata(q). AVAILq. /存取q的字段值并释放其存储空间 【插入算法】:在链表中第k个结点
19、后插入字段值为item的结点。该算法首先要找到第k个结点,其实现过程与存取算法Find类似. 为新插入结点申请存储空间,并令其next指针指向第k+1个结点;修改第k个结点的next指针,令其指向新插入结点。插入算法如图2.6所示,要实现在指针p和q所指结点之间插入结点s,只需修改p和s的next指针,但两个指针的修改是有顺序的.datanextdatadatanextdata插入后插入前pqpdataqdatanextss图2.6 插入算法示意图插入算法的ADL描述如下: 算法Insert ( k, item ) / 在链表中第k个结点后插入字段值为item的结点。指针p指向第k个节点,指针
20、s指向新生成的节点,算法在p之后插入s。I1. k合法?IF ( k 0) THEN (PRINT“插入不合法”. RETURN.)I2. 初始化 phead . i0. I3. p指向第k结点WHILE (pNULL AND ik) DO( pnext(p) . ii+1. ) IF p=NULL THEN ( PRINT “插入不合法”. RETURN. )I4. 插入sAVAIL. data(s) item. next(s) next(p). next(p) s. 删除算法和插入算法时间复杂度的计算与存取算法类似,本书不再赘述。2.3.2 循环链表从单链表一个结点出发,只能访问到链接在它
21、后面的结点,而无法访问位于它前面的结点。这对一些实际应用很不方便。解决的办法是把链接结构“循环化”,即把表尾结点的next域存放指向哨位结点的指针,而不是存放空指针NULL(即L),这样的单链表被称为循环链表。循环链表使我们可从链表的任何位置开始,访问链表中的任一结点。图2.6给出了一个循环链表的示例。图2.6 循环链表datanextdatanextdatanextnexthead空循环链表系指该单链表中只包含一个头指针head指向的哨位结点,其next域存放指向自身的指针。图2.7示出了一个空循环链表。不难看出,对于单链表和循环链表,检测链表是否为空的方法不同:单链表:next (head
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 线性 11 数据结构 word 课件
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。