数据结构查找演示文稿

数据结构查找演示文稿目前一页\总数七十八页\编于十四点优选数据结构查找Ppt目前二页\总数七十八页\编于十四点术语：查找(检索)——根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素

关键字——是记录某个数据项的值，它可以唯一标识一个记录。

次关键字——不能唯一的确定一个记录，但能确定表的一个子表。子表的元素个数应远少于表中元素数。为简化问题，将表中元素看成简单的整型数据，理解为关键字部分。目前三页\总数七十八页\编于十四点8.1静态查找表

1、顺序表的顺序查找

应用范围：顺序表或线性链表表示的表，表内元素之间无序。查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。

search(st,key，n)//在有n个数据的表st中找key{i=n-1;while(i>=0&&st[i]!=key)i--;if(i<0)return-1;//查找不成功返回-1

elsereturni;//查找成功返回下标号}算法主要时间在循环，为减少判定，n个数据用容量为n+1的一维数组表示。st[1]到st[n]存储数据，st[0]作为监视哨

search1(st,key，n){st[0]=key;i=n;while(st[i]!=key)i--;returni;//查找返回序号，0为不成功}目前四页\总数七十八页\编于十四点顺序查找的平均时间为表长的一半。2、顺序有序表的查找———二分（折半）查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定的待查值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较：若k=r[mid]，查找成功，结束若k<r[mid]，则high=mid-1若k>r[mid]，则low=mid+1重复上述操作，直至low>high时，查找失败highmidlow目前五页\总数七十八页\编于十四点bin_search(st[],key,n){low=0;high=n-1;while(low<=high){mid=(low+high)/2;

if(st[mid]==key)returnmid;elseif(st[mid]>key)high=mid-1;elselow=mid+1;}return-1;}mid=(low+high)>>1;递归：bin_search(st[],key,l,h){if(l<=h){mid=(l+h)>>1;if(st[mid]==key)returnmid;elseif(st[mid]>key)returnbin_search(st,key,l,mid-1);elsereturnbin_search(st,key,mid+1,h)}elsereturn-1;}平均查找时间目前六页\总数七十八页\编于十四点3、分块查找数据组织：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找（1）用数组存放待查记录,（2）建立索引表，由每块中最大（小）的关键字及所属块位置的信息组成。目前七页\总数七十八页\编于十四点12345678910111213141516171822121389203342443824486058745786532248861713索引表查38当索引表较大时，可以采用二分查找在数据量极大时，索引可能很多，可考虑建立索引表的索引，即二级索引，原则上索引不超过三级目前八页\总数七十八页\编于十四点分块查找方法评价由上面的公式，在n一定时，可以通过选择s使ASL尽可能小可以证明，当时，对于（1）ASL最小。目前九页\总数七十八页\编于十四点小结：时间：顺序查找最差，二分最好，分块介于两者之间空间：分块最大，需要增加索引数据的空间特点：1）顺序查找对表没有特殊要求2）分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。3）二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。4）在表不大时，一般直接使用顺序查找。目前十页\总数七十八页\编于十四点二分查找的C/C++接口stdlib.hvoid*bsearch(void*key,void*base,intnelement,intsize,int(*fcmp)(constvoid*,constvoid*))其中：fcmp规定：第一个数据小于第二个，返回小于0的数第一个数据等于第二个，返回0第一个数据大于第二个，返回大于0的数目前十一页\总数七十八页\编于十四点#include<iostream.h>#include<stdlib.h>cmp(constvoid*a,constvoid*b){ if(*(int*)a<*(int*)b)return-1; elseif(*(int*)a==*(int*)b)return0; elsereturn1;}voidmain(){ intar[]={-2,3,6,9,10,21,22,34,56}; int*p; intt; t=9; p=(int*)bsearch(&t,ar,sizeof(ar)/sizeof(int),sizeof(int),cmp); if(p!=NULL)cout<<*p<<endl;}目前十二页\总数七十八页\编于十四点8.2动态查找8.2.1二叉排序树和二叉平衡树一、二叉排序树1

二叉排序树定义

二叉排序树（BinarySortTree）或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树中所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树中所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；目前十三页\总数七十八页\编于十四点45372453100619078312根据二叉排序树的定义，对二叉树进行LDR遍历得到是递增序列。目前十四页\总数七十八页\编于十四点2、查找：步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。12225030011020099105230216

TreeNode*SearchBST(t,key)/*在二叉分类树查找关键字之值为key的结点，找到返回该结点的地址，否则返回空。t为二叉分类树的根结点的指针。*/{if(t==NULL||key==t->data)returnt;elseif（key<t->data)returnSearchBST(t->lchild,key);elsereturnSearchBST(t->rchild,key);}//SearchBST目前十五页\总数七十八页\编于十四点3、插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。

