【学习目的要求】:查找方法评价通常以“给定值与数据元素的关键码值比较”作为基本操作，用“关键码值的比较次数”来衡量查找算法的时间性能，
“关键码值的比较次数”称为查找长度。平均查找长度ASL(AverageSearchLength)：为确定记录在表中的
位置，所需进行的关键码比较次数的期望值平均查找长度ASL顺序检索举例intseqsearch(sqlistR[],ke
ytypek){inti=n;R[0].key=k;/设置R[0]为监视哨/w
hile(R[i].key!=k)i--;returni;/返回检索结果
i/}折半查找要求：查找表必须为有序表查找过程：先确定待查找记录的范围
然后逐步缩小范围直到：查找成功或不成功折半查找递归算法已知一个长度为16的顺序表
L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是（）A：4??B：5??
C：6???D：7查找步骤：首先用给定值在索引表中查找，确定满足条件的数据元素应存放在哪一块中，对索引表查找
的方法既可以采用二分法查找，也可以采用顺序查找，然后再到相应的块中进行顺序查找，便可以得到查找的结果。对线性表进行二分查找时，
要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D
.以链接方式存储,且数据元素有序【燕山大学2001一.5（2分）】当在一个有序的顺序存储表上查找一个数据时，即可用折半
查找，也可用顺序查找，但前者比后者的查找速度()A.必定快B.不一定C.在大部分情况下要
快D.取决于表递增还是递减【南京理工大学一.7（2分）】在有序表A[1…20]中，按二分查找方法进行查找，
查找长度为4的元素的下标从小到大依次是__________【合肥工业大学2000三.10（2分）】分块检索中，若索引
表和各块内均用顺序查找，则有900个元素的线性表分成_________块最好：若分成25块，其平均查找长度为_________。
【北京工业大学一.5(2分)】线性探测法示例线性探测法示例(续)－继续插入
57,76,51,84哈希查找过程作业设有关键字(13,29,01,23,44,55,20,84,
27,68,11,10,79,14)记录，用除留余数法(p=17)，分别采用线性探测、平方探测、随机探测(序列:3,1
6,55,44)和链地址法解决冲突，建立Hash表，并分别计算ASL下面关于哈希(Hash，杂凑)查找的说法正确的是(
)A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在
特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可将10个元
素散列到100000个单元的哈希表中，则（）产生冲突。A.一定会B.一定不会
C.仍可能会如图:随机给出一些关键字，取平方后的第2到3位为函数地址。关键字（关键字）2
函数地址010000100001100
1210000120014400001160
137040020614310541
利用平方取中法得到散列函数地址01214
43731将关键字分割成位数相同若干部分（最后一部分的位数可以不同），然后取它们的叠加和（舍弃高位进位）为哈希地址。
有两种叠加处理的方法：移位叠加和间界叠加。4.折叠法此方法适合于:关键字的数字位数特别多。
x=12320324111220从左到右按3个位数—段分割，共得到5个段：123、203、241、112、20。采用移位叠加得
到：A(x)＝123+203+241+112+20＝699若采用间界叠加，则从左到右来回折叠中，第二、四段
反转为302和211得到：B(x)＝123+302+241+211+20＝897移位叠加：将分割后的几部
分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加5.除留余数法设定哈希函数为:
H(key)=keyMODp其中，p≤m(表长)并且p应为不大于m的素数或
是不含20以下的质因子给定一组关键字为：12,39,18,24,33,21，若取p=9,则他们对应的哈
希函数值将为：3,3,0,6,6,3例如：为什么要对p加限制？可见，若p中含质因子3，则所
有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。6.随机数法设定哈希函数为:H(k
ey)=Random(key)其中，Random为伪随机函数通常，此方法用于对长度不等的关键字构造哈希函数
。实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲
突的可能性降到尽可能地小。选取哈希函数，考虑以下因素：计算哈希函数所需时间关键码长度哈希表长度（哈希地址范围）关键码分布
情况记录的查找频率三、处理冲突的方法“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开
放定址法2.链地址法为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,…,Hs
1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di)MODm
i=1,2,…,s1.开放定址法对增量di有三种取法：1)线
性探测再散列di=c?i最简单的情况c=12)平方探测再散列di=12,-
12,22,-22,…,3)随机探测再散列di是一组伪随机数列或者di=i×H2(ke
y)(又称双散列函数探测)例表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key
MOD11,现有第4个记录，其关键字为38，按线性探测、二次探测处理冲突的方法，将它填入表中01
2345678910601729(1)H(3
8)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5+
2)MOD11=7冲突H3=(5+3)MOD11=8不冲突38(2)H(38)=
38MOD11=5冲突H1=(5+12)MOD11=6冲突H2=(5-
12)MOD11=4不冲突38线性探测：二次探测：(3)H(38)=38MOD11=5冲突
设伪随机数序列为9，则：H1=(5+9)MOD11=3不冲突关键字为(13,19,39,
24,28,57,76,51,84)，散列表长m=13，散列函数为H(key)=key%1101
23456789
101112??13???39?19?????
?1???1?1??????1324??3919
??????12??11??????1324
?392819??????12?121???
??132457?392819?????123?1
21???012345
6789101112??13
2457?392819?76????123?121?
1????132457?3928195176????1
23?12131????132457?3928195
17684???123?121315?2.链地址法
将所有关键码为同义词的记录存储在一个单链表中，并用一维数组存放头指针，用链地址法解决冲突建立的散列表也叫开散列表。例
已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key
)=keyMOD13,012345678910111214^1
27796855198420231011^^^^^^^^^^^^查找过
程和造表过程一致。假设采用开放定址处理冲突，则查找过程为：四、哈希表的查找对于给定值K，计算哈希地址
i=H(K)若r[i]=NULL则查找不成功若r[i].key=K则查找成功否则“求下一地址Hi
”，直至r[Hi]=NULL(查找不成功)或r[Hi].key=K(查找成功)
为止。给定k值计算H(k)此地址为空查找失败Y关键字==kN查找成功Y按处理冲突方法计算HiN哈希查找分
析哈希查找过程仍是一个给定值与关键码进行比较的过程评价哈希查找效率仍要用ASLinthashsize[]={997
,...};typedefstruct{ElemTypeelem;intcount;
//当前数据元素个数intsizeindex;//hashsi
ze[sizeindex]为当前容量}HashTable;#defineSUCCESS1#defineUNSU
CCESS0#defineDUPLICATE-1//---开放定址哈希表的存储结构---StatusSea
rchHash(HashTableH,KeyTypeK,
int&p,int&c){//在开放定址哈希表H中查找关键码为K的记录}//S
earchHashp=Hash(K);//求得哈希地址while(H.elem[p].key!=
NULLKEY&&!EQ(K,H.elem[p].key)）
collision(p,++c);//求得下一探查地址pif(EQ(K,H.elem[p].key))
returnSUCCESS;//查找成功，返回待查数据元素位置
pelsereturnUNSUCCESS;//查找不成功StatusInsertHash(HashTable
&H,Elemtypee){}//InsertHashc=0;if(HashSearc
h(H,e.key,p,c)==SUCCESS)returnDUPLICATE;
//表中已有与e有相同关键字的元素elseH.elem[p]=e;++H.co
unt;returnOK;//查找不成功时，返回p为插入位置elseRecreate
HashTable(H);//重建哈希表if(cndex]/2){//冲突次数c未达到上限，（阀值c可调）}
例已知一组关键字(19,14,23,1,68,20,84,27,55,
11,10,79)哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设
每个记录的查找概率相等(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MODmH(55)=3冲突，
H1=(3+1)MOD16=4冲突，H2=(3+2)MOD16=5H(79)=1冲突
，H1=(1+1)MOD16=2冲突，H2=(1+2)MOD16=3
冲突，H3=(1+3)MOD16=4冲突，H4=(1+4)MOD16=5
冲突，H5=(1+5)MOD16=6冲突，H6=(1+6)M
OD16=7冲突，H7=(1+7)MOD16=8冲突，
H8=(1+8)MOD16=90123456789
101112131415ASL=(16+2+33+41+91)/12=2.51416827
5519208479231110H(19)=6H(14)=1H(23)=10H(1)=1冲突，H
1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6冲突，H1=(6+1)MOD16=7
冲突，H2=(6+2)MOD16=8H(27)=1冲突，H1=(1+1)MOD16=2
冲突，H2=(1+2)MOD16=3冲突，H3=(1+3)MOD16
=4H(11)=11H(10)=10冲突，H1=(10+1)MOD16=11冲突，H
2=(10+2)MOD16=12(2)用二次探测再散列处理冲突，即Hi=(H(key)+di)MODmH(55)=3
冲突，H1=(3+12)MOD16=4H(79)=1冲突，H1=(1+12)MOD16=2
冲突，H2=(1﹣12)MOD16=0冲突，H3=(1+22)MOD16=
5冲突，H4=(1﹣22)MOD16=1301234
56789101112131415ASL=(16+22+33+
51)/12=214168275519208479231110H(19)=6H(14)=1H(2
3)=10H(1)=1H(68)=3H(20)=7H(84)=6冲突，H1=(6+12)MOD16=7
冲突，H2=(6﹣12)MOD16=5H(27)=1冲突，H1=(1+12)MOD16=2
冲突，H2=(1-12)MOD16=0H(11)=11H(10)=10冲突，H1=(10+
12)MOD16=11冲突，H2=(10﹣12)MOD16=9关键字(19,14,23
,1,68,20,84,27,55,11,10,79)冲突，H1=(1+12)MOD16=2(2)用拉链法处理冲突A
SL=(16+24+31+41)/12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,
79)012345678910111214^12779685519842
0231011^^^^^^^^^^^^1)选用的哈希函数；2)选用的处理冲突的方法；3
)哈希表饱和的程度，装载因子α=n/m值的大小（n—记录数，m—表的长度）决定哈希表查找的ASL的
因素：哈希表查找的分析:从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。一般情况下，可以认
为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的ASL是处理冲突方法和装载因子的
函数。线性探测再散列链地址法随机探测再散列可以证明：查找成功时有下列结果：从以上结果可见：哈希表的平均查找长度是
?的函数，而不是n的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子?，使得平均查找长度限定在
某个范围内。——这是哈希表所特有的特点。假设n=2h-1并且查找概率相等则在n>50时，可得近似结果
一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。【2010年全国硕士研究生
入学计算机学科专业基础综合试题】例对于给定11个数据元素的有序表{2,3,10,15,20,25,28,29,30,35,40
},采用二分查找,试问：(1)若查找给定值为20的元素,将依次与表中哪些元素比较？(2)若查找
给定值为26的元素,将依次与哪些元素比较？(3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度和查找
不成功时的平均查找长度。二分查找判定树(2)若查找给定值为26的元素,依次与25,30,28元素比较,共比较3次。
(3)在查找成功时,会找到图中某个圆形结点,则成功时的平均查找长度：(1)若查找给定值为20的元素,依次
与表中25,10,15,20元素比较,共比较4次。在查找不成功时,会找到图中某个方形结点,则不成功时的平均查找长度：索
引顺序查找又称分块查找，它是顺序查找方法的一种改进方法，是介于顺序查找和二分法查找之间的一种折中查找方法。它的基本思想是把线性表
分成若干块，在每一块中数据元素的存放次序是任意的，但是块与块之间必须有序，即前一块中的最大关键字必须小于后一块中的最小关键字。另
外还要建立一个索引表，把每块中最大的关键字值按关键字值大小存入索引表，使索引表保持为有序表。索引顺序表索引表A的每个元素包含两
个字段，一个是该块的最大关键字值，另一个是指向子表的指针。【索引顺序查找算法】分块查找的速度比顺序查找要快得多，但又不如二分法
查找。如果线性表元素个数很多，且被分成的块数b很大时，对索引表的查找可以采用二分法查找，还能进一步提高速度。例如，给定关键字
序列如下：{22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53},假设B=3
，即将该序列分成3个子表（如何划分此处不考虑），每个子表有6个元素，则得到的主表和索引表如图：538649745860
48243844423320981312221371864822以每块中最大关键字作为该块所
有元素的索引12345678910111213
14151617182212138920334244382448
6058745786532248861713索引表
查38索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度【分析索引
顺序查找的平均查找长度】当时，ASL取最小，即所以，ASL=(n/s+s)/2+1其中，n是线
性表中数据元素个数，s是每块中的元素个数【三种查找方法比较】顺序、链式均可，索引表顺序存储表中元素逐段有序次小分块查找
仅适用于顺序存储顺序、链式结构均可表的存储结构仅适用于有序表有序表、无序表均可表的结构等概率查找最小最大平均查找长
度折半查找顺序查找7.2动态查找树表一、哈希表是什么？二、哈希函数的构造方法三、处理冲
突的方法四、哈希表的查找7.3哈希表前面讨论的表示查找表的各种结构的共同特点：记录在表中的位置和
它的关键字之间不存在一个确定的关系，一、哈希表是什么？查找的过程为给定值依次和关键字集合中各个关键字进行比较，
查找的效率取决于和给定值进行比较的关键字个数。用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其
差别仅在于：关键字和给定值进行比较的顺序不同。只有一个办法：预先知道所查关键字在表中的位置对于频繁使用的
查找表，希望ASL=0。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为000~999
的顺序表表示之。例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999
(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。因此在一般
情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这
个函数f(key)为哈希函数。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}
例如：对于如下9个关键字设哈希函数f(key)=?(Ord(第一个字母)-Ord(''A'')+1)/2?
ChenZhaoQianSunLiWuHanYeDei问题:若添加关键字Zhou,怎么办？能否找到另
一个哈希函数？01234567
8910111213
1)哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小
不超出允许范围即可；从这个例子可见：2)由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：ke
y1?key2，而f(key1)=f(key2)。3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当
的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函
数之外；还需要找到一种“处理冲突”的方法。哈希表的定义：根据设定的哈希函数H(key)和所选中的处理冲突的方法，
将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所
得的查找表称之为“哈希表”。二、构造哈希函数的方法对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其
进行数字化处理。1.直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法哈希函数
为关键字的线性函数H(key)=key或者H(key)=a?key+b1.直接定址
法地址01…51年份
19491950…2000人数…
………关键字是年份，散列函数取关键字的线性函数：
H(key)=key+(-1949)例如：有一个解放后出生人口调查表
，每个记录包含年份、人数等数据项【注意】由于直接定址法所得地址集合和关键字大小相同，因此，关键字不会产生冲突，但实际应用中能够
使用这种散列函数的情况很少。此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。2.数字分析法
假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布
均匀的若干位或它们的组合作为地址。例有80个记录，关键码为8位十进制数，假设表长为l00，则可取两位十进制数(00～99)组
成散列地址，取其中的哪两位?813465328137224281
3874228130136781322817
8133896781368537814193
55…..…..????????分析：?只取8?只取1
?只取3、4?只取2、7、5????数字分布近乎随机所以：取????任意
两位或两位与另两位的叠加作哈希地址以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”
的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法此方法适合于:
关键字中的每一位都有某些数字重复出现频度很高的现象。第页第七章查找顺序表、有序表、索引顺序表的定义、查找及算法。
散列表的定义及构造法。散列表冲突的处理方法。何谓查找表？查找表是由同一类型的数据元素(或记录)构成的集合。
由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的操作:1）查询某个“特定的”数
据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元
素。仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或
者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类:是数据元素（或记录）中某个数据项的值
，用以标识（识别）一个数据元素（或记录）。关键字若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此
关键字能识别若干记录，则称之谓“次关键字”。根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。
查找若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否
则称“查找不成功”。查找结果给出“空记录”或“空指针”。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查
找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。
如何进行查找？查找的方法取决于查找表的结构。7.1静态查找表7.2动态查找树表7.3哈希表7.1静
态查找表以顺序表或线性链表表示静态查找表一、顺序查找表数据元素类型的定义为:typedefstruct
{keytypekey;//关键字域……//其它属性域}s
qlist;SqlistR[n+1];顺序查找【基本思想】:用给定的值与表中各个记录的关键字值逐个
进行比较，若找到相等的则查找成功，否则查找不成功，给出找不到的提示信息。RiRi60ik=64k=60i64
i01234567
8910115131921
37566475808892找6464监视哨iii
i本例比较次数：5【顺序表的查找过程】：假设给定值k=64,要求R[i]=k,问:i=?从最后一个元素
开始按照顺序依次往下查找比较次数：查找第n个元素：1 (最好情况)查找第n-1个元素：2 ……….查找第1
个元素：n (最怀情况)查找第i个元素：n+1-i查找失败：n+1在等概率查
找的情况下，顺序表查找的平均查找长度为：对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)
P2+…+2Pn-1+Pn若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的
记录直接移至表尾的位置上。在不等概率查找的情况下，ASLss在Pn≥Pn-1≥···≥P2≥P1时取极小值优
点：算法简单且适用面广。它对表的结构无任何要求，无论记录是否按关键字有序均可应用，而且上述所有讨论对线性链表也同样适用。缺点
:平均查找长度较大，特别是当n很大时，查找效率低。二、有序查找表若以有序表表示静态查找表，则查找过程可以基于“折
半”进行。Rn例如:key=64的查找过程如下：lowhighmidlowmid
highmidlow指示查找区间的下界high指示查找区间的上界mid=(low+h
igh)/2intbinarysearch(sglistR[],keytypek){intlow,mid
,high;low=1;high=n;while(low<=high)
{mid=(low+high)/2;if(k==R[mid].key)
returnmid;elseif(khigh=mid-1;else
low=mid+1;}return0;}intSearch(sqlistR[],k
eytypek,intlow,inthigh){if(low>high)return0;mid=(l
ow+high)/2;if(key==R[mid].key)returnmid;∥找到待查元素else
if(key>R[mid].key)∥继续在后半区间查找returnSearch(R,key,mid+1,
high);else∥继续在前半区间查找returnSea
rch(R,key,low,mid-1);}midlowhigh1234
56789101151
319213756647580889
2找2112345678
9101151319213756
6475808892lowhighmid123
4567891011
51319213756647580
8892lowhighmid查找的数据在表中：找到1234
5678910115
131921375664758088
92lowhighmid找70123456
78910115131921
37566475808892lowhighmid1234567891011513192137566475808892lowhighmid查找的数据不在表中：1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighlow>high查找失败1185210741936判定树：1234567891011513192137566475808892二分查找过程可用二叉树来描述,我们把当前查找区间的中间位置上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树,由此得到的二叉树,称为描述二分查找的判定树或比较树。先看一个具体的情况，假设：n=11分析折半查找的平均查找长度6391425781011判定树12233334444第页 |
|
