欢迎来到天天文库
浏览记录
ID:57014453
大小:275.00 KB
页数:37页
时间:2020-07-26
《基本数据结构及其运算02顺序表课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、2.2线性表及其顺序存储结构一、线性表及其运算线性表定义:n(0)个数据元素的有限序列,记作(a1,…ai-1,ai,ai+1,…,an)其中,ai是表中数据元素,n是表长度。特点:同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外,其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。顺序表定义:将线性表中的元素相继存放在一个连续的存储空间中。存储结构:数组。特点:线性表的顺序存储方式。存取方式:随机存取顺序存储结构示意图458990674078012345顺序表的存储方式:LO
2、C(ai+1)=LOC(a0)+(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){L.data=(ListDa
3、ta*)malloc(sizeof(SEQList));if(L.data==NULL){printf(“存储分配失败!”);exit(1);}L.length=0;}按值查找:找x在表中的位置,若查找成功,返回表项的位置,否则返回-1intFind(SeqList&L,ListDatax){inti=0;while(i4、取i号个元素的值ListDataGetData(SeqList&L,inti){if(i>=0&&i=0&&i0&&i5、.length)returnl.data[i-1];elsereturnnull;}插入253457164809630123456750插入x25345750164809630123456750i顺序表插入时,平均数据移动次数AMN在各表项插入概率相等时顺序表的插入intInsert(SeqList&L,ListDatax,inti){//在表中第i个位置插入新元素xif(i<06、7、i>L.length8、9、L.length==ListSize)return0;//插入不成功else{for(j=L.length;j>i;j--)L.data[10、j]=L.data[j-1];L.data[i]=x;L.length++;return1;//插入成功}}删除253457501648096316删除x2534575048096301234567顺序表删除平均数据移动次数AMN在各表项删除概率相等时顺序表的删除intDelete(SeqList&L,ListDatax){//在表中删除已有元素xinti=Find(L,x);//在表中查找xif(i>=0){L.length--;for(intj=i;j11、//成功删除}return0;//表中没有x}顺序表的应用:集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i12、gth(B);inti=0;while(i
4、取i号个元素的值ListDataGetData(SeqList&L,inti){if(i>=0&&i=0&&i0&&i5、.length)returnl.data[i-1];elsereturnnull;}插入253457164809630123456750插入x25345750164809630123456750i顺序表插入时,平均数据移动次数AMN在各表项插入概率相等时顺序表的插入intInsert(SeqList&L,ListDatax,inti){//在表中第i个位置插入新元素xif(i<06、7、i>L.length8、9、L.length==ListSize)return0;//插入不成功else{for(j=L.length;j>i;j--)L.data[10、j]=L.data[j-1];L.data[i]=x;L.length++;return1;//插入成功}}删除253457501648096316删除x2534575048096301234567顺序表删除平均数据移动次数AMN在各表项删除概率相等时顺序表的删除intDelete(SeqList&L,ListDatax){//在表中删除已有元素xinti=Find(L,x);//在表中查找xif(i>=0){L.length--;for(intj=i;j11、//成功删除}return0;//表中没有x}顺序表的应用:集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i12、gth(B);inti=0;while(i
5、.length)returnl.data[i-1];elsereturnnull;}插入253457164809630123456750插入x25345750164809630123456750i顺序表插入时,平均数据移动次数AMN在各表项插入概率相等时顺序表的插入intInsert(SeqList&L,ListDatax,inti){//在表中第i个位置插入新元素xif(i<0
6、
7、i>L.length
8、
9、L.length==ListSize)return0;//插入不成功else{for(j=L.length;j>i;j--)L.data[
10、j]=L.data[j-1];L.data[i]=x;L.length++;return1;//插入成功}}删除253457501648096316删除x2534575048096301234567顺序表删除平均数据移动次数AMN在各表项删除概率相等时顺序表的删除intDelete(SeqList&L,ListDatax){//在表中删除已有元素xinti=Find(L,x);//在表中查找xif(i>=0){L.length--;for(intj=i;j11、//成功删除}return0;//表中没有x}顺序表的应用:集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i12、gth(B);inti=0;while(i
11、//成功删除}return0;//表中没有x}顺序表的应用:集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i12、gth(B);inti=0;while(i
12、gth(B);inti=0;while(i
此文档下载收益归作者所有