第8章(查找表).ppt

第八章查找表
★基本概念
★静态查找表
★动态查找表
★ Hash法
North China Electric Power University
查找表:是一种以集合为逻辑结构,以查找为核
心运算,同时包括其他运算的数据结构。
关键字:用来标识数据元素的数据项,简称键。
★基本概念
主关键字:可以唯一标识一个数据元素的关键字。
次关键字:可以标识若干数据元素的关键字。
查找:根据某个给定的K值,在查找表中寻找一
个键值等于K的元素,若找到这样的元素,
则称查找成功,此时的运算结果为该数据
元素在查找表中的位置,否则称查找不成
功,运算结果为一特殊标志。
North China Electric Power University
North China Electric Power University
查找表
静态查找表
动态查找表
:Create(st)
:Search(st,k)
:Get(st,pos)
:Search(st,k)
:Get(st,pos)
:Initiate(st)
:Insert(st,k)
:Delete(st,k)
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
Procedure SqSearch(r:sqTable;k:KeyType);
Begin
r[n+1].key:=k;
i:=1;
while (r[i].key< >k) Do
i:=i+1;
if i<=n then Write(‘ i=’,i)
else Write(‘’);
End;
平均查找长度:为确定某元素在表中某位置所进行的比
较次数的期望值。
在长度为n的表中找某一元素,查找成功的平均查找长度:
ASL=∑PiCi
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
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].key<k,则k必在较高标号的那一半表中,
令low:=mid+1
再取中间项进行比较,直到查找成功或low>high(查找失败)为止。
North China Electric Power University
例:给出表元素关键字为:{05,13,19,21,37,56,64,75,80,88,92}
=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].k