(8)--lecture8数据结构数据结构.ppt

《(8)--lecture8数据结构数据结构.ppt》由会员分享，可在线阅读，更多相关《(8)--lecture8数据结构数据结构.ppt（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 查查找是使用广泛的技找是使用广泛的技术术，本章，本章强调强调以算法分析的以算法分析的结结论论来来审视审视各种各种查查找方法。找方法。查查找表有多种找表有多种类类型，也有着各异的型，也有着各异的查查找方法，找方法，对应对应着各自的使用范筹，将其运用到的恰当着各自的使用范筹，将其运用到的恰当场场合是学合是学习查习查找表的精髓。找表的精髓。哈希哈希查查找表在数据加密、金融服找表在数据加密、金融服务领务领域日益受到倚域日益受到倚重，是本章学重，是本章学习习的重点之一。的重点之一。讲讲授本章授本章课课程大程大约约需需4 4课时课时。第第9章章 查找找2v 查找表的基本概念找表的基本概念v 9.1 静

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

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

4、的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人人为地附加地附加某种确定的关系，换句话说，用另外一种用另外一种结构来表示构来表示查找表找表。如何如何进行行查找？找？查找的方法取决于找的方法取决于查找表的找表的结构。构。109.1 静静 态态 查查 找找 表表11 查找表具有相同特性的数据元素的集合。每个数据元素含有每个数据元素含有类型相型相同的关同的关键字字，可唯一标识数据元素。查找表找表的定的定义12Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST);静静态查找表找表的基本操作的基本操

5、作：13构造一个含n个数据元素的静态查找表ST。Create(&ST,n);操作结果：14销毁表ST。Destroy(&ST);初始条件：操作结果：静态查找表ST存在；15若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Search(ST,key);初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；16按某种次序输出ST中的每个数据元素。Traverse(ST);初始条件：操作结果：静态查找表ST已存在。17typedef struct /数据元素存储空间基址，建表时 /按实际长度分配，0号单元留空 i

6、nt length;/表的长度 SSTable;静静态查找表找表的的顺序存序存储结构：构：ElemType*elem;18数据元素数据元素类型型的定的定义为:typedef struct keyType key;/关键字域 /其它属性域 ElemType;,TElemType;19一、一、顺序序查找表找表二、有序二、有序查找表找表三、索引三、索引顺序表序表20 以顺序表或线性链表表示静态查找表一、顺序序查找表找表21ST.elemiST.elemi60ikey=64key=60i64从高端开始查找查找不成功，定位在0下标22int Search_Seq(SSTable ST,KeyType k

7、ey)/在顺序表ST中顺序查找其关键字等于 /key的数据元素。若找到，则函数值为 /该元素在表中的位置，否则为0。ST.elem0.key=key;/“哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找 return i;/找不到时，i为0/Search_Seq23 定定义：查找算法的平均平均查找找长度度ASL (Average Search Length)为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中:n 为表长，Pi 为查找表中第i个记录的概率，且 ，Ci为找到该记录时，曾和给定 值比较过的关键字的个数。分析顺序查找

8、的时间性能24在等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表序表而言，Ci=n-i+1ASL=nP1+(n-1)P2+2Pn-1+Pn25 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。二、有序二、有序查找表找表 若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。26ST.elemST.length例如例如:key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/227int Search_Bin(SSTable ST,K

9、eyType key)low=1;high=ST.length;/置区间初值 while(low=high)mid=(low+high)/2;if（key=ST.elemmid.key)return mid;/找到待查元素 else if(key 50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。30三、索引顺序表三、索引顺序表索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。31 注意：索引可以根据查找表的特点来构造。索引顺序查找的过程也是一个“缩小区间”的查找过程。32索引顺序查找的平均查找长度

10、=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度33分分块查找找ASLbs=Lb+Lw349.2 动动 态态 查查 找找 表表35InitDSTable(&DT)动态查找表找表的基本操作的基本操作：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT);36操作结果：构造一个空的动态查找表DT。InitDSTable(&DT);37销毁动态查找表DT。DestroyDSTable(&DT);初始条件：操作结果：动态查找表DT存在；38

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