注意：新插入的结点总是叶子结点。例：将序列：122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。12299250300280110目前十六页\总数七十八页\编于十四点voidInsertBST(*&t，key)//在二叉排序树中插入查找关键字key{if(t==NULL){t=newBiTree;t->lchild=t->rchild=NULL;t->data=key;return;}if(key<t->data)InsertBST(t->lchild,key);elseInsertBST(t->rchild,key);}voidCreateBiTree(tree,d[],n）//n个数据在数组d中，tree为二叉排序树根{tree=NULL;for(i=0;i<n;i++)InsertBST(tree,d[i]);}类C程序实现：目前十七页\总数七十八页\编于十四点4.二叉排序树中一个结点的删除在二叉排序树中删除结点的原则是：删除结点后仍是二叉排序树。

设在二叉排序树被删除结点是x，其双亲结点为f。情况讨论：（1）x为叶子结点，则直接删除（2）x只有左子树xL或只有右子树xR,则令xL或xR直接成为双亲结点f的子树；ffxxLfxxRf目前十八页\总数七十八页\编于十四点（3）x即有左子树xL也有右子树xRfxxRxL在xL中选值最大的代替x，该数据按二叉排序树的性质应在最右边。qfxxRcscLqLsLfsxRcqcLqLsL目前十九页\总数七十八页\编于十四点二叉排序树的删除操作例子

叶子结点：直接删除。如：删除数据为15、70的结点。15607030205060302050目前二十页\总数七十八页\编于十四点12225030011020099105230216400450500若被删结点的左儿子为空或者右儿子为空。如下图所示，删除结点的数据场为200的结点。删除20012225030023021640045050011099105目前二十一页\总数七十八页\编于十四点被删结点的左、右子树皆不空1222503001102009910523021640045050011025030010520099230216400450500目前二十二页\总数七十八页\编于十四点voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}目前二十三页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq目前二十四页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq目前二十五页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq目前二十六页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq目前二十七页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pqs目前二十八页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}psq目前二十九页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}psdq目前三十页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}dpsdq目前三十一页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}dpsdq目前三十二页\总数七十八页\编于十四点voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}p等于q的情况spxqsxqp目前三十三页\总数七十八页\编于十四点删除一个结点：DeleteBST(*&t,key)//在根为t的排序二叉树中删去值为key的结点{

if(!t)returnelseif(t->data==key){delete(t);elseif(t->data>key)DeleteBST(t->lchild,key);elseDeleteBST(t->rchild,key);}目前三十四页\总数七十八页\编于十四点DABCFEG二、平衡二叉树

起因：提高查找速度，避免最坏情况出现。如下图单枝情况的出现。

平衡因子（平衡度）：结点的平衡因子是结点的左子树的高度减去右子树的高度。（或反之定义）

平衡二叉树：每个结点的平衡因子都为1、－1、0的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。1、概念与定义目前三十五页\总数七十八页\编于十四点例：014125392863536050171873011-1-1-100000000平衡二叉树028181453963536050173012-1-100001-1非平衡二叉树0目前三十六页\总数七十八页\编于十四点

2、平衡树的平衡方法：在左图所示的平衡树中插入数据为2的结点。插入之后仍应保持平衡分类二叉树的性质不变。14125392863536050171873011-1-1-100000000平衡树1412539286353605017187301-1-1-1000000002112原平衡度为0不平衡点解决：如何用最简单、最有效的办法保持平衡分类二叉树的性质2目前三十七页\总数七十八页\编于十四点141253928635360501718730+1+1-1-1-1000000002112原平衡度为0不平衡点Adelson解决思路：不涉及到不平衡点的双亲，即以不平衡点为根的子树的高度应保持不变。新结点插入后，向根回溯找到第一个原平衡因子不为0的结点（如图中9）。新插入的结点和第一个平衡因子不为0的结点之间的结点，其平衡因子原皆为0在调整中，仅涉及前面所提到的最小子树（如：以9为根的子树）仍应保持排序二叉树的性质不变。目前三十八页\总数七十八页\编于十四点3、平衡种类分析

左调整（新结点插入在左子树上的调整）：1、LL情况：（插入在结点左子树的左子树上）LL旋转旋转前后：高度都为h+11h-10AB1h-12hh-1BRARBLBA0h0h-1h-1BRARBL目前三十九页\总数七十八页\编于十四点旋转算法voidLL_rotate(BBSTNode*a){BBSTNode*b;b=a->Lchild;a->Lchild=b->Rchild;b->Rchild=a;a->Bfactor=b->Bfactor=0;a=b;}目前四十页\总数七十八页\编于十四点2、LR情况：（新插入结点在左子树的右子树上）h-1旋转前后高度仍然是h+1h-1CB0h-1BLARACRh-2CLh-1-10BLAB1h-102-1ARARCCRCLh-2h-101LR旋转目前四十一页\总数七十八页\编于十四点旋转算法voidLR_rotate(BBSTNode*a){BBSTNode*b,*c;b=a->Lchild;c=b->Rchild;/*初始化*/a->Lchild=c->Rchild;b->Rchild=c->Lchild;c->Lchild=b;c->Rchild=a;if(c->Bfactor==1){a->Bfactor=-1;b->Bfactor=0;}elseif(c->Bfactor==0)a->Bfactor=b->Bfactor=0;else{a->Bfactor=0;b->Bfactor=1;}}目前四十二页\总数七十八页\编于十四点

