第二章+线性表.ppt

《第二章+线性表.ppt》由会员分享，可在线阅读，更多相关《第二章+线性表.ppt（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 线性表的应用线性表的应用线性表的应用线性表的应用2.1线性表的类型定义线性表的类型定义线性结构的线性结构的基本特征基本特征:n n 集合中必存在唯一的一个集合中必存在唯一的一个集合中必存在唯一的一个集

2、合中必存在唯一的一个“第一元素第一元素第一元素第一元素”；n n 集合中必存在唯一的一个集合中必存在唯一的一个集合中必存在唯一的一个集合中必存在唯一的一个“最后元素最后元素最后元素最后元素”；n n 除最后元素之外，均有唯一的除最后元素之外，均有唯一的除最后元素之外，均有唯一的除最后元素之外，均有唯一的后继后继后继后继；n n 除第一元素之外，均有唯一的除第一元素之外，均有唯一的除第一元素之外，均有唯一的除第一元素之外，均有唯一的前驱前驱前驱前驱。从逻辑上：数据之间的关系可以分从逻辑上：数据之间的关系可以分从逻辑上：数据之间的关系可以分从逻辑上：数据之间的关系可以分4 4类类类类：线性结构线性

3、结构线性结构线性结构,树型结构树型结构树型结构树型结构,图状结构图状结构图状结构图状结构,集合集合集合集合n n线性表最简单的一种线性结构线性表最简单的一种线性结构线性表最简单的一种线性结构线性表最简单的一种线性结构n n一个线性表是一个线性表是一个线性表是一个线性表是n n个数据元素的有限序列个数据元素的有限序列个数据元素的有限序列个数据元素的有限序列n n比如比如比如比如 ABZABZ英文字母表英文字母表英文字母表英文字母表n n比如比如比如比如001高等数学华罗庚S01002线性代数銮汝书L01003高等数学郑杭生 S01004离散数学耿素云S02线性表中每个数据元素的具体含义，各不相同

4、，数据元素是基线性表中每个数据元素的具体含义，各不相同，数据元素是基线性表中每个数据元素的具体含义，各不相同，数据元素是基线性表中每个数据元素的具体含义，各不相同，数据元素是基本单位，一个数据元素由若干个数据项组成本单位，一个数据元素由若干个数据项组成本单位，一个数据元素由若干个数据项组成本单位，一个数据元素由若干个数据项组成2.1线性表的类型定义线性表的类型定义n n线性表记为线性表记为线性表记为线性表记为（a a1 1,a ai i-1-1,a ai i,a ai i+1+1,a an n）n na ai-1i-1 在在在在a ai i 之前之前之前之前 称称称称 a ai i-1-1是是

5、是是 a ai i 的的的的 前驱前驱前驱前驱n na ai i 在在在在 a ai i-1-1之后之后之后之后 称称称称 a ai i 是是是是 a ai i-1-1的的的的 后继后继后继后继n n序列中数据元素的个数序列中数据元素的个数序列中数据元素的个数序列中数据元素的个数 n n 定义为线性表的表长定义为线性表的表长定义为线性表的表长定义为线性表的表长 n n称称称称 i i 为为为为a ai i在线性表中的位序在线性表中的位序在线性表中的位序在线性表中的位序 n n i i=2=2，,n nn n线性表的元素个数称为的线性表的元素个数称为的线性表的元素个数称为的线性表的元素个数称为的

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

