算法13--静态查找表

,第8章查找,2,本章主要内容8.1静态查找表8.2动态查找表8.3哈希表,3,基本概念,1什么是查找表是由同一类型的数据元素(或记录)组成的数据集合。2.对查找表经常进行的操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。,4,3.查找表分类,动态查找表,静态查找表,4.关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。,5,5.查找,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或(记录)。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。,例：高考成绩表示,typedeffloatKeyType;/实型typedefintKeyType;/整型typedefchar*KeyType;/字符串型数据元素类型定义为：typedefstructKeyTypekey;/关键字域/其它域ElemType;。,典型的关键字类型说明：,对两个关键字的比较约定为如下的宏定义：/对数值型关键字#defineEQ(a,b)(a)=(b)#defineLT(a,b)(a)(b)#defineLQ(a,b)(a)=(b)/对字符串型关键字#defineEQ(a,b)(!Strcmp(a),(b)#defineLT(a,b)(Strcmp(a),(b)0)#defineLQ(a,b)(Strcmp(a),(b)=0),典型的关键字类型说明：,对两个关键字的比较约定为如下的宏定义：/对数值型关键字#defineEQ(a,b)(a)=(b)#defineLT(a,b)(a)(b)#defineLQ(a,b)(a)=(b)/对字符串型关键字#defineEQ(a,b)(!Strcmp(a),(b)#defineLT(a,b)(Strcmp(a),(b)0)#defineLQ(a,b)(Strcmp(a),(b)x，把查找区间缩小到表的前半部分，再继续进行对分查找；Lmid.Keyx，把查找区间缩小到表的后半部分，再继续进行对分查找。每比较一次，查找区间缩小一半。如果查找区间已缩小到一个记录，仍未找到想要查找的记录，则查找失败。,2有序表的查找：折半查找（二分法查找）,4/29/2020,4/29/2020,4/29/2020,折半查找算法描述,intSearch_Bin(SSTableST,KeyTypekey)/在有序表ST中折半查找其关键字等于key的数据元素。/若找到，则函数值为该元素在表中的位置，否则为0。low=1;high=ST.length;/置区间初值while(lowlchild,R,sw,low,i-1);/构造左子树if(i=high)T-rchild=NULL;/右子树空elseSecondOptimal(T-rchild,R,sw,i+1,high);/构造右子树returnOK;/SecondOptimal,4/29/2020,StatusCreateSOSTre(SOSTree/CreatSOSTree,4/29/2020,(a),(b),4/29/2020,三、索引顺序表的查找(分块查找)索引顺序表的查找是鉴于顺序查找和折半查找的一种查找。索引顺序表是由索引表和顺序表两部分组成。索引顺序表的特点是把若干个数据元素分成若干块，每一块称为一个顺序表，要求块与块之间要有序，即第i+1块的所有元素的关键字要大于第i块的所有元素的关键字。为了查找方便，为每一块建立一个索引项：索引项：(key,addr),key域标记该块中最大记录的关键字，addr域指向该块的起始地址。索引表是由若干索引项组成的有序表。,4/29/2020,例：,4/29/2020,分块查找的数据结构：D=d1,d2,.,dn1.将n个数据元素分为s个块B1,B2,Bs；2.块之间有序：Bi+1中的任一元素小于Bi中的任一元素(i=1,2,n-1)；3.为每个Bi块设一索引项(keyi,addri)；4.s个索引项构成索引表；5.块内可有序也可无序;,4/29/2020,在索引顺序表中查找的基本思想:首先在索引表中查找，确定该查找的元素在哪个块中(可以是折半查找，也可以是顺序查找)。2.先确定待查记录所在块，再在块内查找(顺序查找)。3.算法实现typedefstructIndexTypekeyTypemaxkey;/*块中最大的关键字*/intstartpos;/*块的起始位置指针*/Index;,4/29/2020,intBlock_search(RecTypeST,Indexind,KeyTypekey,intn,intb)/*在分块索引表中查找关键字为key的记录*/*表长为n，块数为b*/inti=0,j,k;while(ib)printf(nNotfound);return(0);j=indi.startpos;while(jn|!EQ(STj.key,key)j=0;printf(nNotfound);return(j);,4/29/2020,4.算法分析：设表长为n个记录，均分为b块，每块记录数为s，则b=n/s。设记录的查找概率相等，每块的查找概率为1/b，块中记录的查找概率为1/s，则平均查找长度ASL：,设在索引表中和块内都是顺序查找。索引表中查找：ALSindex=(s+1)/2块中查找：ALSlock=(n/s+1)/2所以：ALSbs=(s+1)/2+(n/s+1)/2=(n/s+s)/2+1显然它与s的取值有关。当时，ASLbs有最小值,4/29/2020,例n=10000;s=100;,则顺序查找：ASL=(n+1)/25000次,索引顺序表退化成有序表,即可进行折半查找,索引顺序表退化成顺序表,即可进行顺序查找,当s=n时,当s=1时,4/29/2020,Fibonacci查找,Fibonacci查找方法是根据Fibonacci数列的特点对查找表进行分割。Fibonacci数列的定义是：F(0)=0，F(1)=1，F(j)=F(j-1)+F(j-2)。1查找思想设查找表中的记录数比某个Fibonacci数小1，即设n=F(j)-1。用Low、High和Mid表示待查找区间的下界、上界和分割位置，初值为Low=1，High=n。取分割位置Mid：Mid=F(j-1)；比较分割位置记录的关键字与给定的K值：,4/29/2020,相等：查找成功；大于：待查记录在区间的前半段(区间长度为F(j-1)-1)，修改上界指针：High=Mid-1，转；小于：待查记录在区间的后半段(区间长度为F(j-2)-1)，修改下界指针：Low=Mid+1，转；直到越界(LowHigh)，查找失败。2算法实现在算法实现时，为了避免频繁计算Fibonacci数，可用两个变量f1和f2保存当前相邻的两个Fibonacci数，这样在以后的计算中可以依次递推计算出。,4/29/2020,intfib(intn)inti,f,f0=0,f1=1;if(n=0)return(0);if(n=1)return(1);for(i=2;i=n;i+)f=f0+f1;f0=f1;f1=f;return(f);intFib_search(RecTypeST,KeyTypekey,intn)/*在有序表ST中用Fibonacci方法查找关键字为key的记录*/intLow=1,High,Mid,f1,f2;High=n;f1=fib(n-1);f2=fib(n-2);while(Low=High)Mid=Low+f1-1;,4/29/2020,if(EQ(ST.Mid.key,key)return(Mid);elseif(LT(key,