右调整（新结点插入在右子树上进行的调整）1、RR情况：（插入在的右子树的右子树上）处理方法和LL对称2、RL情况：（插入在右子树的左子树上）处理方法与LR对称平衡树建立方法：（1）按二叉排序树插入结点（2）如引起结点平衡因子变为|2|，则确定旋转点，该点是离根最远（或最接近于叶子的点）（3）确定平衡类型后进行平衡处理，平衡后以平衡点为根的子树高不变目前四十三页\总数七十八页\编于十四点589162127431011二叉排序树目前四十四页\总数七十八页\编于十四点二叉平衡树811122371095614目前四十五页\总数七十八页\编于十四点采用B_树和B+

树目的应文件系统的要求而发展起来的，大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外存次数。在1972年由R.Bayer和E.Macreight提出用B_树作为索引组织文件。提高访问速度、减少时间。 8.2.2B_树和B+树一、B_树及其操作目前四十六页\总数七十八页\编于十四点1、m阶B_树定义：m阶B_树满足或空，或为满足下列性质的m叉树：(1)树中每个结点最多有m棵子树(2)根结点在不是叶子时，至少有两棵子树(3)除根外，所有非终端结点至少有m/2棵子树(4)有s个子树的非叶结点具有n=s-1个关键字，结点的信息组织为:(n,A0,K1,A1,K2,A2

…Kn，An）

这里：n:关键字的个数，ki（i=1,2,…,n)为关键字，且满足Ki<Ki+1,，Ai(i=0,1,..n)为指向子树的指针。(5)所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。目前四十七页\总数七十八页\编于十四点例：4阶B_树。除根结点和叶子结点之外，每个结点的子树个数至少为m/2=2个；结点的关键字个数至少为1。该B_树的深度为4。叶子结点都在第4层上。蓝色代表结点中关键字个数黑色代表结点中关键字第1层第2层第3层第4层133118243781111271391993475864FFFFFFFFFFFF目前四十八页\总数七十八页\编于十四点3、B_树的查找：查找过程，类似于二叉树的查找，关键字为key的记录。从根开始在结点中顺序或二分（当m较大时）查找，如果Ki=key则查找成功,

若Ki<key<Ki+1：顺Ai指向的子树重复查找若key<K1：顺A0指向的子树重复查找若key>Kn;：找顺An指向的子树重复查找若找到叶子，则查找失败。目前四十九页\总数七十八页\编于十四点4、B_树中结点的插入

m代表B_树的阶，插入总发生在最低层1）插入后关键字个数小于等于m-1,完成。2）插入后关键字个数等于m,结点分裂，以中点数据为界一分为二，中点数据放到双亲结点中。这样就有可能使得双亲结点的数据个数为m,引起双亲结点的分裂，最坏情况下一直波及到根，引起根的分裂——B_树长高。

