数据结构查找

第9章查找1整理ppt查找表(SearchTable)：是由同一类型的数据元素〔或记录〕构成的集合。

前面已介绍了各种线性或非线性的数据结构，本章讨论另一种在实际应用中大量使用的数据结构---查找表。由于“集合〞中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。2整理ppt对查找表经常进行的操作：〔1〕查询某个“特定的〞数据元素是否在查找表中。〔2〕检索某个“特定的〞数据元素的各种属性。〔3〕在查找表中插入一个数据元素。〔4〕从查找表中删去某个数据元素。3整理ppt查找表可分为两类：假设对查找表只作查询和检索操作，那么称此类查找表为静态查找表〔StaticSearchTable)。假设在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，那么称此类查找表为动态查找表〔DynamicSearchTable〕。4整理ppt

在各种系统软件或应用软件中，查找表是最常见的结构之一。如编译程序中符号表、信息处理系统中信息表等。综上所述，所谓“查找〞即为在一个含有众多的数据元素〔或记录〕的查找表中找出某个“特定的〞数据元素〔或记录〕。关于“特定的〞词的具体含义：关键字〔Key〕：是数据元素〔或记录〕中某个数据项的值，用它可以标识一个数据元素〔或记录〕。主关键字〔PrimaryKey〕：假设此关键字可以惟一地标识一个记录，那么称此关键字为主关键字。对不同的记录，其主关键字均不同。5整理ppt次关键字〔SecondaryKey〕：用以识别假设干记录的关键字为次关键字。

当数据元素只有一个数据项时，其关键字即为该数据元素的值。查找〔Searching)：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素〔或记录〕。查找成功：假设表中存在这样的一个记录，那么查找成功，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置。查找不成功：假设表中不存在关键字等于给定值的记录，那么查找不成功，此时查找的结果可给出一个“空〞记录或“空〞指针。6整理ppt此表为一个查找表。表中每一行为一个记录，学生的学号为记录的关键字。假设给定值为20010985，那么通过查找可得学生王五的各项信息。此时查找是成功的。假设给定值为20011930，那么由于表中没有关键字为20011930的记录，那么查找不成功。学号姓名性别入学总分录取专业┊┊┊┊┊20010983张三女438计算机20010984李四男430计算机20010985王五女445计算机┊┊┊┊┊20010998张三男458计算机┊┊┊┊┊招生录取登记表例：7整理ppt如何进行查找？在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。即：对查找表进行查找的方法取决于表中数据元素依何种关系组织在一起。〔这个关系是人为加上的。因为查找表中数据元素之间原本仅存在“同属于一个集合〞的松散关系〕。例：查英文单词。字典是按单词的字母在字母表中的次序编排的，那么查找时不需要从字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。字典这种查找表的数据元素之间原本仅存在着“同属于一个集合〞的松散关系，给查找带来不便。对字典按单词的字母在字母表中的次序进行编排，就是对字典这种查找表人为加上的一种关系，以便按某种规那么进行查找。8整理ppt

总之：查找的方法取决于查找表的结构。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。9整理ppt内查找和外查找：假设整个查找过程全部在内存进行，那么称为内查找；假设在查找过程中还需要访问外存，那么称为外查找。本书仅介绍内查找。平均查找长度ASL：查找算法的效率，主要看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。10整理ppt

对一个含n个数据元素的表，查找成功时：

其中：Pi为找到表中第i个数据元素的概率，且有：

Ci为查找表中第i个数据元素所用到的比较次数。不同的查找方法有不同的Ci。

查找是许多程序中最消耗时间的一部分。因而，一个好的查找方法会大大提高运行速度。11整理ppt9.1

静态查找表9.2动态查找表9.3

哈希表本章内容：12整理ppt9.1

静态查找表13整理ppt1.顺序表的查找静态查找表的存储结构可用顺序表或线性链表表示。本节只讨论在顺序存储结构中查找的实现。顺序查找的根本思想：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，假设某个记录的关键字和给定值比较相等，那么查找成功，找到所查记录；反之，假设直至第一个记录，其关键字和给定值比较都不等，那么说明表中没有所查记录，查找不成功。14整理ppti例

012

34567891011

513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n-i+1查找失败：n+115整理ppt例01234567891011

