数据结构课件(李春葆第3版)第2章线性表.ppt

第2章线性表2.1线性表的基本概念2.2线性表的顺序存储2.3线性表的链式存储2.4线性表的应用本章小结2.5有序表2.1线性表的基本概念2.1.1线性表的定义2.1.2线性表的运算2.1.1线性表的定义线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1≤i≤n)。线性表的一般表示为:(a1,a2,…ai,ai+1,…,an)其中a1为第一个元素,又称做表头元素,a2为第二个元素,an为最后一个元素,又称做表尾元素。例如,在线性表(1,4,3,2,8,10)中,1为表头元素,10为表尾元素。2.1.2线性表的运算线性表的基本运算如下:(1)初始化线性表InitList(&L):构造一个空的线性表L。(2)销毁线性表DestroyList(&L):释放线性表L占用的内存空间。(3)判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。(4)求线性表的长度ListLength(L):返回L中元素个数。(5)输出线性表DispList(L):当线性表L不为空时,顺序显示L中各结点的值域。(6)求线性表L中指定位置的某个数据元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))个元素的值。(7)定位查找LocateElem(L,e):返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。(8)插入数据元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。(9)删除数据元素ListDelete(&L,i,&e):删除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。例2.1假设有两个集合A和B分别用两个线性表LA和LB表示,即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合C=A∪B,即将两个集合的并集放在线性表LC中。解:本算法思想是:先初始化线性表LC,将LA的所有元素复制到LC中,然后扫描线性表LB,若LB的当前元素不在线性表LA中,则将其插入到LC中。算法如下:voidunionList(ListLA,ListLB,List&LC){intlena,lenc,i;ElemTypee;InitList(LC);for(i=1;i=ListLength(LA);i++)/*将LA的所有元素插入到Lc中*/{GetElem(LA,i,e);ListInsert(LC,i,e);}lena=ListLength(LA);/*求线性表的长度*/lenB=ListLength(LB);for(i=1;i=lenb;i++){GetElem(LB,i,e);/*取LB中第i个数据元素赋给e*/if(!LocateElem(LA,e))ListInsert(LC,++lenc,e);/*LA中不存在和e相同者,则插入到LC中*/}}由于LocateElem(LA,e)运算的时间复杂度为O(ListLength(LA)),所以本算法的时间复杂度为:O(ListLength(LA)*ListLength(LB))。2.2线性表的顺序存储2.2.1线性表的顺序存储—顺序表2.2.2顺序表基本运算的实现2.2.1线性表的顺序存储—顺序表线性表的顺序存储结构就是:把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。这样,线性表中第一个元素的存储位置就是指定的存储位置,第i+1个元素(1≤i≤n-1)的存储位置紧接在第i个元素的存储位置的后面。线性表逻辑结构顺序表存储结构假定线性表的元素类型为ElemType,则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为:n*sizeof(ElemType)其中,n表示线性表的长度。a1LOC(A)0a2LOC(A)+sizeof(ElemType)1线性表存储空间存储地址下标位置┇┇aiLOC(A)+(i-1)*sizeof(ElemType)i-1┇┇anLOC(A)+(n-1)*sizeof(ElemType)n-1┇┇┇LOC(A)+(MaxSize-1)*sizeof(ElemType)MaxSize-1顺序表示意图在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用data[MaxSize]表示,长度整型变量用length表示,并采用结构体类型表示,则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下:typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;/*顺序表类型*/其中,data成员存放元素,length成员存放线性表的实际长度。说明：由于C/C++中数组的下标从0开始，线性表的第i个元素ai存放顺序表的第i-1位置上。为了清楚，将ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。2.2.2顺序表基本运算的实现一旦采用顺序表存储结构,我们就可以用C/C++语言实现线性表的各种基本运算。为了方便,假设ElemType为char类型,使用如下自定义类型语句:typedefcharElemType;1.建立顺序表其方法是将给定的含有n个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。算法如下：voidCreateList(SqList*&L,ElemTypea[],intn)/*建立顺序表*/{inti;L=(SqList*)malloc(sizeof(SqList));for(i=0;in;i++)L-data[i]=a[i];L-length=n;}2.顺序表基本运算算法(1)初始化线性表InitList(L)该运算的结果是构造一个空的线性表L。实际上只需将length成员设置为0即可。voidInitList(SqList*&L)//引用型指针{L=(SqList*)malloc(sizeof(SqList));/*分配存放线性表的空间*/L-length=0;}本算法的时间复杂度为O(1)。顺序表L(2)销毁线性表DestroyList(L)该运算的结果是释放线性表L占用的内存空间。voidDestroyList(SqList*&L){free(L);}本算法的时间复杂度为O(1)。(3)判定是否为空表ListEmpty(L)该运算返回一个值表示L是否为空表。若L为空表,则返回1,否则返回0。intListEmpty(SqList*L){return(L-length==0);}本算法的时间复杂度为O(1)。(4)求线性表的长度ListLength(L)该运算返回顺序表L的长度。实际上只需返回length成员的值即可。intListLength(SqList*L){return(L-length);}本算法的时间复杂度为O(1)。(5)输出线性表DispList(L)该运算当线性表L不为空时,顺序显示L中各元素的值。voidDispList(SqList*L){inti;if(ListEmpty(L))return;for(i=0;iL-length;i++)printf(%c,L-data[i]);printf(\n);}本算法中基本运算为for循环中的printf语句,故时间复杂度为:O(L-length)或O(n)(6)求某个数据元素值GetElem(L,i,e)该运算返回L中第i(1≤i≤ListLength(L))个元素的值,存放在e中。intGetElem(SqList*L,inti,ElemType&e){if(i1||iL-length)return0;e=L-data[i-1];return1;}本算法的时间复杂度为O(1)。(7)按元素值查找LocateElem(L,e)该运算顺序查找第1个值域与e相等的元素的位序。若这样的元素不存在,则返回值为0。intLocateElem(SqList*L,ElemTypee){inti=0;while(iL-length&&L-data[i]!=e)i++;if(i=L-length)return0;elsereturni+1;}本算法中基本运算为while循环中的i++语句,故时间复杂度为:O(L-length)或O(n)(8)插入数据元素ListInsert(L,i,e)该运算在顺序表L的第i个位置(1≤i≤ListLength(L)+1)上插入新的元素e。思路：如果i值不正确,则显示相应错误信息；否则将顺序表原来第i个元素及以后元素均后移一个位置,腾出一个空位置插入新元素,顺序表长度增1。intListInsert(SqList*&L,inti,ElemTypee){intj;if(i1||iL-length+1)return0;i--;/*将顺序表逻辑位序转化为elem下标即物理位序*/for(j=L-length;ji;j--)L-data[j]=L-data[j-1];/*将data[i]及后面元素后移一个位置*/L-data[i]=e;L-length++;/*顺序表长度增1*/return1;}a0…ai-1ai…an-1……逻辑位序1ii+1nMaxSize对于本算法来说,元素移动的次数不仅与表长L.length=n有关,而且与插入位置i有关:当i=n+1时,移动次数为0；当i=1时,移动次数为n,达到最大值。在线性表sq中共有n+1个可以插入元素的地方。假设pi(=)是在第i个位置上插入一个元素的概率,则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为:因此插入算法的平均时间复杂度为O(n)。11＋n)(2)1(11)1(1111nOninninniniip(9)删除数据元素ListDelete(L,i,e)删除顺序表L中的第i(1≤i≤ListLength(L))个元素。思路：如果i值不正确,则显示相应错误信息；否则将线性表第i个元素以后元素均向前移动一个位置,这样覆盖了原来的第i个元素,达到删除该元素的目的,最后顺序表长度减1。intListDelete(SqList*&L,inti,ElemType&e){intj;if(i1||iL-length)return0;i--;/*将顺序表逻辑位序转化为elem下标即物理位序*/e=L-data[i];for(j=i;jL-length-1;j++)L-data[j]=L-data[j+1];/*将data[i]之后的元素后前移一个位置*/L-length--;/*顺序表长度减1*/return1;}a0…ai-1ai…an-1……逻辑位序1ii+1nMaxSize对于本算法来说,元素移动的次数也与表长n和删除元素的位置i有关:当i=n时,移动次数为0；当i=1时,移动次数为n-1。在线性表sq中共有n个元素可以被删除。假设pi(pi=)是删除第i个位置上元素的概率,则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为:=因此删除算法的平均时间复杂度为O(n)。)(21)(1)(11nOninninpniniin1例2.2设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构即顺序表)的适当位置上,并保持线性表的有序性。解:先通过比较在顺序表L中找到存放x的位置i,然后将x插入到L.data[i]中,最后将顺序表的长度增1。voidInsert(SqList*&L,ElemTypex){inti=0,j;while(iL-length&&L-data