第2章线性表
第2章 线性表
线性结构 线性结构是一个数据元素的有序(次序)集合。 它有四个基本特征: 集合中必存在唯一的一个"第一元素 集合中必存在唯一的一个最后元素 3.除最后元素之外,其它数据元素均有唯一的 "后继"; 4.除第一元素之外,其它数据元素均有唯一的 前驱
线性结构 • 线性结构是一个数据元素的有序（次序）集合。 • 它有四个基本特征： 1．集合中必存在唯一的一个"第一元素" ； 2．集合中必存在唯一的一个"最后元素" ； 3．除最后元素之外，其它数据元素均有唯一的 "后继" ； 4．除第一元素之外，其它数据元素均有唯一的 "前驱"
第一节线性表的类型定义 21.1抽象数据类型线性表的定义 ·通常可以下列n个数据元素的序列表示线性 表( Linear_list)(a 25·9i15=i5=i+15 序列中数据元素的个数n定义为线性表的表长 ·n=0时的线性表被称为空表 ·称i为a在线性表中的位序
第一节 线性表的类型定义 2.1.1 抽象数据类型线性表的定义 • 通常可以下列" n 个数据元素的序列"表示线性 表 (Linear_List) ( a1 , a2 ,...,ai-1 ,ai ,ai+1,...,an ) • 序列中数据元素的个数 n 定义为线性表的表长 • n=0 时的线性表被称为空表 • 称 i 为ai在线性表中的位序
线性表的抽象数据类型的定义 ADT List t 数据对象:D={a1a1∈ Elem Set=1,2…,n,n0} 数据关系:R1={<a1,a1叫a1a1∈D,i=2,,n} 基本操作: {结构初始化} InitList( &L 操作结果:构造一个空的线性表L。 销毁结构} Destroy List(&L 初始条件:线性表L已存在。 操作结果:销毁线性表L
线性表的抽象数据类型的定义 • ADT List { 数据对象：D＝{ai | ai ∈ ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ <ai-1 ,ai >| ai-1 ,ai∈D, i=2,...,n } 基本操作： {结构初始化} InitList( &L ) 操作结果：构造一个空的线性表 L 。 {销毁结构} DestroyList( &L ) 初始条件：线性表 L 已存在。 操作结果：销毁线性表 L
{引用型操作} ListEmpty( L 初始条件:线性表L已存在。 操作结果:若L为空表,则返回TRUE,否则 返回 FALSE。 ListLength( L 初始条件:线性表L已存在。 操作结果:返回L中元素个数 PriorElem(L, cur 操作结果:若cu已是的数据元素,则用 pree返回它的前驱,否则操作失败,pee无定义。 NextElem( L, cur e, &next e) 初始条件:线性表L已存在。 cu 中的数据元素,则用 next e返回它的后继,否则操作失败, next e无定义
• {引用型操作} ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若 L 为空表，则返回 TRUE，否则 返回 FALSE。 ListLength( L ) 初始条件：线性表 L 已存在。 操作结果：返回 L 中元素个数。 PriorElem( L, cur_e, &pre_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。 NextElem( L, cur_e, &next_e ) 初始条件：线性表 L 已存在。 操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义