《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第8章 查找-1》由会员分享，可在线阅读，更多相关《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第8章 查找-1（36页珍藏版）》请在金锄头文库上搜索。
1、1,第8章 查找,第1讲,第6章 树与二叉树,2,第8章 查找,查找是对数据进行处理时常用操作，是各种数据结构中最常用的算法之一。不论在线性表中还是在树或图中都会涉及查找问题。 例如：在一个电话通信表中，查找某个员工的电话；在计算机的某个操作系统环境下，查找某个文件；在互联网上，通过搜索引擎查找所需要的某类信息。这些都是典型的查找问题。 查找算法的优劣对系统运行效率的影响极大。本章讨论有关查找的若干算法，并通过对它们的分析来比较各种查找方法的优劣。,3,第8章 查找,本章重点介绍基于内存中的数据集合的典型查找方法。同时简单介绍涉及外部存储的查找方法，如：B树、B+树等。 主要内容： 查找的基本
2、概念 静态查找 动态查找 哈希表及其查找,4,本章分为（34）讲,第1讲 8.1 查找的基本概念 8.2 静态查找表,第3讲 8.4 哈希表及其查找,第2讲 8.4 动态查找表,供教师参考,5,8.1 查找的基本概念,查找（Search）也称检索，就是确定一个已给的数据是否出现在某个数据元素集合中。 查找表（Search Table）是由一组类型相同的数据元素（记录）构成的集合。由于“集合”中的数据元素间存在着松散的关系。因此，查找表是一种灵便的数据结构。,口述： 例如，学生高考成绩表存放着全体考生的记录，每个记录看作一个数据元素，包含有考生的准考证号、姓名以及语文、数学等各科成绩和总成绩。当
3、按照准考证号或姓名进行成绩查询时，就是数据查找问题。将高考成绩表视为查找表。,6,查找表、记录和关键字,表通常是指文件，文件是由记录组成的集合。本章讨论的是用于查找的内存中若干记录的集合，称查找表。 每个记录（Record）表示数据元素，由若干个数据项组成。每个数据项，称为域（Field）或字段（Segment）。是数据表示的基本单位。 每个记录（数据元素）中总存在一个或一组数据项，它们的值能够标识（识别）一个数据元素，这个数据项称为关键字（Key）。,7,主关键字和次关键字,能够唯一地标识一个记录的关键字叫主关键字（Primary Key）。 不能唯一确定一个记录的关键字，称为次关键字（Se
4、condary Key）或属性域。 例如：高考成绩表准考证号为主关键字。语文、数学成绩是次关键字或属性域。,8,查找（Searching）一般提法是： 设查找表有n个具有相同类型的记录r0，r1，r2，rn1，每个记录由一个称为主关键字的数据项和若干相关数据项的值组成，对给定值K，查找是否存在关键字值等于K的某个记录。 查找的结果有两种： 1. 查找成功，可给出整个记录的信息，或该记录的位置； 2. 查找失败，可给出查找不成功的信息，或一个“空”记录或“空”指针。,9,查找方法的分类,按查找表的结构可将查找表分为静态查找表（Static Search Table）和动态查找表（Dynamic
5、Search Table）两类。 静态查找表是指在查找过程中其结构始终不发生变化的查找表；动态查找表是指其结构在查找过程中可能发生插入/删除变化的查找表。 静态查找表主要采用顺序存储结构。而动态查找表一般都采用链表存储结。 后面的哈希表及查找，有时采用顺序结构，有时采用链表结构。,10,分析算法的主要因素：,常以算法的效率和存储开销来衡量查找算法的优劣。效率和存储开销常常是相互制约很难兼顾，效率只是相对的。 衡量查找算法效率的主要因素是，已知的K值与记录中关键字的比较。 通常把对关键字的最多比较次数和平均比较次数作为两个基本的技术指标。 对查找表进行查找，对关键字比较的最多次数叫做最大查找长度
6、（Maximum Search Length，MSL）。,11,平均查找长度：,对查找表进行查找，对关键字的平均比较次数叫做平均查找长度（Average Search Length，ASL）。 对n个对象记录进行查找时，平均查找长度：,Ci 为查找第i个记录所需的比较次数， Pi 为查找第i个记录的查找概率（可能性）。 简单情况下认为是等概率的，Pi均等于1/n。,12,8.2 静态查找表,静态查找表是指在查找过程中其结构始终不发生变化的查找表。静态查找表主要采用顺序存储结构。 数据元素（记录）结构如下： const int MAXSIZE = 100; /表的最大长度 typedef int
7、 KeyType; /关键字的类型 struct datanode /记录结构 KeyType key; /关键字域 char ch; /其他属性域 ;,13,顺序表类：,class Sqtable private: datanode rMAXSIZE ; /查找表 int n ; /数据元素个数，表长 public: Sqtable (); void creat(); void output(); void sq_search (KeyType K ); /顺序查找 void binary_search (KeyType K ); /折半查找 / ;,14,8.2.1 顺序表的查找,已知表r
8、、关键数据K、表长n，算法8.1 void Sqtable:sq_search (KeyType K) rn.key=K; /设置监视哨 int i = 0; while ( ri.key != K) i+; if(in) cout“n 查找成功，记录下标为：“iendl; else cout“n 查找失败!n“endl; ,15,算法分析：,（1）在最坏的情况下，顺序查找需要比较n次，即MSL=n。 （2）假定各记录的查找机会均等，即 Pi =1/n。由于查找第i个记录需要比较i 次，即Ci=i，于是有： 这样，最大查找长度和平均查找长度的数量级，即算法的时间复杂度为O(n)。,16,假设有
9、n=8个记录的查找表：,8个关键字为：81 31 104 43 47 5 73 12 分析： 如果K=12需要比较8次，成功。 如果K=60也需要比较8次，不成功。 因此可以说最大比较长度为MSL=n=8。 查找成功的平均比较长度：ASL=(1+2+8)/8=4.5。 常将ASL看成查找算法的时间复杂度。,17,实际的数据查询系统中，记录被查找的频率或机会并不相同。 在高考成绩记录中，单科成绩优秀者、总成绩排在前10名者常被查询，而单科成绩和总成绩一般的人则很少问津，若把常查找的记录尽量放前，则可降低ASL。如，根据对10个记录做100次查询得到的统计资料，其中一个被查找37次，两个各被查找2
10、5次，三个各被查找3次，其余各被查找1次。 按查找次数递减的顺序进行排列（见下页表），则对这些记录进行顺序查找时，其平均查找长度为2.41。这比一般平均查找长度5.5效率提高了1.28倍。,可播放讲解, 可只讲,但不播放文字.,18,10个记录按查找次数递减顺序排列情况 记录 查找次数 统计概率 记录 查找次数 统计概率 r1 37 0.37 r6 3 0.03 r2 25 0.25 r7 1 0.01 r3 25 0.25 r8 1 0.01 r4 3 0.03 r9 1 0.01 r5 3 0.03 r10 1 0.01,可播放讲解, 可只讲,但不播放文字.,19,8.2.2 有序表的折半
11、查找,对于以数组方式存储的记录，如果数组中各个记录的次序是按其关键字值的大小顺序排列的，则称为有序表。 对顺序分配的有序表可以采用折半查找（Binary Search），又称二分查找。 折半查找不像顺序查找那样，从第1个记录开始逐个顺序搜索，而是每次把要找的给定值K，与在中间位置的记录的关键字值进行比较。,20,有序表的折半查找,设数组r有n个记录。每个记录的关键字值按升序排列为： r0.key，r1.key，r2.key， rn-1.key 当ij时，有ri.keyrj.key。 开始，中间位置记录的序号为m= 将给定值K与rm.key比较，有3种可能的结果： （1）K=rm.key。查找成
12、功，结束查找。 （2）Krm.key。则对右半部分继续用折半查找进行搜索。,21,这样，在查找过程中搜索区间不断对分并成指数地缩小，因而查找速度明显地快于顺序查找。当最后只剩下一个记录，而且此记录不是要找的记录，则宣告查找失败。 假有一组记录的关键字值（ri.key）为： 5 12 31 43 47 73 81 104 用low,m,high 分别指向第一个、中间一个和最后一个记录的下标。 low=0，high=7，m=3。,22,例如： K=73,假设要查找K=73的记录，则折半查找过程如下： 5 12 31 43 47 73 81 104 low m high 因K43(rm.key)，下
13、一步查找区间必定在右半部： 5 12 31 43 47 73 81 104 low m high 此时，low=4，high=7，m=5。由于K=73，查找成功，所找到的记录序号为5。,23,再如：k=15,假若查找K=15的记录，则折半查找过程如下： 5 12 31 43 47 73 81 104 low m high 因low=0、high=7、m=3，有K43。下一步查找区间必定在下标为3的记录的左半部分: 5 12 31 43 47 73 81 104 low m high,24,5 12 31 43 47 73 81 104 low m high 因low=0、high=2、m=1，
14、K12，下一步查找区间必定转到下标为1的记录的右半部分: 5 12 31 43 47 73 81 104 low m high 此时low、high、m均指31，K31，查找失败。,25,折半查找算法-算法8.2,void Sqtable:Sqtable binary_search (KeyType K ) int m,low,high,find; low = 0; high = n-1; find = 0; do m = (low + high)/2; if(K=rm.key) cout“n查找成功，记录下标：“mendl; find = 1; else if(Krm.key) high =
15、m1; else low =m+1; while( find = 0 ,26,折半查找分析-折半查找的二叉判定树,可用二叉树来说明，分析前例中的8个记录： 数据：5 12 31 43 47 73 81 104 下标：0 1 2 3 4 5 6 7,树根结点是第一次中指针m值(下标)，左子树的根值是左半表的m值，。该树是二叉排序树，由m取值组成。,27,查找成功的情况：,在判定树中可直 观看出查找关键字的 比较次数。 若 K=43，记录下标是3，比较1次找到。 又如 K=81，记录下标6在第三层，比较3次找到。 再如K=104，记录下标7在第四层，比较4次找到。 查找成功时的平均查找长度： ASL = (1*1+2*2+4*3+1*4)/8 = 21/8=2.625,28,查找不成功的情况：,若K=1，它比0号记录的关键字5还要小，该记录不存在，从树中可以看出比较3次未找到。 又如K=8，它比0号记录的关键字5大，但它比1号记录的
