计算机软件技术基础课件

计算机软件技术基础教师：曾晓东电话_mail:zengxiaodong@263.net计算机软件技术基础教师：曾晓东5.1查找一、概念和术语二、顺序表查找三、散列查找四、各种查找算法的比较计算机软件技术基础查找与排序5.1查找一、概念和术语计算机软件技术基础查找与排序5.1查找访问与查找都是数据结构中的重要操作，访问数据结构中数据元素的访问算法都是与具体数据结构的特性紧密相关的。如根据下标访问数组中的数据元素，沿指针指向访问线性链表中的结点、遍历一棵二叉树等。在这一节中，我们将讨论各种查找算法，并对查找算法进行分析。计算机软件技术基础查找与排序5.1查找访问与查找都是数据结构中的重要操作，访问数据结构一、概念和术语记录(record)：它是由若干个数据项(或称为域)组成的数据元素，它和结点、顶点的意义完全相同。文件(file)：它是由若干记录组成的集合，即含有若干记录的表称为文件。关键字1）主关键字：在数据处理中，被查找的元素通常是以记录形式出现的，即每一个数据元素（记录）由若干个数据项组成，其中能用来唯一标识该记录的数据项称为主关键字。

2）次关键字：用来标识若干记录的数据项称为次关键字。计算机软件技术基础查找与排序一、概念和术语记录(record)：它是由若干个数据项(或称一、概念和术语查找给定一个值K，在含有n个记录的文件中进行查找，寻找一个关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。动态查找与静态查找查找的同时对表作修改操作的表称为动态查找表，否则称之为静态查找表。计算机软件技术基础查找与排序一、概念和术语查找计算机软件技术基础查找与排序一、概念和术语平均查找长度 由于待查记录在文件中的位置随意性很大，因此通常用比较次数的平均值，即统计意义上的数学期望值来评估查找算法，称为平均查找长度（ASL）：

其中，n是文件中记录的个数，Pi是查找第i个记录的查找概率，通常我们认为每个记录的查找概率相等，即Pi=1/n；Ci是找到第i个记录时所经历的比较次数。计算机软件技术基础查找与排序一、概念和术语平均查找长度 其中，n是文件中记录的个数，Pi二、顺序表查找1、顺序查找顺序查找又称线性查找，是一种最简单的查找方法。1）基本思想从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中所有关键字都不等，则查找失败。2）算法描述

顺序表的类型定义constintMAXSIZE=100;typedefstruct{ structelemtypedata[MAXSIZE]; intlength;}listtype;结点的类型定义typedefstruct{ keywordtypekey; datatypeelemdata;}elemtype;计算机软件技术基础查找与排序二、顺序表查找1、顺序查找顺序表的类型定义结点的类型定义计算二、顺序表查找intseqSearch(listtype*a,keywordtypek){//在顺序表a中查找关键字k，若成功则返回记录号，否则返回-1 inti; a->data[a->length]=k; //设置监视哨

for(i=0;a->data[i].key!=k;i++); if(i==a->length) return(-1); //查找不成功

else return(i); //查找成功}3)性能分析 等概率情况下，Pi=1/n，Ci=i，所以：计算机软件技术基础查找与排序二、顺序表查找intseqSearch(listtype二、顺序表查找2、折半查找又称对分查找，是对有序表进行的一种查找。1)基本思想 先找到“中间记录”，比较其关键字，如果关键字与给定值K相等，则查找成功；如果关键字x小于给定值K，则说明被查找记录必在前半区间内；反之则在后半区间内。这样把查找区间缩小了一半，继续进行查找。计算机软件技术基础查找与排序二、顺序表查找2、折半查找计算机软件技术基础查找与排序二、顺序表查找513174246557094lowmidhigk=55513174246557094

lowmidhig513174246557094lowmidhigk=12513174246557094lowmidhig513174246557094higlow查找成功查找失败计算机软件技术基础查找与排序二、顺序表查找513174246二、顺序表查找2)算法描述intbinSearch(listtype*a,keywordtypek){/*在有序顺序表a中查找关键字k，若成功则返回记录号，否则返回-1*/

intmid,low=0，high=a->length-1;

while(low<=high){

mid=(low+high)/2;

if(k==a->data[mid].key)return(mid);

if(k<a->data[mid].key)high=mid-1;

if(k>a->data[mid].key)low=mid+1;

}

return(-1);}计算机软件技术基础查找与排序二、顺序表查找2)算法描述计算机软件技术基础查找与排序二、顺序表查找3)性能分析对分查找的判定树：在查找过程中，各记录的比较次数与待查记录在文件中的相对位置有关，我们把比较次数相同的记录关键字放在同一层次，各层次之间用分支相连，可得到一棵二叉树，称为判定树。429455704613175序列：5,13,17,42,46,55,70,94的判定树

