第 9 章查找查找表概念查找表概念查找表是由查找表是由同一类型同一类型的数据元的数据元素构成的集合。由于素构成的集合。由于“集合集合”中的数据元素之间存在着松散中的数据元素之间存在着松散的关系，因此查找表是一种应的关系，因此查找表是一种应用灵活且方便的结构。用灵活且方便的结构。查找表的常见查找表的常见操作操作 1）查查询询某某个个“特特定定的的”数数据据元元素素是是否否在查找表中；在查找表中； 2）检检索索某某个个“特特定定的的”数数据据元元素素的的各各种属性；种属性； 3）在查找表中）在查找表中插入插入一个数据元素；一个数据元素； 4）从查找表中）从查找表中删去删去某个数据元素。某个数据元素。仅作仅作查询查询操作的查找表。操作的查找表。静态查找表静态查找表如果在查询之后，还需要将如果在查询之后，还需要将“不在查不在查找表中找表中”的数据元素的数据元素插入插入到查找表中；到查找表中；或者，从查找表中或者，从查找表中删除删除其其“查询查询”结结果为果为“在查找表中在查找表中”的数据元素。的数据元素。动态查找表动态查找表查找表的两个类别：是数据元素（或记录）中某个是数据元素（或记录）中某个数据项数据项的值，用以的值，用以标识标识（识别）一个数据元（识别）一个数据元素（或记录）。素（或记录）。关键字关键字若此关键字可以标识若此关键字可以标识惟一惟一的记录，则称的记录，则称之谓之谓“主关键字主关键字”。若此关键字能识别若此关键字能识别若干个若干个记录，则称记录，则称之谓之谓“次关键字次关键字”。 根据给定的某个值，在查找表中根据给定的某个值，在查找表中确定一确定一个其关键字等于给定值的数据元素。个其关键字等于给定值的数据元素。 查找查找若查找表中存在这样一个记录，则称若查找表中存在这样一个记录，则称“查找成功查找成功”。查找结果。查找结果给出整个记录的给出整个记录的信息，或指示该记录在查找表中的位置信息，或指示该记录在查找表中的位置；否则称否则称“查找不成功查找不成功”。查找结果。查找结果给出给出“空记录空记录”或或“空指针空指针”。由于查找表中的数据元素之间不存在明显的由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找组织规律，因此不便于查找。为了提高查找的效率，的效率， 需要在查找表中的元素之间人为需要在查找表中的元素之间人为地地 附加某种确定的关系，即附加某种确定的关系，即用另外一种结用另外一种结构来表示查找表构来表示查找表。如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。9.1 静态查找表静态查找表9.2 动态查找表动态查找表9.3 哈希表哈希表9.1 静静 态态 查查 找找 表表数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数是具有相同特性的数据元素的集合。据元素的集合。每个数每个数据元素含有类型相同的据元素含有类型相同的关键字，可惟一地标识关键字，可惟一地标识数据元素。数据元素。 数据元素同属一个集合。数据元素同属一个集合。ADT StaticSearchTable 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 为与为与查找表中元素的关键字类型相查找表中元素的关键字类型相同的给定值；同的给定值；按某种次序对ST的每个元素调用函数Visit()一次且仅一次。一旦Visit()失败，则操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；typedef struct ElemType *elem; / 0号单元留空号单元留空 int Length; / 表的长度表的长度 SSTable;静态查找表静态查找表的顺序存储结构顺序存储结构实现typedef struct keyType key; / 关键字域关键字域 / 其它属性域其它属性域 ElemType ; 一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表三、静态查找树表三、静态查找树表四、索引顺序表四、索引顺序表 以顺序表或线性链表表示静态查找表。一、顺序查找表顺序查找表ST.elem顺序表的查找过程：顺序表的查找过程：假设给定值假设给定值 e=64,要求要求 ST.elemk = e, 问问: k = ?k k k k k k kint location( SSTable ST, KeyType key) k = 1; for (k=1; k=L.Length &ST.elemk!=key;k+); if ( k= L.Length) return k; else return 0;ST.elemST.elem60ikey=64key=60i64iiiiiiiiiiiiiiiint Search_Seq(SSTable ST, KeyType key) ST.elem0.key = key; / “哨兵哨兵” for (i=ST.Length; ST.elemi.key!=key; -i); return i; / 找不到时，找不到时，i为为0 定义：定义： 查找算法的查找算法的平均查找长度平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需与给为确定记录在查找表中的位置，需与给定值定值进行比较的关键字个数的期望值。进行比较的关键字个数的期望值。 其中其中: n 为表长，为表长，Pi 为查找表中第为查找表中第i个记录的概率，个记录的概率， 且且 ， Ci为找到该记录时与为找到该记录时与给定给定 值比较过的关键字个数。值比较过的关键字个数。分析顺序查找的时间性能在等概率查找的情况下， 顺序表查找成功的平均查找长度为：对顺序表顺序表而言，Ci = n-i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn若查找概率无法事先测定，则查找过程若查找概率无法事先测定，则查找过程采取的改进办法是，采取的改进办法是，在每次查找之后，在每次查找之后，将刚刚查找到的记录直接移至表尾的位将刚刚查找到的记录直接移至表尾的位置上置上。在不等概率查找的情况下，ASLss 在 PnPn-1P2P1时取极小值。 上述顺序查找表的查找算法简单，上述顺序查找表的查找算法简单，但平均查找长度较大，不适用于数但平均查找长度较大，不适用于数据元素数目比较多的查找表。据元素数目比较多的查找表。二、有序查找表若以若以有序表有序表表示静态查找表，则表示静态查找表，则查找过程可以基于查找过程可以基于“折半折半”进行。进行。ST.elemST.length例如例如: : key=64key=64 的查找过程如下：的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界指示查找区间的下界high 指示查找区间的上界指示查找区间的上界mid = (low+high)/2int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值置区间初值 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=2 0.2+3 0.3+1 0.05+2 0.3+3 0.15=2.4若改变比较顺序若改变比较顺序 2 1 3 2 3则则 ASL=2 0.2+1 0.3+3 0.05+2 0.3+3 0.15=1.9若只考虑查找成功的情形，则若只考虑查找成功的情形，则最优判定树为带权的内路径长最优判定树为带权的内路径长度之和度之和PH最小。即：最小。即：其中：其中：n：有序表的长度有序表的长度hi：第第i个结点在判定树中的层次数个结点在判定树中的层次数wi=c*pipi：查找概率查找概率c：常量常量关键字关键字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3 Ci： 2 1 3 2 3CADBEPH=0.05+(0.2+0.3)*2 +(0.3+0.15)*3 =2.4BADBEPH=0.3+(0.2+0.3)*2 +(0.05+0.15)*3 =1.9 由于构造最优判定树的代价过由于构造最优判定树的代价过高，因此，通常寻找接近最优高，因此，通常寻找接近最优判定树的次优判定树。即带权判定树的次优判定树。即带权的内路径长度近似最小。的内路径长度近似最小。 (rl,rl+1,.,rh) rl.keyrl+1.key.data = Ri; / 生成结点生成结点构造次优二叉树的算法构造次优二叉树的算法if (i=low) T-lchild = NULL; / 左子树空左子树空else SecondOptimal(T-lchild, R, sw, low, i-1); / 构造左子树构造左子树 if (i=high) T-rchild = NULL; / 右子树右子树空空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 构造右子树构造右子树 return OK;次优查找树采用二叉链表的存储结构次优查找树采用二叉链表的存储结构Status CreateSOSTre(SOSTree &T, SSTable ST) / 由有序表由有序表 ST 构造一棵次优查找树构造一棵次优查找树 T / ST 的数据元素含有权域的数据元素含有权域 weight if (ST.length = 0) T = NULL; else FindSW(sw, ST); / 按照有序表按照有序表 ST 中各数据元素中各数据元素 / 的的 weight 值求累计权值表值求累计权值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree四、索引顺序表的查找过程：四、索引顺序表的查找过程：1）由索引确定记录所在区间；）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。）在顺序表的某个区间内进行查找。注意：索引可以根据查找表的特点来构造。注意：索引可以根据查找表的特点来构造。可见，可见， 索引顺序查找索引顺序查找的过程也是一个的过程也是一个“缩小区间缩小区间”的查找过程。的查找过程。22 12 13 8 22 9 20 33 42 44 38 24 48 60 58 74 49 86 5322 48 8617 13索引表索引表最大关键字最大关键字起始地址起始地址索引顺序查找的平均查找长度索引顺序查找的平均查找长度 = 查找查找“索引索引”的平均查找长度的平均查找长度(Lb) + 查找查找“顺序表顺序表”的平均查找长度的平均查找长度(Lw)9.2 动态查找表动态查找表ADT DynamicSearchTable 抽象数据类型抽象数据类型动态查找表动态查找表的定义如下：的定义如下：数据对象数据对象D：数据关系数据关系R： 数据元素同属一个集合。数据元素同属一个集合。D是具有相同特性的数据元是具有相同特性的数据元素的集合。素的集合。每个数据元素含有类型相同每个数据元素含有类型相同的关键字，可惟一地标识数的关键字，可惟一地标识数据元素。据元素。InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT, key);InsertDSTable(&DT, e);DeleteDSTable(&T, key);TraverseDSTable(DT, Visit();ADT DynamicSearchTable操作结果：操作结果：构造一个空的动态查找表构造一个空的动态查找表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为和关键字类型相同的给为和关键字类型相同的给定值；定值；DeleteDSTable(&T, key);初始条件：初始条件：操作结果：操作结果：若若DT中存在其关键字等中存在其关键字等于于key的数据元素，则删的数据元素，则删除之。除之。动态查找表动态查找表DT存在，存在，Visit是对结点操作的应用函数；是对结点操作的应用函数；TraverseDSTable(DT, Visit();初始条件：初始条件：操作结果：操作结果：按某种次序对按某种次序对DT的每个结的每个结点调用函数点调用函数 Visit() 一次且一次且至多一次。一旦至多一次。一旦 Visit() 失失败，则操作失败。败，则操作失败。一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）二、平衡二叉树二、平衡二叉树三、三、B - 树树四、四、B+树树五、键五、键 树树一、二叉排序树（二叉查找树）1定义定义2查找算法查找算法3插入算法插入算法4删除算法删除算法5查找性能的分析查找性能的分析（1）若它的左子树不空，则左子树上）若它的左子树不空，则左子树上 所有所有结点的值结点的值均小于均小于根结点的值；根结点的值；1定义定义 二叉排序树二叉排序树或者是一棵空二叉树；或者是一棵空二叉树；或者是具有如下特性的二叉树：或者是具有如下特性的二叉树：（3）它的左、右子树）它的左、右子树也都也都分别分别是二叉是二叉 排序树排序树。（2）若它的右子树不空，则右子树上）若它的右子树不空，则右子树上 所有所有结点的值结点的值均大于均大于根结点的值；根结点的值；503080209010854035252388是二叉排序树是二叉排序树503080209010854035252388不是二叉排序树。不是二叉排序树。66通常，用二叉链表作为二叉排序树的存储结构。typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;2二叉排序树的查找算法：二叉排序树的查找算法： 1）若给定值）若给定值等于等于根结点的关键字，根结点的关键字，则查找成功；则查找成功； 2）若给定值）若给定值小于小于根结点的关键字，根结点的关键字，则继续在左子树上进行查找；则继续在左子树上进行查找； 3）若给定值）若给定值大于大于根结点的关键字，根结点的关键字，则继续在右子树上进行查找。则继续在右子树上进行查找。否则，否则，若二叉排序树若二叉排序树为空为空，则查找不成功；，则查找不成功；50308020908540358832例如例如: :二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径： 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。 查找成功查找成功 查找不成功查找不成功Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / SearchBSTif (!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 ); / 在右子树中继续查找在右子树中继续查找30201040352523fT设 key = 48fTfT22pfTfTTTTfffpq根据动态查找表的定义，根据动态查找表的定义，“插入插入”操作在操作在查找不成功查找不成功时才进行；时才进行；3二叉排序树的插入算法二叉排序树的插入算法若二叉排序树为空树，则新插入的结点为若二叉排序树为空树，则新插入的结点为新的根结点新的根结点；否则，新插入的结点必为一；否则，新插入的结点必为一个个新的叶子结点新的叶子结点，其插入位置由查找过程，其插入位置由查找过程得到。得到。Status Insert BST(BiTree &T, ElemType e ) / 当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 / 数据元素时，插入元素值为数据元素时，插入元素值为 e 的结点，并返的结点，并返 / 回回 TRUE; 否则，不进行插入并返回否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BSTs = new 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; / 插入成功插入成功 (1) 被删除的结点被删除的结点是叶子是叶子； (2) 被删除的结点被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树； (3) 被删除的结点被删除的结点既有左子树，也有既有左子树，也有右子树右子树。4二叉排序树的删除算法二叉排序树的删除算法可分可分三种情况三种情况讨论：讨论：与插入相反，删除在与插入相反，删除在查找成功查找成功之后进行，之后进行，并且要求在删除二叉排序树上某个结点之并且要求在删除二叉排序树上某个结点之后，后，仍然保持二叉排序树的特性。仍然保持二叉排序树的特性。50308020908540358832（1）被删除的结点是）被删除的结点是叶子结点叶子结点被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832（2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 408050308020908540358832（3）被删除的结点）被删除的结点既有左子树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点被删结点前驱结点前驱结点被删关键字被删关键字 = 50Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序树若二叉排序树 T 中存在其关键字等于中存在其关键字等于 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 ); / 继续在左子树中进行查找继续在左子树中进行查找DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找继续在右子树中进行查找void Delete ( BiTree &p ) / 从从二叉排序树中删除结点二叉排序树中删除结点 p， / 并重接它的左子树或右子树并重接它的左子树或右子树 if (!p-rchild) /右空右空 else if (!p-lchild) /左左空空 else / Delete其中其中删除操作删除操作过程如下所描述：过程如下所描述： / 右子树为空树则只需重接它的左子树q = p; p = p-lchild; delete q;pp/ 左子树为空树只需重接它的右子树q = p; p = p-rchild; delete q;ppq = p; s = p-lchild;while (!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的左子树的左子树delete s;pqs5查找性能的分析查找性能的分析对于每一棵特定的二叉排序树，均对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它可按照平均查找长度的定义来求它的的 ASL 值，显然，由值相同的值，显然，由值相同的 n 个个关键字构造所得的不同形态的各棵关键字构造所得的不同形态的各棵二叉排序树的平均查找长二叉排序树的平均查找长 度的值不度的值不同，甚至可能差别很大。同，甚至可能差别很大。由关键字序列由关键字序列 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平均情况平均情况: :不失一般性，假设长度为不失一般性，假设长度为 n 的序列中的序列中有有 k 个关键字个关键字小于小于第一个关键字，则第一个关键字，则必有必有 n-k-1 个关键字个关键字大于大于第一个关键字第一个关键字,由它构造的二叉排序树：由它构造的二叉排序树：n-k-1k的平均查找长度是的平均查找长度是 n 和和 k 的函数的函数P(n, k) ( 0 k n-1 )。假设假设 n 个关键字可能出现的个关键字可能出现的 n! 种排列种排列的可能性相同，则含的可能性相同，则含 n 个关键字的二叉个关键字的二叉排序树的平均查找长度：排序树的平均查找长度：在在等概率查找等概率查找的情况下，的情况下，二、平衡二叉树二、平衡二叉树n何谓何谓“平衡平衡二叉树二叉树”？n如何构造如何构造“平衡二叉树平衡二叉树”n平衡二叉树的查找性能分析平衡二叉树的查找性能分析平衡二叉树平衡二叉树是二叉排序树的另一种形式，是二叉排序树的另一种形式，其特点为：其特点为：树中每个结点的树中每个结点的左、右子树深度之差的左、右子树深度之差的绝对值不大于绝对值不大于1，即，即548254821是平衡树是平衡树不是平衡树不是平衡树 构造平衡二叉树的方法是：构造平衡二叉树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如例如:依次插入的关键字为依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转一次先向右旋转再向左旋转426589642895向左旋转一次继续插入关键字 9二叉排序树的平衡旋转ABBLARBRhh-1h-112ABBLARBR00LL型型二叉排序树的平衡旋转RR型型ABBRALBLhh-1h-1-1-2ABBRBLAL00二叉排序树的平衡旋转LR型型ABBLARCLh-1h-2h-1-12CRC1ACBLARCR-10B0CL二叉排序树的平衡旋转RL型型BCALBRCR-10A0CLABBRALCLh-1h-2h-11-2CRC1在平衡树上进行查找的过程和二叉排序在平衡树上进行查找的过程和二叉排序树相同，因此，树相同，因此，查找过程中和给定值进查找过程中和给定值进行比较的关键字的个数不超过平衡行比较的关键字的个数不超过平衡 树的树的深度。深度。在平衡二叉树上进行查找时，在平衡二叉树上进行查找时，查找过程查找过程中与给定值进行比较的关键字个数与中与给定值进行比较的关键字个数与 log(n) 相当相当。平衡树的查找性能分析：平衡树的查找性能分析：三、三、B - 树树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作5查找性能的分析查找性能的分析1. B-树的定义 一棵一棵m阶的阶的B-树，或为空树，或为满足下列特性的树，或为空树，或为满足下列特性的m叉树：叉树： (1)树中每个结点至多有树中每个结点至多有m棵子树；棵子树； (2)若根结点不是叶子结点，则至少有两棵子树；若根结点不是叶子结点，则至少有两棵子树； (3)除根之外的所有非终端结点至少有除根之外的所有非终端结点至少有 m/2 棵子树；棵子树； (4)所有的非终端结点中包含下列信息数据所有的非终端结点中包含下列信息数据 (n,A0,K1,A1,K2,A2,.,Kn,An) 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) return (p,i,1); / 查找成功查找成功 else return (q,i,0); / 查找不成功查找不成功 / SearchBTree在查找不成功之后，需进行插在查找不成功之后，需进行插入。显然，入。显然，关键字插入的位置关键字插入的位置必定位于最下层叶结点必定位于最下层叶结点，有下，有下列几种情况：列几种情况：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 & i=K.num-1)则查找成功，则查找成功，返回指向相应记录的指针返回指向相应记录的指针 p-infoptr 若若 ( p = NULL)则表明查找不成功，返回则表明查找不成功，返回“空指针空指针”;3. Trie树树(retrieve) 以树的多重链表表示法存储键树以树的多重链表表示法存储键树分支结点分支结点叶子结点叶子结点指向记录指向记录的指针的指针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叶子结点叶子结点分支结点分支结点指向记录指向记录的指针的指针typedef 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 为待查关键字为待查关键字(给定值给定值)。则查找过程中的基本操作为：则查找过程中的基本操作为： 搜索和对应字母相应的指针搜索和对应字母相应的指针:若若 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 )则表明则表明查找不成功查找不成功，返回，返回“空指针空指针”;9.3 9.3 哈希表哈希表一、哈希表是什么？一、哈希表是什么？二、哈希函数的构造方法哈希函数的构造方法三、处理冲突的方法处理冲突的方法四、哈希表的查找哈希表的查找五、哈希表的删除操作哈希表的删除操作 以上两节讨论的表示查找表的各种以上两节讨论的表示查找表的各种结构结构的共同的共同特点特点：记录在表中的位记录在表中的位置和它的关键字之间不存在一个确置和它的关键字之间不存在一个确定的关系，定的关系，查找的过程查找的过程为给定值依为给定值依次和关键字集合中各个关键字进行次和关键字集合中各个关键字进行比较比较，查找的效率查找的效率取决于和给定值取决于和给定值进行比较进行比较的关键字个数。的关键字个数。一、哈希表是什么？哈希表是什么？用这类方法表示的查找表，用这类方法表示的查找表，其平其平均查找长度都不为零。均查找长度都不为零。 不同的表示方法，其差别仅在于：不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不关键字和给定值进行比较的顺序不同。同。只有一个办法：预先知道所查关键只有一个办法：预先知道所查关键字在表中的位置，即，要求：字在表中的位置，即，要求：记录记录在表中位置和其关键字之间存在一在表中位置和其关键字之间存在一种确定的关系种确定的关系。 对于频繁使用的查找表，希望对于频繁使用的查找表，希望 ASL = 0。若若以下标为以下标为000 999 的顺序表的顺序表表示之。表示之。例如：例如：为每年招收的为每年招收的 1000 名新生建立一名新生建立一张查找表，其关键字为学号，其值的范围张查找表，其关键字为学号，其值的范围为为 xx000 xx999 (前两位为年份前两位为年份)。则查找过程可以简单进行：取给定值（学号）则查找过程可以简单进行：取给定值（学号）的后三位，的后三位，不需要经过比较便可直接从顺序不需要经过比较便可直接从顺序表中找到待查关键字。表中找到待查关键字。但是，对于但是，对于动态查找表动态查找表而言，而言，因此在一般情况下，需要利用关键字设计因此在一般情况下，需要利用关键字设计一个函数关系，以确定该记录的存储位置。一个函数关系，以确定该记录的存储位置。该函数将该函数将以记录的关键字以记录的关键字 key 作为自变作为自变量量，通常通常称称这个函数这个函数 H(key) 为哈希函数。为哈希函数。1) 表长不确定；表长不确定；2) 在设计查找表时，只知道关键字所在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。属范围，而不知道确切的关键字。 0 1 2 3 4 5 6 7 8 9 10 11 12 13Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例如：对于如下 9 个关键字设设 哈希函数哈希函数 H(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 ChenZhaoQian SunLiWuHanYeDei问题问题: :若添加关键字若添加关键字 Z Zhouhou , , 怎么办？怎么办？能否找到另一个哈希函数？能否找到另一个哈希函数？1) 哈希函数是一个哈希函数是一个映象映象，即：，即： 将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要不超出地址集合它的设置很灵活，只要不超出地址集合允许的范围即可；允许的范围即可；从这个例子可见：从这个例子可见：2) 由于哈希函数是一个由于哈希函数是一个压缩映象压缩映象，因此，因此，在一般情况下，很容易产生在一般情况下，很容易产生“冲突冲突”现象，现象，即：即： key1 key2，而而 H(key1) = H(key2)。3) 3) 很难很难找到一个不产生冲突的哈希函数。找到一个不产生冲突的哈希函数。一般情况下，一般情况下，只能选择恰当的哈希函数，使冲只能选择恰当的哈希函数，使冲突尽可能少地产生。突尽可能少地产生。因此，在构造这种特殊的因此，在构造这种特殊的“查找表查找表” 时，除了时，除了需要选择一个需要选择一个“好好”( (尽可能少产生冲突尽可能少产生冲突) )的哈的哈希函数之外；还需要找到希函数之外；还需要找到一种一种“处理冲突处理冲突” 的的方法。方法。哈希表的定义：哈希表的定义：根据设定的根据设定的哈希函数哈希函数 H(key) 和所选用的和所选用的处理冲突的方法处理冲突的方法，将一组关键字，将一组关键字映象到映象到一一个有限的、地址连续的地址集个有限的、地址连续的地址集 (区间区间) 上，上，并以关键字在地址集中的并以关键字在地址集中的“映象映象”作为相作为相应记录在表中的应记录在表中的存储位置存储位置，如此构造所得，如此构造所得的查找表称之为的查找表称之为“哈希表哈希表”。关键字取值范围地址空间取值范围H(key)解决冲突的方法哈希表二、构造哈希函数的方法构造哈希函数的方法对于数字型关键字可以有下列构造方法：对于数字型关键字可以有下列构造方法：若是非数字型关键字，则需先对其进若是非数字型关键字，则需先对其进行数字化处理。行数字化处理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数法除留余数法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法哈希函数为关键字的线性函数哈希函数为关键字的线性函数 H(key) = key 或者或者 H(key) = a key + b1. 直接定址法直接定址法此此方法仅适用于：方法仅适用于：地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小此方法仅适用于：此方法仅适用于：能预先估计出全部关键字在每一位上出现能预先估计出全部关键字在每一位上出现各种数字的频度。各种数字的频度。2. 数字分析法数字分析法假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由 s 位数字组成位数字组成 (u1, u2, , us)，分析关键字分析关键字集的特点，集的特点，从中提取出分布均匀的若干位从中提取出分布均匀的若干位或或它们的组合它们的组合作为地址。作为地址。以以关键字的平方值的中间几位关键字的平方值的中间几位作为存作为存储地址。求储地址。求“关键字的平方值关键字的平方值” 的目的目的是的是“扩大差距扩大差距” ，而且平方值的中，而且平方值的中间各位又能受到关键字的各位约束。间各位又能受到关键字的各位约束。3. 平方取中法平方取中法 此方法适用于此方法适用于: 关键字中的每一位都有某些数字重复关键字中的每一位都有某些数字重复出现频度很高的现象。出现频度很高的现象。 将关键字分割成若干部分，然后取它将关键字分割成若干部分，然后取它们的叠加和为哈希地址。们的叠加和为哈希地址。有两种叠加有两种叠加处理的方法：移位和折叠。处理的方法：移位和折叠。4. 折叠法折叠法 此方法适用于此方法适用于: 关键字的数字位数特别多。关键字的数字位数特别多。 设定哈希函数为设定哈希函数为: H(key) = key MOD p 其中其中， pm ( (表长表长) ) 并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以下的质因子以下的质因子5. 除留余数法除留余数法6.随机数法随机数法设定哈希函数为设定哈希函数为: H(key) = Random(key)其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法适用于关键字长度不通常，此方法适用于关键字长度不等的情况。等的情况。在构造哈希表时，采用何种哈希函在构造哈希表时，采用何种哈希函数将取决于关键字集合的特征情况数将取决于关键字集合的特征情况(包括关键字的范围和形态包括关键字的范围和形态)，总的，总的原则是原则是降低产生冲突的机会降低产生冲突的机会。三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突” 的实际含义是：的实际含义是：为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。1. 开放定址法开放定址法3. 链地址法链地址法2. 再哈希法再哈希法4. 建立一个公共溢出区建立一个公共溢出区为冲突的地址为冲突的地址 H(key)设计一个设计一个地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1其中：其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s1. 开放定址法开放定址法对增量对增量 di 有三种取法：有三种取法： 1) 线性探测再散列线性探测再散列 di = c i 最简单的情况 c=1 2) 二次探测再散列二次探测再散列 di = 12, -12, 22, -22, , 3) 伪随机探测再散列伪随机探测再散列 di 是一组伪随机数列伪随机数列 或者 di=iH2(key) (又称双散列函数探测又称双散列函数探测)例如例如: 关键字集合 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 12.2.再哈希法再哈希法 Hi=RHi(key) i=1,2,.,k 其中，其中， RHi是是一系列不同的哈希函一系列不同的哈希函数。当产生冲突时，选用另一个哈数。当产生冲突时，选用另一个哈希函数计算另一个哈希地址，直到希函数计算另一个哈希地址，直到不冲突为止。不冲突为止。将所有哈希地址相同的记录都链接在同一链表中。 3. 链地址法链地址法0123456140136198223116855 ASL=(61+22+3)/9=13/9例如例如:同前例的关键同前例的关键字，哈希函数为字，哈希函数为 H(key)=key MOD 7查找过程和造表过程一致。假设采用开查找过程和造表过程一致。假设采用开放定址处理冲突，则放定址处理冲突，则查找过程查找过程为：为： 四、哈希表的查找四、哈希表的查找 对于给定值 K， 计算哈希地址 i = H(K)若若 ri = NULL 则查找不成功则查找不成功若若 ri.key = K 则查找成功则查找成功否则否则 “求下一地址求下一地址 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/- 开放定址哈希表的存储结构开放定址哈希表的存储结构 -Status SearchHash (HashTable H, KeyType 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) c = 0; if ( HashSearch ( H, e.key, p, c ) = SUCCESS ) return DUPLICATE; / 表中已有与表中已有与 e 有相同关键字的元素有相同关键字的元素 else if ( c hashsizeH.sizeindex/2 ) / 冲突次数冲突次数 c 未达到上限，（阀值未达到上限，（阀值 c 可调）可调） H.elemp = e; +H.count; return OK; else RecreateHashTable(H); / 重建哈希重建哈希表表/InsertHash n1) 选用的选用的哈希函数哈希函数；n2) 选用的选用的处理冲突的方法处理冲突的方法；n3) 哈希表饱和程度的哈希表饱和程度的装载因子装载因子 =n/m 值的值的大小大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找的决定哈希表查找的ASL的因素的因素：哈希表查找的分析哈希表查找的分析: :从查找过程得知，哈希表查找的平均查从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。找长度实际上并不等于零。一般情况下，可以认为选用的哈希函数是一般情况下，可以认为选用的哈希函数是“均匀均匀”的，则在讨论的，则在讨论ASL时，可以不考虑时，可以不考虑它的因素。它的因素。因此，因此，哈希表的哈希表的ASL是是处理冲突方法处理冲突方法和和装装载因子载因子的函数。的函数。例如：前述例子例如：前述例子线性探测处理冲突时，线性探测处理冲突时， ASL =ASL =二次探测处理冲突时，二次探测处理冲突时， ASL =ASL =链地址法处理冲突时，链地址法处理冲突时， ASL =ASL =22/914/913/9线性探测再散列链地址法随机探测再散列可以证明：可以证明：查找成功查找成功时有下列结果：时有下列结果：从以上结果可见：从以上结果可见： 哈希表的平均查找长度是哈希表的平均查找长度是 的函数的函数，而，而不是不是 n 的函数。的函数。这说明，用哈希表构造查找表时，可以这说明，用哈希表构造查找表时，可以选择一个适当的装填因子选择一个适当的装填因子 ，使得，使得平均平均查找长度限定在某个范围内查找长度限定在某个范围内。 这是哈希表所特有的特点。这是哈希表所特有的特点。 从哈希表中删除记录时，要作特殊处理特殊处理，相应地，需要修改查找的算法。五、哈希表的删除操作哈希表的删除操作第9章作业9.19.59.99.199.219.189.259.269.319.32第9章上机作业 对对任意给定的字符串序列，创建二任意给定的字符串序列，创建二叉排序树，并对其进行中序遍历。叉排序树，并对其进行中序遍历。 假设每个字符串代表一个英文单词。假设每个字符串代表一个英文单词。