数据结构华中科技大学计算机学院(1)
数据结构 华中科技大学计算机学院(1) -------------------------------------------------
第二章线性表 2.1线性表的定义 2.1.1线性表的逻辑结构 1.线性表— 由n(n≥0)个数据元素(a1,a2,,.,an)构成的 有限序列 记作:L=(a1,a2,,an 首元素 an 尾元素 2.表的长度(表长)——线性表中数据元素的数目。 3.空表——不含数据元素的线性表
第二章 线性表 2.1 线性表的定义 2.1.1 线性表的逻辑结构 1.线性表── 由n(n≥0)个数据元素(a1,a2,...,an)构成的 有限序列。 记作: L=(a1,a2,...,an) a1──首元素 an──尾元素 2.表的长度(表长)──线性表中数据元素的数目。 3.空表──不含数据元素的线性表
线性表举例 例1.字母表L1=(A,B,C,,,Z 表长26 例2.姓名表L2=(李明,陈小平,王林,周爱玲) 表长4 的” 图书登记表 书名。作者单价(元)数量(册) 序设计语 明10.50500 2L数据结构 陈小平9.80450 nDoS使用手册周爱玲20.50945 表长n
线性表举例 例1. 字母表 L1=(A,B,C,...,Z) 表长26 例2. 姓名表 L2=(李明, 陈小平, 王林, 周爱玲) 表长4 例3. 图书登记表 序号 书 名 作 者 单价(元) 数量(册) 1 程序设计语言 李 明 10.50 500 2 数据结构 陈小平 9.80 450 ... ...... ..... ..... ... n DOS使用手册 周爱玲 20.50 945 表长n
线性表的特征 对于L=(a1,a2, a a: a a 1.a1-1在a1之前,称a1-1是a的直接前驱 (1<i≤n) 2.a+在ai之后,称a1计是a;的直接后继 (1≤i<n) 3.a1没有前驱 4.an没有后继 5.a;(1<i<n)有且仅有一个直接前驱和一个 直接后继
线性表的特征 对于 L=(a1,a2,...,ai-1 , ai,ai+1,...,an) 1.ai-1在ai之前,称ai-1是ai的直接前驱 (1＜i≤n) 2.ai+1在ai之后,称ai+1是ai的直接后继 (1≤i＜n) 3.a1没有前驱 4.an没有后继 5.ai(1＜i＜n)有且仅有一个直接前驱和一个 直接后继
2.1.2抽象数据类型线性表的定义 ADJ List 数据对象:L={aiai∈ ElemNet,i=1,2,n,n>=0} 数据关系:R1={ai-1,aiai-1∈D,i=1,2,,,n 基本操作: Iinilist(&L) //构造空表L。 2. LengthList(L) /求表L的长度 3. GetElem( L, i, &e) //取元素ai,由e返回ai 4. Priorelem(L,ce,&pree)//求ce的前驱,由pree返回 5. Insertelem(&L,i,e)//元素ai之前插入新元素e 6 DeleteElem(&L, i) //删除第i个元素 7. EmptyList(L) //判断L是否为空表 8. Clearlist(&L) //置L为空表 JAD List
2.1.2抽象数据类型线性表的定义 ADJ List { 数据对象：L={ai|ai∈ElemSet,i=1,2,,...n,n>=0} 数据关系：R1={|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
说明 1.删除表L中第i个数据元素(1<=i<=n),记作 DeleteElem(&L, i) a 指定序号i,删除ai↑ 1,ai+1 2.指定元素值x,删除表L中的值为x的元素,记作 DeleteElem(&L, X) 3.在元素ai之前插入新元素e(1<=i<=n+1) a 插入e↑ a e. a 4.査找——确定元素值(或数据项的值)为e的元素 给定:L=(a1,a2,,a1,,,,an)和元素e 若有一个a;=e,则称“查找成功”,i=1,2,,,n 否则,称“査找失败
说 明 1.删除表L中第i个数据元素(1<=i<=n),记作: DeleteElem(&L,i) L=(a1,a2,...,ai-1 , ai,ai+1,...,an) 指定序号i,删除ai ↑ L=(a1,a2,...,ai-1,ai+1,...,an) 2.指定元素值x,删除表L中的值为x的元素,记作: DeleteElem(&L,x)； 3.在元素ai之前插入新元素e(1<=i<=n+1) L=(a1,a2,...,ai-1 , ai,...,an) 插入e ↑ L=(a1,a2,...,ai-1 ,e, ai,...,an) 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=(2,14,20,45,80) Lb=(2,14,20,45,80
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= (2,14,20,45,80) Lb= (2,14,20,45,80)
可利用现有操作组成更复杂的操作: void union list &la, List &lb) alen- List length(La);∥求线性表La的长度 Lb len- List length(Lb);∥求线性表Lb的长度 for(i=l; i<=Lb len; 1++) Getelem(Lb,e),∥取Lb的的第个数据元素赋给e if(! Locateelem( La, e, equa)判断e在La中是否存在 ListInsert(a++ La len,e);∥不存在则插入
可利用现有操作组成更复杂的操作： 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) 内存状态 304010 55 248066 45678910 C语言中静态一维数组的定义: int a[lll 2345678910
2.2 线性表的顺序表示（顺序存储结构） 2.2.1.顺序分配──将线性表中的数据元素依次存放到计算 机存储器中一组地址连续的存储单元中, 这种分配方式称为 顺序分配或顺序映像。由此得到的存储结构称为顺序存储结 构或向量(一维数组）。 例. a=(30,40,10,55,24,80,66) 内存状态 C语言中静态一维数组的定义： int a[11]； 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 30 40 10 55 24 80 66
(a1,a1,a2,,an)顺序存储结构的一般形式 序号存储状态存储地址 1a1 al b+(i-1)* n an //|自由区 maxleng // b+(maxleng-1)*p 其中:b-—表的首地址/基地址/元素al的地址。 p--1个数据元素所占存储单元的数目。 maxing-最大长度,为某个常数
(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----最大长度,为某个常数。 a1 a2 ... ai ... an // // //