数据结构与算法基础(第三版)第五章查找

数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-15.1线性查找5.2折半查找5.3分快查找5.4二元查找树5.5散列法第五章查找数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-2查找分类传统的查找方法较先进的查找方法（散列法）线性查找折半查找分快查找二元查找树几个概念：查找表：由同一类型的数据元素（或纪录）构成的集合。关键字：数据元素中某一数据项的值，用以表示一个数据元素。静态查找：查找+提取数据元素属性信息动态查找：查找+（插入或删除元素）查找：根据给定的值，在查找表中确定一个其关键字等于给定值的纪录或数据元素。数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-3IntSearch(k,last,F)Keytyoek,intlast;LISTF;/*在F中查找关键字为k的纪录，若找到，则返回该纪录所在的下表，否则返回0*/{inti;F[0].key=k;i=last;while(F[i].key!=k)i=i–1;returni;}/*Search*/Structrecords{keytypekey;fieldsother;}TypedefrecordsLIST[maxsize];LISTF;5.1线性查找算法一：顺序表数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-4LISTSearch(k,F)Keytypek;LISTF;{LISTp;p=F;while(p!=NULL)if(p-data.key==k)returnp;elsep=p-next;returnp;}Structcelltype{recordsdata;celltype*next;}Typedefcelltype*LIST;算法二：链表数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-5性能分析定义为确定纪录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearchLength)。设Pi为查找表中第i个记录的概率。∑Pi=1Ci为比较次数ASL=∑Pi·Cini=1在等概率情况下Pi=1/n，且一般情况下Ci=n－i+1ASL=nP1+(n-1)P2+…+2Pn-1+Pn=1/n·∑(n－i+1)ni=1=(n+1)/2数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-65.2折半查找查找表=[05,13,19,21,37,56,64,75,80,88,92]Key=210513192137566475808892Low=1mid=6Up=11Up=5mid=3Low=4,mid=40513192137566475808892Low=1mid=6Up=11Key=85low=5mid=9Low=10,mid=10Low=10Up=9数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-7Intbinary-search(keytypek,LISTF){intlow,up,mid;low=0;up=last;while(low=up){mid=(low+up)/2;if(F[mid].key==k)returnmid;elseif(F[mid].keyk)up=mid–1;elselow=mid+1;}return–1}折半查找算法折半查找算法分析6391471025811hn=2h-1(h=log2(n+1))ASLbs=∑Pi·CiPi=1/nni=1=1/n·∑j·2j-1hj=1=(n+1)/n·log2(n+1)-1平均查找长度ASLbs=log2(n+1)-1O(log2n)数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-8intBsearch(F,i,j,k){intm;if(ij)return(-1);else{m=(i+j)/2;if(F[m].key==k)returnm;if(F[m].keyk)return(Bsearch(F,i,m-1,k));elsereturn(Bsearch(F,m+1,j,k));}}数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-95.3分块查找(线性查找+折半查找)224474012IX221213983342443824486058744701234567891011121314F索引表Intindex_search(k,last,blocks,ix,F,L)Keytypek;intlast,blocks;indexixLISTF;intL;{inti,j;i=0;while((kix[i])&&(iblocks))i++;if(iblocks){j=i*L;while((k!=F[j].key)&&(j=(i+1)*L-1)&&(jlast))j=j+1;if(k==F[j].key)returnj;}return–1;}Typedefkeytypeindex[maxblock]数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-105.4二元查找树(二元排序树)1031415121671518Structcelltype{recordsdata;celltype*lchild,*rchild;}Typedefcelltype*BST;BSTsearch(keytypek,BSTF);{p=F;if(p==NULL)returnNull;elseif(k==p-data.key)returnp;elseif(Kp-data.key)return(search(k,p-lchild));elseif(Kp-data.key)return(search(k,p-rchild));}数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-11Voidinsert(recordsR,BST&F){if(F==NULL){F=newcelltype;F-data=R;F-lchild=NULL;F-rchild=NULL;}elseif(R.keyF-data.key)insert(R.key,F-lchild)elseif(R.keyF-data.key)insert(R.key,F-rchild)}在二元查找树中插入新结点数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-12在二元查找树中删除结点1051437121811516删除之前10514371215116删除18之后10515371218116删除14之后数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-13Voiddelete(keytypek,BST&F){if(F!=NULL)if(kF-data.key)delete(k,f-lchild);elseif(kF-data.key)delete(k,f-rchild);elseif(F-rchild==NULL)F=F-lchild;elseif(F-lchild==NULL)F=F-rchild;elseF-data=deletemin(F-rchild)}在二元查找树中删除结点Recordsdeletemin(F){recordstmp;BSTp;if(F-lchild==NULL){p=F;tmp=F-data;F=F-rchild;deletep;returntmp;}elsereturn(deletemin(F-lchild);}数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-14例：二元树用二元链表表示，且每个结点的键值互不相同，编写算法判别该二元树是否为二元排序树。intjudge(BTree*bt){BTree*s[100],*p=bt;inttop=0,preval=min;do{while(p){s[top++]=p;p=p-lchild;}if(top0){p=s[--top];if(p-datapreval)return0;//不是二元排序树preval=p-data;p=p-rchild;}}while(p||top0);return(1)；//是二元排序树}数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-155.5散列法——哈希（Hash）查找散列法——地址散列法被查找元素的存储地址=Hash(Key)KeyBEIJING（北京)TIANJIN(天津)HEBEI(河北)SHANXI(山西)SHANGHAI(上海)SHANGDONG(山东)HENAN(河南)SICHUAN(四川)f1(key)0220081919190819f2(key)0904172828262203f3(key)0426021323171616例：全国30个地区的人口统计，每个地区为一个记录，内容如下：编号地区名总人口汉族回族…f1(key):取关键字第一个字母在字母表中的序号f2(key):求第一和最后字母在字母表中序号之和，然后取30的余数f3(key):将第一个字母的八进制看成十进制，再取30的余数数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-16Hash查找的关键问题①构造Hash函数②制订解决冲突的方法散列（Hash）函数（表）分类内散列表（数组）外散列表（链表）构造散列函数（Hash）的几种方法：直接定址法：Hash(key)=key;或Hash(key)=a·key+b;质数除余法平方取中法折叠法数字分析法随机数法解决冲突的方法：开放定址法再散列法链地址法建立一个公共溢出区数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-17地址0102030405…252627…100年龄12345…252627…100人数300020005000…6000……：地址0102030405…252627…100年份194919501951…1973…人数300020005000…6000……：直接定址法：Hash(key)=key;或Hash(key)=a·key+b;例一：Hash(key)=key例二：Hash(key)=key+（-1949）+1数据结构与算法D.S.第五章查找国家示范性软件学院·秋Slide.5-18质数除余法设桶数B，取质数m≤BHash(key)=key%m平方取中法取key2的中间的几位数作为散列地址记录keykey2HashA0100001000001