第5章数据结构基础 ppt课件_1

刘传平刘传平 中国地质大学（北京） 计算机技术应用基础 第 5章 数据结构基础 J5.1 引言 J5.2 线性结构 J5.3 树形结构 J5.4 内部排序 J5.5 检索（查找） 5.1 引言 J5.1.1 什么是数据结构 C数据之间的相互关系 J5.1.2 数据的逻辑结构 J5.1.3 数据的存储结构 J5.1.4 数据的运算 C检索、插入、更新、排序 5.1.2数据的逻辑结构 J集合 ：无其他关系 J线性结构 ：一对一 J树形结构 ：一对多 J图形结构 ：多对多 5.1.3 数据的存储结构 J数据的逻辑结构在计算机存储器中的实 现，也称 物理结构 J顺序映射方式 J链接映射方式 J索引映射方式 J散列映射方式 5.2 线性结构 J5.2.1 线性表 J5.2.2 栈 J5.2.3 队列 J5.2.4 链表 5.2.1 线性表 v线性列表是一个 列表 ，列表内每个元素 都有 唯一的后继元素 (除去最后一个元 素 )。线性表具有顺序结构。 J向量（一维数组）：类型相同、有序 插入 删除 5.2.2 栈 J栈是一种 线性表 ， 对栈的添加和删除只 能在 “ 栈顶 ” 进行 。 1、入栈 push J入栈在入栈在 栈顶添加新的元素栈顶添加新的元素 ，入栈后，入栈后， 新的新的 元素成为栈顶元素成为栈顶 。如果没有足够的空间，栈。如果没有足够的空间，栈 处于溢出状态，不能添加元素。处于溢出状态，不能添加元素。 2、出栈 pop J出栈出栈 将栈顶元素移走并返回给用户将栈顶元素移走并返回给用户 。当最。当最 后一个元素被删除后，栈为空，当栈为空后一个元素被删除后，栈为空，当栈为空 时不能再执行出栈操作。时不能再执行出栈操作。 5.2.3 队列 J队列也是一种线性表。数据 只能在称为 “ 尾部 ” 的一端插入，只能从称为 “ 头 部 ” 的一端删除 。 1、入列 J入列入列 enquene操作将数据操作将数据 插入队尾，新元插入队尾，新元 素成为队尾素成为队尾 。空间用完后，不能插入数据。空间用完后，不能插入数据 。 2、出列 J出列出列 dequeue从队首移出数据并返回给用从队首移出数据并返回给用 户户 。队列中没有数据时，不能执行出列。队列中没有数据时，不能执行出列。 5.2.4 链表 J1、链接栈 2、链式队列 5.3 树形结构 J5.3.1 树及其遍历 J5.3.2 二叉树 J5.3.3 遍历二叉树 5.3.1 树及其遍历 J树包括一组有限的元素，这些元素称为 结点 ；同时包括一组有向线段，用来连 接结点，称为 分支 。 J一个结点的子树个数称为该结点的 度数 5.3.2 二叉树 J二叉树是结点的有限集合，此集合或为 空集，或为由一个根结点和两棵互不相 交的称为左右的二叉树构成 J深度 ：树中结点的最大层次 J平衡因子 ：二叉树中任一结点的右子树 与左子树的深度之差 J平衡二叉树 ：所有结点的平衡因子的绝 对值不大于 1的二叉树 5.3.3 遍历二叉树 J遍历二叉树是按照 预定的顺序处理每一 个节点且仅处理一次 。 J先根顺序遍历 、 中根顺序遍历 、 后根顺序遍 历 先序遍历 J在在 先序遍历先序遍历 (DLR)中，首先访问根，再访中，首先访问根，再访 问左子树，最后访问右子树。问左子树，最后访问右子树。 ABCDEF 中序遍历 J在在 中序遍历中序遍历 (LDR)中，首先处理左子树，中，首先处理左子树， 再访问根，最后访问右子树。再访问根，最后访问右子树。 CBDAEF 后序遍历 J在在 后序遍历后序遍历 (LRD)中，首先处理左子树，中，首先处理左子树， 再访问右子树，最后访问根。再访问右子树，最后访问根。 CDBFEA 练习 J一棵二叉数共有 10个节点（分别用 A、 BJ 表示），已知树的中序遍历结果为： DHBEAFCIGJ，前序遍历结果为： ABDHECFGIJ。 回答下列问题。 C请画出这棵二叉树。 C写出该树的后序遍历结果。 5.5 内部排序 J5.5.1 简单插入排序 J5.5.2 简单选择排序 J5.5.3 冒泡排序 5.5.1 简单插入排序 J列表被分成两个子列表： 已排序 和 未排 序 的；初始时已排序部分为空。 J在每次扫描过程中，取出未排序列表中 的第一个元素，然后转到已排序列表中 ，将其 插入到合适的位置上 。每次扫描 ，未排序列表增加 1个，已排序列表减 少 1个。 J对于 n个数据，需要进行 n-1次扫描 。 插入排序 插入排序示意 插入排序示意 5.5.2 简单选择排序 J列表被分成两个子列表： 已排序 和 未排序 的 ；初始时已排序部分为空。 J排序时， 从未排序列表中找到最小元素，与 第一个元素交换 。 J经过选择和交换后，将未排序列表中的第一 个元素划入排序列表中，这一过程称为一次 扫描 。每次扫描后，未排序列表减少一个元 素，已排序列表增加一个元素。 J对于 n个数据，需要进行 n-1次扫描 。 选择排序 选择排序示意 选择排序示意 5.5.3 冒泡排序 J列表被分成两个子列表： 已排序 和 未排序 的 ；初始时已排序部分为空。 J在未排序的子列表中，最小的元素通过 冒泡 的方法 选出来并移动到已排序子列表中，这 一过程称为一次扫描。每次扫描，未排序元 素增加 1个，已排序元素减少 1个。 J冒泡时，进行 两两比较 ，如果前者较大，则 交换数据。 J对于 n个数据，需要进行 n-1次扫描 。 冒泡排序 冒泡排序示意 冒泡排序示意 冒泡法排序示意 10,1,2,7,6,8,9,3,4,5 J第 1轮 J第 2轮 J第 3轮 10 1 2 7 6 8 9 3 4 51 102 107 106 108 109 103 104 105 10 1 2 7 6 8 9 3 4 5 106 7 3 94 95 9 1 2 6 7 8 3 4 5 9 103 84 85 8 冒泡法排序示意 10,1,2,7,6,8,9,3,4,5 J继续排序 1 2 6 7 3 4 5 8 9 103 74 75 73 64 65 6 5.6 检索（查找） J查找实现在列表中确定目标所在位置。 查找通常返回具有要查找目标值的 第一 个元素 的 位置 (索引 ) J5.6.1 顺序检索 J5.6.2 二分法检索 J5.6.3 分块检索 * J5.6.4 散列表检索 * 5.6.1 顺序检索（查找） J用于查找无序列表 ，一般用这种方法查 找规模较小的列表。 J顺序查找 从表头开始逐个元素查找 ，当 找到目标元素或查找完整个列表时，查 找过程结束。 顺序查找示意 顺序查找示意 5.6.2 二分法检索（折半查找） J顺序查找很慢 ，尤其当列表中数据非常多时 ，逐个元素比较非常费时。当 列表有序 时， 可采用效率非常高的 折半查找算法 。 J折半查找时， 先测试中间元素 ，可以判断出 目标在列表的前半部分还是后半部分。如果 在前半部分，则不用比较后半部分数据，排 除掉一半数据。 J重复折半过程，直到找到目标或确定目标不 在列表中。 示意 小结 J 数据结构：数据的逻辑结构、数据的