算法13-静态查找表.ppt

《算法13-静态查找表.ppt》由会员分享，可在线阅读，更多相关《算法13-静态查找表.ppt（53页珍藏版）》请在三一办公上搜索。

1、,第8章 查找,2,本章主要内容8.1 静态查找表8.2 动态查找表8.3 哈希表,3,基本概念,1什么是查找表 是由同一类型的数据元素(或记录)组成的数据集合。2.对查找表经常进行的操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。,4,3.查找表分类,动态查找表,静态查找表,4.关键字 是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。,5,5.查找,根据

2、给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或(记录)。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。,例：高考成绩表示,typedef float KeyType;/实型typedef int KeyType;/整型typedef char*KeyType;/字符串型数据元素类型定义为：typedef struct KeyType key;/关键字域/其它域ElemType;。,典型的关键字类型说明：,对两个关键字的比较约定为如下的宏定义：/对数值型关键字#

3、define EQ(a,b)(a)=(b)#define LT(a,b)(a)(b)#define LQ(a,b)(a)=(b)/对字符串型关键字#define EQ(a,b)(!Strcmp(a),(b)#define LT(a,b)(Strcmp(a),(b)0)#define LQ(a,b)(Strcmp(a),(b)=0),典型的关键字类型说明：,对两个关键字的比较约定为如下的宏定义：/对数值型关键字#define EQ(a,b)(a)=(b)#define LT(a,b)(a)(b)#define LQ(a,b)(a)=(b)/对字符串型关键字#define EQ(a,b)(!Str

4、cmp(a),(b)#define LT(a,b)(Strcmp(a),(b)0)#define LQ(a,b)(Strcmp(a),(b)=0),典型的关键字类型说明：,静态查找数据类型定义：ADT StaticSearchTable 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有 类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。,8.1静态查找表,8.1.1顺序表的查找,/静态查找表的顺序存储结构：typedef struct ElemType*elem;/数据元素存储空间基址，建表时按实长度分配，0号单 元留空int length;/表长度SST

5、able;,8.1.1顺序表的查找,int Search_Seq(SSTable ST,KeyType key)ST.elem 0.key=key;/“哨兵”for(i=ST.length;!EQ(ST.elemI.key,key);i);/从后往前找Return i;/找不到时，i 为0/Search_Seq,“顺序”的含义：从表尾（或表头）开始以顺序方式搜索查找表，将关键字与给定值进行比较。查找的顺序与数据元素的存储位置有关系，与数据元素的值没有关系。,ST.elem,回顾顺序表的查找过程：,假设给定值 e=64,要求 ST.elemi=e,i=?,20,7,ST.elem,ST.elem

6、,60,kval=64,kval=60,64,哨兵,改进,查找成功时平均查找长度(A S L)为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中:n 为表长,Pi 为查找表中第i个记录的查找概率，且 Ci为找到该记录时，曾和给定值比较过的关键字的个数。,分析顺序查找的时间性能,在等概率查找的情况下，顺序表查找的平均查找长度为：,ASL=nP1+(n-1)P2+2Pn-1+Pn,对顺序表 a1,a2,an 而言:C1=n,Ci=n-i+1,Cn=1,如果查找概率无法事先测定，则查找过程采取的改进办法是，(1)在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上；(2)每

7、个记录附设一访问频度域，按访问频度非递减有序排列。,在不等概率查找的情况下，如果 已知每个数据元素的概率，则当 PnPn-1P2P1 时，ASLss取极小值，即：为提高查找效率，,概率大的记录应该放在表尾！,2 有序表的查找：折半查找（二分法查找）,1)算法思想：要求n个记录存放在一个顺序表L中，并按其关键码从小到大排好了序，称此表为有序表。先求位于查找区间正中的记录的下标mid，用其关键码与给定值x比较:Lmid.Key=x，查找成功；Lmid.Key x，把查找区间缩小到表的前半部分，再继续进行对分查找；Lmid.Key x，把查找区间缩小到表的后半部分，再继续进行对分查找。每比较一次，查

