North China Electric Power University I 第八章查找表 ★基本概念 ★静态查找表 ★动态查找表 ★Hash法
第八章 查找表 ★ 基本概念 ★ 静态查找表 ★ 动态查找表 ★ Hash法 North China Electric Power University
North China Electric Power University I ★基本念 查找表:是一种以集合为逻辑结构,以查找为核 心运算,同时包括其他运算的数据结构 关鍵字:用来标识数据元素的数据项,简称键。 主关键字:可以唯一标识一个数据元素的关键字。 次关键字:可以标识若干数据元素的关键字。 查找:根据某个给定的K值,在查找表中寻找一 个键值等于K的元素,若找到这样的元素, 则称查找成功,此时的运算结果为该数据 元素在查找表中的位置,否则称查找不成 功,运算结果为一特殊标志
查找表：是一种以集合为逻辑结构，以查找为核 心运算，同时包括其他运算的数据结构。 关键字：用来标识数据元素的数据项，简称键。 ★ 基本概念 主关键字：可以唯一标识一个数据元素的关键字。 次关键字：可以标识若干数据元素的关键字。 查找：根据某个给定的K值，在查找表中寻找一 个键值等于K的元素，若找到这样的元素， 则称查找成功，此时的运算结果为该数据 元素在查找表中的位置，否则称查找不成 功，运算结果为一特殊标志。 North China Electric Power University
North China Electric Power University I 1建表: Create(st) 静态查找表2查找: Search(s,1) 3读表元:Ge(st;pos 查找表 1初始化: Initiate(t 2查找: Search(st,k) 动态查找表3读表元: Get(st, pos) 4插入: Insert(st,k) 5删除: Delete(st,k)
North China Electric Power University 查找表 静态查找表 动态查找表 1.建表：Create(st) 2.查找：Search(st,k) 3.读表元：Get(st,pos) 2.查找：Search(st,k) 3.读表元：Get(st,pos) 1.初始化：Initiate(st) 4.插入：Insert(st,k) 5.删除：Delete(st,k)
North China Electric Power University I ★静态查找表 1)顺序表上的查找:以顺序表作为存储结构,然后在这 个存储结构上实现静态査找表的基本运算 顺序表类型定义如下: Const maxsize=静态査找表的表长; Type rec=record key: Keytype End: sqTable-arraylo. maxsize of rec; n: Integer; 顶序查找过程:假定该查找表有n个记录,首先将要查找 的那个关键字赋给实际上并不存在的第n1个记录的关键 字域,然后从头开始一个一个的向下查找,用计数查 到就送出来看是第几个,若<=n,则查找成功,若=n+1 则查找失败
North China Electric Power University ★ 静态查找表 1)顺序表上的查找：以顺序表作为存储结构，然后在这 个存储结构上实现静态查找表的基本运算。 顺序表类型定义如下： Const maxsize=静态查找表的表长; Type Rec=Record key:KeyType; … End; sqTable=Array[0..maxsize] of Rec; n:Integer; 顺序查找过程：假定该查找表有n个记录，首先将要查找 的那个关键字赋给实际上并不存在的第n+1个记录的关键 字域，然后从头开始一个一个的向下查找，用i来计数,查 到就送出来看i是第几个，若i<=n，则查找成功，若i=n+1 则查找失败
North China Electric Power University I Procedure Sqsearch(r:sq Table; ke KeyType); begin rn+1. key: =k; l; while(rli. keyk) do i:=i+1 if i<=n then Write(Succ i=,i) else write( Unsucc’); End: 平均查找长度:为确定某元素在表中某位置所进行的比 较次数的期望值 在长度为n的表中找某一元素,查找成功的平均查找长度 ASL=∑PC1
North China Electric Power University Procedure SqSearch(r:sqTable;k:KeyType); Begin r[n+1].key:=k; i:=1; while (r[i].keyk) Do i:=i+1; if i<=n then Write(‘Succ i=’,i) else Write(‘Unsucc’); End; 平均查找长度：为确定某元素在表中某位置所进行的比 较次数的期望值。 在长度为n的表中找某一元素，查找成功的平均查找长度: ASL=∑PiCi
North China Electric Power University I P1:为查找表中第个元素的概率 C;1:为查到表中第个元素时已经进行的比较次数 在顺序查找时,C;取决于所查元素在表中的位置 i;=设每个元素的查找概率相等,即P=1,则 ASL=∑PcC1=(n+1)2 查找不成功的查找长度为n+1。 顺序查找表的优点:算法简单且适应面广,对表的结 构无任何要求,无论元素是否按关键字有序都可应用 顺序查找表的缺点:平均查找长度比较大,特别是当n 较大时,查找效率较低
North China Electric Power University Pi :为查找表中第i个元素的概率 Ci :为查到表中第i个元素时已经进行的比较次数 在顺序查找时，Ci取决于所查元素在表中的位置， Ci =i,设每个元素的查找概率相等，即Pi=1/n,则: ASL=∑PiCi=(n+1)/2 查找不成功的查找长度为n+1。 顺序查找表的优点：算法简单且适应面广，对表的结 构无任何要求，无论元素是否按关键字有序都可应用。 顺序查找表的缺点：平均查找长度比较大，特别是当n 较大时，查找效率较低
North China Electric Power University I 2)折半查找(有序表上进行查找): 基本思想:设三个指针ow,high和md分别指示待查有 序表的表头,表尾和中间元素,在开始查找时,三个 指针的初值分别为:low:=;hgh:=n;md:=(ow+high) div2。折半查找是从表的中间元素开始,用待查元素 的关键字k和 tImid. key比较,此时有三种情况(假设该 查找表按关键字的非递减次序排列): )若 tImid. key=k,则查找成功; 2)若 tImid key>k,则k必在较低标号的那一半表中, 令high:=mid-1 3)若 rmid. keyhgh查找 失败)为止
North China Electric Power University 2)折半查找(有序表上进行查找)： 基本思想：设三个指针low,high和mid分别指示待查有 序表的表头，表尾和中间元素，在开始查找时，三个 指针的初值分别为：low:=1;high:=n;mid:=(low+high) div 2 。折半查找是从表的中间元素开始，用待查元素 的关键字k和r[mid].key比较，此时有三种情况 (假设该 查找表按关键字的非递减次序排列) ： 1) 若r[mid].key=k，则查找成功； 2) 若r[mid].key>k，则k必在较低标号的那一半表中， 令 high:=mid-1 3) 若r[mid].keyhigh(查找 失败)为止
North China Electric Power University I 例:给出表元素关键字为:05,13,9,21,37567:8.892 1査找关键字k=21的情况 (I)low: =l; high: =ll; mid: =(1+lldiv 2=6 0513192137566475808892 lowl high 因为 rmid. key>k,所以向左找,令high:=md-1=5 (2 )low: =l;high: =5; mid: =(1+5)div 2=3 0513192137566475808892 mI hi 因为r| mid]. key<k,所以向右找,令low:=mid+1=4 (3)low:=4;high:=5;mid:=(4+5div2=4 0513192137566475808892 lowl I mid I high 因为 mid key==k,查找成功,所查元素在表中的序号为md的值
North China Electric Power University 例：给出表元素关键字为：{05,13,19,21,37,56,64,75,80,88,92} 1.查找关键字k=21 的情况 (1) low:=1;high:=11;mid:=(1+11) div 2=6 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key>k，所以向左找，令high:=mid-1=5 (2) low:=1;high:=5;mid:=(1+5) div 2=3 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key<k，所以向右找，令low:=mid+1=4 (3) low:=4;high:=5;mid:=(4+5) div 2=4 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key=k，查找成功，所查元素在表中的序号为mid 的值
North China Electric Power University I 2查找关键字k=85的情况 D)low:l; high: =ll; mid: =(1+11)div 2=6 0513192137566475808892 m high 因为r| mid keyk,所以向左找,high:=mid-1=9 因为ow>high,所以查找失败
North China Electric Power University (1) low:=1;high:=11;mid:=(1+11) div 2=6 因为r[mid].keyk，所以向左找，high:=mid-1=9 2.查找关键字k=85 的情况 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为low>high，所以查找失败
North China Electric Power University I Procedure Bin Search(r: stAble; k: KeyType); Begin OW high: =n; while low<=high Do I mid: =(lowthigh) div 2; ase krlmid. key: low: =mid+1; krlmid. key: write(mid); Return; I k<rlmid key: high: =mid-1; End case: Write(Unsucc) End
North China Electric Power University Procedure BinSearch(r:sqTable;k:KeyType); Begin low:=1; high:=n; while lowr[mid].key: low:=mid+1; k=r[mid].key: [Write(mid);Return;] k<r[mid].key: high:=mid-1; EndCase; ] Write(‘Unsucc’); End;