数据结构：chap9查找

《数据结构：chap9查找》由会员分享，可在线阅读，更多相关《数据结构：chap9查找（167页珍藏版）》请在金锄头文库上搜索。

1、第九章第九章查查 找找何谓查找表何谓查找表 ？ 查找表是由同一类型同一类型的数据元素(或记录)构成的集合集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的对查找表经常进行的操作操作:1）查查询询某个“特定的”数据元素是否在查找表中；2）检检索索某个“特定的”数据元素的各种属性；3）在查找表中插入插入一个数据元素；4）从查找表中删去删去某个数据元素。仅作查询和检索操作的查找表。静态查找表静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查

2、找表动态查找表查找表可分为两类查找表可分为两类:是数据元素（或记录）中某个数据项数据项的值，用以标识标识（识别）一个数据元素（或记录）。关键字关键字 若此关键字可以识别唯一的唯一的一个记录，则称之谓“主关键字主关键字”。 若此关键字能识别若干若干记录，则称之谓“次关键字次关键字”。 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 查找查找 若查找表中存在这样一个记录，则称“查找成功查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功查找不成功”。查找结果给出“空记录”或“空指针”。 由于查找表中的数据元素之间不存在明显的组织规

3、律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表用另外一种结构来表示查找表。如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。9.1 静态查找表静态查找表9.2 动态查找树表动态查找树表(二叉排序树二叉排序树)9.3 哈希表哈希表9.1 静静 态态 查查 找找 表表数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数据元素的集合。每个数每个数据元素含有类型相同的据元素含有类型相同的关键字关键字，可唯一标识数据元素。 数据元素同属一个集合。ADT StaticSea

4、rchTable Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P： ADT StaticSearchTable构造一个含n个数据元素的静态查找表ST。 Create(&ST, n);操作结果：销毁表ST。Destroy(&ST);初始条件：操作结果：静态查找表ST存在；若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。 Search(ST, key);初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；按

5、某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;假设静态查找表静态查找表的顺序存储结构顺序存储结构为ElemType *elem;数据元素类型的定义为数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; ,