12、verseDSTable(DT)初始条件：操作结果：按某种次序输出ST中的每个数据元素。42(n)(1)(n)(1)(nlogn)综合上一合上一节讨论的几种的几种查找表的特性：找表的特性：查找找 插入插入 删除除无序顺序表 无序线性链表有序顺序表 有序线性链表 静态查找树表(n)(n)(logn)(n)(logn)(1)(1)(n)(1)(nlogn)431)从查找性能看，最好情况能达(logn)，此时要求表有序；2)从插入和删除的性能看，最好情况能达(1)，此时要求存储结构是链表。可得如下可得如下结论：动态查找表找表可以可以综合以上两点，构建合以上两点，构建自己的自己的结构。构。44一、二叉

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

14、Node,*BiTree;TElemType data;48一、二叉排序一、二叉排序树（二叉（二叉查找找树）1查找算法找算法2插入算法插入算法3删除算法除算法4查找性能的分析找性能的分析491.二叉排序树的查找算法二叉排序树的查找算法1）若）若给定定值等于根根结点的关点的关键字，字，则查找 成功；2）若）若给定定值小于根根结点的关点的关键字，字，则继续 在左子树上进行查找；3）若）若给定定值大于根根结点的关点的关键字，字，则继续 在右子树上进行查找。若二叉排序树为空空，则查找不成功找不成功；否则，5050308020908540358832例如例如:二叉排序二叉排序树查找关找关键字字=50,5

15、05035,503040355090,5080909551从上述查找过程可见，在查找过程中，生成了一条查找路径找路径：从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。查找成功找成功 查找不成功找不成功52bool Search_BST(BiTree T,KeyType kval,BiTree&p,BiTree&f)/无论查找成功与否，f 总是指向 T 所指结点的双亲，/其初始调用值为NULL p=T;/p 指向树中某个结点，f指向其双亲结点 while(p)if(kval=p-data.key)return

16、 TRUE;/查找成功 else if(kval data.key)f=p;p=p-lchild;/在左子树中继续查找 else f=p;p=p-rchild;/在右子树中继续查找 /while return FALSE;/查找不成功/SearchBST53v 根据根据动态查找表的定找表的定义，“插入”操作在 查找不成功时才进行；2.二叉排序树的插入算法二叉排序树的插入算法v 若二叉排序若二叉排序树为空树，则新插入的新插入的结点点为 新的根结点；否；否则，新插入的，新插入的结点必点必为一一 个个新的叶子结点，其，其插入位置由由查找找过程程 得到。得到。5430201040352523fT设 k

