《数据结构（C#）》-第8章 查找

第8章

查找8.1顺序查找

8.2折半查找

8.3分块查找

8.4哈希法

1、查找的相关概念查找是计算机科学中研究的重要研究课题之一，在计算机应用系统中，在查找方面所花费的时间占系统运行总时间的25%，所以查找算法的合理应用，对系统的运行效率影响非常大。所谓查找（Search），就是在某一个数据表中，查找给定的数据是否能在数据表中找到。8.1顺序查找给定查找的数据称为关键字(Key)。查找得到的记录(Record)，每个数据项称为字段(Segment)或域(Field)。被查找的数据表称为查找表(SearchTable)。我们对查找表如果只进行查找操作，那么此类查找表称为静态查找表(StaticSearchTable)。我们如果对查找表进行插入和删除操作，那么此类查找表称为动态查找表(DynamicSearchTable)。在进行查找时，如果顺利找到某条记录，说明查找时成功的，否则查找失败。

顺序查找(SequnceSearch)又称线性查找(LinearSearch)，在查找表中，逐个查询各条记录，直到找到与关键字相符的记录为止，查询成功；如果整个查找表都查询完了，还没有找到与关键字相符的记录，查询失败。顺序查找概念例：假设有一组数据{3，5，8，23，57，2}，顺序的存放在数组Arr[i]中。现给定一个关键字57，查询数组中是否能找到57。顺序查找算法顺序查找的基本思路是：假设有n个记录，存放在数组Arr中，其中，第i个记录的值为Arr[i]，将给定的关键字x与数组中的记录逐个比较，如果找到要查询记录，则查找成功，并标出记录在表中的位置；否则，查找失败，给出失败提示。顺序查找算法的实现见教材。折半查找

折半查找(BinarySearch)又称为二分查找，跟顺序查找有所区别，顺序查找是从第一个记录开始逐个查找，并比较是否找到关键字，而折半查找是要先确定待查找记录的范围，然后逐步缩小查找范围，直到找到记录或找不到记录为止。折半查找思路：

折半查找的基本思路是，先将按照从小到大的顺序排序的有序表，用数组Arr来保存，用n来记录数组元素的个数，用Arr[0]来存放查找的关键字x，用low记录有序表中的第一个元素的位置，用high记录有序表中的最后一个元素的位置；再取中间位置的序号m=(n+1)/2，相应记录的值为Arr[m]，将给定的关键字x与Arr[m]比较；比较后会得到三种结果：(1)x<Arr[m]，由于有序表中的元素是从小到大排序的，如果x存在的话，就在有序表的左边。这样，查找的范围就缩小一半了，再继续对左半部分查找；(2)x==Arr[m]，查找成功；(3)x>Arr[m]，由于有序表中的元素是从小到大排序的，如果x存在的话，就在有序表的右边。这样，查找的范围就缩小一半了，再继续对右半部分查找。重复上述过程，查找区间不断折半，当最后只剩下一个记录，而此记录不是要找的记录，查找失败。由于查找范围不断缩小，查找速度明显快于顺序查找。例：假设有一组有序的数据{4，6，9，24，25，32，75，95}，顺序的存放在数组Arr[i]中。现给定一个关键字6，使用折半查找方法查询数组中是否能找到6。折半查找算法

有序表的折半查找算法，实际上是比较有序表中的数组元素与要查找关键字是否相等，是否大于或小于，折半查找算法见教材。分块查找使用分块查找，在处理线性表时，既快速，又可以经常动态变化，将要查找的元素均匀分成几块，块间按照大小排序，块内不用排序，所以使用分块查找时，我们需要建立一个块的最大或最小关键字表，即索引表。分块查找的基本思路和步骤分三步进行：(1)把一个较大的查找区间[1,n]按照某种规则分成若干个子块Arr1，Arr2，…，Arrk，可以按照从小到大顺序排序分块，也可以按照从大到小的顺序分块，块内可有序也可无序，选择每块中最大或最小的元素作为索引表中的成员；(2)根据已给定的查找关键字x，很快定出查找子块Arri；(3)对Arri结合某种查找方法继续查找x。分块查找例：有20个元素组成的一个线性表{4，18，16，8，3，35，28，32，25，36，43，62，67，64，48，98，74，75，84，71}，请分成4块，然后查找线性表中是否有8存在。8.4哈希法1、概念前面的顺序查找、折半查找、分块查找方法，在查找时，需要将查找关键字与给定的一组记录中的数据进行比较，确定被查找记录在表中的位置，查找时间与表的长度有关。哈希法，是将一组数据元素影像到一个有限的连续的存储地址集上，并以数据在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表(HashTable)。在这一影像过程称为哈希表或散列，所得的存贮位置称为哈希地址(HashAddress)或散列(Hash)。哈希法哈希表和哈希函数的概念理想的查找情况是不经过任何比较，一次存取便能得到所查找的记录，这一就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中的一个唯一位置相对应。在查找时，我们只要根据这个对应关系f找到给定值x的像f(x)。若结构中存在关键字和x相等的记录，则必定在f(x)的存储位置上，不需要逐个比较，就可直接取得所查找的记录。我们称这个对应关系f为哈希函数(HashFunction)。例：已知一个员工表，员工表中的数据项有员工编号、员工姓名、性别、年龄等，员工表如下表所示，其中员工编号是关键字，请建立哈希表。哈希函数的构造方法哈希函数的构造方法很多，怎么样衡量哈希函数的优劣，是我们首要明确的问题。好的哈希函数，要能使关键码的紧密的存放在一个连续的存储地址上，经过哈希函数影象到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的哈希函数，方便让一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突，提高查找效率。直接定址法

