1、中国科大C+程序设计实习 数据结构课程本章内容9.1 查找的基本概念查找的基本概念9.2 静态查找表静态查找表9.3 动态查找表动态查找表9.4 哈希表哈希表中国科大数据结构9-3 9.1 查找的基本概念中国科大数据结构9-4 9.1 查找的基本概念中国科大数据结构9-5 9.1 查找的基本概念中国科大数据结构9-6 9.2 静态查找表中国科大数据结构9-7 9.2 静态查找表中国科大数据结构9-8 9.2 静态查找表监视哨兵监视哨兵i=11i=7,找到找到i=8i=9i=10比较次数比较次数=5比较次数分析：比较次数分析：查找第查找第n n个元素：个元素：1 1次次查找第查找第n-1n-1个
2、元素：个元素：2 2次次.查找第查找第1 1个元素：个元素：n n次次查找第查找第i i个元素：个元素：n+1-in+1-i次次查找失败查找失败：n+1n+1次次 0 1 2 3 4 5 6 7 8 9 10 1162513192137566275808892中国科大数据结构9-9 9.2 静态查找表中国科大数据结构9-10 9.2 静态查找表中国科大数据结构9-11 9.2 静态查找表中国科大数据结构9-12 9.2 静态查找表1 2 3 4 5 6 7 8 9 10 11513192137566275808892low=1mid=6high=11第一步：第一步：low=1,high=11,
3、mid=6 STmid=ST6=5662,则改变则改变high；第三步：第三步：high=mid-1=8,mid=7 high=8mid=7STmid=ST7=62=62,找到！找到！62中国科大数据结构9-13 9.2 静态查找表1 2 3 4 5 6 7 8 9 10 11513192137566275808892high=6low=7找找61u 当下界当下界lowlow大于上界大于上界highhigh时，说明有序时，说明有序 表中没有关键字等于表中没有关键字等于K K的元素，查找失败的元素，查找失败中国科大数据结构9-14 9.2 静态查找表n判定树上每个结点需要的查找次数刚好为该结点所
4、在的层数；判定树上每个结点需要的查找次数刚好为该结点所在的层数；n查找成功时查找次数不会超过判定树的深度查找成功时查找次数不会超过判定树的深度nn个结点的判定树的深度为个结点的判定树的深度为 log2n +1n比较次数最多不超过比较次数最多不超过 log2n +1n折半查找的算法复杂度为折半查找的算法复杂度为 log2n +13941756102118判定树判定树中国科大数据结构9-15 9.2 静态查找表中国科大数据结构9-16 9.2 静态查找表中国科大数据结构9-17 9.2 静态查找表 1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755
5、929主表主表索引表索引表中国科大数据结构9-18 9.2 静态查找表1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表找找62中国科大数据结构9-19 9.2 静态查找表中国科大数据结构9-20 9.3 动态查找表p动态查找表动态查找表 如果应用问题涉及的数据量很大，而且数据经常发生变化，如如果应用问题涉及的数据量很大，而且数据经常发生变化，如图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对这类表除了提供前面的介绍的查找外，还要提供动态查找功能：这类
6、表除了提供前面的介绍的查找外，还要提供动态查找功能：1.查找某个查找某个“特定特定”元素是否在表中，若不在，将该元素插入；元素是否在表中，若不在，将该元素插入；2.查找某个查找某个“特定特定”元素是否在表中，若在，从表中删除；元素是否在表中，若在，从表中删除；p如何组织动态查找表？如何组织动态查找表？用静态查找方法不能满足要求了。本节介绍几种方法。用静态查找方法不能满足要求了。本节介绍几种方法。中国科大数据结构9-21 9.3 动态查找表21二叉排序树二叉排序树非二叉排序树非二叉排序树56645923788198021137560566459237881980211375中国科大数据结构9-2
7、2 9.3 动态查找表566459237881980211375例例1：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于3737找到找到例例2：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于88找到找到例例3：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于94无此数无此数中国科大数据结构9-23 9.3 动态查找表56645923788198021137594中国科大数据结构9-24 9.3 动态查找表566492888075中国科大数据结构9-25 9.3 动态查找表566459237881980211375中国科大数据结
8、构9-26 9.3 动态查找表中国科大数据结构9-27 9.3 动态查找表566459237881980211375中国科大数据结构9-28 9.3 动态查找表566453719211392888075中国科大数据结构9-29 9.3 动态查找表566459237888019211375中国科大数据结构9-30 9.3 动态查找表808892647521191356375中国科大数据结构9-31 9.3 动态查找表808892647521191356375中国科大数据结构9-32 9.3 动态查找表阿德尔森一维尔斯和阿德尔森一维尔斯和兰迪斯兰迪斯566459237881980211375605
9、65641913753780928821AVLAVL树树非非AVLAVL树树中国科大数据结构9-33 9.3 动态查找表56564191375378092882100-10-1000100中国科大数据结构9-34 9.3 动态查找表p非平衡二叉树的平衡处理非平衡二叉树的平衡处理若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比处理的原则应
10、该是处理与插入点最近的、而平衡因子又比1大大或比或比-1小的结点。下面将分四种情况讨论平衡处理。小的结点。下面将分四种情况讨论平衡处理。中国科大数据结构9-35 9.3 动态查找表CBA210CBA000中国科大数据结构9-36 9.3 动态查找表2.LR型的处理型的处理(左右型左右型)n如下图所示，在如下图所示，在C的左孩子的左孩子A上扦入一个右孩子上扦入一个右孩子B，使的，使的C的平的平衡因子由衡因子由1变成了变成了2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将B变到变到A与与C 之间，使之成为之间，使之成为LL型，然后按第型，然后按第1种种情形情形LL型
11、处理。型处理。CBA210CBA000CBA2-10中国科大数据结构9-37 9.3 动态查找表3.RR型的处理型的处理(右右型右右型)n如下图所示，在如下图所示，在A的右孩子的右孩子B上扦入一个右孩子上扦入一个右孩子C，使，使A的平衡的平衡因子由因子由-1变成变成-2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将A逆时针旋转，成为逆时针旋转，成为B的左子树，而原来的左子树，而原来B的左子的左子树则变成树则变成A的右子树，待扦入结点的右子树，待扦入结点C成为成为B的右子树。的右子树。CBA-2-10CBA000中国科大数据结构9-38 9.3 动态查找表4.RL
12、型的处理型的处理(右左型右左型)n如下图所示，在如下图所示，在A的右孩子的右孩子C上扦入一个左孩子上扦入一个左孩子B，使，使A的平衡的平衡因子由因子由-1变成变成-2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将B变到变到A与与C之间，使之成为之间，使之成为RR型，然后按第型，然后按第(3)种情形种情形RR型处理。型处理。CBA-2-10CBA000ACB-210中国科大数据结构9-39 9.3 动态查找表p例例1：给定一个关键字序列：给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。，试生成一棵平衡二叉树。p分析：平衡二叉树实际上也是一棵二叉
13、排序树，故可以按建立二叉排序树分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见下图。后就可以建成一棵平衡二叉树。具体生成过程见下图。40a)插入插入4，平衡，平衡4-1b)插入插入5，平衡，平衡50c)插入插入7，不平衡，要处理，不平衡，要处理4-25-170405070RR型处理型处理中国科大数据结构9-40 9.3 动态查找表405170d)插入插入7，平衡，平衡2141527022e)插入插入1，不平衡，
14、要处理，不平衡，要处理104050702010LL型处理型处理4052702-111f)插入插入3，不平衡，要处理，不平衡，要处理30LR型处理型处理30405-1201070中国科大数据结构9-41 9.3 动态查找表304-15-2201071f)插入插入6，不平衡，要处理，不平衡，要处理06RL型处理型处理30406020107050中国科大数据结构9-42 9.3 动态查找表p平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找树完全相同。但它的查找 性能优
15、于二叉排序树，不像二叉排序树一性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树，它的时间复杂度与二叉排序树的最好时间复杂相同，都为的最好时间复杂相同，都为O(log2n)。中国科大数据结构9-43 9.3 动态查找表p例例2，对例，对例1给定的关键字序列给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平，试用二叉排序树和平衡二叉树两种方法查找，给出查找衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。的次数及成功的平均查找长度。p分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平分析：由于
16、关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见下座图，得到的二叉排衡二叉树都是唯一的。得到的平衡二叉树见下座图，得到的二叉排序树见下右图。序树见下右图。3462175平衡二叉树平衡二叉树3452176二叉排序树二叉排序树从右图的二叉排序树可知，查找从右图的二叉排序树可知，查找6 6需需4 4次，平均查找长度次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57ASL=(1+2+2+3+3+3+4)/7=18/72.57从左图的平衡二叉树可知，查找从左图的平衡二叉树可知，查找6 6需需2 2次，平均查找长度次，平均查找长度ASL=(1
17、+2+2+3+3+3+3)=17/72.43ASL=(1+2+2+3+3+3+3)=17/72.43从结果可知，从结果可知，平衡二叉树的查找性能优于二叉排序树平衡二叉树的查找性能优于二叉排序树。中国科大数据结构9-44 9.4 哈希表中国科大数据结构9-45 9.4 哈希表中国科大数据结构9-46 9.4 哈希表中国科大数据结构9-47 9.4 哈希表中国科大数据结构9-48 9.4 哈希表中国科大数据结构9-49 9.4 哈希表中国科大数据结构9-50 9.4 哈希表中国科大数据结构9-51 9.4 哈希表8 1 3 4 6 5 3 28 1 3 4 6 5 3 28 1 3 7 2 2 4
18、 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 3 6 8 5 3 78 1 4 1 9 3 5 58 1 4 1 9 3 5 5 分析：分析：只取只取8 8 只取只取1 1 只取只取3 3、4 4 只取只取2 2、7 7、5 5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位与任意两位或两位与另两位的叠加作哈希地
19、址另两位的叠加作哈希地址中国科大数据结构9-52 9.4 哈希表中国科大数据结构9-53 9.4 哈希表中国科大数据结构9-54 9.4 哈希表中国科大数据结构9-55 9.4 哈希表中国科大数据结构9-56 9.4 哈希表中国科大数据结构9-57 9.4 哈希表5 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加中国科大数据结构9-58 9.4 哈希表中国科大数据结构9-59 9.4 哈希表中国科大数据结构9-60 9.4 哈希表中国科大数据结构9-61 9.4 哈希
20、表中国科大数据结构9-62 9.4 哈希表0 1 2 3 4 5 6 7 8 9 60 17 29 (a)插入前插入前 60 17 29 38(b)线性探测再散列线性探测再散列 38 60 17 29(c)二次探测再散列二次探测再散列60 17 29 38(d)伪随机探测再散列伪随机探测再散列 用开放定址处理冲突时，关键字为用开放定址处理冲突时，关键字为3838的记录插入前后的哈希表的记录插入前后的哈希表 中国科大数据结构9-63 9.4 哈希表中国科大数据结构9-64 9.4 哈希表012345678910190114556811823623中国科大数据结构9-65 9.4 哈希表01234
21、5678910192336116855821401中国科大数据结构9-66 9.4 哈希表#define LEN 31/表长表长LEN最好为质数最好为质数typedef struct node int data;struct node*next;node;struct node HashTabLEN;中国科大数据结构9-67 9.4 哈希表int hash(int key)retAddr=key MOD LEN;return(retAddr);给定给定k值值计算计算hash(key)此地址为空此地址为空关键字关键字=key查找失败返回查找失败返回或插入新结点或插入新结点查找成功查找成功按处理冲突方法按处理冲突方法计算下一地址计算下一地址YNYN中国科大数据结构9-68 9.4 哈希表node*search(int key)i=hash(key);p=HashTabi.next;while(p!=NULL)if(p.data=key)return(p);p=p.next;q=malloc(sizeof(node);/表头插入表头插入q.data=key;q.next=HashTabi.next;HashTabi.next=q;return(q);中国科大数据结构9-69 9.4 哈希表中国科大数据结构9-70 9.4 哈希表中国科大数据结构9-71 习题