17、ey=48fTfT22fTfTTTTfff注意：注意：f 总是指向遍历指针结点的双亲 将为插入和删除操作确定具体位置 查找不到的情况：找不到的情况：55bool Insert_BST(BiTree&T,ElemType e)/当二叉查找树中不存在关键字等于e.key的数据元素时，/插入e并返回TRUE，否则不再插入并返回FALSE f=NULL;if(Search_BST(T,e.key,p,f)return FALSE;/树中已有关键字相同的结点，不再插入 else /查找不成功，插入结点 s=new BiTNode;s-data=e;s-lchild=s-rchild=NULL;if(!f

18、)T=s;/空树时，插入的s 结点为新的根结点 else if(e.key data.key)f-lchild=s;/插入 s 结点为左孩子 else f-rchild=s;/插入 s 结点为右孩子 return TRUE;/else/Insert_BST561.被删除的结点是叶子；2.被删除的结点只有左子树或者只有右子树；3.被删除的结点既有左子树，也有右子树。3二叉排序二叉排序树的的删除算法除算法可分三种情况讨论：和插入相反，删除在查找成功找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序仍然保持二叉排序树的特性的特性。5750308020908540358832（1

19、）被删除的结点是叶子叶子结点点例如例如:被被删关关键字字=2088其双亲结点中相应指针域的值改为“空空”5850308020908540358832（2）被删除的结点只有左子只有左子树或者只有右子只有右子树 其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。被被删关关键字字=40805950308020908540358832（3）被）被删除的除的结点点既有左子既有左子树，也有右子，也有右子树4040以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被被删关关键字字=5060void Delete_BST(BiTree&T,KeyType kval)/若二叉查找树T中存在 /

20、关键字等于kval的数据元素，则删除之。f=NULL;if(Search_BST(T,kval,p,f)/找到其关键字等于kval的数据元素 左、右子树均不空，找p的前驱再改动链接;右子树空，只需挂接它的左子树;左子树空，只需挂接它的右子树;/将指针p所指子树挂接到 /被删结点的双亲结点f Status DeleteBST(BiTree&T,KeyType key)/若二叉排序若二叉排序树 T 中存在其关中存在其关键字等于字等于 key 的的 /数据元素，数据元素，则删除除该数据元素数据元素结点，并返回点，并返回 /函数函数值 TRUE，否，否则返回函数返回函数值 FALSE if(!T)re

21、turn 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

22、)else /Delete其中删除操作除操作过程如下所描述：/右子树为空树则只需重接它的左子树q=p;p=p-lchild;free(q);pp/左子树为空树只需重接它的右子树q=p;p=p-rchild;free(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的左子树free(s);pqs674查找性能的分析找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找

23、长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。68由关键字序列 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.269 假设 n 个关键字可能出现的 n!种排列的可能性相同,在等概率查找的情况下，可以分析求得：70二、二叉平衡树二、二叉平衡树 二叉平衡二叉平衡树 是二叉二叉查找找树的另一种形式 树中每个中每个结点的点的左、右子左、右子树深度深

24、度之差的之差的绝对值不大于不大于1,即：即：二叉平衡二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个中每个结点的点的左、右子左、右子树深度深度之差的之差的绝对值不大于不大于1 。例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树72例如例如:不是平衡不是平衡树是平衡是平衡树由关键字 1,2,3,4,5 可形成的二叉查找树24531341527374 构造二叉平衡（查找）树的方法是：在插入在插入过程中，采用平衡旋程中，采用平衡旋转技技术。例如:依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转426589642895向左旋转一次

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

26、Nh-2+1利用利用归纳法可法可证得，得，Nh=Fh+2-1 因此，在二叉平衡二叉平衡树上进行查找时，查找过程中和给定值进行比行比较的关的关键字字的个数和的个数和 log(n)相当。由此推得，深度深度为 h 的二叉平衡二叉平衡树中所含含结点的最小点的最小值 Nh=h+2/5-1 反之，含有含有 n 个个结点的二叉平衡点的二叉平衡树能能达到的最大深度达到的最大深度 hn=log(5(n+1)-2 81三、三、键 树1.键树的结构特点键树的结构特点2.双链树双链树821.键树的结构特点：键树的结构特点：v 关键字中的各个符号分布在从根结点到叶的路径上，叶结点内的符号为“结束”的标志符。因此，键树的

27、深度和关的深度和关键字集合的大字集合的大小无关小无关。v 键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符$小于任何其它符号。83HAD$S$VE$E$R$E$IGH$S$例如例如:表示关键字集合：HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS 842.双链树双链树 以二叉链表作存储结构实现的键树typedef enum LEAF,BRANCH NodeKind;/两种结点：叶子叶子 和和 分支分支结点点结构构:first symbol next分支分支结点点infoptr symbol next叶子叶子结点点指向孩子结点的指针指向兄弟结

28、点的指针指向记录的指针85 H AD$HADE$R$ES$GH$I HEHERHEREHIGHHIST 叶子叶子结点点分支分支结点点含关含关键字字的的记录86typedef struct DLTNode char symbol;struct DLTNode *next;/指向兄弟结点的指针 NodeKind kind;union Record *infoptr;/叶子结点内的记录指针 struct DLTNode *first;/分支结点内的孩子链指针 DLTNode,*DLTree;/双链树的类型87#define MAXKEYLEN 16 /关键字的最大长度typedef struct c

29、har chMAXKEYLEN;/关键字 int num;/关键字长度 KeysType;/关键字类型88在双在双链树中中查找找记录的的过程程:假设:T 为指向双链树根结点的指针，K.ch0.K.num-1 为待查关键字 (给定值)。则查找过程中的基本操作为进行下列比较:K.chi=?p-symbol 其中:p 指向双链树中某个结点，0 i K.num-189 H AD$HADE$R$ES$GH$I HEHERHEREHIGHHIST K.chHERE查找找过程程实例例90初始状态:p=T-first;i=0;若(p&p-symbol=K.chi&ifirst;i+;若(p&p-symbol!

30、=K.chi)则继续在键树的同一层上进行查找 p=p-next;若 (p&p-symbol=K.chi&i=K.num-1)则 查找成功，返回指向相应记录的指针 p-infoptr 若(p=NULL)则表明查找不成功，返回“空指针”;919.3 哈希表及其查找哈希表及其查找92 一、哈希表是什么？一、哈希表是什么？二、构造哈希函数的几种方法二、构造哈希函数的几种方法 三、处理冲突的方法和建表示例三、处理冲突的方法和建表示例 四、哈希表的四、哈希表的查找及其分析找及其分析 五、哈希表的五、哈希表的删除操作除操作 六、哈希表可构造静态查找表六、哈希表可构造静态查找表93 以上两节讨论的表示查找表的

31、各种结构结构的共同特点特点：记录在表中的位置位置和它的关键字关键字之间不存在不存在一个确定的关系，一、哈希表是什么？哈希表是什么？查找的过程查找的过程为给定值给定值依次和关键字集合中各个关键字关键字进行比较比较，查找的效率找的效率取决于和给定值进行比行比较的关键字个数个数。94 用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差差别仅在于：在于：关键字和给定值进行比较的顺序不同。95 只有一个办法：预先知道所查关键字在表中的位置，对于频繁使用的查找表，希望 ASL=0。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。96若以下以下标为000 999 的的顺序表序表表

32、示之。例如：例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要不需要经过比比较便可直接从顺序表中找到待查关键字。97但是，对于动态查找表找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key)为哈希函数。1)表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。98 Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei

33、 例如：例如：对于如下 9 个关键字设哈希函数哈希函数 f(key)=(Ord(第一个字母第一个字母)-Ord(A)+1)/2 ChenZhaoQianSunLiWuHanYeDei问题:若添加关键字 Zhou,怎么怎么办？能否找到能否找到另一个哈希函数？991)哈希函数是一个映象映象，即：将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上，它的设置很灵活灵活，只要这个地址集地址集合的大小不不超出允许范围超出允许范围即可；从从这个例子可个例子可见：2)由于哈希函数是一个压缩映象压缩映象，因此,在一般情况下，很容易产生“冲突冲突”现象，即：key1 key2，而 f(key1

34、)=f(key2)。100doggieMarycartelbaseballWashingtonf(key)Key Set Beer关键字集合的内容不可预知是一种压缩映射冲突冲突总不可避免不可避免BBS论坛 妮称表妮称表1013)很难很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。102哈希表哈希表的定的定义：根据设定的哈希函数哈希函数 H(key)和所选中的处理冲突的方法理冲突的方法，将一组关键字映象映象到到一个有限的、地址

