《202X年数据库的线性表知识讲解》由会员分享，可在线阅读，更多相关《202X年数据库的线性表知识讲解（42页珍藏版）》请在金锄头文库上搜索。
1、第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 3 1线性链表2 3 2循环链表2 3 3双向链表2 4一元多项式的表示及相加 在数据元素的非空有限集中存在唯一的一个被称作 第一个 的数据元素存在唯一的一个被称作 最后一个 的数据元素除第一个外 集合中的每个数据元素均只有一个前驱除最后一个外 集合中的每个数据元素均只有一个后继 线性结构是一个数据元素的有序 次序 集 线性结构特点 2 1线性表的类型定义 定义 一个线性表是n个数据元素的有限序列 例英文字母表 A B C Z 是一个线性表 特征 元素个数n 表长度 n 0空表1 i n时ai的直接
2、前驱是ai 1 a1无直接前驱ai的直接后继是ai 1 an无直接后继元素同构 且不能出现缺项 线性表是一种典型的线性结构 抽象数据类型线性表的定义如下 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 称n为线性表的表长 称n 0时的线性表为空表 数据关系 R1 ai 1 ai D i 2 n 设线性表为 a1 a2 ai an 称i为ai在线性表中的位序 基本操作 结构初始化 InitList L 操作结果 构造一个空的线性表L 销毁结构 DestroyList L 初始条件 线性表L已存在 操作结果 销毁线性表L 引用型操作 ListEmpty L 初始条
3、件 线性表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无定义 GetElem L cur e next e 初始条件 线性表L已存在 1
4、i LengthList L 操作结果 用e返回L中第i个元素的值 LocateElem L e compare 初始条件 线性表L已存在 compare 是元素判定函数 操作结果 返回L中第1个与e满足关系compare 的元素的位序 若这样的元素不存在 则返回值为0 ListTraverse L visit 初始条件 线性表L已存在 操作结果 依次对L的每个元素调用函数visit 一旦visit 失败 则操作失败 加工型操作 ClearList L 初始条件 线性表L已存在 操作结果 将L重置为空表 PutElem L i e 初始条件 线性表L已存在 1 i LengthList L 操
5、作结果 L中第i个元素赋值同e的值 ListInsert L i e 初始条件 线性表L已存在 1 i LengthList L 1操作结果 在L的第i个元素之前插入新的元素e L的长度增1 ListDelete L i e 初始条件 线性表L已存在且非空 1 i LengthList L 操作结果 删除L的第i个元素 并用e返回其值 L的长度减1 ADTList 利用上述定义的线性表可以完成其它更复杂的操作 例2 1假设有两个集合A和B分别用两个线性表LA和LB表示 即 线性表中的数据元素即为集合中的成员 现要求一个新的集合A A B 上述问题可演绎为 要求对线性表作如下操作 扩大线性表LA
6、 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去 思路 1 从线性表LB中依次取得每个数据元素 GetElem LB i e2 依次在线性表LA中进行查访 LocateElem LA e equal 3 若不存在 则插入之 ListInsert LA n 1 e voidunion List La中不存在和e相同的数据元素 则插入之 union 例2 2已知一个非纯集合B 试构造一个纯集合A 使A中只包含B中所有值各不相同的数据元素 voidpurge List La ListLb 已知线性表Lb中的数据元素依值非递减有序排列 Lb是有序表 构造线性表La 使其只包含
7、Lb中所有值不相同的数据元素 InitList LA La len ListLength La Lb len ListLength Lb 求线性表的长度for i 1 i Lb len i GetElem Lb i e 取Lb中第i个数据元素赋给eif equal en e en初始化为LB中没有的值ListInsert La La len e en e La中不存在和e相同的数据元素 则插入之 purge 例2 3归并两个 其数据元素按值非递减有序排列的 线性表LA和LB 求得线性表LC也具有同样特性设La a1 ai an Lb b1 bj bm Lc c1 ck cm n 则Ck k 1
8、 2 m n 思路 1 分别从LA和LB中取得当前元素ai和bj 2 若ai bj 则将ai插入到LC中 否则将bj插入到LC中 voidMergeList ListLa ListLb List while i La len merge list 2 2线性表的顺序存储结构 顺序表 定义 用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法 LOC ai LOC a1 i 1 LLOC ai 1 LOC ai L其中 L 一个元素占用的存储单元个数LOC ai 线性表第i个元素的地址 顺序表 特点 实现逻辑上相邻 物理地址相邻实现随机存取实现 可用C语言的一维数组实现 typedefin
9、tDATATYPE defineM1000DATATYPEdata M 例typedefstructcard intnum charname 20 charauthor 10 charpublisher 30 floatprice DATATYPE DATATYPElibrary M 数据元素不是简单类型时 可定义结构体数组 动态申请和释放内存DATATYPE pData DATATYPE malloc M sizeof DATATYPE free pData 顺序映像的C语言描述 线性表的动态分配顺序存储结构 defineLIST INIT SIZE80 线性表存储空间的初始分配量 defi
10、neLISTINCREMENT10 线性表存储空间的分配增量typedefstruct ElemType elem 存储空间基址intlength 当前长度intlistsize 当前分配的存储容量 以sizeof ElemType 为单位 SqList 俗称顺序表 线性表的初始化在顺序映像中的实现 StatusInitList Sq SqList InitList Sq 线性表操作LocateElem L e compare 的实现 intLocateElem Sq SqListL ElemTypee Status compare ElemType ElemType 在顺序线性表L中查找第1
11、个值与e满足compare 的元素的位序 若找到 则返回其在L中的位序 否则返回0 i 1 i的初值为第1元素的位序p L elem p的初值为第1元素的存储位置while i L length LocateElem Sq 此算法的时间复杂度为 O ListLength L 线性表操作ListInsert L i e 的实现 问 插入元素时 线性表的逻辑结构发生什么变化 a1 ai 1 ai an 改变为 a1 ai 1 e ai an x 思路 1 合法性检查2 存储空间的处理 判断 申请 3 元素的移动 从n号到pos号往后移动 4 把e插入pos号位置 长度增1 StatusListIn
12、sert Sq SqList if newbase exit OVERFLOW 存储分配失败L elem newbase 新基址L listsize LISTINCREMENT 增加存储容量 q ListInsert Sq 算法时间复杂度T n 设Pi是在第i个元素之前插入一个元素的概率 则在长度为n的线性表中插入一个元素时 所需移动的元素次数的平均次数为 线性表操作ListDelete L i e 的实现 问 删除元素时 线性表的逻辑结构发生什么变化 a1 ai 1 ai ai 1 an 改变为 a1 ai 1 ai 1 an 思路 1 删除位置的合法性检查2 删除元素的提取3 从pos 1号到n号元素前移4 长度减1 StatusListDelete Sq SqList ListDelete Sq 算法评价设Qi是删除第i个元素的概率 则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为 故在顺序表中插入或删除一个元素时 平均移动表的一半元素 当n很大时 效率很低 顺序存储结构的优缺点 优点逻辑相邻 物理相邻可随机存取任一元素存储空间使用紧凑缺点插入 删除操作需要移动大量的元素预先分配空间需按最大空间分配 利用不充分表容量难以扩充