取关键字或关键字的某个线性函数值作为哈希地址，即H(x)=x或x+a，其中a为常数。这种哈希函数又叫做自身函数。但这种函数只适用于哈希地址集合和关键字集合大小相同的情况，故不经常使用。例：有一个人口统计表，其中年龄最为关键字，人口统计表中还包括某个年龄段人数数量等，要求出30岁的人有多少。数字分析法假设关键字是以r为基的数，比如以10为基的十进制数，如果哈希表中可能出现的关键字可以预测，则取关键字的若干数位组成哈希地址。例：有一组关键字，我们取其中的三位组成哈希散列地址。k1=322482262k2=322513678k3=332228671k4=322389671k5=322546577k6=322989576k7=322193562除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得的余数作为哈希地址。哈希函数f(x)=xmodp，并且p≤m。除留余数法不仅可以对关键字直接取模，也可以在平方取中等运算后取模。这个方法虽然简单，但是对p的选择至关重要，如果p选取不好，容易产生同义词，产生冲突。一般情况下p选择为质数，或20以内的质数。平方取中法

取关键字平方后的中间几位为哈希地址，通常我们不知道关键字的全部情况，选取其中几位，可能不一定合适，但是我们将一个数平方以后，中间几位数和数中的每一位都相关，得到中间几位数字是随机分布的，所以哈希地址也是随机的。具体取中间哪几位，由表的长度决定。例

：假设关键字的长度不超过2个字符，在计算机内可用两位八进制数表示字母和数字，字母a到z对应八进制01(8)~32(8)，数字0到9对应八进制33(8)到44(8)，使用取平法取中法来计算i，j，a3，ma的散列地址。折叠法

将关键字分割成位数相同的几部分，然后取这几部分叠加后的和，舍去进位作为哈希地址，这种方法称为折叠法。取的中间的位数可以是连续的，也可以是不连续的。例：设国际标准图书编号k=9787560928005，采用折叠法求哈希地址。冲突处理

哈希函数可以减少冲突，但是不能避免，因此，如何处理冲突时我们构造哈希表的时候要重点处理的问题。当关键字值的域远远大于哈希表的长度时，事先不知道关键字如何取值时，当我们插入的数据溢出哈希表时，冲突都是会产生的。下面讲解几个处理的冲突的方法。线性探测法

假设有一个关键字x的记录要放入表中，先由哈希函数求出其在表中的地址f(x)=j，探测表的第j个位置HT[j]的内容是否为空，如果为空，则插入记录；如果不为空，且第j个位置的记录的关键字不是x，则发生冲突。这时线性探测就继续探测下一个位置j+1，直到找到空位置为止插入记录；如果探测到最后一个位置，都没有找到空位置，则从表头第一个位置，开始探测，直到找到空位置，插入记录；如果从头探测，还是没有找到空位置，那么整个表就满了，发生了溢出。例：如HT表中，已填有关键字分别为18，63，,23的记录（哈希函数为f(x)=xmod11），现在又第四个记录，关键字的值为38和30，采用线性探测的方法将38插入到HT表中。溢出区法

在线性探测法中，会出现结点“堆积”现象，增加冲突发生的概率。溢出区法则另外开辟一个新的存储空间，把发生冲突的结点顺序的插入到溢出区中去，所以溢出区法将散列表分成了基本区和溢出区。例：某散列表中的基本长度为5，其区间中放入了3条记录r1,r2,r3，而溢出区长度为4。现在要放入新记录r4，新记录r4的关键字经过哈希函数计算出来的哈希地址为3，但基本区中的3好位置已有关键字，则将新记录r4放入溢出区的第一个地址中，如下图所示。链地址法

链地址法的基本思路是：把相同散列地址的结点链接在同一个链表中，从而形成n条链。或者当哈希表中相应位置为空时，直接存放；当哈希表中相应位置为非空时，用链表连接。例：已知6个记录的关键字的值为{6，12，15，38，44，55}，试构造哈希表来存放着6个记录，采用除留余数法，解决哈希冲突链表问题。实训项目--折半查找算法的应用【实训】折半查找算法的应用1．实训说明掌握各种基本查找方法，比较几种基本查找方法的局限性和优劣性，能熟练应用到实际应用中，并写代码实现。程序编写：编写一个函数，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。实训项目--折半查找算法的应用【实训】折半查找算法的应用2．算法分析在有序表T中，有一组元素{3，5，47，58，69，73，88}，采用折半查找算法查找关键字等于或小于55的元素，m正好指向等于55的元素或指向正好大于55的元素，插入x即可。3.源程序（见教材）。本章小结本章我们学习了有关查找的基本内容，了解了查找的相关概念，如查找、关键字、平均查找长度、有序表、哈希表、哈希函数等，还学习了查找的方法，如顺序查找、折半查找、分块查找和哈希法，并学习了这些算法的限制条件和优劣性，便于我们在具体情况，选择使用这些查找方法。查找算法比较查找算法没有绝对的好与坏，每种算法都有自己的优劣，也有自身的局限性。以下是4种查找方法的比较见教材。1．设有一组关键字序列{34，56，67，344，26，67，89，