数据结构第九章查找

19.1基本概念9.2静态查找表9.3动态查找表9.4哈希表9.5B-树和B+树第九章查找教材第8、11和12章省略，因《操作系统》课程会涉及。2数据结构课程的内容39.1基本概念查找表——由同一类型的数据元素（或记录）构成的集合

查找——查询(Searching)特定元素是否在表中。查找成功——若表中存在特定元素，称查找成功，应输出该记录；查找不成功——否则，称查找不成功（也应输出失败标志或失败位置）是一种数据结构49.1基本概念静态查找动态查找关键字主关键字——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录

(预先确定的记录的某种标志)——可以唯一标识一个记录的关键字例如“学号”例如“女”次关键字——识别若干记录的关键字5讨论2：对查找表常用的操作有哪些？

查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。

讨论讨论1：查找的过程是怎样的？

给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。“特定的”=关键字6讨论3：有哪些查找方法？查找方法取决于表中数据的排列方式;讨论：例如查字典针对静态查找表和动态查找表的查找方法也有所不同。7讨论4：如何评估查找方法的优劣？明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL。其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。统计意义上的数学期望值物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。AverageSearchLength8针对静态查找表的查找算法主要有：9.2静态查找表一、顺序查找（线性查找）二、折半查找（二分或对分查找）（重点与考点）三、分块查找（索引顺序查找）（第三种物理结构）四、静态树表的查找9静态查找表的定义（抽象数据类型）ADTStaticSearchTable{数据对象D:数据关系R：基本操作P：}ADTStaticSearchTable参见教材P2169.2静态查找表109.2.1顺序查找（又称线性查找）顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？对单链表结构如何线性查找？对非线性树结构如何顺序查找?见下页之例或教材P216从头指针始“顺藤摸瓜”借助各种遍历操作！111顺序表的存储结构(动态数组）typedefstruct{ElemType*elem;

//表基址，0号单元留空。表容量为全部元素

intlength;//表长，即表中数据元素个数

}SSTable;9.2.1顺序查找（又称线性查找）122算法的实现技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。例：若将待查找的特定值key存入顺序表的首部（如0号单元），并从后向前逐个比较,就不必担心“查不到”。9.2.1顺序查找（又称线性查找）13intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0].key=key;

for(i=ST.length;ST.elem[i].key!=key;--i);

returni;}//Search_Seq2算法的实现//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。//找不到=不成功，返回值必为i=0；找得到=成功，返回值i正好代表所找元素的位置。//不要用for(i=1;i<=n;i++)

或for(i=n;i>0;--i)9.2.1顺序查找（又称线性查找）14讨论1：查找失败怎么办？——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束，并返回i=0。讨论2：查找效率怎样计算？——用平均查找长度ASL衡量。4算法分析讨论9.2.1顺序查找（又称线性查找）154算法分析讨论讨论3：如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n=(1+n)n/2未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1这是查找成功的情况若求某一个元素的平均查找次数，还应当除以n（等概率），即：ASL＝（1＋n）/2，时间效率为O(n)9.2.1顺序查找（又称线性查找）16优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL太大，时间效率太低。5顺序查找的特点：9.2.1顺序查找（又称线性查找）179.2.2、折半查找（二分查找）这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。181、存储结构对顺序表结构如何编程实现折半查找算法？

——见下页之例，或见教材（P219）对单链表结构如何折半查找？

——无法实现！因全部元素的定位只能从头指针head开始对非线性(树)结构如何折半查找？

——可借助二叉排序树来查找（属动态查找表形式）。9.2.2、折半查找（二分查找）19解：①先设定3个辅助标志:low,high,mid，显然有：mid=(low+high)/2折半查找举例：已知如下11个元素的有序表：Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置（0513192137566475808892）,请查找关键字为21

和85的数据元素。9.2.2、折半查找（二分查找）20②运算步骤：(1)low=1,high=11,故mid=6，待查范围是[1,11]；(2)若ST.elem[mid].key<key，说明key[mid+1,high]，则令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>key，说明key[low,mid-1]，则令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high<low（意即区间长度小于0）9.2.2、折半查找（二分查找）219.2.2、折半查找（二分查找）22讨论1：若关键字不在表中，怎样得知并及时停止查找？——典型标志是：当查找范围的上界<下界时停止查找。讨论2：如何计算二分查找的时间效率（ASL）？问题讨论9.2.2、折半查找（二分查找）23经1次比较就查找成功的元素有1个（20），即中间值；经2次比较就查找成功的元素有2个（21），即1/4处和3/4处；3次比较就查找成功的元素有4个（22），即1/8，3/8，5/8，7/8处4次比较就查找成功的元素有8个（23），即1/16处，3/16处…………则第m次比较时查找成功的元素应该有（2m-1）个。全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1

