数据结构第2章线性表.pptx

第2章线性表 2012年7月18日 冯鲁涛 第一节线性表的类型定义第二节线性表的顺序存储表示和实现第三节线性表的链式存储表示和实现第四节循环链表 双向链表 有序表 集合操作 目录 第一节线性表的类型定义 线性表是一种最简单的线性结构 线性结构是一个数据元素的有次序的集合 它有4个基本特征 1 集合中必存在唯一的 第一元素 2 集合中必存在唯一的 最后元素 3 除最后元素之外 其它数据元素均有唯一的 后继 4 除第一元素之外 其它数据元素均有唯一的 前驱 第一节线性表的类型定义 线性表的抽象数据类型的定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 第一节线性表的类型定义 基本操作 结构初始化 InitList L 操作结果 构造一个空线性表L 销毁结构 DestroyList L 初始条件 线性表L已存在操作结果 销毁线性表L 第一节线性表的类型定义 引用型操作 ListEmpty L 初始条件 线性表L已存在操作结果 L为空 则返回TRUE 否则返回FALSEListLength 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无定义 第一节线性表的类型定义 GetElem L i e 初始条件 线性表L已存在 1 i ListLength L 操作结果 用e返回L中第i个元素的值LocateElem L e compare 初始条件 线性表L已存在 compare 是元素判定函数操作结果 返回L中第1个与e满足关系compare 的元素的位序 若这样的元素不存在 则返回值为0 第一节线性表的类型定义 ListTraverse L visit 初始条件 线性表L已存在 visit 为元素的访问函数操作结果 依次对L的每个元素调用函数visit 一旦visit 失败 则操作失败 第一节线性表的类型定义 加工型操作 ClearList L 初始条件 线性表L已存在操作结果 将L重置为空表PutElem L i e 初始条件 线性表L已存在 1 i ListLength L 操作结果 L中第i个元素赋值同e的值 第一节线性表的类型定义 ListInsert L i e 初始条件 线性表L已存在 1 i ListLength L 1操作结果 在L的第i个元素之前插入新的元素e L的长度增1ListDelete L i e 初始条件 线性表L已存在且非空 1 i ListLength L 操作结果 删除L的第i个元素 并用e返回其值 L的长度减1 第二节线性表的顺序存储表示和实现 顺序表是线性表的顺序存储表示的简称用一组地址连续的存储单元依次存放线性表中的数据元素前驱和后继的关系 有序对 存储位置相邻线性表的基地址 线性表的起始地址 表中第一个元素的存储位置 第三节线性表的链式存储表示和实现 链表是线性表的链式存储表示的简称特点