算法13静态查找表课件

第第8 8章章 查找查找 2 本章主要内容本章主要内容8 8.1.1 静态查找表静态查找表8 8.2.2 动态查找表动态查找表8 8.3.3 哈希表哈希表3 基本概念1什么是查找表什么是查找表 是是由由同同一一类类型型的的数数据据元元素素(或或记记录录)组组成成的的数数据据集合。集合。2.对查找表经常进行的操作对查找表经常进行的操作1）查询查询某个“特定的”数据元素是否在查找表中；2）检索检索某个“特定的”数据元素的各种属性；3）在查找表中插入插入一个数据元素；4）从查找表中删去删去某个数据元素。43.查找表分类查找表分类 动态查找表动态查找表静态查找表静态查找表4.关键字关键字 是数据元素（或记录）中某个数据项的值，用以标标识识（识别）一个数据元素（或记录）。若此关键字可以识别唯唯一一的的一个记录，则称之谓“主关键字主关键字”。若此关键字能识别若干记录，则称之谓“次次关关键键字字”。55.查找查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或(记录)。若查找表中存在这样一个记录，则称“查查找找成成功功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查查找找不不成成功功”，查找结果：给出“空记录”或“空指针”。例：高考成绩表示例：高考成绩表示准考证号姓名各科成绩总分政治语文外语数学物理化学生物.179325179326179327.陈红陈红陆华陆华张平张平.847685.768488.746573.938779.876962.765763.877178.635455.typedef float KeyType;/实型typedef int KeyType;/整型typedef char *KeyType;/字符串型数据元素类型定义为：typedef struct KeyType key;/关键字域 /其它域ElemType;。典型的关键字类型说明典型的关键字类型说明：对两个关键字的比较约定为如下的宏定义：/对数值型关键字#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)(!Strcmp(a),(b)#define LT(a,b)(Strcmp(a),(b)0)#define LQ(a,b)(Strcmp(a),(b)x，把查找区间缩小到表的前半部分，再继续进行对分查找；Lmid.Key x，把查找区间缩小到表的后半部分，再继续进行对分查找。每比较一次，查找区间缩小一半。如果查找区间已缩小到一个记录，仍未找到想要查找的记录，则查找失败。2 2 有序表的查找：有序表的查找：折半查找（二分法查找）折半查找（二分法查找）例例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找21lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid7/15/2024例例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid7/15/20241 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：描述查找过程的二叉树判定树：描述查找过程的二叉树1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 927/15/2024折半查找算法描述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 data=T-data=RiRi;/;/生成结点生成结点构造次优二叉树的算法构造次优二叉树的算法7/15/2024if(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;/SecondOptimal7/15/2024Status CreateSOSTre(SOSTree&T,SSTable ST)Status CreateSOSTre(SOSTree&T,SSTable ST)/由有序表由有序表 ST ST 构造一棵次优查找树构造一棵次优查找树 T T。/ST /ST 的数据元素含有权域的数据元素含有权域 weightweight if(ST.length=0)T=NULL;if(ST.length=0)T=NULL;else else FindSW(sw,ST);FindSW(sw,ST);/按照有序表按照有序表 ST ST 中各数据元素的中各数据元素的 weight weight 值值 求累计权值表求累计权值表 SecondOpiamal(T,ST.elem,sw,1,ST.length);SecondOpiamal(T,ST.elem,sw,1,ST.length);return OK;return OK;/CreatSOSTree/CreatSOSTree7/15/2024CBDAE(a)BADCE(b)3 3E E2929D D2 230301 1C CB BA A例：例：有序表有序表 对应权值对应权值7/15/2024三、索引顺序表的查找三、索引顺序表的查找(分块查找分块查找)索引顺序表的查找索引顺序表的查找是鉴于是鉴于顺序查找顺序查找和和折半查找折半查找的一种查找。的一种查找。索引顺序表索引顺序表是由是由索引表索引表和和顺序表顺序表两部分组成。两部分组成。索引顺序表的特点索引顺序表的特点是把若干个数据元素分成若干块，每一块是把若干个数据元素分成若干块，每一块称为一个称为一个顺序表，顺序表，要求块与块之间要有序，即第要求块与块之间要有序，即第i+1块的所块的所有元素的关键字要大于第有元素的关键字要大于第i块的所有元素的关键字。块的所有元素的关键字。为了查找方便，为每一块建立一个为了查找方便，为每一块建立一个索引项：索引项：索引项索引项：(key,addr),key 域标记该块中最大记录的关键字，域标记该块中最大记录的关键字，addr域指向该块的起始地址。域指向该块的起始地址。索引表索引表是由若干是由若干索引项索引项组成的有序表。组成的有序表。7/15/202422 15 13 8 17 20 35 24 33 40 36 29 50 48 60 49 54 6122 40 611 7 13最大关键字最大关键字(key)key)起始地址起始地址(addr)addr)第一块第一块索引索引第三块第三块第二块第二块例：例：7/15/2024分块查找的数据结构：分块查找的数据结构：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.块内可有序也可无序块内可有序也可无序;7/15/2024在索引顺序表中查找的基本思想在索引顺序表中查找的基本思想:1.首先在索引表中查找，确定该首先在索引表中查找，确定该查找的元素查找的元素在哪个块在哪个块中中(可以是折半查找，也可以是顺序查找可以是折半查找，也可以是顺序查找)。2.先确定待查记录所在块，再在块内查找先确定待查记录所在块，再在块内查找(顺序查找顺序查找)。3.算法实现算法实现typedef struct IndexType keyType maxkey;/*块中最大的关键字块中最大的关键字 */int startpos;/*块的起始位置指针块的起始位置指针 */Index;7/15/2024int Block_search(RecType ST,Index 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);7/15/20244.算法分析算法分析：设表长为设表长为n个记录，均分为个记录，均分为b块，每块记录数为块，每块记录数为s，则则b=n/s。设记录的查找概率相等，每块的查找概率为。设记录的查找概率相等，每块的查找概率为1/b，块中记录的查找概率为，块中记录的查找概率为1/s，则，则平均查找长度平均查找长度ASL：ASL=Lb+Lw=j+j=1b i=i=1ss12b+12s+1+设在索引表中和块内都是顺序查找。设在索引表中和块内都是顺序查找。索引表中查找：索引表中查找：ALSindex=(s+1)/2块中查找：块中查找：ALSlock=(n/s+1)/2所以：所以：ALSbsbs=(s+1)/2+(n/s+1)/2=(n/s+s)/2+1显然它与显然它与s 的取值有关。当的取值有关。当 时，时，ASLbs有最小值有最小值 7/15/2024 例例 n=10000;s=100;则则顺序查找顺序查找：ASL=(n+1)/2 5000次次 100次次分块查找分块查找:ASLbs=(n/s+s)/2+1 100次次分块查找分块查找:Min(ASLbs)=()索引顺序表索引顺序表退化成有序表退化成有序表,即可进行即可进行折半查找折半查找索引顺序表索引顺序表退化成顺序表退化成顺序表,即可进行即可进行顺序查找顺序查找当当s=n时时,当当s=1时时,折半查找折半查找:ASL14 次次7/15/2024 Fibonacci查找 FibonacciFibonacci查找方法是根据查找方法是根据FibonacciFibonacci数列的特点数列的特点对查找表进行分割。对查找表进行分割。FibonacciFibonacci数列的定义是：数列的定义是：F(0)=0F(0)=0，F(1)=1F(1)=1，F(j)=F(j-1)+F(j-2)F(j)=F(j-1)+F(j-2)。1 1 查找思想查找思想 设查找表中的记录数比某个设查找表中的记录数比某个FibonacciFibonacci数小数小1 1，即，即设设n=F(j)-1n=F(j)-1。用。用LowLow、HighHigh和和MidMid表示待查找区间的下表示待查找区间的下界、上界和分割位置，初值为界、上界和分割位置，初值为Low=1Low=1，High=nHigh=n。取分割位置取分割位置MidMid：Mid=Mid=F(j-1)F(j-1)；比较比较分割位置记录的关键字与给定的分割位置记录的关键字与给定的K K值：值：7/15/2024 相等相等：查找成功；查找成功；大于大于：待查记录在区间的前半段：待查记录在区间的前半段(区间长度为区间长度为F(j-1)-1)，修改上界指针：，修改上界指针：High=Mid-1，转，转；小于小于：待查记录在区间的后半段：待查记录在区间的后半段(区间长度为区间长度为F(j-2)-1)，修改下界指针：，修改下界指针：Low=Mid+1，转，转；直到越界直到越界(LowHigh)，查找失败。，查找失败。2 算法实现算法实现 在算法实现时在算法实现时，为了避免频繁计算，为了避免频繁计算Fibonacci数，数，可用两个变量可用两个变量f1和和f2保存当前相邻的两个保存当前相邻的两个Fibonacci数，数，这样在以后的计算中可以依次递推计算出。这样在以后的计算中可以依次递推计算出。7/15/2024int 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;7/15/2024if(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查找的优点是分割时只需进行加、减运算。查找的优点是分割时只需进行加、减运算。7/15/2024顺序查找顺序查找折半查找折半查找分块查找分块查找ASLASL最大最大最小最小两者之间两者之间表结构表结构有序表、无有序表、无序表序表有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构顺序存储结构顺序存储结构线性链表线性链表查找方法比较查找方法比较