＝推导过程注：为方便起见，假设表中全部n个元素刚好是2m-1个，此时暂不讨论第m次比较后还有剩余元素的情况。9.2.2、折半查找（二分查找）24请注意：ASL的含义是“平均每个数据的查找时间”，而前式是n个数据查找时间的总和，所以：（详细推导过程见教材P221的附录1）推导过程9.2.2、折半查找（二分查找）25练习题课堂练习1（多选题）使用折半查找算法时，要求被查文件：Ａ．采用链式存贮结构Ｂ．记录的长度≤12Ｃ．采用顺序存贮结构Ｄ．记录按关键字递增有序课堂练习2在有序线性表a[20]上进行折半查找，则平均查找长度为

。√√3.79.2.2、折半查找（二分查找）26找到有序表中任一记录的过程就是：走了一条从根结点到与该记录对应结点的路径。比较的关键字个数为：该结点在判定树上的层次数。查找成功时比较的关键字个数最多不超过树的深度d:d=log2n+1查找不成功的过程就是：走了一条从根结点到外部结点的路径。查找不成功最多比较次数也为d再用二分查找树来分析ASL(参见教材P220）以（a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11）为例：a6a3a9判定树由表中元素个数决定，且n个元素表的折半查找判定树是唯一的。a1a10a7a4a11a8a2a527分块查找（索引顺序查找）讨论：对顺序查找除了折半改进法外，还有无其他改进算法？有，例如分块查找法。顺序查找其它改进算法289.2.3分块查找（索引顺序查找）思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。2448605874491312920334244388653822例：特点：块间有序，块内无序29分块查找过程举例：索引表块内最大关键字各块起始地址2212138920334244382448605874498653第1块第2块第3块2248861713特点：块间有序，块内无序查找：块间折半，块内线性9.2.3分块查找（索引顺序查找）30查找步骤分两步进行：①对索引表使用折半查找法（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；9.2.3分块查找（索引顺序查找）31查找效率ASL分析对索引表查找的ASL对块内查找的ASLS为每块内部的记录个数，n/s即块的数目例如：当n=9，s=3时

分块法的ASLbs=3.5折半法的ASL≈log2n=3.1

顺序法的ASL=(1＋n)/2=5ASL=Lb+Lw但折半法要预先全排序，仍需时间。9.2.3分块查找（索引顺序查找）讨论：当有序表中各记录的查找概率不相等时，该如何查找？提醒：此时用折半查找法未必最优！（参见教材P222例）改进：若将各记录的概率看作是二叉树之权值，则转为研究带权路径长度最小的二叉树（类似最优二叉树）。

静态最优查找树算法——时间代价高；实用算法：次优查找树9.2.4静态树表查找33CBDAE(a)BADCE(b)3E29D2301CBA例：有序表

对应权值算法详见教材P222—225不合理较合理9.2.4静态树表查找349.3动态查找表特点：表结构在查找过程中动态生成。要求：对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回；否则插入关键字等于key的记录。典型的动态表———二叉排序树35一、二叉排序树的定义二、二叉排序树的插入与删除三、二叉排序树的查找分析四、平衡二叉树(难点）9.3动态查找表典型的动态表———二叉排序树369.3.1

二叉排序树的定义或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。37例：下列2种图形中，哪个不是二叉排序树？（a）（b）想一想：对它中序遍历之后是什么效果？74110265398510216473989.3.1二叉排序树的定义384524531290查找成功，返回查找成功，返回例：输入待查找的关键字序列=（45，24，53，45，12，24，90）查找不成功则插入树中9.3.2、二叉排序树的插入与删除39如果改变输入顺序为（24，53，45，45，12，24，90），查找成功，返回查找成功，返回则生成的二叉排序树形态不同2453451290这种既查找又插入的过程称为动态查找9.3.2、二叉排序树的插入与删除40①查找过程与顺序结构有序表中的折半查找相似，查找效率高；②中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；③如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。将线性表构造成二叉排序树的优点9.3.2、二叉排序树的插入与删除411二叉排序树的查找&插入算法如何实现？思路：查找不成功，生成一个新结点s，插入到二叉排序树中；查找成功则返回。SearchBST(K,&t){//K为待查关键字，t为根结点指针

p=t;//p为查找过程中进行扫描的指针

while（p!=NULL）{case{K=p->data:{查找成功，return}

K<p->data:{q=p；p=p->L_child}//继续向左搜索

K>p->data:{q=p；p=p->R_child}//继续向右搜索

}

}//查找不成功则插入到二叉排序树中程序：9.3.2、二叉排序树的插入与删除42s=(BiTree)malloc(sizeof(BiTNode));s->data=K;s->L_child=NULL;s->R_child=NULL;

//查找不成功，生成一个新结点s，插入到二叉排序树叶子处case{

t=NULL：t=s;//若t为空，则插入的结点s作为根结点K<q->data:q->L_child=s;//若K比叶子小，挂左边K>q->data:q->R_child=s;//若K比叶子大，挂右边

}

returnOK}以上为查找、插入二合一的非递归程序该模块就是“建树”的非递归算法！9.3.2、二叉排序树的插入与删除43插入模块（非递归方式）参见教材P228算法9.5（b）;查找模块参见教材P228算法9.5（a）;该模块就是“建树”的非递归算法！9.3.2、二叉排序树的插入与删除对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，要求删除后仍需保持二叉排序树的特性。2二叉排序树的删除操作如何实现？如何删除一个结点？假设：*p表示被删结点的指针；PL和PR分别表示*P的左、右孩子指针；*f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况：9.3.2、二叉排序树的插入与删除45*p为叶子：删除此结点时，直接修改*f指针域即可；*p只有一棵子树（或左或右）：令PL或PR为*f的左孩子即可；*p有两棵子树：情况最复杂→fpPLPR9.3.2、二叉排序树的插入与删除2二叉排序树的删除操作如何实现？46分析：设删除前的中序遍历序列为：….PLspPRf….//显然p的直接前驱是s//s是p左子树最右下方的结点希望删除p后，其它元素的相对位置不变。有两种解决方法：法1：令p的左子树为f的左子树，p的右子树接为s的右子树；//即fL=PL;SR=PR;法2：直接令s代替p//s为p左子树最右下方的结点难点：*p有两棵子树时，如何进行删除操作？fpPLPRs9.3.2、二叉排序树的插入与删除47FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:例：请从下面的二叉排序树中删除结点P。SSL9.3.2、二叉排序树的插入与删除481二叉排序树上查找某关键字等于结点值的过程，其实就是走了一条从根到该结点的路径。比较的关键字次数＝此结点的层次数;

最多的比较次数＝树的深度（或高度），即log2n+19.3.3二叉排序树的查找分析49其中：ni是每层结点个数；

Ci是结点所在层次数；m为树深。最坏情况：插入的n个元素从一开始就有序（单调增或减），

——变成了单支树的形态！此时树的深度为n;ASL=(n+1)/2与线性查找的ASL相同！2一棵二叉排序树的平均查找长度为：9.3.3二叉排序树的查找分析50最坏情况：即插入的n个元素从一开始就有序。（单支树）此时树深为n;ASL=(n+1)/2;与顺序查找情况相同。最好情况：即：与折半查找中的判定树相同（形态均衡）此时树深为：log2n+1；ASL=log2(n+1)–1；与折半查找情况相同。一般情况：（与logn同阶）思考：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡平衡二叉树9.3.3二叉排序树的查找分析9.3.4二叉排序树操作代码5152(a)平衡树(b)不平衡树平衡二叉树的特点： 任一结点的平衡因子只能取：-1、0或1。对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。例：判断下列二叉树是否AVL树？00011-1-120001-19.3.4平衡二叉树53如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。9.3.4平衡二叉树54现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：

LL平衡旋转

RR平衡旋转

LR平衡旋转

RL平衡旋转9.3.4平衡二叉树55若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。ABCABC1）LL平衡旋转以B为旋转轴9.3.4平衡二叉树56若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。2）RR平衡旋转ABCABC以B为旋转轴9.3.4平衡二叉树57ABC若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。3）LR平衡旋转ABC以插入的结点C为旋转轴ABC9.3.4平衡二叉树58若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。4）RL平衡旋转ABCABCABC这种调整规则可以保证二叉排序树的次序不变以插入的结点C为旋转轴9.3.4平衡二叉树59013037024例：请将下面序列构成一棵平衡二叉排序树013037-113024-124-213需要RR平衡旋转(绕B逆转,B为根）090-124-137053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053

（13，24，37，90，53）建立平衡二叉树旋转注意要点1、首先确定属于何种类型的旋转；2、确定旋转轴LL和RR型的旋转轴在沿着失衡路径上，以失去平衡点的直接后继结点作为旋转轴；LR和RL的旋转轴是沿着失衡路径上，失去平衡点的后两层结点作为旋转轴。60619.4哈希查找表一、哈希表的概念二、哈希函数的构造方法三、冲突处理方法四、哈希表的查找及分析629.4.1哈希表的概念哈希表：即散列存储结构（第四种物理结构，用于快速查找）。散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。优点：查找速度极快（O(1)）,查找效率与元素个数n无关！639.4.1哈希表的概念例1：若将学生信息按如下方式存入计算机，如：将2001011810201的所有信息存入V[01]单元；将2001011810202的所有信息存入V[02]单元；……将2001011810231的所有信息存入V[31]单元。欲查找学号为2001011810216的信息，便可直接访问V[16]！64例2：

有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。解：根据散列函数H（k）＝k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，对应散列存储表（哈希表）如下：地址…9…11…14…232425…39…内(k)称为散列函数9.4.1哈希表的概念65根据存储时用到的散列函数H(k)表达式，迅即可查到结果！例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。明显缺点：空间效率低如何解决？讨论：如何进行散列查找？9.4.1哈希表的概念66选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。Hash查找专业术语哈希方法(杂凑法)哈希方法中使用的转换函数称为哈希函数(杂凑函数)按上述思想构造的表称为哈希表(杂凑表)哈希表(杂凑表)哈希函数(杂凑函数)67通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。Hash查找专业术语冲突68有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=kmod7通过哈希函数对6个元素建立哈希表：253923914冲突现象举例：6个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有冲突！01234569.4.1哈希表的概念69所以，哈希方法必须解决以下两个问题：1）构造好的哈希函数（a）所选函数尽可能简单，以便提高转换速度；（b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。9.4.1哈希表的概念709.4.2

哈希函数的构造方法要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。719.4.2

哈希函数的构造方法常用的哈希函数构造方法有：直接定址法除留余数法乘余取整法数字分析法平方取中法折叠法随机数法72Hash(key)=a·key+b(a、b为常数)优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。

例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：01234567899008007005003001001、直接定址法9.4.2

哈希函数的构造方法73Hash(key)=keymodp(p是一个整数)特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取p≤m且为质数（也可以是合数，但不能包含小于20的质因子）。2、除留余数法（重点)9.4.2

哈希函数的构造方法74Hash(key)=B*(A*keymod1)

(A、B均为常数，且0<A<1，B为整数)特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。3、乘余取整法（A*keymod1）就是取A*key的小数部分例：欲以学号最后两位作为地址，则哈希函数应为：

H(k)=100*(0.01*k%1)其实也可以用法2实现：H(k)=k%1009.4.2

哈希函数的构造方法75特点：选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。34705243491487348269634852703486305349805834796713473919例：有一组（例如80个）关键码，其样式如下：4、数字分析法讨论：①第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号：①②③④⑤⑥⑦②若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。9.4.2

哈希函数的构造方法76特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。理由：因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。5、平方取中法9.4.2

哈希函数的构造方法776、折叠法特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为地址。适用于：每一位上各符号出现概率大致相同的情况。法1：移位法──将各部分的最后一位对齐相加。法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。例：元素42751896,用法1：427＋518＋96=1041

用法2：42751896—>724+518+69=13119.4.2

哈希函数的构造方法787、随机数法Hash(key)=random(key)(random为伪随机函数)适用于：关键字长度不等的情况。造表和查找都很方便。9.4.2

哈希函数的构造方法79①执行速度（即计算哈希函数所需时间）；②关键字的长度；③哈希表的大小；④关键字的分布情况；⑤查找频率。小结：构造哈希函数的原则：9.4.2

哈希函数的构造方法809.4.3、冲突处理方法（重点与考点）常见的冲突处理方法有开放定址法（开地址法）链地址法（拉链法）再哈希法（双哈希函数法）建立一个公共溢出区811、开放定址法（开地址法）设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。821、开放定址法（开地址法）Hi=(Hash(key)+di)modm(1≤i<m)

其中：

Hash(key)为哈希函数

m为哈希表长度

di

为增量序列1，2，…m-1，且di=i

（1）线性探测法含义：一旦冲突，就找附近（下一个）空地址存入。83关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=keymod11；拟用线性探测法处理冲突。建哈希表如下：解释：①47、7是由哈希函数得到的没有冲突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8为空，因此将29存入。③另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。其中3还连续移动了两次（二次聚集）84线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。1、开放定址法（开地址法）

（1）线性探测法85仍举上例，改用二次探测法处理冲突，建表如下：012345678910112234792167298△▲△△注：只有3这个关键码的冲突处理与上例不同，Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)+12)mod11=4，仍然冲突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。（2）二次探测法Hi=(Hash(key)±di)modm其中：Hash(key)为哈希函数

