第二章线性表讲义――数据结构

BUPT课堂练习for(i=2;i=n;++i){for(j=2;j=i-1;++j){a[i，j]=1;}}i=2，3…n执行次数=0，1,…n-2频度=0+1+…+n-2=(n-2)(n-2+1)/2=n2/2-3n/2+1T(n)=O(n2)BUPTfor(i=3;i=n;++i){for(j=2;j=i+1;++j){a[i，j]=1;}}3+4+…+n=(n+3)(n-2)/2=BUPT线性表BUPT何谓线性结构?线性结构是一个数据元素的有序（次序）集合。四个特征：集合中必存在唯一的一个第一元素“集合中必存在唯一的一个最后元素“除最后元素之外，其它数据元素均有唯一的后继“除第一元素之外，其它数据元素均有唯一的前驱BUPT提纲线性表的定义线性表类型的实现（顺序映象）线性表类型的实现（链式映象）BUPT例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、一副扑克的点数（2，3，4，…，J，Q，K，A）BUPT线性表定义：是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，n＝0时称为空表。BUPT…….…….…….……..……..868470李四880004999095张三880003908580马二880002958590丁一880001英语物理数学姓名学号BUPT线性表的类型定义BUPT抽象数据类型线性表的定义ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai－1,ai|ai∈D,i=2,...,n}序偶，即有序对，可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。BUPT抽象数据类型线性表的定义基本操作：结构初始化InitList(*L)操作结果：构造一个空的线性表L销毁结构DestroyList(*L)初始条件：线性表L已存在操作结果：销毁线性表L可分为四类结构初始化、销毁结构引用型操作、加工型操作BUPT参数传递值传递指针传递引用传递BUPTSwap(inta,intb){inttemp;temp=a;a=b;b=temp;}Main(){intx,y;Swap(x,y);}BUPTSwap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}Main(){intx,y;Swap(&x,&y);}BUPTSwap(int*a,int*b){int*temp;temp=a;a=b;b=temp;}Main(){intx,y;Swap(&x,&y);}BUPTSwap(int&a,int&b){inttemp;temp=a;a=b;b=temp;}Main(){intx,y;Swap(x,y);}BUPTSwap(constint&a,constint&b){inttemp;temp=a;a=b;b=temp;}Main(){intx,y;Swap(x,y);}BUPT抽象数据类型线性表的定义引用型操作（6个）ListEmpty(L)初始条件：线性表L已存在操作结果：若L为空表，则返回TRUE，否则返回FALSEListLength(L)初始条件：线性表L已存在操作结果：返回L中元素个数BUPT抽象数据类型线性表的定义引用型操作（续）PriorElem(L,cur_e,*pre_e)初始条件：线性表L已存在操作结果：若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义NextElem(L,cur_e,*next_e)初始条件：线性表L已存在操作结果：若cur_e是L中的数据元素，则用next_e返回它的后继，否则操作失败，next_e无定义BUPT抽象数据类型线性表的定义引用型操作（续）GetElem(L,i,*e)初始条件：线性表L已存在1≤i≤LengthList(L)。操作结果：用e返回L中第i个元素的值。LocateElem(L,e)初始条件：线性表L已存在。操作结果：返回L中与e相等的元素的序号。若这样的元素不存在，则返回值为0。BUPT抽象数据类型线性表的定义加工型操作ClearList(*L)初始条件：线性表L已存在。操作结果：将L重置为空表。BUPT抽象数据类型线性表的定义加工型操作ListInsert(*L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(*L,i,*e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTListBUPT抽象数据类型线性表的定义例2-1已知集合A和B，求两个集合的并集，使A＝A∪B，且B不再单独存在。思路：对集合B中的所有元素一一检查，看看在集合A中是否存在相同元素，若不存在，则将该元素插入到集合A，否则舍弃之。要在计算机中求解，首先要确定“如何表示集合”。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表示集合。现假设以线性表LA和LB分别表示集合A和B，即构造两个线性表LA和LB，它们的数据元素分别为集合A和B中的成员。上述集合求并的问题演绎为：要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。BUPT抽象数据类型线性表的定义具体操作步骤为：1．从线性表LB中取出一个数据元素；2．依值在线性表LA中进行查询；3．若不存在，则将它插入到LA中。重复上述三步直至LB为空表止。对应四个基本操作1.ListDelete(LB,1,e);2.LocateElem(LA,e);3.ListInsert(LA,n+1,e)4.DestroyList(LB)BUPT抽象数据类型线性表的定义voidunion(List*LA,List*LB){//将所有在线性表LB中但不在LA中的数据元素插入到LA中,//算法执行之后，线性表LB不再存在。La_len=ListLength(LA);//求得线性表LA的长度while(!ListEmpty(LB))//依次处理LB中元素直至LB为空表止{ListDelete(LB,1,e);//LB删除第1个数据元素并赋给eif(!LocateElem(LA,e))ListInsert(LA,++La_len,e);//当LA中不存在和e值相同的数据元素时进行插入}//whileDestroyList(LB);//销毁线性表LB}//unionBUPTMain(){Lista1,a2;//初始化a1，a2；Union(a1,a2);}BUPT线性表的顺序存储表示和实现顺序表：“用一组地址连续的存储单元依次存放线性表中的数据元素”，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系(有序对ai－1,ai)”，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。BUPTABCD0x00010x00020x00030x00040x0005(A,B,C,D,…)BUPT线性表的顺序存储表示和实现LOC(ai)=LOC(ai-1)+C其中，C是一个数据元素所占存储量LOC(ai)=LOC(a1)+(i-1)×C↑基地址BUPT线性表的顺序存储表示和实现用C语言描述的顺序表类型如下所示：//存储结构constintMAXLISTSIZE=80;//预设的存储空间最大容量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//允许的最大存储容量}SqList;//俗称顺序表BUPT线性表的顺序存储表示和实现五个操作的实现一、初始化操作二、元素定位操作三、插入元素操作四、删除元素操作五、销毁结构操作BUPT线性表的顺序存储表示和实现初始化操作对顺序表而言，“初始化”的实质是为它分配一个“足够应用”的元素存储空间。BUPT线性表的顺序存储表示和实现voidInitList(SqList*L,intmaxsize){//构造一个空的线性表Lif(maxsize==0)maxsize=MAXLISTSIZE;L.elem=(ElemType*)malloc(maxsize*sizeof(ElemType));if(!L.elem)exit(1);//存储分配失败L.length=0;//顺序表的初始长度为0L.listsize=maxsize;//该顺序表可以存储元素的最大容量}//InitList•此算法的时间复杂度为O(1)。BUPT线性表的顺序存储表示和实现元素定位操作在顺序表中“查询”是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。BUPT线性表的顺序存储表示和实现intLocateElem(SqListL,ElemTypee){//在顺序表L中查找第1个值与e满足相等条件的元素//若找到，则返回其在L中的位序，否则返回0。i=1;//i的初值为第1元素的位序p=L.elem;//p的初值为第1元素的存储位置while(i=L.length&&!equal(*p++,e))++i;//依次进行判定if(i=L.length)returni;//找到满足判定条件的数据元素为第i个元素elsereturn0;//该线性表中不存在满足判定的数据元素}//LocateElemBUPT线性表的顺序存储表示和实现插入元素操作“插入元素”使线性表的逻辑结构发生什么变化？假设在线性表的第i个元素之前插入一个元素e，使得线性表(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,)(1)改变了表中元素之间的关系,使ai-1,ai改变为ai-1,e和e,ai(2)表长增1.BUPT线性表的顺序存储表示和实现boolListInsert(SqList*L,intpos,ElemTypee){//若存储空间不满且1≤pos≤Listlength(L)+1，则在顺序表L//第pos个元素之前插入e且返回TRUE，否则返回FALSEif(pos1||posL.length+1)returnFALSE;//插入位置不合法if(L.length=L.listsize)returnFALSE;//当前存储空间已满，无法插入for(j=L.length-1;j=pos-1;--j)L.elem[j+1]=L.elem[j];//插入位置及之后元素右移L.elem[pos-1]=e;//插入e++L.length;//表长增1returnTRUE;}//ListInsert时间复杂度为：O(ListLength(L))BUPTa1a2ai-1aiai+1ana1a2ai-1xaiai+1an01i-2i-1in-1n插入前插入后BUPT线性表的顺序存储表示和实现删除元素操作“删除元素”使线性表的逻辑结构发生什么变化？假设删除线性表中第i个元素，使得线性表(a1,…,ai-1,ai,ai+1…,an)改变为(a1,…,ai-1,ai+1,…,an)(1)改变了表中元素之间的关系，使ai-1,ai和ai,ai+1改变为ai-1,ai+1(2)表长减1BUPT线性表的顺序存储表示和实现boolListDelete(SqList*L,intpos,ElemType*e){//若1≤pos≤Listlength(L)，以e带回从L中删除的//第pos个元素且返回TRUE，否则返回FALSEif((pos1)||(posL.length))returnFALSE;//删除位置不合法for(j=pos;jL.length;++j)L.e