《数据结构教程》第八章查找.ppt

数据结构,第一章 绪论 第二章 线性表 第三章 稀疏矩阵和广义表 第四章 栈和队列 第五章 树和二叉树 第六章 二叉树的应用 第七章 图 第八章 查找 第九章 排序,第八章 查找,8.1 对查找的操作： 1）查询(检索)某个“特定的”数 据元素是否在查找表中及各 种属性； 2）在查找表中插入一个数据元素； 3）从查找表中删去某个数据元素。,1.顺序查找,2.二分查找,3.索引顺序,8.2 静态查找表,顺序搜索的平均搜索长度,设搜索第 i 个元素的概率为 pi，搜索到第 i 个元素所需比较次数为 ci，则搜索成功的平均搜索长度:,在顺序搜索情形，ci = i +1, i = 0, 1, , n-1，因此,在等概率情形，pi = 1/n, i = 0, 1, , n-1。,1.顺序查找,顺序查找算法,Struc elemtypeeneytype data; keytype key; Int seqserch(elemtype a, int n, keytype k) an.key=k; for(int i=0;i+) if(ai.key=k) break; If(in) return I Else return -1; ,2.二分查找 条件：表已排序 思想：第一步把表一分为二； 判定查找的元素落在哪部分； 依据上述步骤重复直到最后找 到（或对半结束查找不成 功）,算法下一页,Int binserch(elemtype a, int low, int hiht ,keytype k) if(low=high) int mid =(low+high)/2; if(k=amid.key) return mid; else if(kamid.key) return binserch(a,low,mid-1,k); else return binserch(a,mid,high-1,k) return -1; ,下一页图示,搜索成功的例子 搜索失败的例子,下一页判定树,搜索成功的情形 搜索不成功的情形,从有序表构造出的二叉搜索树(判定树),若设 n = 2h-1，2h = n+1, h = log2(n+1)。 第0层结点有1个，搜索第0层结点要比较1次；第1层结点有2个，搜索第1层结点要比较2次；，,顺序查找表的查找算法简单， 但 平均查找长度较大，特别不适用于 表长较大的查找表。,总结： 有序查找表,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,5.3 索引顺序表的查找过程：,1）由索引确定记录所在区间；,2）在顺序表的某个区间内进行查找。,索引可以根据查找表的特点来构造。,索引顺序查找的过程也是一个 “缩小区间”的查找过程。,一、索引顺序查找的数据结构： Struct indexitem indexkeytype index;int start ;int length;,主表,0 1 2 3,Index start lengh,索引表,二、分块查找：在索引表为稀疏索引,0 1 2,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,Index Start lengh,索引表,主表,注：同一块中的数据没有排序,8.4 散 列 查 找,动态查找表,一、散列的概念 散列：通过对表中的每个元素关健字K为自变量的 H()计算出一值作为一连续存储空间的位置,并将 该元素存储到这个单元中.此函数称散列函数或 哈希函数.()称散列地址或哈希地址,上述的存储 空间称散列表或哈希表.,例:A=(18,75,60,43,54,90,46) h(k)=k%m :m为散列表的长度=13,0 1 2 3 4 5 6 7 8 9 10 11 12,54,90,46,同义词冲突:70,下一页冲突,引起冲突的三个原因: 一、装填因子:=n/m 二、与散函数有关 三、与解决的方法有关,1. 直接定址法,3. 数字分析法,5. 折叠法,4. 平方取中法,2. 除留余数法,二、对数字的关键字可有下列构造方法：,若是非数字关键字，则需先对其进行数字化处理。,1. 直接定址法:h(k)=k+c,3. 数字分析法:(92326875,92343634, 92774638,92381262,92394220),5. 折叠法：k=68242324, 散列分三 段682，423，240，叠加和：1345， 其散列地址为：345,4. 平方取中法:322 取中三位1024,2. 除留余数法:h(k)=k%m,三、处理冲突的方法,“处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个哈希地址。,1. 开放定址法,1 2 3 4 5 6 7 8,26,27,非同义词冲突,线性探查法,2. 链接法,0 1 2 3 4 5 6 7 8 9 10 11 12,B(18,75,60,43,54,90,46,31,58,73,15,34) H(k)=k%13,8.5 B - 树查找,1定义,2查找过程,3插入操作,4查找性能的分析,动态查找表,在 m 阶的B-树上，每个非终端结点 可能含有： n 个关键字 Ki（1 in） nm 或 n 个指向记录的指针 Di（1in） n+1 个指向子树的指针 Ai（0in）,多叉树的特性,a,mt,b,c,d,e,f,g,h,非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn ； Ai-1 所指子树上所有关键字均小于Ki； Ai 所指子树上所有关键字均大于Ki ；,查找树的特性,平衡树的特性,树中所有叶子结点均不带信息，且在树中的同一层次上； 根结点或