《《精编》数据结构之线性表》由会员分享，可在线阅读，更多相关《《精编》数据结构之线性表（90页珍藏版）》请在金锄头文库上搜索。
1、数据结构之线性表 线性结构是一个数据元素的有序 次序 集 线性表的基本特征 存在惟一的一个被称做 第一个 的数据元素 存在惟一的一个被称做 最后一个 的数据元素 除第一个之外 集合中的每个数据元素均只有一个前驱 除最后一个之外 集合中的每个数据元素均只有一个后继 2 1线性表的类型定义2 2线性表类型的实现 顺序映像2 3线性表类型的实现 链式映像2 4一元多项式的表示 抽象数据类型线性表的定义 ADTList 数据对象 D ai ai ElemSeti 1 2 nn 0 称n为线性表的表长 称n 0时的线性表为空表 数据关系 R1 ai ai 1 ElemSet i 1 2 n 1 0 称i
2、为ai在线性表中的位序 a1 a2 ai 1 ai ai 1 an 基本操作 结构初始化 InitList L 操作结果 构造一个空的线性表L 销毁结构 DetroyList L 初始条件 线性表L已经存在操作结果 销毁线性表L 引用型操作 ListEmpty L ListLength L PriorElem L cur e pre e NextElem L cur e next e GetElem L i e LocateElem L e compare ListTraverse L visit ListEmpty L 操作结果 若线性表L为空表 则返回True 否则返回FalseListL
3、ength L 操作结果 返回线性表L中元素的个数PriorElem L cur e pre e 操作结果 若cur e是L的元素 但不是第一个 则用pre e返回它的前驱 否则操作失败 NextElem L cur e next e 操作结果 若cur e是L中的元素 但不是最后一个 则用next e返回它的后继 否则操作失败GetElem L i e 操作结果 用e返回L中第i个元素的值 其中1 i ListLength L LocateElem L e compare 操作结果 返回第一个与e满足compare 关系的数据元素的位序 若不存在这样的元素 则返回0ListTraverse
4、L visit 操作结果 遍历线性表L 对每个元素执行函数visit 加工型操作 ClearList L PutElem L i e ListInsert L i e ListDelete l i e ClearList L 初始条件 线性表L已经存在操作结果 将L重至为空表PutElem L i e 初始条件 线性表L已存在 其中1 i LengthList L 操作结果 L中的第i个元素赋值为e的值 ListInsert L i e 初始条件 线性表L已存在 其中1 i LengthList L 1操作结果 在L的第i个元素之前插入一个新的元素e L的长度增加1ListDelete l i
5、 e 初始条件 线性表L已存在并且非空 其中1 i LengthList L 操作结果 将L的第i个元素删除 并将之 L的长度增加1 利用上述定义的线性表可以完成更复杂的操作 例2 1假设有两个集合A和B 分别用两个线性表LA和LB来表示 即 线性表中的数据元素为集合中的成员 现求一个新的集合A A B 上述问题可以演绎为 要求对线性表作如下操作 扩大线性表LA 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中 E B F H V D A LA A S F G LB V S G 从线性表LB中依次取得每个数据元素 GetElem LB i e依值在线性表LA中进行查访 L
6、ocateElem LA e Equal 若不存在 则插入之 ListInsert LA n 1 e VoidUnion List 取Lb中的第i个元素赋给eif LocateElem La e equal ListInsert La La len e 若La中不存在和e相同的值 则插入之 例2 2已知一个非纯集合B 试构造一个纯集合A 使A中只包含B中所有值各不相同的数据元素 E B E H D A LB B D B E LA E B H D A VoidPurge List 取Lb中的第i个元素赋给eif LocateElem La e equal ListInsert La La len
7、 e 若La中不存在和e相同的值 则插入之 E B E H D A LB B D B E LA E B H D A VoidPurge List 例2 3归并两个 其数据元素按值非递减有序排列的 线性表LA和LB 求得线性表LC也具有同样特性 不会 B L E B LB D L G C G I F A LA D H LC A B B C D D E F G G H I L L 设La a1 ai an Lb b1 bj bn Lc c1 ck cm n 则ck中的k为1 2 m n1 分别从La和Lb中取得当前元素ai和bj2 若ai bj 则将ai插入Lc中去 否则将bj插入到Lc中 Voi
8、dMergeList ListLa ListLb List while While i la len GetElem La i ai ListInsert Lc k ai While j lb len GetElem Lb j bj ListInsert Lc k aj 习题 1 有线性表LA和LB均为有序线性表 试构造线性表LA1和LB1分别为LA和LB中除去最大共同前缀后的子表 比如 LA a b c e f LB a b d e f 则LA1 c e f LB1 d e f 注意 LA和LB有一个是空表LA和LB相等 构造线性表LA1和LB1InitList LA1 InitList L
9、B1 分别从LA和LB中取得第i个数据元素GetElem LA i ai GetElem LB i bi 比较ai和bi是否相等 若相等继续取第i 1个数据元素 若不相等 则已经找到最大前缀 为前i 1项 退出将从第i项开始的LA和LB分别存放到LA1和LB1中即可 VoidwipePrefix ListLA ListLB List j i While j La len GetElem LA j aj ListInsert LA1 j aj j i While j Lb len GetElem LB j bj ListInsert LB1 j bj 2 线性表LA和LB均为递增有序的线性表 要
10、求对LA做如下操作 删除在LB中出现的元素 要求 1 用学到的线性表抽象数据类型中提供的操作编写算法 完成上述两题功能 2 分析所写算法的时间复杂度 2 2线性表类型的实现 顺序映像 用一组地址连续的存储单元依次存放线性表中的数据元素 线性表的起始地址称作线性表的基地址 线性表的起始地址称作线性表的基地址 以 存储位置相邻 表示有序对即 LOC ai LOC ai 1 C所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC ai LOC a1 i 1 C 一个数据元素所占存储量 即在顺序存储结构中 线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的序号惟一确定 一般
11、来说 长度为n的线性表 a1 a2 an 在计算机中的结构如下 顺序存储结构的特点 1 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系 即线性表的逻辑结构与存储结构 物理结构 一致 2 在访问线性表时 可以利用上述给出的数学公式 快速地计算出任何一个数据元素的存储地址 因此 我们可以粗略地认为 访问每个数据元素所花费的时间相等 这种存取元素的方法被称为随机存取法 使用这种存取方法的存储结构被称为随机存储结构 在具体实现时 一般用高级语言中的数组来对应连续的存储空间 设最多可存储MaxLen个元素 在C语言中可用数组data MaxLen 来存储数据元素 为保存线性表的长度需定义一
12、个整型变量length 线性表的第l 2 n个元素分别存放在此数组下标为0 1 length 1数组元素中 如下图所示 顺序映像的C语言描述 defineMaxLen80 线性表存储空间的初始分配量typedefintElemType 在实际应用中 将ElemType定义成实际类型typedefstruct ElemTypedata MaxLen 定义存储表中元素的数组intlength 当前长度 SqList sqListL 定义表结构的变量 顺序映像的C 语言描述 publicclassSqList privateintmaxSize 顺序表的容量privateint data 数组 用于
13、存储数据元素privateintlast 指示顺序表最后一个元素的位置publicintLast 最后一个数据元素位置属性 get returnlast publicintMaxSize 最大容量 get returnmaxSize set maxSize value publicSqList intsize 构造器 data newint size maxSize size last 1 线性表在顺序存储结构下的运算实现 1 初始化顺序表Initlist L 的实现顺序表的初始化即构造一个空表 顺序表L是否为空取决于其元素个数是否为0 因此 要将表L中的表长度置为0publicSqList
14、intsize 构造器 data newint size maxSize size last 1 该算法的时间复杂度为O 1 2 求线性表长度Getlength L 的实现求线性表的长度算法如下 publicintGetLength returnlast 1 该算法的时间复杂度为O 1 3 判断线性表是否为空IsEmpty 的实现判断线性表是否为空算法如下 publicboolIsEmpty if last 1 returntrue elsereturnfalse 该算法的时间复杂度为O 1 4 按序号取元素GetElem L i 的实现按前面的约定 序号为i的元素存储在数组下标为i 1的数组
15、元素中 所以可直接从该数组元素中取得值 i的有效值应大于等于1和小于等于线性表的实际长度 publicintGetElem inti if IsEmpty ilast 1 Console WriteLine ListisEmptyorPositioniserror return0 elsereturndata i 1 5 查找运算LocateElem L e 的实现 publicintLocate intitem if IsEmpty Console WriteLine ListisEmpty return 1 inti 0 for i 0 ilast return 1 returni 1 要
16、确定值为e的元素在L表中的位置 需要依次比较各元素 当查询到第一个满足条件的数据元素时 返回其序号 否则返回 1 表示查找失败 算法复杂度 在查找过程中 数据元素比较次数最少为1 最多为n元素比较次数的平均值为 n 1 2时间复杂度为O n 6 顺序表的插入算法InsertElem L i x 的实现顺序表的插入是指在表的第i个位置上插入一个值为x的新元素 插入后使原表长为n的表 a0 a1 ai 2 ai 1 ai an 1 成为表长为n 1的表 a0 a1 ai 2 x ai 1 ai an i的取值范围为1 i n 1 下图表示一个顺序表中的数组在进行插入运算前后 数据元素在数组中的下标变化 插入x 插入前 插入后 publicvoidInsert intitem inti if IsFull Console WriteLine TheListisfull return if ilast 2 Console WriteLine Thepositioniserror return if i last 2 若是向最后一个元素之后插入 直接插入即可data last 1 item el
