数据结构C语言 线性表.pptx

《数据结构C语言 线性表.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言 线性表.pptx（123页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 2.1 2.1 2.1 2.1 线性表的类型定义线性表的类型定义线性表的类型定义线性表的类型定义 2.2 2.2 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现 2.3 2.3 2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现 2.4 2.4 2.4 2.4 线性表的应用线性表的应用线性表的应用线性表的应用第1页/共123页2.1 线性表的类型定义线性结构的线性结构的基本特征基本特征:集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；集合中必存在唯一的一个集合中必

2、存在唯一的一个“最后元素最后元素”；除最后元素之外，均有唯一的除最后元素之外，均有唯一的后继后继；除第一元素之外，均有唯一的除第一元素之外，均有唯一的前驱前驱。从逻辑上：数据之间的关系可以分从逻辑上：数据之间的关系可以分从逻辑上：数据之间的关系可以分从逻辑上：数据之间的关系可以分4 4类类类类：线性结构线性结构线性结构线性结构,树型结构树型结构树型结构树型结构,图状结构图状结构图状结构图状结构,集合集合集合集合线性结构线性结构线性结构线性结构:是一个数据元素的是一个数据元素的有序（次序）有序（次序）集合。集合。仅指在数据元素之间存在一个 领先 或 落后 的次序关系，而非指数据元素 值 的大小可

3、比性。第2页/共123页 线性表最简单的一种线性结构线性表最简单的一种线性结构 一个线性表是一个线性表是n n个数据元素的有限序列个数据元素的有限序列 比如比如 A BZ A BZ 英文字母表英文字母表 比如比如001高等数学华罗庚S01002线性代数銮汝书L01003高等数学郑杭生 S01004离散数学耿素云S02线性表中每个数据元素的具体含义，各不相同，数据元素是基线性表中每个数据元素的具体含义，各不相同，数据元素是基线性表中每个数据元素的具体含义，各不相同，数据元素是基线性表中每个数据元素的具体含义，各不相同，数据元素是基本单位，一个数据元素由若干个数据项组成本单位，一个数据元素由若干个

4、数据项组成本单位，一个数据元素由若干个数据项组成本单位，一个数据元素由若干个数据项组成2.1 线性表的类型定义第3页/共123页线性表记为线性表记为（a a1 1,a ai i-1-1,a ai i,a ai i+1+1,a an n）a ai-1i-1 在在a ai i 之前之前 称称 a ai i-1-1是是 a ai i 的的 前驱前驱a ai i 在在 a ai i-1-1之后之后 称称 a ai i 是是 a ai i-1-1的的 后继后继序列中数据元素的个数序列中数据元素的个数 n n 定义为线性表的表长定义为线性表的表长 称称 i i 为为a ai i在线性表中的位序在线性表中的

5、位序 i i=2=2，,n n线性表的元素个数称为的线性表的元素个数称为的表长表长，n n0 0时称为时称为空表空表2.1 线性表的类型定义第4页/共123页线性表的抽象数据类型(ADT)(ADT)定义如下：ADTADT ListList 数据对象数据对象：D=aD=ai i|a|ai i ElemSet,i=1,2,.,n,n=0 ElemSet,i=1,2,.,n,n=0 数据关系数据关系：R1=aR1=|a|ai-1i-1,a,ai iD,i=2,.,n D,i=2,.,n /表示为相邻元素的有序对表示为相邻元素的有序对 基本操作基本操作：InitList(&L)InitList(&L)

6、操作结果：构造一个空的线性表操作结果：构造一个空的线性表L L。DestroyList(&L)DestroyList(&L)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：销毁线性表操作结果：销毁线性表L L，将原表中各结，将原表中各结点所点所 占的内存空间释放。占的内存空间释放。任何数据结构在被使用之前都必须进行“初始化”，它类似于编程中使用的变量都必须先有定义。任何数据结构不再使用时都必须进行“结构销毁”，其实质为释放它所占有的存储空间。第5页/共123页引用型操作ListEmpty(L)ListEmpty(L)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性

