数据与结构算法中对线性表格的理解.ppt

《数据与结构算法中对线性表格的理解.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、线性表顺序表链表顺序表与链表的比较第二章线性表线性表(LinearList)线性表的定义和特点定义n（0）个数据元素的有限序列，记作（a1,a2,…,an）ai是表中数据元素，n是表长,n=0时为空表遍历逐项访问：从前向后从后向前线性表的特点除第一个元素外，其他每一个元素有且仅有一个直接前驱除最后一个元素外，其他每一个元素有且仅有一个直接后继a1a2a3a4a5线性表的初始化Init_List(L)求线性表的长度Length_List(L)取表元Get_List(L,i)按值查找Locate_List(L,x)插入操作Insert_

2、List(L,i,x)删除操作Delete_List(L,i)线性表的基本操作顺序表(SequentialList)顺序表的定义和特点定义将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构特点逻辑顺序与物理顺序一致访问顺序存取,随机存取253457164809012345data顺序表的连续存储方式3527491860547783410212345678910llllllllllLoc(ai)=Loc(a1)+(i－1)*l1≤i≤na顺序表(SeqList)的定义#defineMaxsize100//最大允许

3、长度typedefintdatetype;typedefstruct{datatypedata[Maxsize];//存储数组intlast;//当前元素个数}SeqList;SeqList*L;(或SeqListL;)L.dataa5a4a3a2a101234L.last=Ldataa5a4a3a2a101234Llast=Maxsize-1Maxsize-1顺序表基本运算的实现顺序表的初始化SeqList*inti_Seqlist(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));

4、Llast=-1;returnL;}求表的长度intLength(SeqList*L){returnLlast+1;}取表元：在表中提取第i个元素的值datatypeGetData(SeqList*L,inti){if(i>=1&&i<=Llast+1)returnLdata[i-1];elseprintf(“参数i不合理！”);}按值查找：在顺序表中查找结点值等于给定值x的结点动画演示i<=LlastintLocate_SeqList(SeqList*L,datatypex){inti=0;while(&&Ldata

5、[i]!=x)i++;if(i>Llast)return-1;elsereturni;}按值查找动画演示253457164809012345data查找16i＝Llast012345查找成功，返回i的值查找50253457164809012345datai＝Llast012345查找失败，返回－1查找成功的平均比较次数若查找概率相等，则：查找不成功，数据比较n次O(n)2534571648096301234567data5025345701234567data50i=4例:在第４个位置(i=4)插入一个值为50的新元素L

6、last插入运算：在顺序表的第i(1≤i≤n+1)个位置插入一个值为x的新元素63094816i与Llast的关系？intInsert(SeqList*L,datatypex,inti){//在表中第i个位置插入新元素xif(i<1

7、

8、i>)return0;if(Llast==Maxsize-1)return-1;//参数不合理或表已满，插入不成功for(j=Llast;j>=;j--)Ldata[j+1]=Ldata[j];=x;Llast++;return1;//插入成功}Llast+2i-1Ldata[i-1]算

9、法分析：在顺序表上做插入操作需要移动表中一半的元素时间复杂度为Ｏ(n)162534571648096301234567data25345701234567datai=4例:将表中第４个位置(i=4)上的元素删除Llast删除运算：将顺序表中的第i(1≤i≤n)个元素从表中删除630948i与Llast的关系？intDelete(SeqList*L,datatypex){//删除表中第i个位置上的元素if(i<1

10、

11、i>Llast+1)return0;for(;j<=Llast;j++)Ldata[j-1]=Ldata[j]

12、;Llast--；return1;//删除成功}j=i算法分析：在顺序表上做删除操作大约需要移动表中一半的元素时间复杂度为Ｏ(n)例题:P162.1-2.3顺序表应用举例例1将顺序(a1,a2,...,an)表重新排列