第二章线性表 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={<ai ,ai+1>| 1≤i ≤n-1} R是一个序偶的集合，表示线性表中数据 元素之间的相邻关系。 逻辑图 a1 a2 … ai ai+1 an …
2.1线性表及其逻辑结构 ADT List Elem Type是任何 合法的数据类型 数据对象 D={a11s<n,n≌0,a是 ElemType类型} 数据关系: R={<a12a+t>|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>|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线性表及其逻辑结构