算法与数据结构基础.ppt

1 82 第六章算法与数据结构基础 计算机程序主要对数据进行加工和处理 程序中需要说明 数据结构 数据的组织形式和存储方式 算法 操作数据的步骤和方法 数据结构 算法 2 82 6 1数据结构基本概念 随着计算机技术的发展 其应用领域越来越广 计算机应用已不在局限于数值计算 更多地用于数据处理和信息管理等非数值计算 例如 学生 图书 财务和人事等信息管理系统 每个学生对应一个数据 由学号 姓名 性别和出生日期等多个数据项构成 通常对学生信息进行插入 删除或查找等操作 3 82 数据结构的定义 数据结构是指具有相同特征 相互之间有关联的数据集合 现实世界中每个对象都可以映像成数据元素 数据元素可以由一个数 一个字符或一个名字等单个数据项组成 也可以由多个数据项组成 数据元素 结点 数据结构中数据元素都具有某种共同特征数据结构中数据元素之间存在着某种关系 4 82 向量 2 43 68 45 32 是数据结构 每个数据元素由一个数据项组成数据元素之间有位置上的前后关系 每个数据元素由一个数据项组成数据元素之间有位置上的前后关系 季度名称组成的集合是数据结构 春 夏 秋 冬 家庭成员 祖父 父亲 儿子 是数据结构 每个数据元素由一个数据项组成数据元素之间有层次上的高低关系 5 82 数据结构是指带有结构特性的数据元素集合 主要研究 数据集合中数据元素之间所固有的关系 即数据逻辑结构 数据处理时数据在计算机中的存储关系 即数据存储结构 物理结构 对数据所进行的操作 即算法 6 82 数据逻辑结构 数据结构中数据元素之间所固有的关系描述成前后件 前驱与后继 关系 数据之间前后件关系是它们之间的逻辑关系 与它们在计算机中的存储位置无关 因此将这种关系称为逻辑结构 7 82 一个数据结构可以表示为S D R 季节数据结构可以定义成S D R 其中 D 春 秋 冬 夏 R 春 夏 夏 秋 秋 冬 S表示数据结构 D数据元素集合 向量数据结构可以定义成S D R 其中 D 2 43 68 45 32 R 2 43 43 68 68 45 45 32 8 82 线性结构 一般来说 数据之间有集合 线性 树型和图形4种基本逻辑结构 数据元素之间是一对一的关系除第一个结点无前件外 其他结点都只有一个前件除最后一个结点无后件外 其他结点都只有一个后件 9 82 数据之间存在一对多的关系一个结点最多有一个前件 可以有多个后件前件与后件之间有层次关系 一般来说 数据之间有集合 线性 树型和图形4种基本逻辑结构 树型结构 10 82 数据元素之间存在多对多的关系一个结点可以有多个前件和多个后件 一般来说 数据之间有集合 线性 树型和图形4种基本逻辑结构 图形结构 11 82 一般来说 数据之间有集合 线性 树型和图形4种基本逻辑结构 集合 是一种松散结构 数据元素之间的关系只是同属于一个集合 可以用其他结构来表示 12 82 数据物理结构 数据在计算机存储器中的存储方式称为数据物理结构 数据存储结构 在数据存储结构中 不仅要存放各个数据元素信息 还要存放数据元素之间前后件关系信息 数据元素在计算机中通常有四种存储方式 顺序 链式 索引和散列 13 82 顺序存储结构 顺序存储结构是在内存中开辟一块连续内存单元用于存放数据 逻辑上相邻的结点在物理位置上也相邻 即 结点之间的逻辑关系由存储单元的相邻关系来体现 14 82 有如下顺序关系 a b c d 例如 a 地址 2000H 2001H c 2002H 2003H d 数据 顺序存储结构 如果在b和c之间增加新数据x构成 a b x c d 的顺序关系 应该如何存储 b 15 82 链式存储结构 链式存储结构中 结点由两部分组成 用于存放数据元素 数据域 用于存放前件或后件的存储地址 指针域 即 通过指针反映数据元素之间的逻辑关系 16 82 链式存储结构 有如下顺序关系 a b c 例如 a 2000 b c 3001 1003 3001 1003 17 82 顺序存储结构与链式存储结构比较 顺序存储结构 优点 每个结点占用存储空间最少缺点 如果数据元素很多 则可能找不到一块足够大的连续存储单元 不能很好利用存储单元 容易产生碎片 链式存储结构 优点 充分利用所有存储单元缺点 每个结点占用较多存储单元 18 82 链式存储的插入 J L U 在J L之间插入接点S 链式存储的删除 J L U 删除接点L 显然 链式存储的插入和删除操作比较简单 方便 19 82 6 2算法基本概念 程序包含两方面的内容 对数据的描述 对操作的描述算法就是操作步骤 是解决 做什么 和 怎么做 的问题 算法是程序的灵魂 广义来说 为解决一个问题而采取的方法和步骤就称为算法 20 82 计算机算法分为 数值算法 非数值算法 各种数学问题的解法 常用于事物管理领域 如排序 查询 算法是定义在逻辑结构上的操作 独立于计算机 但算法的实现依赖于数据的存储结构 21 82 算法的特征 可行性确定性有穷性输入输出 采取的方法和步骤可行 结果另人满意 算法中的每一个步骤都必须确定 不能产生歧义 执行算法时从外界取得必要的信息 一个算法可以有零或多个输入 算法得到的结果就是输出 没有输出的算法是没有意义的 一个算法应该有一个或多个输出 算法必须由有限步组成 并能在有效时间内完成 22 82 算法描述方法 计算 写出其算法 分析 1 展开上面算式S 1 2 3 99 100 23 82 计算 写出其算法 main ints 0 s 1 s s 2 s s 3 s s 99 s s 100 printf s d n s 利用程序设计中的顺序结构 很不理想算法 24 82 用于描述算法的工具很多 通常有流程图 N S图 自然语言和伪代码等工具 自然语言 带序号的人类语言描述方法 将变量s清0 将变量n置1 把s n的值赋给s 把n 1的值赋给n 判断n 100 是否成立 若成立 转3 否则转66 输出s的值 S 1 2 3 99 100 特点 易懂却不直观 对复杂算法描述很困难 易产生歧义 若成立 25 82 伪代码法 是一种假的代码 不能被计算机所理解 但可以用你熟悉的计算机语言的语句加上自然语言构成 26 82 用于描述算法的工具很多 通常有流程图 N S图 自然语言和伪代码等工具 流程图法 用一些图框 线条以及文字说明来形象地 直观地描述算法 符号说明 27 82 开始 0S 1n S nS n 1n 输出S 结束 T F n 100 S 1 2 3 99 100 优点 直观形象缺点 算法复杂时 篇幅较多 费时且不方便修改 28 82 N S图 完全去掉了带箭头的流程线 算法的所有处理步骤都写在一个大矩形框内 框内还可以包含一些从属于它的小矩形框 适于结构化程序设计 29 82 算法评价 在计算机程序设计中 某一任务的算法设计得优与劣 将直接影响程序的运行效率 稳定性和可维护性 通常从以下4个方面评价一个算法 正确性可读性健壮性执行效率 算法本身没有语法错误 执行时输入正确数据能够得到正确结果 算法要容易理解和阅读 容易实现 同时也要便于程序维护和完善 指算法执行的时间性能和空间性能 算法能够对输入的各种数据给予适当的提示和处理 30 82 算法复杂度 算法复杂度是对算法效率的度量 是评价算法优劣的重要依据 一个算法复杂度高低体现在运行该算法所需要资源的多少 时间资源空间 即存储器 资源 因而 算法复杂度包含时间复杂度和空间复杂度 时间复杂度指执行算法所需时间 执行时间 语句执行时间 语句执行次数 空间复杂度指在算法执行过程中 所占用附加空间数量 31 82 6 3典型数据结构 数据逻辑结构分为 线性结构 非线性结构 有且只有一个开始结点和一个终端结点 并且每个结点最多只有一个前件和一个后件 线性结构也称为线性表 栈 队列 数组和串等是特殊线性表 非线性结构包括树和图 32 82 6 3 1线性表 线性表是一组特征相同数据的有限序列 表示为L a1 a2 a3 an 非空线性表的特征 除a1无前件外 其它任意数据元素ai有且只有一个前件ai 1 除了an无后件外 其它任意数据元素ai有且只有一个后件ai 1 线性表中数据元素个数n n 0 称为线性表长度 当n 0时 称为空表 在非空线性表中 每个数据元素都有一个确定位置 其位置取决于它的序号 a1是第一个元素 a2是第二个元素 an是最后一个元素 33 82 向量 2 43 68 45 32 是线性表 季度名称 春 夏 秋 冬 是线性表 学生基本信息 20040001 刘强 男 1984 02 13 14001 机械制造 20040002 王晓红 女 1986 05 06 14001 机械制造 20040003 李明 男 1984 10 25 14001 机械制造 是线性表 34 82 线性表顺序存储结构具有以下两个基本特点 线性表中所有元素所占的存储空间是连续的 线性表中各元素在存储空间中按逻辑顺序依次存放 即线性表的逻辑结构与存储结构相一致 线性表通常采用顺序存储结构或链式存储结构 由此可以看出 在线性表的顺序存储结构中 其前后两个元素在存储空间中是紧邻的 前件元素一定存放在后件元素的前面 35 82 例如 线性结构 a1 a2 a3 其中每个数据元素占2个存储空间 假设存储a1的首地址为2000 2000 a1 占2个字节 a2 a3 2004 2002 占2个字节 占2个字节 存储地址 结论 假设一个数据元素占用d个字节 线性表的首地址Addr a1 为K 则存储任意一个数据元素ai的首地址为 Addr ai Addr a1 i 1 d K i 1 d其中1 i n 优点 可以方便地随机读取表中任意元素缺点 插入和删除运算需要移动大量元素 浪费大量时间 时间效率较低 36 82 线性表的链式存储 用一组存储单元 可以连续 也可以不连续 存储线性表中数据元素 为了反映数据元素之间的逻辑关系 每个数据元素由两部分组成 1用于存放数据元素 数据域 2用于存放前件或后件的存储地址 指针域 结点之间逻辑关系由指针域来确定 37 82 单链表 定义 每个结点只有一个指针域的链表 head 每个单链表都有一个头指针 存放表中第一个结点的存储地址 每个结点指针域存放后件结点的存储地址 最后一个结点无后件结点 指针域为空 用NULL或 表示 38 82 循环链表 循环链表中增设一个表头结点 其数据域的值可以任意或根据情况来设置 指针域指向第一个结点 将单链表最后一个结点的空指针域改为指向该链表的第一个结点 即首尾相连 空循环链表 非空循环链表 注意头指针和表头结点的区别 39 82 循环链表特点 从表中任一结点出发 均可以找到其它所有结点 在任何情况下 带有表头结点的循环链表中至少有一个结点存在 从而使空表和非空表运算统一 循环链表运算与单链表区别 对单链表进行操作时 要判断是否是表尾 即指针是否为NULL 而对循环链表操作时 要判断是否是头指针 40 82 6 3 2栈 定义 栈是只能在表的一端进行插入和删除运算的线性表 通常将允许插入和删除运算的一端称为栈顶 top 另一端称为栈底 bottom 不含元素的栈称为空栈 向栈中插入元素称为入栈 从栈中删除元素称为出栈 41 82 设有一个栈S a1 a2 an 入栈顺序是a1 a2 最后是an 栈的状态如图所示 a1 a2 an 栈底bottom 栈顶top 入栈 出栈 栈特点 后进先出 故也称为 先进后出 表或 后进先出 表 42 82 栈的基本运算 栈初始化 构造一个空栈 空栈判断 判断栈是否为空 入栈 在栈顶插入一个元素 出栈 在栈顶删除一个元素 读栈 仅读取栈顶数据 并不删除元素 43 82 栈的顺序存储 设用变量top表示栈顶位置 用n表示栈中最多能容纳元素的个数 栈顺序存储结构是用一块连续存储区域存放栈中元素 连续区域的低地址一端作为栈底 栈底固定不变 44 82 入栈运算 S1 如果top n 则栈已满 提示入栈失败 栈 上溢 错误 并结束入栈 S2 top 1 top S3 将新元素放在当前栈顶位置 top 上 a1 a2 a3 bottom top a4 45 82 出栈运算 S1 如果top 0 则栈为空 提示出栈失败 栈 下溢 错误 并结束出栈 S2 将当前栈顶 top 元素赋给一个变量 S3 top 1 top a3 top a1 a2 bottom 46 82 例如 容量为6的栈中已有3个元素 如图所示 1 2 3 4 5 6 A C B bottom top X Y两个元素先后入栈 X Y 元素Y出栈 47 82 6 3 3队列 允许在一端进行插入 而在另一端进行删除的线性表 允许插入的一端称为队尾 允许删除的一端称为队头 入队 退队 队尾 a b c 队头 48 82 队列的基本运算 初始化队列空队列判断入队运算出队运算读队头元素队列长度 49 82 队列顺序存储及其常用运算 队列的特点 先进先出 入队和出队运算时队头和队尾位置要发生变化 队头 front 指向第一个元素的前一个单元位置 队尾 rear 指向最后一个元素的位置 队列中容纳元素个数为n 50 82 创建一个空队列 并令front rear 1 1 初始化队列 front 1 2 0 1 rear 51 82 2 入队运算 S1 如果rear n 1 则队列已满 提示入队失败 队列 上溢 错误 并结束入队 S2 rear 1 rear S3 将新元素放在当前队列位置 rear 上 front rear 1 2 0 1 A B C 52 82 3 退队运算 S1 如果front rear 则队列已空 提示退队失败 队列 下溢 错误 并结束退队 S2 front 1 front S3 取front所指元素 front rear 1 2 0 1 A B C 此时虽然队列有空位置 但也不能插入新结点 53 82 循环队列 将队列存储空间的最后一个位置绕到第一个位置 形成逻辑上的环状空间 这样可以把退队的空间利用起来 0 2 3 1 0 2 1 3 4 54 82 循环队列的运算 1 初始化队列 创建一个空队列 并令front rear 0 1 3 2 4 0 front rear 55 82 S1 先判断队列是否已满 若队满则入队失败 否则元素入队S2 rear 1 n rear当rear 1 n时 0 rearS3 将新元素放在当前队尾位置 rear 循环队列的运算 2 入队运算 1 3 2 4 0 rear front a b c 例如 插入结点a b c 显然 再插入两个结点后front rear 此时为满队列 56 82 循环队列的运算 3 出队 退队 运算 S1 先判断队列是否为空 若队空则出队失败 上溢 S2 front 1 n front当front 1 n时 0 front 0 2 1 3 4 a b c rear front 例如 删除结点a 显然 再删除两个结点后front rear 此时为空队列 因此 通常需要增加一个变量用来标识当front rear时 队列是满还是空 57 82 6 3 5树 树是一种常用的非线性结构 树是由n n 0 个结点组成的有限集合 当n 0时 称为空树 否则 有且仅有一个根结点 当n 1时 其余结点被分成m m 0 个互不相交的子集T1 T2 Tm 每个子集又是一棵树 树是递归定义的 即一棵树由根及若干子树构成 每棵子树又是由更小的子树构成 58 82 结点的度 一个结点所拥有后件个数树的度 树中所有结点的最大度 根 子结点 叶结点 59 82 结点的层次从根结点算起 根结点在第一层 根的直接后继结点在第二层 同一层上所有结点的后继结点均在下一层 1 2 3 4 树中结点的最大层次称为树的深度或高度 60 82 6 3 6二叉树 非空二叉树有且只有一个根结点 每个结点最多有两棵子树 且有左右之分 二叉树是另一种树形结构 每个结点最多只有两个后件 即最大度为2 特点 61 82 二叉树有五种基本形态 62 82 二叉树基本性质 性质一 在二叉树的第i层上 最多有2i 1个结点 i 1 性质二 深度为k的二叉树最多有2k 1个结点 k 1 性质三 对于任意一棵二叉树 度为0的结点 即叶子结点 总比度为2的结点多一个 63 82 满二叉树 如果一个深度为k的二叉树拥有2k 1个结点 则称它为满二叉树 每一层的结点数都达到最大值 叶子结点都在最下面的同一层上 完全二叉树 一棵深度为k的二叉树 如果第一层到第k 1层是一棵满二叉树 第k层上的结点数没有达到最大值2k 1 但这些结点都满放在该层最左边 则称此二叉树为完全二叉树 如果某个结点没有左子树 则它一定没有右子树 64 82 注 满二叉树是完全二叉树 但完全二叉树不一定是满二叉树 65 82 完全二叉树性质 12个结点的完全二叉树 性质一 具有n个结点的完全二叉树的深度为 log2n 1 其中 log2n 表示取log2n的整数部分 66 82 完全二叉树性质 性质二 在有n个结点的完全二叉树中 将所有结点按从上到下 从左到右的顺序用自然数1 2 n进行编号 则对于编号为k的结点有如下结论 k 1时 该结点为根结点 k 1时 该结点的父结点编号为int k 2 2k n时 编号为k的结点的左子结点编号为2k 否则无左子结点 2k 1 n时 编号为k的结点的右子结点编号为2k 1 否则无右子结点 1 2 3 4 5 6 7 10 11 9 8 12 67 82 二叉树的顺序存储 二叉树顺序存储是指用一组连续存储单元存储二叉树中的结点 结点存储顺序是按着从上到下 从左到右顺序 1234567 按照完全二叉树每个结点编号的顺序存放结点 通过结点的编号准确地反映结点之间的逻辑关系 1 2 3 4 5 6 7 68 82 非完全二叉树顺序存储 A C B E G F 1234567 显然 顺序结构适用于完全二叉树 对于非完全二叉树 会浪费许多存储空间 69 82 二叉树链式存储 二叉树每个结点由数据域和指针域组成 两个指针域 o一个用于指向左子结点o一个用于指向右子结点 常见二叉树结点结构如图 数据域 存储左子结点的存储地址 存储右子结点的存储地址 70 82 二叉树链式存储 A T X B C P Z Y BT 71 82 二叉树的遍历 遍历二叉树是指按照某种顺序访问二叉树中每个结点的过程 每个结点被访问一次且仅一次 根据对根访问的次序 二叉树的遍历分为先序遍历 中序遍历和后序遍历 72 82 先序遍历 访问根结点 先序遍历左子树 先序遍历右子树 A 遍历结果 T B Z X C P Y 因为左子树空 故遍历右子树 73 82 中序遍历 中序遍历左子树 访问根结点 中序遍历右子树 A T Z B C X Y P 因为左子树空 遍历结果 74 82 后序遍历左子树 后序遍历右子树 访问根结点 后序遍历 遍历结果 A T Z B C X Y P 因为左子树空 故遍历右子树 75 82 6 4典型算法 对非数值型数据通常有插入 删除 查找和排序等操作 其中查找和排序是数据处理中比较重要的算法 查找又称检索 是指在数据集合中查找某个数据元素的过程 若存在这样数据元素 则查找成功 否则 查找失败 6 4 1查找 76 82 1顺序查找 适用于线性表 其基本方法是 从线性表中第一个元素开始 依次将线性表中的元素与给定值进行比较 若相等 则查找成功 若直到最后一个元素 还没找到与给定值相等的元素 则查找失败 77 82 例如 在顺序表 88 15 23 80 63 8 86 46 71 101 中 查找值为71的数据元素 从线性表中第一个元素88开始 依次将线性表中元素与71进行比较 直到第九个元素为71 查找成功 特点 顺序查找算法简单 但是执行效率较低 在下列两种情况下 只能使用顺序查找法 线性表是线性链表 线性表是顺序表 但表中元素无序排列 此题比较了9次 78 82 2二分查找 又称折半查找 要求被查找的表采用顺序存储结构且数据元素按数据值升序或降序排列 即二分查找法只适用于有序表 基本思想是 设顺序表升序排列 将给定值与中间位置元素比较 若相等 则查找成功 若给定值小于元素值 则继续对前半部分再进行折半查找 若给定值大于中间位置元素值 则继续对后半部分再进行折半查找 79 82 例 在有序顺序表 8 15 23 46 63 71 80 86 88 101 中 用折半查找法查找值为71的数据元素 key 718152346637180868810112345678910 第一次查找mid 5 第二次查找mid 8 第三次查找mid 6 71808688101678910 63 71 故在后半部分进行折半查找 86 71 故在前半部分进行折半查找 718067 71 71 查找成功 80 82 2 排序算法 排序是将一组无序数据按值递增 或递减 进行重新排列 三类基本排序方法 交换排序法 选择排序法 插入排序法 81 82 1交换排序法 在排序过程中 通过数据元素之间不断地进行比较与交换 最终达到排序目的 冒泡排序法的基本思想是 对所有相邻元素进行比较 若逆顺 则将其交换 最终达到有序化 82 82 交换排序法 原序列 42 23 16 47 11 45 13 49 42 23 16 47 11 45 13 49 第1遍 第2遍 第3遍 第4遍 第5遍 第6遍 23 16 42 11 45 47 13 49 16 23 11 42 45 13 47 49 16 23 11 42 45 13 47 49 11 23 16 13 45 42 47 49 11 13 16 23 45 42 47 49 83 82 2选择排序法 简单选择排序法的基本思想是 1扫描整个序列 从中选出最小元素 将它交换到最前面 2再从剩余子序列中 选出最小元素 交换到子序列最前面 3依次类推 直到子序列长度为1为止 每次从待排序数据序列中 选择出最小元素并定位到待排序 升序 序列最前面 由于每遍扫描只能确定一个元素位置 所以对于长度为n的序列 需要扫描n 1遍才能将每个元素位置确定下来 84 82 原序列 42 23 16 27 11 45 13 49 选择排序法 第1遍选择 42 23 16 27 11 45 13 49 11 23 16 27 42 45 13 49 第2遍选择 11 13 16 27 42 45 23 49 第3遍选择 11 13 16 27 42 45 23 49 第4遍选择 11 13 16 23 42 45 27 49 第5遍选择 11 13 16 23 27 45 42 49 第6遍选择 11 13 16 23 27 42 45 49 第7遍选择 85 82 3插入排序法 插入排序是不断地将待排序的元素插入到前面的有序序列中 直至所有元素都进入有序序列 简单插入排序又称直接插入排序 基本思想是 将由n个元素组成的序列分成前后两个子序列 前者为有序序列 后者为无序序列 86 82 将待排序序列中第一个元素作为有序序列 将第二个元素插入到有序序列中 形成由两个元素组成的有序序列 再将第三个元素插入到有序序列中 依此类推 直到最后一个元素插入到有序序列中 形成n个元素组成的有序序列 简单插入排序的步骤 87 82 插入排序法 原序列 42 23 16 27 11 45 13 49 第1遍 23 42 16 27 11 45 13 49 第2遍 16 23 42 27 11 45 13 49 第3遍 16 23 27 42 11 45 13 49 第4遍 11 16 23 27 42 45 13 49 第5遍 11 16 23 27 42 45 13 49 第6遍 11 16 23 27 42 45 49 13 第7遍 13 16 23 27 42 45 49 11