会计学第7章查找7.1基本概念7.1基本概念对查找表经常(jīngcháng)进行的操作:仅作查询和检索(jiǎnsuǒ)操作的查找表。顺序(shùnxù)查找7.2顺序(shùnxù)查找A顺序(shùnxù)查找的查找过程为：从表中最后一个记录开始，逐个地将记录的关键字值和给定值的比较，若某个数据元素的关键字值和给定值相等，则查找成功，找到所查记录；反之，若一直找到第一个，其关键字值和给定值都不相等，则表明数组中没有所查元素，查找不成功。顺序查找的优点是：算法简单且适用面广，它对表的结构无任何要求。无论记录是否按关键字的大小有序，其算法均可应用(yìngyòng)，而且上述讨论对线性链表也同样适用。7.3二分法查找(cházhǎo)基本思想：取表的中间记录的关键字值与给定关键字的值相比较(bǐjiào)，如果给定值比该记录的关键字值大，则要查找的记录一定在表的后半部分;若给定值比该记录的关键字值小，则要查找的记录一定在表的前半部分。依次反复进行，在最坏的情况下，当表长缩小为1时必然能找到;否则就表明找不到要查找的记录。从二分法查找的执行情况分析(fēnxī)，每做一次比较，查找的范围都缩小一半。因此二分法查找的平均查找长度为ASL=log2(n+1)-1当n足够大时，可近似表示为log2n。优点：二分法查找比顺序查找的速度要快得多。当然，使用二分法查找必须是在顺序存储的条件下，且事先必须做到按关键字值排序才行。练习(liànxí)7.4分块查找(cházhǎo)查找步骤：首先用给定值在索引表中查找，确定满足条件的数据元素应存放在哪一块中。然后再到相应(xiāngyīng)的块中进行顺序查找，便可以得到查找的结果。7.4分块查找(cházhǎo)例如，给定关键字序列如下：{22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53},假设B=3，即将该序列分成3个子表（如何划分此处不考虑），每个子表有6个元素，则得到(dédào)的主表和索引表如图：分块查找(cházhǎo)的平均查找(cházhǎo)长度由两个部分组成:ASL=Eb+EwEb为确定某一块所需的平均查找(cházhǎo)长度，Ew为在块内的平均查找(cházhǎo)长度。假设线性表中共有n个数据元素，平均分成b块，每块s个数据元素，并假设查找(cházhǎo)各块概率相等，若在索引表内和块内查找(cházhǎo)均用顺序查找(cházhǎo)方法，则Ew=（s+1）/2，Eb=（b+1）/2，所以ASL=Eb+Ew=（b+s）/2+1=（n/s+s）/2+1当s=时，ASL取最小值，这时ASL=+1。分块查找的速度比顺序查找要快得多，但又不如二分法查找。如果线性表元素个数很多，且被分成的块数b很大时，对索引表的查找可以采用二分法查找，还能进一步提高速度。优点：在线性表中插入或删除(shānchú)一个元素时，只要找到元素应属于的块，然后在块内进行插入和删除(shānchú)运算。由于块内元素的存放是任意的，所以插入和删除(shānchú)比较容易，不需要移动大量元素。练习(liànxí)【三种查找方法(fāngfǎ)比较】7.5散列表(lièbiǎo)及其查找7.5散列表(lièbiǎo)及其查找7.5散列表(lièbiǎo)及其查找【例如】建立(jiànlì)一张全国30个地区的各民族统计表H1：取键值中第一个字母在字母表中的序号作为散列函数。H2：先求键值中首尾两个字母在字母表中的序号之和，如果这个和大于30，则减去30。7.5散列表(lièbiǎo)及其查找散列法查找(cházhǎo)归结为如下两个方面:（1）对给定的一组关键字构造一个计算简单且散列均匀的散列函数;（2）拟订一个较好解决冲突的方法。7.5.2散列函数(hánshù)的构造方法2.数字(shùzì)分析法若以下(yǐxià)标为000~999的顺序表表示之。如:关键字序列(xùliè)9934653299372242993874339930136799322817993389679936853799368532．．．．．．3.平方(píngfāng)取中法如图：随机给出一些关键字，取平方(píngfāng)后的第2到4位为函数地址。4.折叠(zhédié)法例关键字为：0442205864，哈希地址(dìzhǐ)位数为4H（k）=k%p（p≤m）k－关键字m－表长注意：p应取小于表长m的最大素数，才能达到(dádào)使散列函数值均匀分布的目的。例如(lìrú):关键字集合{19,1,24,14,55,16,39}7.5.3冲突(chōngtū)处理1.开放(kāifàng)地址