8、找区间缩小一半。如果查找区间已缩小到一个记录，仍未找到想要查找的记录，则查找失败。,2 有序表的查找：折半查找（二分法查找）,折半查找算法描述,int Search_Bin(SSTable ST,KeyType key)/在有序表ST中折半查找其关键字等于key的数据元素。/若找到，则函数值为该元素在表中的位置，否则为0。low=1;high=ST.length;/置区间初值while(low=high)mid=(low+high)/2;if(key=ST.elemmid.key)return mid;/找到待查元素 else if(key ST.elemmid.key)high=mid-1;

9、/继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找return 0;/顺序表中不存在待查元素/Search_Bin,从折半查找法可知：找到第6个数仅需比较1次，找到第3和第9个数需2次，找到第1，4，7，10个数需3次，找到第2，5，8和11个数需4次。查找过程可以用下图的二叉树来表示。查找某个结点所比较的次数等于该结点的层次数。实际上查找某个结点的过程就是从根结点到相应的结点的路径。,查找成功时进行比较的次数最多不超过该树的深度。而具有n个结点的判定树的深度为log2n1。所以折半查找法在查找成功时的比较次数最多为log2n+1次。如果考虑到查找不成功的情况，则

10、判定树如下所示（方框表示查找不成功的情况）：,由此可见，查找不成功时的最多比较次数也是log2n+1。,2 4 6 8 10 13 15 18 20 22 24 25 27 30,15,6,2,4,10,8,13,24,20,27,18,22,25,30,算法分析：List:1 2 3 4 5 6 7 8 9 10 11 12 13 14,折半查找的判定树：有2n+1个结点，高度不超过完全二叉树。,最多的比较次数不超过完全二叉树的高度：所以：最坏情况下的查找长度是：查找成功的平均查找长度：设查找任一记录的概率都相等，即：pi=1/n 在第k层上最多有2k-1 个结点，在第k层上的结点需 比较k

11、次。所以：,ASL=(n1)/n*log2(n+1)-1log2(n+1)-1优点：比较次数少，检索速度快。缺点：要将元素按关键码排序，且只适用于顺序存储结构。,折半查找法的优缺点,3、静态树表的查找,在概率不等的查找情况下，折半查找不是有序表最好的查找方法。,关键字:A B C D E Pi:0.1 0.2 0.1 0.4 0.2 Ci:2 3 1 2 3,例如:,此时 ASL=20.1+30.2+10.1+20.4+30.2=2.3,若改变Ci的值 3 2 3 1 2,则 ASL=30.1+20.2+30.1+10.4+20.2=1.8,如果只考虑查找成功的情况，则使其查找性能达最佳的判定

12、树是其带权内路径长度之和PH值（和平均查找长度成正比）取最小值的二叉树。,称PH值取最小的二叉树为静态最优查找树。由于构造静态最优查找树花费的时间代价较高，所以构造近视最优查找树的有效算法。,选择二叉树的根结点，使 达最小,为便于计算，引入累计权值和 并设 wl-1=0 和 swl-1=0，则推导可得,0,2,3,8,11,15,18,23,例如:,l,h,21,18,12,4,3,10,18,h,9,6,0,8,E,C,2,1,A,h,5,3,l,h,G,3,0,1,3,查找比较“总次数”=32+41+25+33+14+33+25=52,查找比较“总次数”=32+21+35+13+34+23

