线性结构的基本特征为:2.1线性表的类型定义2.1线性表的类型定义抽象数据类型线性表的定义如下：基本操作：InitList(&L)结构销毁操作ListEmpty(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())加工型操作ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)利用上述定义的线性表可以实现其它更复杂的操作假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．从线性表LB中依次察看每个数据元素;GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之已知一个非纯集合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-2已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍然按非递减有序排列。voidMergeList(ListLa,ListLb,List&Lc){//本算法将非递减的有序表La和Lb归并为Lc}//merge_list//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;}while(i<=La_len){//当La不空时GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}//插入La表中剩余元素2.2线性表类型的实现----顺序映象最简单的一种顺序映象方法是：令y的存储位置和x的存储位置相邻。用一组地址连续的存储单元依次存放线性表中的数据元素以“存储位置相邻”表示有序对<ai-1，ai>即：LOC(ai)=LOC(ai-1)+C一个数据元素所占存储量↑顺序映像的C语言描述线性表的基本操作在顺序表中的实现StatusInitList_Sq(SqList&L){//构造一个空的线性表}//InitList_Sq例如：顺序表intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序表中查询第一个满足判定条件的数据元素，//若存在，则返回它的位序，否则返回0}//LocateElem_Sq线性表操作ListInsert(&L,i,e)的实现：(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L的第i个元素之前插入新的元素e,//i的合法范围为1≤i≤L.length+1}//ListInsert_Sq考虑移动元素的平均情况:if(L.length>=L.listsize){//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L