数据结构liuli查找演示

1、第九章 查找第 九 章 查 找 第九章 查找 9.1 概述 9.2 静态表查找表 9.3 动态表查找表 9.4 哈希表第九章 查 找学习要点1 掌握顺序表和有序表的查找方法；了解二分查找过程的描述方法判定树；2 掌握二叉排序树的查找方法；3 掌握哈希表的构造方法和查找方法，理解哈希表与其他结构的表的实质性的差异，了解哈希表解决冲突的方法：开放地址法，链地址法9.1 概 述本章讨论数据结构：查找表何谓查找表 ？ 查找表是由同一类型的数据元素(或记录)构成的集合。 由于“集合中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的操作:1查询某个“特定的数据元素是否在查

2、找表中；2检索某个“特定的数据元素的各种属性；3在查找表中插入一个数据元素；4从查找表中删去某个数据元素。9.1 概 述二 查找的有关概念1 静态查找表、动态查找表仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询结果为“不在查找表中的数据元素插入到查找表中；或者，从查找表中删除其“查询结果为“在查找表中的数据元素。动态查找表查找表可分为两类:9.1 概 述2 记录、关键字记录：由假设干数据项构成的数据元素称为记录是数据元素或记录中某个数据项的值，用以标识识别一个数据元素或记录。关键字: 假设此关键字可以识别唯一的一个记录，那么称之谓“主关键字。 假设此关键字能识别假设干记录

3、，那么称之谓“次关键字。9.1 概 述例：学生管理系统，假设想按姓名查找，可将姓名作为关键字，假设想按学号查找，可将学号作为关键字，学号 姓名 专业 年龄 01王洪 计算机 17 02 孙文 计算机 18 03 谢军 计算机 18 04李辉 计算机 20 05 沈祥福 计算机 25 06 余斌 计算机 19 07巩力 计算机 17 08王辉 计算机 18说明： 记录的任何数据项都可用为关键字； 假设此关键字的值能唯一标识记录，那么称该关键字为主关键字，否那么次关键字；例：学号是主关键字，姓名是次关键字9.1 概 述3 查找 应用中有各种各样的查找，本章讨论的查找操作定义如下：查找：给定某个值，

4、在查找表中查找关键字值等于给定值的记录，假设表中存在这样的记录，那么称查找成功，查找结果为该记录在表中的位置，否那么称为查找不成功，查找结果为“空记录或“空指针nu11。 查找有内查找和外查找之分。假设整个查找过程全部在内存进行，那么称这样的查找为内查找；反之，假设在查找过程中还需要访问外存，那么称之为外查找。我们仅介绍内查找。 要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL= ，其中i为查找第i个元素的概率，且 =1。一般情形下我们认为

5、查找每个元素的概率相等，i为查找第i个元素所用到的比较次数。查找算法的效率用平均查找长度度量设查找不成功的可能性很小，可忽略不计4 平均查找长度平均查找长度ASL = 在查找过程中与给定值比较的关键字个数的数学期望值 PiCiCi为在查找表中查找第i个记录所需的比较次数，Pi为在查找表中查找第i个记录的概率 i=1,2n9.1 概 述三 查找表的组织与查找如何在查找表中查找？取决于如何组织查找表例1： 查找索引号为的图书1 假设图书馆中的图书无序地摆放，那么只能顺序查找；2 假设图书按索引号顺序摆放，那么可先找到TP类图书，再找到TP3 例2 在词典中查找单词 are1 先找到a打头的单词，再

6、在a打头的单词中找2 假设词典中无序排列，那么只能顺序查找；本章介绍： 静态查找表的组织方法与查找 动态查找表的组织方法与查找 哈希表的组织方法与查找 本章介绍： 静态查找表的组织方法与查找 动态查找表的组织方法与查找9.1 概 述约定：假设1) 本章查找是关于主关键字查找；2假设本章涉及的关键字为整型类型；3为使查找的图示简洁，对于查找表中的每一记录，只写出其关键字；关键字类型定义为 typedef int KeyType; 记录类型定义为： stypedef struct KeyType key; /关键字域 /其它域 ElemType;9.1 概 述 R= 01,02,03,04,05,

7、06,07,084) 本章所讨论的查找方法，只要稍加修改即可用于其他类型的查找例学号 姓名 专业 年龄 01 王洪 计算机 17 02 孙文 计算机 18 03 谢军 计算机 18 04 李辉 计算机 20 05 沈祥福 计算机 25 06 余斌 计算机 19 07 巩力 计算机 17 08 王辉 计算机 189.2 静态查找表9.2 静态查找表只提供如下两种查找的查找表，称为静态查找表 1查询某个“特定元素是否在表中； 2检索某个“特定元素的各种属性；对静态查找表介绍两种组织与查找方法 顺序表及查找 有序表及查找抽象数据类型静态查找表的定义为：数据对象D：数据关系R：D是具有相同特性的数据元

8、素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据元素同属一个集合。ADT StaticSearchTable Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();根本操作 P：next ADT StaticSearchTable构造一个含n个数据元素的静态查找表ST。 Create(&ST, n);操作结果：销毁表ST。Destroy(&ST);初始条件：操作结果：静态查找表ST存在；假设 ST 中存在其关键字等于 key 的数据元素，那么函数值为该元素的值或在表中的位置，否那么为“空。 Sea

9、rch(ST, key);初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，那么操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；9.2.1 顺序表的查找一 顺序表及查找线性表及查找 查找表组织：查找表用线性表表示。即将查找表的记录排成一个记录序列。L1=(45,53,12,3,37,24,100,61,90,78) 顺序查找法 1根本思想：从表的最后一个记录或第一个记录开始，依次将记录的关键字

