数据结构chap002

线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。线性结构是一个数据元素的有序（次序）集线性表是一种最简单的线性结构2.1线性表的类型定义2.3线性表类型的实现链式映象2.4一元多项式的表示2.2线性表类型的实现顺序映象2.1线性表的类型定义抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：结构初始化操作结构销毁操作引用型操作加工型操作}ADTListInitList(&L)操作结果：构造一个空的线性表L。初始化操作结构销毁操作DestroyList(&L)初始条件：操作结果：线性表L已存在。销毁线性表L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作:ListEmpty(L)初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）ListLength(L)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）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无定义。（求数据元素的后继）GetElem(L,i,&e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)。用e返回L中第i个元素的值。（求线性表中某个数据元素）LocateElem(L,e,compare())初始条件：操作结果：线性表L已存在，e为给定值，compare()是元素判定函数。返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）ListTraverse(L,visit())初始条件：操作结果：线性表L已存在，Visit()为某个访问函数。依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）加工型操作ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）PutElem(&L,i,&e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）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。（删除数据元素）利用上述定义的线性表可以实现其它更复杂的操作例2-2例2-3例2-1假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。例2-1要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。上述问题可演绎为：1．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。GetElem(LB,i)→eLocateElem(LA,e,equal())ListInsert(LA,n+1,e)操作步骤：GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之voidunion(List&La,ListLb){La_len=ListLength(La);//求线性表的长度Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){}}//union已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。仍选用线性表表示集合。例2-2集合B集合A从集合B取出物件放入集合A要求集合A中同样物件不能有两件以上因此，算法的策略应该和例2-1相同voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);}//unionGetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之for(i=1;i=Lb_len;i++){}InitList(La);//构造(空的)线性表LA若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)。试改变结构，以有序表表示集合。例如：（2，3，3，5，6，6，6，8，12）对集合B而言，值相同的数据元素必定相邻；对集合A而言，数据元素依值从小至大的顺序插入。因此，数据结构改变了，解决问题的策略也相应要改变。voidpurge(List&La,ListLb){InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i=Lb_len;i++){}}//purgeGetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(ListEmpty(La)||!equal(en,e)){ListInsert(La,++La_len,e);en=e;}//La中不存在和e相同的数据元素，则插入之//La和Lb均非空，i=j=1,k=0GetElem(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;}voidMergeList(ListLa,ListLb,List&Lc){//本算法将非递减的有序表La和Lb归并为Lc}//merge_listwhile((i=La_len)&&(j=Lb_len)){//La和Lb均不空}while(i=La_len)//若La不空while(j=Lb_len)//若Lb不空InitList(Lc);//构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len){//当La不空时GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}//插入La表中剩余元素while(j=Lb_len){//当Lb不空时GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}//插入Lb表中剩余元素最简单的一种顺序映象方法是：令y的存储位置和x的存储位置相邻。顺序映象——以x的存储位置和y的存储位置之间某种关系表示逻辑关系x,y。用一组地址连续的存储单元依次存放线性表中的数据元素a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址以“存储位置相邻”表示有序对ai-1，ai即：LOC(ai)=LOC(ai-1)+C一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)×C↑基地址顺序映像的C语言描述typedefstruct{}SqList;//俗称顺序表#defineLIST_INIT_SIZE80//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量//(以sizeof(ElemType)为单位)线性表的基本操作在顺序表中的实现InitList(&L)//结构初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//删除元素StatusInitList_Sq(SqList&L){//构造一个空的线性表}//InitList_Sq算法时间复杂度：O(1)L.elem=(ElemType*)malloc(LIST_INIT_SIZEsizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;例如：顺序表23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可见，基本操作是：将顺序表中的元素逐个和给定值e相比较。intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序表中查询第一个满足判定条件的数据元素，//若存在，则返回它的位序，否则返回0}//LocateElem_SqO(ListLength(L))算法的时间复杂度为：i=1;//i的初值为第1元素的位序p=L.elem;//p的初值为第1元素的存储位置while(i=L.length&&!(*compare)(*p++,e))++i;if(i=L.length)returni;elsereturn0;(*compare)(*p++,e)线性表操作ListInsert(&L,i,e)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)a1a2…ai-1ai…ana1a2…ai-1…aieanai-1,aiai-1,e,e,ai表的长度增加StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L的第i个元素之前插入新的元素e,//i的合法范围为1≤i≤L.length+1}//ListInsert_Sq算法时间复杂度为:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;……元素右移考虑移动元素的平均情况:假设在第i个元素之前插入的概率