资源描述：
《数据结构第二章线性表课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构 第二章线性表重庆一中葛静1数据元素之间满足线性关系的表称为线性表，是一种最基本、最简单的数据结构类型。本章讨论线性表的逻辑和存储结构、相关算法的实现以及线性表应用举例。2.1线性表的定义及基本操作2.1.1定义：线性表(LinearList)是若干数据元素的一个线性序列，记为：L=(a1,∙∙∙∙ai-1aiai+1∙∙∙∙∙∙an)其中：L为表名，ai(1≤i≤n)为数据元素；n为表长，n>0时，L为非空表，否则为空表。2.1.2线性表的逻辑结构和特征线性表L可用二元组形式描述：L=(D,R)数据元素集合:D={ai
2、ai∈datatype,i=1,2,∙∙∙∙∙∙∙
3、∙∙n,n≥0}关系集合:R={
4、ai,ai+1∈D,1≤i≤n-1}表长n=0时，L为空表；关系符在这里称为有序对，表示任意相邻的两个元素之间的一种先后次序关系，称ai是ai+1的直接前驱,ai+1是ai的直接后继，当表长n≤1时，关系集R为空集。2例2-1线性表的例子L1=(A,B,……,Z)元素为字符；L2=(6,7,……,105)元素为整数；学生记录表：线性表的特征：对非空表,a1是表头,无前驱；an是表尾,无后继；其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。2.1.3线性表的抽象数据类型表示设线性表L
5、=(a1,a2,……,an)，对L的抽象数据类型表示：学号姓名性别年龄班级-------J99001丁兰女19计99-------J99002王林男20计99-------------------------------------------------J99032马红女18计99-------a1a2....a323线性表的抽象数据类型表示ADTList{数据元素集：D={ai
6、ai∈datatype,i=1,2,……n,n≥0}数据关系集：R={
7、ai,ai+1∈D,1≤i≤n-1}基本操作集：P(置表空、求表长、插入、删除、查找一个元素等)42.2.1顺
8、序表若将线性表L=(a0,a1,……,an-1)中的各元素依次存储于计算机一片连续的存储空间，如图2.2所示。这种机内表示为线性表的顺序存储结构(顺序表)。地址：b:占d个单元b+d:设Loc(ai)为ai的地址，Loc(a1)=b，则：…Loc(a2)=b+1*db+（i-1）*d:........…Loc(ai)=b+（i-1）*db+（n-1)*d:图2.2顺序表的特点：(1)逻辑上相邻的元素ai,ai+1，存储位置也是相邻的；(2)对ai的存取为随机存取或按地址存取。(3)存储密度高。存储密度D=(数据结构中元素所占存储空间)/(整个数据结构所占空间)。顺序表的不足：对表
9、的插入和删除等运算的时间复杂度较差。a1a2…ai…an5线性表的顺序存储Typelist=recordvec:array[1..m0]ofelemtype;len:integer;End;VarL:list;1、setnull(L)L.len:=0;操作结果：构造一个空的线性表L。2、length(L)return(L.Len);初始条件：线性表L存在。操作结果：返回L中的元素个数。3、向线性表的第i个元素插入一个元素步骤：（1）检查存储空间是否已经满，若满，则“溢出”。（2）检查i是否超范围1<=i<=n+1,若是，则“超出范围”（3）将线性表中第i个元素和后面所有元素均后移
10、一位。（4）将新元素写在第i个位置上。（5）线性表长度加1.a1…ai…an6线性表的抽象数据类型表示3、向线性表的第i个元素插入一个元素的算法描述Insert(L,i,x);BeginifL.len=m0thenwriteln(‘overflow’);if(i<1)or(i>L.len+1)thenwriteln(‘outofrange’);forj:=L.lendowntoidoL.vec[j+1]:=L.vec[j];L.vec[i]=x;L.len:=L.len+1;End;算法复杂度分析：算法第1、2步根据情况可省略。时间复杂度主要取决于第3步，即for循环的次数，也就
11、是向后移动的元素个数。当i=n+1时，最好情况,元素不移动,当i=1时，最坏情况，移动n次。假定在线性表的任何位置上插入元素的概率相同，为pi=1/(n+1),1<=i<=n+1,则元素平均移动的次数为：Pi(n+n-1+n-2+……+0)=pi(n(n+1)/2)=n/2故最坏和平均O(n)7线性表的抽象数据类型表示4、删除线性表的第i个元素算法步骤：（1）检查1<=i<=n,若不是，则“超出范围”（2）若删除的元素有用，则把第i个元素赋值给变参带回。（3）把第i个元素后面所有
