第二章线性表第二章线性表2．1线性表的类型定义线性表的抽象数据类型(ADT)InitList(&L);DestroyList(&L);ClearList(&L);ListEmpty(L);ListLength(L);GetElem(L,i,&e);LocateElem(L,e,compare());PriorElem(L,cur_e,&pre_e);NextElem(L,cur_e,&next_e);ListInsert(&L,i,e);ListDelete(&L,i,&e);ListTraverse(&L,visited())InitList(&L)操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:线性表L已经存在。操作结果:销毁线性表L。ClearList(&L)初始条件:线性表L已经存在。操作结果:将线性表L重置为空表。ListEmpty(L)初始条件:线性表L已经存在。操作结果:若线性表L为空表，则返回TURE;否则返回FALSE。ListLength(L)初始条件:线性表L已经存在。操作结果:返回线性表L中的数据元素个数。GetElem(L,i,&e)；初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:用e返回线性表L中第i个数据元素的值。LocateElem(L,e,compare())初始条件:线性表L已经存在，compare()是数据元素判定函数。操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。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无意义。ListInsert(&L,i,e)初始条件:线性表L已经存在，1<=i<=ListLength(L)+1。操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加一。插入前（长度为n）:（a1,a2,…,ai-1,ai,…,an）插入后（长度为n+1）:（a1,a2,…,ai-1,e,ai,…,an）ListDelete(&L,i,&e)初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减一。删除前（长度为n）:（a1,a2,…,ai-1,ai,ai+1,…,an）删除后（长度为n-1）:（a1,a2,…,ai-1,ai+1,…,an）基本操作(七)：例2-1线性表La,Lb的合并.La=La∪Lb.(算法2.1)算法描述：例2-1线性表La,Lb的合并.已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。集合Bvoidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);}//union若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)。例如：（2，3，3，5，6，6，6，8，12）voidpurge(List&La,ListLb){InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){}}//purge例2-3非递减线性表La,Lb的合并.Lc=La∪Lb.(算法2.2)非递减线性表La,Lb的合并的C程序(一)非递减线性表La,Lb的合并的C程序(续)线性表（a1,a2,…,ai,ai+1,…,an）的顺序表示----用一组地址连续的存贮单元依次存贮线性表的数据元素.设ι为每个数据元素所需的存储大小Loc(ai+1)=Loc(ai)+ιLoc(ai)=Loc(a1)+(i-1)*ι线性表的顺序表示(图示)顺序映像的C语言描述StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)