数据结构与算法_查找

《数据结构与算法_查找》由会员分享，可在线阅读，更多相关《数据结构与算法_查找（57页珍藏版）》请在金锄头文库上搜索。

1、现实生活中，有许多查找的例子： 如到某学校找某个同学， 邮递员按信件收信人地址确定收信人的位置； 在字典中查询某个单词； 从海量信息中找到自己需要的信息等等。要查询这些信息，涉及到两个主要问题： 一是数据如何组织查找表， 二是在查找表上如何查找查找方法 。,第六章 查找,查找表是由同类型的数据元素(或记录)构成的集合。,基本概念,对查找表基本操作,1）查询某个数据元素是否在查找表中； 2）检索某个数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。,仅作查询和检索操作的查找表。,静态查找表,有时在查询之后，将“查询”结果“不在查找表中”的数据元素插入到查找表

2、中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。,动态查找表,查找表分类,关键字：是数据元素中某个数据项的值，用以标识一个数据元素。,查找过程中，往往是依据数据元素的某个数据项进行查找，这个数据项通常是数据的关键字。,若关键字能标识唯一的一个数据元素，则称谓主关键字。,若关键字能标识若干个数据元素，则称谓次关键字。,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。,查找,若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个数据元素的信息，或指示该数据元素在查找表中的位置；否则称“查找不成功”。,查找方法评价 查找速度 占用存储空间多少 算法本身复杂

3、程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的,6.1 顺序表的查找,6.1.1 顺序查找 基本思想从表中指定位置（一般为最后一个，第0个位置设为岗哨）的记录开始，沿某个方向将记录的关键字与给定值相比较，若某个记录的关键字和给定值相等，则查找成功；反之，若找完整个顺序表，都没有与给定关键字值相等的记录，则此顺序表中没有满足查找条件的记录，查找失败。,算法描述,Ch7_1.c,64,监视哨,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i

4、个元素： n+1-i 查找失败： n+1,6.1.1 顺序查找 3. 性能分析 空间复杂度：需要一个辅助存储单元空间R0 ，因此，顺序查找的空间复杂度为O(1) 时间复杂度：查找算法的基本运算是给定值与顺序表中记录关键字值的比较。 最好情况：第一次比较就成功找到所需数据，这时，时间复杂度为O(1)。 最坏情况：所查找的记录不在顺序表中，这时，需要和整个顺序表的记录进行比较，比较的次数为n，时间复杂度为O(n)。 平均情况：需要和顺序表中大约一半的记录进行比较，即比较次数为n/2，因而，时间复杂度为O(n)。,6.1.1 顺序查找4.顺序表上顺序查找的平均查找长度平均查找长度（ASL）：给定值与

5、关键字比较次数的期望值。对于具有n个记录的顺序表，查找成功时的平均查找长度为：Pi查找第i个记录的概率 Ci找到第i个记录数据需要比较的次数 ， 对于顺序表，Ci = n-i+1,6.1.1 顺序查找 等概率情况不等概率 ASL 在PnPn-1P2P1时取极小值 若查找概率无法事先测定，可采取改进办法： 在每次查找之后，将查找到的记录直接移至表尾。,优点：算法简单，适用面广 缺点：平均查找长度较大。,6.1.2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给

6、定值 初始时，令low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k=rmid.key，查找成功 若krmid.key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败,算法描述,Ch7_2.c,6.1.2 折半查找 性能分析,判定树,1,2,2,3,3,3,3,4,4,4,4,3,9,1,4,2,5,7,8,10,11,6,算法评价 判定树：描述查找过程的二叉树叫 有n个结点的判定树的深度为log2n+1 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 折半查找的ASL,当n值较大时（n50)，有次近似结果）,4.折半查

7、找特点折半查找的查找效率高； 平均查找性能和最坏性能相当接近； 折半查找要求查找表为有序表； 并且，折半查找只适用于顺序存储结构。,见第三章,6.2二叉排序树查找 平衡二叉树查找,例3 给定关键字序列11，78，10，1，3，2，4，21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树)，并求出每一种查找的成功平均查找长度。,顺序查找的顺序表（一维数组）如图3所示，,从图3 可以得到顺序查找的成功平均查找长度为： ASL=(1+2+3+4+5+6+7+8)

