CH2 线性表.ppt

《CH2 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中每个数据元素均只有一个前驱除最后一个外，集合中每个数据元素均只有一个后继2.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素例一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内

2、部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。特征：元素个数n—表长度，n=0空表1

3、ai∈ElemSet,i=1,2,…,n,n>=0}数据关系：Rl={〈ai-1，ai〉

4、ai-1，ai∈D，i=1,2,…,n}基本操作：InitList(&L)DestroyList(&

5、L)ClearList(&L)ListEmpty(L)ListLength(L)GetElemList(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例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(

6、La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}算法的时间复杂度：O（ListLength(LA)×ListLength(LB)）算法2.2例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：voidmergelist(listla，listlb，list&lc){initlist(lc

7、);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，bj);++j;}}while(I<=la-len){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);list

8、insert(lc，++k，bi);}}算法的时间复杂度：O（ListLength(LA)+ListLength(LB)）2.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1typedefintDATATYPE;#defineM1000DATATYP

9、Edata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);由于C语言中的一维数组也是采用顺