数据结构第二章 线性表.ppt

1、第二章第二章 线性表线性表20232023年年5 5月月5 5日星期五日星期五 线性结构的线性结构的基本特征基本特征为为:1 1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2 2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素”；3 3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4 4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。线性结构线性结构 是一个数据元素的是一个数据元素的有序（次序）集合。有序（次序）集合。线性表线性表是一种最简单的线性结构线性结构2.1 2.1 线性表的类型定义线性表的类型定义2.3 2.3

2、线性表类型的链式表示和实现线性表类型的链式表示和实现2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加2.2 2.2 线性表类型的线性表类型的顺序表示和顺序表示和实现实现本章主要内容：本章主要内容：二、线性表的抽象数据类型表示二、线性表的抽象数据类型表示(教材教材P P1919)ADT List ADT List数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：D=ai|aiElemSet,i=1,2,n,n0R=|ai 1,ai D,i=2,nInitList(&L);/建建空表，初始化空表，初始化DestoryList(&L);/撤销表，释放内存撤销表，释放内存int

3、LengthList(L);/求表中元素个数，即表长求表中元素个数，即表长PriorElem(L,cur_e,&pre_e);/求求当前元素当前元素cur_e的前驱的前驱NextElem(L,cur_e,&next_e);/求当前求当前元素元素cur_e的后继的后继ListInsertBefore(&L,i,e);/在在第第i个元素之前插入新的元素个元素之前插入新的元素eListDelete(&L,i,&e);/删除第删除第i个元素并返回此元素个元素并返回此元素2.1 2.1 线性表的类型定义线性表的类型定义抽象数据类型线性表线性表的定义细解：ADT List 数据对象数据对象：D ai|ai

4、 ElemSet,i=1,2,.,n,n0 称 n n 为线性表的表长表长;n=0n=0 时的线性表为空表空表。数据关系数据关系：R1|ai-1,aiD,i=2,.,n 2.1 线性表的类型定义线性表的类型定义 简言之，一个线性表是n个数据元素(a1，a2,，ai，an)的有限序列。称 i 为 ai 在线性表中的位序位序。基本操作：基本操作：结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT ADT List InitListInitList(&L)(&L)操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操作结构销毁操作结构销毁操

