线性表顺序表 链表一元多项式顺序表与链表的比较.ppt

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

1、线性表顺序表链表一元多项式顺序表与链表的比较第二章线性表线性表(LinearList)线性表的定义和特点定义n（0）个数据元素的有限序列，记作（a1,a2,…,an）ai是表中数据元素，n是表长度。遍历逐项访问：从前向后从后向前线性表的特点除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。a1a2a3a4a5a6顺序表(SequentialList)顺序表的定义和特点定义将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构

2、特点线性表的顺序存储方式遍历顺序访问,可以随机存取253457164809123456elem顺序表的连续存储方式3527491860547783410212345678910llllllllllLOC(i)=LOC(i-1)+l=a+(i-1)*lLOC(i)=LOC(i-1)+l=a+(i-1)*l,i>1a,i=1a+(i-1)*la顺序表(SeqList)的定义#defineListSize100//最大允许长度typedefintElemType;typedefstruct{ElemType*ele

3、m;//存储数组intlength;//当前元素个数}SeqList;顺序表基本运算的实现构造一个空的顺序表voidInitList(SeqList&L){L.elem=newElemType;if(L.elem==NULL){printf(“存储分配失败!”);exit(1);}L.length=0;}求表的长度intLength(SeqList&L){returnL.length;}提取函数：在表中提取第i个元素的值ElemTypeGetData(SeqList&L,inti){if(i>=1&&i<

4、=L.length)returnL.elem[i];elseprintf(“参数i不合理！”);}//在出错情况，函数返回值不能用！按值查找：在顺序表中从头查找结点值等于给定值x的结点intFind(SeqList&L,ElemTypex){inti=1;ElemType*p=L.elem;while(p!=NULL&&*p!=x){i++;p++;}if(i<=L.length)returni;elsereturn0;}按值查找：在顺序表中从头查找结点值等于给定值x的结点intFind(SeqList&

5、L,ElemTypex){inti=1;while(i<=L.length&&L.elem[i]!=x)i++;if(i<=L.length)returni;elsereturn0;}顺序查找图示253457164809123456elem查找16i253457164809i253457164809i253457164809i查找成功253457164812345elem查找50i2534571648i2534571648i2534571648i2534571648i查找失败查找成功的平均比较次数若查找

6、概率相等，则查找不成功数据比较n次表项的插入2534571648096312345678elem50插入x253457501648096312345678elem50i表项的插入intInsert(SeqList&L,ElemTypex,inti){//在表中第i个位置插入新元素xif(i<1

7、

8、i>L.length+1

9、

10、L.length==ListSize)return0;//插入不成功else{for(intj=L.length;j>=i;j--)L.elem[j+1]=L.elem[j];L.

11、elem[i]=x;L.length++;return1;//插入成功}}表项的删除253457501648096312345678elem16删除x2534575048096312345678elem表项的删除intDelete(SeqList&L,ElemTypex){//在表中删除已有元素xinti=Find(L,x);//在表中查找xif(i>=1){L.length--;for(intj=i;j<=L.length;j++)L.elem[j]=L.elem[j+1];return1;//成功

12、删除}return0;//表中没有x}顺序表的应用：集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=1;i<=m;i++){intx=GetData(B,i);//在B中取一元素intk=Find(A,x);//在A中查找它if(k==0)//若未找到插入它{Insert(A,x,n);n++