13、+35=59,E,C,G,B,D,F,和折半查找相比较,D,B,A,C,F,E,G,所得次优二叉树如下:,A,Status SecondOptimal(BiTree/生成结点,构造次优二叉树的算法,if(i=low)T-lchild=NULL;/左子树空else SecondOptimal(T-lchild,R,sw,low,i-1);/构造左子树 if(i=high)T-rchild=NULL;/右子树空 else SecondOptimal(T-rchild,R,sw,i+1,high);/构造右子树 return OK;/SecondOptimal,Status CreateSOSTre

14、(SOSTree/CreatSOSTree,(a),(b),三、索引顺序表的查找(分块查找)索引顺序表的查找是鉴于顺序查找和折半查找的一种查找。索引顺序表是由索引表和顺序表两部分组成。索引顺序表的特点是把若干个数据元素分成若干块，每一块称为一个顺序表，要求块与块之间要有序，即第i+1块的所有元素的关键字要大于第i块的所有元素的关键字。为了查找方便，为每一块建立一个索引项：索引项：(key,addr),key 域标记该块中最大记录的关键字，addr域指向该块的起始地址。索引表是由若干索引项组成的有序表。,例：,分块查找的数据结构：D=d1,d2,.,dn1.将n个数据元素分为s个块 B1,B2,

15、Bs；2.块之间有序：Bi+1中的任一元素小于Bi中的任一元 素(i=1,2,n-1)；3.为每个Bi块设一索引项(keyi,addri)；4.s个索引项构成索引表；5.块内可有序也可无序;,在索引顺序表中查找的基本思想:首先在索引表中查找，确定该查找的元素在哪个块中(可以是折半查找，也可以是顺序查找)。2.先确定待查记录所在块，再在块内查找(顺序查找)。3.算法实现typedef struct IndexType keyType maxkey;/*块中最大的关键字*/int startpos;/*块的起始位置指针*/Index;,int Block_search(RecType ST,Ind

16、ex ind,KeyType key,int n,int b)/*在分块索引表中查找关键字为key的记录*/*表长为n，块数为b*/int i=0,j,k;while(ib)printf(nNot found);return(0);j=indi.startpos;while(jn|!EQ(STj.key,key)j=0;printf(nNot found);return(j);,4.算法分析：设表长为n个记录，均分为b块，每块记录数为s，则b=n/s。设记录的查找概率相等，每块的查找概率为1/b，块中记录的查找概率为1/s，则平均查找长度ASL：,设在索引表中和块内都是顺序查找。索引表中查找：

17、ALSindex=(s+1)/2块中查找：ALSlock=(n/s+1)/2所以：ALSbs=(s+1)/2+(n/s+1)/2=(n/s+s)/2+1显然它与s 的取值有关。当 时，ASLbs有最小值,例 n=10000;s=100;,则顺序查找：ASL=(n+1)/2 5000次,索引顺序表退化成有序表,即可进行折半查找,索引顺序表退化成顺序表,即可进行顺序查找,当s=n时,当s=1时,Fibonacci查找,Fibonacci查找方法是根据Fibonacci数列的特点对查找表进行分割。Fibonacci数列的定义是：F(0)=0，F(1)=1，F(j)=F(j-1)+F(j-2)。1 查

18、找思想 设查找表中的记录数比某个Fibonacci数小1，即设n=F(j)-1。用Low、High和Mid表示待查找区间的下界、上界和分割位置，初值为Low=1，High=n。取分割位置Mid：Mid=F(j-1)；比较分割位置记录的关键字与给定的K值：,相等：查找成功；大于：待查记录在区间的前半段(区间长度为F(j-1)-1)，修改上界指针：High=Mid-1，转；小于：待查记录在区间的后半段(区间长度为F(j-2)-1)，修改下界指针：Low=Mid+1，转；直到越界(LowHigh)，查找失败。2 算法实现 在算法实现时，为了避免频繁计算Fibonacci数，可用两个变量f1和f2保存

19、当前相邻的两个Fibonacci数，这样在以后的计算中可以依次递推计算出。,int fib(int n)int i,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);int Fib_search(RecType ST,KeyType key,int n)/*在有序表ST中用Fibonacci方法查找关键字为key的记录*/int Low=1,High,Mid,f1,f2;High=n;f1=fib(n-1);f2=fib(n-2);while(Low=High)Mid=Low+f1-1;,if(EQ(ST.Mid.key,key)return(Mid);else if(LT(key,ST.Mid.key)High=Mid-1;f2=f1-f2;f1=f1-f2;else Low=Mid+1;f1=f1-f2;f2=f2-f1;return(0);由算法知，Fibonacci查找在最坏情况下性能比折半查找差，但折半查找要求记录按关键字有序；Fibonacci查找的优点是分割时只需进行加、减运算。,查找方法比较,