10、与给定值比较，假设相等：查找成功，否那么，继续查找。设查找表用顺序表存储，其类型定义如下：Tyypedef struct ElemType *elem; int length; SSTableint Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。假设找到，那么函数值为 / 该元素在表中的位置，否那么为0。 ST.elem0.key = key; / “哨兵 for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Sea

11、rch_Seq 在上面的程序中，我们首先将关键字的值送到0号存储单元，其目的在于免去查找过程中每一步都要检测整个表是否查找完毕。在此，0号存储单元起到了监视哨的作用。3)说明：1算法简单；2顺序查找法对于查找表的存储结构没有特别的要求，既可用顺序表也可用线性链表存储；假设用顺序表，查找可从前往后扫描，也可从后往前扫描，但假设采用单链表，那么只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。3) 平均查找长度ASLSS=n+1/2ST.elemiST.elemi60ikey=64key=60i64 定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在

12、查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 Ci为找到该记录时，曾和给定值 比较过的关键字的个数分析顺序查找的时间性能。在等概率查找的情况下， 顺序表查找的平均查找长度为：对顺序表而言，Ci = n-i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn 假设查找概率无法事先测定，那么查找过程采取的改进方法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。在不等概率查找的情况下，ASLss 在 PnPn-1P2P1时取极小值 如果再考虑查找成功与不成功的可能性相同，对每个记录的查找概率也相等，那么

13、Pi=1/2n,平均查找长度为： 顺序查找缺点是当n很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。有序表的查找有序表及查找 有序表：假设线性表中的记录按关键字有序，那么称为有序表 查找表组织：查找表用有序表表示。即将查找表的记录排成 按关键字有序的序列。 二分查找法也称为折半查找法1根本思想：将查找范围中间位置的记录关键字与给定值比较： ：继续在前半个表中用二分查找法查找 = ：查找成功，返回记录位置 ：继续在后半个表中中用二分查找法查找有序表的查找 例1 L2=( 3,12,24,37,45,53,61,78,90,100 )，查

14、找 Key=24的记录 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 100lowmid high 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 100lowmid high 24 45 继续在前半个表中用二分查找法查找 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 100Low mid high 24 12 继续在后半个表中用二分查找法查找查找成功int Search_Bin ( SSTable ST, KeyType key ) /在有序表ST中折

15、半查找其关键字等于key的数据元素。假设找到，那么函数值为/该元素在表中的位置，否那么为0。; / 置区间初值 while (low 50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。有序表的查找说明：折半查找法效率比顺序查找高;平均查找长度ASLbs=log2n+1-1要求表中的记录按关键字有序；3) 表中的记录要用顺序结构存储；例 在有1000个记录的查找表查找，顺序查找法平均要比较500次，折半查找法平均要比较9次，可见折半查找法效率比顺序查找高。9.2.2、有序表的查找 Fibonacci 查找 1、Fibonacci 数定

16、义： F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 如：0,1,2,3,5,8,13,21,34,55,89,144,233 2、实现 设结点的总数为 n = Fu - 1，查找键值为 key 的结点 首先比较 key STFu1.key 如果 key STFu1.key ，那么比较 key = STFu1+ Fu3.key 3、注意： 参照以下图，设根结点或子树的根结点同它的左、右儿子的下标之差为Fu3 那么，根结点或子树的根结点的左儿子的同它的儿子的下标之差为Fu4 根结点或子树的根结点的右儿子的同它的儿子的下标之差为Fu5 可以设计类似于二分查找的算法。但先要把 Fu3

17、、 Fu4 、 Fu5计算出来，它们也构成 Fibonacci 数?？9.2、静态查找表 Fibonacci 查找 4、e.g: n = F6 - 1 = 13 - 1 = 12个结点的查找过程 Fu1 = 8 Fu3 = 3 Fu4 = 2 Fu5 = 1 311127105826419STFu1.key差为 Fu3 = 3 差为 Fu5 = 1差为 Fu2 = 2共 Fu1 1817个结点共 Fu2 1514个结点 5、优点：只用 、法，不用除法。平均查找速度更快。Olog2n级。 缺点：最坏情况下比二分查找法差。必须先给出 Fibonacci 数。 插值查找 1、除中点下标的选择和二分查

18、找不同外，其余类似。用于关键字值均匀的情况，平均特性更好。 2、实现 设 mid 为中点的下标。low 为具有最小关键字值结点的下标， high 为具有最大关键字值结点的下标。 mid=(high-low+1)(key-ST.elemlow.key)/ (ST.elemhigh.key - ST.elemlow.key 关键字: A B C D E Pi: Ci: 2 3 1 2 39.2.3 静态查找树表 在不等概率查找的情况下，折半查找不是有序表最好的查找方法例如:此时 ASL=20.2+30.3+10.05+20.3+30.15=假设改变Ci的值 2 1 3 2 3那么 ASL=20.2

19、+10.3+30.05+20.3+30.15= 使 达最小的判定树称为最优二叉树，其中: 定义:为计算方便，令 wi = pi选择二叉树的根结点，使 达最小 介绍一种次优二叉树的构造方法:为便于计算，引入累计权值和 并设 wl-1 = 0 和 swl-1 = 0，那么推导可得023811151823例如:lh211812431018h9608EC21Ah53lhG3013ECGABDF所得次优二叉树如下所示: 查找比较“总次数 = 32+41+25+33 +14+33+25 = 52 查找比较“总次数 = 32+21+35+13 +34+23+35 = 59和折半查找相比较DBACFEG但从上面的查找结果可以看出，该二叉树并不是最优二叉树，棵可以得到比该二叉树更优的二叉树。但研究结果说明，次优查找树和最优查找树的查找性能之差仅