等概率下的平均查找长度为：计算机软件技术基础查找与排序二、顺序表查找3)性能分析429455704613175序列二、顺序表查找3、分块查找1）概念 分块查找又称索引顺序查找，把关键字分成若干块，且后一块中的所有关键字均大于前一块中最大的关键字。而每一块中的关键字则不一定有序。2）基本思想 先将各块中的最大关键字构成一个递增有序的索引表，查找分两步：

①对索引表对分或顺序查找,以确定所在块。

②在所在块中进行顺序查找。计算机软件技术基础查找与排序二、顺序表查找3、分块查找计算机软件技术基础查找与排序二、顺序表查找图例11930438406065847075666584048第1块第2块第3块索引表最大关键字起始地址计算机软件技术基础查找与排序二、顺序表查找图例11930438二、顺序表查找3)算法分析分块查找的平均查找次数包括两部分查找索引表(Lb)在块中查找(Lw)ASL=Lb+Lw设共有n个记录，分成b块，每块有s个记录，则b=n/s设在索引表和块中都进行顺序查找，则

ASL=(b/2+s/2)=(n/s+s)/2+1

当b=s=sqrt(n)时，ASL最小，为sqrt(n)+1其查找效率界于折半查找和顺序查找之间计算机软件技术基础查找与排序二、顺序表查找3)算法分析计算机软件技术基础查找与排序三、散列查找1、散列表又称哈希表1）基本思想：通过对给定值作某种运算，直接求得关键字等于给定值的记录的位置。2）概念：设关键字key与存储位置间的对应关系为H(key)，若用一维数组来存放文件，则H(key)即为数组的下标。我们称函数H为哈希(Hash)函数，H(key)为哈希地址（或散列地址），这个一维数组称为哈希表。计算机软件技术基础查找与排序三、散列查找1、散列表计算机软件技术基础查找与排序三、散列查找3）有关问题①哈希查找是对给定的关键字按哈希函数直接求得记录位置的，不需进行比较。②为提高查找效率，哈希表的空间m要比记录个数n大，定义a=n/m为装填系数(有时也叫装填因子)，实际应用中一般取：0.65～0.85。计算机软件技术基础查找与排序三、散列查找3）有关问题计算机软件技术基础查找与排序三、散列查找③为求得哈希地址，有时须对关键字进行算术或逻辑运算，若关键字为非数值型，可先转化为数值，称为关键字的内部码。而且求得的哈希地址的值域必须在哈希表长的范围内。④若某个哈希函数对不同的关键字得到相同的哈希地址，这种现象称为冲突，这些关键字称为同义词。实际应用中，冲突一般不可避免，应寻找解决冲突的方法。所以，运用哈希技术进行查找，要解决两个问题：哈希函数的构造和解决冲突。计算机软件技术基础查找与排序三、散列查找③为求得哈希地址，有时须对关键字进行算术或逻辑三、散列查找2、构造散列函数构造散列函数的原则散列函数应是简单的，能在较短的时间内计算出结果。散列函数的定义域必须包括需要存储的全部关键码,如果散列表允许m个地址时,其值域必须在0到m-1之间。散列函数计算出来的地址应能均匀分布在整个地址空间中。

计算机软件技术基础查找与排序三、散列查找2、构造散列函数计算机软件技术基础查找与排序三、散列查找1）折叠移位法将关键字分为几段，除了最后一段外，其余各段都须等长，然后将各段相加作为哈希地址。折叠时有两种方法：移位折叠和边界折叠。如关键字值为：12320324111220，分为5段：123,203,241,112,20，两种折叠法分别如下：

123 321

203 203

241 142

112 112

20 02

——

——

879 780计算机软件技术基础查找与排序三、散列查找1）折叠移位法计算机软件技术基础查找与排序三、散列查找2)平方取中法先将关键字平方，再选取其中几位作为哈希地址。例如有一组关键字为：

(0100,1100,1200,1160,2060,2061,2163,2261,2262) 设存储空间为1000,将关键字平方后再取第2,3,4位构成哈希地址为：

(010,210,440,345,243,247,678,112,116)。计算机软件技术基础查找与排序三、散列查找2)平方取中法计算机软件技术基础查找与排序三、散列查找3)除留余数法对关键字取模（余数）作为哈希地址，即：H(key)=key%p。如果将m取为某个偶数，则奇数关键字值被转换为奇地址，偶数关键字值被转换成偶地址。显然，这很容易造成散列冲突。另外，如果用较小的质数或含有小质数因子的合数作为除数m，也会导致散列地址不均匀的结果。为了获得比较均匀的地址分布，最好选择—个较大的质数作为除数。计算机软件技术基础查找与排序三、散列查找3)除留余数法计算机软件技术基础查找与排序三、散列查找注意：经验证明模数m取为超过20的质因子的合数，散列地址分布将比较均匀。也可以使用此方法，作附加处理，将散列地址限制在一个范围内。如允许的地址空间限制在000—499之间，则将H%500即可。计算机软件技术基础查找与排序三、散列查找注意：经验证明模数m取为超过20的质因子的合数，三、散列查找4）数字分析法适合静态数据，关键字已知,分析数字的分布，删除不均匀的数字，再根据存储空间的大小决定数字的数目。例如有7个学生的学号为： 542422241

