算法静态查找表课件

第8章查找

本章主要内容8.1静态查找表8.2动态查找表8.3哈希表2基本概念1．什么是查找表

是由同一类型的数据元素(或记录)组成的数据集合。2.对查找表经常进行的操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。33.查找表分类

动态查找表静态查找表4.关键字

是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。

若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。

若此关键字能识别若干记录，则称之谓“次关键字”。45.查找

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或(记录)。

若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。5例：高考成绩表示准考证号姓名各科成绩总分政治语文外语数学物理化学生物...179325179326179327......陈红陆华张平.......847685......768488......746573......938779......876962......765763......877178......635455..typedeffloatKeyType;//实型typedefintKeyType;//整型typedefchar*KeyType;//字符串型数据元素类型定义为：typedefstruct{KeyTypekey;//关键字域

//其它域}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))<=0)典型的关键字类型说明：

静态查找数据类型定义：ADTStaticSearchTable{

数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。

数据关系R：数据元素同属一个集合。

8.1静态查找表基本操作P初始条件操作结果Create(&ST,n)构造一个含n个数据元素的静态查找表ST。Destroy(&ST)静态查找表ST存在。销毁表ST。Search(ST,key)静态查找表ST存在，key为和关键字类型相同的给定值。若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST,Visit())静态查找表ST存在，Visti是对元素操作的应用函数。按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。8.1.1顺序表的查找//静态查找表的顺序存储结构：typedefstruct{ ElemType*elem;//数据元素存储空间基址，建表时按实长度分配，0号单元留空

intlength;//表长度}SSTable;

8.1.1顺序表的查找

intSearch_Seq(SSTableST,KeyTypekey){ ST.elem[0].key=key;//“哨兵”

for(i=ST.length;!EQ(ST.elem[I].key,

key);――i);//从后往前找

Returni;//找不到时，i为0}//Search_Seq

“顺序”的含义：从表尾（或表头）开始以顺序方式搜索查找表，将关键字与给定值进行比较。

查找的顺序与数据元素的存储位置有关系，与数据元素的值没有关系。ST.elem回顾顺序表的查找过程：假设给定值e=64,要求ST.elem[i]=e,i=?iii207ST.elemiST.elemi60ikval=64kval=60i64ii哨兵改进

查找成功时平均查找长度(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)每个记录附设一访问频度域，按访问频度非递减有序排列。在不等概率查找的情况下，如果已知每个数据元素的概率，则当

Pn≥Pn-1≥···≥P2≥P1时，

ASLss取极小值，即：为提高查找效率，概率大的记录应该放在表尾！

2有序表的查找：折半查找（二分法查找）1)算法思想：要求n个记录存放在一个顺序表L中，并按其关键码从小到大排好了序，称此表为有序表。先求位于查找区间正中的记录的下标mid，用其关键码与给定值x比较:

L[mid].Key==x，查找成功；

L[mid].Key>x，把查找区间缩小到表的前半部分，再继续进行对分查找；

