线性表顺序表 链表顺序表与链表的比较.ppt

《线性表顺序表 链表顺序表与链表的比较.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、线性表顺序表链表顺序表与链表的比较第二章线性表线性表(LinearList)定义n（0）个数据元素的有限序列，记作L=（a1,a2,…,an）ai是表中数据元素，n是表长度。n=0是为空表§2.1线性表的基本概念线性表的逻辑结构除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。a1a2a3a4a5a6线性结构ADTList{数据对象:D={ai

2、1in,n0,ai属Elemtype类型数据关系:R1={

3、ai,ai+

4、1D,i=1,2,…,n-1}基本运算:InitList(&L);DestroyList(&L);ListEmpty(L);ListLength(L):DispList(L);GetElem(L,i,&e);LocateElem(L,e);ListInsert(&L,i,e);ListDelete(&L,i,&e);}抽象数据类型线性表的定义例：清除线性表L中多余的重复元素L=（2，10，2，6，9，2，6）依次处理aii=1,2,3…..扫描其后所有元素ajj=i+1,i+2,…..ai=ajai≠a

5、jj=j+1扫描下一个删除aj?j=j+1Purge(ListL){i=1;while(i

6、素放入LC中，依次处理LB中每一个元素bi,i=1,2,3,….,检查LA中是否存在bi，若无，则将bi插入到LC中。UnionList(ListLA,ListLB,List&LC){InitList(LC);for(i=1;i<=ListLength(LA);i++){GetElem(LA,i,e);ListInsert(LC,i,e);}lena=ListLenth(LA);for(i=1;i<=ListLength(LB);i++){GetElem(LB,i,e);if(！LocateElem(LA

7、,e))ListInsert(LC,++lena,e);}}在这些基本运算的基础上，可以解决更复杂的问题。基本运算的实现完全取决于存储结构。不同的存储方式，基本运算的实现效益也不同§2.2线性表的顺序存储结构顺序表(SequentialList)：即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。可利用一维数组描述存储结构a1a2a3a4a5a6123456data顺序表的连续存储方式ccccccccccLOC(ai)=LOC(a1)+(i-1)*cLOC(ai)=LOC(ai-1)+c,i>

8、0a,i=1a+(i-1)*ca1a2a3aian1234inmaxsizea顺序表(SeqList)的定义#defineMaxSize10//最大允许长度typedefstruct{Elemtypedata[MaxSize+1];//存储数组intlength;//终端结点在数组的位置}SqList;顺序表基本运算的实现构造一个空的顺序表voidInitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));L->length=0;return(L);}T(n

9、)=O(1)求表的长度intListLength(SqList*L){return(L->length);}提取函数：在表中提取第i个元素的值boolGetElem(SqList*L,inti,ElemTypee){if(i<1&&i>L->length)returnfalse;e=L->data[i-1]);returntrue;}顺序查找图示253457164809123456data查找16i253457164809i253457164809i253457164809i查找成功25345716481

10、2345data查找50i2534571648i2534571648i2534571648i2534571648i查找失败按值查找：在顺序表中从头查找结点值等于给定值x的结点intLocateElem(SqList*L,ElemTypee){inti=1;while(ilength&&L->data[i]!=e)i++;if(i>=L->length)return0;elsereturni+1;}时间性能分析最好情况：