第二章线性表 21线性表及其逻辑结构 22线性表的顺序存储结构 23线性表的链式存储结构 24顺序表的应用 25有序表 线性表的逻辑结构和物理结构,以及它 们之间的相互关系 G定义与之相适应的运算 G设计相应的算法 分析算法的效率
1 第二章 线性表 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 顺序表的应用 2.5 有序表 2.1 线性表及其逻辑结构 线性表的逻辑结构和物理结构，以及它 们之间的相互关系 定义与之相适应的运算 设计相应的算法 分析算法的效率
2.1线性表及其逻辑结构 1.线性表 具有相同特性的n个数据元素的一个有限序列, 记为L=(a1,a2 ndii+19.ngan 数据元素之同的关系是: a1领先于at,a领先于ai+,即元素在位置上是有序的 称a1是a的直接前驱元素,a是a的直接后继元素 除a1外,每个元素有旦仅有—个直接前驱元素 除an外,每个元素有仅有一个直接后继元素 线性表中数据元素的个数n(m>=0)称为线性表的长度; 当n=0时,称为空表 2
2 2.1线性表及其逻辑结构 1.线性表 具有相同特性的n个数据元素的一个有限序列， 记为 L＝(a1 ,a2 ,…ai ,ai+1 ,…,an ) 数据元素之间的关系是： ai-1领先于a i , a i领先于a i＋1，即元素在位置上是有序的； 称ai-1是a i的直接前驱元素, a i+1是a i的直接后继元素； 除a1外，每个元素有且仅有一个直接前驱元素； 除an外，每个元素有且仅有一个直接后继元素； 线性表中数据元素的个数n(n>=0）称为线性表的长度； 当n=0时，称为空表
2.1线性表及其逻辑结构 线性表是最常用且最简单的一种数据结构 它的形式化定义为:List=(D,R) 其中D={a1i≤m,a1属 Elemtype类型} Rr r={a;a+1>|lsi≤n-1 R是一个序偶的集合,表示线性表中数据 元素之间的相邻关系。 逻辑图
3 2.1线性表及其逻辑结构 线性表是最常用且最简单的一种数据结构 它的形式化定义为：List=(D,R) 其中:D={ai |1≤i ≤n, ai属ElemType类型} R={r} r={| 1≤i ≤n-1} R是一个序偶的集合，表示线性表中数据 元素之间的相邻关系。 逻辑图 a1 a2 … ai ai+1 an …
2.1线性表及其逻辑结构 ADT List Elem Type是任何 合法的数据类型 数据对象 D={a11s|ai,ai+1∈D,i=1,,,n-1} 基本运算 Initlist(&L):初始化线性表构造一个空表 Destroyliste(&L):销毁线性表:释放表占存储空间 Displist():输出线性表显示表中所有元素值
4 2.1线性表及其逻辑结构 ADT List { 数据对象： D={ai | 1≤i≤n,n≥0, ai是ElemType类型} 数据关系： R={|ai ,ai+1∈D,i=1,…,n-1} 基本运算： InitList(&L):初始化线性表:构造一个空表 DestroyList(&L):销毁线性表:释放表占存储空间 … Displist(L);输出线性表:显示表中所有元素值 } ElemType是任何 合法的数据类型
21线性表及其逻辑结构 例1分析26个英文字母组成的英文表: (A, B, C,D Z) 析:数据元素都是同类型字符),元素间关系是线性的 例2分析学生情况登记表: 姓名学号性别」年龄健康情况 王小林790631 18 健康 陈红790632 男女男男 20 般 刘建平790633 21健康 张立立790634 17 神经衰弱 ■m 分析:数据元素都是同类型(记录), 5 元素间关系是线性的
5 例1 分析26 个英文字母组成的英文表: （ A, B, C, D, …… , Z） 例2 分析学生情况登记表: 分析:数据元素都是同类型(字符), 元素间关系是线性的 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 …….. …….. ……. ……. ……. 分析：数据元素都是同类型（记录）， 元素间关系是线性的。 2.1线性表及其逻辑结构
2.1线性表及其逻辑结构 2.基本运算 A NetlIst(U):初始化线性表:构造一个空的线性 表 e Destroylist(:销毁线性表:释放线性表L占 用的内存空间。 A Listempty(L:判线性表是否为空表:着L为 空表则返回真否则返回假 e Listlengthe(D:求线性表的长度:返回L中元素 个数。 Displist(:输出线性表:当线性表L不为空时 ,顺序显示L中各结点的值域
6 2.1线性表及其逻辑结构 2.基本运算 InitList(L): 初始化线性表：构造一个空的线性 表L DestroyList(L): 销毁线性表：释放线性表L占 用的内存空间。 ListEmpty(L): 判线性表是否为空表: 若L为 空表,则返回真,否则返回假 ListLength(L): 求线性表的长度: 返回L中元素 个数。 DispList(L): 输出线性表: 当线性表L不为空时 ,顺序显示L中各结点的值域
2.1线性表及其逻辑结构 GetElem(L,i,e):求线性表L中指定位置的某个数据 元素:用c返回L中第i(1 <is ListLength()个元素的 值 Locateelem(L,e):定位查找:返回L由第1△值城与e 相等的位序。若这样的元素不有想一想:这些运 s ListInser.,:插入数算已经实现了吗 isListLength(个元素之前细入mm素e L的长度增1。 e ListDelete((删除数据元素:删除L中的第i (1 <i<ListLength个元素,并用e返回其值,L的 长度减1
7 2.1线性表及其逻辑结构 GetElem(L,i,e):求线性表L中指定位置的某个数据 元素:用e返回L中第 i （1≤i≤ ListLength(L))个元素的 值。 ListDelete(L,i,e) : 删除数据元素：删除L中的第i （ 1≤i≤ListLength(L))个元素，并用e返回其值，L的 长度减1。 LocateElem(L,e): 定位查找: 返回L中第1个值域与e 相等的位序。若这样的元素不存在,则返回值为0。 ListInsert(L,i,e): 插入数据元素：在L的第i( 1≤i≤ListLength(L)+1)个元素之前插入新的元素e， L的长度增1。 想一想：这些运 算已经实现了吗？
21线性表及其逻辑结构 对上述的运算的两点说明: 这些运算是在逻辑结构上定义的操作。只给 出这些运算的功能是“做什么”,至于“如 何做”等实现细节,只有待确定了存储结构 之后才考虑。 cR这些运算仅是基本运算集,基于基本运算可 进行复杂的运算,即通过基本运算可派生出 复杂的运算
8 ❖对上述的运算的两点说明： 这些运算是在逻辑结构上定义的操作。只给 出这些运算的功能是“做什么”，至于“如 何做”等实现细节，只有待确定了存储结构 之后才考虑。 这些运算仅是基本运算集，基于基本运算可 进行复杂的运算，即通过基本运算可派生出 复杂的运算。 2.1线性表及其逻辑结构
∠21线性表及其逻辑结构 例21有一个线性表L=(a’;e,"a,;d,b”),求以 下基本运算的执行结果 Listlength(L)=5 Listempty (L)=0 GetElem(L, 3, e)e=a Locateelem(L, 'a)=1 ListInsert(L,4,e”)L=(“a’;e’;a’,‘e’,d’b”) Listdelete(L,3)L=(a’,c’,e’,d”,b”)
9 例2.1 有一个线性表L=(‘a’,‘c’,‘a’,‘d’,‘b’),求以 下基本运算的执行结果 ListLength(L) ListEmpty(L) GetElem(L,3,e) LocateElem(L,‘a’) ListInsert(L,4,‘e’) ListDelete(L,3) =5 =0 e=‘a’ =1 L=(‘a’,‘c’,‘a’, ‘e’,‘d’,‘b’) L=(‘a’,‘c’, ‘e’,‘d’,‘b’) 2.1线性表及其逻辑结构
2.1线性表及其逻辑结构 例22求两个集合的并,即C=AUB 分析:设A、B分别由两个线性表LA和LB表示,要 求将LA和LB合并后的DE放入到线性表LC中。 算法思想: ①初始化LC; ②将LA中所有元素复制到LC中 ③依次从LB中取出一个DE ④判断LC中是否存在; ⑤若不存在,则插入到LC中 10
10 2.1线性表及其逻辑结构 例2.2 求两个集合的并，即C=A∪B 分析：设A、B分别由两个线性表LA和LB表示，要 求将LA和LB合并后的DE放入到线性表LC中。 算法思想： ①初始化LC； ②将LA中所有元素复制到LC中； ③依次从LB中取出一个DE； ④判断LC中是否存在； ⑤若不存在，则插入到LC中