数据结构第8章查找

数据结构（C语言版）第8章查找本章主要知识点静态查找表动态查找表哈希表

查找是在一个数据元素集合中查找是否存在与某个给定属性值相等的数据元素的过程。每一个数据元素都有若干个属性，这些属性值作为查找条件时可以称为关键字。关键字有主次之分，主关键字是指能够唯一标识这个数据元素的关键字，次关键字通常不能唯一区分各个不同的数据元素。查找的结果分为查找成功和查找不成功。查找通常分为静态查找和动态查找。如果在数据元素集合中只查询某个特定的数据元素是否存在，不进行插入或删操作称为静态查找；如果在查询的过程中同时插入数据元素集合中不存在的数据元素，或者从数据元素集合中删除已经存在的某个数据元素则称为动态查找。

静态查找表

1顺序表的查找

执行过程：对于给定关键字，从顺序表的一端开始，逐个和各数据元素的关键字进行比较，如果某个数据元素的关键字和给定的关键字相同，则查找成功；反之，如果所有数据元素的关键字和给定关键字都不相等，则查找不成功。int

SearchSeq(Seqlist

S,KeyTypet){

inti;

for(i=0;i<S.size;i++)

if(t.key==S.list[i]){returni;break;}

if(i==S.size)return-1;}有n个数据元素的顺序表，其平均查找长度：=1/n

顺序表在查找成功时，平均需要查找半个表长的元素；查找不成功时，需要比较完全部的数据元素才能确定，所以其比较的次数为n+1。2有序表的查找

顺序表中的元素按关键字已经排序（递增或递减），该查找表称为有序表。针对有序表通常使用折半查找来提高效率。

折半查找又称为二分查找。折半查找仅针对用顺序结构存储的有序表才可操作。查找过程：在确定的待查找区间中，先将待查找元素的关键字和中间位置元素关键字进行比较，如果相等，则查找成功。否则，如果待查找元素的关键字小于中间元素的关键字，则在前半部分进行查找；如果待查找元素的关键字大于中间元素的关键字，则在后半部分进行查找，重复以上操作，直到查找成功或者失败为止。int

SearchBin(SeqlistS,KeyTypet){int

mid,low=0,high=S.size-1;

while(low<=high){mid=(low+high)/2;

if(t.key==S.list[mid].key)returnmid;elseif(t.key>S.list[mid].key)low=mid+1;elsehigh=mid-1;}return-1;}当有序表包含n个数据元素时，折半查找过程可以对应一棵完全二叉树。该完全二叉树的结点总数为n，根节点对应中间元素，其左子树对应有序表的前半部分，其右子树对应有序表的后半部分。该二叉树的深度为：当要查找的数据元素在有序表中出现的概率相等时，有序表在查找成功时算法的平均查找长度为：3索引顺序表的查找包含所有数据元素的顺序表叫主表，索引表则用来存放主表中所要查找元素的关键字和位置信息。要求主表中数据的关键字分段有序，索引表是选取的每段的最大值，而主表中数据的关键字分段有序，所以索引表是一有序表。

主表中的数据元素个数非常庞大时，索引表本身也很庞大，此时可对索引表再继续建立索引表，这样的索引表称作二级索引表。同样的方法还可以在二级索引表上再建立三级索引表。

查找过程：首先将待查数据关键字和索引表中的关键字进行比较，得以确定待查数据所在主表的哪一部分；然后在主表中所在部分根据顺序查找法进行查找。索引顺序表的查找算法可以分成在主表和索引表两部分中查找。假定索引表的长度为a，主表中每个子表的长度为b，若都使用顺序查找法，则平均查找长度为：

ASL=(a+1)/2+(b+1)/2=(a+b)/2+1

若在查找索引表时用折半查找法，查找主表时使用顺序查找法，则平均查找长度为：

ASL=log2a+(b+1)/2动态查找表

1二叉排序树和平衡二叉树

二叉排序树或者是一颗空树，或者是具有如下性质的二叉树：

