科技数据结构及应用算法研究.pdfVIP

•查找表：

–由同一类元素或记录构成的集合。对数据元素间的关系未作限定。

•对查找表的操作有

–查找某个“特定”的元素是否在表中。

–查找某个“特点”的元素的各种属性。

–在查找表中一个元素。

–在查找表中删除一个元素

•静态查找表、动态查找表

•关键字

–数据元素中的某个数据项值。可以表示一个数据元素，如可以唯一

表示，则为主关键字（primarykey）。

•查找

–根据给定的某个值，在查找表中确定一个关键字等于给定值的数据

元素。若找到表示查找成功，返回该元素详细信息或在查找表中的

位置；负责返回NULL

8.1静态查找表

1.顺序查找

•算法8.1

–intSearch_Seq(SSTableST,KeyTypekval)设监视

哨

•例8.1在顺序查找表中查找成功和失败

•平均查找长度

–查找过程中先后和给定值进行比较的关键字的个

数的期望值

ASL＝∑PC∑P＝1i＝1，2，。。。。。n

iii

C＝n－i＋1P＝1/nASLss＝1/n∑（n－i＋1

ii

）=(n+1)/2

8.1.2折半查找

•折半查找（binarySearch）：二分查找。

•例8.2利用二分查找在顺序有序表中查找。

–算法8.2IntSearch_Bin(SStableST,KeyTypekval)

–ASL＝（n＋1）/nlog(n+1)-1

bs

01h-1hi-1

ASLbs=(2+2*2+…+2*h)Pi=1/n∑12*i

令i=t+1;S=∑1h2i-1*i=2∑1h2i-2*i=2∑0h-12t-1*(t+1)

=2∑0h-12t-1*t+2∑0h-12t-1

ht-1h-10-1h-1th-1h

=2(∑12*t-2*h+2*0)+∑02=2(S-2*h)+2-1

hh

S=2*h-2+1=(n+1)log(n+1)-(n+1)+1(n+1)log(n+1)-n

22

ASL=1/n*S=(n+1)/nlog(n+1)-1

bs2

8.1.3分块查找

•又称索引顺序查找

–介于顺序查和折半查找之间。适合于关键字分块有序

typedefstruct{

KeyTypekey;

intstadr;

}indexItem;

typedefstruct{

indexItem*elem;

intlength;

}indexTable;

–算法8.3Search_Idx(SSTableST,indexTableID,KeyTkval)

–设索引长度b，顺序表长度为n，则：

ASLidx=ASL(b)+ASL(n/b)≈log2(b+1)-1+(n/b+1)/2

8.2动态查找表

•对动态查找表进行的操作有

–InitDSTable（DT）

–DestroyDSTable