自学数据结构课件--线性表资料.ppt

《自学数据结构课件--线性表资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自学数据结构课件--线性表顺序表定义：将线性表中的元素相继存放在一个连续的存储空间中。存储结构：数组。特点：线性表的顺序存储方式。存取方式：顺序存取、随机存取顺序存储结构示意图458990674078012345顺序表的存储方式：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*la1a2…ai………an12…i………naa+l…a+(i-1)*l………a+(n-1)*lidle顺序表（SeqList）的类型定义#defineListSize100//最大允许长度typedefintListData;typedefstruct{List

2、Data*data;//存储空间基址intlength;//当前元素个数}SeqList;顺序表基本运算初始化voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存储分配失败!”);exit(1);}L.length=0;}按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1intFind(SeqList&L,ListDatax){inti=0;while(i

3、=x)i++;if(i

4、L.length&&!found)if(L.data[i]!=x)i++;elsefound=1;returnfound;}求表的长度intLength(SeqList&L){returnL.length;}提取函数：在表中提取第i个元素的值ListDataGetData(SeqList&L,inti){if(i>=0&&i0&&i

5、eturni+1;elsereturn-1;}寻找x的前驱intPrevious(SeqList&L,ListDatax){inti=Find(x);if(i>0&&i

6、

7、i>L.length

8、

9、L.

10、length==ListSize)return0;//插入不成功else{for(intj=L.length;j>i;j--)L.data[j]=L.data[j-1];L.data[i]=x;L.length++;return1;//插入成功}}删除253457501648096316删除x2534575048096301234567顺序表删除平均数据移动次数AMN在各表项删除概率相等时顺序表的删除intDelete(SeqList&L,ListDatax){//在表中删除已有元素xinti=Find(L,x);//在表中查找xif(i>=0){L.leng

11、th--;for(intj=i;j