ch2--线性表.ppt

数据结构 DataStructure 张先xianyi 第2章线性表 本章主要内容2 1线性表的定义和运算2 2线性表的顺序存储结构2 3线性表的链式存储结构2 4其它结构形式的链表2 5串本章小结作业布置 2 1线性表的定义和运算 逻辑结构和运算2 1 1线性表的定义定义 线性表L是由n个元素a1 a2 an组成的有限序列 记作L a1 a2 an 其中n 0为表长度 n 0时L为空表 记作L 表中元素ai的含义 在不同的场合有不同的含义 但是 在同一表中 元素类型相同 例 字母表 A B C D Z 数字表 0 1 2 3 4 9 月份表 1月 2月 12月 季节表 春 夏 秋 冬 学生成绩表 其中每个元素就是一个人的成绩信息 非空线性表的特点 存在一个 第一个 头 首 数据元素 存在一个 最后一个 尾 数据元素 除首元素外其他元素有且仅有一个直接前趋 除尾元素外其他元素有且仅有一个直接后继 2 1 2线性表的运算对线性表有如下基本运算 1 初始化 initialList L 创建一个空的线性表 使用线性表必经过程 2 求表长度 listLength L 返回线性表中的元素个数 3 按序号取元素 getElement L i 从线性表中取出序号为i的数据元素 前提 1 i n 即存在该元素 否则 应当如何处理 4 按值查找元素 listLocate L x 在线性表中查找给定值的元素x所在的位置 若不存在 应如何给出相关信息 5 插入元素 listInsert L i x 在线性表中给定的位置i处 插入给定值的元素x 前提 1 i n 1 即插入位置有效 否则如何处理 6 删除元素 listDelete L i 删除线性表种指定序号i处的元素 前提 1 i n 即存在该元素 否则 应当如何处理 借助这些基本运算可以构造出更加复杂的运算 例 删除x元素 可先用listLocate L x 找出元素x的位置i 再用listDelete L i 进行删除 例 两表合并为一表 一个表拆分为多个表 TheApple1whichwassoldasado it yourselfkit 1976 withoutthelovelycaseseenhere 2 2线性表的顺序存储结构 2 2 1顺序存储结构假设有一个足够大的连续存储空间 数组 data 用于存储线性表的元素 将线性表中的元素依次存储到数组中 顺序存储方式 顺序表 如下图所示 其中 设置一个计数变量ListLen 以记录表中的元素个数 将数组data和listLen作为顺序表的数据成员 L a1 a2 a3 an 顺序表类型描述 defineMaxLen100 最多100个元素typedefstructsList elementTypedata MaxLen 定义存放元素的数组intlistLen 定义长度分量 seqList 注 元素的类型这里用elementType 实际中视实际情况用具体的类型来替换 如 int等 如用typedefintelementType 定义为整型 使用typedef把seqList定义为一种数据类型 我们可以使用此类型来定义变量例 seqListL1 L2 seqList分量的使用方式上例中 L1是seqList型的结构变量 分量的引用方法 L1 listLen L1 data i L2为seqList型的结构指针变量 分量的引用方法 L2 listLen L2 data i 说明 顺序表元素下标和数组data的下标相差1 表元素下标从1开始 数组data按C语言规范 下标从0开始 对应关系如下图 2 2 2顺序表的运算实现6个基本运算的实现描述 1 初始化建立一个空表 即使得顺序表的listLen 0 VoidinitialList seqList L L listLen 0 为什么要用 L 算法时间复杂度O 1 2 求顺序表长度 定义函数返回表L的listLen分量即可 intlistLength seqListL returnL listLen 为什么不用指针呢 时间复杂度O 1 3 按序号取元素 给定元素序号i 取出第i个元素 取出的值用变量x返回 如果i超出范围 怎样处理 voidgetElement seqListL inti elementType 注 此段代码只是为了描述 实际编程不能这样处理 用x返回取得的元素值 这里使用了C 的引用 一种实际实现代码示例 有不同实现方法 boolgetElement seqListL inti elementType 取元素成功 返回1 返回的值在x中 时间复杂度 O 1 4 按值查找元素 将给定的元素x与L中数据元素逐个进行比较 若存在相同的元素 则返回第一个相同元素的位置序号 否则 不存在相同元素 返回值0 intlistLocate seqListL elementTypex inti for i 0 i L lsitlen i if L data i x return i 1 数组的下标比元素序号少1return 0 如果找到了x从上个return语句返回 执行到此 说明没有找到x 所以返回0 算法分析1 基本操作 数据比较 2 若L中存在数据元素x 位置为i 1 i n 需要比较次数 i次 概率为 1 n 所以平均可能比较次数为 3 若L中不存在数据元素x 比较次数为 n 所以时间复杂度 O n 5 插入运算 在序号i位置插入元素x 分析 1 首先要检查插入条件是否满足 表空间未满 即L listLen MaxLen 1 序号正确 范围在1 n 1之间 即 1 i n 1 x的类型与表的数据类型相同 2 插入步骤 ai ai 1 an往后移一位 如何实现 填入x 即L data i 1 x 表长度增1 即L listLen 插入位置 a1 1 空闲 ai 1 ai ai 1 i 1 i i 1 n 空位 位序 内存状态 an n 1 a1 1 空闲 ai 1 ai ai 1 an 1 i 1 i i 1 n 插入新元素 位序 内存状态 an n 1 x an an 1 ai 1 ai voidlistInsert seqList L elementTypex inti if L listLen MaxLen error 溢出 elseif iL listlen 1 error 序号错误 else for j L listlen 1 j i 1 j L data j 1 L data j L data i 1 x L listlen 顺序表满了 序号错了 如何实现ai ai 1 an往后移 一种实际实现 空间满返回0 超范围返回1 正确插入返回2 intlistInsert seqList L elementTypex inti intj if L listLen MaxLen return 0 空间满elseif iL listLen 1 return 1 序号超出范围else for j L listLen 1 j i 1 j L data j 1 L data j 后移元素L data i 1 x 插入元素xL listLen 长度增1return2 算法分析1 基本操作 插入前移动原有数据元素 2 插入位置为i 需要移动次数 n i 1次 3 插入位置概率相同 1 n 1 4 平均可能移动次数 所以时间复杂度 O n 6 删除元素删除表中序号i位置的元素 分析 1 首先要检查删除条件是否满足 序号正确 范围在1 n之间 即 1 i n 2 删除步骤 ai 1 an往前移动一个位置 挤掉 ai元素 表长度减1 即L listLen 删除算法描述voidlistDelete seqList L inti if L listlen 0 error 下溢出 elseif iL listlen error 序号错误 else for j i jlistlen 1 j j为元素下标L data j 1 L data j L listlen 问题 j的含义 见教材p16 一种实际实现 空表返回0 序号超出范围返回1 正确删除返回2 intlistDelete seqList L inti intj if L listLenL listLen return1 删除的序号不在有效范围内else for j i jlistLen j L data j 1 L data j 循环前移表元素L listLen 修改表长度return2 成功删除 返回值2 算法分析1 基本操作 向前移动数据元素 覆盖原来值 2 删除位置为i 需要移动次数 n i次 3 删除元素位置概率相同 1 n 4 平均可能移动次数 所以时间复杂度 O n Amanwhodoesnotplanlongaheadwillfindtroublerightathisdoor Confucius子曰 人无远虑 必有近忧 2 2 3顺序表的应用 例1 现有2个集合A和B 求一个新集合C A B 3个集合都用顺序表表示 比如A 2 4 10 5 9 B 1 4 6 8 则C 2 4 10 5 9 1 6 8 算法思想 这是较简单的顺序表合并问题 要注意的是因为A B和C都是集合 合并后C中不能出现重复的元素 基本步骤如下 循环取出A中的元素 直接插入到C的listLen 1位置 循环取出B中的元素 判断是否出现在A中 在A中时跳过 集合元素不能重复 不在A中插入到C中 算法描述 一种实现 有多种实现 ex211pListMerge cpp voidListMerge seqListA seqListB seqList pC inti elementTypex for i 0 ilistLen 1 for i 0 ilistLen 1 算法分析 假设A的元素个数为m B的元素个数为n 本例的时间性能主要取决于第二个for循环 事实上这是一个双重循环 因为listLocate A x 中有循环 其时间性能为O n 所以总的时间复杂度为O m n 思考问题 为什么listInsert中的插入位置是pC listLen 1 而不是pC listLen呢 本例使用指针从子函数往主函数传回新表C 如果采用C 的 引用 传递 程序该如何修改 还有其它传回C的方法吗 如果算法中的A和B都用指针或引用有什么不同呢 例2 已知顺序表L递增有序 设计算法 在L中插入元素x 使得L依然递增有序 如 L 2 5 7 9 12 14 15 x 8 17 1算法思想 基本思想 找到x的插入位置i 1 i n 1 保持插入后L仍递增 然后插入 对此有2中基本方法 从前往后搜索插入位置 然后批量移动其后面的元素 这种方法比较费时 搜索前面i个元素 移动后面n i 1个元素 每个元素都会访问到 从后往前搜索 同时移动元素 当元素值大于x时后移 重复进行至找到插入位置 比较次数比移动次数多1 除非第一个元素 算法描述 只是描述 不能直接运行 voidinsert seqlist L elementTypex inti L listlen 1 取表中最后元素的数组下标if i MAXLEN thenerror overflow 表满else while i 0 L data i 1 x 为什么是i 1呢 L listlen 算法实现 从前往后搜索插入 ex211OrderedList1 cpp从后往前搜索插入 ex211OrderedList2 cpp算法分析 该算法花费的时间主要是比较和移动元素 在第i个位置插入时需移动n i 1个元素 比较次数比移动次数多1次 即取决于插入位置 最好情况下 比较1次 移动0次 而最差情况下需要比较n次 移动n次 时间复杂度 O n 思考问题 算法中的while循环结束时 空位置 插入位置 的下标是i还是i 1 请模拟在表 4 6 10 15 20 中分别插入25 8和2时的实现过程 如果while循环条件L data i x改为L data i x 结果会有何不同 用for循环能否完成相同功能呢 例2 3 假设顺序表A B分别表示一个集合 设计算法以判断集合A是否是集合B的子集 若是 则返回TRUE 否则返回FALSE 并要求时间尽可能少 算法分析 2层循环实现 第一层循环 依次取出A中元素 第二层循环 判断A中取出的元素是否在B中 若在B中 回到第一层循环 继续取A的下一个元素 若不在B中 直接返回false A所有元素都在B中 返回true 算法描述 实现代码 ex212subset BOOLsubset seqList A B intia ib elementTypex BOOLsuc ia ib为A B元素数组下标for ia 0 ialistLen ia x A data ia 取出A中一个元素ib 0 suc FALSE suc为搜索成功与否的标志while iblistLen 到此处时 一定是成功的 算法分析 由于A中每个元素都要与B中每个元素比较 故该算法的时间复杂度为两表之长度的积的数量级 即为O A B 本题也可这样求解 将判断指定元素是否在B表中的求解也设置为一个布尔函数的形式 在此不再赘述 有兴趣的读者可自己练习 思考问题 此算法函数参数A和B都是指针 不用指针可以吗 用指针有什么好处 使用C 的 引用 是否可行 例2 4 假设递增有序顺序表A B分别表示一个集合 设计算法以判断集合A是否是集合B的子集 若是 返回TRUE 否则返回FALSE 并要求时间尽可能少 算法分析 本题也可用前例算法求解 没有用到所给出的递增有序的条件 时间性能不是最佳 设用ia和ib分别为A和B中元素的数组下标 当ia和ib均指向各自表中某一元素时 可能会出现如下几种情况 1 A data ia B data ib 即A表中当前元素大于B表中当前元素 因而需要继续在B表中搜索 即要执行ib 以使ib指向B表中下一个元素并继续搜索 2 A data ia B data ib A表中当前元素在B表中 即查找成功 因而可继续A表中下一个元素的判断 即要执行ia 以使ia指向A表的下一个元素并继续搜索 与此相对应的是 指示B表中元素的ib应指示到哪儿 一种简单的办法是从头开始 但那样的话 还是没有用上递增有序的条件 因而没有改善算法的时间复杂度 仔细分析可得到另一种办法 即ib还是指示原来的位置 或者简单地往后移动一位 即执行ib 也可以 3 A data ia data ib 即A表中当前元素小于B表中当前元素 因而肯定小于其后面的所有元素 所以该元素肯定不在B表中 即搜索失败 由于只要有一个元素不在B表中 就意味着A表不是B表的子集 故整个算法的求解结束 可返回结果 FALSE 重复执行上述判断过程 直到ia和ib中至少有一个指向表尾之后为止 此时 根据不同的情况可以分别得出如下结论 1 ia A listlen 意味着A表中每个元素都已经被判断过了 并且都在B表中 为什么 因而可以返回结论TRUE 2 否则 意味着A表中的当前元素肯定不在B表中 因而返回结论FALSE A是B的子集演示 A B 成功 返回true A不是B的子集演示 A B 失败 返回false 算法描述 实现 ex225OrderedListSubset BOOLOrderedListSubset Seqlist A B intia 0 ib 0 while ialistlen 算法分析 由于ia ib从头开始依次指示A B表中每个元素一次 严格地说 由于停顿可能使某个元素被比较几次 但每次比较至少要通过一个元素 故算法的时间复杂度为两表长度之和的数量级 即O A B 思考问题 本算法在什么情况下会出现ia和ib同时等于对应表的长度 例2 5 设计算法将递增有序顺序表A B中的元素值合并为一个递增有序顺序表C 并要求时间尽可能少 思考问题 若数据元素有多个数据项 比如学生成绩表有4项 学号 姓名 课程 分数 能不能用顺序表存储呢 如何存储呢 方式一 直接在顺序表中定义typedef