第2章线性表 主要内容: 1.线形表的类型定义 2.线形表的顺序表示和实现 3.线形表的链式表示和实现 4.有序表 5.顺序表和链表的综合比较 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第2章线性表 胡建华 2021/2/19 计算机教研室 第 1 页 第 2 章 线性表 主要内容： 1．线形表的类型定义 2．线形表的顺序表示和实现 3．线形表的链式表示和实现 4．有序表 5．顺序表和链表的综合比较
@线性表是一种最简单的线性结构 ·线性结构的基本特征为: ·线性结构是一个数据元素的有序(次序)集 集合中必存在唯一的一个“第一元素” 2.集合中必存在唯一的一个“最后元素 3.除最后元素在外,均有唯一的后继; 4.除第一元素之外,均有唯一的前驱。 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第2页 线性表是一种最简单的线性结构 • 线性结构的基本特征为: • 线性结构是一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素” ； 2．集合中必存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱
21线形表的类型定义 计算机教研宦 第3页 2021/2/19
Data Structure 数据结构—— 第2章线性表 胡建华 2021/2/19 计算机教研室 第 3 页 2.1 线形表的类型定义
抽象数据类型线性表的定义 ADT List 数据对象: D={a1|a1∈ ElemNet,i=1,2,,n,n≥0} 称n为线性表的表长;称n=0时的线性表为空表。} 数据关系: R1={<a i-1,ai a i-1 a:∈D n 设线性表为(a1,a2, a 称 i为a1在线性表中的位序。} 基本操作: 结构初始化操作 结构销毁操作 引用型操作 加工型操作 AdT List 计算机教研室 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第4页 抽象数据类型线性表的定义 ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长; 称 n=0 时的线性表为空表。} 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } {设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。} 基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 } ADT List
初始化操作 InitList(& 操作结果:构造一个空的线性表L。 结构销毁操作 DestroyList(&L 初始条件:线性表L已存在。 操作结果:销毁线性表L。 引用型操作 ListEmpty(L) 初始条件:线性表L已存在。 操作结果:若L为空表,则返回TRUE, 否则 fAlse。 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第5页 初始化操作 InitList( &L ) 操作结果：构造一个空的线性表L。 结构销毁操作 DestroyList( &L ) 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L。 引用型操作 ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE， 否则FALSE