《数据结构DS08查找》由会员分享，可在线阅读，更多相关《数据结构DS08查找（76页珍藏版）》请在金锄头文库上搜索。
1、 基本概念基本概念 线性表的查找线性表的查找 树表的查找树表的查找 散列散列( (Hash)Hash)技术技术 第八章第八章 查找查找18.1查找的基本概念查找的基本概念 查找（查找（Searching）的定义是：给定的定义是：给定一个关键字值一个关键字值K，在含有，在含有n个结点的个结点的表中找出关键字等于给定值表中找出关键字等于给定值K的结点。的结点。若找到，则查找成功，返回该结点的若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查信息或该结点在表中的位置；否则查找失败，返回相关的指示信息找失败，返回相关的指示信息。2查找表的数据结构表示查找表的数据结构表示若在查找的同时对表
2、做修改操作（如插入和删除等），则相应的表称之为动态查找表动态查找表（DynamicSearchTable）。否则称之为静态查找表静态查找表(StaticSearchTable)。若整个查找过程都在内存进行，则称之为内查找内查找；反之，若查找过程中需要访问外存，则称之为外查找。外查找。3n n平均查找长度平均查找长度平均查找长度平均查找长度 ASLASL（AverageSearchLengthAverageSearchLength）的的的的定义为定义为定义为定义为 ：ASL=ASL= 其中：其中：1、n是结点的个数；是结点的个数；2、Pi是查找第是查找第i个结点的概率。若不特别个结点的概率。若不
3、特别声明，认为每个结点的查找概率相等，即声明，认为每个结点的查找概率相等，即pl=p2=pn=1/n3、ci是找到第是找到第i个结点所需进行的比较次个结点所需进行的比较次数。（数。（i=1,2,n）4顺序查找顺序查找(SequentialSearch)基本思想是：基本思想是：从表的一端开始，顺序扫从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字描线性表，依次将扫描到的结点关键字和给定值和给定值K相比较。若当前扫描到的结点相比较。若当前扫描到的结点关键字与关键字与K相等，则查找成功；若扫描结相等，则查找成功；若扫描结束后，仍未找到关键字等于束后，仍未找到关键字等于K的结点，则的结点，则查
4、找失败。查找失败。8.2线性表的查找线性表的查找5基于顺序结构的顺序查找算法基于顺序结构的顺序查找算法 类型说明类型说明 typedef struct typedef struct KeyType key KeyType key； /* KeyType/* KeyType/* KeyType/* KeyType由用户定由用户定由用户定由用户定义义义义 */ */ */ */ InfoType otherinfo InfoType otherinfo；/* /* /* /* 此类型此类型此类型此类型依赖于依赖于依赖于依赖于 应用应用应用应用 */ */ */ */ NodeType NodeTy
5、pe； typedef NodeType Seqlistn+1 typedef NodeType Seqlistn+1； /*0 /*0号单元用作监视哨号单元用作监视哨*/*/6具体算法具体算法具体算法具体算法 intSeqSearch(SeqlistR，KeyTypeK)/*在顺序表在顺序表R1.n中顺序查找关键字为中顺序查找关键字为K的结点，成功时返回找到的结点位置，失败的结点，成功时返回找到的结点位置，失败时返回时返回0*/inti；R0.key=K；/*设置监视哨设置监视哨*/for(i=n；Ri.key!=K;i-)；/*从表后往前从表后往前找找*/returni；/*若若i为为0，
6、表示查找失败，否，表示查找失败，否则则Ri为要找的结点为要找的结点*/*SeqSearch*/7算法分析算法分析查找成功时的顺序查找的平均查找长度：查找成功时的顺序查找的平均查找长度：ASL= =pASL= =pi i =np =np1 1+(n-+(n-1)p1)p2 2+2p+2pn-1n-1+p+pn n （式（式8.28.2）在等概率情况下，在等概率情况下，p pi i=1/n(1in)=1/n(1in)，故成，故成功的平均查找长度为功的平均查找长度为 (n+2+1)/n=(n+1)/2 (n+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的即查找成功时的平均比较次数约
7、为表长的一半。一半。8n n顺序查找的优点顺序查找的优点顺序查找的优点顺序查找的优点算法简单，且对表的结构无任何要求，无论是用算法简单，且对表的结构无任何要求，无论是用算法简单，且对表的结构无任何要求，无论是用算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是向量还是用链表来存放结点，也无论结点之间是向量还是用链表来存放结点，也无论结点之间是向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。否按关键字有序，它都同样适用。否按关键字有序，它都同样适用。否按关键字有序，它都同样适用。n n顺序查找的缺点顺序查找的缺点顺序查找的缺点顺序查找的缺
8、点 查找效率低。查找效率低。查找效率低。查找效率低。9n n二分查找二分查找二分查找二分查找又称又称又称又称折半查找折半查找折半查找折半查找，它是一种效率较高的查找方，它是一种效率较高的查找方，它是一种效率较高的查找方，它是一种效率较高的查找方法。法。法。法。n n二分查找要求二分查找要求二分查找要求二分查找要求：线性表是有序表，即表中结点按关键：线性表是有序表，即表中结点按关键：线性表是有序表，即表中结点按关键：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有字有序，并且要用向量作为表的存储结构。不妨设有字有序，并且要用向量作为表的存储结构。不妨设有字有序，并且
9、要用向量作为表的存储结构。不妨设有序表是递增有序的。序表是递增有序的。序表是递增有序的。序表是递增有序的。二分查找二分查找二分查找二分查找10二分查找的基本思想是：二分查找的基本思想是：（1）首先确定该区间的中点位置：）首先确定该区间的中点位置： mid = （2）然后将待查的）然后将待查的K值与值与Rmid.key比较：比较：若相等，则查找成功并返回此位置，否则若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。须确定新的查找区间，继续二分查找。 11二分查找算法二分查找算法intBinSearch(SeqListR，KeyTypeK)intlow=1，high=n，mid
10、；while(lowK)high=mid-1;elselow=mid+1；return0；12例：设算法的输入实例中有序的关键字序例：设算法的输入实例中有序的关键字序列为：列为： 05，13，19，21，37，56，64，75，80，88，92，查找的关键字，查找的关键字K=21。 n第一步：05，13，19，21，37，56，64，75，80，88，9213n第二步：05，13，19，21，37，56，64，75，80，88，92n第三步：05，13，19，21，37，56，64，75，80，88，92此时Rmid.keyK，returnmid4。14二分查找判定树二分查找判定树二分查找过程
11、可用二叉树来描述：二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分由此得到的二叉树，称为描述二分查找的查找的判定树判定树(DecisionTree)或或比比较树较树(ComparisonTree)。15二分查找判定树的组成二分查找判定树的组成n n圆结点即树中的内部结点。树中圆结点内圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。的数字表示该结点在有序表中的位置。n n外部结点：圆结
12、点中的所有空指针均用一外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。个虚拟的方形结点来取代，即外部结点。n n当查找时找到外部节点时，表示查找的值当查找时找到外部节点时，表示查找的值没有在该有序表中。没有在该有序表中。16二分查找的平均查找长度二分查找的平均查找长度 n二分查找成功时的平均查找长度为：二分查找成功时的平均查找长度为： ASL ASLbnbnlg(n+1)-1 lg(n+1)-1 n二分查找在查找失败时所需比较的关二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超坏情况下查找成
13、功的比较次数也不超过判定树的深度。即为：过判定树的深度。即为：17二分查找的优点和缺点二分查找的优点和缺点n虽然二分查找的效率高，但是要将表虽然二分查找的效率高，但是要将表按关键字排序。按关键字排序。 n二分查找只适用顺序存储结构。为保二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。删除都必须移动大量的结点。 18分块查找分块查找 n分块查找表分块查找表存储结构存储结构n分块查找表由分块查找表由 分块有序分块有序 的线性表的线性表和和索引表索引表组成。组成。19n分块查找的分块查找的基本思想基本思想 ：n首先查找索引表首
14、先查找索引表 索引表是有序表，可采用二分查索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在找或顺序查找，以确定待查的结点在哪一块。哪一块。n然后在已确定的块中进行顺序查找然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。由于块内无序，只能用顺序查找。 20查找查找关键字等于给定值关键字等于给定值K=24K=24的结点的结点 (见见P197)n因为索引表小，不妨用顺序查找方法查因为索引表小，不妨用顺序查找方法查找索引表。即首先将找索引表。即首先将K K依次和索引表中各依次和索引表中各关键字比较，直到找到第关键字比较，直到找到第1 1个关键宇大小个关键宇大小等于等于K K的
15、结点，由于的结点，由于K48K48，所以关键字为，所以关键字为2424的结点若存在的话，则必定在第二块的结点若存在的话，则必定在第二块中；然后，由中；然后，由ID2.addrID2.addr找到第二块的找到第二块的起始地址起始地址7 7，从该地址开始在，从该地址开始在R7.12R7.12中中进行顺序查找，直到进行顺序查找，直到R11.key=KR11.key=K为止。为止。21算法分析算法分析 n分块查找是两次查找过程。整个查找过程的平分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。均查找长度是两次查找的平均查找长度之和。 以二分查找来确定块，分块查找成功时的以
16、二分查找来确定块，分块查找成功时的平均查找长度平均查找长度nASLASLblkblk=ASL=ASLbnbn+ASL+ASLsqsqnloglog2 2(b+1)-1+(s+1)/2log(b+1)-1+(s+1)/2log2 2(n/s+1)+s/2(n/s+1)+s/2 以顺序查找确定块，分块查找成功时的平以顺序查找确定块，分块查找成功时的平均查找长度均查找长度nASLASLblkblk=(b+1)/2+(s+1)/2=(s=(b+1)/2+(s+1)/2=(s2 2+2s+n)/(2s) +2s+n)/(2s) 22n分块查找的优点分块查找的优点n在表中插入或删除一个记录时，只在表中插入
17、或删除一个记录时，只要找到该记录所属的块，就在该块内要找到该记录所属的块，就在该块内进行插入和删除运算。进行插入和删除运算。n因块内记录的存放是任意的，所以因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量插入或删除比较容易，无须移动大量记录。记录。 238.3 8.3 树表的查找树表的查找n1 1、二叉排序树的、二叉排序树的定义定义 n二叉排序树二叉排序树(Binary Sort Tree)(Binary Sort Tree)又称又称二叉查找二叉查找( (搜索搜索) )树树(Binary Search Tree)(Binary Search Tree)。其定义为：二。其定义为：二
18、叉排序树或者是空树，或者是满足如下性质的二叉排序树或者是空树，或者是满足如下性质的二叉树：叉树：n（1 1）若它的左子树非空，则左子树上所有结点）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；的值均小于根结点的值；n（2 2）若它的右子树非空，则右子树上所有结点）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；的值均大于根结点的值；n（3 3）左、右子树本身又各是一棵二叉排序树。）左、右子树本身又各是一棵二叉排序树。 24n二叉排序树的特点二叉排序树的特点 n（1 1） 二叉排序树中任一结点二叉排序树中任一结点x x，其，其左左( (右右) )子树中任一结点子树中任一结点
19、y(y(若存在若存在) )的的关键字必小关键字必小( (大大) )于于x x的关键字。的关键字。n（2 2） 二叉排序树中，各结点关键字二叉排序树中，各结点关键字是唯一的。是唯一的。n（3 3） 按中序遍历该树所得到的中序按中序遍历该树所得到的中序序列是一个递增有序序列。序列是一个递增有序序列。25二叉排序树的存储结构二叉排序树的存储结构ntypedef int KeyTypetypedef int KeyType； ntypedef struct node typedef struct node n n KeyType key KeyType key； n InfoType otherinf
20、o InfoType otherinfo； n struct node *lchild struct node *lchild，*rchild*rchild； nBSTNodeBSTNode；ntypedef BSTNode *BSTreetypedef BSTNode *BSTree； 26n二叉排序树插入新结点的过程二叉排序树插入新结点的过程n在二叉排序树中插入新结点，要保证插入后仍满足在二叉排序树中插入新结点，要保证插入后仍满足BSTBST性质。其插入过程是：性质。其插入过程是：n1)1)若二叉排序树若二叉排序树T T为空，则为待插入的关键字为空，则为待插入的关键字keykey申请申请一
21、个新结点，并令其为根；一个新结点，并令其为根；n2)2)若二叉排序树若二叉排序树T T不为空，则将不为空，则将keykey和根的关键字比较：和根的关键字比较：n(a)(a)若二者相等，则说明树中已有此关键字若二者相等，则说明树中已有此关键字keykey，无须插入。，无须插入。n(b)(b)若若keyTkeykeyTkeykeyTkey，则将它插入根的右子树中。，则将它插入根的右子树中。 27n二叉排序树插入新结点的二叉排序树插入新结点的算法算法nvoidInsertBST(BSTree*Tptr，KeyTypekey)nnBSTNode*f，*p=*TPtr；nwhile(p)nif(p-ke
22、y=key)return；nf=p；np=(keykey)?p-lchild:p-rchild；nnnp=(BSTNode*)malloc(sizeof(BSTNode)；np-key=key；p-lchild=p-rchild=NULL；nif(*TPtr=NULL)n*Tptr=p；nelsenif(keykey)nf-lchild=p；nelsef-rchild=p；n28n二叉排序树的生成二叉排序树的生成n是从空的二叉排序树开始，每输入一是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法，个结点数据，就调用一次插入算法，将它插入到当前已生成的二叉排序树将它插入到当前已生成的
23、二叉排序树中。中。 29BSTreeCreateBST(void)BSTreeT=NULL；KeyTypekey；scanf(d，&key)；while(key)InsertBST(&T，key)；scanf(d，&key)；returnT；生成二叉排序树的算法生成二叉排序树的算法 30n输入实例(5，3，7，2，4，8)，根据生成二叉排序树算法生成二叉排序树的过程 55325375372537425374831二叉排序树的删除二叉排序树的删除 n从二叉排序树中删除一个结点，不能把以从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保该结点为根的子树都删去，并且还要保证删除后
24、所得的二叉树仍然满足证删除后所得的二叉树仍然满足BSTBST性质。性质。n1)1)删除操作的删除操作的一般步骤一般步骤n 进行查找进行查找 查找时，令查找时，令p p指向当前访问到的指向当前访问到的结点，结点，parentparent指向其双亲指向其双亲( (其初值为其初值为NULL)NULL)。若树中找不到被删结点则返回，。若树中找不到被删结点则返回，否则被删结点是否则被删结点是*p*p。32n 删去删去*p*p。n删删*p*p时，应将时，应将*p*p的子树的子树( (若有若有) )仍连接在树仍连接在树上且保持上且保持BSTBST性质不变。按性质不变。按*p*p的孩子数目分的孩子数目分三种情
25、况进行处理。三种情况进行处理。n2)2)删除删除*p*p结点的三种情况结点的三种情况n*p*p是叶子是叶子( (即它的孩子数为即它的孩子数为0)0)n 无须连接无须连接*p*p的子树，只需将的子树，只需将*p*p的的双亲双亲*parent*parent中指向中指向*p*p的指针域置空即可。的指针域置空即可。n*p*p只有一个孩子只有一个孩子*child*childn只需将只需将*child*child和和*p*p的双亲直接连接后，即的双亲直接连接后，即可删去可删去*p*p。33n*p*p有两个孩子有两个孩子 先令先令q=pq=p，将被删结点的地址保存在，将被删结点的地址保存在q q中；然后找中
26、；然后找*q*q的中序后继的中序后继*p*p，并在查，并在查找过程中仍用找过程中仍用parentparent记住记住*p*p的双亲位的双亲位置。置。*q*q的中序后继的中序后继*p*p一定是一定是*q*q的右子的右子树中最左下的结点，它无左子树。因树中最左下的结点，它无左子树。因此，可以将删去此，可以将删去*q*q的操作转换为删去的操作转换为删去的的*p*p的操作，即在释放结点的操作，即在释放结点*p*p之前将之前将其数据复制到其数据复制到*q*q中，就相当于删去了中，就相当于删去了*q*q。34二叉排序树删除算法二叉排序树删除算法 nvoidDelBSTNode(BSTree*Tptr，Ke
27、yTypekey)nnBSTNode*parent=NUll，*p=*Tptr，*q，*child；nwhile(p)nif(p-key=key)break；nparent=p；np=(keykey)?p-lchild：p-rchild；nnif(!p)return；nq=p；nif(q-lchild&q-rchild)nfor(parent=q，p=q-rchild；p-lchild；nparent=p，p=p=-lchild)；nchild=(p-lchild)?p-lchild：p-rchild；nif(!parent)n*Tptr=child；nelsenif(p=parent-lch
28、ild)nparent-lchild=child；nelseparent-rchild=child；nif(p!=q)nq-key=p-key；nnfree(p)；n35二叉排序树上的查找二叉排序树上的查找n在二叉排序树上进行查找，和二分查找类似，也是一个逐步在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。缩小查找范围的过程。n递归的查找算法：递归的查找算法：nBSTNode *SearchBST(BSTree TBSTNode *SearchBST(BSTree T，KeyType key)KeyType key)n nif(T=NULL|key=T-key) if(
29、T=NULL|key=T-key) n return Treturn T； n if(keykey)if(keykey)n return SearchBST(T-lchildreturn SearchBST(T-lchild，key)key)；n elseelsen return SearchBST(T-rchildreturn SearchBST(T-rchild，key)key)； n 36n在二叉排序树上进行查找时的在二叉排序树上进行查找时的平均查找长度和二平均查找长度和二叉树的形态有关：叉树的形态有关：n(a)(a)在最坏情况下，二叉排序树是通过把一个有在最坏情况下，二叉排序树是通过把
30、一个有序表的序表的n n个结点依次插入而生成的，此时所得的个结点依次插入而生成的，此时所得的二叉排序树蜕化为一棵深度为二叉排序树蜕化为一棵深度为n n的单支树，它的的单支树，它的平均查找长度和单链表上的顺序查找相同，也是平均查找长度和单链表上的顺序查找相同，也是(n+1)/2(n+1)/2。n(b)(b)在最好情况下，二叉排序树在生成的过程中，在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是均查找长度大约是loglog2
31、 2n n。n(c)(c)插入、删除和查找算法的时间复杂度均为插入、删除和查找算法的时间复杂度均为O(logO(log2 2n)n)。37n二叉排序树和二分查找的比较二叉排序树和二分查找的比较 就平均时间性能而言，二叉排序树上的就平均时间性能而言，二叉排序树上的查找和二分查找差不多。查找和二分查找差不多。n就维护表的有序性而言，二叉排序树无须移动结就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为其平均的执行时间均为O(logO(log2 2n)n)，因此更有效。，因此更有效。二分查找所涉及的有序表
32、是一个向量，若有插入二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代和删除结点的操作，则维护表的有序性所花的代价是价是O(n)O(n)。当有序表是静态查找表时，宜用向量。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序作；若有序表是动态查找表，则应选择二叉排序树作为其存储结构。树作为其存储结构。38- - 树树 nB- B- 树的定义树的定义n一棵一棵m(m3)m(m3)阶的阶的B-B-树是满足如下性质的树是满足如下性质的m m叉树：叉树：n(1)(
33、1)每个结点至少包含下列数据域：每个结点至少包含下列数据域：n (n (n，P P0 0，K Kl l，P P1 1，K K2 2，K Ki i，P Pi i) )n其中：其中：n n n为关键字总数为关键字总数n K Ki i(1ij)(1ij)是关键字，关键字序列递增是关键字，关键字序列递增有序：有序：K K1 1 K K2 2Kkeynum；Kkeyi;i-)；nif(i0&T-keyi=1)n*pos=i；nreturnT；nnif(!T-soni)nreturnNULL；nDiskRead(T-soni)；nreturnSearchBTree(T-Soni，k，pos)；n43n查找
34、操作的时间开销查找操作的时间开销 B- B-树上的查找有两个基本步骤：树上的查找有两个基本步骤：n在在B-B-树中查找结点，该查找涉及读盘树中查找结点，该查找涉及读盘DiskReadDiskRead操作，属外查找；操作，属外查找；n在结点内查找，该查找属内查找。在结点内查找，该查找属内查找。n查找操作的时间为：查找操作的时间为：n外查找的读盘次数不超过树高外查找的读盘次数不超过树高h h，故其，故其时间是时间是O(h)O(h)；n内查找中，每个结点内的关键字数目内查找中，每个结点内的关键字数目keynummkeynumm(m(m是是B-B-树的阶数树的阶数) )，故其时间为，故其时间为O(nh
35、)O(nh)。44nB-B-树的插入和生成树的插入和生成nB-B-树的生成是从空树起，逐个插入关键字而得到树的生成是从空树起，逐个插入关键字而得到的。的。n（1 1）插入关键字插入关键字K K的方法的方法n 首先在树中查找首先在树中查找K K，若找到则直接返回，若找到则直接返回( (假设不处理相同关键字的插入假设不处理相同关键字的插入) )；否则查找操作；否则查找操作必失败于某个叶子上，然后将必失败于某个叶子上，然后将K K插入该叶子中。插入该叶子中。若该叶子结点原来是非满若该叶子结点原来是非满( (指指keynumMaxkeynumkeynumMinx-keynumMin，则只需删去，则只需
36、删去K K及及其右指针其右指针(*x(*x是叶子，是叶子，K K的右指针为空的右指针为空) )即可使删即可使删除操作结束。除操作结束。n 情形二情形二：若：若x-keynum=Minx-keynum=Min，该叶子中的关键字，该叶子中的关键字个数已是最小值，删个数已是最小值，删K K及其右指针后会破坏及其右指针后会破坏B-B-树树的性质的性质(3)(3)。若。若*x*x的左的左( (或右或右) )邻兄弟结点邻兄弟结点*y*y中的中的关键字数目大于关键字数目大于MinMin，则将，则将*y*y中的最大中的最大( (或最小或最小) )关键字上移至双亲结点关键字上移至双亲结点*parent*pare
37、nt中，而将中，而将*parent*parent中相应的关键字下移至中相应的关键字下移至x x中。中。 49n情形三情形三：若：若*x*x及其相邻的左右兄弟及其相邻的左右兄弟( (也可能只有一个兄弟也可能只有一个兄弟) )中的关键字数中的关键字数目均为最小值目均为最小值MinMin，则上述的移动操，则上述的移动操作就不奏效，此时须作就不奏效，此时须*x*x和左或右兄弟和左或右兄弟合并。合并。 50 B B树中删除关键字树中删除关键字6 6，7 7的过程的过程 126897521513127985215131258 9 2151351n性能分析性能分析nn个结点的平衡的二叉排序的高度个结点的平衡
38、的二叉排序的高度H H（即（即loglog2 2n n）比）比B-B-树的高度树的高度h h约大约大loglog2 2t t倍。倍。n例如例如m=1024m=1024，则，则loglog2 2t=logt=log2 2512=9512=9。此时若。此时若B-B-树树高度为高度为4 4，则平衡的二叉排序树的高度约为，则平衡的二叉排序树的高度约为3636。显然，若显然，若m m越大，则越大，则B-B-树高度越小。树高度越小。n若要作为内存中的查找表，则若要作为内存中的查找表，则B-B-树却不一定树却不一定比平衡的二叉排序树好，尤其当比平衡的二叉排序树好，尤其当m m较大时更是较大时更是如此。如此。
39、528.4 8.4 散列表的查找散列表的查找n散列表散列表(Hash Table)(Hash Table)散列是一种重要的存储方法，也是一种散列是一种重要的存储方法，也是一种常见的查找方法。散列的基本思想是：以结点常见的查找方法。散列的基本思想是：以结点的关键字的关键字K K为自变量，通过一个确定的函数为自变量，通过一个确定的函数（即映射）关系（即映射）关系h h，计算出对应的函数值，计算出对应的函数值h(K)h(K)，然后把这个值解释为结点的存储地址，将结，然后把这个值解释为结点的存储地址，将结点存入点存入h(K)h(K)所指的存储位置上。在查找时，根所指的存储位置上。在查找时，根据要查找的
40、关键字用同一函数据要查找的关键字用同一函数h h计算出地址，计算出地址，再到相应的单元里去取要找的结点。因此，再到相应的单元里去取要找的结点。因此，散散列方法列方法又称为关键字又称为关键字- -地址转换法，用散列方地址转换法，用散列方法存储的线性表称为法存储的线性表称为散列表散列表(Hash Table)(Hash Table)，也，也称称哈希表哈希表或或杂凑表杂凑表。上述的函数。上述的函数h h称为称为散列函散列函数数，h(K)h(K)称为称为散列地址散列地址。 53 通常散列表的存储空间是一个一维数组，散列地址是该数组的下标。在不会引起混淆的情况下，我们就将这个一维数组简称为散列表。 例例
41、8.98.9 以城市名或省名的拼音作为关键字K，散列函数h(K)为取K的首字母在字母表中的序号，可得散列地址如下：54n散列表的冲突现象散列表的冲突现象（1 1）冲突）冲突 两个不同的关键字，由于散列函数值两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称相同，因而被映射到同一表位置上。该现象称为为冲突冲突(Collision)(Collision)或碰撞。发生冲突的两个或碰撞。发生冲突的两个关键字称为该散列函数的同义词关键字称为该散列函数的同义词(Synonym)(Synonym)。 n（2 2）安全避免冲突的条件）安全避免冲突的条件n最理想的解决冲突的方法是安全避免冲
42、突。要最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：做到这一点必须满足两个条件：关键字的个数小于或等于散列表的长度；关键字的个数小于或等于散列表的长度；选择合适的散列函数。选择合适的散列函数。 55n（3）冲突不可能完全避免n 通常情况下，由于关键字的个数大于散列表的长度，因此，无论怎样设计h，也不可能完全避免冲突。我们只能做到，在设计h时尽可能使冲突最少，同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到散列表中。 n（4）影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关。n 设m表示散列表的表长，n表示表中填入的结点个数，则将=n/m定义为散
43、列表的装填因子装填因子(Load Factor)。越大，表越满，冲突的机会也越大。通常取1。 56常用散列函数常用散列函数n平方取中法平方取中法n具体方法：先通过求关键字的平方值具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列每一位都相关，所以由此产生的散列地址较为均匀。地址较为均匀。57n除留余数法除留余数法 n该方法是最为简单常用的一种方法。该方法是最为简单常用的一种方法。它是以表长它
44、是以表长m m来除关键字，取其余数来除关键字，取其余数作为散列地址，即作为散列地址，即 h(key)=key h(key)=keym mn该方法的关键是选取该方法的关键是选取m m。选取的。选取的m m应使应使得散列函数值尽可能与关键字的各位得散列函数值尽可能与关键字的各位相关。相关。m m最好为素数。最好为素数。58n相乘取整法相乘取整法n该方法包括两个步骤：首先用关该方法包括两个步骤：首先用关键字键字keykey乘上某个常数乘上某个常数A(0A1)A(0A1)，并，并抽取出抽取出key.Akey.A的小数部分；然后用的小数部分；然后用m m乘乘以该小数后取整。即：以该小数后取整。即：n该方
45、法最大的优点是选取该方法最大的优点是选取m m不再不再像除余法那样关键像除余法那样关键 59n随机数法随机数法n选择一个随机函数，取关键字的选择一个随机函数，取关键字的随机函数值为它的散列地址，即随机函数值为它的散列地址，即n h(key)=random(key)h(key)=random(key)n其中其中randomrandom为伪随机函数，但要为伪随机函数，但要保证函数值是在保证函数值是在0 0到到m-1m-1之间。之间。60处理冲突的方法处理冲突的方法 （1 1）用开放地址法解决冲突用开放地址法解决冲突n做法是：当冲突发生时，使用某种探查做法是：当冲突发生时，使用某种探查( (亦称亦称
46、探测探测) )技术在散列表中形成一个探查技术在散列表中形成一个探查( (测测) )序列。序列。沿此序列逐个单元地查找，直到找到给定的关沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址键字，或者碰到一个开放的地址( (即该地址单即该地址单元为空元为空) )为止（若要插入，在探查到开放的地为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。关键字，即查找失败。1、开放地址法61（2 2）开放地址法的一般形式）开放地址
47、法的一般形式n开放定址法的一般形式为：开放定址法的一般形式为： h hi i=(h(key)+d=(h(key)+di i) )m 1im-1m 1im-1（3 3）开放地址法堆装填因子的要求）开放地址法堆装填因子的要求n开放定址法要求散列表的装填因开放定址法要求散列表的装填因子子ll，实用中取，实用中取为为0.50.5到到0.90.9之之间的某个值为宜。间的某个值为宜。62n（4 4）形成探测序列的方法）形成探测序列的方法n按照形成探查序列的方法不同，可将开放定址按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。法区分为线性探查法、二次探查法、双重散列法等
48、。n线性探查法线性探查法(Linear Probing)(Linear Probing)n该方法的基本思想是：该方法的基本思想是：n将散列表将散列表T0.m-1T0.m-1看成是一个循环向量，若初看成是一个循环向量，若初始探查的地址为始探查的地址为d(d(即即h(key)=d)h(key)=d)，则最长的探查序列，则最长的探查序列为：为：n d d，d+ld+l，d+2d+2，m-1m-1，0 0，1 1，d-1d-1n即即: :探查时从地址探查时从地址d d开始，首先探查开始，首先探查TdTd，然后，然后依次探查依次探查Td+1Td+1，直到，直到Tm-1Tm-1，此后又循环到，此后又循环到
49、T0T0，T1T1，直到探查到，直到探查到Td-1Td-1为止。为止。63n二次探查法二次探查法( (Quadratic Probing)Quadratic Probing)n 二次探查法的探查序列是：二次探查法的探查序列是：n h hi i=(h(key)+i*i)=(h(key)+i*i)m mn 0im-1 0im-1 ，即，即d di i=i=i2 2n 即探查序列为即探查序列为d=h(key)d=h(key)，d+1d+12 2，d+2d+22 2，等。，等。n 该方法的缺陷是不易探查该方法的缺陷是不易探查到整个散列空间。到整个散列空间。64n双重散列法双重散列法(Double Ha
50、shing)(Double Hashing)n 该方法是开放定址法中最该方法是开放定址法中最好的方法之一，它的探查序列是：好的方法之一，它的探查序列是：n hi=(h(key)+i*h1(key)hi=(h(key)+i*h1(key)m mn 0im-1 0im-1，即，即d di i=i*h1(key)=i*h1(key)n 即探查序列为：即探查序列为：n d=h(key) d=h(key)，(d+h1(key)(d+h1(key)m m，(d+2h1(key)(d+2h1(key)m m，等。，等。65n2、拉链法处理冲突拉链法处理冲突n拉链法解决冲突的做法是：将所有关拉链法解决冲突的做
51、法是：将所有关键字为同义词的结点链接在同一个单键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为链表中。若选定的散列表长度为m m，则，则可将散列表定义为一个由可将散列表定义为一个由m m个头指针组个头指针组成的指针数组成的指针数组T0.m-1T0.m-1。凡是散列地。凡是散列地址为址为i i的结点，均插入到以的结点，均插入到以TiTi为头指为头指针的单链表中。针的单链表中。T T中各分量的初值均应中各分量的初值均应为空指针。在拉链法中，装填因子为空指针。在拉链法中，装填因子可以大于可以大于1 1，但一般均取，但一般均取11。66例：例：已知一组已知一组关键字为（关键字为（2626，
52、3636，4141，3838，4444，1515，6868，1212，0606，5151），取表），取表长为长为1313，用拉链用拉链法解决冲突构造法解决冲突构造这组关键字的散这组关键字的散列表，如右图所列表，如右图所示。示。 012345869710111226 1541 1236 68 06 3844 51 67n拉链法的优点拉链法的优点n(1)(1)拉链法处理冲突简单，且无堆积现象，即非拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；同义词决不会发生冲突，因此平均查找长度较短；n(2)(2)由于拉链法中各链表上的结点空间是动态申由于拉链法中各链表上的结点
53、空间是动态申请的，故它更适合于造表前无法确定表长的情况；请的，故它更适合于造表前无法确定表长的情况；n(3)(3)开放定址法为减少冲突，要求装填因子开放定址法为减少冲突，要求装填因子较较小，故当结点规模较大时会浪费很多空间。而拉小，故当结点规模较大时会浪费很多空间。而拉链法中可取链法中可取11，且结点较大时，拉链法中增，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；加的指针域可忽略不计，因此节省空间；n(4)(4)在用拉链法构造的散列表中，删除结点的操在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点作易于实现。只要简单地删去链表上相应的结点即可。即
54、可。 68n拉链法的缺点拉链法的缺点n拉链法的缺点是：指针需要额外的空拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。中的冲突，从而提高平均查找速度。 69散列表上的运算散列表上的运算 n散列表类型说明：散列表类型说明：n#defineNIL-1n#definem997ntypedefstructnKeyTypekey；nIn
55、foTypeotherinfo；nNodeType；ntypedefNodeTypeHashTablem；70n基于开放地址法的查找算法基于开放地址法的查找算法n 散列表的查找过程和建表过程相似。假散列表的查找过程和建表过程相似。假设给定的值为设给定的值为K K，根据建表时设定的散列，根据建表时设定的散列函数函数h h，计算出散列地址，计算出散列地址h(K)h(K)，若表中该，若表中该地址单元为空，则查找失败；否则将该地地址单元为空，则查找失败；否则将该地址中的结点与给定值址中的结点与给定值K K比较。若相等则查比较。若相等则查找成功，否则按建表时设定的处理冲突的找成功，否则按建表时设定的处理
56、冲突的方法找下一个地址方法找下一个地址, ,如此反复进行，直到如此反复进行，直到某个地址单元为空某个地址单元为空( (查找失败查找失败) )或者关键字或者关键字比较相等比较相等( (查找成功查找成功) )为止。为止。 71n开放地址法一般形式的函数表示开放地址法一般形式的函数表示nintHash(KeyTypek，inti)nreturn(h(K)+Increment(i)m；nn 若散列函数用除留余数法构造，并假设使若散列函数用除留余数法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数用线性探查的开放定址法处理冲突，则上述函数中的中的h(K)h(K)和和Increment(i)Inc
57、rement(i)可定义为：可定义为：ninth(KeyTypeK)nreturnKm；nnintIncrement(inti)nreturni;/n72n通用的开放定址法的散列表查找算法：通用的开放定址法的散列表查找算法：nintHashSearch(HashTableT，KeyTypeK，int*pos)nninti=0；ndon*pos=Hash(K，i)；nif(T*pos.key=K)returnl；nif(T*pos.key=NIL)return0；nwhile(+i0)nprintf(duplicatekey!)；nelsenError(hashtableoverflow!)；n
58、voidCreateHashTable(HashTableT，NodeTypeA，intn)nnintinif(nm)nError(Loadfactor1)；nfor(i=0;im；i+)nTi.key=NIL；nfor(i=0;in；i+)nHashlnsert(T，Ai)；n74n删除删除n基于开放定址法的散列表不宜执行散列表基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为则不能将被删结点的关键字置为NILNIL，而，而应该将其置为特定的标记应该将其置为特定的标记DELETEDDELETED。n一般
59、情况下，当必须对散列表做删除结点一般情况下，当必须对散列表做删除结点的操作时，是采用拉链法来解决冲突。的操作时，是采用拉链法来解决冲突。 75n性能分析性能分析n因插入和删除的时间均取决于查找，因插入和删除的时间均取决于查找，故只要分析查找操作的时间性能。故只要分析查找操作的时间性能。n虽然散列表在关键字和存储位置之间虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的二分查找等完全依赖于关键字比较的查找要小得多。查找要小得多。76
