第七章+查找-数据结构教程（C语言版）(王欣欣)

第七章查找表7.2静态查找表7.3哈希表7.1基本概念和术语何谓查找表？

查找表是由同一类型的数据元素(或记录)构成的集合。

“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。7.1基本概念和术语对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；与查询不同，检索已知数据元素及它的属性。3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。

查找表的四种操作都在查询基础上完成。作查询和检索操作的查找表；静态查找表若在查找过程中同时插入查找表中不存在的数据元素,或从查找表中删除已存在的某个数据元素,则称此类表为动态查找表.动态查找表查找表可分为两类:(1)基本不改变查找表的结构。(2)“查询”数据元素“不在查找表中”，将其插入；“查询”数据元素“在查找表中”，将其删除；改变查找表的结构。

在一个含有众多数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录)。

查找必须给出“特定的”词的确切含义，首先引入一个“关键字”的概念。

数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。关键字:

若此关键字可以唯一地标识一个数据元素（或记录），则称之谓“主关键字”。（对不同的记录，其主关键字均不同）如：银行中的帐号

若此关键字能识别若干记录，则称之谓“次关键字”。如：姓名

假设关键字是ElemType型，可进行比较。

查找:在查找表中确定一个关键字等于给定的数据元素或（记录）。

若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。

由于查找表本身是一种松散的集合结构，数据元素之间不存在明显的组织规律，因此不便于查找。如：修自行车时，从杂物盒中找镙钉。为了提高查找的效率，需要在查找表松散的集合元素之间人为地附加某种确定的关系，以便按某种规则进行查找，即

用另外一种数据结构来表示查找表。即：将杂物盒中的镙钉分类。如何进行查找？查找的方法取决于查找表的结构。衡量一个算法好坏的量度有三条：

时间复杂度(衡量算法执行的时间量级)

空间复杂度(衡量算法的数据结构所占存储以及大量的附加存储)

算法的其它性能查找操作的性能分析:查找算法中的基本操作是“将记录的关键字和给定值进行比较”，因此，通常以“平均查找长度”作为衡量查找算法的好坏。不再采用时间复杂度作依据。

查找算法的平均查找长度ASL

(AverageSearchLength)

为确定记录在表中的位置，需和给定值进行比较的关键字次数的期望值称为查找算法在查找成功时的平均查找长度。查找操作的时间性能分析对于含有n个数据元素的表,查找成功时的平均查找长度为

:nASL=ΣPiCi

i=1

其中:Pi——为查找第i个数据元素的概率,且Ci——为找到表中其关键字与给定值相等的第i个记录时,和给定值已进行过比较的关键字个数。在等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表每进行一次查找，我们需比较的数据元素的关键字的个数几乎是表长的一半。7.2静态查找表数据对象D：数据关系R：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。

数据元素同属一个集合。抽象数据类型静态查找表的定义为:ADTStaticSearchTable{

Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());基本操作P：next}ADTStaticSearchTable若ST中存在其关键字等于

key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

Search(ST,key);初始条件：操作结果：静态查找表ST存在，key为和查找表中元素的关键字类型相同的给定值；7.2.1顺序查找7.2.2折半表的查找7.2.3索引顺序表的查找顺序查找又称线性查找。其基本思想是：从静态查找表的一端开始，将给定记录的关键字与表中各记录的关键字逐一比较，若表中存在要查找的记录，则查找成功，并给出该记录在表中的位置；否则，查找失败，并给出失败信息。7.2顺序查找表ST.elemii例:在顺序查找表中查找一个key=64的给定值在下标变量为0处赋值给定值key，叫设置监视哨，所赋的给定值叫哨兵。从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,指针向前移，计数器i-1，直到某个记录的关键字和给定值比较相等为止,则查找成功,找到所查记录;iii64监视哨

i指针从表长开始，不相等时i-1,当i指针移到0位置时，就自然停住了，指针不会出界,因为在此处一定是相等的。在整个查找过程中不需检验i值是否大于0，这就是顺序表查找过程。监视哨ST.elemiikey=60iii60i静态查找表的顺序存储结构为算法7.1//----------静态查找表的顺序存储结构-----------#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量typedef

