数据结构-b抽象数据类型线性表的定义讲述.ppt

2.1.2抽象数据类型线性表的定义 ADJ List { 数据对象：D={ai|ai∈ElemSet,i=1,2,,...n,n=0} 数据关系：R1={ai-1,ai|ai-1,ai∈D,i=1,2,,...n} 基本操作： 1.IiniList(L) //构造空表L。 2.LengthList(L) //求表L的长度 3.GetElem(L,i,e) //取元素ai,由e返回ai 4.PriorElem(L,ce,pre_e) //求ce的前驱,由pre_e返回 5.InsertElem(L,i,e) //在元素ai之前插入新元素e 6.DeleteElem(L,i) //删除第i个元素 7.EmptyList(L) //判断L是否为空表 8.ClearList(L) //置L为空表 ...... }ADJ List 说 明 1.删除表L中第i个数据元素,记作:DeleteElem(L,i) L=(a1,a2,...,ai,a(i+1),...,an) 指定序号i,删除ai ↑ L=(a1,a2,...,ai,...,a(n-1)) 2.指定元素值x,删除表L中的值为x的元素,记作: DeleteElem(L,x)； 3.在元素ai之前插入新元素e(1=i=n) L=(a1,a2,...,ai,...,an) 插入e ↑ L=(a1,a2,...,ai,a(i+1)...,a(n+1)) 4.查找----确定元素值(或数据项的值)为e的元素。 给定:L=(a1,a2,...,ai,...,an)和元素e 若有一个 ai=e，则称“查找成功”,i=1,2,...,n 否则，称“查找失败”。 5.排序----按元素值或某个数据项值的递增（或递减）次序 重新排列表中各元素的位置。 例.排序前: L=(90,60,80,10,20,30) 排序后: L=(10,20,30,60,80,90) L变为有序表 6.将表La和表Lb合并为表Lc 例.设有序表： La=(2,14,20,45,80) Lb=(8,10,19,20,22,85,90) 合并为表 Lc=(2,8,10,14,19,20,20,22,45,80,85,90) 7.将表La复制为表Lb La=(90,14,20,45) Lb=(90,14,20,45) 2.2 线性表的顺序表示（顺序存储结构） 2.2.1.顺序分配──将线性表中的数据元素依次存放到计算 机存储器中一组地址连续的存储单元中, 这种分配方式称为 顺序分配或顺序映像。由此得到的存储结构称为顺序存储结 构或向量(一维数组）。 例. a=(30,40,10,55,24,80,66) 内存状态 C语言中静态一维数组的定义： int a[11]； (a1,a1,a2,...an)顺序存储结构的一般形式 序号 存储状态 存储地址 1 b 2 b+p i b+(i-1)*p n b+(n-1)*p 自由区 maxleng b+(maxleng-1)*p 其中: b----表的首地址/基地址/元素a1的地址。 p----1个数据元素所占存储单元的数目。 maxleng----最大长度,为某个常数。 2.2.2 线性表顺序结构在C语言中的定义 例1.分别定义元素所占空间、表长、尾元素的位置 #define maxleng 100 { ElemType la[maxleng+1]；//下标:0,1,…,maxleng int l