山东大学《数据结构》讲义02线性表.docx
《山东大学《数据结构》讲义02线性表.docx》由会员分享,可在线阅读,更多相关《山东大学《数据结构》讲义02线性表.docx(21页珍藏版)》请在咨信网上搜索。
1、第二章线性表内容概述线性结构是每一个有意义的程序基本都使用的一种数据结构,也是最简单的数 据结构。那么,线性结构如何表示与实现?本章从线性表的抽象数据类型定义、 线性表的顺序存储及实现算法、线性表的链式存储及算法实现等三个方面阐述该 问题。重点与难点重点为顺涓表和单链表的描述和插入、删除运算以及算法的效率分析。难点为 单链表的插入、删除运算和链表的应用。思考.线性结构与非线性结构的根本区别是什么?1 .线性表有哪两种存储结构,各有哪些优缺点?2 .在单链表和双向链表中,能否从当前结点出发访问任一结点?3 .当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,那么 采用何种存储结构为
2、宜?当经常进行的是插入和删除操作时,那么应采用存储结构 为宜?4 .在单链表中设置头结点有何作用?5 .有一个单链表L (至少有1个结点),编写一个算法将L逆置,即最后一个 结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。6 .有一个单链表,其结点的元素值以非递减有序排列,其结点的元素值有可能 相同,编写一个算法删除单链表中多余的元素值相同的结点。第一节线性表的类型定义线性表示最常用且最简单的一种数据结构。了解线性表的结构特点、掌握线性表 抽象类型定义是运用线性结构解决具体应用问题的基础。1.线性表定义、线性表的结构特点所谓线性表(Linear_List),就是n (n0)个数
3、据元素的集合al,a2,an, 这些数据元素之间有逻辑上的线性关系。线性表结构的特点是:当数据元素集合为非空时(即n0),那么(1)有且仅 有一个元素作为该结构的第一个元素,即al; (2)有且仅有一个元素作为该结 构的最后一个元素,即an; (3)当l时,第k个元素ak有且仅 有一个直接前驱,即ak-1,有且仅有一个直接后继,即ak+1;另外,al的后继 为a2, al无前驱,an的前驱为an-1, an无后继。具有n个元素的线性表,n称为线性表的长度。当长度n为。时,线性表称为 空表。当n0时,线性表中每个数据元素ai的位置称为ai在线性表中的位序。线性表中每个数据元素在不同的情况下,可以
4、是一个数或一个符号,也可以是 一篇文章,甚至是图片等其他更复杂的信息。例如,2到20的所有质数:(2, 3, 5, 7, 11, 13, 17, 19)是一个线性表,表中的数据元素是单个的整数。又如,一个班级的学生姓名集合: (李帅,张伟,王明)表中的数据元素是字符串。在第一章所举的例子中,航班信息表为稍复杂的线性表,一个数据元素可以由 在数据元素a和数据元素b之间插入数据元素金插入后e所在结点*s的指针域 为其前驱结点*p的原来指针域的值,以实现*s结点的后继为*p结点原来的后继, 同时*P的指针域指向结点*s。StatusListInsert_ L (List_ Link&L, inti,
5、 Elem Typee)p=L;j=O;p指向头结点,j%计数器while(p&jnext;+j;/iJM i-1 个结点if(!pllji-l)returnERROR;s=(List_ Link)malloc(sizeof(LNode);为插入元素申请空间s-data=e;插入元素s-next=p-next;p-next=s;returnOK;/ListInsert_L算法2-11链式存储的线性表的插入算法该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法相同,为查 找到第i-1个元素的位置,进行顺序访问元素的平均次数的数量级为n,故止匕算 法的时间复杂度为O(n)o6、链式存储的线
6、性表的删除算法删除线性表中的第/个元素删除元素的操作是将要删除结点的前驱结点的指针值设置为其后继结点的位 置,然后释放删除结点的空间。如图2.7所示,删除结点a和结点c之间的结点 b,那么将结点a的指针指向结点b的后继即结点c的位置,然后释放结点b的空 间。StatusListDelete_ L (List_ Link&L, inti, Elem Type&e)p=L;j=O;p指向头结点,j为计数器while(p-next&jnext;+j;到第 i-1 个结点 if(!(p-next)Hji-l)returnERROR;q=p_next力完成血除元素操作p-next=q-next;e=q-
7、data;free(q);returnOK;/ListDelete_L算法屋12链式存储的线性表的删除算法该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法相同,为查 找到第i-l个元素的位置,进行顺序访问元素的平均次数的数量级为n,故此算法的时间复杂度为0(n)o_ 7、在链式存储的线性表中查找元素的算法在线性表中查找满足条件的元素同返回第i个元素算法类似,也需要通过顺序访问结点的方式找到满足条件的 元素并返回该元素的位置。假设直到线性表尾还未找到满足条件的元素,那么返回空。 intLocateElem_ L(List_ LinkL, Elem Typee,Status(*compa
8、re)(Elem Type.Elem Type )(p=L-next;j=l;p指向第一个结点,j为计数器while(p&(*compare)(p-data/ e)p=p-next;+j;假设pdata、e满足茨系贝U compare/0查找相匹配的结点if(!p)returnO;elsereturnj;/LocateElem_L算法2-13在链式存储的线性表中查找元素的算法该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法类似,为查 找到满足条件的元素的位置,进行顺序访问元素的平均次数的数量级为,故此 算法的时间复杂度为0(n)o8、链式存储的有序线性表的插入算法有序表的插入有序表的
9、插入也是通过顺序访问结点的方式找到满足条件的插入位置,然后插 入元素即可,插入过程中进行的操作同普通插入操作相同。Status List_ Sorted_ Insert_ L (List_ Link&L, Elem Typee)非递次排列的看序线屉表的钻入p=L;/p指向头结点while(p-next&e =p-next-data)p=p-next;或鲁找到表尾(此时p-next为0)或者找到第一个比e的值大的数据元素结点:* (pnext)对上述两种情况,都意味着新元素插入到p结点之后s=(List_ Link)malloc(sizeof(LNode);s-data=e;s- next=p-
10、 next;插入 元素p-next=s;retumOK;插入操作成功List_Sorted_Insert_L算法2-14链氐存储的有序线性表的插入算法该算法的主要操作和影响算法效率的步骤同在线性表中查找满足条件的元素 类似,进行顺序访问元素的平均次数的数量级为,故此算法的时间复杂度为 0(n)o9、链式存储的有序线性表的合并算法有序表的合并在有序表的合并中,通过比拟两个线性表的元素的大小,选择元素从小到大依 次插入。当其中一个线性表的元素插入完成后,将另一个线性表的剩余元素直接 插入即可。voidMergeList_ L(List_ Link&La, List_ Link&Lb, List_
11、Link&L c)pa=La- next;pb=Lb- next;pa,pb分别指向La, Lb的第一个结点Lc=pc=La;La为最终合并表,实际上是将Lb的元素结点插入到La中while(pa&pb)通过比拟选择插入元素if(pa-data data)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next; _pc-next=pa?pa:pb;将比拟完后的剩余元素插入free(Lb);/MergeList_L算法2-15链式存储的有序线性表的合并算法该算法的主要操作和影响算法效率的步骤同顺序表中有序表的合并类似,为依 次比拟两
12、个线性表的元素,选择符合条件的元素进行插入,然后插入剩余元素。 假定两个线性表的长度分别为n和m,那么此算法的时间复杂度为O(n+m)。10、链式存储的线性表的排序算法线性表的排序本算法采用起泡法对线性表的数据元素进行排序,排序方式同数组排序方式 类似。本算法中利用指向表尾结点的指针p作为结束标记;利用end表示每一 遍处理范围中最后一结点,即每遍的结束标记。如果元素需要交换位置,那么仅需 交换两个结点的数据元素的数据即可。voidSortList_L(List_ Link&L)将原来完序的纺性表排序为非递减线性表,使用起泡法if(L -next=NULL)return;p=L-next;/p
13、指向第一个结点while(p-next)p=p-next;p为表尾结点,作为结束标记end=p;/end为每遍处理范围的结束标记fo(s=L-next;s!=p;s=s-next)只意味循环 n-1 次for(q=L-next;q!=end;temp=q/ q=q-next)使用起泡法进行排序if(q-data)(q-next-data)t=q-data;q-data=q-next-data;q-next-data=t;end=temp;/SortList_L算法2-16链式存储的线性表的排序算法该算法的主要操作和影响算法效率的步骤同顺序表中线性表的排序类似,都是 使用起泡法进行主要的操作。执
14、行此算法时,假定线性表的长度为n,那么通过两 层循环比拟元素并且完成元素交换操作的数量级为n2,故此算法的时间复杂度 为。(n2)。第四节线性表的其他链式表示在特定的运行环境下或针对一些特定操作,线性表也可以采用其他链式表示。比 如,运用不设指针类型的高级语言实现单链表,就应采用静态链表;对于线性 表的合并操作,采用循环链表那么操作更容易实现;采用双向链表那么有助于查找结 点的前驱元素。1.静态链表的生成算法静态链表(StaticLinkedList)是利用一组地址连续的内存空间来描述线性链表, 把数组元素作为存储结点,数组元素类型包含数值域data和游标指示器cur。游 标定义为整型,指示结
15、点在数组中的相对位置。通常下标为零的元素被看成是头 结点,其游标指示器指示线性链表的第一个结点。这种存储结构同样具有链式存 储结构的主要优点,即在插入和删除元素时只需要修改游标而不用移动元素,但 也有一些缺点,例如要预先分配一个较大的空间。静态链表描述如下:#defineMAXSIZE1000typedefstruct ElemTypedata;intcur;component,List_StMAXSIZE;在静态链表中,福入、删除元素的算法为修改游标,与单链表中要通过修改指 针实现插入、删除操作不同的是,malloc和free两个函数使用的是静态链表本 身的已声明的空间,即静态链表中未使用的
16、局部,静态链表的这个局部称为备 用链表。设S为List_St型变量,如图2.8, Sl为线性表的头结点(“为该结点的游标, 即头指针),i=Sl.cu为第一个结点的位置,Si.data存储线性表的第一个元 素,Si.cur指示第二个结点的位置。一般地,假设i指示第k个结点位置,那么Si.data 为第k个结点的值,Si,cu为下一结点(第k+1个结点)的位置。对于备用链 表(也带有头结点,通常为S0),我们可以通过SO.cur指向备用链表的第 一个结点,如图2.8,游标指示器指向S8,那么S8是备用链表的第一个结点, 而后通过每个结点的游标将备用链表的结点连接起来。下面我们将给出几个典型 的静
17、态链表操作的算法。1头指针图2.8静态饿表例如缶刖信我的 第一个结点将整个数组空间初始化成一个空闲链表 voidInitSpace_St(List_St&S)将一维数组S中各分量链成一个备用链表 /SO.cur指向备用链表的第一个结点。为空闲链表头指针for(i=0;iMAXSIZE-l;+i)Si. cur=i+l;SMAXSIZE-1.cur=O;/InitSpace_St算法218空闲链表的初始化算法2静态链表的插入算法在静态链表中实现的定位函数LocateElem本算法通过静态链表各个结点的游标指示器依次顺序访问每个结点,找到满足条 件的元素,或者直到静态链表尾为止。intLocate
18、Elem_St(List_StS/Elem Typee)在静态的串链线栓宝中查找1个值为e的元素假设找到,那么返回它在S中的下标,否那么返回0i=Sl.cur;while(i&Si. data!=e)i=Si. cur;returni;/LocateElem_St算法2-历静态链表的定位函数该算法的主要操作和影响算法效率的步骤为通过静态链表的结点游标依次顺 序访问每个结点,与线性表的长度有关,故此算法的时间复杂度为0()。 在静态链表的指定位置插入元素在静态链表中插入元素,首先使用Malloc_St(List_StS)函数从备用链表中取出 一个结点的单元,即将备用链表头结点的游标指向的单元取出
19、。如图2.9(a)所示, 使用SO.cu/指向的S8结点,令S0,CUr=S8.CU/,使头结点S0指向S8 的后继元素,完成取出S8的操作。然后通过顺序访问找到插入位置,在i=7 的位置即元素a6之后插入S8结点,如图2.9(b)所示,S8.cur=S7.cur, S7.cu=8,使S7的后继元素为S8, S8的后继元素为原S7的后继元素。 intMalloc_St(List_StS)假设备用空间铺表非空,那么返回分配的结点的下标,否那么返回0i=SO.cur;if(SO. cur)SO. cur=Si.cur;returni;/Malloc_StStatusInsert_St(List_S
20、t&SJntifE!em Typee)在静态面单链线屉表中查找第i-l个元素的位置假设找到,那么在它的下一个位置插入元素,否那么返回ERRORj=l;for(k=0;j&ki-l)returnERROR;m=Malloc_St(S);if(!m)exit(OVERFLOW);Sm.data=e;Sm. cur=Sj. cur;Sj. cur=m;returnOK;/Insert_St算法2-20静态链表的插入算法该算法的的主要操作和影响算法效率的步骤为通过静态链表的结点的游标顺序访问每个结点找到插入位置,与线性表的长度有关,故此算法的时间复杂度为O(n)o表的表的表尾3479(b)(c)图2.
21、93、静态链表的删除算法删除静态链表中指定位置的元素在静态链表中删除指定位置的元素,首先需要通过顺序访问找到删除元素的位 置,如图2.9(b)所示,删除第2个位置的元素,即元素a2,贝U令S2.cur=S3.cu, 使S2,cu指向S3的后继元素。然后使用Free_St(List_St&S,intn)函数将结点 S3放回备用链表的头结点之后,如图2.9(c)所示,使S3,cur=S0.Cur, S,cur=3,把S3插入到备用链表,从而完成操作。voidFree_ St(L ist_ StS, intn)将下标为n而结点回收到备用链表Sn. cur=SO. cur;SO. cur=n;Free
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 山东大学 讲义 02 线性
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。