5、作DestroyListDestroyList(&L)(&L)初始条件：初始条件：操作结果：操作结果：线性表 L 已存在。销毁线性表 L。ListEmptyListEmpty(L)(L)ListLengthListLength(L)(L)PriorElemPriorElem(L,cur_e,&pre_e)(L,cur_e,&pre_e)NextElemNextElem(L,cur_e,&next_e)(L,cur_e,&next_e)GetElemGetElem(L,i,&e)(L,i,&e)LocateElemLocateElem(L,e,compare()(L,e,compare()Lis

6、tTraverse(LListTraverse(L,visit(),visit()引用型操作引用型操作:ListEmptyListEmpty(L)(L)（线性表判空）初始条件：操作结果：线性表L L已存在。若L L为空表，则返回TRUE，否则FALSE。ListLengthListLength(L)(L)（求线性表的长度）初始条件：操作结果：线性表L L已存在。返回L L中元素个数。PriorElemPriorElem(L,cur_e,&pre_e)(L,cur_e,&pre_e)（求数据元素的前驱）初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回

7、它的前驱，否则操作失败，pre_e无定义。NextElemNextElem(L,cur_e,&next_e)(L,cur_e,&next_e)（求数据元素的后继）初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。GetElemGetElem(L,i,&e)(L,i,&e)（求线性表中某个数据元素）初始条件：操作结果：线性表L L已存在，且 1iLengthList(L)1iLengthList(L)。用 e 返回L L中第 i 个元素的值。LocateElemLocateElem(L,e,compare(

8、)(L,e,compare()初始条件：操作结果：线性表L L已存在，e为给定值，compare()是元素判定函数。返回L L中第中第1 1个个与e满足满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）ListTraverse(LListTraverse(L,visit(),visit()初始条件：操作结果：线性表L L已存在，Visit()为某个访问函数。依次依次对L L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）加工型操作加工型操作 ClearListClearList(&L)(&L)PutElemPutElem(

9、&L,i,&e)(&L,i,&e)ListInsertListInsert(&L,i,e)(&L,i,e)ListDelete(&LListDelete(&L,i,&e),i,&e)ClearListClearList(&L)(&L)初始条件：操作结果：线性表L L已存在。将L L重置为空表。（线性表置空）PutElemPutElem(&L,i,&e)(&L,i,&e)初始条件：操作结果：线性表L L已存在，且 1iLengthList(L)1iLengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）ListInsertListInsert(&L,i,e)(&L,i,e)初

10、始条件：操作结果：线性表L L已存在，且 1iLengthList(L)+1 1iLengthList(L)+1。在L L的第i i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）ListDelete(&LListDelete(&L,i,&e),i,&e)初始条件：操作结果：线性表L已存在且非空，1iLengthList(L)1iLengthList(L)。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）例例 2-1:2-1:假设假设:有两个集合有两个集合 A A 和和 B B 分别用两个线性分别用两个线性表表 LA LA 和和 LB LB 表示，即：线性表中的数

11、据元素即为表示，即：线性表中的数据元素即为集合中的成员。集合中的成员。现要求一个新的集合现要求一个新的集合A AABAB。要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB LB 中中而不存在于线性表不存在于线性表 LA LA 中中的数据元素插入到线性表插入到线性表 LALA 中中去。上述问题可演绎为：1 1从线性表LB中依次察看每个数据元素;2 2依值在线性表LA中进行查访;3 3若不存在，则插入之。GetElem(LBGetElem(LB,i)e,i)e LocateElem(LALocateElem(LA,e,equal(),e,equal()ListInsert(

12、LAListInsert(LA,n+1,e),n+1,e)操作步骤：操作步骤：GetElem(Lb,i,e);/取取LbLb中第中第i i个数据元素个数据元素赋给赋给e e if if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/LaLa中不存在和中不存在和 e e 相同的数据元素，则插入相同的数据元素，则插入之之voidvoid union(List&La,List Lb)La_len=ListLength(La);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb);forfor(i=1;i=Lb_len;i+)

13、/union算法：算法：2.12.1例例 2-22-2：已知一个非纯集合已知一个非纯集合 B B，试构造一个纯集合，试构造一个纯集合 A A，使使 A A中只包含中只包含 B B 中所有值各不相同的数据元素。中所有值各不相同的数据元素。集合集合 B B集合集合 A A 从集合从集合 B B 取出物件放入集合取出物件放入集合 A A，要求集合，要求集合A A中中同同样物件不能有两件以上样物件不能有两件以上因此，因此，算法的策略应该和例算法的策略应该和例2-12-1相同相同void union(List&La,List Lb)void union(List&La,List Lb)La_len La

14、_len=ListLength(LaListLength(La);Lb_len;Lb_len=ListLength(LbListLength(Lb);/union/union GetElem(Lb,i,e);/取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之forfor(i=1;i=Lb_len;i+)InitList(LaInitList(La););/构造(空的)线性表LA 若线性表中的数据元素相互之

15、间可以比较比较，并且数据元素在线性表中依值非递减或非递增有序依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表有序表(Ordered List)(Ordered List)。试改变结构，以有序表有序表表示集合。例例2-32-3：已知线性表已知线性表LA LA 和和LBLB中数据元素按值非递减有中数据元素按值非递减有序排列，现要求将序排列，现要求将LA LA 和和LBLB归并为一个新的线性表归并为一个新的线性表LCLC，且且LCLC中的数据元素仍按值非递减有序排列。中的数据元素仍按值非递减有序排列。例如：例如：LA=LA=（3 3，5 5，8

16、8，1111），），LB=LB=（2 2，6 6，8 8，9 9，1111，1515，2020），则），则 LC=LC=（2 2，3 3，5 5，6 6，8 8，8 8，9 9，1111，1111，1515，2020）对集合对集合 B B 而言，值相同的数据元素必定相邻；而言，值相同的数据元素必定相邻；对集合对集合 A A 而言，数据元素依值从小至大的顺序插入。而言，数据元素依值从小至大的顺序插入。因此，数据结构改变了，解决问题的策略也相应数据结构改变了，解决问题的策略也相应要改变。要改变。voidvoid MergeList(List La,List Lb,List&Lc)/已知线性表已知线

17、性表La La 和和LbLb中数据元素按值非递减有序排列，归并中数据元素按值非递减有序排列，归并La La 和和LbLb得到新的线性表得到新的线性表LcLc，LcLc中的数据元素也按值非递减排列。中的数据元素也按值非递减排列。whilewhile(i=La_len)&(j=Lb_len)InitList(LcInitList(Lc);/);/构造空的线性表构造空的线性表 LcLci=j=1;k=0;i=j=1;k=0;La_len=ListLength(LaLa_len=ListLength(La););Lb_len=ListLength(LbLb_len=ListLength(Lb););/

18、La 和 Lb 均非空，i=j=1,k=0 GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)/将 ai 插入到 Lc 中 ListInsert(Lc,+k,ai);+i;else /将 bj 插入到 Lc 中 ListInsert(Lc,+k,bj);+j;/接下页接下页/whilewhile(i=La_len)/当La不空时 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插入插入 La La 表中剩余元素表中剩余元素 whilewhile(j=Lb_len)/当Lb不空时 GetElem(Lb,j+,bj);ListIn

19、sert(Lc,+k,bj);/插入插入 Lb Lb 表中剩余元素表中剩余元素 /merge_list算法：算法：2.22.2一、顺序表的表示一、顺序表的表示顺序存储定义：顺序存储定义：把逻辑上相邻的元素存储在物理把逻辑上相邻的元素存储在物理 位置上相邻的存储单元中。位置上相邻的存储单元中。采用顺序存储结构存储的线性表采用顺序存储结构存储的线性表简言之：简言之：逻辑相邻，物理也相邻逻辑相邻，物理也相邻顺序存储方法：顺序存储方法：用一组用一组地址连续地址连续的存储单元依次的存储单元依次 存放线性表的数据元素。存放线性表的数据元素。2.2 线性表的顺序表示和实现已知：已知：L=（a1,a2,ai-

20、1,ai,ai+1,an）bb+1b+2b+(maxlen-1)a1a2ai-1aiai+1anb+(i-1)占占k个存储单元个存储单元b+(i-1)*kLoc(ai+1)Loc(ai)存储单元的个数存储单元的个数+k=Loc(ai)loc(a1)=+(i-1)*k Loc(a1)表示线性表第表示线性表第1个元素个元素a1的存储位置，即基地址的存储位置，即基地址 若每个元素占用若每个元素占用k个存储单元个存储单元2.2 线性表的顺序表示和实现基地址基地址基地址基地址线性表顺序存储结构的特点线性表顺序存储结构的特点1、逻辑上相邻的物理元素，其物理位置上也相邻 2、若已知线性表中第1个元素的存储位

21、置，则线性表中任意 一个元素的位置都可由公式计算得出。即，线性表的顺序存储结构是一种随机存取的存储结构。例：例：一个一维数组一个一维数组M，下标范围是，下标范围是0到到9，每个数组元素用，每个数组元素用相邻的相邻的5个字节存储。存储器按字节编址，设存储数组元素个字节存储。存储器按字节编址，设存储数组元素M0的第一个字节的地址是的第一个字节的地址是98，则，则M3的第一个字节的地的第一个字节的地址是址是 。1132.2 线性表的顺序表示和实现先为顺序表空间设定一个初始分配量，一旦因插入元素而空先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。间不

22、足时，可为顺序表增加一个固定长度的空间增量。线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构#define LIST_INIT_SIZE 100/存储空间的初始分配量存储空间的初始分配量#define LISTINCREMENT 10/存储空间的分配增量存储空间的分配增量Typedef struct ElemType*elem;/表基址表基址(用指针用指针*elemelem表示表示）int length;/表长度（表长度（表中有多少个元素表中有多少个元素）int listsize;/当前分配的表尺寸（当前分配的表尺寸（字节单位字节单位）SqList;存储结构描述如下存储结构描述如下（见

23、教材（见教材P22P22）：2.2 线性表的顺序表示和实现sizeof(x)的意思是：的意思是：计算变量计算变量x的长度的长度(字节数字节数)malloc(m)函数的意思是：新开一片函数的意思是：新开一片大小为大小为m字节的连续空间，并把该字节的连续空间，并把该区首址作为函数值。区首址作为函数值。Status InitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序 L.

24、length=0;/暂无元素放入，空表暂无元素放入，空表 L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始分配量初始分配量 Return OK;/InitList_Sq/InitList_Sq动态创建一个空顺序表的算法：动态创建一个空顺序表的算法：（见教材（见教材P23）2.2 线性表的顺序表示和实现线性表的基本操作在顺序表中的实现：线性表的基本操作在顺序表中的实现：InitList(&LInitList(&L)/)/结构初始化结构初始化LocateElem(LLocateElem(L,e,compare()/,e,compare()/查找查找ListInsert(&L

25、ListInsert(&L,i,e)/,i,e)/插入元素插入元素ListDelete(&LListDelete(&L,i)/,i)/删除元素删除元素StatusStatus InitList_Sq(SqList&L)/构造一个空的线性表 /InitList_Sq算法时间复杂度时间复杂度：O(1)O(1)L.elem=(ElemType*)mallocmalloc (LIST_ INIT_SIZE sizeofsizeof (ElemType);ifif(!L.elem)exitexit(OVERFLOW);/存储分配失败存储分配失败L.length=0;/空表长度为空表长度为0 0L.lis

26、tsizeL.listsize=LIST_INIT_SIZE /=LIST_INIT_SIZE /初始存储容量初始存储容量returnreturn OK;算法：算法：2.32.3线性表操作：ListInsert(&LListInsert(&L,i,e),i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生发生什么变化什么变化？(a1,a ai-1i-1,a,ai i,an)改变为(a1,a ai-1i-1,e,a,e,ai i,an)a a,a1 a2 ai-1 ai anA1 a2 ai-1 ai e ean表的长度增加 Status ListInsert_Sq(SqL

27、ist&L,int i,ElemTypeStatus ListInsert_Sq(SqList&L,int i,ElemType e)e)/在顺序表在顺序表L L的第的第 i i 个元素之前插入新的元素个元素之前插入新的元素e,e,/i /i 的合法范围为的合法范围为 1iL.length+11iL.length+1 /ListInsert_Sq /ListInsert_Sq q=&(L.elemi-1);/q/q 指示插入位置指示插入位置forfor(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移插入位置及之后的元素右移*q=e;/插

28、入插入e e+L.length;/表长增表长增1 1return return OK;/见下页见下页/元素右移元素右移ifif(L.length=L.listsize)/当前存储空间已满，增加分配 newbase=(ElemType newbase=(ElemType*)realloc(L.elem)realloc(L.elem,(L.listsize+LISTINCREMENT)(L.listsize+LISTINCREMENT)*sizeof(ElemTypesizeof(ElemType););if if(!newbase)exitexit(OVERFLOW);/存储分配失败 L.ele

29、m=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量 ifif(i L.length+1)returnreturn ERROR;/插入位置不合法算法：算法：2.42.4算法时间复杂度算法时间复杂度为为:O(ListLength(LO(ListLength(L)考虑移动元素的平均情况考虑移动元素的平均情况:假设在第假设在第 i i 个元素之前插入的概率为个元素之前插入的概率为 P Pi i，则，则在长度为在长度为n n 的线性表中的线性表中插入一个元素所需移动元素插入一个元素所需移动元素次数的期望值次数的期望值为：为：若假定在线性表中任何一个位置上进行

30、若假定在线性表中任何一个位置上进行插入的概插入的概率率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为：为：E Eisis=p=pi i(n-i+1)(n-i+1)n+1n+1i=1i=1E Eisis=p=pi i(n-i+1)=(n-i+1)=n+1n+1i=1i=11 1n+1n+1 (n-i+1)=(n-i+1)=n+1n+1i=1i=1n n2 221 18 30 75 42 56 8721 18 30 75例如：例如：ListInsert_Sq(LListInsert_Sq(L,5,66),5,66)L.length-10pppq87564266q=&(L.elemi

31、-1);/q q=&(L.elemi-1);/q 指示插入位置指示插入位置for(p=&(L.elemL.length-1);p=q;-p)for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=(p+1)=*p;p;p线性表操作线性表操作:ListDelete(&LListDelete(&L,i,&e),i,&e)的实现：的实现：首先分析：首先分析：删除元素时，线性表的逻辑结构发删除元素时，线性表的逻辑结构发生什么变化？生什么变化？(a1,a ai-1i-1,a,ai i,a,ai+1i+1,an)改变为(a1,a ai-1i-1,a,ai+1i+1,an)a,a 表

32、的长度减少a1 a2 ai-1 a ai+1i+1ana1 a2 ai-1 ai a ai+1i+1 an-1anStatus ListDelete_Sq(SqList&L,int i,ElemTypeStatus ListDelete_Sq(SqList&L,int i,ElemType&e)&e)/在顺序表在顺序表L L中删除第中删除第 i i 个元素，并用个元素，并用e e返回其值返回其值,/i /i 的合法范围为的合法范围为 1i1iL.length/ListDelete_Sq/ListDelete_Sqforfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被

33、删除元素之后的元素左移-L.length /表长减表长减1 1returnreturn OK;算法时间复杂度算法时间复杂度为为:O(ListLength(LO(ListLength(L)p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置if(i L.length)return ERROR;if(i L.length)return ERROR;/i /i值不合法值不合法算法：算法：2.52.5考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第假设删

34、除第 i 个元素的概率为个元素的概率为 qi ,则在长度为则在长度为n 的线性表中的线性表中删除一个元素删除一个元素所需所需移动元素次数的期望移动元素次数的期望值值为：为：若假定在线性表中任何一个位置上进行删除的若假定在线性表中任何一个位置上进行删除的概概率率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：E Edldl=q=qi i(n-i(n-i)n ni=1i=1 n n E Edldl=q=qi i(n-i(n-i)=)=n ni=1i=11 1n n(n-i(n-i)=)=i=1i=1n-1n-1 2 221 18 30 75 42 56 8721 18 30 75

35、L.length-10pppq8756p=&(L.elemi-1);p=&(L.elemi-1);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-1)=*p;p;例如：例如：ListDelete_Sq(LListDelete_Sq(L,5,e),5,e)p 讨论例2.1和例2.2在顺序存储结构的线性表中的实现方法和时间复杂度的分析。算法2.1的执行时间主要取决于查找函数LocateElem的执行时间。在顺序表L查访是否存在和e相同的数据元素的最简便的方法是，令e和L中的数据元素逐个比较之

36、，如算法2.6所示。从2.6中可见，基本操作是“进行两个元素之间的比较”，若L中存在和e相同的数据元素a ai i，则比较，则比较次数为次数为i(1iL.length),i(1iL.length),否则为否则为L.lengthL.length，即算法，即算法LocateElem_SqLocateElem_Sq的时间复杂度为的时间复杂度为O(L.length)O(L.length)。由此，对于。由此，对于顺序表顺序表LaLa和和LbLb而言，而言，unionunion的时间复杂度为的时间复杂度为O(La.lengthO(La.lengthLb.length)Lb.length)。例如：顺序表23

37、 75 41 38 54 62 17L.elemL.lengthL.listsizee=38pppppi1 2 3 4 1850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0/LocateElem_Sq算法的算法的时间复杂度时间复杂度为：为：O(ListLength(L)i

38、=1;/i i 的初值为第的初值为第 1 1 元素的位序元素的位序p=L.elem;/p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;算法：算法：2.62.6 void MergeList _Sq(SqList La,SqList Lb,SqList&Lcvoid MergeList _Sq(SqList La,SqList Lb,SqList&Lc)/已知线性表已知线性表La La 和和LbLb中数据元素按值非递减有序排列中数

39、据元素按值非递减有序排列 /归并归并La La 和和LbLb得到新的线性表得到新的线性表LcLc，LcLc中的数据元素也按值非递减中的数据元素也按值非递减排列。排列。pa=La.elem;pb=Lb.elempa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length Lc.listsize=Lc.length=La.length+=La.length+Lb.length;Lb.length;pc=Lc.elem=(ElemType pc=Lc.elem=(ElemType*)malloc)malloc (Lc.listsize (Lc.listsize*sizeof

40、(ElemTypesizeof(ElemType););if(!Lc.elem)exit(OVERFLOW if(!Lc.elem)exit(OVERFLOW);/);/存储分配失败存储分配失败 pa_last=La.elempa_last=La.elem+La.length-1;+La.length-1;pb_last=Lb.elem pb_last=Lb.elem+Lb.length-1;+Lb.length-1;while(pa=pa_last&pb=pb_last while(pa=pa_last&pb=pb_last)/)/归并归并 if(if(*pa=pa=*pbpb)*pc+=p

41、c+=*pa+;pa+;else else*pc+=pc+=*pbpb+;+;while(pa=pa_last)while(pa=pa_last)*pc+=pc+=*pa+;pa+;/插入插入LaLa的剩余元素的剩余元素 while(pb=pb_last)while(pbnext;j=1;/p p指向第一个结点，指向第一个结点，j j为计数器为计数器while(p&jnext;+j;/顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 /或或 p p 为空为空if(!p|ji)return ERROR;/第第 i i 个元素不存在个元素不存在e=p-data;

42、/取得第取得第 i i 个元素个元素return OK;算法：算法：2.82.8ai-1 线性表的操作 ListInsert(&L,i,e)，在单链表中的实现：有序对有序对 a 改变为改变为 a,e 和和e,a eaiai-1 因此，在单链表中第因此，在单链表中第 i i 个结点之前进行插入的个结点之前进行插入的基本操作为基本操作为:找到线性表中第找到线性表中第i-1i-1个结点，然后修改其指向后个结点，然后修改其指向后继的指针。继的指针。可见，在链表中插入结点只需要修改指针。但可见，在链表中插入结点只需要修改指针。但同时，若要在第同时，若要在第 i i 个结点之前插入元素，修改的是个结点之前

43、插入元素，修改的是第第 i-1 i-1 个结点的指针。个结点的指针。eai-1aiai-1sps-next=p-nexts-next=p-nextp-next=sp-next=s StatusStatus ListInsert_L(LinkList L,int i,ElemType e)/L L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 /在链表中第在链表中第i i 个结点之前插入新的元素个结点之前插入新的元素 e e /LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p&j next;+j;/

44、寻找第寻找第 i-1 个结点个结点if(!p|j i-1)return ERROR;/i 大于表长或者小于大于表长或者小于1s=(LinkList)malloc(sizeof(LNode);/生成新结点生成新结点s-data=e;s-next=p-next;p-next=s;/插入插入return OK;算法：算法：2.92.9 线性表线性表的操作的操作ListDeleteListDelete(&L,i,&e)(&L,i,&e)在链表中在链表中的实现的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 在单链表中删除第删除第 i i 个结点个结点的基本操作基本操作为:找找到线

45、性表中第到线性表中第i-1i-1个结点，修改其指向后继的指针。个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pq Status ListDelete_L(LinkList L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点 /ListDelete_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p-next&j next;+j;/寻找第 i 个结点，并令 p 指向其前驱if (!(p-next)|j i-1)r

46、eturn ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;算法：算法：2.102.10操作 ClearList(&L)在链表中的实现:void ClearList(&L)/将单链表重新置为一个空表 while(L-next)p=L-next;L-next=p-next;/ClearListfree(p);算法算法时间复杂度时间复杂度：O(ListLength(LO(ListLength(L)算法：算法：2.112.11如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需要予

47、分配空间，链表是一个动态的结构，它不需要予分配空间，因此因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入”的的过程。过程。例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，建立带个数据元素的值，建立带头结点的单链表。头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素a an n，建立结，建立结点并插入；点并插入；三、输入数据元素三、输入数据元素a an-1n-1，建立结点，建立结点并插入；并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。void CreateList

48、_L(LinkList&L,int n)/逆序输入逆序输入 n 个数据元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 /CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(LO(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表先建立一个带头结点的单链表for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);/生成新结点生成新结点 scanf(&p-data);/输入元素值输入元素值 p-next=L-next;L-

49、next=p;/插入到表头插入到表头 算法：算法：2.122.12 回顾回顾 2.1 节中三个例子的算法，看一下当线节中三个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？它们的时间复杂度为多少？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_len,e);

50、/for/union控制结构：控制结构：基本操作：基本操作：for 循环循环GetElem,LocateElem 和 ListInsert当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)ListLength(Lb)当以链式映像实现抽象数据类型线性表时为:O(ListLength(La)ListLength(Lb)例例2-12-1算法时间复杂度算法时间复杂度void MergeList(List La,List Lb,List&Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);whi