2线性表-顺序.ppt

第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示和相加 顺序映像的 C 语言描述 typedef struct { } SqList; // 俗称 顺序表 #define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位) 线性表的基本操作在顺序表中的实现 InitList(L) // 结构初始化 ListInsert(L, i, e) // 插入元素 ListDelete(L, i) // 删除元素 * * 线性结构的基本特征为: 1．集合中必存在唯一的一个“第一元素”； 2．集合中必存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。 线性结构 是 一个数据元素的有序（次序）集 线性表是一种最简单的线性结构 2.1 线性表的类型定义 抽象数据类型线性表的定义如下： 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 ) 初始化线性表L，为L开辟空间并将L置为空表。 初始化操作 结构销毁操作 DestroyList(L ) 初始条件： 操作结果： 线性表 L 已存在。 将 L 空间释放。 EmptyList ( L ) 初始条件： 操作结果： 线性表L已存在。 若L为空表，则返回 TRUE，否则FALSE。 （线性表判空） LengthList ( L ) 初始条件： 操作结果： 线性表L已存在。 返回L中元素个数。 （求线性表的长度） Priorelem( L, e ) 初始条件： 操作结果： 线性表L已存在，e与线性表中数据元素同型。 求e元素的前驱，并用e返回其前驱值，e存在前驱则函数返回真值，否则返回假值。 （求数据元素的前驱） Nextelem( L, e ) 初始条件： 操作结果： 线性表L已存在，e与线性表中数据元素同型。 求e元素的后继，并用e返回其后继值，e存在后继则函数返回真值，否则返回假值。 （求数据元素的后继） Getelem( L, i) 初始条件： 操作结果： 线性表L已存在， 且 1iLengthList(L)。 返回线性表L中第i个元素的值。否则提示出错。 （求线性表中某个数据元素） Locate ( L, e) 初始条件： 操作结果： 线性表L已存在，e与线性表中数据元素兼容 如果L中存在e元素，则返回元素e所在位置，如果L中不存在元素e，则返回0。 （定位函数） Traverse(L) 初始条件： 操作结果： 线性表L已存在且非空。 对L的每个元素进行遍历。 （遍历线性表） ClearList(L ) 初始条件： 操作结果： 线性表L已存在。 将L置为空表。 （线性表置空） InsertList (L, i, e ) 初始条件： 操作结果： 线性表L已存在， 且 1iLengthList(L)+1 。 在L的第i个元素之前插入 新的元素e，L的长度增1。 （插入数据元素） DeleteList (L, i, e) 初始条件： 操作结果： 线性表L已存在且非空， 1≤i≤LengthList(L) 。 删除L的第i个元素，并用e返回其值，L的长度减1。 （删除数据元素） 利用上述定义的线性表 可以实现其它更复杂的操作 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成