81查找

2.对分查找021611222527334256778179013245687910111312lowmidhigh举例：K＝39K33low=mid+1midK56high=mid-1mid39经过与关键字33,56,39的比较，查找成功K==39查找成功K16high=mid-102161122252739334256778179013245687910111312lowmidhigh举例，K＝13midmidmidK33high=mid-1K02low=mid+1K11low=mid+1经过与关键字33,16,02,11的比较，查找失败n=13的折半查找判定树71..68..133101..24..68..911..131581224691113typedefstruct{intkey;datatypeinfo;}rec;intbinsearch(recr[],intn,intk){intlow,high,mid,found;low=1;high=n;found=0;while((low=high)&&(found==0)){mid=(low+high)/2;if(kr[mid].key)low=mid+1;elseif(k==r[mid].key)found=1;elsehigh=mid-1;}算法：if(found==1)returnmid;elsereturn0;}3.分块查找intblocksearch(recr[],refnd[],intb,intk,intn){inti=1,j;while((knd[i].key)&&(i=b))i++;if(ib){cout“notfound”;return0;}j=nd[i].link;while((jn)&&(k!=r[j].key)&&(r[j].key=nd[i].key))j++;if(k!=r[j].key){j=0;cout“notfound”;}returnj;}4.二叉排序树查找JD*t;intbstsearch(intk){JD*p,*q,*s;p=t;while(p!=NULL){if(k==p-data)return1;elseif(kp-data){q=p;p=p-lchild;else{q=p;p=p-rchild;}}s=newJD;s-data=k;s-lchild=s-rchild=NULL;if(t==NULL)t=s;elseif(kq-data)q-lchild=s;elseq-rchild=s;return0;}5.哈希查找（1）思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系，这样，不经过比较，一次存取就能得到所查元素。哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数可写成：addr(ai)=H(ki)，ai为一个记录，ki为关键字。哈希查找：利用哈希函数进行查找的过程。013NAN1BAI14OU2CHEN153DIAO16QIAN417518SUN6GAO19TANG7208219JIN22WU1023XAIO11LI2412MA25ZHAO举例，一组关键字：S={ZHAO,QIAN,SUN,LI,CHEN,DIAO,MA,BAI,OU,NAN,TANG,JIN,XIAO,WU,GAO,YI}哈希函数：关键字的第一个字符在字母表中的位序－1哈希表的存储结构:用一维数组HT[m]存放n个元素：0123m－1n：表长m：哈希表的容量(mn),哈希地址空间：0..m-1=n/m1：装填系数，一般取为0.65~0.85装填系数反映了哈希表的装满程度，是影响哈希表查找性能的重要参数。哈希表需要解决的两个问题：1.哈希函数H()的构造：2.解决冲突问题：冲突：H(Key1)==H(Key2),且Key1Key2不同的记录争夺同一个哈希地址；Key1与Key2称为同义词(2)哈希函数的构造方法1.直接定址法2.数字分析法3.平方取中法4.除留余数法5.折叠法6.随机数法取关键字或关键字的某个线性函数值为哈希地址：H(key)=key或H(key)=a×key＋b举例：学生档案，地址空间:000..999H(k)=k－98015001哈希地址000001002......学号980150019801500299015003......姓名王平李凯田爱玲..................特点：一般不会发生冲突，但适用面比较窄一、直接定址法二、数字分析法取关键字的若干位或其组合作哈希地址。适用于关键字位数比哈希地址位数大的情况。例：7个学生的学号为542422241542813678542228171542389671542541577542885376542193552哈希地址422836281396515853135三、平方取中法取关键字平方后中间几位作哈希地址。适用于关键字每一位上对某些数字的重复频率较高关键字(关键字)2哈希地址010000100000101100121000021012001440000440116013704003702061431054131020624731304731四、除留余数法对关键字取模作为哈希函数，即：H(key)=keymodp除数p的选择不当将会导致很多同义词出现；p一般取小于或等于表长的最大质数。五、折叠法将关键字分为几段，除最后一段外，其余各段都等长，将各段相加作为哈希地址，相加的方法有两种：移位叠加：各段向右靠齐相加。边界叠加：将奇数字段或偶数字段倒排后相加。六、随机数法取关键字的随机函数值作为哈希地址，即H(key)=random(key)适用于关键字长度不等的情况。(3)解决冲突的方法两个不同的关键字得到相同的哈希地址称为“冲突”，这两个关键字称为同义词，解决冲突就需要寻找别的地址。①开放地址法②链地址法①开放定址法当冲突发生时，形成一个探查序列，沿此序列逐个地址探查，直到找到一个空位置，将发生冲突的记录放在该地址中。探测序列：Hi=(H(key)+di)modmi=1,2,...,k(k=m-1)H(key)---hash函数值di---增量序列m---哈希表长增量di的三种取法：(1)线性探测再散列di=1,2,3,…,m-1(2)二次探测再散列di=12,-12,22,-22,…,k2,-k2(k≤m/2)(3)随机探测再散列di=随机数序列，②链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。key2636413844156812065125H(key)010212523126121201∧234∧567∧8∧9∧1011∧121526∧41∧68∧44∧06∧36∧25511238∧H(key)=keymod13哈希查找过程：给定k值计算H(k)此地址为空？关键字=k?按处理冲突的方法计算HiNN查找失败查找成功YY处理冲突平均搜索长度ASL的方法搜索成功Sn搜索不成功(登入新记录)Un开放线性探查法)(定址法随机探查法二次探查法11ln链地址法e