《数据结构用C语言描述》第二章.ppt

《《数据结构用C语言描述》第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二章线性表线性表顺序表链表顺序表与链表的比较线性表定义：n（0）个数据元素的有限序列，记作（a1,…ai-1,ai,ai+1,…,an）其中,ai是表中数据元素，n是表长度。特点:同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。线性表的基本操作1）SETNULL(L)初始化，构造一个空的线性表2）LENGTH(L)求长度,返回线性表中数据元素个数3）GET(L,i)取表L中第i个数据元素赋值4）LOCATE(L,x)按值查找，若表

2、中存在一个或多个值为x的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。5）INSERT(L,x,i)在L中第i个位置前插入新的数据元素x，表长加1。6）DELETE(L,i)删除表中第i个数据元素，e返回其值，表长减1。复杂运算可以通过基本运算的组合实现例：利用线性表的基本运算实现清除表L中多余的重复结点PURGE(Linear_list*L){inti=1,j,x,y;while(i

3、sej++;}i++;}}顺序表定义：将线性表中的元素相继存放在一个连续的存储空间中。存储结构：数组。特点：线性表的顺序存储方式。存取方式：顺序存取顺序存储结构示意图458990674078012345顺序表的存储方式：LOC(ai)=LOC(a1)+(i-1)*la1a2…ai………an12…i………naa+l…a+(i-1)*l………a+(n-1)*lidle顺序表（Sequenlist）的类型定义#definemaxsize1024//最大允许长度typedefintdatatype;typedefstruct{datatypedata[maxsize

4、];//存储空间基址intlast;//当前元素个数}sequenlist;sequenlist*L;顺序表基本运算按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1intLOCATE(sequenlist*L,datatypex){inti=0;while(i<(*L).last&&(*L).data[i]!=x)i++;if(i<(*L).last)returni;elsereturn-1;}求表的长度intLength(sequenlist*L){return(*L).last+1;}提取函数：在表中提取第i个元素的值datatype

5、Get(sequenlist*L,inti){if(i>=0&&i<(*L).last)return(*L).data[i];elseprintf(“参数i不合理！”);}插入253457164809630123456750插入x25345750164809630123456750i顺序表的插入intInsert(sequenlist*L,datatypex,inti){intj;//在表中第i个位置插入新元素xif(i<0

6、

7、i>(*L).last

8、

9、(*L).last>=maxsize-1)return0;//插入不成功else{for(j=

10、(*L).last;j>=i-1;j--)(*L).data[j]=(*)L.data[j-1];(*L).data[i]=x;(*L).last++;return1;//插入成功}}顺序表插入时，平均数据移动次数AMN在各表项插入概率相等时平均时间复杂度：T(n)=O(n)253457164809630123456750插入x25345750164809630123456750i删除253457501648096316删除x2534575048096301234567顺序表的删除intDELETE(sequenlist*L,inti){in

11、tj;//在表中删除第i个元素xif((i<1)

12、

13、(i>(*L).last+1)){printf(“error”);returnnull;//非法位置else{for(j=i;j<=(*L).last;j++)(*L).data[j-1]=(*L).data[j];(*L).last--;}return(1);//成功删除}顺序表的删除intDELETE(sequenlist*L,datatypex){inti,j;//在表中删除已有元素xi=LOCATE(L,x);//在表中查找xif(i>=0){(*L).last--;for(j=i;j

14、;j++)(*L).data[j]=(*L).dat