542813678

542228171

542389671

542541577

542885376

542193552分析知：第1,2,3位分布太不均匀，删去；第8位出现的7太多，删去。设存储空间为1000，则可取第4,6,7位作为关键字的存储地址，分别为：422，836，281，396，515，853，135计算机软件技术基础查找与排序三、散列查找4）数字分析法分析知：第1,2,3位分布太不三、散列查找数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况,它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。计算机软件技术基础查找与排序三、散列查找数字分析法仅适用于事先明确知道表中所有关键码每一三、散列查找3、处理散列冲突所谓散列冲突(conflict)就是两个不相同的关键字值被转换成同—个散列地址的现象。1）线性探测设性线表的空间为T[m]，哈希函数为H(key)，冲突时求另一个记录的地址公式为：

dj+1=(d1+j)%m(j=1,2,…,s,s≥1)其中d1=H(key)。计算机软件技术基础查找与排序三、散列查找3、处理散列冲突计算机软件技术基础查找与排序1）线性探测线性探测再散列是把哈希表作为一个环状空间，当冲突发生时，以线性方式从下一个哈希表地址开始探测，直到查到一个空的存储地址，将数据存入。若找完一个循环还没有找到空间，则表示地址已满。计算机软件技术基础查找与排序1）线性探测线性探测再散列是把哈希表作为一个环状空间，当冲突三、散列查找设有一组关键字为：(13,29,01,23,44,55,20,84,27,68,11,10,79,14)n=14，选取a=0.75,则哈希表长m=19，哈希表为T[0..18]，用除留余数法构造哈希函数，选p=19，采用线性探测法处理冲突0123456789101112131415161718K=13H(K)=13%19=13填入13K=29H(K)=29%19=10填入29K=01H(K)=1%19=1填入01K=23H(K)=23%19=4填入23K=44H(K)=44%19=6填入44K=55H(K)=55%19=16填入55K=20H(K)=20%19=1冲突Add=1+1=2填入20K=84H(K)=84%19=8填入84K=27H(K)=27%19=8冲突Add=8+1=9填入27K=68H(K)=68%19=11填入68K=11H(K)=11%19=11冲突Add=11+1=12填入11K=10H(K)=10%19=10冲突Add=10+1=11冲突Add=11+1=12冲突Add=12+1=13冲突Add=13+1=14填入10K=79H(K)=79%19=3填入79K=14H(K)=14%19=14冲突Add=14+1=15填入14平均查找长度：ASL=总比较次数/记录个数；采用不同的解决冲突方法，ASL也可能不同。对此例，平均查找长度为ASL=(1+1+1+1+1+1+2+1+2+1+2+5+1+2)/14=22/14计算机软件技术基础查找与排序三、散列查找设有一组关键字为：0123三、散列查找查找算法如下：

intlinearProbing(elemtypehash[],intn,intk){

/*hash:哈希表;n:哈希表的表长；k：关键字*/

i=H(k);/*计算地址*/j=i;/*线性探测位置*/

while(hash[j].key!=k&&hash[j].key!=0){

j=(j+1)%n;

if(j==i){return(-1);//表满}

}

return(j);

}若hash[j].key=0表示此地址为空。缺点：线性探测方法容易产生“记录群集”,不同探查序列的关键码占据可用的空位,为寻找某一关键码需要经历不同的探查序列,导致查找时间增加。计算机软件技术基础查找与排序三、散列查找查找算法如下：

intlinearProbin三、散列查找2)随机探测线性探测产生群集的主要原因是：每次都探测邻接的下一步个位置，即探测步长不变，如果按不同的步长探测，则可减少群集现象。本方法是用一组预先给定的随机数在冲突时求地址，公式为：dj=(d1+Rj)%m(j=1,2,...,s,s≥1)

