③第八章查找表 ·8.1概述 ·8,2静态查找表 ·8.3动态查找表 84哈希表及其查找 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第八章 查找表 • 8.1概述 • 8.2静态查找表 • 8.3动态查找表 • 8.4哈希表及其查找
③8.1概述 查找表: 由同一类元素或记录构成的集合。对数据元素间的关系未作限定。 对查找表的操作有 查找某个“特定”的元素是否在表中。 查找某个“特点”的元素的各种属性。 在查找表中插入一个元素。 在查找表中删除个元素 静态查找表、动态查找表 关键字 数据元素中的某个数据项值。可以标识一个数据元素,如可以唯一 标识,则为主关键字( primary key)。 查找 根据给定的某个值,在查找表中确定一个关键字等于给定值的数据 元素。若找到表示查找成功,返回该元素详细信息或在查找表中的 位置;否则返回NULL pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 • 查找表： – 由同一类元素或记录构成的集合。对数据元素间的关系未作限定。 • 对查找表的操作有 – 查找某个“特定”的元素是否在表中。 – 查找某个“特点”的元素的各种属性。 – 在查找表中插入一个元素。 – 在查找表中删除一个元素 • 静态查找表、动态查找表 • 关键字 – 数据元素中的某个数据项值。可以标识一个数据元素，如可以唯一 标识，则为主关键字（primary key）。 • 查找 – 根据给定的某个值，在查找表中确定一个关键字等于给定值的数据 元素。若找到表示查找成功，返回该元素详细信息或在查找表中的 位置；否则返回NULL 8.1概述
③82静态查找表 typedef struct( Datatype data;∥元素数据 Key Type key;∥元素关键字 } Elemtype;/数据元素类型 typedef struct( E! emtype*elem;∥约定从下标1开始 Int en } StaticSrhtable;/顺序静态查找表类型 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 8.2静态查找表 typedef struct{ Datatype data; //元素数据 KeyType key; //元素关键字 }Elemtype; //数据元素类型 typedef struct{ Elemtype *elem; //约定从下标1开始 int len; }StaticSrhTable; //顺序静态查找表类型
821顺序查找 算法81 int SeqSearch( StaticSrhTable SsT, Key Type kval /*在顺序表SST中顺序查找关键字为kvl的记录。 若找到,则返回记录在表中的位序;否则,返回0 SSTelem( 0]. key = kval ∥放置监视哨 for(i= SSTlen; SSTelem i]keyl=kval;i-);∥查找 return 1 ∥查找结果 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 8.2.1顺序查找 算法8.1 int SeqSearch(StaticSrhTable SST, KeyType kval) { /* 在顺序表SST中顺序查找关键字为kval的记录。 若找到，则返回记录在表中的位序；否则，返回0 */ SST.elem[0].key = kval; // 放置监视哨 for (i = SST.len; SST.elem[i].key != kval; i--); // 查找 return i; // 查找结果 }
例8.1在顺序查找表中查找成功和失败 平均查找长度 查找过程中先后和给定值进行比较的关键字的个 数的期望值 AsL=∑PfC;∑P;=1i=1,2 n C;=n-i+1P;=1/n ASLs1/n∑(n-i+1)=(n+1)/2 pboustc. edu. cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 • 例8.1在顺序查找表中查找成功和失败 • 平均查找长度 – 查找过程中先后和给定值进行比较的关键字的个 数的期望值 ASL＝∑PiCi ∑Pi＝1 i＝1，2，。。。。。n Ci＝n－i＋1 Pi＝1/n ASLss＝1/n∑（n－i＋1）=(n+1)/2
822折半查找(顺序有序表) 折半查找( binary Search):二分查找。 int Bin Search(StaticSrhTable Sst, Key type kval)t bot=l, top=SST.len //置査找范围初值 while(bot=top mid =(bot+top)/2 if(SST.elem[mid].key=kval) return mid;/查找成功 else if(SST.elem[mid]. key>kval)top=mid-1;//前半区 else bot≡mid+1; //后半区 return 0 //未查找到 pboustc. edu. cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 8.2.2折半查找(顺序有序表) 折半查找（binary Search）：二分查找。 int BinSearch(StaticSrhTable SST, KeyType kval){ bot=1, top=SST.len; // 置查找范围初值 while(botkval) top=mid-1;//前半区 else bot =mid+1; // 后半区 } } return 0; // 未查找到 }
二分査找平均查找长度(假设满二叉树) ASLhe=(n+1)/nlog(n+1) ASLb=(20+2*2+…+21+h)Pin21*2-(n=21 i=t+1 令:S=∑hi*21-1=*24-2 2zb-1(t+1)2-1 b-1t*2-1+2b-12-1=2b1(t+1)2-1 2(ht*2-1-h*2h-1)+2b12 =2(S-h*2h-)+2h-1 所以:S=h*2h-2h+1=(n+1)log2(n+1)-n aSls=S=log2(n+1)-1 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 二分查找平均查找长度（假设满二叉树） ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(2 0+2 1*2+…+2 h-1*h)Pi=
③8.2.3分块查找(索引顺序) 又称索引顺序查找 介于顺序查和折半查找之间。适合于关键字分块有序 typedef struct Ke e ke Int stadr Bindexltem typedef struct( Indexltem selem Int length Indexable 设索引长度b,顺序表长度为n,则: ASLidx Asl(b+asl(/b -log2(b+1)-1+(n/b+1)/2 pboustc. edu. cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 • 又称索引顺序查找 – 介于顺序查和折半查找之间。适合于关键字分块有序 typedefstruct { KeyType key; int stadr; }indexItem; typedefstruct{ indexItem *elem; int length; }indexTable; 设索引长度b，顺序表长度为n，则： ASLidx=ASL(b)+ASL(n/b)≈log2(b+1)-1+(n/b+1)/2 8.2.3分块查找（索引顺序）
state BlkInxSearch(StaticSrhTable SST, InxTab Inx, Key Type kval) bot=1,top=nx|en, blFound= FALSE;∥置查找范围初值 if(kva|> Inxelem[top]key) return0;∥越界 while(bot kva)top=md-1;∥前半区 else bot mid +1 ∥后半区 }∥退出循环时,bot所指的为所找的块 bn=inκelem[bo! StartEd;∥第bot块的数据记录起始地址 if (bot < Inx. len en= Inx elem[bot 1]. StartAdd-1 else en= sst.len ∥第bot块的数据记录尾地址 for(i=bn; (<=en)&& (SsTelemi]. key ! =kval); i ++ if (i<=en return i return 0 ∥查找到
state BlkInxSearch(StaticSrhTable SST, InxTab Inx, KeyType kval){ bot = 1, top = Inx.len, blFound = FALSE; // 置查找范围初值 if (kval > Inx.elem[top].key) return 0; // 越界 while (bot kval) top = mid - 1; // 前半区 else bot = mid + 1; // 后半区 } } //退出循环时，bot所指的为所找的块 bn = Inx.elem[bot].StartAdd; //第bot块的数据记录起始地址 if (bot < Inx.len) en = Inx.elem[bot + 1].StartAdd – 1; else en = SST.len; //第bot块的数据记录尾地址 for (i = bn; (i <= en) && (SST.elem[i].key != kval); i++); if (i <= en) return i; return 0; //未查找到 } 为什么选择bot 而不是top?
③索引顺序查找 索引表 块内最大关键字1726487696 块的起始序号 1518 SSTelem 171016821262347304032484229765268869682 1234567891011121314151617 1920 pboustc. edu. cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 索引顺序查找 索引表 17 26 48 76 96 1 5 8 15 18 块内最大关键字 块的起始序号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 17 10 16 8 21 26 23 47 30 40 32 48 42 29 76 52 68 86 96 82 SST.elem