数据结构第八章查找讲解.ppt

第八章 查找;　查找表;　哈希表;　折半查找;　查找方法 　　将待查关键字值与查找表中各数据元素的关键字值一一 进行比较，直至找到或确定找不到。;查找表：;　存储结构设计;　类型定义;　思路;　算法;　算法分析;　　设查找表中含n个数据元素，若各数据元素被查找的概 率相同，则顺序查找算法在查找成功时的平均查找长度：;　查找方法;　举例;　举例;　存储结构设计;　思路;　算法;　　else if (st[mid].keyskey) low=mid+1;;　算法分析;　算法分析;　查找方法;⑵ 创建索引表，为每个分块创建一个索引项，其中记录该块 最大关键字值及其首地址，各索引项按关键字值有序排列。;　查找方法;　举例;　举例;　算法分析;　B-树;定义;　查找;　举例;　举例;　存储结构设计;　思路;　算法;　算法分析;　插入;　举例;思路;思路细化;思路细化;　//调用前确保T非空;　else if (T-data.keyskey){;　//若T-data.keye.key;　if (!T) {;　//若T非空，则调用改造后的查找算法，在T中查找e：;　　if (!s) exit(OVERFLOW);;　删除;　举例——待删结点为叶子结点;36;15;　举例——待删结点既有左子树，又有右子树——方法一;　举例——待删结点既有左子树，又有右子树——方法一;　举例——待删结点既有左子树，又有右子树——方法二;　举例——待删结点既有左子树，又有右子树——方法二;　算法;　　　if (T-rchild==NULL){//待删结点为叶子结点;　　　if (T-rchild==NULL ) {//待删结点只有左子树;　　　　return DeleteBST(p,p-data.key);　//删除p;　构造;　举例;　构造 　　二叉查找树的构造过程是从空树开始，不断向其中插入 结点的过程。;　平衡;思路：;思路细化1：;举例：;思路细化2：;思路细化2：;思路细化2：;0;RR型失衡;12;0;30;1;0;0;0;⒈置平衡二叉树T为空树，此时T显然平衡；;根结点平衡因子改为0，T高度不变；;(a)若T的左子树根的平衡因子为1，则新结点必插在T的左子;(b)若T的左子树根的平衡因子为-1，则新结点必插在T的左子;;1、二叉查找树;1、二叉查找树;(a)若T的右子树根的平衡因子为1，则新结点必插在T的右子;;(b)若T的右子树根的平衡因子为-1，则新结点必插在T的右子;定义;4. 所有的分支结点含如下格式信息： 　　（A0，K1，A1，… ，Ai-1 ，Ki，Ai ，… ，Kn，An）;^;　查找方法;T;T;　插入;T;T;　删除;　举例——待删关键字位于最底层分支结点中，且该结点 　　　　　中关键字个数多于ém/2ù -1个;　举例——待删关键字位于最底层分支结点中，且该结 　　　　　点中只有ém/2ù -1个关键字;　举例——待删关键字位于最底层分支结点中，且该结 　　　　　点中只有ém/2ù -1个关键字;　若待删关键字位于上层分支结点中，则先用其左侧子树 　中的最大关键字值或右侧子树中的最小关键字值替换该待 　删关键字，再删除用以替换的关键字即可。;　　在查找的过程中，时间主要用于关键字值间的比较。　　可不可以不经过关键字值间的比较就找到我要的记录呢？;　　若能在待查记录的关键字值和它的存储位置之间建立一个确定的对应关系则查找时不必再进行关键字值间的比较！;　举例;　　关键字值和存储地址要一一对应的！ 　　你每次都有那么好的运气，能构造出理想的哈希函数吗？;电话号码;定义 　　根据设定的哈希函数及处理冲突的方法将查找表中各数 据元素存储在一段有限的连续空间中，即得哈希表。;　基本要求;　方法;　举例;　方法;　　　　　设要在长为100的哈希地址空间中保存80个数据 元素，部分关键字值如下，试用数字分析法设计哈希函数。;　方法;　举例 　　设某计算机语言中标识符定义为一个字母或一个字母 加一个数字，又知字母、数字的机内码（以八进制数表示） 如下： 　　Ａ：０１　Ｂ：０２　Ｃ：０３　…　Ｚ：３２ 　　０：６０　１：６１　２：６２　…　９：７１ 　　现以标识符的机内码为关键字，构造哈希表，试用平方 取中法设计哈希函数。;标识符 Ａ Ｉ Ｊ Ｉ０ Ｐ１ Ｐ２ Ｑ１ Ｑ２ Ｑ３;　移位叠加 　　将各部分按最低位对齐，然后相加；;　举例;　举例;　方法;　举例;　　处理冲突是指对于一个待插入哈希表的数据元素，若按 给定的哈希函数求得的哈希地址已被占用，则按一定规则求 下一哈希地址，如此重复，直至找到一个可用的地址以保存 该元素。; 若取di=1,2,3,…,m-1，则称线性探测再散列；;　举例 　　设有一组关键字：(67,84,18,26,34