其中Rj为一组随机数列。计算机软件技术基础查找与排序三、散列查找2)随机探测计算机软件技术基础查找与排序2)随机探测设有一组关键字为：(13,29,01,23,44,55,20,84,27,68,11,10,79,14) n=14，选取a=0.75,则哈希表长m=19，哈希表为T[0..18]，用除留余数法构造哈希函数，选p=19，用随机探测法解决冲突。其中随机数序列为：23,2,19,14,3,16,55,44,…计算机软件技术基础查找与排序2)随机探测设有一组关键字为：计算机软件技术基础查找与排序三、散列查找0123456789101112131415161718K=13H(K)=13%19=13填入关键字：(13,29,01,23,44,55,20,84,27,68,11,10,79,14)13K=29H(K)=29%19=10填入29K=01H(K)=01%19=01填入01K=23H(K)=23%19=4填入23K=44H(K)=44%19=6填入44K=55H(K)=55%19=17填入55K=20H(K)=20%19=1冲突Add=(1+23)%19=5填入20K=84H(K)=84%19=8填入84K=27H(K)=27%19=8冲突Add=(8+23)%19=12填入27K=68H(K)=68%19=11填入68K=11H(K)=11%19=11冲突Add=(11+23)%19=15填入11K=10H(K)=10%19=10冲突Add=(10+23)%19=14填入10K=79H(K)=79%19=3填入79K=14H(K)=14%19=14冲突Add=(14+23)%19=18填入14对此例，平均查找长度为ASL=(1+1+1+1+1+1+2+1+2+1+2+2+1+2)/14=19/14明显比采用线性探测法处理冲突为优计算机软件技术基础查找与排序三、散列查找012345三、散列查找查找算法如下：intrandomProbing(elemtypehash[],intrnd[],intn,intk){

/*hash:哈希表;rnd:随机数列；n:哈希表的表长；k：关键字*/

i=H(k);/*计算地址*/j=0;/*随机数列位置*/

add=i;/*随机探测位置*/ while(hash[add].key!=k&&hash[add].key!=0){

add=(i+rnd[j])%n; j++;

}

return(j);

}缺点：处理表满不方便。若hash[add].key=0表示此地址为空。计算机软件技术基础查找与排序三、散列查找查找算法如下：若hash[add].key=0表三、散列查找线性探测及随机探测的缺点：不能真正删除表中已有表项。删除表项会影响其他表项的查找。若把关键码为68的表项真正删除,以后在查找关键码为11的表项时就查不下去,会错误地判断表中没有关键码为11的表项。若想删除一个表项,只能给它做一个删除标记,进行逻辑删除,不能把它真正删去。逻辑删除的副作用是：在执行多次删除后,表面上看起来散列表很满,实际上有许多位置没有利用。当然，也可以物理删除表项，不过，需要将表项后面的各项前移计算机软件技术基础查找与排序三、散列查找线性探测及随机探测的缺点：计算机软件技术基础查找三、散列查找3）链地址法适用于记录内容变动较大的散列表若哈希表为T[0..m-1]，设置一个由m个指针分量组成的一维数组ST[0..m-1]，凡哈希地址为i的记录都插入到头指针为ST[i]的链表（称为散列链表或桶，哈希地址相同的元素称为同义词）中。链地址法是个动态结构，所以更适合在造表之前无法确定记录个数的情况。计算机软件技术基础查找与排序三、散列查找3）链地址法计算机软件技术基础查找与排序3）链地址法散列链表的结点定义与普通单链表一致，只是其elemtype域包含两个域：keywordtype(关键词)和datatype(数据)，其定义与前面的Hast表的结点定义类似计算机软件技术基础查找与排序3）链地址法散列链表的结点定义与普通单链表一致，只是其ele三、散列查找查找算法如下：node*hashLinkSearch(node*ST[],intm,keywordtypek){/*ST:散列链表的头指针数组；m:哈希表长度；k：关键词*/

i=H(k);/*取哈希地址*/ p=ST[i];/*散列链表的头指针*/

while(p&&p->key!=k)p=p->next;

return(p);}返回值p为指向查找元素的地址，若p=NULL，说明表中无此元素，可将其插入到哈希表中。计算机软件技术基础查找与排序三、散列查找查找算法如下：计算机软件技术基础查找与排序三、散列查找示例：给出一组表项关键码

{Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly}。散列函数为：Hash(x)＝ord(x)－ord('A')。用它计算可得：

Hash(Burke)=1 Hash(Ekers)=4Hash(Broad)=1 Hash(Blum)=1Hash(Attlee)=0 Hash(Hecht)=7Hash(Alton)=0 Hash(Ederly)=4散列表为T[0..25]，m=26。

计算机软件技术基础查找与排序三、散列查找示例：给出一组表项关键码计算机软件技术基础查找三、散列查找0123456789AttleeBurkeEkersHechtAltonBroadBlumEderly计算机软件技术基础查找与排序三、散列查找0AttleeBurkeEkersHechtAl三、散列查找通常，每个桶中的同义词子表都很短，设有n个关键码通过某一个散列函数，存放到散列表中的m个桶中。那么每一个桶中的同义词子表的平均长度为n/m。以查找平均长度为n/m的同义词子表代替了查找长度为n的顺序表，查找速度快得多。装填因子：

