数据结构课件.ppt
- 文档编号:18680551
- 上传时间:2023-09-06
- 格式:PPT
- 页数:97
- 大小:608.50KB
数据结构课件.ppt
《数据结构课件.ppt》由会员分享,可在线阅读,更多相关《数据结构课件.ppt(97页珍藏版)》请在冰点文库上搜索。
第2章线性表扬州大学信息学院扬州大学信息学院王丽爱王丽爱23962知识点什么是线性表?
什么是线性表?
(逻辑结构逻辑结构)线性表如何存储?
线性表如何存储?
(存储结构存储结构)不同存储方式下如何实现线性表的基本操作?
不同存储方式下如何实现线性表的基本操作?
(操作操作)23963第2章线性表2.1线性表的类型定义线性表的类型定义2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性表的链式表示和实现线性表的链式表示和实现2.3.1线性链表线性链表2.3.2循环链表循环链表2.3.3双向链表双向链表2.3.4单链表应用举例单链表应用举例239642.1线性表的类型定义定义定义线性表线性表(Linear_List)是是n个数据元素的个数据元素的有限有限序序列。
列。
说明说明数据元素根据需要可以不同数据元素根据需要可以不同(同一线性表中的数据同一线性表中的数据元素具有相同属性,换句话说,属于某个数据对元素具有相同属性,换句话说,属于某个数据对象象)数据元素可以由若干个数据项数据元素可以由若干个数据项(dataitem)组成,此组成,此时,常把数据元素称为时,常把数据元素称为记录记录(record),含有大量记含有大量记录的线性表称为录的线性表称为文件文件(file)举例举例字母表字母表(A,B,C,D,Z)整数数据表整数数据表(6,17,28,50,92,188)学生健康登记表学生健康登记表239652.1线性表的类型定义学生健康登记表学生健康登记表姓名学号性别年龄班级健康状况姓名学号性别年龄班级健康状况王小林王小林010631男男18计计01健康健康陈红陈红010632女女20计计01一般一般刘建平刘建平010633男男21计计01健康健康张立立张立立010634男男19计计01神经衰弱神经衰弱239662.1线性表的类型定义线性表中数据元素之间的关系可以排成一个线性序线性表中数据元素之间的关系可以排成一个线性序列:
列:
(a1,a2,ai-1,ai,ai+1,an)其中其中n称作表的称作表的长度长度,当,当n=0时,称作时,称作空表空表。
非空表中,非空表中,a1称为称为第第1个元素个元素,an称为称为最后一个最后一个元素元素,ai是是第第i个元素个元素,称,称i为数据元素为数据元素ai在线性在线性表中的表中的位序位序。
相邻两个数据元素之间存在着有序偶关系,相邻两个数据元素之间存在着有序偶关系,ai-1领先于领先于ai,ai领先于领先于ai+1,称称ai-1是是ai的的直接直接前前驱驱元素元素,ai+1是是ai的的直接直接后继后继元素元素。
239672.1线性表的类型定义线性表的特点:
线性表的特点:
1.线性表中所有元素的性质相同。
即属于同线性表中所有元素的性质相同。
即属于同一数据对象。
一数据对象。
2.非空表中,除第一个和最后一个数据元素之非空表中,除第一个和最后一个数据元素之外,其它数据元素有且仅有一个直接前驱元外,其它数据元素有且仅有一个直接前驱元素和一个直接后继元素。
第一个数据元素素和一个直接后继元素。
第一个数据元素a1无前驱,最后一个数据元素无前驱,最后一个数据元素an无后继。
无后继。
3.数据元素在表中的位置只取决于它自身的序数据元素在表中的位置只取决于它自身的序号。
号。
4.线性表的长度可以根据需要增长或缩短。
线性表的长度可以根据需要增长或缩短。
239682.1线性表的类型定义ADTLinear_list数据元素数据元素ai属于同一数据对象,属于同一数据对象,i=1,2,3,n,n0结构结构对所有的数据元素存在次序关系对所有的数据元素存在次序关系操作操作设设L为为Linear_list类型的线性表,则可类型的线性表,则可进行如下操作:
进行如下操作:
线性表初始化:
线性表初始化:
Init_List(L)初始条件:
表初始条件:
表L不存在不存在操作结果:
构造一个空的线性表操作结果:
构造一个空的线性表求线性表的长度:
求线性表的长度:
Length_List(L)初始条件:
表初始条件:
表L存在存在操作结果:
返回线性表中的所含元素的个数操作结果:
返回线性表中的所含元素的个数取表元:
取表元:
Get_List(L,i)初始条件:
表初始条件:
表L存在且存在且1=i=Length_List(L)操作结果:
返回线性表操作结果:
返回线性表L中的第个元素的值或中的第个元素的值或地址地址23969按值查找:
按值查找:
Locate_List(L,x),是给定的一,是给定的一个数据元素。
个数据元素。
初始条件:
线性表初始条件:
线性表L存在存在操作结果:
在表操作结果:
在表L中查找值为的数据元素中查找值为的数据元素,其结果返回在,其结果返回在L中首次出现的值为的那个中首次出现的值为的那个元素的序号或地址,称为查找成功元素的序号或地址,称为查找成功;否则,在否则,在L中未找到值为的数据元素,返回一特殊值表示中未找到值为的数据元素,返回一特殊值表示查找失败。
查找失败。
插入操作:
插入操作:
Insert_List(L,i,x)初始条件:
线性表初始条件:
线性表L存在,插入位置正确存在,插入位置正确(1=i=n+1,为插入前的表长为插入前的表长)。
操作结果:
在线性表操作结果:
在线性表L的第的第i个位置上插个位置上插入一个值为入一个值为x的新元素,这样使原序号为的新元素,这样使原序号为i,i+1,.,n的数据元素的序号变为的数据元素的序号变为i+1,i+2,.,n+1,插入后表长,插入后表长=原表长原表长+1。
239610删除操作:
删除操作:
Delete_List(L,i)初始条件:
线性表初始条件:
线性表L存在,存在,1=ilast=-1;returnL;2396182.2线性表的顺序表示和实现、顺序表的插入、顺序表的插入.1顺序表的插入顺序表的插入1213212428304277插入前插入前插入插入25121321242528304277插入后插入后线性表长度增线性表长度增1线性表长度增线性表长度增1239619ai-1.a2a1aiai+1alength2.2线性表的顺序表示和实现.1顺序表的插入顺序表的插入alengthai+1ai-1.a2a1alengthai+1aixaix239620线性表的插入是指在表的第线性表的插入是指在表的第i个位置上插个位置上插入一个值为入一个值为x的新元素,插入后使原表长的新元素,插入后使原表长为为n的表的表:
(a1,a2,.,ai-1,ai,ai+1,.,an)成为表长为成为表长为n+1表表:
(a1,a2,.,ai-1,x,ai,ai+1,.,an)。
i的取值范围为的取值范围为1=ilast=MAXSIZE1)printf(“表满”表满”);return(-1);/*表空间已满,不能插入表空间已满,不能插入*/if(iL-last+2)/*检查插入位置的正检查插入位置的正确性确性*/printf(位置错位置错);return(0);for(j=L-last;j=i-1;j-)L-dataj+1=L-dataj;/*结点结点移动移动*/L-datai-1=x;/*新元素插新元素插入入*/L-last+;/*last仍指向最后元素仍指向最后元素*/return
(1);/*插入成功,返回插入成功,返回*/2396222.2线性表的顺序表示和实现2.2顺序表的插入算法的分析顺序表的插入算法的分析11)1(Eniiisinp顺序表上的插入运算,时间主要消耗在了数据的移顺序表上的插入运算,时间主要消耗在了数据的移动上,在第动上,在第i个位置上插入个位置上插入x,从从ai到到an都要都要向后移动一个位置,共需要移动向后移动一个位置,共需要移动ni1个元个元素,而素,而i的取值范围为:
的取值范围为:
1in+1,即有即有n1个位置可以插入。
个位置可以插入。
设在第设在第i个位置上作插入的概率为个位置上作插入的概率为pi,则平均移动则平均移动数据元素的次数:
数据元素的次数:
2396232.2线性表的顺序表示和实现2.2顺序表的插入算法的分析顺序表的插入算法的分析假设在线性表的任何位置上插入元素都是等概率的,假设在线性表的任何位置上插入元素都是等概率的,则则11112)1(11)1(Eniniiisninninp11npi2396242.2线性表的顺序表示和实现2.2顺序表的插入算法的分析顺序表的插入算法的分析结论:
结论:
在顺序表中插入一个数据元素,平均移动约在顺序表中插入一个数据元素,平均移动约一半的元素一半的元素若表长为若表长为n,则算法则算法Ins_SqList的时间复杂的时间复杂度为度为O(n)2396252.2线性表的顺序表示和实现3.顺序表的删除顺序表的删除.分析:
分析:
问题:
对线性表问题:
对线性表(a1,ai-1,ai,ai+1,an)删除数删除数据元素据元素ai思想:
将思想:
将ai+1到到an依次前移一个位置依次前移一个位置结果:
线性表结果:
线性表(a1,ai-1,ai+1,an)注意:
必须按照从左到右的次序移动;删除结束注意:
必须按照从左到右的次序移动;删除结束后表长减一后表长减一示例:
教材示例:
教材p24图图2.4(略略)239626intDelete_SeqList(SeqList*L;inti)intj;if(iL-last+1)/*检查空表及删除位置的合法检查空表及删除位置的合法性性*/printf(不存在第不存在第i个元素个元素);return(0);for(j=i;jlast;j+)L-dataj-1=L-dataj;/*向上移动向上移动*/L-last-;return
(1);/*删除成功删除成功*/2396272.2线性表的顺序表示和实现3.2顺序表的删除算法的分析顺序表的删除算法的分析与插入运算相同,其时间主要消耗在了移动表中元与插入运算相同,其时间主要消耗在了移动表中元素上,删除第素上,删除第i个元素时,其后面的元素个元素时,其后面的元素ai+1an都要向前移动一个位置,共移动了都要向前移动一个位置,共移动了n-i个元素个元素设设qi是删除第是删除第i个元素的概率,则在长度为个元素的概率,则在长度为n的线的线性表中删除一个元素时所需移动元素次数的期望值性表中删除一个元素时所需移动元素次数的期望值(平均次数平均次数)为:
为:
niidlinq1)(E2396282.2线性表的顺序表示和实现假定在线性表的任何位置上删除元素都是等概率的假定在线性表的任何位置上删除元素都是等概率的,即,即nqi1niniidlninninq1121)
(1)(E3.2顺序表的删除算法的分析顺序表的删除算法的分析2396292.2线性表的顺序表示和实现这说明顺序表上作删除运算时大约需要移这说明顺序表上作删除运算时大约需要移动表中一半的元素动表中一半的元素显然算法显然算法Del_SqList的时间复杂度为的时间复杂度为O(n)。
3.2顺序表的删除算法的分析顺序表的删除算法的分析2396304.按值查找按值查找线性表中的按值查找是指在线性表中查找与给定值线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。
相等的数据元素。
在顺序表中完成该运算最简单的方法:
在顺序表中完成该运算最简单的方法:
从第一个元素从第一个元素a1起依次和起依次和x比比较,直到找到一个与较,直到找到一个与x相等的数据元素,则返相等的数据元素,则返回它在顺序表中的存储下标或序号(二者差回它在顺序表中的存储下标或序号(二者差一);或者查遍整个表都没有找到与一);或者查遍整个表都没有找到与x相等相等的元素,返回的元素,返回-1。
2.2线性表的顺序表示和实现239631算法如下:
算法如下:
intLocation_SeqList(SeqList*L,ElemTypex)inti=0;while(ilast&L-datai!
=x)i+;if(iL-last)return-1;elsereturni;/*返回的是存储位置返回的是存储位置*/2.2线性表的顺序表示和实现239632本算法的主要运算是比较。
本算法的主要运算是比较。
显然比较的次数与显然比较的次数与x在表中的位置有关,也在表中的位置有关,也与表长有关。
当与表长有关。
当a1=x时,比较一次成功。
时,比较一次成功。
当当an=x时比较时比较n次成功。
平均比较次次成功。
平均比较次数为(数为(n+1)/2,时间性能为,时间性能为O(n)。
2.2线性表的顺序表示和实现2396332.2.1顺序表应用举例顺序表应用举例例例21将顺序表将顺序表(a1,a2,.,an)重新排列为以重新排列为以a1为界的两部分:
为界的两部分:
a1前面的值均比前面的值均比a1小,小,a1后面的值都后面的值都比比a1大大(这里假设数据元素的类型具这里假设数据元素的类型具有可比性有可比性,不妨设为整型不妨设为整型)。
这一操作。
这一操作称为划分。
称为划分。
a1也称为基准。
也称为基准。
239634划分的方法有多种,下面介绍的划分算法其划分的方法有多种,下面介绍的划分算法其思路简单,性能较差。
思路简单,性能较差。
基本思路:
基本思路:
从第二个元素开始到最后一个元素,逐一向从第二个元素开始到最后一个元素,逐一向后扫描:
后扫描:
(1)当前数据元素)当前数据元素aI比比a1大时,表明大时,表明它已经在它已经在a1的后面,不必改变它与的后面,不必改变它与a1之间之间的位置,继续比较下一个。
的位置,继续比较下一个。
(2)当前结点若比)当前结点若比a1小,说明它应该在小,说明它应该在a1的前面,此时将它上面的元素都依次向下移的前面,此时将它上面的元素都依次向下移动一个位置,然后将它置入最上方。
动一个位置,然后将它置入最上方。
2.2.1顺序表应用举例顺序表应用举例239635voidpart(SeqList*L)inti,j;ElemTypex,y;x=L-data0;/*将基准置入将基准置入x中中*/for(i=1;ilast;i+)if(L-dataidatai;for(j=i-1;j=0;j-)/*移动移动*/Ldataj+1=L-dataj;L-data0=y;239636本算法中,有两重循环,外循环执行本算法中,有两重循环,外循环执行n1次,内循环中移动元素的次数与当前数据的大小次,内循环中移动元素的次数与当前数据的大小有关,当第个元素小于有关,当第个元素小于a1时,要移动它上面时,要移动它上面的的i-1个元素,再加上当前结点的保存及置入,个元素,再加上当前结点的保存及置入,所以移动所以移动i-1+2次,在最坏情况下,次,在最坏情况下,a1后面的后面的结点都小于结点都小于a1,故总的移动次数为:
,故总的移动次数为:
即最坏情况下移动数据时间性能为即最坏情况下移动数据时间性能为()。
2)3(*)1()21(22nniinini239637例例22有顺序表有顺序表A和和B,其元素均按从小,其元素均按从小到大的升序排列,编写一个算法将它们合到大的升序排列,编写一个算法将它们合并成一个顺序表并成一个顺序表C,要求,要求C的元素也是从的元素也是从小到大的升序排列。
小到大的升序排列。
2.2.12.2.1顺序表应用举例顺序表应用举例239638算法思路:
依次扫描通过算法思路:
依次扫描通过A和和B的元素,比的元素,比较当前的元素的值,将较小值的元素赋给较当前的元素的值,将较小值的元素赋给C,如此直到一个线性表扫描完毕,然后,如此直到一个线性表扫描完毕,然后将未完的那个顺序表中余下部分赋给将未完的那个顺序表中余下部分赋给C即可。
即可。
C的容量要能够容纳的容量要能够容纳A、B两个两个线性表相加的长度。
线性表相加的长度。
2.2.1顺序表应用举例顺序表应用举例239639voidmerge(SeqListA,SeqListB,SeqList*C)inti,j,k;i=0;j=0;k=0;while(i=A.last&j=B.last)if(A.dataidatak+=A.datai+;elseC-datak+=B.dataj+;while(idatak+=A.datai+;while(jdatak+=B.dataj+;C-last=k-1;算法的时间性能是算法的时间性能是O(m+n),其中其中m是是A的表长,的表长,n是是B的表的表长。
长。
2396402.2.1顺序表应用举例顺序表应用举例例例.编写一函数从一给定的编写一函数从一给定的顺序表顺序表A中删除元素值在中删除元素值在x到到y(x=y)之间的所有元素。
之间的所有元素。
239641算法思路:
算法思路:
先扫描,将先扫描,将xy之间的元素置成一个特殊之间的元素置成一个特殊的值(如的值(如0),并不立即删除它们。
),并不立即删除它们。
然后从后往前扫描,遇到然后从后往前扫描,遇到0再移动其后面再移动其后面的元素将其删除。
算法如下:
的元素将其删除。
算法如下:
239642voiddel(SeqList*A,ElemTypex,ElemTypey)for(i=0;ilast;i+)/先扫描先扫描if(A-datai=x&A-dataidatai=0;for(i=A-last;i=0;i-)/从后往前扫描从后往前扫描if(A-datai=0)for(k=i;klast;k+)Ak=Ak+1;A-last-;239643voiddel(SeqList*A,ElemTypex,ElemTypey)for(i=A-last;i=0;i-)/从后往前扫描从后往前扫描if(A-datai=x&A-datai=y)for(k=i;klast;k+)Ak=Ak+1;A-last-;239644voiddel(SeqList*A,ElemTypex,ElemTypey)i=0;j=0;while(ilast)/从前往后扫描从前往后扫描if(A-datai=x&A-datailast=j-;239645小结顺序表的存贮特点:
顺序表的存贮特点:
用物理上的相邻实现了逻辑上的相用物理上的相邻实现了逻辑上的相邻邻;它要求用连续的存储单元顺序存储线它要求用连续的存储单元顺序存储线性表中各元素,因此,对顺序表插入、删除性表中各元素,因此,对顺序表插入、删除时需要通过移动数据元素来实现,影响了运时需要通过移动数据元素来实现,影响了运行效率。
行效率。
239646第2章线性表2.1线性表的类型定义线性表的类型定义2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性表的链式表示和实现线性表的链式表示和实现2.3.1线性链表线性链表2.3.2循环链表循环链表2.3.3双向链表双向链表2.4一元多项式的表示及相加一元多项式的表示及相加2396472.3线性表的链式表示和实现顺序表:
顺序表:
逻辑上相邻的数据元素在物理上也相邻逻辑上相邻的数据元素在物理上也相邻可以随机存取表中任一元素,每个元素的地址可可以随机存取表中任一元素,每个元素的地址可用一个简单、直观的公式来表示用一个简单、直观的公式来表示插入或删除元素时,需要移动大量元素插入或删除元素时,需要移动大量元素线性表的链式存储结构线性表的链式存储结构不要求逻辑上相邻的数据元素在物理上也相邻不要求逻辑上相邻的数据元素在物理上也相邻插入、删除时无需移动元素插入、删除时无需移动元素不能随机存取不能随机存取2396482.3.1线性链表线性表的链式存储结构的特点:
线性表的链式存储结构的特点:
用一组用一组任意的任意的存储单元存储单元(可以是连续的,也可以可以是连续的,也可以是不连续的是不连续的)存放线性表的存放线性表的数据元素数据元素为了表示每个数据元素为了表示每个数据元素ai与其直接后继元素与其直接后继元素ai+1之之间的间的逻辑关系逻辑关系对数据元素对数据元素ai来说,除了存储其本身的信息外来说,除了存储其本身的信息外,还需存储一个指示其直接后继的信息,还需存储一个指示其直接后继的信息(即直接即直接后继的存储位置后继的存储位置)这两部分信息组成数据元素这两部分信息组成数据元素ai的存储映像,称的存储映像,称为为结点结点(node)结点包含两个域:
存储数据元素信息的结点包含两个域:
存储数据元素信息的数据域数据域,存储直接后继存储位置的存储直接后继存储位置的指针域指针域指针域中存储的信息称为指针域中存储的信息称为指针指针或或链链2396492.3.1线性链表n个结点个结点(ai的存储映像的存储映像,1in)链结成一链结成一个个链表链表,即为线性表,即为线性表(a1,a2,an)的的链式存储结构链式存储结构。
此链表的每个结点中只包含一个指针域,故此链表的每个结点中只包含一个指针域,故又称为又称为线性链表线性链表或或单链表单链表2396502.3.1线性链表示例:
示例:
(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)NIL头指针头指针:
指示链:
指示链表中第一个结点表中第一个结点的存储位置的存储位置头指针头指针:
指示链:
指示链表中第一个结点表中第一个结点的存储位置的存储位置最后一最后一个数据个数据元素无元素无直接后直接后继,线继,线性链表性链表中最后中最后一个结一个结点的指点的指针为针为空空2396512.3.1线性链表示例:
示例:
(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)2396522.3.1线性链表常用“头指针”来标识一个单链表,如单链表常用“头指针”来标识一个单链表,如单链表L、单链表、单链表H等,是指某链表的第一个结点等,是指某链表的第一个结点的地址放在了指针变量的地址放在了指针变量L、H中,头指中,头指针为“针为“NULL”则表示一个空表。
则表示一个空表。
2396532.3.1线性链表带头结点的非空单链表带头结点的非空单链表带头结点的空链表带头结点的空链表a1a2anL.L2396542.3.1线性链表描述:
描述:
线性表的链式存储结构可用线性表的链式存储结构可用C语言中的“指针”描语言中的“指针”描述述datanext线性表的单链表的存储结构;线性表的单链表的存储结构;TypedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;239655将操作中用到指向某结点的指针变量说明为将操作中用到指向某结点的指针变量说明为LNode*类类型,如型,如LNode*p;则语句:
;则语句:
p=malloc(sizeof(LNode);则完成了申请一块则完成了申请一块LNode类型的存储单元的操作,并将类型的存储单元的操作,并将其地址赋值给变量其地址赋值给变量p。
P所指的结点为所指的结点为*p,*p的类型为的类型为LNode型,型,该结点的数据域为该结点的数据域为(*p).data或或p-data,指针域为指针域为(*p).next或或p-next。
free(p)则表示释放则表示释放p所指的结点。
所指的结点。
239656单链表上基本运算的实现1.建立单链表链表是一种动态管理的存储结构(顺序表不同)。
链
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件
![提示](https://static.bingdoc.com/images/bang_tan.gif)