1、第八章 查找 查找在计算机信息处理、数据库查询等方面均有广泛的应用。查找算法的优劣和能否针对不同要求来选用恰当的查找算法，直接影响到查找效率。在一个数据集合中进行查找所使用的方法与该数据集合的存储结构密切相关。查找的基本概念线性表的查找树表的查找哈希表及其查找小结 over查找的基本概念 查找就是在数据元素(记录)集合中找出“满足查找要求”的数据元素(记录)。查找表(search table)-指同一类型的记录构成的集合。关键字(key)-记录中某个数据项的值，用它可以识别、确定一个记录。主关键字(primary key)-指查找表中能唯一地确定一个记录的关键字。next 次关键字(secon
2、dary key)-指查找表中能够确定多个记录的关键字。查找(searching)-给定一个确定的值，在查找表中确定一个记录，其相应的关键字等于给定值的操作。查找的结果有两种：查找成功和查找失败。查找表分为：静态查找表和动态查找表两种。静态查找表-指只查询给定记录是否存在于表中或检索某个特定记录的有关属性。动态查找表-除上之外，还可以对表进行插入、删除或修改操作。next 基于比较的查找算法的执行时间取决于给定值和关键字的比较次数，通常以比较次数的平均值作为衡量算法的依据，称其为算法在查找成功时的平均查找长度(Average Search Length，简记为ASL)。若查找表有n个记录，则
3、其中：pi位在查找表中查找第i个记录的概率niiipcASL1back线性表的查找 说明：本节讨论的是数组实现的顺序表 记录结构：typedef struct int key;NODE;顺序表下的三种查找方法：顺序查找折半查找分块查找back顺序查找(sequential search)方法：从顺序表的一端开始，将给定值依次与数组中各个记录的关键字进行比较，若在表中找到某个记录的key与给定值相等，则查找成功，返回记录所在下标；若查找失败则给出失败信息。适用：顺序表中记录的关键字无序的情况。基本算法8-1 改进算法8-2 性能分析back 算法8-1 p163 int search(NODE
4、a,int n,int k)int i=0;while(i=n)return-1;else return i;back 顺序查找的基本操作是关键字的比较。查找成功的最好情况是第一个记录就是所查，比较一次即可；查找成功最坏的情况是第n个记录符合要求，进行n次比较。若查找概率相等，即pi=1/n，则顺序查找成功的平均查找长度为：对算法8-2，查找不成功的比较次数为n+1，顺序查找算法的时间复杂度为O(n)。niniiinninpcASL112211back折半查找(binary search)(二分查找)适用：查找表中记录关键字值有序。查找过程：(顺序表记录关键字升序排列)设low、mid、hig
5、h指向表当前待查范围的下、中和上界。初始：给定查找值为k，low=0，high=n-1，mid=比较，若k=amid.key，成功；若kamid.key，令low=mid+1，继续查找；比较，若lowhigh，重复执行，否则查找完毕，若无满足记录则查找失败。2/)(highlow next搜索成功的例子搜索成功的例子 搜索失败的例子搜索失败的例子next 例8-1 顺序表8,11,18,28,45,55,63,80，用折半查找的方法查找55和22的记录。查找55过程：初始low=0,high=7,mid=(0+7)/2=3 下标 0 1 2 3 4 5 6 7 low mid high 比较,
6、(k=55)(amid.key=28),令low=mid+1=4,high=7,mid=(4+7)/2=5 下标 0 1 2 3 4 5 6 7 low mid high 比较,(k=55)=(amid.key=55),查找成功,返回5811 18 28 45 55 63 80811 18 28 45 55 63 80next 算法8-3 p166 int Binary_Search(NODE a,int n,int k)int low=0,high=n-1,mid;while(low=high)mid=(low+high)/2;if(amid.key=k)return mid;else if
7、(amid.keyk)low=mid+1;eles high=mid-1;return-1;next 折半查找过程可用一棵二叉树表示：树中每个结点对应于查找表中一个记录，结点值为相应记录在查找表中的位置值，根结点值是查找表中间元素下标；左子树结点是key中间元素的右子表，右子树的根结点是右子表的中间元素的下标 依此类推得到相应的判定树。next从有序表构造出的判定树next 在等概率条件下，可求得成功查找的平均查找长度。例：上图ASL=(1+2*2+3*4+4*2)/9=25/93 当查找成功时，最好情况是比较1次。查到每个记录的比较次数=该结点在判定树中的深度。折半查找算法的时间复杂度为O(
8、log2n)。back分块查找(索引顺序查找)是顺序查找的一种改进，在分块查找时，把表内记录按某种属性分成n(1)个块(子表)，且块间有序，即后一块中所有记录key值前一块重所有记录key值，而块内key值可以无序。建立一相应“索引表”，由若干索引记录组成，每个索引记录对应一个块。索引记录包括两个数据项：对应块内最大key值和块中第一个记录位置的地址指针。next 分块查找的步骤：对索引表进行查找以确定给定值所在的块，因为索引表有序，可用顺序查找或折半查找；在确定的块中查找给定的值，块内不一定有序，所以一般用顺序查找。例：子表数据分开存储next 例8-2 线性表16,22,5,11,66,3
9、8,62,88,1009个元素，用分块查找法查找66的数据元素。索引表 块内最大关键字值 块的起始地址 下标 0 1 2 3 4 5 6 7 8 线性表分为3块，每块3个元素。给定值k=66，与索引表中各块内最大key值比较，100k62，可判定在第三块中查找，直至成功或失败。1662100036165112238626688 100back树表的查找 树表查找是指查找表用二叉树表示，存储结构采用二叉链表，链表中每个结点对应查找表中一个记录。二叉排序树的定义 二叉排序树的查找 二叉排序树的插入和删除back二叉排序树(binary sort tree)的定义 或者是一棵空树，或者具有下列性质的
10、二叉树：若它的左子树非空，则在左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则在右子树的所有结点的值都大于等于根结点的值；左右子树也分别是一棵二叉排序树。简而言之，二叉排序树每个结点的值都大于它的左子树上的所有结点的值，而小于等于它的右子树上所有结点的值。对二叉排序树进行中序遍历即可得到从小到大的有序序列。back二叉排序树的查找 具体做法：当二叉排序树非空时，将给定值k与根的key比较，若相等则表示查找成功；否则，若kkey!=k)if(kkey)p=p-left;else p=p-right;if(!p)break;return p;back二叉排序树的插入和删除 按照一定规
11、则在二叉排序树上插入、删除结点仍能保持二叉排序树的性质。只要解决了插入问题，也就解决了建树过程，因为建树过程就是从空树开始逐次插入新结点的过程。用二叉排序树插入算法生成的二叉排序树，其形状、高度不仅依赖于关键字值的大小和数量，还与记录输入的先后次序有关系。next 插入的具体做法：动态生成一新结点p，若二叉排序树root为空，则作为根结点插入；若非空，则比较，若p-keykey则插入左子树，否则插入右子树。在左或右子树上进行同样的操作，实际是一个递归的过程。最后p的插入位置是二叉排序树中某结点的空指针位置。新结点p是作为叶结点插入，所以新结点插入时其左右子指针均为NULL。next 算法8-5
12、 二叉排序树中插入新结点的非递归算法 p170-171#include#include#define MAX 5 Bnode*btInsert(int x,Bnode*root);void main()int i,aMAX=60,40,70,20,80;Bnode*root=NULL;for(i=0;ikey=x;p-left=p-right=NULL;if(!root)root=p;return p;q=root;while(!flag)if(q-key x)if(q-left)q=q-left;else q-left=p;flag=1;else if(q-right)q=q-right;e
13、lse q-right=p;flag=1;return root;next 在二叉排序树上删除一个结点p，分四种情况：若p是叶结点，直接删除即可；若p只有右子树没有左子树，直接将其右子树的根结点放到被删位置上即可；若p只有左子树没有右子树，直接将其左子树的根结点放到被删位置上即可；若p既有左右子树，找p右子树key最小结点s，用s取代p的位置，用s右子树的根结点取代s的位置。二叉排序树的平均查找长度为O(log2n)。二叉排序树适用于经常要进行插入删除操作的查找表。back哈希(Hash)表及其查找 指通过待查记录的key进行相应的计算就能找到要查找记录的方法。这需要在待查记录的key与该记录
14、的存储位置之间建立确定的对应关系。哈希表的基本概念 哈希函数的构造方法 处理冲突的方法back 哈希函数-p174 是记录的关键字值与该记录的存储地址之间所构造的对应关系。哈希表-p174 是用来存放查找表中记录序列的表，每一个记录的存储位置是以该记录的关键字为自变量，由相应哈希函数计算所得到的函数值。要保证哈希表查找能正确操作，必须保证记录的存放规则和查找规则一致，即是用相同的哈希函数。next 例子：将关键字序列8,10,14,21存储到编号为0到4的表长为5的哈希表中，哈希函数为H(Ki)=Ki mod 5，Ki是关键字值。哈希表结构如：0 1 2 3 4 冲突(collision)-p
15、174 指不同的关键字值具有相同的哈希地址。同义词(synonym)-p174 指对应一个哈希函数具有相同函数值的的关键字。1021814back哈希函数的构造方法 哈希函数的构造，与key长度、哈希表大小、key的实际取值状况等多种因素有关。直接定址法：当key是正数时，取key本身或者它的某个线性函数作为它的哈希地址，即：H(K)=K 或者 H(K)=ak+b(a、b为常数)该方法简单，key取值不同时不会产生冲突，但是，它要求散列地址空间的大小与关键码集合的大小相同。若key分布不连续则哈希表会造成空间大量浪费。实际少用。next例：有一组关键码942148,941269,940527,
16、941630,941805,941558,942047,940001。散列函数为Hash(key)=key940000 则有 Hash(942148)=2148 Hash(941269)=1269 Hash(940527)=527 Hash(941630)=1630 Hash(941805)=1805 Hash(941558)=1558 Hash(942047)=2047 Hash(940001)=1 可以按计算出的地址存放记录。next 平方取中法：一种较好的方法 先计算key的平方值，再取其平方值的中间若干位作为哈希地址，即：H(K)=“K的平方值的中间几位”key平方后其中间几位和组成k
17、ey的各位均有关系，使得哈希地址的分布较为均匀，减少了发生冲突的可能。其所取的位数取决于哈希表的长度。例：K1=11052501,K2=11052502,计算出K12=122157778355001,K22=122157800460004,取左起第7到第9位作为哈希地址。next 除留余数法：最简单最常用的方法 选一个合适的不大于哈希表长度的正整数P，用P去除关键字K，得到余数作为哈希地址，即：H(K)=K mod P 这样可以保证哈希函数的值在有效地址空间之内。该方法的好坏取决于P值得选择，当P取小于哈希表长度的最大质数时，产生的哈希函数比较好。next 例：有一个关键码key=962148
18、，散列表大小 m=25，即HT25。取质数p=23。散列函数 hash(key)=key%p。则散列地址为 hash(962148)=962148%23=12。可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是0到22，因此，从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。next 数字分析法：设key有d位，对各个key的每位进行分析，选取key中取值较均匀的若干位作为哈希地址。计算key中符号分布的均匀度 k的公式：其中，表示第i个符号在第k位上出现的次数，n/r表示各种符号在n个数中均匀出现的期望值。计算
19、出的k值越小，表明在该位(第k位)各种符号分布得越均匀。rikikrn12)/(kinext 若散列表地址范围有3位数字,取各关键码的位做为记录的散列地址。也可以把第和第位相加，舍去进位位，变成一位数，与第位合起来作为散列地址。还有其它方法。next 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。随即数法：适用于key长度不等的情况 取key的随机函数作为它的哈希地址，即：H(K)=random(K)其中random()为取随机数的函数。back处理冲突的方法 在实际应用中，不论选择何种哈希函数，都不可能完
20、全避免冲突。下面介绍两种处理冲突的方法：链地址法 开放地址法链地址法 这种方法是把具有相同哈希地址的key的值存放在一个链表中，哈希表中的每个单元所存放的不是key的值，而是相应单链表的指针。例：给出一组表项关键码Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly。散列函数为：Hash(x)ord(x)ord(A)。next 用哈希函数计算可得：Hash(Burke)=1 Hash(Ekers)=4 Hash(Broad)=1 Hash(Blum)=1 Hash(Attlee)=0 Hash(Hecht)=7 Hash(Alton)=0Hash(E
21、derly)=4 散列表为 HT0.25，m=26。采用链地址发法处理冲突，则上述关键码在散列表中的散列位置如图所示。nextnext 该方法适合于冲突现象比较严重的情况，能够较好解决溢出问题，也很容易实现插入和删除操组。不足，除了哈希表的存储空间外，还增加了链域空间。如果哈希函数的均匀性较差，会造成存储单元的浪费。back开放地址法 开放地址法是在冲突发生时，按照某种方法继续探测表中其它存储单元，直到找到空位置为止。如：Hi(K)=(H(K)+di)mod m(i=1,2,3,k(km-1)其中Hi(K)为在探测到的地址，H(K)为关键字K的直接哈希地址，m为哈希表长，di为再探测时的地址增
22、量。next 首先计算key的直接哈希地址H(K)，若该单元已被占用则继续探测地址为H(K)+d1单元，若也被占用，再继续探测地址为H(K)+d2单元，直到发现某个单元为空，停止探测，将记录存放其中。增量di的取法有三种：线性探测再散列：di=1,2,3,.；二次探测再散列：di=12,-12,22,-22,；伪随机再散列：di=伪随机序列。next 例8-7 八个记录的哈希地址分别为：H(K1)=2,H(K2)=2,H(K3)=3,H(K4)=3,H(K5)=8,H(K6)=0,H(K7)=7,H(K8)=8 存入表长为10的哈希表A中。用线性探测再散列法来构造哈希表，结果如下：0 1 2
23、3 4 5 6 7 8 9 在用开放地址发构造哈希表时，可能会产生由非哈希函数所引起的冲突。k6k1k2k3k4k7k5k8back小结 查找表是同一类型的记录构成的集合，查找就是给定一个确定的值，在查找表确定一个记录，其key就等于给定值的操作。顺序查找的查表表为线性表，存储结构为顺序表。若查找表长度为n，它的平均查找长度为(n+1)/2，查找方法是顺序比较。next 折半查找要求查找表为有序的线性表，存储结构为有序的顺序表，它的时间复杂度为O(log2n)。查找方法是逐次取中、比较、确定新查找区间。描述折半查找过程的二叉树称为折半查找找的判定树，通过它能容易得到查找某元素的比较次数和等概率条件下的成功查找的平均查找长度，构造判定树的方法是逐次取序列和子序列中间记录的下标。next 二叉排序树是用递归定义的方式给出的，3个条件缺一不可。查找表用二叉排序树表示的方法是按照定义逐个插入，在二叉排序树上查找时逐次用待查值与根或子树的根做比较，确定查找范围(子表)。对二叉排序树进行中序遍历可以得到一个有序序列。散列查找的原理是在待查记录的key值与该记录的存储位置之间建立确定的对应关系。实现方法是通过哈希函数、哈希表。back
