线性表的逻辑结构及其基本操作线性表的顺序存储结构线性表.ppt

《线性表的逻辑结构及其基本操作线性表的顺序存储结构线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、线性表的逻辑结构及其基本操作线性表的顺序存储结构线性表的链式存储结构静态链表应用实例第二章线性表7/27/202112.1.线性表的逻辑结构及其基本操作线性表是n(n>=0)个相同类型数据元素a0,a1,…，an-1构成的有限序列。形式化定义：Linearlist=(D,R)其中：D0为某个数据对象的集合N为线性表长度7/27/20212线性表的主要操作初始化求长度取元素定位插入删除7/27/20213例：利用线性表的基本运算实现清除L中多余的重复节点。PURGE(Linear_list*L){inti=1,j,x,y;while(i

2、L,i);j=i+1;while(j<=LENGTH(L)){y=GET(L,j);if(x==y)DELETE(L,j);elsej++;}i++;}}7/27/202142.2线性表的顺序存储结构--顺序表设线性表的基地址为：LOC(a1),ai的存储地址为：LOC(ai)=LOC(a0)＋i*k1<=i<=na0a1aian-1……a0a1aian-1……01n-1Loc(a0)Loc(a0)+kiLoc(a0)+i*kLoc(a0)+(n-1)*k7/27/20215线性表的定义为：typedefintdatatype;//假定线性表元素的类型为整型#defin

3、emaxsize1024//假定线性表的最大长度为1024typedefstruct{datatypedata[maxsize];intlast;//指向最后结点的位置}sequenlist;7/27/202161、先定义结构类型，再定义变量名structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}；Structstudentstudent1,student2;C语言中定义结构的方法7/27/202172、在声明类型的同时定义结构变量structstudent{intnum;ch

4、arname[20];charsex;intage;floatscore;charaddr[30];}student1,student2;7/27/202183、直接定义结构变量struct{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}student1,student2;7/27/20219例：#defineMAXSIZE<最大元素个数>typedefstruct{charName[20];charSex;intAge;floatfareAmount;}datatype;7/27/202110线

5、性表元素的插入（在线性表L中第i个位置前插入新元素x）intINSERT(sequenlist*L,datatypex,inti){intj;if(((*L).last)>=maxsize－1){printf(“overflow”);returnNULL;}//溢出elseif((i<1)

6、

7、(i>((*L).last)＋1){printf(“error”);returnNULL;}//非法位置else{for(j=(*L).last;j>=i-1;j--)(*L).data[j+1]＝(*L).data[j];(*L).data[i-1]＝x;(*L).las

8、t＝(*L).last+1;}return(1);}7/27/202111线性表元素的删除（在线性表L中删除第i个元素）intDELETE(sequenlist*L,inti){intj;if((i<1)

9、

10、(i>(*L).last+1)){printf(“error”);returnNULL;}//非法位置else{for(j=i;j<=(*L).last;j++)(*L).data[j-1]＝(*L).data[j];(*L).last--;//表长减1}return(1);}7/27/2021121、插入n/22、删除(n-1)/23、按序号检索O(1)4、按

11、内容检索n/2算法复杂性分析7/27/202113顺序表的优点：无须为表示节点间的逻辑关系而增加额外的存储空间可以方便的随机存取表中的任一节点顺序表的缺点：插入和删除运算不方便由于要求占用连续的存储空间，存储分配只能预先进行7/27/2021142.3线性表的链式存储hh不带头节点的链表带头节点的链表7/27/202115单链表结点的定义：typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;节点的申请p＝malloc(sizeof(link