513192137566475808892找6464监视哨#defineM500typedefstruct{intkey;floatinfo;}JD;intseqsrch(JDr[],intn,intk){inti=n;r[0].key=k;while(r[i].key!=k)i--;return(i);}16整理ppt监测哨的作用：〔1〕省去判定循环中下标越界的条件，从而节约比较时间。〔2〕保存查找值的副本，查找时假设遇到它，那么表示查找不成功。这样在从后向前查找失败时，不必判断查找表是否检测完，从而到达算法统一。上述算法中，对于有n个数据元素的表，给定值k与表中第i个元素的关键字相等，即定位第i个记录时，需进行：ni+1次关键字比较，即Ci=ni+1。那么查找成功时，顺序查找的平均查找长度为：顺序查找性能分析：对一个含有n个数据元素的表，查找成功时有：17整理ppt设每个数据元素的查找概率相等，即Pi=，那么等概率情况下有：查找不成功时，关键字的比较次数总是n+1次。算法中的根本工作就是关键字的比较，因此，查找长度的量级就是查找算法的时间复杂度为O(n)。顺序查找缺点是当n很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有特殊要求。18整理ppt2.有序表的查找以有序表表示静态查找表时，可用折半查找法来实现查找。折半查找的根本思想：在有序表中，取中间元素作为比较对象，假设给定值与中间元素的关键字相等，那么查找成功；假设给定值小于中间元素的关键字，那么在中间元素的左半区继续查找；假设给定值大于中间元素的关键字，那么在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。折半查找也叫二分查找，是一种效率较高的查找方法，但前提是表中元素必须按关键字有序〔按关键字递增或递减〕排列。19整理ppt算法实现：设表长为n，low，high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较：假设k==r[mid].key，那么查找成功假设k<r[mid].key，那么high=mid-1假设k>r[mid].key，那么low=mid+1重复上述操作，直至low>high时，查找失败20整理ppt算法描述：lowhighmid例

