数据结构-线性表ppt课件.ppt

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

1、定义：n(n0)个数据元素的有限序列，记作L=(D,R)D=(a1,…ai-1,ai,ai+1,…,an)R={

2、ai-1,aiD,2in}其中,ai是表中数据元素，n(n0)是表长度,n=0为空表。2.2线性表特点：ai是抽象符号，在不同的数据对象中有不同含义i表示数据元素序号，表示元素在线性表中位置。同一线性表中元素具有相同特性。相邻数据元素之间存在序偶关系。除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。2.2线性表逻辑结构：线性结构物理结构：向量（顺序存储）链表（链式存储）

3、无序表和有序表：升序(递增)ai≥ai-1降序(递减)ai≤ai-1(2≤i≤n)基本运算：置空、求长度、取结点、定位、插入、删除、查找、排序等。2.2线性表定义：将线性表中的元素相继存放在一个连续的存储空间中(线性表的顺序存储方式)。存储结构：一维数组。存取方式：随机存取特点：逻辑上相邻的结点其物理位置亦相邻。顺序存储结构示意图：4589906740780123452.2.2顺序表顺序表的存储方式：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*la1a2…ai………an12…i………naa+l…a+(i-1)*l………a+(n-1)*l

4、idle2.2.2顺序表顺序表(SeqList)的类型定义#defineListSize100//最大允许长度typedefintListData;typedefstruct{ListData*data;//存储空间基址intlength;//当前元素个数}SeqList;2.2.2顺序表顺序表基本运算初始化voidInitList(SeqList&L){L.data=(ListData*)malloc(ListSize*sizeof(ListData));if(L.data==NULL){printf(“存储分配失败!”);exit(1);}L.length=0;}2

5、.2.2顺序表按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1intFind(SeqList&L,ListDatax){inti=0;while(i

6、表求表的长度intLength(SeqList&L){returnL.length;}提取函数：在表中提取第i个元素的值ListDataGetData(SeqList&L,inti){if(i>=0&&i＝0&&i

7、stDatax){inti=Find(x);if(i>0&&i

8、

9、i>L.length

10、

11、L.length==ListSize

12、)return0;//插入不成功else{for(intj=L.length;j>i;j--)L.data[j]=L.data[j-1];L.data[i]=x;L.length++;return1;//插入成功}}2.2.2顺序表删除253457501648096316删除x2534575048096301234567顺序表删除，在各表项删除概率(qi=1/n)相等时平均数据移动次数AMN：2.2.2顺序表01234567时间复杂度：O(n)顺序表的删除intDelete(SeqList&L,ListDa