m为哈希表长度，m要求是某个4k+3的质数；

di为增量序列12，-12，22，-22，…，q2

1、开放定址法（开地址法）862、链地址法(拉链法）基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。872、链地址法(拉链法）

设{47,7,29,11,16,92,22,8,3,50,37,89,10}的哈希函数为：Hash(key)=keymod11，用拉链法处理冲突，则建表如右图所示。例：

01234567891022118934737922971650810有冲突的元素可以插在表尾,也可以插在表头。883、再哈希法（双哈希函数法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。优点：不易产生聚集；缺点：增加了计算时间。894.建立一个公共溢出区思路：除设立哈希基本表外，另设立一个溢出向量表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。909.4.4哈希表的查找及分析明确：散列函数没有“万能”通式（杂凑法），要根据元素集合的特性而分别构造。算法：见教材P2591：哈希查找的速度是否为真正的O（1）？答：不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。919.4.4哈希表的查找及分析2：“冲突”是不是特别讨厌？答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。典型应用：md5散列算法哈希表特点：源文件稍稍改动，会导致哈希表变动很大。923散列存储的查找效率到底是多少？答：ASL与装填因子有关！既不是严格的O(1)，也不是O(n)应尽量选择一个合适的，以降低ASL的长度9.4.4哈希表的查找及分析9.4.5哈希应用93HASH函数，又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，它有一种类似于指纹的应用。

在网络安全协议中，杂凑函数用来处理电子签名，将冗长的签名文件压缩为一段独特的数字信息，像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。

1、数字签名（数字手印）9.4.5哈希应用94

SHA-1和MD5都是目前最常用的杂凑函数。经过这些算法的处理，原始信息即使只更动一个字母，对应的压缩信息也会变为截然不同的“指纹”，这就保证了经过处理信息的唯一性。为电子商务等提供了数字认证的可能性。1、数字签名（数字手印）95md5散列算法——信息-摘要算法（1991年）md5的典型应用是对一段信息（message）产生一个128位的信息摘要（message-digest），以防止被篡改。md5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位(链接变量参数)分组组成，将这四个32位分组级联后将生成一个128位散列值。message-digestalgorithm）——用于加解密和数字签名9.4.5哈希应用96例1：在unix系统下，有很多软件在下载的时候都有一个文件名相同、文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：

md5(file)=0ca175b9c0f726a831d895e269332461这就是file文件的数字签名。9.4.5哈希应用97例2：md5用于BBS登录时的身份认证在BBS服务器上，用户的密码都是以md5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成md5值，然后再去和预存在服务器中的md5值进行比较，进而确定输入的密码是否正确。优点：系统在不知用户密码明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。9.4.5哈希应用98例3：单纯的数据校验下载光盘镜像文件时一般会有一个MD5文件记录校验和，以防止下载600MB的文件出现错误导致软件无法安装，这在Linux/FreeBSD等通过网络发布的光盘安装系统中常用。9.4.5哈希应用99现在使用的重要计算机安全协议，如SSL，PGP都用杂凑函数来进行签名。但是，如果有人一旦找到两个文件可以产生相同的压缩值，就可以伪造签名，给网络安全领域带来巨大隐患。

9.4.5哈希应用9.5B-树和B+树1、B-树2B+树9.5.1B-树

一B-树的定义B-树是一种平衡的多路查找树。一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：

1．树中每个结点至多有m棵子树，m-1个关键字；

2．若根结点不是叶子结点，则至少有两棵子树；

3．除根之外的所有非终端结点至少有棵子树，至少有-1个关键字；4．所有的非终端结点中包含下列信息数据：

(n,A0,K1,A1,K2,A2,…,Kn,An)其中：Ki(i=1,…,n)为关键字，且Ki<Ki+1(i=1,…,n-1)；

Ai(i=1,…,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1,…,n)，An所指子树中所有结点的关键字均大于Kn，n

为关键字的个数（或n＋1为子树个数）。一、B-树的定义9.5.1B-树

5．所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。一、B-树的定义9.5.1B-树

二、图形表示图1 一棵4阶的B-树tabcfegdh135111243781181271391993475364FFFFFFFFFFFF结点中关键字个数为1<=n<=3

子树数量范围为2<=k<=49.5.1B-树

从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。三、查找

若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，则返回插入位置。9.5.1B-树

#define m 3 //B-树的阶，暂设为3typedefstructBTNode{ int keynum

//结点中关键字个数，即结点的大小

structBTNode*parent;//指向双亲结点

KeyType key[m+1];

//关键字向量，0号单元未用

structBTNode*ptr[m+1]; //子树指针向量

Record *recptr[m+1];

//记录指针向量，0号单元未用

}BTNode,*BTree;B-树结构体B-树查询结构体typedefstruct{ BTNode *pt; //指向找到的结点

int i; //1..m，在结点中的关键字序号

int tag; //1:查找成功，0:查找失败

}Result; //B-树的查找结果类型四、B-树的查找1．算法思想：在B-树上进行查找的过程是一个顺着指针查找结点和在结点的关键字中进行查找交叉进行的过程。9.5.1B-树

四、B-树的查找2．算法代码9.5.1B-树

3．查找分析从上述算法可见，在B-树上进行查找包含两种基本操作：a.在B-树中找结点（操作在磁盘上进行）；b.在结点中找关键字（操作在内存中进行）。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数、即待查关键字所在结点在B-树上的层次数，是决定B-树查找效率的首要因素。

9.5.1B-树

四、B-树的查找

根据B-树的定义，第一层至少有1个结点；第二层至少有2个结点；棵子树，则第三层至少有2()个结点；……；依次类推，第l＋1层至少有)l-1由于除根之外的每个非终端结点至少有2(个结点。而l＋1层的结点为叶子结点。若m阶B-树中具有N个关键字，则叶子结点即查找不成功的结点为N＋1，由此有：推得：3．查找分析9.5.1B-树

四、B-树的查找3．查找分析这就是说，在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过9.5.1B-树

四、B-树的查找五、B-树的插入2．算法思想：由于B-树结点中的关键字个数必须

。因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”。9.5.1B-树

五、B-树的插入

一般情况下，结点可如下实现“分裂”：假设p结点中已有m-1个关键字，当插入一个关键字之后，结点中含有信息为：m,A0,(K1,A1),…,(Km,Am)且其中Ki<Ki+1，1≤i<m，此时可将p结点分裂为p和p’两个结点，其中p结点中含有信息为：

9.5.1B-树

五、B-树的插入p’结点中含有信息：而关键字指针p’一起插入到p的双亲结点中。9.5.1B-树

3．例子例如，图2所示为3阶B-树（图中略去F结点，即叶子结点），假设需一次插入关键字30，26，85和7。(a) bta45b24c312d37f50h100g6170e5390图2一棵2-3树五、B-树的插入bta45b24c312df50h100g6170e53903037(b)五、B-树的插入bta45b24c312df50h100g6170e5390263037(c)五、B-树的插入bta45b2430c312df50h100g6170e53903726d’(d)五、B-树的插入bta45b2430c312df50h100g617085e53903726d’(e)五、B-树的插入(f)bta45b2430c312df50h100g61e5370903726d’85g’五、B-树的插入(g)bta4570b2430c312df50h100g61e533726d’85g’e’90五、B-树的插入(h)bta4570b72430c3df50h100g61e533726d’85g’e’9012c’五、B-树的插入bta244570b7c3df50h100g61e5326d’85g’e’9012c’30b’37(i)五、B-树的插入(j)bta70b7c3df50h100g61e5326d’85g’e’9012c’30b’ma’452437(a)一棵2-3树；(b)插入30之后；

(c)、(d)插入26之后；

(e)~(g) 插入85之后；(h)~(j)插入7之后；图2 在B-树中进行插入（省略叶子结点）五、B-树的插入

六、B-树的删除1．算法思想：在B-树中删除一个关键字，则首先应找到该关键字所在结点，并从中删除之。（1）若所删关键字为非终端结点中的Ki，则以指针Ai所指子树中的最小关键字Y替代Ki，然后在相应的结点中删去Y。（2）若所删关键字在最下层非终端结点中。有下列3种情况：a．被删关键字所在结点中的关键字数目不小于，则只需从该结点中删去该关键字Ki