struct{

ElemType*elem; //存储空间基址

intlength; //当前线性表长度

int

listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;int

Search_Seq(SSTableST,

KeyTypekey){

//在顺序表ST中顺序查找其关键字等于

//key的数据元素。若找到，则函数值为

//该元素在表中的位置，否则为0。

ST.elem[0].key=key;//设置“哨兵”

for(i=ST.length；ST.elem[i].key!=key;--i);

//从后往前找，i的初值是表长，终值元素是//赋的值，在不相等的情况下i-1。

returni;//找不到时，i为0；找到时，i大于0。}//Search_Seqintmain() //主程序用来检验顺序查找算法7.1{

SqList

st;

inti;

st.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

for(i=1;i<=6;i++)st.elem[i]=i;st.length=6;//构造静态查找表st=(1,2,3,4,5,6)

i=Search(st,5);

//调用顺序查找方法，在查找表st中查找5是否存在

printf(“位置为：%d\n”,i);i=Search(st,8); //调用顺序查找方法，在查找表st中查找8是否存在

printf(“位置为：%d\n”,i); //不存在位置为0}性能分析：假设顺序表中每个记录的查找概率相同，即pi = 1/n，查找表中第i个记录顺序查找的平均查找需进行n-i+1次比较，即ci = n-i+1。当查找成功时顺序查找的平均查找长度为

ASL ==(n - i + 1) = (n+1)/2

当查找不成功时，关键字的比较次数是n+1次。顺序查找的基本操作是关键字的比较，因此，查找表的长度就是查找算法的时间复杂度，即为O(n)。

上述顺序查找表的查找算法简单，但平均查找长度较大，不太适用于表长较大的查找表。7.2.2折半查找表

以有序表（按关键字的大小从小到大或从大到小排列的表）表示静态查找表，查找过程可以基于“折半”进行。ST.elemST.length折半查找的算法：例如:key=64

的查找过程如下lowhighmidlow

mid

high

mid指针low

指示查找区间的下界;指针high

指示查找区间的上界;指针mid=(low+high)/2intSearch_Bin(SSTableST,KeyTypekey){

low=1;high=ST.length;

//置区间初值

while(low<=high){mid=(low+high)/2;

if（key==ST.elem[mid].key)

returnmid;//找到待查元素

elseif(key<ST.elem[mid].key))

high=mid-1;

//继续在前半区间进行查找

else

low=mid+1;//继续在后半区间进行查找

}return0;//顺序表中不存在待查元素}//Search_Bin先看一个具体的情况，假设：n=11分析折半查找的平均查找长度122333344440513192137566475808892从上述查找过程可知：找到第⑥个元素仅需比较1次；找到第③和第⑨个元素需比较2次；找到第①、④、⑦和⑩个元素需比较3次；找到第②、⑤、⑧…需比较4次。这个查找过程可用二叉树来描述,通常称这个描述查找过程的二叉树为判定树，从判定树上可见，(1)查找到给定值21的过程恰好是走了一条从根到结点④的路径，(2)与给定值21进行比较的关键字的个数为该路径上的结点数或结点④在判定树上的层次数。6391425781011判定树查找成功时折半查找的平均查找长度(ASL):假设n=2h-1并且查找概率相等则在n>50时，可得近似结果

折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构。（对线性链表无法有效地进行折半查找）7.2.3索引顺序表是顺序查找的一种改进方法,在建立顺序表的同时，建立一个索引。012345678910111213……1708211914313322254052617846……2104057810……例：索引顺序表=索引+顺序表顺序表索引一般情况下，索引表是一个有序表。例：表中含有18个记录，可分成三个子表(Rl，R2，…，R6)、(R7，R8，…，R12)、(R13，R14，…R18)，对每个子表(或称块)建立一个索引项

索引表按关键字有序，则表有序或分块有序。“分块有序”是第i个子表中所有记录的关键字均大于第i-1个子表中的最大关键字。索引表包括两项内容：关键字项：其值为该子表内的最大关键字指针项：指示该子表的第一个记录在表中位置137186482286745860484442338131222索引表最大关键字

起始地址17

1338244953920

假设给定值key=38，则先将key依次和索引表中各最大关键字进行比较，由于22<key<48，则关键字为38的记录若存在，必定在第二个子表中，由于索引表中的指针项指示第二个子表中的第一个记录是表中第7个记录，则自第7个记录起进行顺序查找，直到ST.elem[10].key=38为止。137186482286745860384842338131222索引表最大关键字起始地址分块查找过程需分两步进行：（1）确定待查记录所在的块(子表)；（2）在块中顺序查找。17

13137186482286745860384842338131222索引表最大关键字起始地址

索引表是有序的，子表不是有序的但是有限的。

每个子表中都有空格字符，可直接插入元素而不移动其它元素。索引顺序查找表由有序表和顺序表的简单合成17

13例如：在一个系中有多个班级，索引表中是班级名，子表中是每个班级中同学的名单，是有限的，当有插班的同学时，可直接将其姓名插入，索引表不变。索引顺序查找的平均查找长度为在索引中进行查找的平均查找长度和在“顺序表”中进行查找的平均查找长度之和。

7.3.1哈希表的基本概念7.3.2哈希函数的构造方法

7.3.3

理冲突的方法

7.3.4哈希表的查找7.3哈希表

以上两节讨论了查找表的查找的过程为给定值依次和关键字集合中各个关键字进行比较。7.3.1哈希表的基本概念共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系。

不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。前几节几种方法表示的查找表，其平均查找长度都不为零。

查找的效率取决于和给定值进行比较的关键字个数即平均查找长度ASL。对于频繁使用的查找表，希望平均查找长度ASL=0。只有一个办法：预先知道所查关键字在表中的位置。

即，要求：记录在表中位置和其关键字之间存在一种确定的关系。因此，需在关键字与记录在表中的存储位置之间建立一个函数关系。以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例如：对于如下9个关键字设哈希函数

f(key)=

(Ord(第一个字母))/2

ChenZhaoQianSunLiWuHanYeDei问题:

若添加关键字Zhou,怎么办？能否找到另一个哈希函数？261917

1)哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，

