09第9章 查找

null第9章 查找 第9章 查找 基本概念 静态查找表 动态查找表 哈希表基本概念 基本概念 查找表：由同一类型的数据元素（或记录）构成的集合。 对查找表进行的操作有以下四种： 查询某个特定的数据元素是否在查找表中。 检索某个特定的数据元素的各种属性。 在查找表中插入一个数据元素。 从查找表中删除某个数据元素。 静态查找表：对查找表只作前两种操作 。 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。 null关键字： 标志 禁止坐卧标志下载饮用水保护区标志下载桥隧标志图下载上坡路安全标志下载地理标志专用标志下载 数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素 。 查找：根据给定的某个值，在查找表中确定是否存在一个数据元素其关键字等于给定值的记录或数据元素 。 平均查找长度ASL (Average Search Length)为： 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值其中: n 为表长 Pi 为查找表中第i个记录的概率 Ci为找到该记录时，曾和给定比较过的关键字的个数。静态查找表 静态查找表 顺序表的查找 有序表的查找 索引顺序表的查找顺序表的查找 顺序表的查找 基本思想：从表的一端开始，顺序扫描线性表，依次用待查找的关键字值与线性表里各结点的关键字值逐个比较，若在表中找到了某个记录的关键字与待查找的关键字值相等，表明查找成功；如果找遍所有结点也没有找到与待查找的关键字值相等，则表明查找失败 。null 顺序查找的算法： int Search_seq(SSTable ST[ ], int n, int key) { int i=n; ST[0].key=key; while(ST[i].key!=key) i- -; /*从表尾往前查*/ return i; }监视哨使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。 找到：返回元素在线性表中的存储位置； 未找到：返回0。null根据上述算法可知： 查找成功时的平均查找次数为： ASL=(1+2+3+4+……+n)/n=(n+1)/2 查找不成功时的比较次数为： n+1 则顺序查找的平均查找长度为： ASL==((n+1)/2+n+1)/2=(n+1)3/4 顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。 缺点：平均查找长度较大。因此，当n较大时，不宜采用顺序查找。等概率查找的情况下折半查找 折半查找 基本思想： 首先用要查找的关键字值与中间位置结点的关键字值相比较；比较结果如果相等，则查找完成；若不相等，再根据要查找的关键字值与该中间结点关键码值的大小来确定下一步查找在哪个子表中进行：如果待查关键字大于中间结点的关键字值，则应查找中间结点以后的子表，否则，查找中间结点以前的子表。nullST.elemST.length例如: key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2nullint Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if （EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Binnull折半查找判定树 ：折半查找过程可用二叉树来形象的描述，把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树，由此得到的二叉树，称为描述折半查找的判定树。 实例： null 先看一个具体的情况，假设：n=11 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 折半查找的平均查找长度6391425781011判定树12233334444null优点:平均查找长度小 缺点:要求表中元素按关键字排序。 二分查找适用于那种一经建立就很少改动、而又经常需要查找的有序表，且限于线性存储结构。 对于查找少而又需经常改动的线性表，可采用链表作存储结构。 折半查找（二分法查找）分块查找 分块查找 基本思想：把线性表分成若干块，在每一块中结点的存放是任意的，块与块之间必须排序；建立一个索引表，存放每块中最大的关键字值；查找时首先用要查找的关键字值在索引表中查找，确定应在哪一块中，然后再到相应的块中顺序查找。 该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。 null索引表块中的最大关键字块内第一个记录位置的指针分块查找（索引顺序查找）存储结构null分块查找步骤：查索引表，确定要找的记录在哪一块。 在相应的块中查找。例：要找关键字为22的记录。 由索引的第一项可知，要找的记录要么在第二块中，要么不存在。并获取第二块中第一个记录的位置。分块查找的效率介于对分查找和顺序查找之间。索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度null一、二叉排序树（二叉查找树）二、二叉平衡树(AVL树）三、B - 树四、B+树五、数字查找树（键树）动态查找表null一、二叉排序树 （二叉查找树）1．定义2．查找算法3．插入算法4．删除算法5．查找性能的分析null（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值；1．定义： 二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉 排序树。（2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值；null503080209010854035252388例如:是二叉排序树。66不null 通常，取二叉链表作为 二叉排序树的存储结构typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;TElemType data;2．二叉排序树的查找算法：2．二叉排序树的查找算法：1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。否则，若二叉排序树为空，则查找不成功；null50308020908540358832例如:二叉排序树查找关键字== 50 ,505035 ,503040355090 ,50809095 ,null算法描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) { // 在根指针 T 所指二叉排序树中递归地查找其 // 关键字等于 key 的数据元素，若查找成功， // 则返回指针 p 指向该数据元素的结点，并返回 // 函数值为 TRUE; } // SearchBST … … … … 否则表明查找不成功，返回 // 指针 p 指向查找路径上访问的最后一个结点， // 并返回函数值为FALSE, 指针 f 指向当前访问 // 的结点的双亲，其初始调用值为NULLnullif (!T) else if ( EQ(key, T->data.key) ) else if ( LT(key, T->data.key) ) else{ p = f; return FALSE; } // 查找不成功{ p = T; return TRUE; } // 查找成功SearchBST (T->lchild, key, T, p ); // 在左子树中继续查找SearchBST (T->rchild, key, T, p ); // 在右子树中继续查找null30201040352523fT设 key = 48fTfT22pfTfTTTTfffp3．二叉排序树的插入算法根据动态查找表的定义，“插入”操作在查找不成功时才进行；3．二叉排序树的插入算法若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。nullStatus Insert BST(BiTree &T, ElemType e ) { // 当二叉排序树中不存在关键字等于 e.key 的 // 数据元素时，插入元素值为 e 的结点，并返 // 回 TRUE; 否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p )) { } else return FALSE; } // Insert BST … …nulls = (BiTree) malloc (sizeof (BiTNode)); // 为新结点分配空间 s->data = e; s->lchild = s->rchild = NULL; if ( !p ) T = s; // 插入 s 为新的根结点else if ( LT(e.key, p->data.key) ) p->lchild = s; // 插入 *s 为 *p 的左孩子 else p->rchild = s; // 插入 *s 为 *p 的右孩子return TRUE; // 插入成功null（1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。4．二叉排序树的删除算法可分三种情况讨论： 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。null50308020908540358832（1）被删除的结点是叶子结点例如:被删关键字 = 2088其双亲结点中相应指针域的值改为“空”null50308020908540358832（2）被删除的结点只有左子树 或者只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。被删关键字 = 4080null50308020908540358832（3）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字 = 50null5．查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。null由关键字序列 3，1，2，5，4构造而得的二叉排序树，由关键字序列 1，2，3，4，5构造而得的二叉排序树，例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2二 平衡二叉树(AVL树）二 平衡二叉树(AVL树）概念：或者是一棵空树，或者是具有下列性质的二叉树： 它的左子树和右子树都是平衡二叉树。 左子树和右子树的深度之差的绝对值不超过1。 实例：不平衡的二叉树 二叉平衡树是二叉查找树的另一种形式null实例：构造关键字的序列为（1，2，3，9，5）的平衡二叉树 。构造二叉平衡（查找）树的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 是： 在插入过程中，采用平衡旋转技术。null 平衡处理的方法 ： LL型调整： RR型调整： null LR型调整： RL型调整 ： null 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析： 在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和 log(n) 相当。null三 B - 树1．定义2．查找过程3．插入操作4．删除操作5．查找性能的分析null1．B-树的定义B-树是一种 平衡 的 多路 查找 树：null 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字 Ki（1≤ i≤n） nkeynum; i=Search(p, K); // 在p->key[1..keynum]中查找 i ， p->key[i]<=Kkey[i+1] if (i>0 && p->key[i]==K) found=TRUE; else { q=p; p=p->ptr[i]; } // q 指示 p 的双亲 } if (found) return (p,i,1); // 查找成功 else return (q,i,0); // 查找不成功null在查找不成功之后，需进行插入。 显然，关键字插入的位置必定在最下 层的非叶结点，有下列几种情况：3．插入1）插入后，该结点的关键字个数n 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 主要需要解决两方面的问题： 构造好的哈希函数，使冲突的现象尽可能少 Hash码均匀性好 Hash码的计算要尽量简单 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 有效的解决冲突的方法null二、构造哈希函数的方法 对数字的关键字可有下列构造方法： 若是非数字关键字，则需先对其进行 数字化处理。1. 直接定址法3. 平方取中法5. 除留余数法4. 折叠法6. 随机数法2. 数字分析法null哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a  key + b1. 直接定址法此法仅适合于： 地址集合的大小 = = 关键字集合的大小null此方法仅适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度。2. 数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。null 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。3. 平方取中法 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。null 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。4. 折叠法 此方法适合于: 关键字的数字位数特别多。null5. 除留余数法 设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子null 给定一组关键字为：12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3例如：为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。null6.随机数法设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。null 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。null三、处理冲突的方法 “处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个哈希地址。1. 开放定址法2. 链地址法3. 溢出Hash表null 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤ s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, …, s1. 开放定址法对增量 di 有三种取法：对增量 di 有三种取法：1) 线性探测再散列 di = c i 最简单的情况 c=1 2) 平方探测再散列 di = 12, -12, 22, -22, …, 3) 随机探测再散列 di 是一组伪随机数列 或者 di=i×H2(key) (又称双散列函数探测)null即：产生的 Hi 均不相同，且所产生的 Hi 值能覆盖哈希表中所有地址。 则要求： 注意：增量 di 应具有“完备性”※ 随机探测时的 m 和 di 没有公因子。※ 平方探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, … 等）；null例如: 关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 }设定哈希函数 H(key) = key MOD 11 ( 表长=11 )1901231455681901231468若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突118236551182361 1 2 1 3 6 2 5 1null H2(key) 是另设定的一个哈希函数，它的函数值应和 m 互为素数。若 m 为素数，则 H2(key) 可以是 1 至 m-1 之间的任意数； 若 m 为 2 的幂次，则 H2(key) 应是 1 至 m-1 之间的任意奇数。例如，当 m=11时， 可设 H2(key)=(3 key) MOD 10+11901231455681182362 1 1 1 2 1 2 1 3null将所有哈希地址相同的记录 都链接在同一链表中。 2. 链地址法0 1 2 3 4 5 6140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:同前例的关键字，哈希函数为 H(key)=key MOD 7null3. 溢出Hash表 溢出Hash表包括Hash表和溢出表两部分。 在Hash表的填入过程中，将冲突的元素顺序填入溢出表，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。 溢出表是一个顺序查找表。例 将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21) 依次填入长度为n＝12的溢出Hash表中。 设Hash码为i＝INT(k/3)＋1。null 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为： 四、哈希表的查找 对于给定值 K， 计算哈希地址 i = H(K)若 r[i] = NULL 则查找不成功若 r[i].key = K 则查找成功否则 “求下一地址 Hi” ，直至 r[Hi] = NULL (查找不成功) 或 r[Hi].key = K (查找成功) 为止。nullint hashsize[] = { 997, ... }; typedef struct { ElemType *elem; int count; // 当前数据元素个数 int sizeindex; // hashsize[sizeindex]为当前容量 } HashTable; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1//--- 开放定址哈希表的存储结构 ---nullStatus SearchHash (HashTable H, KeyType K, int &p, int &c) { // 在开放定址哈希表H中查找关键码为K的记录 } // SearchHashp = Hash(K); // 求得哈希地址while ( H.elem[p].key != NULLKEY && !EQ(K, H.elem[p].key)） collision(p, ++c); // 求得下一探查地址 pif (EQ(K, H.elem[p].key)) return SUCCESS; // 查找成功，返回待查数据元素位置 pelse return UNSUCCESS; // 查找不成功nullStatus InsertHash (HashTable &H, Elemtype e){ } // InsertHashc = 0;if ( HashSearch ( H, e.key, p, c ) == SUCCESS ) return DUPLICATE; // 表中已有与 e 有相同关键字的元素else H.elem[p] = e; ++H.count; return OK; // 查找不成功时，返回 p为插入位置else RecreateHashTable(H); // 重建哈希表 if ( c < hashsize[H.sizeindex]/2 ) { // 冲突次数 c 未达到上限，（阀值 c 可调） } null1) 选用的哈希函数； 2) 选用的处理冲突的方法； 3) 哈希表饱和的程度，装载因子 α=n/m 值的大小（n—记录数，m—表的长度）决定哈希表查找的ASL的因素：哈希表查找的分析: 从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。null 一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。 因此，哈希表的ASL是处理冲突方法和装载因子的函数。例如：前述例子线性探测处理冲突时， ASL =双散列探测处理冲突时，ASL =链地址法处理冲突时， ASL =22/914/913/9null 哈希表的平均查找长度是  的函数，而不是 n 的函数。 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子  ，使得平均查找长度限定在某个范围内。—— 这是哈希表所特有的特点。查找方法的比较 查找方法的比较 顺序查找的效率很低，对于待查的结构没有任何要求，算法非常简单，既适用于顺序存储结构，又适用于链接存储结构。 折半查找法的平均查找长度小，查找速度快，但要求表中的记录是有序的，且只能用于顺序存储结构。 分块查找的平均查找长度介于顺序查找和折半查找之间。由于结构是分块的，所以，当表中记录有变化时，只要调整相应的块，可用于顺序存储结构，也可用于链接存储结构。 哈希法是直接计算地址的方法，在查找过程中不需要进行比较，其查找时间与表中记录的个数无关。 null(n) (1) (n) (1) (logn)综合讨论的几种查找表的特性：查找 插入 删除无序顺序表 无序线性链表 有序顺序表 有序线性链表 AVL树 (n) (n) (logn) (n) (logn)(1) (1) (n) (1) (logn)null基本内容：讨论查找表的各种实现方法：顺序表、有序表、树表、哈希表； 了解其查找平均长度。 学习要点： 熟练掌握基本查找方法 熟练掌握二叉排序树的构造及查找方法 理解B-树的特点及建树过程 熟练掌握哈希表的特点及构造方法，理解哈希表技术与其他查找技术的区别。