35、连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存存储位置位置，如此构造所得的查找表称之为“哈希表哈希表”。103二、构造哈希函数的几种方法二、构造哈希函数的几种方法 对数字数字的关键字可有下列构造方法：若是非数字关非数字关键字字，则需先需先对其进行行数字化数字化处理理。1.直接定址法直接定址法3.平方取中法平方取中法5.除留余数法除留余数法4.折叠法折叠法6.随机数法随机数法2.数字分析法数字分析法104哈希函数为关键字的线性函数 H(key)=key 或者 H(key)=a key+b1.直接定址法直接定址法此法此法仅适合于：适合于：地址集合的大小地址集合的大小=关

36、关键字集合的大小字集合的大小105 此方法此方法仅适合于：适合于：能预先估先估计出出全体关键字的每一位上每一位上各种数字出数字出现的的频度度。2.数字分析法数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。106 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法平方取中法 此方法适合于此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。107 将关键字分割成若干部分，然后取它们的

37、叠加和为哈希地址。有两种叠加处理的方法：移位叠加移位叠加和间界叠加间界叠加。4.折叠法折叠法1081 1 0 1 0 2 1 9 1 1 1 2 3 1 0 9 1 11 1 0 1 0 21 1 0 1 0 21 1 0 1 0 22 1 1 1 9 13 1 0 9 1 1+）6 3 2 2 0 41 1 0 1 0 21 9 1 1 1 23 1 0 9 1 1+）6 1 2 1 2 5 此方法适合于此方法适合于:关键字的数字位数特别多。1095.除留余数法除留余数法 设定哈希函数为:H(key)=key MOD p 其中，pm(表表长)并且 p 应为不大于 m 的素数 或是或是 不含

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