应用链地址法处理冲突,需要增设链接指针,似乎增加了存储开销。事实上,由于线性探测和随机探测法都必须保持大量的空闲空间以确保查找效率，如随机探测法要求装填因子

0.5，而表项所占空间又比指针大得多，所以使用链地址法反而比线性探测法和随机探测法节省存储空间。计算机软件技术基础查找与排序三、散列查找通常，每个桶中的同义词子表都很短，设有n个关键三、散列查找4）性能分析ASL=总比较次数/记录个数；采用不同的解决冲突方法，平均查找长度也可能不同。与线性查找、对分查找相比，ASL较小。但最坏情况的查找性能较差平均查找长度是装填系数a的函数。适当选择a的值是很关键的。计算机软件技术基础查找与排序三、散列查找4）性能分析计算机软件技术基础查找与排序4）性能分析散列表的装填因子表明了表中的装满程度。越大,说明表越满,再插入新元素时发生冲突的可能性就越大。散列表的查找性能,即平均查找长度依赖于散列表的装填因子,不直接依赖于n或m。不论表的长度有多大,我们总能选择一个合适的装填因子,以把平均查找长度限制在一定范围内。计算机软件技术基础查找与排序4）性能分析散列表的装填因子表明了表中的装满程度。越大三、散列查找用不同的方法溢出处理冲突时散列表的平均查找长度如图所示。计算机软件技术基础查找与排序三、散列查找用不同的方法溢出处理冲突时散列表的平均查找长度如四、不同查找算法的比较1.顺序查找查找效率低对记录结构无要求，可在链表、顺序表上查找2.折半查找查找效率高只能在有序的顺序表上查找，不适用记录多变的表3.分块查找查找效率界于顺序查找和折半查找之间对记录结构的要求也界于顺序查找和折半查找之间，较适合大型文件的查找4.散列查找查找性能与文件中的记录数无关，只与其装填因子相关最坏情况的查找性能不佳计算机软件技术基础查找与排序四、不同查找算法的比较1.顺序查找计算机软件技术基础查找与排小结1、理解基本概念：关键字、ASL（平均查找次数）2、掌握：线性查找、折半查找、哈希查找3、了解：分块查找计算机软件技术基础查找与排序小结1、理解基本概念：关键字、ASL（平均查找次数）计算机软计算机软件技术基础教师：曾晓东电话_mail:zengxiaodong@263.net计算机软件技术基础教师：曾晓东5.1查找一、概念和术语二、顺序表查找三、散列查找四、各种查找算法的比较计算机软件技术基础查找与排序5.1查找一、概念和术语计算机软件技术基础查找与排序5.1查找访问与查找都是数据结构中的重要操作，访问数据结构中数据元素的访问算法都是与具体数据结构的特性紧密相关的。如根据下标访问数组中的数据元素，沿指针指向访问线性链表中的结点、遍历一棵二叉树等。在这一节中，我们将讨论各种查找算法，并对查找算法进行分析。计算机软件技术基础查找与排序5.1查找访问与查找都是数据结构中的重要操作，访问数据结构一、概念和术语记录(record)：它是由若干个数据项(或称为域)组成的数据元素，它和结点、顶点的意义完全相同。文件(file)：它是由若干记录组成的集合，即含有若干记录的表称为文件。关键字1）主关键字：在数据处理中，被查找的元素通常是以记录形式出现的，即每一个数据元素（记录）由若干个数据项组成，其中能用来唯一标识该记录的数据项称为主关键字。

