敦案 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 第2章线性表 2.1线性表的类型定义 2.1.1抽象数据类型线性表的定义 抽象数据类型指一个数学模型和定义在该模型上的一组操作的接口和语义说明。 ◆不研究具体的实现，反映其逻辑特征，而其在计算机的内部表示和实现对用户是透 明的。 ◆包含各种处理器（包括计算机硬件系统、操作系统、高级语言、数据库等）中己定 义并实现的数据类型（固有数据类型）和用户自定义的数据类型。 分类：原子类型、固定聚合类型、可变聚合类型、多形数据类型 抽象数据类型定义：(D,S,P)D-数据对象，S-数据关系，P基本操作 线性表的抽象数据类型定义： ADT List{ 数据对象：D={ala∈ElemSet,.i=l,2,…,n,n≥0} 数据关系：R={R1},R1={<a-1,a>a-1,a∈D,=2,3,…,n} 基本操作： InitList(&L) 操作结果：构造一个空的线性表L DestroyList(&L) 初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(&L) 初始条件：线性表L己存在 操作结果：将线性表L重置为空表 ListEmpty(L) 初始条件：线性表L己存在 操作结果：若L为空表，则返回TRUE,否则返回FALSE ListLength(L) 初始条件：线性表L己存在 操作结果：返回线性表L中数据元素的个数 GetElem(L,i,&e) 初始条件：线性表L己存在，l≤i≤ListLength(L) 操作结果：用e返回L中第ⅰ个数据元素的值 LocateElem(L,e,compare()) 初始条件：线性表L己存在，compare()是数据元素的判定函数 操作结果：返回L中第1个与e满足关系compare(()的数据元素的位序。 若这样的元素不存在，则返回值为0 PriorElem(L,cur_e,&pre_e) 初始条件：线性表L已存在 操作结果：若cure是L的数据元素，且不是第一个，则用pre_e返回 它的前驱，否则操作失败，pree无定义 NextElem(L,cur e,&next_e) 初始条件：线性表L己存在 操作结果：若cure是L的数据元素，且不是最后一个，则用next e返 文档编号 完成时间 完成人 张昱 修改时间2003-9-10 第1页程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 1 页 第 1 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 第2章 线性表 2.1 线性表的类型定义 2.1.1 抽象数据类型线性表的定义 抽象数据类型指一个数学模型和定义在该模型上的一组操作的接口和语义说明。 ◆ 不研究具体的实现，反映其逻辑特征，而其在计算机的内部表示和实现对用户是透 明的。 ◆ 包含各种处理器（包括计算机硬件系统、操作系统、高级语言、数据库等）中已定 义并实现的数据类型（固有数据类型）和用户自定义的数据类型。 分类：原子类型、固定聚合类型、可变聚合类型、多形数据类型 抽象数据类型定义：(D,S,P) D-数据对象，S-数据关系，P-基本操作 线性表的抽象数据类型定义： ADT List{ 数据对象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={<ai-1,ai>|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitList(&L) 操作结果：构造一个空的线性表 L DestroyList(&L) 初始条件：线性表 L 已存在 操作结果：销毁线性表 L ClearList(&L) 初始条件：线性表 L 已存在 操作结果：将线性表 L 重置为空表 ListEmpty(L) 初始条件：线性表 L 已存在 操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE ListLength(L) 初始条件：线性表 L 已存在 操作结果：返回线性表 L 中数据元素的个数 GetElem(L, i ,&e) 初始条件：线性表 L 已存在，1≤i≤ListLength(L) 操作结果：用 e 返回 L 中第 i 个数据元素的值 LocateElem(L, e, compare( )) 初始条件：线性表 L 已存在，compare( )是数据元素的判定函数 操作结果：返回 L 中第 1 个与 e 满足关系 compare( )的数据元素的位序。 若这样的元素不存在，则返回值为 0 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 返