39、态),总的原的原则是是使使产生冲突的可能性降到尽可能地小生冲突的可能性降到尽可能地小。113三、处理冲突的方法和建表示例三、处理冲突的方法和建表示例 “处理冲突理冲突”的实际含义是：为产生冲突的地址寻找下一个找下一个哈希地址。1.开放定址法开放定址法2.链地址法链地址法114 为产生冲突的地址 H(key)求得一个地址序列地址序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s1.开放定址法开放定址法115对增量对增量 di 有三种取法：有三种取法：1)线性探测再散列 di=c i 最简单的情况 c=12)平方探测再散列 di

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

41、190123 1468若采用线性探性探测再散列再散列处理冲突若采用二次探二次探测再散列再散列处理冲突11 8236551182361 1 2 1 3 6 2 5 1118 H2(key)是另设定的一个哈希函数，它的函数值应和 m 互为素数。若 m 为素数，则 H2(key)可以是 1 至 m-1 之间的任意数任意数；若 m 为 2 的幂次，则 H2(key)应是 1 至 m-1 之间的任意奇数任意奇数。例如，当 m=11时，可设 H2(key)=(3 key)MOD 10+11901231455681182362 1 1 1 2 1 2 1 3119将所有哈希地址相同的记录都链接在同一链表中。

42、2.链地址法链地址法0123456140136198223116855 ASL=(61+22+3)/9=13/9例如:同前例的关键字，哈希函数为 H(key)=key MOD 7120 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为：四、哈希表的四、哈希表的查找及其分析找及其分析 对于给定值 K，计算哈希地址 i=H(K)若若 ri=NULL 则查找不成功若若 ri.key=K 则查找成功否否则“求下一地址 Hi”，直至 rHi=NULL (查找不成功)或 rHi.key=K (查找成功)为止。121int hashsize=997,.;typedef struct E

43、lemType *elem;int count;/当前数据元素个数 int sizeindex;/hashsizesizeindex为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1/-开放定址哈希表开放定址哈希表的存储结构-122Status SearchHash(HashTable H,KeyType K,int&p,int&c)/在开放定址哈希表H中查找关键码为K的记录/SearchHashp=Hash(K);/求得哈希地址while(H.elemp.key!=NULLKEY&!EQ(K,H.e

44、lemp.key)collision(p,+c);/求得下一探查地址 pif(H.elemp.key=K)return SUCCESS;/查找成功，返回待查数据元素位置 pelse return UNSUCCESS;/查找不成功123Status InsertHash(HashTable&H,Elemtype e)/InsertHashc=0;if(HashSearch(H,e.key,p,c)=SUCCESS)return DUPLICATE;/表中已有与 e 有相同关键字的元素else H.elemp=e;+H.count;return OK;/查找不成功时，返回 p为插入位置else R

45、ecreateHashTable(H);/重建哈希表 if(c lchild,pre,verdict);if(!pre|verdict&T-data pre-data)/当前结点数据域值大于前驱时 pre=T;/把当前指针交给前驱，pre比T迟一步完成中序遍历 divideBST(T-rchild,pre,verdict);else verdict=FALSE;/当前结点数据域值不比前驱大，给出否定的结论 138503080209010854035252788T TprepreT TprepreT TprepreT TT Tprepreverdict=TRUE;T-data pre-dataFALSE；