第3章-线性表.ppt

数据结构与算法作者 胡明王红梅出版社 电子工业出版社邮箱 wanghm 第3章线性表 线性表的逻辑结构线性表的存储结构及实现应用实例 本章的基本内容是 3 1引言 数据元素之间的关系是什么 3 1引言 数据元素之间的关系是什么 现实生活中 许多问题抽象出的数据模型是线性表 如何存储这种线性结构并实现插入 删除 查找等基本操作呢 3 1引言 约瑟夫环问题 设n n 0 个人围成一个环 n个人的编号分别为1 2 n 从第1个人开始报数 报到m时停止报数 报m的人出环 再从他的下一个人起重新报数 报到m时停止报数 报m的出环 如此下去 直到所有人全部出环为止 当任意给定n和m后 求n个人出环的次序 n 5 m 3时的出圈次序 约瑟夫环问题的数据模型是一种典型的环状线性结构 如何存储这种环形结构并求解约瑟夫环的出环次序呢 线性表 简称表 是n n 0 个具有相同类型的数据元素的有限序列 线性表的长度 线性表中数据元素的个数 空表 长度等于零的线性表 记为 L 非空表记为 L a1 a2 ai 1 ai an 3 2线性表的逻辑结构 线性表的定义 其中 ai 1 i n 称为数据元素 下角标i表示该元素在线性表中的位置或序号 3 2线性表的逻辑结构 线性表的特性 1 有限性 线性表中数据元素的个数是有穷的 2 相同性 线性表中数据元素的类型是同一的 3 顺序性 线性表中相邻的数据元素ai 1和ai之间存在序偶关系 ai 1 ai 即ai 1是ai的前驱 ai是ai 1的后继 a1无前驱 an无后继 其它每个元素有且仅有一个前驱和一个后继 线性表的抽象数据类型定义 ADTListData线性表中的数据元素具有相同类型 相邻元素具有前驱和后继关系OperationInitList前置条件 表不存在输入 无功能 表的初始化输出 无后置条件 建一个空表 3 2线性表的逻辑结构 DestroyList前置条件 表已存在输入 无功能 销毁表输出 无后置条件 释放表所占用的存储空间Length前置条件 表已存在输入 无功能 求表的长度输出 表中数据元素的个数后置条件 表不变 3 2线性表的逻辑结构 线性表的抽象数据类型定义 Get前置条件 表已存在输入 元素的序号i功能 在表中取序号为i的数据元素输出 若i合法 返回序号为i的元素值 否则抛出异常后置条件 表不变Locate前置条件 表已存在输入 数据元素x功能 在线性表中查找值等于x的元素输出 若查找成功 返回x在表中的序号 否则返回0后置条件 表不变 3 2线性表的逻辑结构 线性表的抽象数据类型定义 Insert前置条件 表已存在输入 插入i 待插x功能 在表的第i个位置处插入一个新元素x输出 若插入不成功 抛出异常后置条件 若插入成功 表中增加一个新元素Delete前置条件 表已存在输入 删除位置i功能 删除表中的第i个元素输出 若删除成功 返回被删元素 否则抛出异常后置条件 若删除成功 表中减少一个元素 3 2线性表的逻辑结构 线性表的抽象数据类型定义 Empty前置条件 表已存在输入 无功能 判断表是否为空输出 若是空表 返回1 否则返回0后置条件 表不变ADT 进一步说明 1 线性表的基本操作根据实际应用是而定 2 复杂的操作可以通过基本操作的组合来实现 3 对不同的应用 操作的接口可能不同 3 2线性表的逻辑结构 线性表的抽象数据类型定义 3 3线性表的存储结构及实现 顺序表 线性表的顺序存储结构 例 34 23 67 43 34 23 67 43 4 顺序表 线性表的顺序存储结构 例 34 23 67 43 34 23 67 43 4 用什么属性来描述顺序表 3 3线性表的存储结构及实现 顺序表 线性表的顺序存储结构 例 34 23 67 43 34 23 67 43 4 如何实现顺序表的内存分配 3 3线性表的存储结构及实现 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 长度 一般情况下 a1 a2 ai 1 ai an 的顺序存储 数组的长度Max 线性表的长度Length 数组的长度大于等于当前线性表的长度 3 3线性表的存储结构及实现 顺序表存储结构的定义 3 3线性表的存储结构及实现 如何求得任意元素的存储地址 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 长度 一般情况下 a1 a2 ai 1 ai an 的顺序存储 3 3线性表的存储结构及实现 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 长度 Loc ai Loc a1 i 1 c 随机存取 在O 1 时间内存取数据元素 一般情况下 a1 a2 ai 1 ai an 的顺序存储 3 3线性表的存储结构及实现 存储结构是数据及其逻辑结构在计算机中的表示 存取结构是在一个数据结构上对查找操作的时间性能的一种描述 存储结构和存取结构 顺序表是一种随机存取的存储结构 的含义为 在顺序表这种存储结构上进行的查找操作 其时间性能为O 1 3 3线性表的存储结构及实现 操作接口 voidInitList SeqList L 算法描述 voidSeqList SeqList 顺序表的实现 初始化顺序表 0 3 3线性表的存储结构及实现 操作接口 voidCreat SeqList L DataTypea intn 顺序表的实现 建立顺序表 5 35 12 24 33 42 3 3线性表的存储结构及实现 voidCreat SeqList 算法描述 3 3线性表的存储结构及实现 顺序表的实现 建立顺序表 操作接口 voidInsert inti DataTypex 插入前 a1 ai 1 ai an 插入后 a1 ai 1 x ai an 顺序表的实现 插入 ai 1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 3 3线性表的存储结构及实现 例 35 12 24 42 在i 2的位置上插入33 表满 length MaxSize合理的插入位置 1 i length 1 i指的是元素的序号 顺序表的实现 插入 4 35 12 24 42 a1 a2 a3 a4 01234 42 24 12 33 什么时候不能插入 3 3线性表的存储结构及实现 1 如果表满了 则抛出上溢异常 2 如果元素的插入位置不合理 则抛出位置异常 3 将最后一个元素至第i个元素分别向后移动一个位置 4 将元素x填入位置i处 5 表长加1 算法描述 伪代码 顺序表的实现 插入 3 3线性表的存储结构及实现 voidInsert SeqList 算法描述 C描述 顺序表的实现 插入 基本语句 3 3线性表的存储结构及实现 最好情况 i n 1 基本语句执行0次 时间复杂度为O 1 最坏情况 i 1 基本语句执行n 1次 时间复杂度为O n 平均情况 1 i n 1 时间复杂度为O n 时间性能分析 顺序表的实现 插入 3 3线性表的存储结构及实现 操作接口 DataTypeDelete inti 删除前 a1 ai 1 ai ai 1 an 删除后 a1 ai 1 ai 1 an 顺序表的实现 删除 ai 1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 3 3线性表的存储结构及实现 例 35 33 12 24 42 删除i 2的数据元素 仿照顺序表的插入操作 完成 1 分析边界条件 2 分别给出伪代码和C描述的算法 3 分析时间复杂度 顺序表的实现 删除 5 35 a1 a2 a3 a4 01234 42 24 12 33 a5 12 24 42 3 3线性表的存储结构及实现 顺序表的实现 按位查找 操作接口 DataTypeGet inti 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 n 算法描述 DataTypeGet SeqList 时间复杂度 3 3线性表的存储结构及实现 顺序表的实现 按值查找 操作接口 intLocate DataTypex 5 35 a1 a2 a3 a4 01234 42 24 12 33 a5 例 在 35 33 12 24 42 中查找值为12的元素 返回在表中的序号 3 3线性表的存储结构及实现 intLocate SeqList 退出循环 说明查找失败 顺序表的实现 按值查找 算法描述 时间复杂度 3 3线性表的存储结构及实现 顺序表的优缺点 顺序表的优点 无需为表示表中元素之间的逻辑关系而增加额外的存储空间 随机存取 可以快速地存取表中任一位置的元素 顺序表的缺点 插入和删除操作需要移动大量元素 表的容量难以确定 表的容量难以扩充 造成存储空间的碎片 3 3线性表的存储结构及实现 单链表 线性表的链接存储结构 存储思想 用一组任意的存储单元存放线性表的元素 单链表 3 3线性表的存储结构及实现 存储特点 逻辑次序和物理次序不一定相同 2 元素之间的逻辑关系用指针表示 例 a1 a2 a3 a4 的存储示意图 单链表 a10200 a20325 a30300 a4 3 3线性表的存储结构及实现 单链表 数据域 指针域 单链表是由若干结点构成的 单链表的结点只有一个指针域 data 存储数据元素next 存储指向后继结点的地址 3 3线性表的存储结构及实现 typedefintDataType DataType为线性表的数据类型typedefstructNode DataTypedata Node next Node first first为指向单链表的头指针 单链表 如何申请一个结点 3 3线性表的存储结构及实现 s Node malloc sizeof Node 单链表 3 3线性表的存储结构及实现 单链表 如何引用数据元素 data 如何引用指针域 next s next s Node malloc sizeof Node 3 3线性表的存储结构及实现 单链表 重点在数据元素之间的逻辑关系的表示 所以 将实际存储地址抽象 什么是存储结构 3 3线性表的存储结构及实现 单链表 头指针 指向第一个结点的地址 尾标志 终端结点的指针域为空 3 3线性表的存储结构及实现 单链表 空表和非空表不统一 缺点 如何将空表与非空表统一 3 3线性表的存储结构及实现 头结点 在单链表的第以一个元素结点之前附设一个类型相同的结点 以便空表和非空表处理统一 单链表 非空表 3 3线性表的存储结构及实现 单链表的实现 初始化单链表 操作接口 Node InitList Node first Node InitList Node first first Node malloc sizeof Node 生成头结点first next NULL 头结点的指针域置空returnfirst first 3 3线性表的存储结构及实现 单链表的实现 遍历操作 操作接口 voidPrintList Node first 核心操作 关键操作 工作指针后移 从头结点 或开始结点 出发 通过工作指针的反复后移而将整个单链表 审视 一遍的方法称为扫描 或遍历 first a1 a2 an ai 3 3线性表的存储结构及实现 单链表的实现 遍历操作 算法描述 voidPrintList Node first p first next 工作指针p初始化while p NULL printf p data p p next 3 3线性表的存储结构及实现 单链表的实现 按位查找 操作接口 DataTypeGet inti first a1 a2 an ai 1 工作指针p初始化 累加器count初始化 2 重复执行下述操作 直到p为空 2 1工作指针p后移 2 2count 3 返回累加器count的值 3 3线性表的存储结构及实现 DataTypeGet Node first inti p first next count 1 while p NULL 单链表的实现 按位查找 算法描述 3 3线性表的存储结构及实现 intLocate Node first DataTypex p first next count 1 while p NULL if p data x returncount 查找成功p p next count return0 退出循环表明查找失败 单链表的实现 按值查找 算法描述 3 3线性表的存储结构及实现 单链表的实现 插入 操作接口 voidInsert inti DataTypex 如何实现结点ai 1 x和ai之间逻辑关系的变化 算法描述 s Node malloc sizeof Node s data x s next p next p next s 3 3线性表的存储结构及实现 注意分析边界情况 表头 表尾 单链表的实现 插入 first a1 an ai 算法描述 s Node malloc sizeof Node s data x s next p next p next s 由于单链表带头结点 表头 表中 表尾三种情况的操作语句一致 3 3线性表的存储结构及实现 算法描述 伪代码 1 工作指针p初始化 2 查找第i 1个结点并使工作指针p指向该结点 3 若查找不成功 则插入位置不合理 抛出插入位置异常 否则 3 1生成一个元素值为x的新结点s 3 2将新结点s插入到结点p之后 单链表的实现 插入 3 3线性表的存储结构及实现 voidInsert Node first inti DataTypex p first count 0 工作指针p应指向头结点while p NULL 单链表的实现 插入 基本语句 时间复杂度 3 3线性表的存储结构及实现 单链表的实现 建立单链表 操作接口 LinkList DataTypea intn 头插法 将待插入结点插在头结点的后面 算法描述 first Node malloc sizeof Node first next NULL 3 3线性表的存储结构及实现 操作接口 LinkList DataTypea intn 头插法 将待插入结点插在头结点的后面 算法描述 s Node malloc sizeof Node s data a 0 s next first next first next s 插入第一个元素结点 first 单链表的实现 建立单链表 3 3线性表的存储结构及实现 操作接口 LinkList DataTypea intn 头插法 将待插入结点插在头结点的后面 依次插入每一个结点 算法描述 s Node malloc sizeof Node s data a 1 s next first next first next s 单链表的实现 建立单链表 3 3线性表的存储结构及实现 Node Creat Node first DataTypea intn first Node malloc sizeof Node first next NULL 初始化头结点for i 0 idata a i 为每个数组元素建立一个结点s next first next first next s returnfirst 单链表的实现 建立单链表 3 3线性表的存储结构及实现 尾插法 将待插入结点插在终端结点的后面 操作接口 LinkList DataTypea intn 算法描述 first Node malloc sizeof Node r first 单链表的实现 建立单链表 3 3线性表的存储结构及实现 尾插法 将待插入结点插在终端结点的后面 操作接口 LinkList DataTypea intn 算法描述 s Node malloc sizeof Node s data a 0 r next s r s 插入第一个元素结点 单链表的实现 建立单链表 3 3线性表的存储结构及实现 尾插法 将待插入结点插在终端结点的后面 操作接口 LinkList DataTypea intn 依次插入每一个结点 35 单链表的实现 建立单链表 3 3线性表的存储结构及实现 尾插法 将待插入结点插在终端结点的后面 操作接口 LinkList DataTypea intn 算法描述 r next NULL 最后一个结点插入后 35 单链表的实现 建立单链表 3 3线性表的存储结构及实现 Node Creat Node first DataTypea intn first Node malloc sizeof Node 生成头结点r first 尾指针初始化for i 0 idata a i 为每个数组元素建立一个结点r next s r s r next NULL returnfirst 算法描述 单链表的实现 建立单链表 3 3线性表的存储结构及实现 单链表的实现 删除 操作接口 DataTypeDelete inti 如何实现结点ai 1和ai之间逻辑关系的变化 算法描述 q p next x q data p next q next free q 3 3线性表的存储结构及实现 单链表的实现 删除 算法描述 q p next x q data p next q next free q 注意分析边界情况 表头 表尾 表尾的特殊情况 虽然被删结点不存在 但其前驱结点却存在 p next NULL 3 3线性表的存储结构及实现 算法描述 伪代码 1 工作指针p初始化 2 查找第i 1个结点并使工作指针p指向该结点 3 若p不存在或p不存在后继结点 则抛出位置异常 否则 3 1暂存被删结点和被删元素值 3 2摘链 将结点p的后继结点从链表上摘下 3 3释放被删结点 3 4返回被删元素值 单链表的实现 删除 3 3线性表的存储结构及实现 DataTypeDelete Node first inti p first count 0 注意工作指针p要指向头结点while p NULL 单链表的实现 删除 3 3线性表的存储结构及实现 启示 算法设计的一般过程 算法设计的一般步骤 第一步 确定入口 已知条件 出口 结果 第二步 根据一个小实例画出示意图 第三步 正向思维 选定一个思考问题的起点 逐步提出问题 解决问题 逆向思维 从结论出发分析为达到这个结论应该先有什么 正逆结合 第四步 写出顶层较抽象算法 分析边界情况 第五步 验证第四步的算法 第六步 写出具体算法 第七步 进一步验证 手工运行 双链表 如何求结点p的直接前驱 时间性能 为什么可以快速求得结点p的后继 如何快速求得结点p的前驱 3 3线性表的存储结构及实现 双链表 在单链表的每个结点中再设置一个指向其前驱结点的指针域 双链表 结点结构 data 数据域 存储数据元素 prior 指针域 存储该结点的前趋结点地址 next 指针域 存储该结点的后继结点地址 3 3线性表的存储结构及实现 typedefintDataType DataType为线性表的数据类型typedefstructDulNode DataTypedata structDulNode prior next DulNode first first为双链表的头指针 双链表 启示 时空权衡 空间换取时间 定义结点结构 3 3线性表的存储结构及实现 双链表的操作 插入 s prior p s next p next p next prior s p next s ai 1 ai 操作接口 voidInsert DulNode p DataTypex 注意指针修改的相对顺序 3 3线性表的存储结构及实现 双链表的操作 删除 p prior next p next p next prior p prior 操作接口 DataTypeDelete DulNode p ai 1 ai ai 结点p的指针是否需要修改 free p 3 3线性表的存储结构及实现 循环链表 first a1 ai 1 an ai 从单链表中某结点p出发如何找到其前驱 将单链表的首尾相接 将终端结点的指针域由空指针改为指向头结点 构成单循环链表 简称循环链表 3 3线性表的存储结构及实现 循环链表 3 3线性表的存储结构及实现 first a1 ai 1 an ai 循环链表 插入 算法描述 s Node malloc sizeof Node s data x s next p next p next s 3 3线性表的存储结构及实现 templatevoidLinkList Insert inti DataTypex p first count 0 while p first 循环链表 插入 与单链表的插入操作相比 差别是什么 3 3线性表的存储结构及实现 循环条件 p NULL p firstp next NULL p next first 循环链表 3 3线性表的存储结构及实现 如何查找开始结点和终端结点 循环链表 开始结点 first next终端结点 将单链表扫描一遍 时间为O n 3 3线性表的存储结构及实现 开始结点 rear next next终端结点 rear 循环链表 带尾指针的循环链表 一个存储结构设计得是否合理 取决于基于该存储结构的运算是否方便 时间性能是否提高 3 3线性表的存储结构及实现 静态链表 用数组来表示单链表 用数组元素的下标来模拟单链表的指针 静态链表 data 存储放数据元素 next 也称游标 存储该元素的后继在数组的下标 数组元素 结点 的构成 数据域 指针域 3 3线性表的存储结构及实现 例 线性表 张 王 李 赵 吴 的静态链表存储 012345678 datanext 静态链表 first avail first 静态链表头指针 为了方便插入和删除操作 通常静态链表带头结点 avail 空闲链表头指针 空闲链表由于只在表头操作 所以不带头结点 3 3线性表的存储结构及实现 静态链表 静态链表的存储结构定义如下 constintMaxSize 10 最多10个数组单元typedefintDataType DataType是线性表的数据类型typedefstruct DataTypedata intnext 指针域 也称游标 注意不是指针 SNode SList MaxSize 3 3线性表的存储结构及实现 在线性表 张 王 李 赵 吴 中 王 之后插入 孙 012345678 datanext 静态链表 3 3线性表的存储结构及实现 静态链表 假设结点s插在结点p之后 则修改指针的操作为 s avail 利用空闲链的第一个结点avail SList avail next 空闲链的头指针后移SList s data x 将x填入下标为s的结点SList s next SList p next 将下标为s的结点插入到SList p next s 下标为p的结点后面 3 3线性表的存储结构及实现 在线性表 张 王 李 赵 吴 中删除 赵 012345678 datanext 静态链表 3 3线性表的存储结构及实现 在线性表 张 王 李 赵 吴 中删除 赵 012345678 datanext 静态链表 012345678 datanext 3 3线性表的存储结构及实现 静态链表 假设删除结点p的后继结点 则修改指针的操作为 q SList p next 暂存被删结点的下标SList p next SList q next 摘链SList q next avail 将结点q插在链avail的最前端avail q 空闲链头指针avail指向结点q 3 3线性表的存储结构及实现 静态链表 相对于顺序表而言 静态链表有什么优点 优点 在执行插入和删除操作时 只需修改游标 不需要移动表中的元素 从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点 缺点 没有解决连