数2-线性表a 数据结构 教学教案.pptVIP

数据结构 华中科技大学计算机学院(1) -------------------------------------------------;第二章 线性表;线性表举例;线性表的特征;2.1.2抽象数据类型线性表的定义 ADJ List { 数据对象：L={ai|ai∈ElemSet,i=1,2,,...n,n=0} 数据关系：R1={ai-1,ai|ai-1∈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;可利用现有操作组成更复杂的操作： void union(List La,List Lb) { La_len=List_length(La); //求线性表La的长度 Lb_len=List_length(Lb); //求线性表Lb的长度 for (i=1;i= Lb_len;i++) { GetElem(Lb,i,e); //取Lb的的第i个数据元素赋给e if (!LocateElem(La,e,equal)) //判断e在La中是否存在 ListInsert(La,++La_len,e); //不存在则插入 } } ; 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 length； //当前长度 int last； //an的位置 } 或： ;线性表顺序结构在C语言中的定义（一） 例2.元素所占空间和表长合并为C语言的一个结构类型： #define maxleng 100 { typedef struct { ElemType elem[maxleng]；//下标:0,1,...,maxleng-1 int length； //表长 } SqList； SqList La； .......... } 其中：typedef---别名定义，SqList----结构类型名 La----结构类型变量名 La.length---表长 La.ele