1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid21整理ppt例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid22整理ppt1234567891011513192137566475808892lowhighintbinsrch(JDr[],intn,intk){intlow,high,mid,found;low=1;high=n;found=0;//found为找到标志。值为0表示未找到。while((low<=high)&&(found==0)){mid=(low+high)/2;if(k>r[mid].key)low=mid+1;elseif(k==r[mid].key)found=1;elsehigh=mid-1;}if(found==1)//如果已找到return(mid);//找到的记录的下标肯定为midelsereturn(0);}#defineM500typedefstruct{intkey;floatinfo;}JD;23整理ppt折半查找的性能分析：从折半查找的过程看，每次查找都是以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续作同样的操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树称为判定树。判定树中每一结点对应表中一个记录，但结点值不是某个记录的关键字，而是某个记录在表中的位置序号。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。24整理ppt1185210741936判定树：1234567891011513192137566475808892从上面判定树可看到，查找第一层的根结点56，一次比较即可找到；查找第二层的结点19和80，二次比较即可找到；查找第三层的结点5、21、64、88，三次比较即可找到；查找第四层的结点13，37、75、92，四次比较即可找到。25整理pptn个结点的判定树，树高为k，那么有2k-1-1<n≤2k-1，即k-1<log2(n+1)≤k，所以k=log2(n+1)。因此，二分查找在查找成功时，进行的关键字比较次数至多为log2(n+1)。查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键字的比较次数，也即该元素结点在树中的层次数。以树高为k的满二叉树(n=2k-1)为例。假设表中每个元素的查找是等概率的，即Pi=，那么树的第i层有2i-1个结点。二分查找的平均查找长度为：26整理ppt所以，二分查找的时间复杂度为：O(log2n)。二分查找的优点：效率高。二分查找的缺点：必须按关键字排序，有时排序也很费时；只适用顺序存储结构，所以进行插入、删除操作必须移动大量的结点。二分查找适用于一经建立就很少改动，而又经常需要查找的线性表。对于经常需要改动的线性表，可采用链表存储结构，进行顺序查找。27整理ppt3.索引顺序表的查找假设以索引顺序表表示静态查找表，可用分块查找法实现查找。分块查找又称索引顺序查找，是顺序查找的一种改进方法。查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。算法实现：用数组存放待查记录，每个数据元素至少含有关键字域。建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。28整理ppt12345678910111213141516171822121389203342443824486058745786532248861713索引表查38typedefstruct{intkey;intlink;}SD;typedefstruct{intkey;floatinfo;}JD;29整理pptintblocksrch(JDr[],SDd[],intb,intk,intn){inti=1,j;while((k>d[i].key)&&(i<=b))//确定要比较的值k在哪一块i++;//k<=d[i].key时的i就确定了k所在块的索引结点下标序号if(i>b){printf("\nNotfound");return(0);}j=d[i].link;//要比较的值k在以d[i].link为起点下标的块中while((j<n)&&(k!=r[j].key)&&(r[j].key<=d[i].key))j++;//在所在块中进行顺序查找if(k!=r[j].key){j=0;printf("\nNotfound");}return(j);}索引表长顺序表长30整理ppt分块查找方法评价:31整理pptASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找32整理ppt9.2

动态查找表33整理ppt动态查找表特点：动态查找表用于频繁进行插入、删除、查找。表结构本身是在查找过程中动态生成的，即对于给定值key，假设表中存在其关键字等于key的记录，那么查找成功返回，否那么插入关键字等于key的记录。本节讨论以各种树结构表示动态查找表时的插入、删除、查找的实现方法。34整理ppt1.二叉排序树〔1〕二叉排序树的定义二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：1〕假设它的左子树不空，那么左子树上所有结点的值均小于根结点的值；2〕假设它的右子树不空，那么右子树上所有结点的值均大于根结点的值；3〕它的左、右子树也都分别是二叉排序树。35整理ppt503080209010854035252388例如:是二叉排序树。66不36整理ppt45125333724100619078按中序遍历：3，12，24，37，45，53，61，78，90，100递增中序遍历二叉排序树可得到一个关键字的有序序列。37整理ppttypedefstructBiTNode{//

结点结构

TElemTypedata;structBiTNode*lchild,*rchild;//左、右指针

}BiTNode,

*BiTree;通常，以二叉链表作为二叉排序树的存储结构：38整理ppt〔2〕二叉排序树的查找算法假设二叉排序树为空，那么查找不成功；否那么：1〕假设给定值等于根结点的关键字，那么查找成功；2〕假设给定值小于根结点的关键字，那么继续在左子树上进行查找；3〕假设给定值大于根结点的关键字，那么继续在右子树上进行查找。39整理ppt50308020908540358832例如:二叉排序树查找关键字==

50

,505035

,503040355090

,50809095,40整理ppt从上述查找过程可见，在查找过程中，生成了一条查找路径：

从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者

从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

——查找成功

——查找不成功41整理pptStatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，假设查找成功，那么返回指针p指向该数据元素的结点，并返回函数值为TRUE;否那么，说明查找不成功，返回指针p指向查找路径上访问的最后一个结点，并返回函数值为FALSE,指针f指向当前访问的结点的双亲，其初始调用值为NULLif(!T){p=f;returnFALSE;}//查找不成功elseif(EQ(key,T->data.key)){p=T;returnTRUE;}//查找成功elseif(LT(key,T->data.key))SearchBST(T->lchild,key,T,p);//在左子树中继续查找elseSearchBST(T->rchild,key,T,p);//在右子树中继续查找}42整理ppt30201040352523fT设

key=48fTfT22pfTfTTTTfffp43整理ppt二叉排序树的查找分析：

在二叉排序树上查找其关键字等于给定值结点的过程，恰是走了一条从根结点到该结点的路径的过程。含有n个结点的二叉树是不唯一的，如何来进行查找分析呢？44整理ppt例如：上图两棵二叉排序树中，结点的个数和值均相同。但〔a〕的深度为3，而〔b〕的深度为6。其等概率平均查找长度分别为：ASL(a)=(1*1+2*2+3*3)/6=14/6ASL(b)=(1*1+2*1+3*1+4*1+5*1+6*1)/6=21/6因此，二叉排序树的平均查找长度和二叉树的形态有关。最好情况下，二叉排序树在生成过程中，树的形态比较均匀，其最终得到的是一颗形态与二分查找的判定树相似的二叉排序树，如图(a)所示。最坏情况下，二叉排序树通过一个有序表的n个结点依次插入生成的，此时所得的二叉排序树为一颗深度为n的单支树，如图(b)所示。它的平均查找长度和单链表的顺序查找相同，也是〔n+1〕/2。对均匀的二叉排序树进行插入或删除结点后，应对其进行调整，使其依然保持均匀。45整理ppt(3)二叉排序树的插入算法根据动态查找表的定义，插入操作在查找不成功时才进行。假设二叉排序树为空树，那么新插入的结点为新的根结点；否那么，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。4512533372410061907820例如：在右图给定的二叉排序树中插入结点2046整理pptStatusInsertBST(BiTree&T,ElemTypee){//当二叉排序树中不存在关键字等于e.key的数据元素时，插入元素值为e的结点，并返回TRUE;否那么，不进行插入并返回FALSE。if(!SearchBST(T,e.key,NULL,p))//如果查找不成功，才进行插入{……}else//如果查找成功，那么不进行插入returnFALSE;}

47整理ppts=(BiTree)malloc(sizeof(BiTNode));

//

为新结点分配空间s->data=e;

s->lchild=s->rchild=NULL;

if(!p)T=s;//插入s为新的根结点elseif(LT(e.key,p->data.key))p->lchild=s;//插入*s为*p的左孩子elsep->rchild=s;//插入*s为*p的右孩子returnTRUE;//插入成功48整理ppt(4)二叉排序树的删除算法

和插入相反，删除在查找成功之后进行，并且要求删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：1〕被删除的结点是叶子；2〕被删除的结点只有左子树或者只有右子树；3〕被删除的结点既有左子树，也有右子树。49整理ppt50308020908540358832被删除的结点是叶子结点。例如:被删关键字=2088其双亲结点中相应指针域的值改为“空〞50整理ppt50308020908540358832被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树〞。被删关键字=408051整理ppt50308020908540358832被删除的结点既有左子树，也有右子树。4040以其前驱替代之，然后再删除该前驱结点。被删结点前驱结点被删关键字=5052整理pptStatusDeleteBST(BiTree&T,KeyTypekey){//假设二叉排序树T中存在其关键字等于key的数据元素，那么删除该数据元素结点，并返回函数值TRUE，否那么返回函数值FALSE。if(!T)//假设T为空returnFALSE;//不存在关键字等于key的数据元素else{if(EQ(key,T->data.key)){Delete(T);returnTRUE;}//找到关键字等于key的数据元素elseif(LT(key,T->data.key))DeleteBST(T->lchild,key);//继续在左子树中进行查找，删除elseDeleteBST(T->rchild,key);//继续在右子树中进行查找，删除}}53整理pptvoidDelete(BiTree&p){//从二叉排序树中删除结点p，并重接它的左子树或右子树

if(!p->rchild){……}elseif(!p->lchild){……}else{……}}其中删除操作过程如下所描述：54整理ppt//右子树为空树那么只需重接它的左子树q=p;p=p->lchild;free(q);pp55整理ppt//左子树为空树只需重接它的右子树q=p;p=p->rchild;free(q);pp56整理pptq=p;s=p->lchild;//转左while(s->rchild)//转左后，到右尽头{q=s;s=s->rchild;}

//q

指向s

的双亲，s指向被删结点的前驱p->data=s->data;//以前驱结点的数据替换被删结点的数据if(q!=p)q->rchild=s->lchild;//重接*q的右子树

elseq->lchild=s->lchild;//重接*q的左子树free(s);//左右子树均不空pqs57整理ppt(5)二叉排序树的构造过程例：记录的关键字序列为：33，50，42，18，39，9，77，44，2，11，24，那么构造一棵二叉排序树的过程如下：从空树开始建立二叉排序树的过程图示58整理ppt一个无序序列可以通过构造二叉排序树而成为一个有序序列。每次插入新结点都是二叉排序树上新的叶子结点，不必移动其它结点，仅需改动某个结点指针，由空变为非空即可。59整理ppt#include<stdio.h>typedefintTElemType;typedefstructBiTNode{//结点结构

TElemTypedata;structBiTNode*lchild,*rchild;//左、右指针

}BiTNode,*BiTree;生成二叉排序树的算法：60整理pptvoidInsBST(BiTree&T,TElemTypeK){BiTNode*f,*p;p=T;while(p)//当p为空时，即左孩子或右孩子为空时，p不再往下指//即从根结点开始找插入的位置，找到后，f为要插入位置的双亲结点的地址{if(p->data==K){printf("树中已有%d，不需插入\n",K);return;}f=p;p=(K<p->data)?p->lchild:p->rchild;//p指向自己的左孩子或右孩子，f指向左右孩子的双亲}p=newBiTNode;//申请一个新结点，把输入的值放入新结点p->data=K;p->lchild=p->rchild=NULL;if(T==NULL)//如果根结点为空，新结点为根结点T=p;elseif(K<f->data)//如果输入值小于它的根结点，那么作为此根结点的左孩子f->lchild=p;elsef->rchild=p;//如果输入值大于它的根结点，那么作为此根结点的右孩子}61整理pptBiTreeCreateBST(){BiTreeT;//T是一个指针变量，指向二叉排序树的根结点

TElemTypeK;T=NULL;printf("请输入一个整数关键字(输入0时结束输入)：");scanf("%d",&K);while(K){InsBST(T,K);printf(“请输入下一个整数关键字(输入0时结束输入)：");scanf("%d",&K);}returnT;}voidmain(){CreateBST();}62整理ppt例如:548254821是平衡树不是平衡树平衡二叉树的定义：又称AVL树。它或者是一棵空树，或者是具有以下性质的二叉树：1〕它的左子树和右子树高度之差的绝对值不超过1；2〕它的左子树和右子树都是平衡二叉树。2.二叉平衡树63整理ppt二叉树上结点的平衡因子：为该结点的左子树的深度减去它的右子树的深度。平衡二叉树上所有结点的平衡因子只可能是：-1、0、1

64整理ppt65整理ppt在插入过程中，采用平衡旋转技术。例如：依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转构造二叉平衡树的方法：66整理ppt426589642895向左旋转一次67整理ppt当平衡的二叉排序树因插入结点而失去平衡时，仅需对离插入结点最近的最小不平衡子树进行平衡旋转处理即可。平衡旋转处理可分为以下4种情况：〔1〕单向右旋〔顺时针〕〔2〕单向左旋〔逆时针〕〔3〕先左后右双向旋转〔4〕先右后左双向旋转68整理ppt例：一棵平衡二叉排序树如图〔a〕所示。在A的左子树的左子树上插入15后，导致失衡，如图〔b〕所示。为恢复平衡并保持二叉排序树的特性，可将A改为B的右子，B原来的右子改为A的左子，如图〔c〕所示。这相当于以B为轴，对A做了一次顺时针旋转。

不平衡二叉树的调整(1)

69整理ppt例：一棵平衡二叉排序树如图〔a〕所示。在A的右子树B的右子树上插入70后，导致失衡，如图〔b〕所示。为恢复平衡并保持二叉排序树的特性，可将A改为B的左子，B原来的左子改为A的右子，如图〔c〕所示。这相当于以B为轴，对A做了一次逆时针旋转。不平衡二叉树的调整(2)

70整理ppt例：一棵平衡二叉排序树如图〔a〕所示。在A的左子树B的右子树上插入45后，导致失衡，如图〔b〕所示。为恢复平衡并保持二叉排序树的特性，可首先将B改为C的左子，而C原来的左子改为B的右子；然后将A改为C的右子，C原来的右子改为A的左子，如图〔c〕所示。这相当于对C做了一次逆时针旋转，对A做了一次顺时针旋转。71整理ppt不平衡二叉树的调整(3)72整理ppt例：一棵平衡二叉排序树如图〔a〕所示。在A的右子树的左子树上插入55后，导致失衡，如图〔b〕所示。为恢复平衡并保持二叉排序树的特性，可首先将B改为C的右子，而C原来的右子改为B的左子；然后将A改为C的左子，C原来的左子改为A的右子，如图〔c〕所示。这相当于对C做了一次顺时针旋转，对A做了一次逆时针旋转。73整理ppt不平衡二叉树的调整(4)74整理ppt在二叉平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。二叉平衡树的查找性能分析：问，含n个关键字的二叉平衡树可能到达的最大深度是多少？75整理pptn=0空树最大深度为

0n=1最大深度为

1n=2最大深度为

2n=4最大深度为

3n=7最大深度为

4先看几个具体情况:76整理ppt反过来问，深度为

h的二叉平衡树中所含结点的最小值Nh

是多少？h=0N0=0h=1h=2h=3一般情况下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用归纳法可证得Nh=Fh+2-177整理ppt因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和log(n)相当。即：在二叉平衡树上进行查找的时间复杂度为Olog(n)。由此推得，深度为

h的二叉平衡树中所含结点的最小值Nh=

h+2/5-1。反之，含有n

个结点的二叉平衡树能达到的最大深度为：hn=log

(5(n+1))-2。78整理ppt9.3

哈希表79整理ppt1.什么是哈希表以上讨论的查找方法，由于数据元素的存储位置与关键字之间不存在确定的关系，因此，查找时，需要进行一系列对关键字的查找比较，即查找算法是建立在比较的根底上的，查找效率由比较一次缩小的查找范围决定。理想的情况是依据关键字直接得到其对应的数据元素位置，即要求关键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的数据元素位置。80整理ppt例：11个元素的关键字分别为18，27，1，20，22，6，10，13，41，15，25。选取关键字与元素位置间的函数为：f(key)=keymod111.通过这个函数对11个元素建立查找表如下：

01234567891010204118627152513122查找时，对给定值kx通过这个函数计算出地址，再将kx与该地址单元中元素的关键字比较，假设相等，查找成功。81整理ppt哈希表与哈希方法：选取某个函数，依据该函数按关键字计算数据元素的存储地址，并按此地址存放数据元素；查找时，由同一个函数对给定值kx计算出地址，将kx与该地址单元中数据元素的关键字进行比较，确定查找是否成功，这就是哈希方法。哈希方法中使用的转换函数称为哈希函数。哈希方法中计算的存储地址称为哈希地址或散列地址。按这个思想构造的查找表称为哈希表。82整理ppt对于n个数据元素的集合，总能找到关键字与存放地址一一对应的函数。假设最大关键字为m，可以分配m个数据元素存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关键字的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突。83整理ppt冲突不可能防止，只能尽可能减少。所以，哈希方法需要解决以下两个问题：1〕构造好的哈希函数a.所选函数尽可能简单，以便提高转换速度。b.所选函数对关键字计算出的地址，应在哈希地址集中大致均匀分布，以减少空间的浪费。2〕制定解决冲突的方案。换句话说，就是使关键字经过哈希函数得到一个随机的地址，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。84整理ppt2.哈希函数的构造方法〔1〕直接定址法Hash(key)=a·key+b(a、b为常数)即：取关键字的某个线性函数值为哈希地址。这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键字集合大小相同，因此，对于较大的关键字集合不适用。实际中能使用这种哈希函数的情况很少。例：关键字集合为{20，30，50，60，80，90}，选取哈希函数为：Hash(key)=key/10，那么存放如下：0123456789关键字存放地址图示80605030209085整理ppt〔2〕除留余数法Hash(key)=keymodp(p是一个整数)即：取关键字除以p的余数作为哈希地址。使用除留余数法，选取适宜的p很重要，假设哈希表表长为m，那么要求p≤m，且接近m或等于m。p一般选取质数，也可以是不包含小于20质因子的合数。这是一种最简单，也最常用的构造哈希函数的方法。86整理ppt〔3〕平方取中法对关键字平方后，按哈希表大小，取中间的假设干位作为哈希地址。例：假设存储区域可存100个记录，关键字=4731那么4731×4731=22382361 取地址82例：假设存储区域可存10000个记录，关键字=14625那么14625×14625=213890625 取地址8906取的位数由表长决定，这是一种较常用的构造哈希函数的方法。87整理ppt3.处理冲突的方法〔1〕开放定址法所谓开放定址法，即是由关键字得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。1〕线性探测法Hi=(Hash(key)+di)modm(1≤i<m)其中：Hash(key)为哈希函数m为哈希表长度di=i； i=1，2，3，…，m-188整理ppt例：关键字集为{47，7，29，11，16，92，22，8，3}，哈希表表长为11，Hash(key)=keymod11。用线性探测法处理冲突，建表如下：

01234

5

6

78

910829731692472211△△△▲

用线性探测法处理冲突的哈希表图示47、7、11、16、92均是由哈希函数得到的没有冲突的哈希地址而直接存入的；

Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址。由H1=(Hash(29)+1)mod11=8，哈希地址8为空，将29存入。另外，22、8同样在哈希地址上有冲突，也是由H1找到空的哈希地址的；89整理ppt而Hash(3)=3，哈希地址上冲突，由

H1=(Hash(3)+1)mod11=4仍然冲突；

H2=(Hash(3)+2)mod11=5仍然冲突；

H3=(Hash(3)+3)mod11=6找到空的哈希地址，存入。线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积〞起来，大大降低了查找效率。为此，可采用二次探测法，或双哈希函数探测法，以改善“堆积〞问题。90整理ppt2〕二次探测法〔平方探测法〕

Hi=(Hash(key)±di)modm

其中：Hash(key)为哈希函数

m为哈希表长度，m要求是