工程软件基础5(计算机软件技术基础)

哈尔滨工业大学3.1基本的查找技术(基于线性表的查找法)顺序查找对分查找分块查找第三章查找与排序技术哈尔滨工业大学顺序查找【查找过程】：从表的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者符合，查到所要找的元素为止。否则就是表中没有要找的元素，检索不成功。【适用条件】：顺序存储或链式存储的静态表均可。【特点】：对表结构为有序表、无序表均可适用；对存储结构为顺序存储和链式存储的表均适用；适合于短表，方法简单；不适合长表，检索起来太慢；平均查找长度比其他方法大，查找成功时：第三章查找与排序技术12n哈尔滨工业大学【查找算法】：intSearch(structsequenlistL,intkey){intk=0;while((kL.len)&&(L.a[k]!=key))k=k+1;if(k==L.len)k=-1;return(k);}第三章查找与排序技术#definemaxsizemaxlenstructsequenlist{Elemtypea[maxsize];intlen;}；哈尔滨工业大学有序表对分查找第三章查找与排序技术【查找过程】：首先选择表中间的一个记录，比较其关键字的值，若要找的记录的关键字值大，则再取表的后半部的中间记录进行比较；否则取前半部的中间记录进行比较，如此反复，直到找到为止。【适用条件】：采用顺序存储结构的有序表(按值非递减排列)【特点】：仅适用于有序表；只适用顺序存储结构的表。平均查找长度小，n50时，log2(n+1)-1哈尔滨工业大学•E.g：在下列数据中查找元素26：010205091113161921262731lowhighmiddlelowhighmiddlelowmiddlehigh第一次第二次第三次high第四次第三章查找与排序技术哈尔滨工业大学【查找算法】：#defeinemaxsizemaxlenstructsequenlist{Elemtypea[maxsize];intlen;}；intBinSearch(structsequenlistL,intkey){intlow,high,mid;low=0;high=L.len-1;while(low=high){mid=(low+high)/2;if(L.a[mid]==key)returnmid;if(L.a[mid]key)high=mid-1;if(L.a[mid]key)low=mid+1;}return-1;}第三章查找与排序技术哈尔滨工业大学分块查找（索引顺序查找）第三章查找与排序技术【查找过程】：将n个元素均匀地分成块，每块有s个记录，块间按大小排序，块内元素不排序。要建立一个块的最大（或最小）关键字表。查找时，先用对分法由最大关键字查出所在的块，再用线性法在块中查找。【适用条件】：分块有序表将长度为n的线性表分成m个子表，各子表的长度可以相等，也可以不等，但要求后一个子表中的每一个元素大于前一个子表中的所有元素。分块有序表由两部分组成：(1)、顺序存储的线性表；(2)、再建立一个索引表。其中对线性表的每一个子表建立一个索引结点，索引结点包含数据域和指针域。哈尔滨工业大学12345678910111213141516171822121389203342443824486058745786532248861713索引表查38成功structindnode{ElemtypeKey；intk；};数据域，存放字表中的最大值，其类型与线性表中元素相同指针域，指示子表中第一个元素在线性表中的序号第三章查找与排序技术哈尔滨工业大学基本查找技术的查找方法比较顺序查找对分查找分块查找平均查找长度最大(n+1)/2最小log2（n+1）-1两者之间表结构有序表无序表有序表分块有序表存储结构顺序存储线性链表顺序存储顺序存储线性链表第三章查找与排序技术哈尔滨工业大学3.2哈希表技术(计算公式查找法)基本概念常用哈希表第三章查找与排序技术哈尔滨工业大学3.2.1哈希(Hash)表的基本概念•Hash：指形式上杂乱无章，没有规律的一组元素队列。•Hash查找的基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较，一次存取就能得到所查元素的查找方法。•Hash函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数可写成：addr(ai)=H(ki)。其中：ai是表中的一个元素，addr(ai)是ai的存储地址，ki是ai的关键字。•Hash表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫Hash表。第三章查找与排序技术哈尔滨工业大学E.g:假设有一批关键字序列18,75,60,43,54,90,46，给定哈希函数：H(k)=k%13，存贮区的内存地址从1到15，则可得关键字哈希地址：H（18）=18%13=5H（75）=75%13=10H（60）=60%13=8H（43）=43%13=4H（54）=54%13=2H（90）=90%13=12H（46）=46%13=7第三章查找与排序技术表项序号1234567891011由Hash函数填入k：544318466075表项序号12131415由Hash函数填入k：90哈尔滨工业大学1.Hash冲突•哈希存贮中冲突的产生：直接查找表是一种理想的情形，即每一个关键字对应一个唯一的地址。当Hash表中的元素关键字k与Hash表项序号H之间关系不满足一一对应的条件，即对于2个不同关键字k1,k2,存在H(k1)＝H(k2)，则认为发生了元素冲突(collision)。在哈希存贮中，冲突是很难避免的。哈希函数选得比较差，则发生冲突的可能性越大。把相互发生冲突的关键字互称为“同义词”。第三章查找与排序技术哈尔滨工业大学E.g将关键字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入长度n为12的Hash表中，设Hash函数H(k)=INT(k/3)+1。表项序号123456789101112由Hash函数填入k：010205091113161921262731第三章查找与排序技术•Hash表技术关键是要处理好表中元素冲突问题。主要包括2方面的工作：1、构造合适的哈希函数。2、当冲突发生时，要有适当的解决冲突的方法。哈尔滨工业大学2.Hash函数的构造方法•直接定址法【构造】：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b比如：统计1-100岁的人口，用年龄做关键字，哈希函数可以就取关键字本身。【特点】：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少第三章查找与排序技术哈尔滨工业大学2.Hash函数的构造方法•分段折叠法【构造】：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希函数地址，称为折叠法。比如：关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加，即有5355＋8101＋1046＋430＝14932，舍去高位，则有H（430104681015355）＝4932为该身份证关键字的散列函数地址。【特点】：适于关键字位数很多，且每一位上数字分布大致均匀情况第三章查找与排序技术哈尔滨工业大学2.Hash函数的构造方法•除留余数法【构造】：取关键字被某个不大于哈希表表长n的数p除后所得余数作哈希地址，即H(key)=key%p，p≤n【特点】：简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词第三章查找与排序技术哈尔滨工业大学上文回顾•图的遍历•最小生成树•图的最短路径•基本查找方法•哈希表的基本概念概念及意义概念及意义顺序查找、对分查找、分块查找纵向优先DFS横向优先BFS哈尔滨工业大学第三章查找与排序技术3.2.2几种常用的Hash表•线性Hash表（采用开放定址法处理冲突）设表长度为n。对线性Hash表的查找首先要填入Hash表，然后才能查找取出。哈尔滨工业大学线性Hash表取出•(1)计算关键字k的Hash函数i=H(k);•(2)检查表中第i项的内容：如果第i项登记着关键字k，则取出该项元素即可；如果第i项为空，则Hash表中没有该关键字信息；如果第i项不空，且登记的不是关键字k，则将i＝(i+1)%n,转(2)继续检查。第三章查找与排序技术线性Hash表填入•(1)计算关键字k的Hash函数i=H(k);•(2)检查表中第i项的内容：如果第i项为空，则将k及其有关信息填入该项；如果第i项不空，则将i＝(i+1)%n,转(2)继续检查。哈尔滨工业大学E.g将关键字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入长度n为12的Hash表中，设Hash函数H(k)=INT(k/3)+1。第三章查找与排序技术得到的线性Hash表如下：表项序号关键字k冲突次数409011310926071901010513020216112102708162305112214哈尔滨工业大学#defineNN12structHnode{intflag;intc;intkey;};structHnode*LH;voidLinear_Hash(intm){intk;LH=(structHnode*)malloc(m*sizeof(structHnode));for(k=0;km;k++){LH[k].flag=0;LH[k].c=0;}}intHash_Function(intk){return(k/3+1);}//Hash表的长度//Hash表结点的类型//表项是否为空//发生冲突的次数//关键字//Hash空间的基地址//Hash函数//为Hash表申请空间//Hash表初始化第三章查找与排序技术哈尔滨工业大学intFlag_Linear_Hash(){intk,count=0;for(k=0;kNN;k++)if(LH[k].flag==0)count=count+1;return(count);}第三章查找与排序技术//判定Hash表中空项的个数voidInsert_Linear_Hash(int(*f)(int),intx){intk,c=0;if(Flag_Linear_Hash()==0){printf(线性表已满/n);return;}k=(*f)(x);while(LH[k-1].flag){k=k+1;c=c+1;if(k==NN+1)k=1;}//Hash表中填入元素//满Hash表无法插入//计算Hash码//判定冲突哈尔滨工业大学intLookup_Linear_Hash(int(*f)(int),intx){intk;k=(*f)(x);while((LH[k-1].flag&&LH[k-1].key!=x)){k=k+1;if(k==NN+1)k=1;}if((LH[k-1].flag)&&(LH[k-1].key==x))return(k);return(0);}LH[k-1].key=x;LH[k-1].flag=1;LH[k-1].c=c;return;}//填入元素//Hash表查找元素//计算Hash码//冲突项的处理第三章查找与排序技术哈尔滨工业大学线性Hash表的缺点•1：在线性Hash表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当Hash冲突较多时，会存在“堆聚”现象，降低查找效率。•2：线性Hash表的填入是不顾后效的。处理冲突时，会带来新的冲突。如上例，本来只有两对元素发生冲突，但采用开放定址法处理后，本来不冲突的元素也发生了冲突。•3：线性Hash表不能填满，否则在查找一个不存在的元素是会出现无限循环。第三章查找与排序技术定义：Hash表的填满率：，m：关键字个数，n：Hash表的长度。mn222E