6、TElemType ;一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表三、静态查找树表（不讲）三、静态查找树表（不讲）四、索引顺序表四、索引顺序表 以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找表ST.elem回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值 e=64,要求 ST.elemk = e, 问: k = ?kkint location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem; while ( k=L.length & !(*compare)(

7、*p+,e) k+; if ( k= L.length) return k; else return 0; /locationST.elemiST.elemi60ikey=64key=60i64int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Sear

8、ch_Seq 定义：定义： 查找算法的平均查找长度平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 ， Ci为找到该记录时，曾和给定值比较过的关键字的个数。分析顺序查找的时间性能在等概率查找的情况下， 顺序表查找的平均查找长度为：对顺序表顺序表而言，Ci = n-i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。在不等概率查找的情

9、况下，ASLss 在 PnPn-1P2P1时取极小值 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表二、有序查找表 若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。ST.elemST.length例如例如: key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid = (low+high)/2int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间

10、初值 while (low 50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。关键字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3三、静态查找树表三、静态查找树表 在不等概率查找不等概率查找的情况下，折半查找折半查找不是不是有序表最好的查找方法。ASL:平均查找长度例如例如:此时 ASL=20.2+30.3+10.05+20.3+30.15=2.4若改变Ci的值 2 1 3 2 3则 ASL=20.2+10.3+30.05+20.3+30.15=1.9 使 达最小的判定树称为最

11、优二叉树，其中: 定义定义:为计算方便，令 wi = pi选择二叉树的根结点，使 达最小 介绍一种次优二叉树的构造方法：为便于计算，引入累计权值和 并设 wl-1 = 0 和 swl-1 = 0，则推导可得023811 15 18 23例如例如:lh21 18 124310 18h9608EC21Ah53lhG3013ECGABDF所得次优二叉树如下所示所得次优二叉树如下所示: 查找比较查找比较“总次数总次数” = 3 2+4 1+2 5+3 3 +1 4+3 3+2 5 = 52 查找比较查找比较“总次数总次数” = 3 2+2 1+3 5+1 3 +3 4+2 3+3 5 = 59和折半查

12、找相比较和折半查找相比较DBACFEGStatus SecondOptimal(BiTree &T, ElemType R, float sw, int low, int high) / 由有序表Rlow.high及其累计权值表sw / 递归构造次优查找树T。 选择最小的选择最小的Pi值值 if (!(T = (BiTree)malloc(sizeof(BiTNode) return ERROR; T-data = Ri; / 生成结点构造次优二叉树的算法if (i=low) T-lchild = NULL; / 左子树空else SecondOptimal(T-lchild, R, sw,

13、low, i-1); / 构造左子树 if (i=high) T-rchild = NULL; / 右子树空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 构造右子树 return OK; / SecondOptimal次优查找树采用二叉链表的存储结构Status CreateSOSTre(SOSTree &T, SSTable ST) / 由有序表 ST 构造一棵次优查找树 T / ST 的数据元素含有权域 weight if (ST.length = 0) T = NULL; else FindSW(sw, ST); / 按照有序表 S

14、T 中各数据元素 / 的 weight 值求累计权值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree索引顺序表的查找过程：索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。注意：索引可以根据查找表的特点来构造。可见， 索引顺序查找索引顺序查找的过程也是一个“缩小区间缩小区间”的查找过程。索引顺序查找的平均查找长度索引顺序查找的平均查找长度 = 查找查找“索引索引”的平均查找长度的平均查找长度 + 查找查找“顺序表顺序表”的平均查找长度的平均查找长度ADT Dynam

15、icSearchTable 抽象数据类型抽象数据类型动态查找表动态查找表的定义如下：的定义如下：数据对象数据对象D：数据关系数据关系R： 数据元素同属一个集合。D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字， 可唯一标识数据元素。InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT, key);InsertDSTable(&DT, e);DeleteDSTable(&T, key);TraverseDSTable(DT, Visit();ADT DynamicSearchTable操作结果：操作结果：构造

16、一个空的动态查找表DT。InitDSTable(&DT);销毁动态查找表DT。DestroyDSTable(&DT);初始条件： 操作结果：动态查找表DT存在；若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。SearchDSTable(DT, key);初始条件：操作结果：动态查找表DT存在，key为和关键字类型相同的给定值；动态查找表DT存在， e 为待插入的数据元素；InsertDSTable(&DT, e);初始条件：操作结果：若DT中不存在其关键字等于 e.key 的 数据元素，则插入 e 到DT。动态查找表DT存在，key为和关键字类型相

17、同的给定值；DeleteDSTable(&T, key);初始条件：操作结果：若DT中存在其关键字等于key的数据元素，则删除之。动态查找表DT存在，Visit是对结点操作的应用函数；TraverseDSTable(DT, Visit();初始条件：操作结果：按某种次序对DT的每个结点调用函数 Visit() 一次且至多一次。一旦 Visit() 失败，则操作失败。9.2 动动 态态 查查 找找 树树 表表(n) (1)(n) (1)(nlogn)综合上一节讨论的几种查找表的特性：综合上一节讨论的几种查找表的特性：查找 插入 删除无序顺序表 无序线性链表有序顺序表 有序线性链表 静态查找树表(

18、n)(n) (logn)(n) (logn)(1) (1)(n) (1)(nlogn)1）从查找性能看，最好情况能达 (logn)，此时要求表有序；2）从插入和删除的性能看，最好 情况能达 (1)，此时要求存储 结构是链表。可得如下结论：可得如下结论：一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）二、二叉平衡树二、二叉平衡树三、三、B - 树树四、四、B+树树五、键五、键 树树一、二叉排序树一、二叉排序树（二叉查找树）（二叉查找树）1定义定义2查找算法查找算法3插入算法插入算法4删除算法删除算法5查找性能的分析查找性能的分析（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点

19、的值；1定义：定义： 二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉 排序树。（2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值；503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不不 通常，取二叉链表作为二叉排序树的存储结构typedef struct BiTNode / 结点结构结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;TElemType data;2二叉排序树的查找算法：二叉排序树的查找算法：1）若给定值等于

20、等于根结点的关键字，则查找成功查找成功；2）若给定值小于小于根结点的关键字，则继续在左子树上进行查找继续在左子树上进行查找；3）若给定值大于大于根结点的关键字，则继续在右子树上进行查找继续在右子树上进行查找。否则，若二叉排序树为空为空，则查找不成功查找不成功；50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 ,从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径： 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定

21、值的结点逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。 查找成功查找成功 查找不成功查找不成功算法描述如下：算法描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指针在根指针 T 所指二叉排序树中递归地查找其所指二叉排序树中递归地查找其 / 关键字等于关键字等于 key 的数据元素，若的数据元素，若查找成功查找成功， / 则返回指针则返回指针 p 指向该数据元素的结点，并返指向该数据

22、元素的结点，并返回回 / 函数值为函数值为 TRUE; / SearchBST 否则表明否则表明查找不成功查找不成功，返回，返回 / 指针指针 p 指向查找路径上访问的最后一个结点，指向查找路径上访问的最后一个结点， / 并返回函数值为并返回函数值为FALSE, 指针指针 f 指向当前访问指向当前访问 / 的结点的双亲，其初始调用值为的结点的双亲，其初始调用值为NULLif (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功 p = T; re

23、turn TRUE; / 查找成功SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找30201040352523fT设 key = 48fTfT22pfTfTTTTfffp根据动态查找表的定义，“插入插入”操作在操作在查找不成功查找不成功时才进行时才进行；3二叉排序树的插入算法二叉排序树的插入算法若二叉排序树为空树空树，则新插入的结点为新的根结点新的根结点；否则，新插入的结点必为一个新的叶子结点新的叶子结点，其插入位置插入位置由查找过程得到。Status Inser

24、t BST(BiTree &T, ElemType e ) / 当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 / 数据元素时，插入元素值为数据元素时，插入元素值为 e 的结点，并返的结点，并返 / 回回 TRUE; 否则，不进行插入并返回否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST s = (BiTree) malloc (sizeof (BiTNode); / 为新结点分配空间s-data = e; s-lchild = s-rchi

25、ld = 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; / 插入成功（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法二叉排序树的删除算法可分三种情况讨论： 和插入相反，删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍仍然保持二叉排序树

26、的特性然保持二叉排序树的特性。上述算法描述太复杂给出我的算法描述算法描述：1. 如果被删除的是叶子节点，直接删除；2. 如果不是叶子节点，则删除该节点后，以该节点的左子树的根节点替换该节点的位置；根据左子树情况，处理右子树：A. 若左子树为空，则以右子树的根节点替换被删除节点；B. 若左子树不为空，则右子树的根节点成为该左子树最右端的节点（可能为叶子或非叶子节点）的右孩子。50308020908540358832（1）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”503080209085403588

27、32（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 408050308020908540358832（3）被删除的结点既有左子树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键字被删关键字 = 50Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序树若二叉排序树 T 中存在其关键字等于中存

28、在其关键字等于 key 的的 / 数据元素，则删除该数据元素结点，并返回数据元素，则删除该数据元素结点，并返回 / 函数值函数值 TRUE，否则返回函数值否则返回函数值 FALSE if (!T) return FALSE; / 不存在关键字等于key的数据元素 else / DeleteBST算法描述如下：算法描述如下： if ( EQ (key, T-data.key) ) / 找到关键字等于key的数据元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key );

29、/ 继续在左子树中进行查找DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找void Delete ( BiTree &p ) / 从二叉排序树中删除结点 p， / 并重接它的左子树或右子树 if (!p-rchild) else if (!p-lchild) else / Delete其中删除操作删除操作过程如下所描述： / 右子树为空树则只需重接它的左子树q = p; p = p-lchild; free(q);pp/ 左子树为空树只需重接它的右子树q = p; p = p-rchild; free(q);ppq = p; s = p-lchild;whi

30、le (!s-rchild) q = s; s = s-rchild; / s 指向被删结点的前驱/ 左右子树均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接*q的左子树free(s);pqs5查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。由关键字序列 3，1，2，5，4构造而得的二叉排序树，由关键字序列 1，

31、2，3，4，5构造而得的二叉排序树，例如：例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 下面讨论平均情况下面讨论平均情况: 不失一般性，假设长度为 n 的序列中有 k 个关键字小于小于第一个关键字，则必有 n-k-1 个关键字大于大于第一个关键字,由它构造的二叉排序树：n-k-1k的平均查找长度是 n 和 k 的函数P(n, k) ( 0 k n-1 )。 假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度：在等概率查找等概率查找的情况下，由此可类似于解差分方程，此递

32、归方程有解：二、二叉平衡树二、二叉平衡树何谓何谓“二叉平衡树二叉平衡树”？二叉平衡树的查找性能分析二叉平衡树的查找性能分析如何构造如何构造“二叉平衡树二叉平衡树” 二叉平衡树二叉平衡树是二叉查找树的另一种形式，其特点为： 树中每个结点的树中每个结点的左、右子树深度左、右子树深度之差的绝对值不大于之差的绝对值不大于1 。例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树 构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如:依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转一次先向右旋转再向左旋转42

33、6589642895向左旋转一次继续插入关键字 9 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析：平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可能达到的最大深度最大深度是多少？n = 0空树空树最大深度为最大深度为 0n = 1最大深度为最大深度为 1n = 2最大深度为最大深度为 2n = 4最大深度为最大深度为 3n = 7最大深度为最大深度为 4先看几个具体情况:反过来问，深度为深度为 h 的二叉平衡树平衡树中所含结点的最小值含结点的最小值 Nh 是多少？h = 0N0

34、 = 0h = 1h = 2h = 3一般情况下一般情况下N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用归纳法可证得利用归纳法可证得Nh = Fh+2 - 1 因此，在二叉平衡树二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字进行比较的关键字的个数和的个数和 log(n) 相当。 由此推得，深度为深度为 h 的二叉平衡树二叉平衡树中所含结点的最小值含结点的最小值 Nh = h+2/5 - 1。 反之，含有含有 n 个结点的二叉平衡树能个结点的二叉平衡树能达到的最大深度达到的最大深度 hn = log ( 5 (n+1) - 2。 三、三、 B - 树

35、树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作5查找性能的分析查找性能的分析1B-树的定义树的定义B-树是一种 平衡平衡 的 多路多路 查找查找 树： 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字关键字 Ki（1 in） nm n 个指向记录的指针指向记录的指针 Di（1in） n+1 个指向子树的指针指向子树的指针 Ai（0in）多叉树的特性typedef struct BTNode int keynum; / 结点中关键字个数，结点大小 struct BTNode *parent; / 指向双亲结点的指针 KeyType keym+1; / 关键字（0号

36、单元不用） struct BTNode *ptrm+1; / 子树指针向量 Record *recptrm+1; / 记录指针向量 BTNode, *BTree; / B树结点和B树的类型B-树结构的树结构的C语言描述如下语言描述如下: :非叶结点中的多个关键字多个关键字均自小至大自小至大有序排列，即：K1 K2 keynum; i=Search(p, K); / 在p-key1.keynum中查找 i ， p-keyi=Kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的双亲 if (found) retu

37、rn (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点，有下列几种情况：3插入插入1）插入后，该结点的关键字个数nsymbol 其中: p 指向双链树中某个结点， 0 i K.num-1初始状态: p=T-first; i = 0;若 ( p & p-symbol = K.chi & ifirst; i+;若 ( p & p-symbol != K.chi )则继续在键树的同一层上进行查找 p=p-next;若 ( p & p-symbol=K.chi &

38、i=K.num-1)则 查找成功，返回指向相应记录的指针 p-infoptr 若 ( p = NULL)则表明查找不成功，返回“空指针”;3. Trie树树 以多重链表作存储结构实现的键树结点结构结点结构:分支结点分支结点叶子结点叶子结点指向记录的指针0 1 2 3 4 5 24 25 26关键字关键字指向下层结点的指针每个域对应一个“字母”0 1(A) 3 4 5(E) 9(I) 268(H)4(D) 19(S) 22(V) 0 18(R) 7(G) 190 5(E)THADHAS HAVE HEHERHEREHIGHHIS叶子结点叶子结点分支结点分支结点指向记录指向记录的指针的指针type

39、def struct TrieNode NodeKind kind; / 结点类型 union struct KeyType K; Record *infoptr lf; / 叶子结点(关键字和指向记录的指针) struct TrieNode *ptr27; int num bh; / 分支结点(27个指向下一层结点的指针) TrieNode, *TrieTree; / 键树类型结点结构的结点结构的 C 语言描述语言描述:在在 Trie 树中查找记录的过程树中查找记录的过程:假设假设: T 为指向 Trie 树根结点的指针， K.ch0.K.num-1 为待查关键字(给定值)。则则查找过程中的

40、基本操作为： 搜索和对应字母相应的指针搜索和对应字母相应的指针:若若 p 不空，且 p 所指为分支结点，则则 p = p-bh.Ptrord(K.Chi) ; ( 其中: 0 i K.num-1 )初始状态初始状态: p=T; i = 0;若若 ( p & p-kind = BRANCH & ibh.ptrord(K.chi); i+;其中，ord 为求字符在字母表中序号的函数若若 ( p & p-kind=LEAF & p-lf.K=K)则则 查找成功查找成功，返回返回指向相应记录的指针 p-lf.infoptr 反之，反之，即 ( !p | p-kind=LEAF & p-lf.K!=K

41、)则则表明查找不成功查找不成功，返回返回“空指针”; 一、一、哈希表是什么？哈希表是什么？二、哈希函数的构造方法哈希函数的构造方法 三、处理冲突的方法处理冲突的方法 四、哈希表的查找哈希表的查找 五、哈希表的删除操作哈希表的删除操作 六、对静态查找表，对静态查找表，9.3 哈哈 希希 表表 以上两节讨论的表示查找表的各种结构结构的共同特点特点：记录在表中的位置位置和它的关关键字键字之间不存在不存在一个确定的关系，一、哈希表是什么？哈希表是什么？ 查找的过程查找的过程为给定值给定值依次和关键字集合中各个关键字关键字进行比较比较， 查找的效率查找的效率取决于和给定值进行比较进行比较的关键字个数个数

42、。 用这类方法表示的查找表，其平均查找长度都不为零。 不同的表示方法，其差别仅在于：差别仅在于：关键字和给定值进行比较的顺序不同。 只有一个办法：预先知道所查关键字在表中的位置， 对于频繁使用的查找表，希望 ASL = 0。 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为以下标为000 999 的顺序表的顺序表表示之。例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键字。但是，对于动态查找表动

43、态查找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。1) 表长不确定；2) 在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例如：对于如下 9 个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 ChenZhaoQianSunLiWuHanYeDei问题问题: 若添加关键字 Zhou , 怎么办？怎么办

44、？能否找到能否找到另一个哈希函数？1) 哈希函数是一个映象映象，即： 将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上， 它的设置很灵活灵活，只要这个地址集地址集合的 大小不超出允许范围不超出允许范围即可；从这个例子可见：从这个例子可见：2) 由于哈希函数是一个压缩映象压缩映象，因此，在一般情况下，很容易产生“冲突冲突”现象，即： key1 key2，而 f(key1) = f(key2)。3) 很难很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)

45、的哈希函数之外；还需要找到一种“处理冲突” 的方法。哈希表的定义： 根据设定的哈希函数哈希函数 H(key) 和所选中的处理冲突的方法处理冲突的方法，将一组关键字映象映象到到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置存储位置，如此构造所得的查找表称之为“哈希表哈希表”。二、构造哈希函数的方法构造哈希函数的方法 对数字数字的关键字可有下列构造方法： 若是非数字关键字非数字关键字，则需先需先对其进行进行数字化处理数字化处理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数法除留余数法4. 折叠法折叠法6. 随机数法随机数法

46、2. 数字分析法数字分析法哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b1. 直接定址法直接定址法此法仅适合于：此法仅适合于：地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小此方法仅适合于：此方法仅适合于： 能预先估计出预先估计出全体关键字的每一位上每一位上各种数字出现的频度数字出现的频度。2. 数字分析法数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, , us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。 以关键字的平方值的中间几位作为存储地址。求“关键字的

47、平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。3. 平方取中法平方取中法 此方法适合于此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加移位叠加和间界叠加间界叠加。4. 折叠法折叠法 此方法适合于此方法适合于: 关键字的数字位数特别多。5. 除留余数法除留余数法 设定哈希函数为设定哈希函数为: H(key) = key MOD p 其中其中， pm ( (表长表长) ) 并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以

48、下的质因子以下的质因子给定一组关键字为：12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3例如：例如：为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质则所有含质因子因子 3 的关键字均映射到的关键字均映射到“3 的倍数的倍数”的的地址上地址上，从而增加了“冲突”的可能。6.随机数法随机数法设定哈希函数为设定哈希函数为: H(key) = Random(key)其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。 实际造表时，采用何种采用何种构造哈希函数的

49、方法方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到的原则是使产生冲突的可能性降到尽可能地小尽可能地小。三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突” 的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址。1. 开放定址法开放定址法2. 链地址法链地址法 为产生冲突的地址 H(key) 求得一个地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s1. 开放定址法开放定址法对增量 di 有三种取法：1) 线线性性探探

50、测测再再散散列列 di = c i 最简单的情况 c=12) 平平方方探探测测再再散散列列 di = 12, -12, 22, -22, ,3) 随随机机探探测测再再散散列列 di 是一组伪随机数列伪随机数列 或者 di=iH2(key) (又又称称双双散散列列函函数数探探测测)即：产生的 Hi 均不相同，且所产生的 s(m-1)个个 Hi 值能覆盖覆盖哈希表中所有 地址。则要求： 注意：注意：增量增量 di 应具有应具有“完备性完备性” 随机探测时的 m 和 di 没有公因子。 平方探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, 等）；例如例如: 关键字集合

51、 19, 01, 23, 14, 55, 68, 11, 82, 36 设定设定哈希函数 H(key) = key MOD 11 ( 表长=11 )190123 145568190123 1468若采用线性探测再散列线性探测再散列处理冲突若采用二次探测再散列二次探测再散列处理冲突11 8236551182361 1 2 1 3 6 2 5 1 H2(key) 是另设定的一个哈希函数，它的函数值应和 m 互为素数。若 m 为素数，则 H2(key) 可以是 1 至 m-1 之间的任意数任意数； 若 m 为 2 的幂次，则 H2(key) 应是 1 至 m-1 之间的任意奇数任意奇数。例如，当 m

52、=11时， 可设 H2(key)=(3 key) MOD 10+11901231455681182362 1 1 1 2 1 2 1 3将所有哈希地址相同的记录都链接在同一链表中。 2. 链地址法链地址法0123456140136198223116855 ASL=(61+22+3)/9=13/9例如:同前例的关键字，哈希函数为 H(key)=key MOD 7 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为： 四、哈希表的查找哈希表的查找 对于给定值 K， 计算哈希地址 i = H(K)若若 ri = NULL 则查找不成功若若 ri.key = K 则查找成功否则否则

53、 “求下一地址 Hi” ，直至 rHi = NULL (查找不成功) 或 rHi.key = K (查找成功) 为止。int hashsize = 997, . ; typedef struct ElemType *elem; int count; / 当前数据元素个数 int sizeindex; / hashsizesizeindex为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1/- 开放定址哈希表开放定址哈希表的存储结构 -Status SearchHash (HashTable H, Ke

54、yType K, int &p, int &c) / 在开放定址哈希表H中查找关键码为K的记录 / SearchHashp = Hash(K); / 求得哈希地址while ( H.elemp.key != NULLKEY & !EQ(K, H.elemp.key)） collision(p, +c); / 求得下一探查地址 pif (EQ(K, H.elemp.key) return SUCCESS; / 查找成功，返回待查数据元素位置 pelse return UNSUCCESS; / 查找不成功Status InsertHash (HashTable &H, Elemtype e) /

55、InsertHashc = 0;if ( HashSearch ( H, e.key, p, c ) = SUCCESS ) return DUPLICATE; / 表中已有与 e 有相同关键字的元素else H.elemp = e; +H.count; return OK; / 查找不成功时，返回 p为插入位置else RecreateHashTable(H); / 重建哈希表 if ( c hashsizeH.sizeindex/2 ) / 冲突次数 c 未达到上限，（阀值 c 可调） 1) 选用的哈希函数哈希函数；2) 选用的处理冲突的方法处理冲突的方法；3) 哈希表饱和的程度，装载因子

56、装载因子 =n/m 值的大小大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找的决定哈希表查找的ASL的因素的因素：哈希表查找的分析: 从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。 一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。 因此，因此，哈希表的哈希表的ASL是是处理冲突方法处理冲突方法和和装载因子装载因子的函数。的函数。例如：前述例子线性探测处理冲突时， ASL =双散列探测处理冲突时，ASL =链地址法处理冲突时， ASL =22/914/913/9线性探测再散列线性探测再散列链地址法链地址法随机探测再散列

57、随机探测再散列可以证明：查找成功查找成功时有下列结果：从以上结果可见： 哈希表的平均查找长度是 的函数，而不是 n 的函数。 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定在某个范围内平均查找长度限定在某个范围内。 这是哈希表所特有的特点。这是哈希表所特有的特点。 从哈希表中删除记录时，要作特殊处理特殊处理，相应地，需要修改查找的算法。五、哈希表的删除操作哈希表的删除操作六、哈希表也可以用来构造静态查六、哈希表也可以用来构造静态查找表找表 并且，对静态查找表，有时可以对静态查找表，有时可以找到不发生冲突的哈希函数。即，此时的哈希表的哈希表的 ASL=0, 称此类哈希函数为理想（perfect）的哈希函数。 1. 顺序表顺序表和有序表有序表的查找方法及其平均查找长度的计算方法。 3. 熟练掌握二叉排序树二叉排序树的构造和查找方法。 2. 静态查找树的构造方法和查找算法,理解静态查找树和折半查找的关系。 4. 理解B-树树、B+树和建树树和建树的特点特点以及以及它们的建树和查找的过程。它们的建树和查找的过程。 5. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。 6. 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。