第二章数据结构教案精选文档.ppt

第二章数据结构教案1本讲稿第一页，共一百四十七页第二章第二章 线性表线性表线性表是一种最简单的线性结构。线性表是一种最简单的线性结构。什么是线性结构？简单地说，线性结构是一什么是线性结构？简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基个数据元素的有序（次序）集合。它有四个基本特征：本特征：1集合中必存在唯一的一个集合中必存在唯一的一个第一元素第一元素；2集合中必存在唯一的一个集合中必存在唯一的一个最后元素最后元素；3除最后元素之外，其它数据元素均有唯一的除最后元素之外，其它数据元素均有唯一的后继后继；4除第一元素之外，其它数据元素均有唯一的除第一元素之外，其它数据元素均有唯一的前驱前驱。本讲稿第二页，共一百四十七页2.1.1抽象数据类型线性表的定义抽象数据类型线性表的定义 通常可以下列通常可以下列n个数据元素的序列个数据元素的序列表示线性表表示线性表(Linear_List)(a1,a2,.,ai,.,an)序列中数据元素的个数序列中数据元素的个数n定义为线性表的表长；定义为线性表的表长；n=0时的线性表被称为时的线性表被称为空表空表。称。称i为为ai在线性表在线性表中的中的位序位序。本讲稿第三页，共一百四十七页2.1.1 抽象数据类型线性表的定义 其抽象数据类型的定义如下：其抽象数据类型的定义如下：ADTList数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,aiD,i=2,.,n本讲稿第四页，共一百四十七页2.1.1 抽象数据类型线性表的定义 基本操作：基本操作：结构初始化结构初始化InitList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L。销毁结构销毁结构DestroyList(&L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：销毁线性表操作结果：销毁线性表L。本讲稿第五页，共一百四十七页2.1.1 抽象数据类型线性表的定义引用型操作引用型操作ListEmpty(L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：若操作结果：若L为空表，则返回为空表，则返回TRUE，否，否则返回则返回FALSE。ListLength(L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：返回操作结果：返回L中元素个数。中元素个数。本讲稿第六页，共一百四十七页2.1.1 抽象数据类型线性表的定义 PriorElem(L,cur_e,&pre_e)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：若操作结果：若cur_e是是L中的数据元素，则用中的数据元素，则用pre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定义。无定义。NextElem(L,cur_e,&next_e)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：若操作结果：若cur_e是是L中的数据元素，则用中的数据元素，则用ext_e返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_e无定义无定义。本讲稿第七页，共一百四十七页2.1.1 抽象数据类型线性表的定义 GetElem(L,i,&e)初始条件：线性表初始条件：线性表L已存在，已存在，1iLengthList(L)。操作结果：用操作结果：用e返回返回L中第中第i个元素的值。个元素的值。LocateElem(L,e,compare()初始条件：线性表初始条件：线性表L已存在，已存在，compare()是元素判定函数。是元素判定函数。操作结果：返回操作结果：返回L中第中第1个与个与e满足关系满足关系compare()的元素的位的元素的位序。若这样的元素不存在，则返回值为序。若这样的元素不存在，则返回值为0。本讲稿第八页，共一百四十七页2.1.1 抽象数据类型线性表的定义 ListTraverse(L,visit()初始条件：线性表初始条件：线性表L已存在，已存在，visit()为元素的访为元素的访问函数。问函数。操作结果：依次对操作结果：依次对L的每个元素调用函数的每个元素调用函数visit()。一旦一旦visit()失败，则操作失败。失败，则操作失败。本讲稿第九页，共一百四十七页2.1.1 抽象数据类型线性表的定义加工型操作加工型操作ClearList(&L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：将操作结果：将L重置为空表。重置为空表。PutElem(&L,i,e)初始条件：线性表初始条件：线性表L已存在，已存在，1iLengthList(L)。操作结果：操作结果：L中第中第i个元素赋值同个元素赋值同e的值。的值。本讲稿第十页，共一百四十七页2.1.1 抽象数据类型线性表的定义ListInsert(&L,i,e)初始条件：线性表初始条件：线性表L已存在，已存在，1iLengthList(L)+1。操作结果：在操作结果：在L的第的第i个元素之前插入新的元素个元素之前插入新的元素e，L的长度增的长度增1。ListDelete(&L,i,&e)初始条件：线性表初始条件：线性表L已存在且非空，已存在且非空，1iLengthList(L)。操作结果：删除操作结果：删除L的第的第i个元素，并用个元素，并用e返回其值，返回其值，L的长度减的长度减1。ADTList本讲稿第十一页，共一百四十七页2.1.2线性表类型的应用线性表类型的应用 如果已经实现了上述定义的线性表类型，那么如果已经实现了上述定义的线性表类型，那么在应用问题的求解中就可以利用类型中定义的各在应用问题的求解中就可以利用类型中定义的各种操作。下面将举几个例子说明之。种操作。下面将举几个例子说明之。例例2-1已知集合已知集合A和和B，求两个集合的并集，使，求两个集合的并集，使AAB，且，且B不再单独存在。不再单独存在。本讲稿第十二页，共一百四十七页2.1.2 线性表类型的应用 从集合的观点看，此问题求解的方法很简单，从集合的观点看，此问题求解的方法很简单，只要对集合只要对集合B中的所有元素一个一个地检查，看中的所有元素一个一个地检查，看看在集合看在集合A中是否存在相同元素，若不存在，则中是否存在相同元素，若不存在，则将该元素插入到集合将该元素插入到集合A，否则舍弃之。，否则舍弃之。要在计算机中求解，首先要确定要在计算机中求解，首先要确定如何表示集如何表示集合合。集合可以有多种表示方法，对上述集合求。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表示集合。并的问题可以用线性表表示集合。本讲稿第十三页，共一百四十七页2.1.2 线性表类型的应用 现假设以线性表现假设以线性表LA和和LB分别表示集合分别表示集合A和和B，即构造两个线性表，即构造两个线性表LA和和LB，它们的数，它们的数据元素分别为集合据元素分别为集合A和和B中的成员。中的成员。由此，上述集合求并的问题便可演绎为：要求由此，上述集合求并的问题便可演绎为：要求对线性表作如下操作：对线性表作如下操作：扩大线性表扩大线性表 LA，将存在，将存在于线性表于线性表 LB 中而不存在于线性表中而不存在于线性表 LA 中的数据中的数据元素插入到线性表元素插入到线性表 LA 中去。中去。本讲稿第十四页，共一百四十七页2.1.2 线性表类型的应用具体操作步骤为：具体操作步骤为：1从线性表从线性表LB中取出一个数据元素；中取出一个数据元素；2依值在线性表依值在线性表LA中进行查询；中进行查询；3若不存在，则将它插入到若不存在，则将它插入到LA中。中。重复上述三步直至重复上述三步直至LB为空表止。为空表止。那么，其中的每一步能否利用上述线性表类型中那么，其中的每一步能否利用上述线性表类型中定义的基本操作来完成呢？定义的基本操作来完成呢？本讲稿第十五页，共一百四十七页2.1.2 线性表类型的应用容易看出，上述的每一步恰好对应线性表的一个基容易看出，上述的每一步恰好对应线性表的一个基本操作：本操作：1.ListDelete(LB,1,e);2.LocateElem(LA,e,equal();3.ListInsert(LA,n+1,e)本讲稿第十六页，共一百四十七页2.1.2 线性表类型的应用算法算法2.1voidunion(List&LA,List&LB)/将所有在线性表将所有在线性表LB中但不在中但不在LA中的数据元中的数据元/素插入到素插入到LA中中,/算法执行之后，线性表算法执行之后，线性表LB不再存在。不再存在。La_len=ListLength(LA);/求得线性表求得线性表LA/的长度的长度while(!ListEmpty(LB)/依次处理依次处理LB中中/元素直至元素直至LB为空表止。为空表止。本讲稿第十七页，共一百四十七页2.1.2 线性表类型的应用 ListDelete(LB,1,e);/从从LB中删除第中删除第1个数个数/据元素并赋给据元素并赋给eif(!LocateElem(LA,e,equal()ListInsert(LA,+La_len,e);/当当LA中不存在和中不存在和e值相同的数据元素时进行值相同的数据元素时进行/插入插入/whileDestroyList(LB);/销毁线性表销毁线性表LB/union本讲稿第十八页，共一百四十七页2.1.2 线性表类型的应用例例2-2已知一个已知一个“非纯集合非纯集合”B，试构造一个集合，试构造一个集合A，使，使A中只包含中只包含B中所有值各不相同的数据元中所有值各不相同的数据元素。素。算法算法2.2voidpurge(List&LA,ListLB)/构造线性表构造线性表LA，使其只包含，使其只包含LB中所有值不相中所有值不相/同的数据元素同的数据元素,算法不改变线性表算法不改变线性表LB本讲稿第十九页，共一百四十七页2.1.2 线性表类型的应用 InitList(LA);/创建一个空的线性表创建一个空的线性表LALa_len=0;Lb_len=ListLength(LB);/求线性表求线性表LB的的长度长度for(i=1;i=Lb_len;i+)/依次处理依次处理LB中每个元素中每个元素GetElem(LB,i,e);/取取LB中第中第i个个数据数据/元素赋给元素赋给e本讲稿第二十页，共一百四十七页2.1.2 线性表类型的应用E if(!LocateElem(LA,e,equal()ListInsert(LA,+La_len,e);/当当LA中不存在和中不存在和e值相值相/同的数据元素时进行插入同的数据元素时进行插入/for/purge本讲稿第二十一页，共一百四十七页2.1.2 线性表类型的应用例例2-3判别两个集合是否相等。判别两个集合是否相等。算法算法2.3boolisEqual(ListLA,ListLB)/若线性表若线性表LA和和LB不仅长度相等，且所不仅长度相等，且所/含数据元素也相同，含数据元素也相同，则返回则返回TRUE，否则，否则/返回返回FALSE。La_len=Listlength(LA);Lb_len=Listlength(LB);本讲稿第二十二页，共一百四十七页2.1.2 线性表类型的应用if(La_len!=Lb_len)returnFALSE;/两表的长度不等两表的长度不等elsei=1;found=TRUE;while(i=La_len&found)GetElem(LA,i,e);/取得取得LA中一个元素中一个元素本讲稿第二十三页，共一百四十七页2.1.2 线性表类型的应用if(LocateElem(LB,e,equal()i+;/依次处理下一个依次处理下一个elsefound=FALSE;/LB中没有和该元素相同的元素中没有和该元素相同的元素/whilereturnfound;/else/isEqual本讲稿第二十四页，共一百四十七页2.2线性表的顺序存储表示和实现线性表的顺序存储表示和实现2.2.1顺序表顺序表顺序表是线性表的顺序存储表示的简称，它指顺序表是线性表的顺序存储表示的简称，它指的是，的是，“用一组地址连续的存储单元依次存放线用一组地址连续的存储单元依次存放线性表中的数据元素性表中的数据元素”，即以，即以“存储位置相邻存储位置相邻”表表示示“位序相继的两个数据元素之间的前驱和后继位序相继的两个数据元素之间的前驱和后继的关系的关系(有序对有序对)，并以表中第一个元，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性素的存储位置作为线性表的起始地址，称作线性表的基地址。如下图所示。表的基地址。如下图所示。本讲稿第二十五页，共一百四十七页 2.2.1 顺序表 不失一般性，假设每个数据元素占据的存储不失一般性，假设每个数据元素占据的存储量是一个常量量是一个常量C，则后继元素的存储地址和其前，则后继元素的存储地址和其前驱元素相隔一个常量，驱元素相隔一个常量，即：即：LOC(ai)=LOC(ai-1)+C一个数据元素所一个数据元素所占存储量占存储量本讲稿第二十六页，共一百四十七页2.2.1 顺序表由此，所有数据元素的存储位置均可由第一个由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到数据元素的存储位置得到LOC(ai)=LOC(a1)+(i-1)C基地址基地址用用C语言描述的顺序表类型如下所示：语言描述的顺序表类型如下所示：本讲稿第二十七页，共一百四十七页2.2.1 顺序表/存储结构存储结构constintMAXLISTSIZE=80;/预设的存预设的存储储/空间最大容量空间最大容量typedefstructElemType*elem;/存储空间基存储空间基址址intlength;/当前长度当前长度intlistsize;/允许的最大存储容允许的最大存储容量量(以以sizeof(ElemType)为单位为单位)SqList;/俗称俗称顺序表顺序表本讲稿第二十八页，共一百四十七页2.2.1 顺序表/基本操作接口基本操作接口(函数声明函数声明)voidInitList(SqList&L,intmaxsize);/构造一个最大存储容量为构造一个最大存储容量为maxsize的空的的空的/顺序表顺序表L。voidDestroyList(SqList&L)/销毁顺序表销毁顺序表L。本讲稿第二十九页，共一百四十七页2.2.1 顺序表boolListEmpty(SqListL)/若顺序表若顺序表L为空表，则返回为空表，则返回TRUE，否则，否则/返回返回FALSE。intListLength(SqListL)/返回顺序表返回顺序表L中元素个数。中元素个数。本讲稿第三十页，共一百四十七页2.2.1 顺序表 intPriorElem(SqListL,ElemTypecur_e)/若若cur_e是顺序表是顺序表L的元素，则返回其前驱的位序的元素，则返回其前驱的位序/(设第一个元素的前驱的位序为设第一个元素的前驱的位序为0)，否则返回，否则返回-1。intNextElem(SqListL,ElemTypecur_e)/若若cur_e是顺序表是顺序表L的元素，则返回其后继的位序的元素，则返回其后继的位序/(设最后一个元素的后继的位序为设最后一个元素的后继的位序为L的表长的表长+1)，否则，否则/返回返回-1。本讲稿第三十一页，共一百四十七页2.2.1 顺序表boolGetElem(SqListL,intpos,ElemType&e)/若若1posLengthList(L)，则用，则用e带回顺序表带回顺序表L中第中第pos个元素个元素/的值且返回函数值为的值且返回函数值为TRUE，否则返回函数值为，否则返回函数值为FALSE。intLocateElem(SqListL,ElemTypee,bool(*compare)(ElemType,ElemType)/返回顺序表返回顺序表L中第中第1个与个与e满足关系满足关系compare()的数的数/据元素的位序。若这样的元素不存在，则返回值为据元素的位序。若这样的元素不存在，则返回值为0。/compare()为数据元素的判定函数。为数据元素的判定函数。本讲稿第三十二页，共一百四十七页2.2.1 顺序表voidListTraverse(SqListL,void(*visit)(ElemType)/依次对顺序表依次对顺序表L的每个元素调用函数的每个元素调用函数/visit()。一旦。一旦visit()失败，则操作失败。失败，则操作失败。voidClearList(SqList&L)/将顺序表将顺序表L重置为空表。重置为空表。本讲稿第三十三页，共一百四十七页2.2.1 顺序表boolPutElem(SqListL,intpos,ElemType&e)/若若1posLengthList(L)，则对顺序表，则对顺序表L中第中第pos/个元素赋值同个元素赋值同e的值且返回函数值为的值且返回函数值为TRUE，否则返，否则返/回函数值为回函数值为FALSE。boolListInsert(SqList&L,intpos,ElemTypee)/若存储空间未满且若存储空间未满且1posLengthList(L)+1，则在，则在/顺序表顺序表L的第的第pos个元素之前插入新的元素个元素之前插入新的元素e，L的长的长/度增度增1，且返回函数值为，且返回函数值为TRUE，否则不改变顺序表且，否则不改变顺序表且/返回函数值为返回函数值为FALSE。本讲稿第三十四页，共一百四十七页2.2.1 顺序表boolListDelete(SqList&L,intpos,ElemType&e)/若若1posLengthList(L)，则删除顺序表，则删除顺序表L/的第的第pos个元素个元素e，L的长度增的长度增1，且返回，且返回函函/数值为数值为TRUE，否则不改变顺序表且返回函，否则不改变顺序表且返回函/数值为数值为FALSE。本讲稿第三十五页，共一百四十七页2.2.1 顺序表以上定义的函数可在程序设计中引用，例如，以上定义的函数可在程序设计中引用，例如，述算法述算法2.2可改写为下列可在主函数中调用的函数。可改写为下列可在主函数中调用的函数。voidpurge(SqList&La,SqListLb)/构造顺序表构造顺序表La，使其只包含，使其只包含Lb中所有值中所有值/不相同的数据元素不相同的数据元素,算法不改变顺序表算法不改变顺序表Lbboolb;intLb_len=Listlength(Lb);/求线性表求线性表Lb的长度的长度本讲稿第三十六页，共一百四十七页2.2.1 顺序表 InitList(La,Lb_len);/创建一个空的线性表创建一个空的线性表LaintLa_len=0;for(i=1;i=Lb_len;i+)/依次处理依次处理Lb/中每个元中每个元素素b=GetElem(Lb,i,e);/取取Lb中第中第i/个数据元素赋个数据元素赋给给eif(!LocateElem(La,e,equal()本讲稿第三十七页，共一百四十七页2.2.1 顺序表+La_len;b=ListInsert(La,La_len,e);/当当La中不存在和中不存在和e值相同的数据元值相同的数据元/素时，进行插入。素时，进行插入。/for/purge本讲稿第三十八页，共一百四十七页2.2.2顺序表中基本操作的实现顺序表中基本操作的实现从顺序表的存储结构定义容易看出，由于顺序表的从顺序表的存储结构定义容易看出，由于顺序表的长长度度是个是个显值显值，且由于第，且由于第i个元素恰好存储在数组的第个元素恰好存储在数组的第i个个分量分量(数组下标为数组下标为i-1)中，因此其中，因此其求长求长、判空判空以及以及存取存取第第i个数据元素个数据元素等操作都很容易实现。下面重点讨论顺序等操作都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现。表类型定义中五个操作的实现。一、初始化操作一、初始化操作二、元素定位操作二、元素定位操作三、插入元素操作三、插入元素操作四、删除元素操作四、删除元素操作五、销毁结构操作五、销毁结构操作本讲稿第三十九页，共一百四十七页2.2.2顺序表中基本操作的实现一、初始化操作一、初始化操作对顺序表而言，对顺序表而言，初始化初始化的实质是为它分配一个的实质是为它分配一个足够应用足够应用的元素存储空间，由用户根据它对线的元素存储空间，由用户根据它对线性表的使用要求定义一个最大存储容量性表的使用要求定义一个最大存储容量maxsize，并约定当用户没有提出特殊需求，并约定当用户没有提出特殊需求(maxsize=0)时，按予设的最大存储量时，按予设的最大存储量MAXLISTSIZE进行分进行分配。配。本讲稿第四十页，共一百四十七页2.2.2顺序表中基本操作的实现算法算法2.4voidInitList(SqList&L,intmaxsize)/构造一个空的线性表构造一个空的线性表Lif(maxsize=0)maxsize=MAXLISTSIZE;L.elem=newElemTypemaxsize;本讲稿第四十一页，共一百四十七页2.2.2顺序表中基本操作的实现if(!L.elem)exit(1);/存储分配失败存储分配失败L.length=0;/顺序表的初始长度为顺序表的初始长度为0L.listsize=maxsize;/该顺序表可以该顺序表可以存储存储/元素的最大容元素的最大容量量/InitList此算法的时间复杂度为此算法的时间复杂度为O(1)。本讲稿第四十二页，共一百四十七页2.2.2顺序表中基本操作的实现二、元素定位操作二、元素定位操作在顺序表中在顺序表中查询查询是否存在一个和给定值满是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。结构中的每个元素和给定值进行比较。算法算法2.5intLocateElem(SqListL,ElemTypee,void（*compare)(ElemType,lemType)本讲稿第四十三页，共一百四十七页2.2.2顺序表中基本操作的实现 /在顺序表在顺序表L中查找第中查找第1个值与个值与e满足判定条件满足判定条件/compare()的元素，的元素，若找到，则返回其在若找到，则返回其在L中中/的位序，否则返回的位序，否则返回0。i=1;/i的初值为第的初值为第1元素的位序元素的位序p=L.elem;/p的初值为第的初值为第1元素的存储位元素的存储位置置while(i=L.length&!(*compare)(*p+,e)+i;/依次进行判定依次进行判定本讲稿第四十四页，共一百四十七页2.2.2顺序表中基本操作的实现if(i=L.length)returni;/找到满足判定条件的数据元素为第找到满足判定条件的数据元素为第i个元素个元素elsereturn0;/该线性表中不存该线性表中不存在在/满足判定的数据元满足判定的数据元素素/LocateElem此算法的时间复杂度为：此算法的时间复杂度为：O(ListLength(L)本讲稿第四十五页，共一百四十七页2.2.2顺序表中基本操作的实现三、插入元素操作三、插入元素操作首先分析，首先分析，插入元素插入元素使线性表的逻辑结构使线性表的逻辑结构发生什么变化？发生什么变化？假设在线性表的第假设在线性表的第i个元素之前插入一个元素个元素之前插入一个元素e，使得线性表，使得线性表(a1,ai-1,ai,an)改变为改变为(a1,ai-1,e,ai,an)即：即：(1)改变了表中元素之间的关系，使改变了表中元素之间的关系，使改变为改变为和和本讲稿第四十六页，共一百四十七页2.2.2顺序表中基本操作的实现(2)表长增表长增1由于顺序表是以由于顺序表是以存储位置相邻存储位置相邻表示表示元素元素之间的前驱和后继关系之间的前驱和后继关系，则必须，则必须移动元素移动元素来来体现体现元素之间发生的变化元素之间发生的变化。算法算法2.6boolListInsert(SqList&L,intpos,ElemTypee)/若存储空间不满若存储空间不满,且且1posListlength(L)+1，/则在顺序表则在顺序表L的第的第pos个元素之前插入新的个元素之前插入新的元元/素素e且返回且返回TRUE，否则返回，否则返回FALSE本讲稿第四十七页，共一百四十七页2.2.2顺序表中基本操作的实现if(posL.length+1)returnFALSE;/插入位置不合法插入位置不合法if(L.length=L.listsize)returnFALSE;/当前存储空间已满，无法插入当前存储空间已满，无法插入for(j=L.length-1;j=pos-1;-j)L.elemj+1=L.elemj;/插入位置及之后的元素右移插入位置及之后的元素右移本讲稿第四十八页，共一百四十七页2.2.2顺序表中基本操作的实现L.elempos-1=e;/插入插入e+L.length;/表长增表长增1returnTRUE;/ListInsert此算法的时间复杂度为：此算法的时间复杂度为：O(ListLength(L)本讲稿第四十九页，共一百四十七页2.2.2顺序表中基本操作的实现四、删除元素操作四、删除元素操作同样首先分析，同样首先分析，“删除元素删除元素”使线性表的逻辑使线性表的逻辑结构发生什么变化？结构发生什么变化？假设删除线性表中第假设删除线性表中第i个元个元素，使得线性表素，使得线性表(a1,ai-1,ai,ai+1,an)改变为改变为(a1,ai-1,ai+1,an)即：即：(1)改变了表中元素之间的关系，使改变了表中元素之间的关系，使和和改变为改变为本讲稿第五十页，共一百四十七页2.2.2顺序表中基本操作的实现(2)表长减表长减1对顺序表而言，需要改变从第对顺序表而言，需要改变从第i+1个元素起个元素起到第到第n个元素的存储位置，即进行个元素的存储位置，即进行“从第从第i+1到到第第n个元素往前移动一个位置个元素往前移动一个位置”。算法算法2.7boolListDelete(SqList&L,intpos,ElemType&e)/若若1posListlength(L)，则以，则以e带回从顺序带回从顺序/表表L中删除的第中删除的第pos个元素且返回个元素且返回TRUE，本讲稿第五十一页，共一百四十七页2.2.2顺序表中基本操作的实现/否则返回否则返回FALSEif(posL.length)returnFALSE;/删除位置不合法删除位置不合法for(j=pos;jL.length;+j)L.elemj-1=L.elemj;/被删除元素被删除元素之后之后/的元素左移的元素左移本讲稿第五十二页，共一百四十七页2.2.2顺序表中基本操作的实现 -L.length;/表长减表长减1returnTRUE;/ListDelete此算法的时间复杂度为：此算法的时间复杂度为：O(ListLength(L)本讲稿第五十三页，共一百四十七页2.2.2顺序表中基本操作的实现五、销毁结构操作五、销毁结构操作算法算法2.8voidDestroyList(SqList&L)/释放顺序表释放顺序表L所占存储空间所占存储空间deleteL.elem;L.listsize=0;L.length=0;/DestroyList_Sq此算法的时间复杂度为：此算法的时间复杂度为：O(1)本讲稿第五十四页，共一百四十七页2.2.2顺序表中基本操作的实现六、插入和删除操作的性能分析六、插入和删除操作的性能分析试问，在顺序表中任何一个合法位置上进行试问，在顺序表中任何一个合法位置上进行一次一次插入或删除操作时，需要移动的元素个数插入或删除操作时，需要移动的元素个数的平均值是多少？的平均值是多少？令令Ein(n)表示在长度为表示在长度为n的顺序表中进行一的顺序表中进行一次插入操作时所需进行次插入操作时所需进行移动移动元素个数的期望值元素个数的期望值（即平均移动个数），则（即平均移动个数），则本讲稿第五十五页，共一百四十七页2.2.2顺序表中基本操作的实现其中，其中，pi是在第是在第i个元素之前插入一个元素的概个元素之前插入一个元素的概率，率，n-i+1是在第是在第i个元素之前插入一个元素时所个元素之前插入一个元素时所需移动的元素个数。由于可能插入的位置需移动的元素个数。由于可能插入的位置i=1,2,3,n+1共共n+1个，假设在每个位置上进个，假设在每个位置上进行插入的机会均等，则行插入的机会均等，则本讲稿第五十六页，共一百四十七页2.2.2顺序表中基本操作的实现由此，在上述等概率假设的情况下，由此，在上述等概率假设的情况下，本讲稿第五十七页，共一百四十七页2.2.2顺序表中基本操作的实现类似地，删除操作类似地，删除操作在上述等概率假设的情况下是：在上述等概率假设的情况下是：本讲稿第五十八页，共一百四十七页2.2.3顺序表其它算法举例顺序表其它算法举例例例2-4试编写算法试编写算法“比较比较”两个顺序表的大小。两个顺序表的大小。算法的基本思想为：若算法的基本思想为：若aj=bj，则，则j增增1，之后继续比较后继元素；否则即可得出比较结果。之后继续比较后继元素；否则即可得出比较结果。显然，显然，j的初值应为的初值应为0，循环的条件是，循环的条件是j不超出其不超出其中任何一个表的范围。若在循环内不能得出比较中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有三种可能出现的情况需要结果，则循环结束时有三种可能出现的情况需要区分。根据以上分析可得下列算法。区分。根据以上分析可得下列算法。本讲稿第五十九页，共一百四十七页2.2.3 顺序表其它算法举例算法算法2.9intcompare(SqListA,SqListB)/若若AB，则返回，则返回1j=0;while(jA.length&jB.length)if(A.elemjB.elemj)return(1);本讲稿第六十页，共一百四十七页2.2.3 顺序表其它算法举例elsej+;if(A.length=B.length)return(0);elseif(A.lengthB.length)return(-1);elsereturn(1);/compare上述算法中只有一个上述算法中只有一个while循环，它的执行次循环，它的执行次数依赖于待比较的顺序表的表长，因此，算法数依赖于待比较的顺序表的表长，因此，算法2.9的时间复杂度为的时间复杂度为O(Min(A.length,B.length)。本讲稿第六十一页，共一百四十七页2.2.3 顺序表其它算法举例例例2-5试设计一个算法，用尽可能少的辅助空间试设计一个算法，用尽可能少的辅助空间将顺序表中前将顺序表中前m个元素和后个元素和后n个元素进行互换，个元素进行互换，即将线性表即将线性表(a1,a2,am,b1,b2,bn)改变成改变成(b1,b2,bn,a1,a2,am)。算法算法2.10voidinvert(ElemType&R,ints,intt)/本算法将数组本算法将数组R中下标自中下标自s到到t的元素逆置，的元素逆置，/即将（即将（Rs,Rs+1,Rt-1,Rt）改变为）改变为/（Rt,Rt-1,Rs+1,Rs）本讲稿第六十二页，共一百四十七页2.2.3 顺序表其它算法举例for(k=s;k0&mA.length)n=A.length-m;invert(A.elem,0,m+n-1);invert(A.elem,0,n-1);invert(A.elem,n,m+n-1);/exchange本讲稿第六十四页，共一百四十七页2.2.3 顺序表其它算法举例例例2-6编写算法删除顺序表中编写算法删除顺序表中“多余多余”的数据元的数据元素，素，即使操作之后的顺序表中所有元素的值都不相同。即使操作之后的顺序表中所有元素的值都不相同。算法算法2.12void purge_Sq(SqList&L)/删除顺序表删除顺序表L中的冗余元素，即使操作之中的冗余元素，即使操作之/后的顺序表中只保留操作之前表中所有值后的顺序表中只保留操作之前表中所有值/都不相同的元素都不相同的元素本讲稿第六十五页，共一百四十七页2.2.3 顺序表其它算法举例 k=-1;/k指示新表的表尾指示新表的表尾for(i=0;iL.length;+i)/顺序考察表中每个元素顺序考察表中每个元素j=0;while(jk)/k=-1表明当前考察的是第一个元素表明当前考察的是第一个元素L.elem+k=L.elemi;/forL.length=k+1;/修改表长修改表长/purge_Sq本讲稿第六十六页，共一百四十七页2.2.3 顺序表其它算法举例此算法的时间复杂度为此算法的时间复杂度为O(ListLength2(L)分析：分析：算法中的基本操作为算法中的基本操作为比较比较，控制结构为两，控制结构为两重循环，外循环的执行次数和顺序表的表长相同，重循环，外循环的执行次数和顺序表的表长相同，内循环的执行次数则不超过表长。此外，内循环的执行次数则不超过表长。此外，比较比较操作相对于操作相对于移动移动操作所需的时间也少。操作所需的时间也少。从这个题的算法可以得到一些有益的启示，从这个题的算法可以得到一些有益的启示，某种情况下，某种情况下，删除删除操作也可利用操作也可利用插入插入来实现。来实现。本讲稿第六十七页，共一百四十七页2.3线性表的链式存储表示和实现线性表的链式存储表示和实现2.3.1单链表和指针单链表和指针线性表的链式存储表示的特点是用一组任意的存储单元存储线线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素的）。因此，为了表示每个数据元素ai与其直接后继数据元素与其直接后继数据元素ai+1之间的逻辑关系，对数据元素之间的逻辑关系，对数据元素ai来说，除了存储其本身的信来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个存储位置）。由这两部分信息组成一个结点结点（如下图所示），（如下图所示），表示线性表中一个数据元素表示线性表中一个数据元素ai。数据域数据域data指针域指针域next本讲稿第六十八页，共一百四十七页2.3.1 单链表和指针其中存储数据元素信息的域称作数据域（设域其中存储数据元素信息的域称作数据域（设域名为名为data），存储直接后继存储位置的域称为指），存储直接后继存储位置的域称为指针域（设域名为针域（设域名为next）。指针域中存储的信息又）。指针域中存储的信息又称做指针或链。称做指针或链。由分别表示由分别表示,的的N个结点依次相链构个结点依次相链构成的链表，称为线性表的链式存储表示，由于此成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称类链表的每个结点中只包含一个指针域，故又称单链表或线性链表，如下图所示。单链表或线性链表，如下图所示。本讲稿第六十九页，共一百四十七页2.3.1 单链表和指针和顺序表类似，在链式存储结构中仍以第一个数据元素的和顺序表类似，在链式存储结构中仍以第一个数据元素的存储地址作为线性表的基地址，通常称它为头指针，线性表存储地址作为线性表的基地址，通常称它为头指针，线性表中所有数据元素都可以从头指针出发找到。因为线性表的最中所有数据元素都可以从头指针出发找到。因为线性表的最后一个数据元素没有后继，因此最后一个结点中的后一个数据元素没有后继，因此最后一个结点中的指针指针是是一个特殊的值一个特殊的值NULL（在图上用（在图上用表示），通常称它为表示），通常称它为空空指针指针。本讲稿第七十页，共一百四十七页2.3.1 单链表和指针为了便于处理一些特殊情况，在第一个结点为了便于处理一些特殊情况，在第一个结点之前附加一个之前附加一个头结点头结点，令该结点中指针域的，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头指针指向第一个元素结点，并令头指针指向头结点，如下图