数据结构6(4月28日).ppt

查找 根据给定的关键字值 在一组数据元素中确定一个其关键字值等于给定值的数据元素的过程 若存在这样的数据元素 则称查找成功 若不存在这样的数据元素 则称查找失败 关键字 指数据元素中可以标识该数据元素的一组数据项 例如学生记录中的学号 公民记录中的身份证号码等 查找表 指一组待查数据元素的集合 它具有一定存储结构 如顺序表结构 链式结构 树形结构等 2 6查找 1 查找的方法查找某个数据元素依赖于查找表中数据元素的组织方式 按照数据元素的组织方式决定采用某种查找方法 反之 为了提高查找方法的效率 又要求数据元素采用某些特殊的组织方式 因此 在研究各种查找方法时 必须弄清各种查找方法所适用的组织方式 2 查找算法的评价衡量一个算法的标准主要有两个 时间复杂度和空间复杂度 而在查找算法中 基本运算是给定值与关键字值的比较 即算法的主要时间是花费在 比较 上的 所以 用平均查找长度作为评价查找算法好坏的依据 对于含有n个数据元素的查找表 查找成功的平均查找长度为 ASL 其中 Pi为查找第i个数据元素的概率 Ci为查找到第i个数据元素时 需进行的比较次数 查找方法分类 线性查找法顺序查找法对半查找法分块查找法 基于树的查找法二叉排序树B树 计算式查找法 哈希法 顺序存储的查找方法 链式存储的查找方法 散列存储的查找方法 2 6 1顺序查找法基本思想是 从数组的第一个元素开始 与查找的关键字逐个比对 直到找到关键字所在的位置或遇到数组的结尾为止 若找到 则返回关键字在数组中的位置 否则返回 1 因为C 的数组下标不可能为 1 publicintsearch intkeyValue inti 0 while i if return i elsereturn 1 假设每个元素等概率查找 则平均查找次数为 n 1 2 i length data i keyValue i length 2 6 2对半查找法以顺序方式存放的有序表的查找可采用对半查找 将被查关键字k与线性表中间位置mid上的数据元素的关键字进行比较 假设表按由小到大顺序排列 1 若k a mid 则查找成功 过程结束 2 若k a mid 则取表的后半部分作为新表再去查找 3 若k a mid 则取表的前半部分作为新表再进行查找 这个过程一直进行到查找成功或子表的长度为0为止 对半查找是基于关键字比较的最优方法 publicintbinSearch intkeyValue intlow high mid low 0 high length 1 while mid low high 2 if data mid keyValue elseif data mid keyValue else return 1 low high return mid low mid 1 high mid 1 对半查找成功时比较次数最多为log2n 1 分块查找 索引顺序查找 分块有序 表特点 1 表中数据分块 2 块中数据不必有序 3 块间有序 分块有序 表的结构有两部分 1 顺序存储结构的线性表 2 索引表 由每块的最大元素组成 分块查找过程 1 用对半查找法查找索引表 确定待查项x所在的块 2 在相应的块中用顺序查找法查找待查项x 2 6 3二叉排序树及查找若线性表中的结点经常插入和删除 就应设计成把链表和二分法结合的查找方法 二叉排序树是将线形表中的元素组织成二叉树的形式 以达到与对半查找相同的查找效率 1 二叉排序树定义 1 若它的左子树不空 则左子树上所有的关键字均小于它的根结点的关键字 2 若它的右子树不空 则右子树上所有的关键字均大于或等于它的根结点的关键字 3 它的左 右子树也是二叉排序树 如果按中序遍历二叉排序树 可得到一个递增排列的序列 中序遍历序列 1 2 3 4 5 6 7 8 9 二叉排序树示例 TreeNode类publicclassTreeNode publicchardata publicTreeNodeleftChild publicTreeNoderightChild publicTreeNode charc data c leftChild null rightChild null BiTree类publicclassBiTree privateTreeNoderoot publicBiTree root null publicvoidinsBTree chark 二叉排序树创建 publicTreeNodebanSearch chark 二叉排序查找方法 二叉排序树代码表示 2 查找算法及实现在给定的二叉排序树t中查找给定待查关键字k 从根结点出发 1 如果树t为空 那么查找失败 算法结束 否则 转 2 2 如果t data等于k 则查找成功 算法结束 否则转 3 3 如果k t data 则t t leftchild 到左子树查找 转 1 否则t t rightchild 到右子树查找 转 1 publicTreeNodebanSearch chark TreeNodep root while if p data k else return p p null p data k p p leftChild p p rightChild 假设一组数据元素的关键字序列如下 45 24 53 12 37 93 30 40 80 分析查找元素40 如何创建二叉排序树 3 创建二叉排序树通过在初始为空的树中不断插入数k来建立二叉排序树 步骤 1 若二叉排序树为空 则插入结点应为根结点 2 若二叉排序树非空 根据关键字比较的结果确定是在左子树还是在右子树中继续查找插入位置 直至某个结点的左子树或右子树空为止 则插入结点应为该结点的左孩子或右孩子 假定由整数序列 10 6 19 22 8 2 生成一棵二叉排序树 可以采用逐个元素插入的方法实现 1 首先将10作为根结点 2 然后插入6时 通过比较知6 10 所以将6作为10的左孩子插入 3 同理将19作为10的右孩子插入 4 整数22通过和10 19比较后 作为19的右孩子插入 5 依次插入剩余的其他元素 publicvoidinsBTree chark 将k插入到二叉排序树 TreeNodep q q newTreeNode k if root null 树为空 该节点即根节点 root q return p root 从根开始开始找位置while p leftChild q p p leftChild p leftChild q p rightChild null 4 二叉排序树的构造如果给定一个数据元素的集合 则数据元素的读入顺序不同 其构造出的二叉排序树的形态也不同 例序列 53 61 12 37 90 100 3 78 45 61 37 90 45 100 78 12 3 53 3 12 37 45 53 61 78 90 100 构造的二叉排序树分别为图1 图2和图3 53 12 61 3 37 90 45 78 100 61 37 90 12 45 3 53 78 100 图1 图2 3 12 37 45 53 61 78 90 100 图3 5 二叉排序树的平衡化处理二叉排序树的查找效率与构成的二叉排序树的形态有关 为了提高查找效率 还需在构造二叉排序树的过程中进行 平衡化 处理 使之成为平衡的二叉排序树 这样 平衡二叉排序树的查找就与折半查找一样高效 平衡二叉树的递归定义如下 平衡二叉树或是一棵空树 或是一棵具有下列性质的二叉树 1 左子树与右子树的深度之差的绝对值不超过1 2 左 右子树也是平衡二叉树 2 7排序排序是将一个数据元素的无序序列 按其关键字的大小重新排列 变成一个有序序列 分为内部排序和外部排序 内部排序 排序操作都在内存中进行 以比较次数衡量算法效率 外部排序 排序操作还需访问外存 以访问外存的次数衡量算法效率排序算法的稳定性 对于关键字相同的元素 排序中不改变其相对次序 称为稳定的排序算法 反之称为不稳定的排序算法 按算法效率分简单的排序和先进的排序 前者包括选择法排序 冒泡法排序 插入法排序 后者则包括快速排序法和归并排序 2 7 1选择排序 第1步 在N个元素的排序表中选择最小元素第2步 将最小元素与表头元素交换第3步 N N 1第4步 若N 1 则执行第1步 否则结束排序初始状态4521341952603424第1趟 i 1 19 21344552603424第2趟 i 2 1921 344552603424第3趟 i 3 192124 4552603434第4趟 i 4 19212434 52604534第5趟 i 5 1921243434 604552第6趟 i 6 192124343445 6052第7趟 i 7 19212434344552 60 可见 选择排序是一种不稳定的排序 具体算法描述如下 publicvoidselectSort inti j k for i 0 i length 1 i for j i 1 j n j if k j 记录最小元素的位置if intx data i data i data k data k x k i data j data k k i 2 6 2交换排序1 冒泡排序将待排序文件中的记录两两比较 若为逆序 则进行交换 按此方法将文件从头到尾处理一遍称作一趟起泡 一趟起泡的结果是将关键字最大的记录交换到了表尾 对余下n 1个记录 重复此过程 直至文件排好序为止 若某一趟起泡过程中没有任何交换发生 则表明此时文件已经排好序了 不必再继续重复起泡过程 初始状态 4521341952603424 第一趟21341945523424 60 第二趟211934453424 5260 第三趟1921343424 455260 第四趟19213424 34455260 第五趟192124 3434455260 第六趟1921243434455260 可见 冒泡算法是稳定的 publicvoidbubSort boolneedChange true intj length 1 while needChange false 先假定不需要交换for inti 0 idata i 1 inttemp data i data i data i 1 data i 1 temp j needChange的作用是当前内循环无交换时 即终止程序的运算 needChange j 0 needChange true 直接插入排序 基本思想 将n个待排序元素看成为一个有序表和一个无序表 开始有序表只有一个元素 无序表中则有n 1个元素 排序过程中每次从无序表中取出第一个元素 将其关键字与有序表的关键字比较 将其插入到适当位置 使之成为新的有序表 插入步骤 1 将无序表中的第一个元素存入辅助变量temp中 2 将temp和有序表中从最后一个元素开始进行比较 若小于有序表中的元素 则有序表中该元素后移一位 同时继续和前一元素比较 否则插入到该元素的后面 初始状态 45 21341952603424第一趟 2145 341952603424第二趟 213445 1952603424第三趟 19213445 52603424第四趟 1921344552 603424第五趟 192134455260 3424第六趟 19213434455260 24第七趟 1921243434455260 有序文件1921243434455260 插入排序是稳定的排序 publicvoidinsertSort inti j temp for i 1 i 0 data j 1 data j data j 1 temp temp data i 2 6 4快速排序基本思想 在待排序的n个元素中任取一个元素R 以该元素排序码k为准 将所有剩下的n 1个元素分割为两个子序列 第一个子序列中每个元素的排序码均小于或等于k 第二个子序列中每个元素的排序码均大于或等于k 然后将k所对应的元素放在两个子序列之间 完成第一趟排序 使得待排序序列成为R分别对子序列1和子序列2重复上述划分 直到每个子序列中只有一个元素时为止 线性表分割步骤 1 设置两个指示器i和j 其初始状态分别指向区间内第一个记录和最后一个记录 2 将第一个记录移向辅助变量x中 3 从j所指位置起向前搜索第一个小于x的记录 找到后 将a j 移至a i 的位置 4 从i 所指向的位置向后搜索第一个关键字大于x的记录 找到后 将a i 移至a j 的位置 5 重复3 4两步 直至i j 最后将x送至a i 中去 至此一趟排序完成 文件划分为两个子序列 重复以上步骤直到每个子序列中只有一个元素时为止 初始状态4521341952603424ij一次交换2421341952603424i j二次交换2421341952603452i j三次交换2421341934603452i j 2421341934 45 6052 ij a 一趟排序初始状态 4521341952603424 第一趟 2421341934 45 6052 第二趟 1921 24 3434 第三趟1921第四趟3434第五趟5260有序文件1921243434455260 b 全部快速排序 privatevoidqkOne intstart intend outintmid intx i j i start j end x data i 将第一个值保存在x中while while i x 自右向左扫描 if i j i while i j i j j data i data j i data i x 一趟分割的代码 快速排序是不稳定的排序 但是内排序中速度最快的 publicvoidqkSort intstart 0 end length 1 mid ArrayStackas newArrayStack 100 建立一个堆栈as push start as push end while as isEmpty end as pop 与压栈的次序相反 弹出位置start as pop while start end qkone start end outmid as push mid 1 将分割后的第二个序列压栈as push end end mid 1 调节位置准备对第一个序列再分割 位置从start到mid 1 快速排序 2 7 3归并排序采用二路归并技术 即每次将数组a中两个相邻的有序序列归并为一个有序序列 排序步骤 1 假设待排序文件含有n个记录 则可看成是n个有序的子序列 每个子序列的长度为1 2 两两归并 得到 n 2 个长度为2或1的有序子序列 3 再两两归并 直到得到一个长度为n的有序文件为止 初始状态 45 21 34 19 52 60 34 24 第一趟 2145 1934 5260 2434 第二趟 19213445 24345260 第三趟1921243434455260二路归并排序过程示例 二路归并排序是