7、操作基本操作：InitListInitList(&L)(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表操作结果：构造一个空的线性表操作结果：构造一个空的线性表L L。DestroyListDestroyList(&L)(&L)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在。已存在。已存在。已存在。操作结果：销毁线性表操作结果：销毁线性表操作结果：销毁线性表操作结果：销毁线性表L L，将原表中各结点所，将原表中各结点所，将原表中各结点所，将原表中各结点所占的内存空间释放。占的内存空间释放。占的内存空间释放。占的内存空间释放。引用型操作ListEmpt

8、yListEmpty(L)(L)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在。已存在。已存在。已存在。操作结果：若操作结果：若操作结果：若操作结果：若L L为空表，则返回为空表，则返回为空表，则返回为空表，则返回TRUETRUE，否则，否则，否则，否则FALSEFALSE。ListLengthListLength(L)(L)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在。已存在。已存在。已存在。操作结果：返回操作结果：返回操作结果：返回操作结果：返回L L中元素个数中元素个数中元素个数中元素个数。PriorElemPriorElem

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

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

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

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

13、，已存在，已存在，1iLengthList(L)1iLengthList(L)操作结果：用操作结果：用操作结果：用操作结果：用e e返回返回返回返回L L中第中第中第中第i i个元素的值。个元素的值。个元素的值。个元素的值。PutElemPutElem(&L,i,e)(&L,i,e)初始条件：线性表初始条件：线性表初始条件：线性表初始条件：线性表L L已存在，已存在，已存在，已存在，1iLengthList(L)1iLengthList(L)操作结果：操作结果：操作结果：操作结果：L L中第中第中第中第i i个元素赋个元素赋个元素赋个元素赋e e的值。的值。的值。的值。ListDelete(&

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

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

16、重置为空表。加工型操作 算法2.1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。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)ListInsert(la，+la_en，e)时间复杂度O(ListLength(La)ListLength(Lb)算法2.2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表L

17、C，且LC中的元素仍按值非递减有序排列。此问题的算法如下：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-len)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

18、(lc，+k，ai);while(j=lb-len)GetElem(lb，j+，bj);ListInsert(lc，+k，bj);时间复杂度O(ListLength(La)+ListLength(Lb)思考1已知一个已知一个“非纯集合非纯集合”B，试构造一个集合，试构造一个集合A，使，使A中只包含中只包含B中所有值各不相同的数据元素。中所有值各不相同的数据元素。分析分析:将每个从将每个从B中取出的元素和已经加入到集合中取出的元素和已经加入到集合A中中的元素相比较。的元素相比较。void purge(List&LA,List LB)/构造线性表LA，使其只包含LB中所有值不相同的数据元素,算法不

19、改变线性表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()ListInsert(LA,+La_len,e);/for/purge思考2判别两个集合是否相等。判别两个集合是否相等。分析分析:首先判别两者的表长是否相等；在表长首先判别两者的表长是否相等；在表长相等的前提下

20、，对于一个表中的所有元素，是相等的前提下，对于一个表中的所有元素，是否都能在另一个表中找到和它相等的元素否都能在另一个表中找到和它相等的元素.如果如果集合集合中的元素中的元素不能保证都相异不能保证都相异，还应反过来判别还应反过来判别LB中每个元素都能在中每个元素都能在LA中中找到相同者。找到相同者。2.1 2.1 线性表的类型定义线性表的类型定义 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.4 2.4 线性表的应用线性表的应用2.2线性表的顺序表示和实现线性表的顺序表示和实现n n线性表的起始地址，称作线性表的

21、线性表的起始地址，称作线性表的线性表的起始地址，称作线性表的线性表的起始地址，称作线性表的基地址基地址基地址基地址n n特点特点特点特点：用一组：用一组：用一组：用一组 地址连续地址连续地址连续地址连续 的存储单的存储单的存储单的存储单元依次存放线性表中的数据元素元依次存放线性表中的数据元素元依次存放线性表中的数据元素元依次存放线性表中的数据元素以数组的方式存储线性表中的所有数据元素以数组的方式存储线性表中的所有数据元素以数组的方式存储线性表中的所有数据元素以数组的方式存储线性表中的所有数据元素顺序表顺序表顺序表顺序表线性表：（线性表：（线性表：（线性表：（3,9,6,8,1,73,9,6,8

22、,1,7）顺序存储顺序存储顺序存储顺序存储1 13 32 2i-1i-1i iC C以以以以“存储位置相邻存储位置相邻存储位置相邻存储位置相邻”表示有序对表示有序对表示有序对表示有序对a即：即：即：即：loc(aloc(ai i)=loc(a)=loc(ai-1i-1)+C)+C loc(aloc(ai i)=loc(a)=loc(a1 1)+(i-1)*C)+(i-1)*C其中其中其中其中 C C 为每个数组元素的大小为每个数组元素的大小为每个数组元素的大小为每个数组元素的大小2.2线性表的顺序表示和实现线性表的顺序表示和实现例：有一线性表（例：有一线性表（例：有一线性表（例：有一线性表（a

23、,b,c,d,ea,b,c,d,ea,b,c,d,ea,b,c,d,e,，x,y,zx,y,zx,y,zx,y,z），用），用），用），用顺序存储的方式存储该线性表，如已知线性表的顺序存储的方式存储该线性表，如已知线性表的顺序存储的方式存储该线性表，如已知线性表的顺序存储的方式存储该线性表，如已知线性表的基地址为基地址为基地址为基地址为200200200200，请问，请问，请问，请问h h h h的存储地址？的存储地址？的存储地址？的存储地址？207207顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致（2）在访

24、问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。p用用C语言描述顺序映像的线性表语言描述顺序映像的线性表#definedefine LIST_INIT_SIZELIST_INIT_SIZE 8080/线性表存储空间的初始分配量线性表存储空间的初始分配量#define#define LISTINCREMENTLISTINCREMENT 1010/线性表存储空间的分配增量线性表存储空间的分配增量LelemLength 3Listsize 8661583typedeftypedef structstruct ElemTypeElemType *elemelem;/存储

25、空间基址存储空间基址intint length;length;/当前长度当前长度intint listsizelistsize;/当前分配的存储容当前分配的存储容量量 SqListSqList;/俗称俗称 顺序表顺序表sequence list2.2线性表的顺序表示和实现线性表的顺序表示和实现typedeftypedef?ElemTypeElemType;/根据实际需要定义根据实际需要定义InitList_SqInitList_Sq (SqListSqList&L)&L)DestroyList_SqDestroyList_Sq(SqList(SqList&L)&L)ListLength_SqL

26、istLength_Sq(SqList(SqList L)L)IsEmptyIsEmpty(SqList(SqList L)L)GetElem_SqGetElem_Sq(SqList(SqList L,L,intint pos,&e)pos,&e)LocateElem_SqLocateElem_Sq (SqListSqList L,L,ElemTypeElemType e)e)LocateElem_SqLocateElem_Sq (SqListSqList L,L,ElemTypeElemType e,status e,status compare(ElemTypecompare(ElemTy

27、pe,ElemTypeElemType)ClearList_SqClearList_Sq(SqList(SqList&L)&L)ListInsert_SqListInsert_Sq (SqListSqList&L,&L,intint pos,pos,ElemTypeElemType e)e)ListDelete_SqListDelete_Sq (SqListSqList&L,&L,intint pos,pos,ElemTypeElemType&e)&e)线性表的基本操作：线性表的基本操作：pp顺序表的初始化顺序表的初始化Status Status InitList_SqInitList_Sq