它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；从这个例子可见：

2)由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：

key1

key2，而

f(key1)=f(key2)。

3)

很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。

因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”

的方法。哈希表的定义：

根据设定的哈希函数H(key)

和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。对于哈希表，主要考虑两个问题，其一是如何构造哈希函数，其二是如何解决哈希冲突。对于如何构造哈希函数，应解决两个主要问题：(1)哈希函数是一个压缩映像函数，它具有较大的压缩性，不可避免地产生冲突。(2)哈希函数具有较好的散列性，尽可能均匀地把记录映射到各个存储地址上，尽量减少冲突的产生，从而提高查找效率。7.3.2构造哈希函数的方法

构造哈希函数时，一般都要对关键字进行计算，为了尽量避免产生相同的哈希函数值，应使关键字的所有组成成分都能起作用。对数字的关键字可有下列构造方法：

若是非数字关键字，则需先对其进行数字化处理。1.

直接定址法4.平方取中法2.除留余数法3.数字分析法哈希函数为关键字的线性函数

H(key)=key或者

H(key)=a

key+b1.

直接定址法此法仅适合于：地址集合的大小==关键字集合的大小2.除留余数法

设定哈希函数为:

H(key)=keyMODp

其中，

p≤m(表长)

对P的选择很重要。

给定一组关键字为：12,39,18,24,33,21，若取p=9,则他们对应的哈希函数值将为：

3,3,0,6,6,3例如：为什么要对p加以选择？

可见，若p中含质因子3，

则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。此方法仅适合于：

能哈希表中可能出现的关键字是事先知道的。3.

数字分析法