(1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

(2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

(3)其左右子树也是一颗二叉排序树。二叉排序树特性：进行中序遍历可得到递增序列。结点结构定义：

typedef

structnode{

ElemTypeData;

structnode*lchild;

structnode*rchild;}BitreeNode;433767514133404337675133二叉排序树的查找过程：如果二叉排序树非空，先将给定关键字和根结点关键字进行比较，如果相等，则查找成功；否则，如果小于根结点关键字，则在左子树上继续查找；如果大于根结点关键字，则在右子树上继续查找，直到查找成功或者失败为止。int

SearchBitree(BitreeNode*t,ElemTypek){ BitreeNode*p;

if(t!=null){p=t;

while(p){if(p->data==k)return1;elseif(p->data>k)p=p->lchild;elsep=p->rchild;}} return0;}43376751413340查找成功的平均查找长度为：4337675133查找成功的平均查找长度为：有n个结点的二叉排序树的平均查找长度和树的形态有关，最坏的情况是当二叉排序树是一棵单分支斜树时，则其平均查找长度为(n+1)/2；较优情况是当二叉排序树是完全二叉树时，其平均查找长度和折半查找的查找长度相同，为log2n。

二叉排序树的插入过程：若二叉排序树非空，先将给定关键字和根结点关键字进行比较，如果相等，则停止插入操作并返回；否则，如果小于根结点关键字，则在左子树上搜得合适位置插入该元素；如果大于根结点关键字，则在右子树上搜得合适位置插入该元素。int

InsertBitree(BitreeNode**t,ElemTypek){BitreeNode*p=t,*q;

while(p!=NULL){if(p->data==k)return0;q=p;

if(p->data<k)p=p->rchild;elsep=p->lchild;}p=(BiTreeNode*)malloc(sizeof(BiTreeNode));p->data=k;p->rchild=NULL;p->lchild=NULL;

if(q==null)*t=p;elseif(k<q->data)q->lchild=p; elseq->rchild=p; return1;}给定关键字集合为{43、37、51、33、41、40、67}，构造一棵二叉排序树：

二叉排序树的删除过程：如果二叉排序树非空，则在该二叉排序树中查找给定数据元素是否存在，若不存在，则返回；若存在则：

(1)要删除的结点为叶子结点，则直接将其删除；

6743376751423338416043375142333841

(2)要删除的结点只有左子树，删除该结点并使被删除结点的双亲结点指向被删除结点的左孩子结点；4337675142333841604337675133384160

(3)要删除的结点只有右子树，删除该结点并使删除结点的双亲结点指向被删除结点的右孩子结点；

4337675142333841604337674233384160

(4)要删除的结点既有左子树，又有右子树，首先找出要删除结点右子树的最左结点，然后用该最左结点替换要删除的数据元素，最后以最左结点为参数继续调用删除函数。即要删结点右子树的最左结点。6743376751423338416043514233384160

平衡二叉树或者是一棵空树，或者是具有如下性质的二叉树：它的左、右子树都是平衡二叉树，并且任一结点的左、右子树深度之差的绝对值不大于1。结点的左、右子树深度之差被称为该结点的平衡因子。43376751413340433751413340是非如何构造平衡二叉树？（1）LL型调整（在A的左孩子的左子树上插入结点，使得A结点的平衡因子从1变成2）（2）RR型调整（在A的右孩子的右子树上插入结点，使得A结点的平衡因子从-1变成-2）（3）LR型调整（在A的左孩子的右子树上插入结点，使得A结点的平衡因子从1变成2）（4）RL型调整（在A的右孩子的左子树上插入结点，使得A结点的平衡因子从-1变成-2）假设以Nk表示深度为h的平衡树中含有的最少结点数。显然，N0=0，N1=1，N2=2，并且Nk=Nk-1+Nk-2+1，这个关系和斐波那契序列极为相似。利用归纳法容易证明：当h0时，Nk=Fk+2-1，而Fk

фk/(其中ф=(1+)/2)，则Nkфk+2/-1。反之，含有n个结点的平衡树的最大深度为logф((n+1))-2，因此，在平衡树上进行查找的时间复杂度为O(log2n)。

2B-树和B+树

一棵m阶的B-树，或者是空树，或者是具有以下性质的m叉树：

(1)树中每个结点至多有m棵子树；

(2)若根结点不是叶子结点，根结点至少有两个孩子结点；

(3)除根结点外，其他结点至少有m/2个孩子结点；

(4)每个结点包括以下信息：

(n，P0，K1，P1，K2，P2，……，Kn，Pn)其中：n为该结点中关键字的个数；Ki(i=1,……，n)为该结点的关键字，且满足条件Ki<Ki+1；Pi(i=1,……，n)为指向该结点孩子结点的指针，且Pi-1指针所指结点的关键字均小于或等于Ki；Pi指针所指子树所有结点的关键字均大于Ki。

(5)所有叶子结点都在同一层上，并且指针域为空。14315122337141130120149167

B-树上的结点可以含有m-1个关键字和m个指针，查找过程：将数据元素关键字和跟结点的若干个关键字逐个进行比较，如果相等，则查找成功返回；否则，将沿着指针继续查找下层结点。

B-树的生成从空树开始，逐个插入关键字得到。根据B-树的特点，其关键字的个数必须至少为m/2-1，但又不能超过m-1。每次插入时总是根据其大小在最底层某个叶子结点上添加一个关键字，如果该结点的关键字个数小于m-1，则直接插入，如果发现新插入关键字后，关键字总数超过m-1，则该结点必须分裂。

(1)假设结点q中已经有m-1个关键字，再插入一个关键字后就有m个关键字了，必须“分裂”：以m/2为界，将结点q分裂为q和q′，前面m/2-1个关键字所构成的一部分由q指向，后面一部分则由q′指向，而关键字Km/2

和指向q′的指针一起插入到q的双亲结点中去。

(2)检查双亲结点，如果双亲结点中也出现了(1)的情况，则回到步骤(1)继续对双亲结点执行“分裂”动作，直到最终符合要求不再“分裂”。3阶B-树的插入操作：

B-树在叶子结点上删除关键字：

(1)被删除关键字所在结点其关键字数目大于或等于m/2，则只需要直接删除该关键字，该结点的关键字数目大于或等于m/2-1；

(2)被删除关键字所在结点其关键字数目等于m/2-1，相邻的左右兄弟关键字数目至少有一方大于或等于m/2时，则可以向左/右兄弟去借关键字：如果右兄弟关键字数目大于或等于m/2，则将右兄弟中最小关键字上移到双亲结点中，然后将双亲结点中紧靠在上移关键字左边的那一个关键字移动到被删除关键字所在的结点的最右边；如果左兄弟的关键字数目大于或等于m/2，则将左兄弟中最大关键字上移到双亲结点中，然后将双亲结点中紧靠在该上移关键字右边的那一个关键字移动到被删除关键字所在的结点的最左边。

(3)被删除结点关键字数目等于m/2-1，相邻的左右兄弟关键字数目均等于m/2-1，则不可以向左/右兄弟去借关键字，那么就只能从双亲结点借关键字补充，可以参考非叶子结点的删除操作。

非叶子结点上删除关键字：

(1)被删除结点关键字数目大于或等于m/2，则删除关键字后，原来关键字的左右孩子进行合并，若合并后的结点关键字数目满足B-树性质，则结束，若合并后的结点关键字数目大于m-1，则需再一次分裂，将其中值居中的一个关键字移到当前结点中。

(2)被删除结点关键字数目等于m/2-1，相邻的左右兄弟关键字数目均为m/2-1，则删除该关键字之后首先判断能否从被删除的关键字的左右孩子中寻找关键字补充，如果其左右孩子的关键字数目均为m/2-1，且此结点已经是根结点，则直接将被删除关键字的左右孩子结点合并即可，如果此结点并不是根结点，则从自己的双亲补充关键字，然后重复上述(1)、(2)操作。

哈希表

哈希表的构造过程：对于要存储的m个数据元素，确定一个称为哈希函数的函数H(k)，将要存储元素的关键字k按照该函数进行计算后得到该元素的存储地址，并将该数据元素存储到存储地址对应的内存单元里。哈希函数H(k)实质上是关键字k到内存单元的映射，因此哈希表又叫散列表。哈希表是一种重要的查找技术，既适用于静态查找，又适用于动态查找，并且查找效率非常高。构造哈希表时，关键字k1≠k2，而H(k1)=H(k2)的情况称为哈希冲突。关键字不同而哈希地址相同的数据元素称为“同义词”，由同义词引起的冲突称作同义词冲突。构造哈希表时，同义词冲突很难避免，这时可通过哈希冲突函数来产生一个新的地址，使关键字不相同的数据元素的哈希地址不同。哈希冲突函数所产生的哈希地址仍可能发生冲突，此时可再使用下一个冲突函数得到新的哈希地址，直到不存在哈希冲突为止。哈希函数的构造

1.直接定址法直接定址法是根据数据元素关键字或关键字的某个线性函数值作为哈希地址的方法。直接定址法的哈希函数H(k)为：

H(k)=C*k+T(其中，C、T为常数)

使用直接定址法方便和简单，但有可能会造成内存单元的大量浪费。2、除留余数法除留余数法是用数据元素关键字除以哈希表长度得到的余数作为哈希地址的方法。除留余数法的哈希函数H(k)为：

H(k)=kmodn(其中n为哈希表长度)

除留余数法计算简单，是经常用到的一种哈希函数。除留余数法的关键是如何选取哈希表的长度n，如果长度n选取的不好，就会容易产生冲突。数据元素集合a={78,7,99,13,25,53,59,30}，哈希表长度n取11时，并不会产生哈希冲突；当n取9时，就会产生哈希冲突。通常情况下，哈希表的长度n习惯选取质数，确定了数据元素个数后，哈希表长度n一般选取比该数略大的质数，这样可以有效减少哈希冲突的发生。3、数字分析法数字分析法是通过对数据元素关键字中的数字进行分析，选取关键字中的部分数字作为哈希地址的方法。数字分析法适用于哈希表中数据元素关键字都已知的情况。例如，一组学生的学号：

201061310201061421201061571201061285201061713201061337201061222201061833201061603201061314

该组学号的前7位取值相对比较集中，剩下的后两位取值较均匀，可以直接使用学号的最后两位作为哈希地址，则不易产生哈希冲突，所以这十个关键字的哈希地址分别为：10、21、71、85、13、37、22、33、3、14。

4、平方取中法对数据元素关键字进行平方运算后取中间某几位作为哈希地址的方法。因为平方后中间几位和关键字中的每一位都有关系，因此不同的关键字会以较高的概率产生不同的哈希地址。处理冲突

1.开放定址法

a.线性探测再散列线性探测再散列公式：

Di=(H(k)+di)modm

其中：Di

为哈希函数，m为哈希表长度，di为增量序列,取1,2,3，……，m-1。线性探测再散列容易产生堆积问题，当出现多个同义词后，若第一个同义词占用内存单元a，后面的同义词将依次占用其后的内存空间，一旦随后有a+1等空间上的哈希地址时，将会再次产生冲突，这就是常说的“二次聚集”。

b.二次探测再散列二次探测再散列公式：