第8章 查找概要.ppt

应用：文件中单词词频统计 [例] 给定一个英文文本文件，统计文件中所有单词出现的频率，并输出词频最大的前10%的单词及其词频。 假设单词字符定义为大小写字母、数字和下划线，其它字符均认为是单词分隔符，不予考虑。 【分析】关键：对新读入的单词在已有单词表中查找，如果已经存在，则将该单词的词频加1，如果不存在，则插入该单词并记词频为1。 如何设计该单词表的数据结构才可以进行快速地查找和插入？ 散列表 (4) 删除64后，为保持各分支等长（平衡），将删除64后的剩余信息(在此为空指针)及78合并入右兄弟，如图8.10(e)所示。也可将删除64后的剩余信息及47与左兄弟合并。 结论：被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于[m/2]-1，设该结点有右兄弟且所在结点中剩余的关键字和指针，加上双亲中的Ki一起，合并到Ai所指兄弟结点中。 (5) 删除27时，首先将剩余信息(在此为空指针)与父结点中的18并入左兄弟，并释放空结点，结果如图8.10(f)所示。再将父结点中的剩余信息与祖父结点中的35并入47左端，释放空结点后的结果如图8.10(g)所示。至此，祖父结点仍需要合并，但由于待合并结点的父指针为NULL，故停止合并，直接将根指针bt置为指针p2的值，释放空结点后的结果如图8.10(h)所示。 图8.10 在B-树最下层结点中删除关键字 图8.11 在B-树非最下层删除关键字 2） 在非最下层结点中删除一个关键字 四．B+树 B+树是应文件系统所需而出的一种B-树的变型。一棵m阶的B+树和一棵m阶的B-树的差异在于： ① 有n棵子树的结点中含有n个关键字。 ② 所有的叶子结点中包含了全部关键字信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序连接。 ③ 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。 B+树可以进行两种查找运算。 注：若从根开始查找时，若非终端结点等于该关键字，并不停止，继续到叶子。 已知的几种查找方法： 顺序查找 O(N) 二分查找（静态查找） O (log 2 N) 二叉有哪些信誉好的足球投注网站树 O(h) 平衡二叉树 O (log 2 N) 还有其他方法吗? 8.3 哈希表 [例] 在登录QQ的时候，QQ服务器是如何核对你的身份？面对庞大的用户群,如何快速找到用户信息? 【分析】看看是否可以用二分法查找。 ? 十亿（109 ≈ 230）有效用户，用二分查找30次。 ? 十亿（109 ≈ 230） × 1K ≈ 1024G，1T连续空间。 ? 按有效QQ号大小有序存储：在连续存储空间中，插入和删除一个新QQ号码将需要移动大量数据。 （不合适） 【问题】如何快速有哪些信誉好的足球投注网站到需要的关键词？如果关键词不方便比较怎么办？ 查找的本质: 已知对象找位置。 有序安排对象：全序、半序 直接“算出”对象位置：散列 ? 散列查找法的两项基本工作： 计算位置：构造散列函数确定关键词存储位置； 解决冲突：应用某种策略解决多个关键词位置相同的问题 ? 时间复杂度几乎是常量：O(1)，即查找时间与问题规模无关！ 8.3.1什么是哈希表 哈希表又称散列表。 “散列（Hashing）”的基本思想是： （1）以关键字key为自变量，通过一个确定的函数 h（散列函数），计算出对应的函数值h(key)，作为数据对象的存储地址。 （2）可能不同的关键字会映射到同一个散列地址上， 即h(keyi) = h(keyj)（当keyi ≠keyj），称为“冲突(Collision)”。 ----需要某种冲突解决策略 实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。 一个记录： 全国总共有30个地区的各民族人口统计表。用C[31]来存放，C[i]为编号为i地区的人口情况，如北京编号为1，而key=1，只需输出C[1]记录即可。此时，f(key)=key. 三种方式： ① 取关键字中第一个字母在字母表中的序号作为哈希函数。 如BEIJING B等于02，而C[2]放北京 f(BEIJING)= 2 ② 取关键字中第一个和最后一个字母在字母表中的序号之和， 若这个值比30（表长）大，则减去30。 f(TIANJIN)= 4 ③ 求每个汉字的第一个拼音字母的ASCII码之和的八进制形式，然后将这个八进制数看成十进制再除30取余，若为0加上30。