7、表L L已存在。已存在。已存在。已存在。操作结果：若操作结果：若操作结果：若操作结果：若L L为空表，则返回为空表，则返回为空表，则返回为空表，则返回TRUETRUE，否则，否则，否则，否则FALSEFALSE。ListLength(L)ListLength(L)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在。已存在。已存在。已存在。操作结果：返回操作结果：返回操作结果：返回操作结果：返回L L中元素个数中元素个数中元素个数中元素个数。PriorElem(L,cur_e,&pre_e)PriorElem(L,cur_e,&pre_e)初始条件：线性表初始条件：线性

8、表初始条件：线性表初始条件：线性表L L已存在。已存在。已存在。已存在。操作结果：若操作结果：若操作结果：若操作结果：若cur_ecur_e是是是是L L的元素，但不是第一个，则用的元素，但不是第一个，则用的元素，但不是第一个，则用的元素，但不是第一个，则用pre_epre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_epre_e无定义。无定义。无定义。无定义。NextElem(L,cur_e,&next_e)NextElem(L,cur_e,&next_e)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：

9、线性表L L已存在。已存在。已存在。已存在。操作结果：若操作结果：若操作结果：若操作结果：若cur_ecur_e是是是是L L的元素，但不是最后一个，则用的元素，但不是最后一个，则用的元素，但不是最后一个，则用的元素，但不是最后一个，则用next_enext_e返回它的后继，否则操作失败，返回它的后继，否则操作失败，返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_enext_e无定义无定义无定义无定义。第6页/共123页LocateElem(L,e,compare()LocateElem(L,e,compare()初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性

10、表L L已存在，已存在，已存在，已存在，compare()compare()是元素判定函数。是元素判定函数。是元素判定函数。是元素判定函数。操作结果：返回操作结果：返回操作结果：返回操作结果：返回L L中第中第中第中第1 1个与个与个与个与e e满足关系满足关系满足关系满足关系compare()compare()的元素的的元素的的元素的的元素的位序。若这样的元素不存在，则返回值为位序。若这样的元素不存在，则返回值为位序。若这样的元素不存在，则返回值为位序。若这样的元素不存在，则返回值为0 0。ListTraverse(L,visit()ListTraverse(L,visit()初始条件：线性

11、表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在。已存在。已存在。已存在。操作结果：依次对操作结果：依次对操作结果：依次对操作结果：依次对L L的每个元素调用函数的每个元素调用函数的每个元素调用函数的每个元素调用函数visit()visit()。一旦。一旦。一旦。一旦visit()visit()失败，则操作失败。失败，则操作失败。失败，则操作失败。失败，则操作失败。GetElem(L,i,&e)GetElem(L,i,&e)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在，已存在，已存在，已存在，1iLengthList(L)1iLengthList(

12、L)操作结果：用操作结果：用操作结果：用操作结果：用e e返回返回返回返回L L中第中第中第中第i i个元素的值。个元素的值。个元素的值。个元素的值。函数参数函数参数 compare()作为判定的条件，参数作为判定的条件，参数 e 和线性表中数据元素具有相同类型。较和线性表中数据元素具有相同类型。较多场合是以多场合是以“相等相等”作为判定条件，此时可省略函数参数，且操作结果为：若线作为判定条件，此时可省略函数参数，且操作结果为：若线性表中存在与性表中存在与 e 值相同的数据元素，则返回第一个这样的元素在表中的位序，值相同的数据元素，则返回第一个这样的元素在表中的位序，否则返回函数值为否则返回函

13、数值为0。visit()亦为函数参数，常见的情况是亦为函数参数，常见的情况是“依次输出表中元素的值依次输出表中元素的值”，同样在这种情，同样在这种情况下，通常的写法也是省略函数参数。况下，通常的写法也是省略函数参数。第7页/共123页 PutElem(&L,i,e)PutElem(&L,i,e)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在，已存在，已存在，已存在，1iLengthList(L)1iLengthList(L)操作结果：操作结果：操作结果：操作结果：L L中第中第中第中第i i个元素赋个元素赋个元素赋个元素赋e e的值。的值。的值。的值。ListDe

14、lete(&L,i,&e)ListDelete(&L,i,&e)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在且非空，已存在且非空，已存在且非空，已存在且非空，1iLengthList(L)1iLengthList(L)操作结果：删除操作结果：删除操作结果：删除操作结果：删除L L的第的第的第的第i i个元素，并用个元素，并用个元素，并用个元素，并用e e返回其值，返回其值，返回其值，返回其值，L L的长度减的长度减的长度减的长度减1 1。ListInsert(&L,i,e)ListInsert(&L,i,e)初始条件：线性表初始条件：线性表初始条件：线性表初始条

15、件：线性表L L已存在，已存在，已存在，已存在，1iLengthList(L)+11iLengthList(L)+1操作结果：在操作结果：在操作结果：在操作结果：在L L的第的第的第的第i i个元素之前插入新的元素个元素之前插入新的元素个元素之前插入新的元素个元素之前插入新的元素e e，L L的长度增的长度增的长度增的长度增1 1。ADT List ADT ListClearList(&L)ClearList(&L)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在。已存在。已存在。已存在。操作结果：将操作结果：将操作结果：将操作结果：将L L重置为空表。重置为空表。

16、重置为空表。重置为空表。加工型操作第8页/共123页 算法2.1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。从集合的观点看，此问题求解的方法很简单，只要对集合 B 中的所有元素一个一个地检查，看看在集合 A 中是否存在相同元素，若不存在，则将该元素插入到集合 A，否则舍弃之。要在计算机中求解，首先要确定“如何表示集合”。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表示集合。现假设以线性表 LA 和 LB 分别表示集合 A 和 B，即构造两个线性表 LA 和 LB，它们的数据元素分别为集合 A 和 B 中的成员。由此，上述集合求并的问题便可演绎为：要求

17、对线性表作如下操作：扩大线性表 LA，将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。第9页/共123页具体操作步骤为：1从线性表 LB 中取出一个数据元素；2依值在线性表 LA 中进行查询；3若不存在，则将它插入到 LA 中。重复上述三步直至 LB 为空表止。那么，其中的每一步能否利用上述线性表类型中定义的基本操作来完成呢？容易看出，上述的每一步恰好对应线性表的一个基本操作：1.ListDelete(LB,1,e);2.LocateElem(LA,e,equal();3.ListInsert(LA,n+1,e)第10页/共123页void union(L

18、ist&La，List&Lb)while(!ListEmpty(Lb)ListDelete(Lb,1,e);if(!LocateElem(La,e,equal()ListInsert(La,1,e);DestroyList(Lb);/union时间复杂度O(ListLength(La)ListLength(Lb)第11页/共123页void union(List&La，List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=lb_len;i+)GetElem(lb，i，e);if(!LocateElem(la,e,equal(

19、)ListInsert(la,+la_en,e);/union时间复杂度O(ListLength(La)ListLength(Lb)第12页/共123页 算法2.2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：第13页/共123页void mergelist(List la，List lb，List&lc)InitList(lc);i=j=1;k=0;la-len=ListLength(la);lb-len=ListLength(lb);while(i=la-len)&(j=lb-le

20、n)GetElem(la，i，ai);GetElem(lb，j，bj);if(ai=bj)ListInsert(lc，+k，ai);+i;else ListInsert(lc，+k，bj);+j;while(i=la-len)GetElem(la，i+，ai);ListInsert(lc，+k，ai);while(j=lb-len)GetElem(lb，j+，bj);ListInsert(lc，+k，bj);时间复杂度O(ListLength(La)+ListLength(Lb)第14页/共123页思考1已知一个“非纯集合”B，试构造一个集合 A，使 A 中只包含 B 中所有值各不相同的数据元

21、素。分析:将每个从 B 中取出的元素和已经加入到集合 A 中的元素相比较。void purge(List&LA,List LB)/构造线性表LA，使其只包含LB中所有值不相同的数据元素,算法不改变线性表LBInitList(LA);/创建一个空的线性表 LALa_len=0;Lb_len=ListLength(LB);/求线性表 LB 的长度for(i=1;i=Lb_len;i+)/处理 LB 中每个元素 GetElem(LB,i,e);/取LB中第 i 个数据赋给 e /当 LA 中没有和 e 值相同的数据元素时进行插入 if(!LocateElem(LA,e,equal()ListInse

22、rt(LA,+La_len,e);/for/purge第15页/共123页思考2判别两个集合是否相等。分析:首先判别两者的表长是否相等；在表长相等的前提下，对于一个表中的所有元素，是否都能在另一个表中找到和它相等的元素.第16页/共123页bool isEqual(List LA,List LB)/若线性表 LA 和 LB 不仅长度相等，且所含数据元素也相同，/则返回 TRUE，否则返回 FALSE。La_len=Listlength(LA);Lb_len=Listlength(LB);/如果集合中的元素不能保证都相异，那么这个问题的算法应如何写？if(La_len!=Lb_len)retur

23、n FALSE;/两表的长度不等 i=1;while(i=La_len)GetElem(LA,i,e);/取得 LA 中一个元素 if(LocateElem(LB,e,equal()i+;/依次处理下一个 else return FALSE;/LB中没有和该元素相同的元素 /whilereturn true;/isEqual 第17页/共123页J这个算法是否在任何情况下都正确，会不会有例外的情况？当然，这个算法思想还有一个前提是，已知集合符合集合论中的约定集合中的元素都是彼此相异的。J如果“集合”中的元素不能保证都相异，那么这个问题的算法应如何写？除了判别每个 LA 中的元素在 LB 中都存

24、在之外，还应反过来判别 LB 中每个元素都能在 LA 中找到相同者。第18页/共123页若要在实际的程序设计中真正引用线性表的基本操作，首先必须实现线性表类型。即在计算机中确定它的存储结构并在此存储结构上实现类型中定义的所有基本操作。本节将讨论它的顺序存储结构以及在顺序存储结构中基本操作的实现。第19页/共123页 2.1 2.1 2.1 2.1 线性表的类型定义线性表的类型定义线性表的类型定义线性表的类型定义 2.2 2.2 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现 2.3 2.3 2.3 2.3 线性表的链式表示和实现线性表的

25、链式表示和实现线性表的链式表示和实现线性表的链式表示和实现 2.4 2.4 2.4 2.4 线性表的应用线性表的应用线性表的应用线性表的应用第20页/共123页2.2 线性表的顺序表示和实现 线性表的起始地址，称作线性表线性表的起始地址，称作线性表的的基地址基地址 特点特点：用一组：用一组 地址连续地址连续 的存储单的存储单元依次存放线性表中的数据元素元依次存放线性表中的数据元素用一组地址连续的存储单元依次存放线性表中的数据用一组地址连续的存储单元依次存放线性表中的数据元素元素 顺序表顺序表顺序表顺序表线性表：（线性表：（3,9,6,8,1,73,9,6,8,1,7）顺序存储顺序存储顺序存储顺

26、序存储第21页/共123页顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致（2）在访问线性表时，可以利用数学公式，快速地计算出任何一个数据元素的存储地址。第22页/共123页1 13 32 2i-1i-1i iC C以以以以“存储位置相邻存储位置相邻存储位置相邻存储位置相邻”表示有序对表示有序对表示有序对表示有序对a即：即：即：即：loc(aloc(ai i)=loc(a)=loc(ai-1i-1)+C)+C loc(a loc(ai i)=loc(a)=loc(a1 1)+(i-1)*C)+(i-1)*C其中其

27、中其中其中 C C 为每个数组元素的大小为每个数组元素的大小为每个数组元素的大小为每个数组元素的大小2.2 线性表的顺序表示和实现例：有一线性表（例：有一线性表（例：有一线性表（例：有一线性表（a,b,c,d,e,a,b,c,d,e,a,b,c,d,e,a,b,c,d,e,，x,y,zx,y,zx,y,zx,y,z），用），用），用），用顺序存储的方式存储该线性表，如已知线性表的顺序存储的方式存储该线性表，如已知线性表的顺序存储的方式存储该线性表，如已知线性表的顺序存储的方式存储该线性表，如已知线性表的基地址为基地址为基地址为基地址为200200200200，请问，请问，请问，请问h h h

28、h的存储地址？的存储地址？的存储地址？的存储地址？207207第23页/共123页p用C语言描述顺序映像的线性表#definedefine LIST_INIT_SIZELIST_INIT_SIZE 8080/线性表存储空间的初始分配量线性表存储空间的初始分配量#define#define LISTINCREMENTLISTINCREMENT 1010/线性表存储空间的分配增量线性表存储空间的分配增量LelemLength 3Listsize 8661583typedef structtypedef struct ElemType *elem;ElemType *elem;/存储空间基址存储空间

29、基址int length;int length;/当前长度当前长度int listsize;int listsize;/当前分配的存储容量当前分配的存储容量 SqListSqList;/俗称俗称 顺序表顺序表sequence list2.2 线性表的顺序表示和实现typedeftypedef?ElemType;ElemType;/根据实际需要定义根据实际需要定义第24页/共123页InitList_SqInitList_Sq (SqList&L)(SqList&L)DestroyList_SqDestroyList_Sq(SqList&L)(SqList&L)ListLength_SqList

30、Length_Sq(SqList L)(SqList L)IsEmptyIsEmpty(SqList L)(SqList L)GetElem_SqGetElem_Sq(SqList L,int pos,&e)(SqList L,int pos,&e)LocateElem_Sq LocateElem_Sq(SqList(SqList L,L,ElemType e)ElemType e)LocateElem_Sq LocateElem_Sq(SqList(SqList L,L,ElemType e,status compare(ElemType,ElemType e,status compare(

31、ElemType,ElemType)ElemType)ClearList_SqClearList_Sq(SqList&L)(SqList&L)ListInsert_Sq ListInsert_Sq(SqList&L,int pos,ElemType e)(SqList&L,int pos,ElemType e)ListDelete_Sq ListDelete_Sq(SqList&L,int pos,ElemType&e)(SqList&L,int pos,ElemType&e)线性表的基本操作：第25页/共123页思考如果你已经学习了C+语言，那么你认为这里讨论的顺序表类型和C+语言中的“类”

32、有何联系？抽象数据类型是程序设计的理论基础。如果以顺序存储结构来实现抽象数据类型线性表，则用面向对象的程序设计语言编程时就可以实现一个“顺序表类”。这里对顺序表类型的结构定义即为顺序表类私有的数据成员，所定义的基本操作即为顺序表类中的成员函数。如果用结构化语言，也很容易地用结构体表示抽线数据类型中的数据和结构，用定义在结构体上的一组函数来表示抽象数据类型的基本操作。第26页/共123页pp 顺序表的初始化Status Status InitList_Sq InitList_Sq(SqList&L)(SqList&L)/构造一个空的顺序表构造一个空的顺序表L L L.elem=(ElemType

33、*)malloc(L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemLIST_INIT_SIZE*sizeof(ElemType)Type););if(!L.elem)exit(OVERFLOW);if(!L.elem)exit(OVERFLOW);/存储分配失败存储分配失败 L.length=0;L.length=0;/长度为长度为0 0 L.listsize=LIST_INIT_SIZE;L.listsize=LIST_INIT_SIZE;/初始存储容量初始存储容量 return OK;return OK;/InitList_Sq/Ini

34、tList_SqLelemLength 0Listsize80顺序表操作第27页/共123页pp 顺序表的销毁void void DestroyList_Sq DestroyList_Sq(SqList&L)(SqList&L)if(L-item)free(L-item);/释放线性表占据的所有存储空间释放线性表占据的所有存储空间 /DestroyList_Sq/DestroyList_Sq顺序表操作第28页/共123页pp 顺序表的长度Status Status ListLength_Sq ListLength_Sq(SqList L)(SqList L)return(L.length);/

35、ListLength_Sq/ListLength_Sq顺序表操作第29页/共123页pp 顺序表是否为空Status Status IsEmpty_Sq IsEmpty_Sq(SqList L)(SqList L)if(L.length=0)return TRUE;else return FALSE;/IsEmpty_Sq/IsEmpty_Sq顺序表操作第30页/共123页pp 顺序表的数据获取Status GetElem_Sq(SqLIST L,int pos,EntryType&e)if(posL.length)return ERROR;/判断判断i i i i值是否合理，若不合理，返回值

36、是否合理，若不合理，返回ERRORERRORERRORERROR e=L.itempos-1;/数组中第数组中第i-1i-1i-1i-1的单元存储着线性表中第的单元存储着线性表中第i i i i个数据元素的内容个数据元素的内容 return OK;/GetElem_Sq/GetElem_Sq顺序表操作第31页/共123页StatusStatus LocateElem_SqLocateElem_Sq(SqList(SqList L,L,ElemType ElemType e)e)/*/*在顺序线性表在顺序线性表L L中查找第中查找第1 1个值与个值与e e相等的元素相等的元素的位序。若找到，则返

37、回其在的位序。若找到，则返回其在L L中的位序，否则中的位序，否则返回返回0 0。*/p=L.elem;p=L.elem;/指针指针p p从顺序表基地址开从顺序表基地址开始始 while(p-L.elem)L.length&while(p-L.elem)L.length&*p!=e*p!=e)p+;p+;if(*p=e)return(p-L.elem+1);if(*p=e)return(p-L.elem+1);else return 0;else return 0;/LocateElem_Sq/LocateElem_Sqpp 顺序表的定位(按值查找)V1.0(指针法)第32页/共123页p 顺

38、序表的定位(按值查找)V2.0(下标法)StatusStatus LocateElem_SqLocateElem_Sq (SqList L,ElemType x)(SqList L,ElemType x)int i=0 int i=0；for(;i L.length;i+)for(;i L.length;i+)if(if(L.elemi=xL.elemi=x )return i+1;)return i+1;if(i=L.length)return 0;if(i=L.length)return 0;注意：数组元素的两种标识方法：指针法和下标法注意：数组元素的两种标识方法：指针法和下标法注意：数组

39、元素的两种标识方法：指针法和下标法注意：数组元素的两种标识方法：指针法和下标法例：例：例：例：p=L.elemp=L.elemp=L.elemp=L.elem；*p p p p 和和和和L.elem0L.elem0L.elem0L.elem0指同一个元素指同一个元素指同一个元素指同一个元素p=p+1;*p p=p+1;*p p=p+1;*p p=p+1;*p 和和和和L.elem1L.elem1L.elem1L.elem1指同一个元素指同一个元素指同一个元素指同一个元素顺序表操作第33页/共123页StatusStatus LocateElem_SqLocateElem_Sq(SqList(S

40、qList L,ElemType e L,ElemType e,Status,Status compare(ElemType,ElemType)compare(ElemType,ElemType)int i=0 int i=0；for(;i L.length;i+)for(;ib;return ab;/*/*/*/Status Status LocateElem_SqLocateElem_Sq(SqList L,ElemType e(SqList L,ElemType e,Status compare(ElemType,ElemType),Status compare(ElemType,Ele

41、mType)for(;i L.length;i+)for(;ilength=0;/将线性表的长度置为将线性表的长度置为0 0 0 0 /ClearList_Sq/ClearList_Sq顺序表操作第36页/共123页顺序表的插入线性表的插入运算是指在表的i(1in+1个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an)变成长度为n+1的线性表 (a1，a i-1，x，ai，an)第37页/共123页返回第38页/共123页p 顺序表插入操作V1.0(下标法)插入元素时，注意线性表的插入元素时，注意线性表的插入元素时，注意线性表的插入元素时，注意线性表的逻辑结构逻辑结

42、构逻辑结构逻辑结构发生什么变化？发生什么变化？发生什么变化？发生什么变化？(a(a1 1,a,ai-1i-1,a,ai i,a,an n)改变为改变为改变为改变为 (a(a1 1,a,ai-1i-1,e,a,e,ai i,a,an n)pospos的合法值为的合法值为的合法值为的合法值为1posL.length+11posL.length+1 if(pos L.length+1)return ERROR;/位置是否合位置是否合位置是否合位置是否合法法法法 if(L.length=L.Listsize)exit(OVERFLOW);/空间是否够用空间是否够用空间是否够用空间是否够用 for(j=

43、L.length-1;j=pos-1;j-)for(j=L.length-1;j=pos-1;j-)/插入位置后的元素右移插入位置后的元素右移插入位置后的元素右移插入位置后的元素右移 L.elemj+1=L.elemj;L.elemj+1=L.elemj;L.elempos-1=e;/插入插入插入插入e e e e L.length+;/表长增表长增表长增表长增1 1 1 1 return OK;/ListInsert_Sq/ListInsert_Sq StatusStatus ListInsert_Sq ListInsert_Sq(SqList&L,int pos,ElemType e)(S

44、qList&L,int pos,ElemType e)/在顺序表在顺序表在顺序表在顺序表L L L L中中中中pospospospos位置插入位置插入位置插入位置插入e e e e第39页/共123页Status Status ListInsert_Sq ListInsert_Sq(SqList&L,int pos,ElemType e)(SqList&L,int pos,ElemType e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L L L中中中中pospospospos位置插入位置插入位置插入位置插入e e e e if(posL.length+1)return ERROR

45、if(posL.length+1)return ERROR;/位置是否合法位置是否合法位置是否合法位置是否合法 if(L.length=L.listsize)exit(OVERFLOW);if(L.length=L.listsize)exit(OVERFLOW);/空间是否够用空间是否够用空间是否够用空间是否够用q=&(L.elempos-1);q=&(L.elempos-1);/q/q指示插入位置，注意指示插入位置，注意指示插入位置，注意指示插入位置，注意pospos值和下标差值和下标差值和下标差值和下标差1 1for(p=&(L.elemL.length-1);p=q;p-)for(p=&

46、(L.elemL.length-1);p=q;p-)*(p+1)=*p;*(p+1)=*p;/插入位置后元素右移插入位置后元素右移插入位置后元素右移插入位置后元素右移 *q=e;q=e;/插入插入插入插入e e L.length+L.length+;/表长增表长增表长增表长增1 1 return OK;return OK;/ListInsert_Sq/ListInsert_Sq p顺序表插入操作V2.0(指针法)第40页/共123页if(L.length=L.listsize)exit(OVERFLOWOVERFLOW);if(L.length=L.listsize)newbase=(Elem

47、Type*)realloc (L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);/*分配一个大小为(L.listsize+LISTINCREMENT)*sizeof(ElemType)的存储空间，将原表元素填充到新空间中，把首地址赋值给newbase*/if(!newbase)exit(OVERFLOW);/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量插入时检测到空间不够时可以用插入时检测到空间不够时可以用插入时检测到空间不够时可以用插入时检测到空间不够时可以用rea

48、llocrealloc申请增加空间申请增加空间申请增加空间申请增加空间第41页/共123页 现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）不仅依赖于表的长度，而且还与插入位置有关。当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度动画第42页/共123页在长度为n的线性表中第i个位置上插入一个

49、结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。故 Eis(n)=pi(n-i+1)不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)=(n-i+1)/(n+1)=n/2也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。顺序表操作第43页/共123页顺序表的删除线性表的删除运算是指将

50、表的第i(1in)结点删除，使长度为n的线性表：(a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表 (a1，a i-1，a i+1，an)第44页/共123页返回第45页/共123页p 顺序表删除操作V1.0(指针法)：删除元素时，注意线性表的逻辑结构发生什么变化？删除元素时，注意线性表的逻辑结构发生什么变化？删除元素时，注意线性表的逻辑结构发生什么变化？删除元素时，注意线性表的逻辑结构发生什么变化？(a a1 1,a ai i-1-1,a ai i,a ai i+1+1,a an n)变为变为(a a1 1,a ai i-1-1,a ai i+1+1,a an n)Stat