假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。例如，有80个记录，要构造的哈希表长度为100。为了不失一般性，取其中8个记录的关键字进行分析，8个关键字如下所示：1231034612560783114201282113151712850435222416512178187421600002…..…..

分析：8个关键字可知，关键字从左到右的第1、2、5位的取值比较集中，不宜作为哈希地址，剩余的第3、4、6、7、8位取值近乎随机，可选取其中的两位作为哈希地址。设选取第6和7位作为哈希地址，则8个关键码的哈希地址为34、78、12、51、43、65、87、02。4．平方取中法

平方取中法是指取关键字平方后的中间几位作为哈希地址。这是一种较常用的构造哈希函数的方法。但是，在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数与数的每一位都相关，所以，随机分布的关键字得到的，哈希地址也是随机的，取的位数由表长决定。实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。7.3.3处理冲突的方法

“处理冲突”

的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.开放定址法2.链表法

为产生冲突的地址H(key)寻找下一个哈希地址：

H=

H(key)MODm

Hi=(H(key)+di

)MODm

i=1,2,…,s1≤s≤m-11.开放定址法对增量di

有三种取法：1)线性探测再散列

di=c

i

最简单的情况c=12)平方探测再散列

di=12,-12,22,-22,…,3)随机探测再散列

di

是一组伪随机数列

或者

di=i×H2(key)

(又称双散列函数探测)例7.3已知9个记录的关键字为(12，22，25，38，24，47，29，16，36)，试构造哈希表存放这9个记录。哈希函数为H(key) = keymod12，哈希表的内存空间为12个存储单元。采用线性探测法处理冲突过程如下：

H(key) = keymod12 = 12mod12 = 0，不冲突，关键字12放入0号单元。

H(key) = keymod12 = 22mod12 = 10，不冲突，关键字22放入10号单元。

H(key) = keymod12 = 25mod12 = 1，不冲突，关键字25放入1号单元。

H(key) = keymod12 = 38mod12 = 2，不冲突，关键字38放入2号单元。

H(key) = keymod12 = 24mod12 = 0，冲突，按照处理冲突的方法求下一个哈希地址。

H1 = 0 + 1 = 1，1号单元有记录，冲突。

H2 = 0+2 = 2，冲突。

H3 = 0+3 = 3，不冲突，关键字24放入3号单元。

H(key) = keymod12 = 47mod12 = 11，不冲突，关键字47放入11号单元，

H(key) = keymod12 = 29mod12 = 5，不冲突，关键字29放入5号单元，

H(key) = keymod12 = 16mod12 = 4，不冲突，关键字16放入4号单元，

H(key) = keymod12 = 36mod12 = 0，冲突，按照处理冲突的方法求下一个哈希地址。

H1 = 0+1 = 1，1号单元有记录，冲突。

H2 = 0+2 = 2，冲突。

H3 = 0+3 = 3，冲突。

H4 = 0+4 = 4，冲突。

H5 = 0+5 = 5，H6 = 0+6 = 6，不冲突，关键字36放入6号单元。

最后建成的哈希表如书上表7.2所示

例表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中012345678910601729(1)H(38)=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+1²)MOD11=6冲突

H2=(5-1²)MOD11=4不冲突38(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：

H1=(5+9)MOD11=3不冲突38线性探测再散列：平方探测再散列：随机探测再散列：例如:

关键字集合

{19,01,23,14,55,68,11,82,36}设定哈希函数

H(key)=keyMOD11(表长=11)1901231455681901231468若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突118236551182360123456140136198223116855

ASL=(6×1+2×2+3)/9=13/9例如:同前例的关键字，哈希函数为H(key)=keyMOD7平均查找长度：2.链表法将所有哈希地址相同的记录都链接在同一链表中。

例7.5已知12个记录的关键字为(12,22,25,38,24,47,29,16,37,44,55,50)，试构造哈希表存放这12个记录，哈希函数H(key)=keymod12，用链表法处理冲突。

H(key)=keymod12=12mod12=0；

H(key)=keymod12=22mod12=10；

H(key)=keymod12=25mod12=1；