[理学]数据结构数 2-线性表.ppt

数据结构 华中科技大学计算机学院 ------------------------------------------------- 第二章 线性表 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 例3. 图书登记表 序号 书 名 作 者 单价(元) 数量(册) 1 程序设计语言 李 明 10.50 500 2 数据结构 陈小平 9.80 450 ... ...... ..... ..... ... n DOS使用手册 周爱玲 20.50 945 表长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抽象数据类型线性表的定义 ADT List { 数据对象：D={ai|ai∈ElemSet,i=1,2,,...n,n=0} 数据关系：R1={ai-1,ai| ai-1,ai∈D,i=2,,...n} 基本操作： 1.IniList(L) //构造空表L。 2.ListLength (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是否为空表 ...... }ADT List 说 明 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)； L=(a1,a2,...,ai-1, ai, ai+1,...,an) 若ai=x， 删除ai↑ L=(a1,a2,...,ai-1,ai+1,...,an) 3.在元素ai之前插入新元素e(1=i=n+1)，记作： InsertElem(L,i,e) 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=(