《算法与数据结构》PPT课件.ppt

第5章算法与数据结构 5 1算法与数据结构的基本概念 5 1 1算法算法 是一个有穷的指令集 是解决某一问题的运算序列 算法一般应具有以下几个基本特征 1 可行性 2 确定性 3 有穷性 4 有0个或多个输入 5 有一个或多个输出 1 算法的两个基本要素 1 对数据对象的运算和操作1 算术运算 主要有加 减 乘 除等运算 2 逻辑运算 主要有与 或 非等运算 3 关系运算 主要有大于 小于 等于 不等于等运算 4 数据传输 主要包括赋值 输入 输出等操作 2 算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构 一个算法一般都可以用顺序 选择 循环三种基本控制结构组合而成 2 算法设计基本方法 1 列举法列举法是针对待解决的问题 列举所有可能的情况 并用问题中给定的条件来检验哪些是必需的 哪些是不需要的 2 归纳法归纳法是从特殊到一般的抽象过程 通过分析少量的特殊情况 找出一般的关系 3 递归递归分为直接递归与间接递归两种 如果一个算法A显式地调用自己则称为直接递归 如果算法A调用另一个算法B 而算法B又调用算法A 则称为间接递归调用 4 回溯法通过对待解决的问题进行分析 找出一个解决问题的线索 然后根据这个线索进行探测 若探测成功便可得到问题的解 若探测失败 就要逐步回退 改换别的路经进一步探测 直到问题得到解答或问题最终无解 5 1 2算法的事前估计 我们可以在算法运行之前对算法进行估计 它可以分为空间复杂度和时间复杂度 1 算法的空间复杂度算法的空间复杂度是对算法所需存储空间的度量 2 算法的时间复杂度所谓算法的时间复杂度 是指执行算法所需要的计算工作量 通常 一个算法所用的时间等于编译时间加上运行时间 5 1 3数据结构 数据处理 是指对数据集合中的各元素以各种方式进行操作 包括插入 删除 查找 更改等 也包括对数据元素进行分析 数据的组织方式不同 通常对它进行处理时的效率也不同 如 对两个存放相同元素的表进行查找时 一个表中的所有数据元素是没有规律的 而另外一个表中的元素是经过排序的 则对于前者用顺序查询法进行查找 后者采用折半查询法进行查询 可见后者效率较高 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合 数据元素 在数据处理领域中 每一个需要处理的对象都可以抽象成数据元素 数据元素一般简称为元素 作为某种处理 其中的数据元素一般具有某种共同特征 例如 描述一年四季的季节名 春 夏 秋 冬 可以作为季节的数据元素 表示家庭成员的各成员名 父亲 儿子 女儿 可以作为家庭成员的数据元素 表示数值的各个数 35 21 44 70 66 可以作为数值的数据元素 一般情况下 在具有相同特征的数据元素集合中 各个数据元素之间存在着关系 这种关系反映了该集合中的数据元素所固有的一种结构 在数据处理领域中 通常把数据元素之间这种固有的关系简单地用前后件关系 或直接前驱与直接后继关系 来描述 例如 一年四个季节的顺序关系时 则 春 是 夏 的前件 即直接前驱 下同 而 夏 是 春 的后件 即直接后继 下同 1 数据的逻辑结构所谓数据的逻辑结构 是指描述数据元素之间逻辑关系的数据结构 数据的逻辑结构由某一数据对象及该对象中所有数据成员之间的关系 前后件关系 组成 即一个数据结构可以表示成 Data Structure D R 上式中Data Structure表示数据结构 D是数据元素的集合 R是D上的关系 它反映了D中各数据元素之间的前后件关系 例如 设a与b是D中的两个数据 则二元组 a b 表示a是b的前件 b是a的后件 例如 一年四季的数据逻辑结构可以表示为 B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 2 数据的物理结构数据的物理结构 数据的逻辑结构在计算机中的存储方式称为数据的物理结构 它包括数据元素的存储方式和关系的存储方式 一种数据的逻辑结构根据需要可以表示成多种存储结构 常用的存储结构有顺序 链接 索引等存储结构 采用不同的存储结构 其数据处理的效率是不同的 5 1 4线性结构与非线性结构 空的数据结构 如果在一个数据结构中一个数据元素都没有 则称该数据结构为空的数据结构 在一个空的数据结构中插入一个新的元素后就变为非空的数据结构 根据数据元素之间关系的不同特性 一般将数据结构分为两大类型 线性结构与非线性结构 线性结构 如果一个非空的数据结构满足下列两个条件 1 有且只有一个根结点 2 每一个结点最多有一个前件 也最多有一个后件 则称该数据结构为线性结构 线性结构又称线性表 如一年四季这个数据结构就属于线性结构 如图所示 在一个线性结构中插入或删除任何一个结点后还应是线性结构 非线性结构 如果一个数据结构不是线性结构 则称之为非线性结构 如家庭成员间辈分关系的数据结构就属于非线性结构 如图所示 显然 在非线性结构中 各数据元素之间的前后件关系要比线性结构复杂 因此 对非线性结构的存储与处理比线性结构要复杂得多 5 2线性表与线性链表 5 2 1线性表1 线性表的基本概念线性表是最简单且最常用的一种数据结构 一个线性表是n个数据元素的有限序列 表中的每一个数据元素 除了第一个外 有且只有一个前件 除了最后一个外 有且只有一个后件 线性表或是一个空表 或可以表示为 a1 a2 ai an 其中ai i 1 2 n 是属于数据对象的元素 通常也称其为线性表中的一个结点 如26个英文字母的字母表 A B C Z 是一个长度为26的线性表 其中的数据元素是单个字母字符 在稍微复杂的线性表中 一个数据元素还可以由若干个数据项组成 例如 某班的学生情况登记表是一个复杂的线性表 表中每一个学生的情况就组成了线性表中的每一个元素 每一个数据元素包括姓名 学号 性别 年龄和健康状况5个数据项 如表所示 2 线性表的顺序存储结构线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素 线性表的顺序存储结构具有以下两个基本特点 1 线性表中所有元素所占的存储空间是连续的 2 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 在线性表的顺序存储结构中 如果线性表中各数据元素所占的存储空间 字节数 相等 则要在该线性表中查找某一个元素是很方便的 假设线性表中的第一个数据元素的存储地址为LOC b1 每一个数据元素占m个字节 则线性表中第i个元素bi在计算机存储空间中的存储地址为 LOC bi LOC b1 i 1 m 在计算机中的顺序存储结构如图所示 3 顺序表的插入操作在一般情况下 要在第i 1 i n 个元素之前插入一个新元素时 首先要从最后一个 即第n个 元素开始 直到第i个元素之间共n i 1元素依次向后移动一个位置 移动结束后 第i个位置就被空出 然后将新元素插入到第i项 插入结束后 线性表的长度就增加了1 图 a 为长度6的线性表顺序存储在长度为7的存储空间中 现在要求在第5个元素之前插入一个新元素25 具体操作步骤为 首先从最后一个元素开始直到第5个元素 将其中的每一个元素均依次往后移动一个位置 然后将新元素25插入到第5个位置 插入一个新元素后 线性表的长度变成了7 如图 b 所示 这时 为线性表开辟的存储空间已经满了 如果再要插入 则会造成称为 上溢 的错误 4 顺序表的删除操作在一般情况下 要删除第i 1 i n 个元素时 则要从第i 1个元素开始 直到第n个元素之间共n i个元素依次向前移动一个位置 删除结束后 线性表的长度就减小了1 图 a 为一个长度为6的线性表顺序存储在长度为7的存储空间中 现在要求删除线性表中的第3个元素 即删除元素5 具体操作步骤为 从第4个元素开始直到最后一个元素 将其中的每一个元素均依次往前移动一个位置 此时 线性表的长度变成了5 如图 b 所示 5 2 2线性链表 线性表的顺序存储结构具有简单 操作方便等优点 但在做插入或删除操作时 需要移动大量的元素 因此 对于大的线性表 特别是元素变动频繁的大线性表不宜采用顺序存储结构 而是通常采用链式存储结构 在链式存储结构中 存储数据结构的存储空间可以不连续 各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致 链式存储方式既可用于表示线性结构 也可用于表示非线性结构 假设数据结构中的每一个数据结点对应于一个存储单元 这种存储单元称为存储结点 简称结点 在链式存储方式中 要求每个结点由两部分组成 一部分用于存放数据元素值 称为数据域 另一部分用于存放指针 称为指针域 其中指针用于指向该结点的前一个或后一个结点 从而可以表示数据元素之间的逻辑关系 我们把线性表的链式存储结构称为线性链表 线性链表中存储结点的结构如图所示 存储地址i 在线性链表中 用一个专门的指针H 称为头指针 指向线性链表中第一个数据元素的结点 即存放线性表中第一个数据元素的存储结点的序号 从头指针开始 沿着线性链表各结点的指针可以扫描到链表中的所有结点 线性表中最后一个元素没有后件 因此 线性链表中最后一个节点的指针域为空 用 NULL或0表示 表示链表终止 当头指针H NULL 或0 时称为空表 在某些应用中 对线性链表中的每个结点设置两个指针 一个称为左指针 用以指向其直接前驱 另一个称为右指针 用以指向其直接后继 这样的线性链表称为双向链表 5 2 3对线性链表的基本操作 1 在线性链表中查找指定的元素在非空线性链表中寻找包含指定元素值x的前一个结点n的操作过程为 从头指针指向的结点开始向后沿指针进行扫描 直到后面已经没有结点或下一个结点的数据域为x为止 因此 由这种方法找到的结点n有两种可能 当线性链表中存在包含元素x的结点时 则找到的n为首次发现的包含元素x的前一个结点序号 当线性链表中不存在包含元素x的结点时 则找到的n为线性链表中的最后一个结点序号 2 线性链表的插入线性链表的插入操作是指在线性链表中的指定位置上插入一个新的元素 为了要在线性链表中插入一个新元素 首先要为该元素申请一个新结点 以存储该元素的值 然后将存放新元素值的结点链接到线性链表中指定的位置 3 线性链表的删除线性链表的删除是指在线性链表中删除包含指定元素的结点 为了在线性链表中删除包含指定元素的结点 首先要在线性链表中找到这个结点 然后将要删除结点释放 以便于以后再次利用 4 循环链表及其基本操作循环链表的结构与前面所讨论的线性链表相比 具有以下两个特点 1 在循环链表中增加了一个表头结点 表头结点的数据域可以是任意值 也可以根据需要来设置 指针域指向线性表的第一个元素的结点 循环链表的头指针指向表头结点 2 循环链表中最后一个结点的指针域不为空 而是指向表头结点 从而在循环链表中 所有结点的指针构成了一个环 5 3栈和队列 5 3 1栈1 什么是栈栈实际上是一种特殊的线性表 在这种特殊的线性表中 插入与删除操作都只在线性表的一端进行 因此 栈是指被限定仅在一端进行插入与删除操作的线性表 在栈中 允许插入与删除的一端称为栈顶 而不允许插入和删除的另一端称为栈底 栈是按照 后进先出 的原则组织数据的 因此 栈也被称为 后进先出 的线性表 在程序设计语言中 一般用一维数组作为队列的顺序存储空间 通常用指针top来指示栈顶的位置 用指针bottom指向栈底 向栈中插入一个元素称为进栈操作 从栈中删除一个元素称为出栈操作 栈顶指针top动态反映了栈中元素的变化情况 图是栈的示意图 栈顶top 栈底bottom 进栈出栈 2 对栈的操作对栈的基本操作有两种 进栈和出栈 1 进栈操作进栈操作是指在栈顶位置插入一个新元素 其过程是 先将栈顶指针加一 然后将新元素放到栈顶指针指向的位置 当栈顶指针已经指向存储空间的最后一个位置时 说明栈空间已满 不能再进栈 这种情况称为栈 上溢 错误 2 出栈操作出栈操作是指取出栈顶元素 其过程是 先将栈顶指针指向的元素赋给一个指定的变量 然后将栈顶指针减1 当栈顶指针为0时 说明栈空 不能再出栈 这种情况称为栈 下溢 错误 5 3 2队列 1 什么是队列队列是指只允许在一端进行插入 而在另一端进行删除的线性表 允许插入的一端称为队尾 通常用一个称为尾指针 rear 的指针指向队尾元素 允许删除的一端称为队头 通常也用一个队头指针 front 指向队头元素的前一个位置 队列是按照 先进先出 的原则组织数据的 因此队列又称为 后进后出 的线性表 在队列中 队尾指针rear与队头指针front共同反映了队列元素中元素动态变化的情况 下图是队列的示意图 front rear 向队列的队尾插入一个元素称为进队操作 从队列的队头删除一个元素称为出队操作 由上图可知 在队列的末尾插入一个元素 进队操作 只涉及队尾指针rear的变化 而要删除队列中的队头元素 出队操作 只涉及队头指针front的变化 2 循环队列及其操作循环队列是一种将顺序队列臆造为一个环状的空间的方法 通过把存储队列元素的表在逻辑上看成一个环 将队列存储空间的第一个位置作为队列最后一个位置的下一个位置 供队列循环使用 循环队列的初始状态为空 即rear front m 如图所示 A 1 n n21 在循环队列中 用队尾指针rear指向队列中的队尾元素 用队头指针front指向队头元素的前一个位置 因此 从队头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素 循环队列主要有两种基本操作 进队操作与出队操作 每进行一次进队操作 队尾指针加一 当队尾指针rear n 1时 则置rear 1 每进行一次出队操作 队头指针就加一 当队头指针front n 1时 则置front 1 为了能区分队列满还是队列空 通常还需增加一个标志s s值的定义如下 由此可以得出队列空与队列满的条件如下 队列空的条件为s 0 队列满的条件为s 1且front rear 5 4树与二叉树 5 4 1树的基本概念树是一种重要的非线性结构 在这种数据结构中 所有数据元素之间的关系具有明显的层次特性 并以分支关系定义了层次结构 下图是一棵树的例子 现实世界中有很多可以用树来表示的例子 例如图中的树表示了高校中院系之间的关系 树中每一个结点只有一个直接前驱 称作父结点 没有直接前驱的结点只有一个 称作树的根结点 简称为树的根 例如 在上图中 结点沈阳工业大学是树的根结点 每一个结点可以有多个直接后继 它们都称为该结点的子女 没有直接后继的结点称为叶子结点 如 图中的结点理学院 数学教研室等 除树根以外的其它结点被划分为多个互不相交的有限集合 每个集合又是一棵树 被称为根的子树 结点所拥有的子树的棵树被称为该结点的度 如上图中沈阳工业大学根节点的度是4 理学院的度是2 树中所有结点的度的最大值称为树的度 例如 图中所示的树的度为4 用树来表示算术表达式的原则如下 1 算术表达式中的每一个运算符对应于树中的一个结点 2 运算符的任一运算对象皆为该运算符结点的子树 3 运算对象中的单个变量均为叶子结点 下图是用树结构对表达式a b c d x y z e的表示 注意 表示一个表达式的表达式树可能并不唯一 5 4 2二叉树及其基本性质 1 什么是二叉树二叉树是另一种树型结构 当然二叉树也是一种非线性结构 它的特点是 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 顺序不能颠倒 分别称为该结点的左子树与右子树 可见在二叉树中 不存在度大于2的结点 从而所有子树也均为二叉树 另外 在二叉树中 一个结点可以只有左子树而没有右子树 也可以只有右子树而没有左子树 当一个结点既没有左子树也没有右子树时 该结点即是叶子结点 下图是一棵深度为3的二叉树 2 二叉树的基本性质性质1在二叉树的第i层上 最多有 i 1 个结点 性质2深度为m的二叉树最多有 1个结点 性质3在任意一棵二叉树中 度为0的结点 即叶子结点 总是比度为2的结点多一个 性质4具有n个结点的二叉树 其深度至少为 log2n 1 其中 log2n 表示取log2n的整数部分 2i 1 2m 3 满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树 1 满二叉树满二叉树是一棵深度为m且有 1个结点的二叉树 该二叉树每一层上的所有结点数都达到最大值 2m 2 完全二叉树完全二叉树除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 称之为完全二叉树 由满二叉树与完全二叉树的特点可以看出 满二叉树也是完全二叉树 而完全二叉树一般不是满二叉树 5 4 3二叉树的存储结构 在计算机中 二叉树通常采用链式存储结构 用于存储二叉树中各元素的存储结点由两部分组成 数据域与指针域 但在二叉树中 由于每一个元素可以有两个子结点 因此 用于存储二叉树的存储结点的指针域有两个 一个用于指向该结点的左子结点 称左指针域 另一个用于指向该结点的右子结点 称为右指针域 由于二叉树的存储结构中每一个存储结点有两个指针域 因此 二叉树的链式存储结构也称为二叉树链表 5 4 4二叉树的遍历 二叉树的遍历 是指不重复地访问二叉树中的所有结点 在遍历二叉树的过程中 一般先遍历左子树 然后再遍历右子树 在先左后右的原则下 根据访问根结点的次序 二叉树的遍历可以分为三种 前序遍历 中序遍历 后序遍历 1 前序遍历所谓前序遍历是指首先访问根结点 然后遍历左子树 最后遍历右子树 并且 在遍历左 右子树时 仍然先访问根结点 然后遍历左子树 最后遍历右子树 下面是二叉树中序遍历的简单描述 若二叉树为空 则结束返回 否则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 2 中序遍历所谓中序遍历是指首先遍历左子树 然后访问根结点 最后遍历右子树 并且 在遍历左 右子树时 仍然先遍历左子树 然后访问根结点 最后遍历右子树 下面是二叉树中序遍历的简单描述 若二叉树为空 则结束返回 否则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 3 后序遍历所谓后序遍历是指首先遍历左子树 然后遍历右子树 最后访问根结点 并且 在遍历左 右子树时 仍然先遍历左子树 然后遍历右子树 最后访问根结点 下面是二叉树后序遍历的简单描述 若二叉树为空 则结束返回 否则 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点 5 5查找和排序技术 5 5 1查找技术1 顺序查找顺序查找的基本方法是 从线性表的第一个元素开始 逐个将线性表中的元素与被查元素进行比较 若相等则表示找到 即查找成功 若线性表中所有的元素都与被查元素进行了比较但都不相等 则表示线性表中没有要找的元素 即查找失败 虽然顺序查找的效率不高 但在下列两种情况下只能采用顺序查找 1 如果线性表为无序表 则只能用顺序查找 2 采用链式存储结构的有序线性表 只能采用顺序查找 2 折半查找折半查找只适用于顺序存储的有序表 也就是说 线性表中的元素已经按值非递减排列 假设有序线性表的长度为m 被查元素值为x 则折半查找的方法如下 将x与线性表的中间项的元素值进行比较 若中间项的值等于x 则查找成功 结束返回 若x小于中间项的值 则在线性表的前半部分用相同的方法进行查找 若x大于中间项的值 则在线性表的后半部分用相同的方法进行查找 这个过程一直进行到查找成功或线性表中没有这个元素为止 5 5 2排序技术 1 插入排序所谓插入排序 是指将无序序列中的各元素依次插入到已经有序的线性表中 1 简单插入排序简单插入排序的基本思想是 将一个新元素插入到已经排好序的有序序列中 从而元素的个数增一 并成为新的有序序列 在简单插入排序过程中 由于每一次比较后最多去掉一个逆序 因此 这种排序方法的效率在最坏情况下 需要n n 1 2次比较 2 希尔排序希尔排序的基本思想是 将整个初始序列分割成若干个子序列 对每个子序列分别进行简单插入排序 最后再对全体元素进行一次简单插入排序 由此可见 希尔排序也是一种插入排序方法 2 交换排序所谓交换排序是指借助数据元素之间的互相交换进行排序的一种方法 冒泡排序法与快速排序法都属于交换类的排序方法 1 冒泡排序冒泡排序的过程简单 它的基本思想是通过对相邻元素进行比较 并根据比较的结果交换位置 从而逐步由任意序列变为有序序列 具体过程是 首先 将第一个元素和第二元素进行比较 若为逆序 则交换之 接下来对第二个元素和第三个元素进行同样的操作 并依次类推 直到倒数第二个元素和最后一个元素为止 其结果是将最大的元素交换到了整个序列的尾部 这个过程叫做第一趟冒泡排序 而第二趟冒泡排序是在除去这个最大元素的子序列中从第一个元素起重复上述过程 直到整个序列变为有序为止 排序过程中 小元素好比水中气泡逐渐上浮 而大元素好比大石头逐渐下沉 冒泡排序故此得名 假设初始序列的长度为n 冒泡排序需要经过n 1趟排序 需要的比较次数为n n 1 2 下图是冒泡排序的示意图 初始序列第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后2618181818918262626915323232915185447915264791532915471554 2 快速排序快速排序法就是一种可以通过一次交换而消除多个逆序的排序方法 其基本思想如下 任取待排序序列中的某个元素对象作为基准 按照该元素值的大小 将整个序列划分为左右两个子序列 这个过程称为分割 左侧子序列中所有元素的值都小于或等于基准对象元素的值 右侧子序列中所有元素的值都大于基准对象元素的值 基准对象元素则排在这两个子序列中间 这也是该对象最终应该被安放的位置 接下来分别对这两个子序列重复进行上述过程 直到所有的对象都排在相应位置上为止 3 选择排序选择排序的基本思想是 每一趟排序过程都是在当前位置后面剩下的待排序对象中选出元素值最小的对象 放到当前的位置上 1 简单选择排序简单选择排序的基本步骤是 1 在一组对象S i S n 1 中选择元素值最小的对象 2 若它不是这组对象中的第一个对象 则将它与这组对象中的第一个对象对调 3 在剩下的对象中重复执行上述两步 直到只剩下一个对象为止 下图是这种排序法的示意图 图中有方框的元素是刚被选出来的最小元素 2 堆排序堆排序法属于选择类的排序方法 堆的定义如下 具有n个元素的序列 a1 a2 an 当且仅当满足 i 1 2 n 2 时称之为堆 根据堆的定义和堆的调整过程 可以得到堆排序的方法如下 1 首先将一个无序序列建成堆 2 然后将堆顶元素与堆中最后一个元素交换 并将除了已经换到最后的那个元素之外的其它元素重新调整为堆 反复做第 2 步 直到所有的元素都完成交换为止 从而得到一个有序序列 堆排序的方法对于规模较小的线性表并不合适 但对于较大规模的线性表来说是很有效的