线性表的类型定义

第二章线性表,2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加,在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继,线性结构是一个数据元素的有序（次序）集,线性结构特点：,2.1线性表的类型定义：定义：一个线性表是n个数据元素的有限序列,例英文字母表（A,B,C,.Z)是一个线性表,特征：,元素个数n表长度，n=0空表1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项,线性表是一种典型的线性结构。,抽象数据类型线性表的定义如下：,ADTList数据对象：Dai|aiElemSet,i=1,2,.,n,n0称n为线性表的表长;称n=0时的线性表为空表。数据关系：R1|ai-1,aiD,i=2,.,n设线性表为(a1，a2,.，ai，.，an),称i为ai在线性表中的位序。,基本操作：,结构初始化InitList(GetElem(LB,i)e2依次在线性表LA中进行查访;LocateElem(LA,e,equal()3若不存在，则插入之。ListInsert(LA,n+1,e),voidunion(List/La中不存在和e相同的数据元素，则插入之/union,例2-2已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。voidpurge(ListLa_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取Lb中第i个数据元素赋给eif(!equal(en,e)/en初始化为LB中没有的值ListInsert(La,+La_len,e);en=e;/La中不存在和e相同的数据元素，则插入之/purge,例2-3归并两个“其数据元素按值非递减有序排列的”线性表LA和LB，求得线性表LC也具有同样特性设La=(a1,ai,an)Lb=(b1,bj,bm)Lc=(c1,ck,cm+n)则Ck=k=1,2,m+n,思路：,1分别从LA和LB中取得当前元素ai和bj；2若aibj，则将ai插入到LC中，否则将bj插入到LC中。,voidMergeList(ListLa,ListLb,List,while(i=La_len)/merge_list,2.2线性表的顺序存储结构,顺序表：定义：用一组地址连续的存储单元存放一个线性表叫元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L一个元素占用的存储单元个数LOC(ai)线性表第i个元素的地址,顺序表：,特点：实现逻辑上相邻物理地址相邻实现随机存取实现：可用C语言的一维数组实现,typedefintDATATYPE;#defineM1000DATATYPEdataM;,例typedefstructcardintnum;charname20;charauthor10;charpublisher30;floatprice;DATATYPE;DATATYPElibraryM;,数据元素不是简单类型时,可定义结构体数组,动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE);free(pData);,顺序映像的C语言描述,/-线性表的动态分配顺序存储结构-#defineLIST_INIT_SIZE80/线性表存储空间的初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量typedefstructElemType*elem;/存储空间基址intlength;/当前长度intlistsize;/当前分配的存储容量(以sizeof(ElemType)为单位)SqList;/俗称顺序表,线性表的初始化在顺序映像中的实现,StatusInitList_Sq(SqList/InitList_Sq,线性表操作LocateElem(L,e,compare()的实现：,intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/在顺序线性表L中查找第1个值与e满足compare()的元素的位序。/若找到，则返回其在L中的位序，否则返回0。,i=1;/i的初值为第1元素的位序p=L.elem;/p的初值为第1元素的存储位置while(i=L.length/LocateElem_Sq,此算法的时间复杂度为:O(ListLength(L),线性表操作ListInsert(/存储分配失败L.elem=newbase;/新基址L.listsize+=LISTINCREMENT;/增加存储容量q=/ListInsert_Sq,算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,线性表操作ListDelete(&L,i,&e)的实现：,问：删除元素时，线性表的逻辑结构发生什么变化？(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an),思路：,1、删除位置的合法性检查2、删除元素的提取3、从pos+1号到n号元素前移4、长度减1。,StatusListDelete_Sq(SqList/ListDelete_Sq,算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数