2）次关键字：用来标识若干记录的数据项称为次关键字。计算机软件技术基础查找与排序一、概念和术语记录(record)：它是由若干个数据项(或称一、概念和术语查找给定一个值K，在含有n个记录的文件中进行查找，寻找一个关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。动态查找与静态查找查找的同时对表作修改操作的表称为动态查找表，否则称之为静态查找表。计算机软件技术基础查找与排序一、概念和术语查找计算机软件技术基础查找与排序一、概念和术语平均查找长度 由于待查记录在文件中的位置随意性很大，因此通常用比较次数的平均值，即统计意义上的数学期望值来评估查找算法，称为平均查找长度（ASL）：

其中，n是文件中记录的个数，Pi是查找第i个记录的查找概率，通常我们认为每个记录的查找概率相等，即Pi=1/n；Ci是找到第i个记录时所经历的比较次数。计算机软件技术基础查找与排序一、概念和术语平均查找长度 其中，n是文件中记录的个数，Pi二、顺序表查找1、顺序查找顺序查找又称线性查找，是一种最简单的查找方法。1）基本思想从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中所有关键字都不等，则查找失败。2）算法描述

顺序表的类型定义constintMAXSIZE=100;typedefstruct{ structelemtypedata[MAXSIZE]; intlength;}listtype;结点的类型定义typedefstruct{ keywordtypekey; datatypeelemdata;}elemtype;计算机软件技术基础查找与排序二、顺序表查找1、顺序查找顺序表的类型定义结点的类型定义计算二、顺序表查找intseqSearch(listtype*a,keywordtypek){//在顺序表a中查找关键字k，若成功则返回记录号，否则返回-1 inti; a->data[a->length]=k; //设置监视哨

for(i=0;a->data[i].key!=k;i++); if(i==a->length) return(-1); //查找不成功

else return(i); //查找成功}3)性能分析 等概率情况下，Pi=1/n，Ci=i，所以：计算机软件技术基础查找与排序二、顺序表查找intseqSearch(listtype二、顺序表查找2、折半查找又称对分查找，是对有序表进行的一种查找。1)基本思想 先找到“中间记录”，比较其关键字，如果关键字与给定值K相等，则查找成功；如果关键字x小于给定值K，则说明被查找记录必在前半区间内；反之则在后半区间内。这样把查找区间缩小了一半，继续进行查找。计算机软件技术基础查找与排序二、顺序表查找2、折半查找计算机软件技术基础查找与排序二、顺序表查找513174246557094lowmidhigk=55513174246557094

lowmidhig513174246557094lowmidhigk=12513174246557094lowmidhig513174246557094higlow查找成功查找失败计算机软件技术基础查找与排序二、顺序表查找513174246二、顺序表查找2)算法描述intbinSearch(listtype*a,keywordtypek){/*在有序顺序表a中查找关键字k，若成功则返回记录号，否则返回-1*/

intmid,low=0，high=a->length-1;

while(low<=high){

mid=(low+high)/2;

if(k==a->data[mid].key)return(mid);

if(k<a->data[mid].key)high=mid-1;

if(k>a->data[mid].key)low=mid+1;

}

return(-1);}计算机软件技术基础查找与排序二、顺序表查找2)算法描述计算机软件技术基础查找与排序二、顺序表查找3)性能分析对分查找的判定树：在查找过程中，各记录的比较次数与待查记录在文件中的相对位置有关，我们把比较次数相同的记录关键字放在同一层次，各层次之间用分支相连，可得到一棵二叉树，称为判定树。429455704613175序列：5,13,17,42,46,55,70,94的判定树

等概率下的平均查找长度为：计算机软件技术基础查找与排序二、顺序表查找3)性能分析429455704613175序列二、顺序表查找3、分块查找1）概念 分块查找又称索引顺序查找，把关键字分成若干块，且后一块中的所有关键字均大于前一块中最大的关键字。而每一块中的关键字则不一定有序。2）基本思想 先将各块中的最大关键字构成一个递增有序的索引表，查找分两步：

①对索引表对分或顺序查找,以确定所在块。

②在所在块中进行顺序查找。计算机软件技术基础查找与排序二、顺序表查找3、分块查找计算机软件技术基础查找与排序二、顺序表查找图例11930438406065847075666584048第1块第2块第3块索引表最大关键字起始地址计算机软件技术基础查找与排序二、顺序表查找图例11930438二、顺序表查找3)算法分析分块查找的平均查找次数包括两部分查找索引表(Lb)在块中查找(Lw)ASL=Lb+Lw设共有n个记录，分成b块，每块有s个记录，则b=n/s设在索引表和块中都进行顺序查找，则

ASL=(b/2+s/2)=(n/s+s)/2+1

当b=s=sqrt(n)时，ASL最小，为sqrt(n)+1其查找效率界于折半查找和顺序查找之间计算机软件技术基础查找与排序二、顺序表查找3)算法分析计算机软件技术基础查找与排序三、散列查找1、散列表又称哈希表1）基本思想：通过对给定值作某种运算，直接求得关键字等于给定值的记录的位置。2）概念：设关键字key与存储位置间的对应关系为H(key)，若用一维数组来存放文件，则H(key)即为数组的下标。我们称函数H为哈希(Hash)函数，H(key)为哈希地址（或散列地址），这个一维数组称为哈希表。计算机软件技术基础查找与排序三、散列查找1、散列表计算机软件技术基础查找与排序三、散列查找3）有关问题①哈希查找是对给定的关键字按哈希函数直接求得记录位置的，不需进行比较。②为提高查找效率，哈希表的空间m要比记录个数n大，定义a=n/m为装填系数(有时也叫装填因子)，实际应用中一般取：0.65～0.85。计算机软件技术基础查找与排序三、散列查找3）有关问题计算机软件技术基础查找与排序三、散列查找③为求得哈希地址，有时须对关键字进行算术或逻辑运算，若关键字为非数值型，可先转化为数值，称为关键字的内部码。而且求得的哈希地址的值域必须在哈希表长的范围内。④若某个哈希函数对不同的关键字得到相同的哈希地址，这种现象称为冲突，这些关键字称为同义词。实际应用中，冲突一般不可避免，应寻找解决冲突的方法。所以，运用哈希技术进行查找，要解决两个问题：哈希函数的构造和解决冲突。计算机软件技术基础查找与排序三、散列查找③为求得哈希地址，有时须对关键字进行算术或逻辑三、散列查找2、构造散列函数构造散列函数的原则散列函数应是简单的，能在较短的时间内计算出结果。散列函数的定义域必须包括需要存储的全部关键码,如果散列表允许m个地址时,其值域必须在0到m-1之间。散列函数计算出来的地址应能均匀分布在整个地址空间中。

