基本数据结构及其运算-02顺序表

《基本数据结构及其运算-02顺序表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.2线性表及其顺序存储结构一、线性表及其运算线性表定义：n（0）个数据元素的有限序列，记作（a1,…ai-1,ai,ai+1,…,an）其中,ai是表中数据元素，n是表长度。特点:同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。顺序表定义：将线性表中的元素相继存放在一个连续的存储空间中。存储结构：数组。特点：线性表的顺序存储方式。存取方式：随机存取顺序存储结构示意图458990674078012345顺序表的

2、存储方式：LOC(ai+1)=LOC(a1)+(i-1)*lLOC(ai)=LOC(a1)+(i-1)*la1a2…ai………an12…i………naa+l…a+(i-1)*l………a+(n-1)*lidle顺序表（SeqList）的类型定义#defineListSize100//最大允许长度typedefintListData;typedefstruct{ListDatadata[listsize];//存储空间基址intlength;//当前元素个数}SeqList;顺序表基本运算初始化voidInitList(SeqList&L){

3、L.data=(ListData*)malloc(sizeof(SEQList));if(L.data==NULL){printf(“存储分配失败!”);exit(1);}L.length=0;}按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1intFind(SeqListL,ListDatax){inti=0;while(i

4、nL.length;}提取函数：在表中提取i号个元素的值ListDataGetData(SeqList&L,inti){if(i>=0&&i=0&&i

5、inti=Find(L,x);if(i>0&&i

6、

7、i>L.length

8、

9、L.length==ListSize)return0;//插入不成功el

10、se{for(j=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.length--;for(intj=i;j

11、ength;j++)L.data[j]=L.data[j+1];return1;//成功删除}return0;//表中没有x}顺序表的应用:集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i

12、on(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(i