8、/8=4.5；,二分查找的判定树（中序序列为从小到大排列的有序序列）如图4所示，,从图4可以得到二分查找的成功平均查找长度为： ASL=(1+2*2+3*4+4)/8=2.625；,二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图 5(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图5(b)所示。,从图5(a)可以得到二叉排序树查找的成功平均查找长度为： ASL=(1+2*2+3*2+4+5*2)/8=3.125； 从图5(b)可以得到平衡二叉树的成功平均查找长度为： ASL=(1+2*2+3*3+4*2)/8=2.75；,6.2 索引表查找,6.2.1 索引表

9、的基本概念 索引 书的目录就是一种索引，使用索引能够快速地定位查找范围。计算机中对数据的存储和处理也可以采用索引。当数据量太大，以至内存装不下，可以对数据建立“索引”， 根据索引将所需要的数据块读入内存，这样只需对读入的部 分数据进行查询，提高查找效率。,2.索引表的构建 分块：按查找表中数据按关键字分成若干块：R1, R2, , RL，使得“分块有序”，即第Rk 块中所有关键字 Rk+1块中所有关键字，k=1, 2, , L-1， 2) 建立索引项：对每一个块建立一个索引项， 每个索引项包含两项内容： 关键字项：记载该块中最大关键字值； 指针项： 记载该块第一个记录在表中位置。 3) 所有索

10、引项组成索引表。,3.索引表的查找索引表的查找分两步进行： 索引表上查找：由索引表确定记录所在区间 查找表上查找：在查找表的某个区间内进行查找由于索引表有序，对索引表上的查找可用顺序查找、二分查找或树组织查找等方法。,查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针 算法描述,Ch7_3.c,最大关键字,起始地址,分块查找方法评价,6.3 哈希表的查找,问题引入前面介绍的查找方法，都有一个共同特点：都是通过一系列比

11、较来确定关键字为key的记录在查找表中的地址。这些方法的平均查找长度都不为零。差别仅在于：关键字和给定值进行比较的顺序不同。,我们总希望 ASL = 0，比较次数为0。,如果记录在表中的存放位置和其关键字之间存在着某种确定的关系，将会怎样？我们有何计可施?,6.3.1 基本概念,若将学号为xx000 xx999的学生记录分别存放在查找表下标为000 999中 ，,例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。,则查找过程为：取给定学号的后三位，不需要经过比较，便可直接从查找表中找到给定学生的记录。,哈希查找 基本思想

12、：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫 哈希查找又叫散列查找，利用哈希函数进行查找的过程叫,以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2,以地区别作

13、关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19,从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫 同义词：具有相同函数值的两个关键字，叫该哈希函数的 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 哈希函数的构造方法 直接哈希函数法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=

14、akey+b,例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为: H（key）=key +（-1948） 这样就可以方便地存储和查找1948年后任一年的记录。,特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少,数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析： 只取8只取1只取3、4只取2、7、5数字分布近乎随机 所以：取任意两位或两位与另

15、两位的叠加作哈希地址,6.3.2 哈希函数 3. 平方取中法 取关键字平方后的中间几位作为哈希地址，即哈希函数为：H（key）=“key2的中间几位”， 其中，所取的位数由哈希表的大小确定,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别”和“贡献均衡”。 即：关键字的各位都在平方值的中间几位有所贡献，Hash值中应该有各位影子。适于不知道全部关键字情况,平方取中法思想,折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键

16、字位数很多，且每一位上数字分布大致均匀情况,例 关键字为 ：0442205864，哈希地址位数为4,除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 若p含有质因子pf，则所有含有质因子pf的关键字的哈希地址均为pf的倍数。如当p=21=(3*7)时，下列含因子7的关键字对21取模的哈希地址均为7的倍数。一般情况下，应取p为不大于m 的质数或是不包含小于20的质因子的合数。例如：key = 12, 39, 18, 24, 33, 21 时， 若取 p=9, 则使所有含质因子3的关键字均映射到地址0, 3, 6 上，从而增加了“冲突”的可能性。,随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况 选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率,