《数据结构 Java语言版 教学课件 ppt 王学军 第九章》由会员分享，可在线阅读，更多相关《数据结构 Java语言版 教学课件 ppt 王学军 第九章（84页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Java语言版）,人民邮电出版社,第9章 查找,主编:王学军,【内容简介】 本章通过实例引入查找概念，重点介绍查找的相关概述，包括查找、关键字、查找方法等基本概念，以及各种查找算法的思想、程序实现。查找的实例应用。 【知识要点】 1.查找相关概述； 2.顺序查找法、二分查找法的算法原理及程序实现； 3.二叉排序树查找法的应用及平衡二叉排序树的实现过程； 4.哈希查找的概述； 5.哈希函数构造方式及冲突解决办法。,【教学提示】 本章共设10个学时，理论6学时，实验4学时，介绍查找的概念及相关概述、各种查找方式及算法实现；重点突出顺序查找法、二分查找法等查找方法的执行过程和算法实现，加强
2、查找综合应用的理解。本章采用理论和实践结合的方式进行学习，结合查找的工程实例组织教学，其中二叉排序树的平衡问题和用链表法解决哈希冲突部分内容作为选学内容。,第一节 实例引入,1.实例引入 【学习任务】通过实例的引入，了解查找的基本过程。 【例9.1】办公软件中查找操作 如图9.1所示为Office办公软件中的Word文字处理软件，在文字处理中，经常遇到查找某个（或者某一批）信息，并对其处理的情况。图9.1中所示就是在该文章中对“数学教育”进行查找，并将其修改成“数学高职素质教育”，在该操作中就涉及到了在文章中对所要求的内容进行查找，并且对查找到的信息进行相应的修改。,图9.1 word应用软件
3、中查找实例示意图,【例9.2】学生成绩管理系统中的查找。 如表9.1所示为某学校2004级计算机专业学生某学期成绩表，在该学期综合测评中要查找学生的各种相关信息，如查找程序设计课程最高分（98分）的学生，或查找总分最低（295分）学生；有些条件还可以同时使用，如查找数据结构和大学英语都在前三名的学生是否存在等问题，都是具有代表性的查找问题。 表9.1 某校2004级计算机专业学生成绩表,在生活中经常用到查找，如查找门牌号码，图书馆书架上查找图书等，计算机中查找的操作应用非常普遍，例如学生信息系统、工资管理系统等管理系统中都需要实现查找等操作。,第二节 基本概念与术语,.基本概念与术语 【学习任
4、务】结合实例分析，理解查找、关键字、查找方法等相关概念。 2.1查找的概念 查找是指在给定的由同一数据类型构成的整体范围内（如一篇文章、一个数据库等等），寻找用户需要数据的过程。若满足条件的数据存在，则称查找成功，否则查找失败。查找的过程要依据用于识别某元素的字段，该字段可惟一识别数据元素，称其为查找关键字。,说明： （1）查找的操作是在一定范围之内的，若查找成功，将对其进行相应操作，在查找范围之外的数据将不被操作。 （2）查找的数据可以是单个元素（如表9.1的学生成绩表中某单科成绩或总成绩），也可以是有多个数据元素构成的一个整体（如表9.1中查找某个学生的相关信息），将这样的数据称为查找的关
5、键字（关键字的概念在计算机的操作中经常见到，在第10章排序中也要用到这个概念）。,（3）查找可以按照多个关键字进行，如例9.2所示中可按“数据结构”成绩在90分以上，同时“总分”成绩在330分以上的学生，此时查找包括两个关键字（“数据结构”和“总分”），其中“数据结构”为第一关键字，而“总分”为第二关键字，也称为次关键字，这样的关键字若有多个，应依次排列。,2.2 查找方法 根据定义，查找过程是在同类型数据构成的整体集合中进行查找操作，若只对数据进行查找（结果为查找成功或查找失败），并不改变数据的结构，若要对这些数据进行修改，则将改变数据的结构。 查找的方法主要有：顺序查找法、二分查找法（折半
6、查找法）、二叉排序树法、哈希查找法等等。,第三节 顺序查找法,3. 顺序查找法 【学习任务】理解顺序查找法的算法思路及程序实现，重点掌握顺序查找法的时间复杂度和表长的关系。 .1问题引入 【例9.3】设有如下数字构成的序列表A=55，25，6，95，76，12，124，32，9，73，查找给定的某个数字X是否存在，并给出相应提示。,3.2 算法描述 这是一个典型的查找问题，可将序列表A用数组表示，用数值X和系列A中的每个元素进行比较，若相等，则表示X在序列表A中存在，则查找成功，否则失败。如图9.2所示。,图9.2 顺序查找示意图,3.3 程序实现 public class shunxucha
7、zhao public void c(int a,int x) int i=0; while(i=a.length) System.out.println(“查找失败！“); else System.out.println(“查找成功！“);, public static void main(String args) int b=12,25,6,95,76,55,124,32,9,73; shunxuchazhao c1=new shunxuchazhao(); c1.c(b,25); 结果为： 查找成功！,4算法分析 顺序查找实际上以关键字与序列中每个元素依次比较而确定结果的查找方法，其算法
8、复杂度与序列表的长度有直接关系，若查找成功，则比较次数小于或者等于n，若查找不成功，则查找的次数永远为n 。查找算法的时间复杂度，其为O(n)。 顺序查找算法在n比较小，或者所查找的元素比较靠前时，算法较优。,第四节 折半查找法,4 .折半查找法 【学习任务】理解折半查找的算法思路及程序实现，重点理解折半查找法的前提条件及其含义，在算法分析方面重点理解与二叉排序树异同点。 .1问题引入 【例9.4】若将【例9.3】中的数据排成一个有序序列，即A= 6，9，12，25，32，55，73，76，95，124，查找给定的某个数字X是否存在，并给出相应提示。,.2算法描述 折半查找的思想：首先将查找序
9、列分成两半，确定查找数可能在哪一半，在确定的部分中继续折半，直到找到该元素，显示查找成功，并确定元素位置；若判断该元素不存在，则返回查找失败。 折半查找每次将查找序列分成两部分，又称为二分法，其前提是查找序列必须是有序的。 对于【例9.4】中的有序序列A，预查找X=95和X=13是否存在，其算法描述如图9.3所示。,（1）将序列A以数组方式存储，其图如9.3（a）所示，用i和j分别表示数组的第一个元素和最后一个元素的下标，取中间元素的下标m=(i+j)/2（，为取整符号）。,图9.3(a) 折半查找第一步分析,（2）调整i或j的位置，使m为新中间元素的下标，使原序列折半，继续查找相应元素，如图
10、9.3(b)所示。,图9.3(b) 折半查找第一步分析,（3）继续调整i或j的位置，使m为新中间元素的下标，使原序列继续折半，如图9.3(c)所示。,图9.3(c) 折半查找第一步分析,（4）X=95已经查找成功；对于X=13，继续调整i的位置，使m为新中间元素的下标，使原序列继续折半，如图9.3(d)所示。,图9.3(d) 折半查找第一步分析,图9.3 有序序列的折半查找示意图,3.3程序实现 public class Zhebanchazhao public int Binary_Search(int a,int k) int low ,high,mid ,flag=0; low=1;hi
11、gh=a.length; while(low=high) mid=(low+high)/2; if(kamid),low=mid+1; else flag=mid; System.out.println(flag); break; return flag; public static void main(String args),int b=6,9,12,25,32,55,73,76,95,124; zhebanchazhao c1=new zhebanchazhao(); c1.Binary_Search(b,25); 结果为：3,4.4算法分析 折半查找的算法分析比较复杂，对于有序序列来说
12、，每次减少一半，算法比顺序查找要优一些，其时间复杂度为O(log2n)。,第五节 二叉排序树法,5 .二叉排序树法 【学习任务】结合第7章的相关内容掌握利用二叉排序树法进行查找的过程，了解二叉排序平衡树的思想及构造过程，了解平衡二叉树在算法实现上优于普通二叉排序树的思想。 5.1问题引入 对于折半查找可将全部序列按照某关键字分成两部分，一部分数值小于等于关键字数值，另一部分数值大于等于关键字数值；在每个部分又可选出新的关键字，将其继续分解，直至最后结束。,该思想和第7章所介绍的二叉排序树的思想是一致的，因此可通过建立二叉排序树进行查找（具体内容请参阅相关章节）。 5.2算法描述 【例9.5】对
13、于【例9.3】中给定的序列表A=55，25，6，95，76，12，124，32，9，73，建立二叉排序树并完成查找过程。 （1）建立二叉排序树 根据二叉排序树性质，将第一个元素作为根结点，将其余元素和根结点元素比较，若比它小，则进入左子树，否则进入右子树，依次类推,完成二叉排序树的建立。 对于例9.5所示的序列，其建立二叉排序树的过程如图9.4所示。,（2）查找过程 在按照上面过程所建立的二叉树中，预查找X=95和X=13这两个数是否在这个序列中，即判断这两个数是否在如图9.4所示的二叉排序树中出现，其过程如下： （i）对于X=95的情况 将X=95和根结点比较（9555），查找在右子树进行；
14、 将X=95和右子树根结点比较（95=95），查找成功。,ii）对于X=13的情况 将X=13和根结点比较（136），查找在右子树进行； 将X=13和右子树根结点比较（1312），查找在右子树进行； 而此时，结点12已经没有右子树，因此，查找失败。,（3）算法分析 对于利用二叉排序树法进行查找，其时间复杂度受二叉树的深度影响，假设给定序列为有序情况，则构造的二叉排序树则只有左子树或者只有右子树，其算法退化为顺序查找；而当给定序列二叉排序树的左右子树分布比较均匀，每次查找可减少一半左右的结点数，则可提高查找效率。 因此，建立均匀的二叉排序树是提高此算法的重要因素。,3平衡二叉排序树 （1）定义
15、平衡二叉排序树（又称平衡二叉树），其定义过程和普通二叉树的一样，是一个递归过程。 平衡二叉树中每个结点为根结点的左子树和右子树深度之差的绝对值不超过1。如图9.5所示。 说明： 平衡二叉树可以是一棵空树； 平衡二叉树某结点的左、右子树深度之差的绝对值不超过1。,平衡二叉树定义过程是一个递归过程，即以每个结点为根的子树都要满足子树深度之差的绝对值不超过1的条件，只要有一个不满足该条件，就不能成为平衡二叉树。 【例9.6】在【例9.5】建立二叉排序树的过程中，前6步构成的二叉排序树如图9.5所示，图中结点左侧数字表示以其为根结点的左、右子树深度之差的绝对值，其平衡情况具体如下：,图(a)是一棵平衡
16、二叉排序树，其左、右子树深度之差的绝对值为0； 图(b)是一棵平衡二叉排序树，其左、右子树深度之差的绝对值为1； 图(c)是一棵非平衡二叉排序树，根结点的左、右子树深度之差的绝对值为2（超过1）； 图(d)是一棵平衡二叉排序树，其每个结点为根结点的左、右子树深度之差的绝对值都没有超过1； 图(e)是一棵平衡二叉排序树，其每个结点为根结点的左、右子树深度之差的绝对值都没有超过1； 图(f)是一棵非平衡二叉排序树，以25为根结点的的左、右子树深度之差的绝对值为2（超过1）。,图9.5 例9.5建立二叉排序树的前6步示意图,（2）二叉排序树的平衡 当二叉树排序树不能构成平衡时，将降低查找效率，因此，二叉排序树的平衡是一个关键问题，其平衡操作主要分为两个方面，具体为： （i）顺时针旋转型 当二叉树在以某结点为根的子树上，由于插入结点进