L[mid].Key<x，把查找区间缩小到表的后半部分，再继续进行对分查找。每比较一次，查找区间缩小一半。如果查找区间已缩小到一个记录，仍未找到想要查找的记录，则查找失败。2有序表的查找：折半查找（二分法查找）例1234567891011513192137566475808892找21lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh1185210741936判定树：描述查找过程的二叉树1234567891011513192137566475808892折半查找算法描述intSearch_Bin(SSTableST,KeyTypekey){

//在有序表ST中折半查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0。low=1;high=ST.length;//置区间初值while(low<=high)

{

mid=(low+high)/2;

if(key==ST.elem[mid].key)

returnmid;//找到待查元素

elseif(key<ST.elem[mid].key)

high=mid-1;//继续在前半区间进行查找

elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}//Search_Bin从折半查找法可知：找到第6个数仅需比较1次，找到第3和第9个数需2次，找到第1，4，7，10个数需3次，找到第2，5，8和11个数需4次。查找过程可以用下图的二叉树来表示。查找某个结点所比较的次数等于该结点的层次数。实际上查找某个结点的过程就是从根结点到相应的结点的路径。6391471025811查找成功时进行比较的次数最多不超过该树的深度。而具有n个结点的判定树的深度为log2n＋1。所以折半查找法在查找成功时的比较次数最多为log2n+1次。如果考虑到查找不成功的情况，则判定树如下所示（方框表示查找不成功的情况）：由此可见，查找不成功时的最多比较次数也是log2n+1。6391471025811-13-46-79-101-23-44-55-67-88-910-1111-246810131518202224252730156241081324202718222530算法分析：List[]:1

234

5

678910

11121314

折半查找的判定树：有2n+1个结点，高度不超过完全二叉树。最多的比较次数不超过完全二叉树的高度：所以：最坏情况下的查找长度是：

查找成功的平均查找长度：设查找任一记录的概率都相等，即：pi=1/n

在第k层上最多有2k-1

个结点，在第k层上的结点需比较k次。所以：ASL=(n＋1)/n*log2(n+1)-1≈log2(n+1)-1优点：比较次数少，检索速度快。缺点：要将元素按关键码排序，且只适用于顺序存储结构。折半查找法的优缺点3、静态树表的查找

在概率不等的查找情况下，折半查找不是有序表最好的查找方法。关键字:ABCDEPi:0.10.2

0.10.4

0.2

Ci:23123例如:此时

ASL=20.1+30.2+10.1+20.4+30.2=2.3若改变Ci的值32312则ASL=30.1+20.2+30.1+10.4+20.2=1.8

如果只考虑查找成功的情况，则使其查找性能达最佳的判定树是其带权内路径长度之和PH值（和平均查找长度成正比）取最小值的二叉树。称PH值取最小的二叉树为静态最优查找树。由于构造静态最优查找树花费的时间代价较高，所以构造近视最优查找树的有效算法。选择二叉树的根结点，使达最小为便于计算，引入累计权值和并设wl-1=0和swl-1=0，则推导可得023811151823例如:lh211812431018h9608EC21Ah53lhG3013查找比较“总次数”=32+41+25+33+14+33+25=52查找比较“总次数”=32+21+35+13+34+23+35=59ECGBDF和折半查找相比较DBACFEG所得次优二叉树如下:AStatusSecondOptimal(BiTree&T,ElemTypeR[],floatsw[],intlow,inthigh){//由有序表R[low..high]及其累计权值表sw//递归构造次优查找树T。

选择最小的ΔPi值

if(!(T=(BiTree)malloc(sizeof(BiTNode))))returnERROR;T->data=

R[i];//生成结点构造次优二叉树的算法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);

//构造右子树

returnOK;}//SecondOptimalStatusCreateSOSTre(SOSTree&T,SSTableST){//由有序表ST构造一棵次优查找树T。//ST的数据元素含有权域weightif(ST.length=0)T=NULL;else{FindSW(sw,ST);

//按照有序表ST中各数据元素的weight值求累计权值表

SecondOpiamal(T,ST.elem,sw,1,ST.length);}returnOK;}//CreatSOSTreeCBDAE(a)BADCE(b)3E29D2301CBA例：有序表

对应权值三、索引顺序表的查找(分块查找)索引顺序表的查找是鉴于顺序查找和折半查找的一种查找。索引顺序表是由索引表和顺序表两部分组成。索引顺序表的特点是把若干个数据元素分成若干块，每一块称为一个顺序表，要求块与块之间要有序，即第i+1块的所有元素的关键字要大于第i块的所有元素的关键字。为了查找方便，为每一块建立一个索引项：索引项：(key,addr),key域标记该块中最大记录的关键字，addr域指向该块的起始地址。索引表是由若干索引项组成的有序表。221513817203524334036295048604954612240611713最大关键字(key)起始地址(addr)第一块索引第三块第二块例：分块查找的数据结构：D={d1,d2,….,dn}1.将n个数据元素分为s个块B1,B2,…,Bs；2.块之间有序：Bi+1中的任一元素小于Bi中的任一元素(i=1,2,…,n-1)；3.为每个Bi块设一索引项(keyi,addri)；4.s个索引项构成索引表；5.块内可有序也可无序;在索引顺序表中查找的基本思想:首先在索引表中查找，确定该查找的元素在哪个块中(可以是折半查找，也可以是顺序查找)。2.

先确定待查记录所在块，再在块内查找(顺序查找)。3.算法实现typedefstructIndexType{keyTypemaxkey;/*块中最大的关键字*/intstartpos;/*块的起始位置指针*/}Index;intBlock_search(RecTypeST[],Indexind[],KeyTypekey,intn,intb)/*在分块索引表中查找关键字为key的记录*//*表长为n，块数为b*/{inti=0,j,k;while((i<b)&<(ind[i].maxkey,key))i++;if(i>b){printf("\nNotfound");return(0);}j=ind[i].startpos;while((j<n)&&LQ(ST[j].key,ind[i].maxkey)){if(EQ(ST[j].key,key))break;j++;}/*在块内查找*/if(j>n||!EQ(ST[j].key,key)){j=0;printf("\nNotfound");}return(j);}4.算法分析：设表长为n个记录，均分为b块，每块记录数为s，则b=⌈n/s⌉。设记录的查找概率相等，每块的查找概率为1/b，块中记录的查找概率为1/s，则平均查找长度ASL：ASL=Lb+Lw=∑j+j=1b∑i=i=1ss―12b+12s+1+设在索引表中和块内都是顺序查找。索引表中查找：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次

≈100次分块查找:ASLbs=(n/s+s)/2+1≈100次分块查找:Min(ASLbs)=()索引顺序表退化成有序表,即可进行折半查找索引顺序表退化成顺序表,即可进行顺序查找当s=n时,当s=1时,折半查找:ASL≈14

次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值：①相等