《数据结构2_第10章》由会员分享，可在线阅读，更多相关《数据结构2_第10章（31页珍藏版）》请在金锄头文库上搜索。
1、第十章 查找查找也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元素 关键字是数据元素中某个数据项的值，它可 以标识一个数据元素 查找方法评价 v查找速度 v占用存储空间多少 v算法本身复杂程度 v平均查找长度ASL(Average Search Length)：为确定 记录在表中的位置，需和给定值进行比较的关键字的 个数的期望值叫查找算法的 10.1 顺序查找查找过程：从表的一端开始逐个进行记录的关键 字和给定值的比较 算法描述Ch7_1.ci例 0 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找646
2、4监视哨iiii比较次数=5比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1顺序查找方法的ASL 10.2 折半查找查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 v设表长为n，low、high和mid分别指向待查元素所在 区间的上界、下界和中点,k为给定值 v初始时，令low=1,high=n,mid=(low+high)/2 v让k与mid指向的记录比较 l若k=rmid.key，查找成功 l若krmid.key，则low=mid+1 v重复上述操作，直至lowhig
3、h时，查找失败算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmidCh7_2.c例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6
4、 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92low high mid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9 10 11 5 13 19 21
5、37 56 64 75 80 88 92算法评价 v判定树：描述查找过程的二叉树叫 v有n个结点的判定树的深度为log2n+1 v折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 v折半查找的ASL 10.3 分块查找查找过程：将表分成几块，块内无序，块间有序 ；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 v用数组存放待查记录,每个数据元素至少含有关键字域 v建立索引表，每个索引表结点含有最大关键字域和指 向本块第一个结点的指针 算法描述Ch7_3.c1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13
6、 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表 查38分块查找方法评价ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结构顺序存储结构 线性链表顺序存储结构 顺序存储结构 线性链表查找方法比较顺序查找折半查找分块查找二叉排序树 v定义：二叉排序树或是一棵空树，或是具有下列性质 的二叉树： l若它的左子树不空，则左子树上所有结点的值均小于它的根 结点的值 l若它的右子树不空，则右子树上所有结点的值均大于或等于 它的根结点的值 l它的左、右子树也分别为二叉排序树 v二叉排序树的插入 l插入原则：若二叉排序树为
7、空，则插入结点应为新的根结点 ；否则，继续在其左、右子树上查找，直至某个叶子结点的 左子树或右子树为空为止，则插入结点应为该叶子结点的左 孩子或右孩子 l二叉排序树生成：从空树出发，经过一系列的查找、插入操 作之后，可生成一棵二叉排序树l插入算法例 10， 18， 3， 8， 12， 2， 7， 310101810183101838101838 12 101838 122101838 1227101838 12273Ch5_9.cv二叉排序树的删除 要删除二叉排序树中的p结点，分三种情况： lp为叶子结点，只需修改p双亲f的指针f-lchild=NULL f-rchild=NULL lp只有左
8、子树或右子树 up只有左子树，用p的左孩子代替p (1)(2) up只有右子树，用p的右孩子代替p (3)(4) lp左、右子树均非空 u沿p左子树的根C的右子树分支找到S，S的右子树为空 ，将S的左子树成为S的双亲Q的右子树，用S取代p (5) u若C无右子树，用C取代p (6) 10.4 哈希查找 基本思想：在记录的存储地址和它的关键字之间 建立一个确定的对应关系；这样，不经过比较， 一次存取就能得到所查元素的查找方法 定义 v哈希函数在记录的关键字与记录的存储地址之间 建立的一种对应关系叫 l哈希函数是一种映象，是从关键字空间到存储地址空间的一 种映象 l哈希函数可写成：addr(ai)
9、=H(ki) uai是表中的一个元素 uaddr(ai)是ai的存储地址 uki是ai的关键字关键字 集合存储地址 集合hashv哈希表应用哈希函数，由记录的关键字确定记录 在表中的地址，并将记录放入此地址，这样构成的表 叫 v哈希查找又叫散列查找，利用哈希函数进行查找 的过程叫例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族.1 北京2 上海.以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19从例子可见：
10、 l哈希函数只是一种映象，所以哈希函数的设定很灵活，只要 使任何关键字的哈希函数值都落在表长允许的范围之内即可 l冲突：key1key2，但H(key1)=H(key2)的现象叫 l同义词：具有相同函数值的两个关键字，叫该哈希函数的 l哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽 量减少；同时，冲突发生后，应该有处理冲突的方法 哈希函数的构造方法 v直接定址法 l构造：取关键字或关键字的某个线性函数作哈希地址，即 H(key)=key 或 H(key)=akey+b l特点 u直接定址法所得地址集合与关键字集合大小相等，不会 发生冲突 u实际中能用这种哈希函数的情况很少v数字分析法 l
11、构造：对关键字进行分析，取关键字的若干位或其组合作哈 希地址 l适于关键字位数比哈希地址位数大，且可能出现的关键字事 先知道的情况例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5. 分析： 只取8只取1只取3、4只取2、7、5数字分布近乎随机 所以：取任意两位或两位与另两位的叠加作哈希地址v平方取中法 l构造：取关键字平方后中间几
12、位作哈希地址 l适于不知道全部关键字情况 v折叠法 l构造：将关键字分割成位数相同的几部分，然后取这几部分 的叠加和（舍去进位）做哈希地址 l种类 u移位叠加：将分割后的几部分低位对齐相加 u间界叠加：从一端沿分割界来回折送，然后对齐相加 l适于关键字位数很多，且每一位上数字分布大致均匀情况例 关键字为 ：0442205864，哈希地址位数为45 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088移位叠加5 8 6 4 0 2 2 4 0 46 0 9 2 H(key)=6092间界叠加v除留余数法 l构造：取关键字被某个不大于哈希表表长m的数p除后所得余 数作哈希地址，即H(key)=key MOD p，pm l特点 u简单、常用，