122430457053902610039506185例：3阶B_树的插入操作。最多3棵子树，2个数据；最少2棵子树，1个数据。所以3阶B_树也称为2-3树。插入位置插入数据：33目前五十页\总数七十八页\编于十四点31224304570539026100395061857243034570539026100395061851230324457053902610039506185127100303245390263950618512745707插入7目前五十一页\总数七十八页\编于十四点5、B_树中结点的删除*删除发生在最底层（1）被删关键字所在结点中的关键字数目大于等于m/2，直接删除。（2）删除后结点中数据为m/2-2，而相邻的左（右）兄弟中数据大于m/2-1，此时左（右兄弟）中最大（小）的数据上移到双亲中，双亲中接（靠）在它后（前）面的数据移到被删数据的结点中。32445539037100506170被删关键字324456190371005370目前五十二页\总数七十八页\编于十四点(3)其左右兄弟结点中数据都是m/2-1，此时和左（右）兄弟合并，合并时连同双亲中相关的关键字。此时，双亲中少了一项，因此又可能引起双亲的合并，最坏一直到根，使B-树降低一层。324459010061703244590371006170删除3732445901006170目前五十三页\总数七十八页\编于十四点*删除不在最底层在大于被删数据中选最小的代替被删数据，按B_树性质，其位置如下图所示（x是要删除的数据）xy用于代替x的数据问题转换成在最底层的删除目前五十四页\总数七十八页\编于十四点作业：试从空树开始，画出按以下次序向2-3树中插入数据的建树过程：20，30，50，52，60，68，70。如果以后删除50和68，画出每一步执行后2-3树的状态。目前五十五页\总数七十八页\编于十四点二、B+树在实际的文件系统中，用的是B+树或其变形。有关性质与操作类似与B_树。1、差异：（1）有n棵子树的结点中有n个关键字（2）所有叶子结点中包含全部关键字信息及对应记录位置信息（3）所有非叶子为索引，只含关键字而且仅有子树中最大或最小的信息。（4）非叶最底层顺序联结，这样可以进行顺序查找目前五十六页\总数七十八页\编于十四点59971544591015010203060910对应01的记录目前五十七页\总数七十八页\编于十四点2．查找过程※在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找；※在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；※若在结点内查找时，给定值≤Ki，则应继续在Ai所指子树中进行查找3．插入和删除的操作类似于B_树进行，即必要时，也需要进行结点的“分裂”或“合并”。目前五十八页\总数七十八页\编于十四点8.3哈希表前面查找方法共同特点：通过将关键字值与给定值比较，来确定位置。效率取决比较次数。理想的方法是：不需要比较，根据给定值能直接定位记录的存储位置。这样，需要在记录的存储位置与该记录的关键字之间建立一种确定的对应关系，使每个记录的关键字与一个存储位置相对应。例1949-2000年某地区人口统计表可以按公式确定其人数：y年人数=表[y-1948]年份人数123…..5152194919501951……...19992000200021002200……...44004420目前五十九页\总数七十八页\编于十四点1.哈希（也称为Hash、杂凑、散列）基本思想在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到元素。哈希函数——在记录的关键字与记录的存储位置之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储位置空间的一种映象。哈希函数可写成：

addr(ai)=h(ki)ai是表中的一个元素addr(ai)是ai的存储位置信息ki是ai的关键字目前六十页\总数七十八页\编于十四点哈希表——应用哈希函数，由记录的关键字确定记录在表中的位置信息，并将记录根据此信息放入表中，这样构成的表叫哈希表。哈希查找——利用哈希函数进行查找的过程。除了特别简单的应用，在大多数情况下，所构造出的哈希函数是多对一的（非单射函数）。即可能有多个不同的关键字，它们对应的哈希函数值是相同的，这意味着不同记录由哈希函数确定的存储位置是相同的。这种情况被称为冲突。即：若key1不等于key2,而h(key1)=h(key2)

Hash查找适合于关键字可能出现的值的集合远远大于实际关键字集合的情形。根据抽屉原理，冲突是不可能完全避免的，所以，要解决：（1）构造一个性能好，冲突少的Hash函数（2）如何解决冲突目前六十一页\总数七十八页\编于十四点2、常用的哈希函数（1）直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b特点：

直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少。此法仅适合于：地址集合的大小==关键字集合的大小目前六十二页\总数七十八页\编于十四点(2)数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。

例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址目前六十三页\总数七十八页\编于十四点此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。(2)数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。

目前六十四页\总数七十八页\编于十四点以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。（3）平方取中法目前六十五页\总数七十八页\编于十四点（4）折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址。种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加。例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加目前六十六页\总数七十八页\编于十四点

此方法适合于:关键字的数字位数特别多，且每一位上数字分布大致均匀情况。（4）折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址。种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加。目前六十七页\总数七十八页\编于十四点（5）除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key%p，pm特点：简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词（6）随机数法构造：取关键字的伪随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的情况说明：哈希函数构造不应太复杂不存在绝对好和坏的函数目前六十八页\总数七十八页\编于十四点3、冲突解决A)开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)%m，i=1,2,……k(km-1)其中：H(key)——哈希函数

m——哈希表表长

di——增量序列分类线性探测再散列：di=1,2,3,……m-1二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(km/2)伪随机探测再散列：di=伪随机数序列目前六十九页\总数七十八页\编于十四点例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key%13,哈希表长为m=16，

设每个记录的查找概率相等用线性探测再散列处理冲突，即Hi=(H(key)+di)%mH(55)=3冲突->H1=(3+1)%16=4

冲突->H2=(3+2)%16=5H(79)=1冲突->H1=(1+1)%16=2

冲突->H2=(1+2)%16=3

冲突->H3=(1+3)%16=4

冲突->H4=(1+4)%16=5

冲突->H5=(1+5)%16=6

冲突->H6=(1+6)%16=7

冲突->H7=(1+7)%16=8

冲突->H8=(1+8)%16=9012345678910111213141514168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1冲突->H1=(1+1)%16=2H(68)=3H(20)=7H(84)=6冲突->H1=(6+1)%16=7

冲突->H2=(6+2)%16=8H(27)=1冲突->H1

=(1+1)%16=2

冲突->H2=(1+2)%16=3

冲突->H2=(1+3)%