计算机软件技术基础查找与排序三、散列查找2、构造散列函数计算机软件技术基础查找与排序三、散列查找1）折叠移位法将关键字分为几段，除了最后一段外，其余各段都须等长，然后将各段相加作为哈希地址。折叠时有两种方法：移位折叠和边界折叠。如关键字值为：12320324111220，分为5段：123,203,241,112,20，两种折叠法分别如下：

123 321

203 203

241 142

112 112

20 02

——

——

879 780计算机软件技术基础查找与排序三、散列查找1）折叠移位法计算机软件技术基础查找与排序三、散列查找2)平方取中法先将关键字平方，再选取其中几位作为哈希地址。例如有一组关键字为：

(0100,1100,1200,1160,2060,2061,2163,2261,2262) 设存储空间为1000,将关键字平方后再取第2,3,4位构成哈希地址为：

(010,210,440,345,243,247,678,112,116)。计算机软件技术基础查找与排序三、散列查找2)平方取中法计算机软件技术基础查找与排序三、散列查找3)除留余数法对关键字取模（余数）作为哈希地址，即：H(key)=key%p。如果将m取为某个偶数，则奇数关键字值被转换为奇地址，偶数关键字值被转换成偶地址。显然，这很容易造成散列冲突。另外，如果用较小的质数或含有小质数因子的合数作为除数m，也会导致散列地址不均匀的结果。为了获得比较均匀的地址分布，最好选择—个较大的质数作为除数。计算机软件技术基础查找与排序三、散列查找3)除留余数法计算机软件技术基础查找与排序三、散列查找注意：经验证明模数m取为超过20的质因子的合数，散列地址分布将比较均匀。也可以使用此方法，作附加处理，将散列地址限制在一个范围内。如允许的地址空间限制在000—499之间，则将H%500即可。计算机软件技术基础查找与排序三、散列查找注意：经验证明模数m取为超过20的质因子的合数，三、散列查找4）数字分析法适合静态数据，关键字已知,分析数字的分布，删除不均匀的数字，再根据存储空间的大小决定数字的数目。例如有7个学生的学号为： 542422241

542813678

542228171

542389671

542541577

542885376

542193552分析知：第1,2,3位分布太不均匀，删去；第8位出现的7太多，删去。设存储空间为1000，则可取第4,6,7位作为关键字的存储地址，分别为：422，836，281，396，515，853，135计算机软件技术基础查找与排序三、散列查找4）数字分析法分析知：第1,2,3位分布太不三、散列查找数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况,它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。计算机软件技术基础查找与排序三、散列查找数字分析法仅适用于事先明确知道表中所有关键码每一三、散列查找3、处理散列冲突所谓散列冲突(conflict)就是两个不相同的关键字值被转换成同—个散列地址的现象。1）线性探测设性线表的空间为T[m]，哈希函数为H(key)，冲突时求另一个记录的地址公式为：

dj+1=(d1+j)%m(j=1,2,…,s,s≥1)其中d1=H(key)。计算机软件技术基础查找与排序三、散列查找3、处理散列冲突计算机软件技术基础查找与排序1）线性探测线性探测再散列是把哈希表作为一个环状空间，当冲突发生时，以线性方式从下一个哈希表地址开始探测，直到查到一个空的存储地址，将数据存入。若找完一个循环还没有找到空间，则表示地址已满。计算机软件技术基础查找与排序1）线性探测线性探测再散列是把哈希表作为一个环状空间，当冲突三、散列查找设有一组关键字为：(13,29,01,23,44,55,20,84,27,68,11,10,79,14)n=14，选取a=0.75,则哈希表长m=19，哈希表为T[0..18]，用除留余数法构造哈希函数，选p=19，采用线性探测法处理冲突0123456789101112131415161718K=13H(K)=13%19=13填入13K=29H(K)=29%19=10填入29K=01H(K)=1%19=1填入01K=23H(K)=23%19=4填入23K=44H(K)=44%19=6填入44K=55H(K)=55%19=16填入55K=20H(K)=20%19=1冲突Add=1+1=2填入20K=84H(K)=84%19=8填入84K=27H(K)=27%19=8冲突Add=8+1=9填入27K=68H(K)=68%19=11填入68K=11H(K)=11%19=11冲突Add=11+1=12填入11K=10H(K)=10%19=10冲突Add=10+1=11冲突Add=11+1=12冲突Add=12+1=13冲突Add=13+1=14填入10K=79H(K)=79%19=3填入79K=14H(K)=14%19=14冲突Add=14+1=15填入14平均查找长度：ASL=总比较次数/记录个数；采用不同的解决冲突方法，ASL也可能不同。对此例，平均查找长度为ASL=(1+1+1+1+1+1+2+1+2+1+2+5+1+2)/14=22/14计算机软件技术基础查找与排序三、散列查找设有一组关键字为：0123三、散列查找查找算法如下：