28、(SqListSqList&L)&L)/构造一个空的顺序表构造一个空的顺序表构造一个空的顺序表构造一个空的顺序表L L L.elemL.elem=(=(ElemTypeElemType*)*)malloc(malloc(LIST_INIT_SIZELIST_INIT_SIZE*sizeof(ElemTypesizeof(ElemType););if(!if(!L.elemL.elem)exit(OVERFLOWexit(OVERFLOW););/存储分配失败存储分配失败存储分配失败存储分配失败 L.lengthL.length=0;=0;/长度为长度为长度为长度为0 0 L.listsizeL

29、.listsize=LIST_INIT_SIZE;=LIST_INIT_SIZE;/初始存储容量初始存储容量初始存储容量初始存储容量 return OK;return OK;/InitList_SqInitList_SqLelemLength 0Listsize80顺序表操作pp顺序表的销毁顺序表的销毁void DestroyList_Sq(SqList&L)if(L-item)free(L-item);/释放线性表占据的所有存储空间释放线性表占据的所有存储空间/DestroyList_Sq顺序表操作pp顺序表的长度顺序表的长度Status ListLength_Sq(SqList L)ret

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

31、第数组中第i-1i-1i-1i-1的单元存储着线性表中第的单元存储着线性表中第的单元存储着线性表中第的单元存储着线性表中第i i i i个数据元素的内容个数据元素的内容个数据元素的内容个数据元素的内容 return OK;/GetElem_Sq顺序表操作StatusStatus LocateElem_SqLocateElem_Sq(SqList(SqList L,L,ElemTypeElemType e)e)/*/*在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L中查找第中查找第中查找第中查找第1 1个值与个值与个值与个值与e e相等的元素的相等的元素的相等的元素的相等的元素的位序。若找

32、到，则返回其在位序。若找到，则返回其在位序。若找到，则返回其在位序。若找到，则返回其在L L中的位序，否则返回中的位序，否则返回中的位序，否则返回中的位序，否则返回0 0。*/p=p=L.elemL.elem;/指针指针指针指针p p从顺序表基地址开始从顺序表基地址开始从顺序表基地址开始从顺序表基地址开始 while(while(p-L.elemp-L.elem)L.lengthL.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;/

33、LocateElem_SqLocateElem_Sqpp顺序表的定位顺序表的定位(按值查找按值查找)V1.0(指针指针法法)p 顺序表的定位顺序表的定位(按值查找按值查找)V2.0(下标下标法法)StatusStatus LocateElem_SqLocateElem_Sq (SqListSqList L,L,ElemTypeElemType x)x)intint i=0 i=0；for(;i for(;i L.lengthL.length;i+);i+)if(if(L.elemiL.elemi=x=x )return i+1;)return i+1;if(i=if(i=L.lengthL.l

34、ength)return 0;)return 0;注意：数组元素的两种标识方法：指针法和下标法注意：数组元素的两种标识方法：指针法和下标法注意：数组元素的两种标识方法：指针法和下标法注意：数组元素的两种标识方法：指针法和下标法例：例：例：例：p=p=p=p=L.elemL.elemL.elemL.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指同一个元素指同一个元素指

35、同一个元素指同一个元素顺序表操作StatusStatus LocateElem_SqLocateElem_Sq(SqList(SqList L,L,ElemTypeElemType e,Status e,Status compare(compare(ElemTypeElemType,ElemTypeElemType)intint i=0 i=0；for(;i for(;ib;return ab;/*/*/Status Status LocateElem_SqLocateElem_Sq(SqList(SqList L,L,ElemTypeElemType e,Status e,Status co

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

37、发生什么变化？发生什么变化？发生什么变化？发生什么变化？(a(a1 1,a,ai-1i-1,a,ai i,a,an n)改变为改变为改变为改变为(a(a1 1,a,ai-1i-1,e,e,a 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=L.length-1

38、;j=pos-1;j-)for(j=L.length-1;j=pos-1;j-)/插入位置后的元素右移插入位置后的元素右移插入位置后的元素右移插入位置后的元素右移 L.elemj+1=L.elemj+1=L.elemjL.elemj;L.elempos-1=e;/插入插入插入插入e e e e L.length+;/表长增表长增表长增表长增1 1 1 1 return OK;/ListInsert_SqListInsert_Sq StatusStatus ListInsert_SqListInsert_Sq(SqListSqList&L,&L,intint pos,pos,ElemTypeEl

39、emType e)e)/在顺序表在顺序表在顺序表在顺序表L L L L中中中中pospospospos位置插入位置插入位置插入位置插入e e e eStatus Status ListInsert_SqListInsert_Sq (SqListSqList&L,&L,intint pos,pos,ElemTypeElemType e)e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L L L中中中中pospospospos位置插入位置插入位置插入位置插入e e e e if(posL.length+1)return ERRORif(posL.length+1)return ERROR

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

41、)=*p;*(p+1)=*p;/插入位置后元素右移插入位置后元素右移插入位置后元素右移插入位置后元素右移 *q=e;q=e;/插入插入插入插入e e L.lengthL.length+;/表长增表长增表长增表长增1 1 return OK;return OK;/ListInsert_SqListInsert_Sq p顺序表插入操作顺序表插入操作V2.0(指针法指针法)if(L.length=L.listsize)exit(OVERFLOWOVERFLOW);if(L.length=L.listsize)newbase=(ElemType*)realloc (L.elem,(L.listsize

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

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

44、点，令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)。顺序表操作顺序表的删除线性表的删除运算是指将表的第i(1in)结点

45、删除，使长度为n的线性表：(a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表 (a1，a i-1，a i+1，an)返回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)Status Status ListDelete_

46、SqListDelete_Sq(SqList(SqList&L,&L,intint pos,pos,ElemTypeElemType&e)&e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L中删除第中删除第中删除第中删除第pospos个元素，并用个元素，并用个元素，并用个元素，并用e e返回其值。返回其值。返回其值。返回其值。if(posif(posL.lengthL.length)return ERROR;)return ERROR;/删除位置不合法删除位置不合法删除位置不合法删除位置不合法 p=&L.elempos-1;p=&L.elempos-1;/p/p为被删除元素的地址为被

47、删除元素的地址为被删除元素的地址为被删除元素的地址 e=*p;e=*p;/被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给e e q=L.elem+L.length-1;q=L.elem+L.length-1;/表尾元素的地址表尾元素的地址表尾元素的地址表尾元素的地址 for(+p;p=q;p+)for(+p;p=q;p+)*(p-1)=*p;*(p-1)=*p;/被删除位置后元素上移被删除位置后元素上移被删除位置后元素上移被删除位置后元素上移 L.lengthL.length-;-;/表长减表长减表长减表长减1 1 return OK;return OK;/ListD

48、elete_SqListDelete_Sqpospos的合法值为的合法值为的合法值为的合法值为1posL.length1posL.lengthp顺序表删除操作顺序表删除操作V2.0(下标法下标法)Status Status ListDelete_SqListDelete_Sq(SqList(SqList&L,&L,intint pos,pos,ElemTypeElemType&e)&e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L中删除第中删除第中删除第中删除第pospos个元素，并用个元素，并用个元素，并用个元素，并用e e返回其值。返回其值。返回其值。返回其值。if(posL.

49、length)return ERROR;/删除位置不合删除位置不合删除位置不合删除位置不合法法法法 e=L.elempos-1 /被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给e e for(j=pos;j next=NULL 三、带头结点的单链表L L2 28 85 59 97 7L L为什么要设头结点？为什么要设头结点？为什么要设头结点？为什么要设头结点？可不可以不设头结点可不可以不设头结点可不可以不设头结点可不可以不设头结点n答：头结点即在链表的首元素结点之前附设的一个结点，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元素结点进行统一处理，免去

50、对链表第一个结点的特殊处理，编程更方便。当然，根据需要有时候也可以不设头节点。讨论讨论讨论讨论.在链表中设置在链表中设置在链表中设置在链表中设置头结点头结点头结点头结点有什么好处有什么好处有什么好处有什么好处？可不可以不设头结点？Status InitList_L(LinkList&L)Status DestoryList_L(LinkList&L)Status ListLength_L(LinkList L)Status IsEmpty(LinkList L)Status GetElem_L(LinkList L,int pos,ElemType&e)Status LocateElem_L(