资源描述：
《-数据结构考研笔记》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、易考网（chinakao.cn）-易考网，优秀的考试资源整合服务商！！7×24全天候客服热线：86-22-89761734，89761570，网址：http://www.chinakao.cn第二章线性表从第二章到第四章是线性结构。线性结构的特点是：在数据元素的非空有限集中（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中和每个元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。2．1线性表的类型定义：ADTList{数据对象：D={ai
2、ai∈Elemset,i=1,2,…,n,n>0}
3、数据关系：R1={
4、}基本操作：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_e&next_e)listInsert(&L,I,e)listdelete(&L,I,&e)ListTraverse(L,visit())}ADTList例2-1利用线性表表示两个集合A和B，现在
5、要求一个新的集合A=A∪B。算法voidunion(List&La,ListLb){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，算法：voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);I=j=
6、1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);While((i<=La_len)&&(j<=Lb_len))要考试？上易考网！第68页易考网（chinakao.cn）-易考网，优秀的考试资源整合服务商！！7×24全天候客服热线：86-22-89761734，89761570，网址：http://www.chinakao.cnGetElem(La,I,ai);GetElem(Lb,j,bj);If(ai<=bj){ListInsert(Lc,++k,ai);++I;}Else{ListInsert(Lc,++k,by);++j;}}w
7、hile(i<=La_len){GetElem(La,++i,ai);ListInsert(Lc,++k,ai);}While(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}}//MergeList线性表的动态分配顺序存储结构：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;Intlength;Intlistsize;}SqList;构造一个空的线性表L。StatusInitList_Sq(SqList&L){L．elem=(
8、ElemType*)malloc(List_INIT_SIZE*sizeof(ElemType));If(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;L.listsize=LIST_INIT_SIZE;Returnok;}//InitList_Sq算法2.4在顺序表L中第I个位置之前插入一个元素StatusListInsert_sq(SqList&L,intI,ElemTypee){if(i<1
9、
10、i>L.length+1)returnError;if(L.length>=L.lostsize)newbase=(ElemType*)realloc
11、(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnok;}//ListInsert_Sq算法2.5在顺序线性表L中删除第I个
