-数据结构考研笔记.docVIP

第二章 线性表 从第二章到第四章是线性结构。 线性结构的特点是：在数据元素的非空有限集中 存在唯一的一个被称做“第一个”的数据元素； 存在唯一的一个被称做“最后一个”的数据元素； 除第一个之外，集合中和每个元素均只有一个前驱； 除最后一个之外，集合中每个数据元素均只有一个后继。 2．1 线性表的类型定义： ADT List { 数据对象：D={ai| ai∈Elemset,i=1,2,…,n,n0} 数据关系：R1={ ai-1, ai| } 基本操作： Initlist(L) 操作结果：构造一个空的线性表L。 DestroyList(L) 初始条件：线性表L已存在。 cearlist(l) listempty(L) listlength(L) getelem(L,I,e) LocateElem(L,e,compare()) PriorElem(L,cur_e,pre_e) NextElem(L,cur_enext_e) listInsert(L,I,e) listdelete(L,I,e) ListTraverse(L,visit()) }ADT List 例2-1 利用线性表 表示两个集合A和B， 现在要求一个新的集合A=A∪B。 算法 void union (List La,List Lb) { La_len=listgength(La); Lb_len=Listlength(Lb); For(i=1;i=Lb_len;i++) {getElem(Lb,I,e); if(!LocateElem(la,e,equal)) ListInsert(La,++La_len,e); } }//union 例2-2 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC， 算法： void MergeList(List La, List Lb, List Lc) { InitList(Lc); I=j=1;k=0; La_len=ListLength(La);Lb_len=ListLength(Lb); While((i=La_len)(j=Lb_len)) GetElem(La,I,ai); GetElem(Lb,j,bj); If(ai=bj) {ListInsert(Lc,++k,ai);++I;} Else{ListInsert(Lc,++k,by);++j;} } while(i=La_len){ GetElem(La,++i,ai); ListInsert(Lc,++k,ai);} While(j=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);} } }//MergeList 线性表的动态分配顺序存储结构： #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; Int length; Int listsize; } SqList; 构造一个空的线性表L。 Status InitList_Sq(SqList L){ L．elem=(ElemType*)malloc(List_INIT_SIZE*sizeof(ElemType)); If(!L.elem)exit(OVERFLOW); //存储分配失败 L.length=0; L.listsize=LIST_INIT_SIZE; Return ok; }//InitList_Sq 算法2.4 在顺序表L中第I个位置之前插入一个元素 Status ListInsert_sq(SqList L,int I, ElemTyp