intlinearProbing(elemtypehash[],intn,intk){

/*hash:哈希表;n:哈希表的表长；k：关键字*/

i=H(k);/*计算地址*/j=i;/*线性探测位置*/

while(hash[j].key!=k&&hash[j].key!=0){

j=(j+1)%n;

if(j==i){return(-1);//表满}

}

return(j);

}若hash[j].key=0表示此地址为空。缺点：线性探测方法容易产生“记录群集”,不同探查序列的关键码占据可用的空位,为寻找某一关键码需要经历不同的探查序列,导致查找时间增加。计算机软件技术基础查找与排序三、散列查找查找算法如下：

intlinearProbin三、散列查找2)随机探测线性探测产生群集的主要原因是：每次都探测邻接的下一步个位置，即探测步长不变，如果按不同的步长探测，则可减少群集现象。本方法是用一组预先给定的随机数在冲突时求地址，公式为：dj=(d1+Rj)%m(j=1,2,...,s,s≥1)

其中Rj为一组随机数列。计算机软件技术基础查找与排序三、散列查找2)随机探测计算机软件技术基础查找与排序2)随机探测设有一组关键字为：(13,29,01,23,44,55,20,84,27,68,11,10,79,14) n=14，选取a=0.75,则哈希表长m=19，哈希表为T[0..18]，用除留余数法构造哈希函数，选p=19，用随机探测法解决冲突。其中随机数序列为：23,2,19,14,3,16,55,44,…计算机软件技术基础查找与排序2)随机探测设有一组关键字为：计算机软件技术基础查找与排序三、散列查找0123456789101112131415161718K=13H(K)=13%19=13填入关键字：(13,29,01,23,44,55,20,84,27,68,11,10,79,14)13K=29H(K)=29%19=10填入29K=01H(K)=01%19=01填入01K=23H(K)=23%19=4填入23K=44H(K)=44%19=6填入44K=55H(K)=55%19=17填入55K=20H(K)=20%19=1冲突Add=(1+23)%19=5填入20K=84H(K)=84%19=8填入84K=27H(K)=27%19=8冲突Add=(8+23)%19=12填入27K=68H(K)=68%19=11填入68K=11H(K)=11%19=11冲突Add=(11+23)%19=15填入11K=10H(K)=10%19=10冲突Add=(10+23)%19=14填入10K=79H(K)=79%19=3填入79K=14H(K)=14%19=14冲突Add=(14+23)%19=18填入14对此例，平均查找长度为ASL=(1+1+1+1+1+1+2+1+2+1+2+2+1+2)/14=19/14明显比采用线性探测法处理冲突为优计算机软件技术基础查找与排序三、散列查找012345三、散列查找查找算法如下：intrandomProbing(elemtypehash[],intrnd[],intn,intk){

/*hash:哈希表;rnd:随机数列；n:哈希表的表长；k：关键字*/

i=H(k);/*计算地址*/j=0;/*随机数列位置*/

add=i;/*随机探测位置*/ while(hash[add].key!=k&&hash[add].key!=0){

add=(i+rnd[j])%n; j++;

}

return(j);

}缺点：处理表满不方便。若hash[add].key=0表示此地址为空。计算机软件技术基础查找与排序三、散列查找查找算法如下：若hash[add].key=0表三、散列查找线性探测及随机探测的缺点：不能真正删除表中已有表项。删除表项会影响其他表项的查找。若把关键码为68的表项真正删除,以后在查找关键码为11的表项时就查不下去,会错误地判断表中没有关键码为11的表项。若想删除一个表项,只能给它做一个删除标记,进行逻辑删除,不能把它真正删去。逻辑删除的副作用是：在执行多次删除后,表面上看起来散列表很满,实际上有许多位置没有利用。当然，也可以物理删除表项，不过，需要将表项后面的各项前移计算机软件技术基础查找与排序三、散列查找线性探测及随机探测的缺点：计算机软件技术基础查找三、散列查找3）链地址法适用