数据结构线性表课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构线性表课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 线性 课件
- 资源描述:
-
1、第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储线性表的顺序存储2.3 2.3 线性表的链式存储线性表的链式存储2.4 2.4 线性表的应用线性表的应用 本章小结本章小结 2.5 2.5 有序表有序表 最新.课件12.1 2.1 线性表的基本概念线性表的基本概念 2.1.1 线性表的定义线性表的定义2.1.2 线性表的运算线性表的运算最新.课件22.1.1 2.1.1 线性表的定义线性表的定义 线性表是具有相同特性的数据元素的一个有线性表是具有相同特性的数据元素的一个有限序列。限序列。该序列中所含元素的个数叫做线性表的该序列中所含
2、元素的个数叫做线性表的长度长度,用用n表示表示,n0。当当n=0时时,表示线性表是一个空表表示线性表是一个空表,即表中不包即表中不包含任何元素。设序列中第含任何元素。设序列中第i(i表示位序表示位序)个元素为个元素为ai(1in)。线性表的一般表示为线性表的一般表示为:(a1,a2,ai,ai+1,an)最新.课件3 其中其中a1为第一个元素为第一个元素,又称做表头元素又称做表头元素,a2为为第二个元素第二个元素,an为最后一个元素为最后一个元素,又称做表尾元又称做表尾元素。素。例如例如,在线性表在线性表 (1,4,3,2,8,10)中中,1为表头元素为表头元素,10为表尾元素。为表尾元素。最
3、新.课件42.1.2 2.1.2 线性表的运算线性表的运算 线性表的基本运算如下线性表的基本运算如下:(1)初始化线性表初始化线性表InitList(&L):构造一个空的线性构造一个空的线性表表L。(2)销毁线性表销毁线性表DestroyList(&L):释放线性表释放线性表L占用占用的内存空间。的内存空间。最新.课件5 (3)判线性表是否为空表判线性表是否为空表ListEmpty(L):若若L为空为空表表,则返回真则返回真,否则返回假。否则返回假。(4)求线性表的长度求线性表的长度ListLength(L):返回返回L中元素中元素个数。个数。(5)输出线性表输出线性表DispList(L):
4、当线性表当线性表L不为空时不为空时,顺序显示顺序显示L中各结点的值域。中各结点的值域。(6)求线性表求线性表L中指定位置的某个数据元素中指定位置的某个数据元素GetElem(L,i,&e):用用e返回返回L中第中第 i(1iListLength(L)个元素的值。个元素的值。最新.课件6 (7)定位查找定位查找LocateElem(L,e):返回返回L中第中第1个值域个值域与与e相等的位序。若这样的元素不存在相等的位序。若这样的元素不存在,则返回值为则返回值为0。(8)插入数据元素插入数据元素ListInsert(&L,i,e):在在L的第的第i(1iListLength(L)+1)个元素之前插
5、入新的元素个元素之前插入新的元素e,L的长度增的长度增1。(9)删除数据元素删除数据元素ListDelete(&L,i,&e):删除删除L的第的第i(1iListLength(L)个元素个元素,并用并用e返回其值返回其值,L的长度的长度减减1。最新.课件7 例例2.1 假设有两个集合假设有两个集合 A 和和 B 分别用两个线性分别用两个线性表表 LA 和和 LB 表示表示,即线性表中的数据元素即为集合即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合中的成员。编写一个算法求一个新的集合C=AB,即将两个集合的并集放在线性表即将两个集合的并集放在线性表LC中。中。解解:本算法思想是
6、本算法思想是:先初始化线性表先初始化线性表LC,将将LA的所的所有元素复制到有元素复制到LC中中,然后扫描线性表然后扫描线性表LB,若若LB的当的当前元素不在线性表前元素不在线性表LA中中,则将其插入到则将其插入到LC中。算法中。算法如下如下:最新.课件8void unionList(List LA,List LB,List&LC)int lena,lenc,i;ElemType e;InitList(LC);for(i=1;i=ListLength(LA);i+)/*将将LA的所有元素插入到的所有元素插入到Lc中中*/GetElem(LA,i,e);ListInsert(LC,i,e);le
7、na=ListLength(LA);/*求线性表的长度求线性表的长度*/lenB=ListLength(LB);最新.课件9for(i=1;i=lenb;i+)GetElem(LB,i,e);/*取取LB中第中第i个数据元素赋给个数据元素赋给e*/if (!LocateElem(LA,e)ListInsert(LC,+lenc,e);/*LA中不存在和中不存在和e相同者相同者,则插入到则插入到LC中中*/最新.课件10 由于由于LocateElem(LA,e)运算的时间复杂度为运算的时间复杂度为O(ListLength(LA),所以本算法的时间复杂度为所以本算法的时间复杂度为:O(ListLe
8、ngth(LA)*ListLength(LB)。最新.课件112.2 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表2.2.2 顺序表基本运算的实现顺序表基本运算的实现最新.课件122.2.1 2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储结构就是线性表的顺序存储结构就是:把线性表中的所把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。器中指定存储位置开始的一块连续的存储空间中。这样这样,线性表中第一个元素的存储位置就是指线性
9、表中第一个元素的存储位置就是指定的存储位置定的存储位置,第第i+1个元素个元素(1in-1)的存储的存储位置位置紧接在第紧接在第i i个元素的存储位置的后面。个元素的存储位置的后面。线性表线性表 逻辑结构逻辑结构顺序顺序表表 存储结构存储结构最新.课件13 假定线性表的元素类型为假定线性表的元素类型为ElemType,则每个元则每个元素所占用存储空间大小素所占用存储空间大小(即字节数即字节数)为为sizeof(ElemType),整个线性表所占用存储空间的大整个线性表所占用存储空间的大小为小为:n*sizeof(ElemType)其中其中,n表示线性表的长度。表示线性表的长度。最新.课件14
10、a a1 1 LOC(A)0 a a2 2 LOC(A)+sizeof(ElemType)1 线性表存储空间线性表存储空间 存储地址存储地址 下标位置下标位置 a ai i LOC(A)+(i-1)*sizeof(ElemType)i-1 a an n LOC(A)+(n-1)*sizeof(ElemType)n-1 LOC(A)+(MaxSize-1)*sizeof(ElemType)MaxSize-1 顺序表示意图顺序表示意图最新.课件15 在定义一个线性表的顺序存储类型时在定义一个线性表的顺序存储类型时,需要定义需要定义一个数组来存储线线表中的所有元素和定义一个整一个数组来存储线线表中的
11、所有元素和定义一个整型变量来存储线性表的长度。型变量来存储线性表的长度。假定数组用假定数组用dataMaxSize表示表示,长度整型变量用长度整型变量用length表示表示,并采用结构体类型表示并采用结构体类型表示,则元素类型为通则元素类型为通用类型标识符用类型标识符ElemType的线性表的顺序存储类型可的线性表的顺序存储类型可描述如下描述如下:最新.课件16 typedef struct ElemType dataMaxSize;int length;SqList;/*顺序表类型顺序表类型*/其中其中,data成员存放元素成员存放元素,length成员存放线性表的成员存放线性表的实际长度。
12、实际长度。说明:由于说明:由于C/C+C/C+中数组的下标从中数组的下标从0 0开始,线性表的第开始,线性表的第i i个元素个元素a ai i存放顺序表的第存放顺序表的第i-1i-1位置上。为了清楚,将位置上。为了清楚,将a ai i在逻辑在逻辑序列中的位置称为序列中的位置称为逻辑位序逻辑位序,在顺序表中的位置称为,在顺序表中的位置称为物理位物理位序序。最新.课件172.2.2 2.2.2 顺序表基本运算的实现顺序表基本运算的实现 一旦采用顺序表存储结构一旦采用顺序表存储结构,我们就可以用我们就可以用C/C+语言实现线性表的各种基本运算。为了方便语言实现线性表的各种基本运算。为了方便,假设假设
13、ElemType为为char类型类型,使用如下自定义类型语句使用如下自定义类型语句:typedef char ElemType;最新.课件181.建立顺序表建立顺序表其方法是将给定的含有其方法是将给定的含有n个元素的数组的个元素的数组的每个元素依次放入到顺序表中,并将每个元素依次放入到顺序表中,并将n赋给顺赋给顺序表的长度成员。算法如下:序表的长度成员。算法如下:void CreateList(SqList*&L,ElemType a,int n)/*建立顺序表建立顺序表*/int i;L=(SqList*)malloc(sizeof(SqList);for(i=0;idatai=ai;L-l
14、ength=n;最新.课件192.顺序表基本运算算法顺序表基本运算算法(1)初始化线性表初始化线性表InitList(L)该运算的结果是构造一个空的线性表该运算的结果是构造一个空的线性表L。实际上只。实际上只需将需将length成员设置为成员设置为0即可。即可。void InitList(SqList*&L)/引用型指针引用型指针 L=(SqList*)malloc(sizeof(SqList);/*分配存放线性表的空间分配存放线性表的空间*/L-length=0;本算法的时间复杂度为本算法的时间复杂度为O(1)。顺序表L最新.课件20 (2)销毁线性表销毁线性表DestroyList(L)该
15、运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间。占用的内存空间。void DestroyList(SqList*&L)free(L);本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件21 (3)判定是否为空表判定是否为空表ListEmpty(L)该运算返回一个值表示该运算返回一个值表示L是否为空表。若是否为空表。若L为空为空表表,则返回则返回1,否则返回否则返回0。int ListEmpty(SqList*L)return(L-length=0);本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件22 (4)求线性表的长度求线性表的长度ListLength
16、(L)该运算返回顺序表该运算返回顺序表L的长度。实际上只需返回的长度。实际上只需返回length成员的值即可。成员的值即可。int ListLength(SqList*L)return(L-length);本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件23 (5)输出线性表输出线性表DispList(L)该运算当线性表该运算当线性表L不为空时不为空时,顺序显示顺序显示L中各元素的中各元素的值。值。void DispList(SqList*L)int i;if(ListEmpty(L)return;for(i=0;ilength;i+)printf(%c,L-datai);prin
17、tf(n);最新.课件24 本算法中基本运算为本算法中基本运算为for循环中的循环中的printf语句语句,故时间复杂度为故时间复杂度为:O(L-length)或或O(n)最新.课件25 (6)求某个数据元素值求某个数据元素值GetElem(L,i,e)该运算返回该运算返回L中第中第 i(1iListLength(L)个元素的值个元素的值,存放在存放在e中。中。int GetElem(SqList*L,int i,ElemType&e)if(iL-length)return 0;e=L-datai-1;return 1;本算法的时间复杂度为本算法的时间复杂度为O(1)。最新.课件26 (7)按
18、元素值查找按元素值查找LocateElem(L,e)该运算顺序查找第该运算顺序查找第1个值域与个值域与e相等的元素的位序。相等的元素的位序。若这样的元素不存在若这样的元素不存在,则返回值为则返回值为0。int LocateElem(SqList*L,ElemType e)int i=0;while(ilength&L-datai!=e)i+;if(i=L-length)return 0;else return i+1;最新.课件27 本算法中基本运算为本算法中基本运算为while循环中的循环中的i+语句语句,故时故时间复杂度为间复杂度为:O(L-length)或或O(n)最新.课件28 (8)
19、插入数据元素插入数据元素ListInsert(L,i,e)该 运 算 在 顺 序 表该 运 算 在 顺 序 表 L 的 第的 第 i 个 位 置个 位 置(1iListLength(L)+1)上插入新的元素上插入新的元素e。思路:如果思路:如果i值不正确值不正确,则显示相应错误信息;则显示相应错误信息;否则将顺序表原来第否则将顺序表原来第i个元素及以后元素均后移个元素及以后元素均后移一个位置一个位置,腾出一个空位置插入新元素腾出一个空位置插入新元素,顺序表长顺序表长度增度增1。最新.课件29 int ListInsert(SqList*&L,int i,ElemType e)int j;if(
20、iL-length+1)return 0;i-;/*将顺序表将顺序表逻辑位序逻辑位序转化为转化为elem下标即下标即物理位序物理位序*/for(j=L-length;ji;j-)L-dataj=L-dataj-1;/*将将datai及后面元素后移一个位置及后面元素后移一个位置*/L-datai=e;L-length+;/*顺序表长度增顺序表长度增1*/return 1;a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 最新.课件30 对于本算法来说对于本算法来说,元素移动的次数不仅与表长元素移动的次数不仅与表长L.length=n有关有关,而且与插入位置而且与插入位置
21、i有关有关:当当i=n+1时时,移移动次数为动次数为0;当;当i=1时时,移动次数为移动次数为n,达到最大值。在达到最大值。在线性表线性表sq中共有中共有n+1个可以插入元素的地方。假设个可以插入元素的地方。假设pi(=)是在第是在第i个位置上插入一个元素的概率个位置上插入一个元素的概率,则在则在长度为长度为n的线性表中插入一个元素时所需移动元素的线性表中插入一个元素时所需移动元素的平均次数为的平均次数为:因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。11n)(2)1(11)1(1111nOninninniniip 最新.课件31 (9)删除数据元素删除数据元素List
22、Delete(L,i,e)删除顺序表删除顺序表L中的第中的第i(1iListLength(L)个元个元素。素。思路:如果思路:如果i值不正确值不正确,则显示相应错误信息;则显示相应错误信息;否则将线性表第否则将线性表第i个元素以后元素均向前移动一个个元素以后元素均向前移动一个位置位置,这样覆盖了原来的第这样覆盖了原来的第i个元素个元素,达到删除该元达到删除该元素的目的素的目的,最后顺序表长度减最后顺序表长度减1。最新.课件32int ListDelete(SqList*&L,int i,ElemType&e)int j;if(iL-length)return 0;i-;/*将顺序表逻辑位序转化
23、为将顺序表逻辑位序转化为elem下标即物理位序下标即物理位序*/e=L-datai;for(j=i;jlength-1;j+)L-dataj=L-dataj+1;/*将将datai之后的元素后前移一个位置之后的元素后前移一个位置*/L-length-;/*顺序表长度减顺序表长度减1*/return 1;a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 最新.课件33 对于本算法来说对于本算法来说,元素移动的次数也与表长元素移动的次数也与表长n和和删除元素的位置删除元素的位置i有关有关:当当i=n时时,移动次数为移动次数为0;当;当i=1时时,移动次数为移动次数为n-1
24、。在线性表。在线性表sq中共有中共有n个元素可以个元素可以被删除。假设被删除。假设pi(pi=)是删除第是删除第i个位置上元素的概个位置上元素的概率率,则在长度为则在长度为n的线性表中删除一个元素时所需移的线性表中删除一个元素时所需移动元素的平均次数为动元素的平均次数为:=因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)。)(21)(1)(11nOninninpninii n1最新.课件34 例例2.2 设计一个算法设计一个算法,将将x插入到一个有序插入到一个有序(从小到大排序从小到大排序)的线性表的线性表(顺序存储结构即顺序顺序存储结构即顺序表表)的适当位置上的适当位置上
25、,并保持线性表的有序性。并保持线性表的有序性。解解:先通过比较在顺序表先通过比较在顺序表L中找到存放中找到存放x的位的位置置i,然后将然后将x插入到插入到L.datai中中,最后将顺序表的最后将顺序表的长度增长度增1。最新.课件35 void Insert(SqList*&L,ElemType x)int i=0,j;while(ilength&L-datailength-1;j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-length+;查找插入位置查找插入位置元素后移一个位置元素后移一个位置a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize
展开阅读全文