计算机软件基础课件：查找技术

查找技术BasicsofComputerSoftware答辩人：XXX目录顺序查找表1折半查找2二叉排序树3哈希查找45索引表的查找顺序查找表PART1查找的概念静态查找表动态查找表哈希表查找数据结构：查找01020304检索检索某个“特定的”数据元素的各种属性删除元素从查找表中删去某个数据元素查询查询某个“特定的”数据元素是否在查找表中插入元素在查找表中插入一个数据元素查找的概念查找表：由同一类型的数据元素(或记录)构成的集合。静态查找表动态查找表1仅作查询和检索操作的查找表2在查找过程中同时插入查找表中不存在的数据元素，或从查找表中删除已存在的某个数据元素查找表的分类：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。关键字查找的定义根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置。查找成功否则称“查找不成功”，查找结果：给出“空记录”或“空指针”查找失败查找方法评价查找速度ASL：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值对有n个记录的表：其中：pi为查找表中第i个元素的概率

ci为找到表中第i个元素所需比较次数平均查找长度ASL占用的存储空间算法的复杂程度

以顺序表表示静态查找表，则Search函数可用顺序查找来实现。其顺序存储结构定义如下：typedefstruct{ElemTypeelem[maxsize];

intlength;}SSTable;静态表的查找回顾：顺序表的查找intFind(SeqListL,ListDatax){inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)returni;elsereturn-1;}回顾：顺序表的按值查找查找第n个元素：

1查找第n-1个元素：2……….查找第1个元素：

n查找第i个元素：

n+1-i查找失败：

n+1增加监视哨的按值查找intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找关键字等于key的数据元素。ST.elem[0]=key;//设置“哨兵”

i=ST.length;//设置开始查询位置while（ST.elem[i]!=key）i--;//从后往前找returni;//找不到时，i为0}//Search_Seq增加监视哨的查找算法查找算法的平均查找长度：

对顺序表而言，Ci=n-i+1

又∵在等概率查找的情况下，∴顺序表查找的平均查找长度为：

顺序表查找的时间复杂度为：O(n)顺序查找性能分析在不等概率查找的情况下，ASLss在

Pn≥Pn-1≥……≥P2≥P1时取最小值。表中记录可按查找概率由小到大重新排列,以提高查找效率。 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。顺序查找性能分析有序表的查找PART2

顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。折半查找查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。有序表的查找lowhigmid123456789101111513192137566475808892找21例如:在有序表中查找key=21的查找过程mid=(low+high)/2hig=mid-1low=mid+1折半查找midlowhig123456789101111513192137566475808892找20例如:在表中查找key=20的查找过程mid=(low+high)/2hig=mid-1low=mid+1Low>hig,查找失败折半查找—查找失败的情况1.设表长为n，low、hig和mid分别指向待查元素所在区间的上界、下界和中点,k为给定的待查元素。

2.令mid=(low+hig)/2

让k与mid指向的记录比较

若k==r[mid]，查找成功

若k<r[mid]，则hig=mid-1

若k>r[mid]，则low=mid+1

3.重复2，直至low>hig时，查找失败。折半查找的算法描述开始low⩽higlow=上界hig=下界K=r[mid]K<r[mid]查找成功hig=mid-1low=mid+1结束查找失败hig=mid-1yesyesyesintSearch_Bin(SSTableST,KeyTypekval){low=1;hig=ST.length;//置区间初值

while(low<=hig){mid=(low+hig)/2;if（kval==ST.elem[mid])returnmid;//找到待查元素

elseif(kval<ST.elem[mid])hig=mid-1;//继续在前半区间进行查找

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

}return0;//顺序表中不存在待查元素}//Search_Bin折半查找算法6391425781011判定树：描述折半查找过程的二叉树。有n个结点的判定树的深度为

log2n+1折半查找在查找过程中进行的比较次数最多不超过log2n+1位置1234567891011元素513192137566475808892次数34234134234折半查找算法的时间复杂度为：O(log2n)折半查找的性能分析顺序表有序表表的特性无序有序存储结构顺序或链式顺序插删操作易于进行需移动元素ASL的值大小顺序表和有序表的比较二叉排序树PART3动态查找表的特点表结构本身是在查找过程中动态生成若表中存在其关键字等于给定值key的记录,则查找成功否则插入关键字等于key的记录动态查找表二叉排序树（二叉查找树）定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：(1)若它的左子树不空，则左子树上所有结点的值均小于根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于根结点的值;(3)它的左、右子树也都分别是二叉排序树。66先序序列：后序序列：中序序列：50302010252340358070908588102325203540307088859080501020232530354050708085889050308020901085403525238870二叉排序树这是一棵二叉排序树这不是一棵二叉排序树有序序列typedefstructBiTNode{//结点结构

TElemTypedata;structBiTNode*lchild,*rchild;//左右指针

}BiTNode,*BiTree;二叉排序树的存储结构以二叉链表形式存储查找85查找35查找2850308020901085403525238870二叉排序树的查找过程若二叉排序树为空，则查找不成功；否则

1）若给定值等于根结点的关键字，则查找成功；

2）若给定值小于根结点的关键字，则继续在左子树上进行查找；

3）若给定值大于根结点的关键字，则继续在右子树上进行查找。二叉排序树的查找算法描述{if(T==nil)returnnil;//查找不成功elseif(T->data==key)returnT;//查找成功elseif(key<T->data)returnSearchBST(T->lchild,key);//在左子树中查找elsereturnSearchBST(T->rchild,key);//在右子树中查找BiTreeSearchBST(BiTreeT,KeyTypekey)}//SearchBST二叉排序树的查找算法实现输入序列3，1，2，5，4→输入序列：1，2，3，4，5

→同一组数据，输入顺序不同，构造的二叉排序树不同，查找效率也不同2134535412其ASL=(1+2+3+4+5)/5=3其ASL=(1+2+3+2+3)/5=2.2输入顺序和构建的二叉排序树之间的关系哈希查找PART4哈希表的相关定义哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的插入哈希查找分析哈希表的查找哈希查找的概念基本思想存在的问题1哈希查找哈希查找又叫散列查找，利用哈希函数进行查找的过程2基本思想在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。3存在的问题但是存储地址和它的关键字之间不一定是一一对应关系，因此一般还要进行比较，只是尽量减少比较次数。哈希表的相关定义地址元素:357元素2:478元素4:1028元素3:1280元素1:元素1元素4元素2元素3HashFunction哈希函数图示哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。 可写成，addr(ai)=H(ki)其中：ai是表中的一个元素

addr(ai)是ai的存储地址

ki是ai的关键字哈希表的相关定义哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。地址元素:357元素2:478元素4:1028元素3:1280元素1:元素1元素4元素2元素3HashFunction哈希表哈希表的相关定义哈希函数的构造方法直接定址法数字分析法平方取中法折叠法除留余数法随机数法

以数据元素关键字key本身或它的线性函数作为它的哈希地址，即：

H(key)=k

或

H(key)=a×key+b

；

(其中a,b为常数)地址A1A2……A99A100年龄12……99100人数980800……495107

例如，有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图所示：哈希函数的构造方法：直接定址法取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。例：构造一个长为100的哈希表。现给出其中8个关键字进行分析，8个关键字如下：K1=61317602

K2=61326875

K3=62739628

K4=61343634K5=62706815

K6=62774638

K7=61381262

K8=61394220分析上述8个关键字可知，关键字从左到右的第1、2、3、6位取值比较集中，不宜作为哈希地址，剩余的第4、5、7、8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8个关键字的哈希地址分别为：哈希地址：2，75，28，34，15，38，62，20。哈希函数的构造方法：数字分析法关键字关键字的平方哈希函数值1234152275622721434592449924413217073424734321410329796297哈希函数的构造方法：平方取中法原理02方法01先取关键字的平方，然后根据可使用空间的大小，选取平方数中间几位为哈希地址。通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。哈希函数的构造方法：折叠法适用范围02方法01将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和。关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。当哈希表长为1000时，关键字key=110108331119891，允许的地址空间为三位十进制数，则采用三位折叠法有：

H(key)=

1

1

0

+1

0

8+

3

3

1+1

1

9+

8

9

1

=

5

5

9（舍去进位），例我们就可以用关键字做为随机种子数，那么针对相同的关键字就会产生相同的随机数，所以说计算机中的随机函数都是伪随机函数哈希函数的构造方法：随机数法主要原因02方法01选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时采用此法。计算机中的随机函数都是伪随机函数，只要设定的随机种子数相同，会产生相同的随机数的设定哈希函数为:H(key)=keyMODp(p≤m)其中：m为表长；p为不大于m的素数，或是不含20以下的质因子，称为模除留余数法不仅可以对关键字直接取模，也可以在折叠、平方取中等运算后取模。理论研究表明，除留余数法的模p取不大于表长且最接近表长m的素数时效果最好。哈希函数的构造方法：除留余数法给定一组关键字为:12,39,18,24,33,21若取p=9，则他们对应的哈希函数值将为:3,3,0,6,6,3可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能若取p=11,则他们对应的哈希函数值将为:1，6，7，2，0，10哈希函数的构造方法：除留余数法对p加以限制？例为产生冲突的地址寻找下一个哈希地址。哈希查找处理冲突的方法开放地址法再哈希法链地址法010203处理冲突的含义为产生冲突的地址H（key）

求得一个地址序列：H1,H2,…,Hs1≤s≤m-1Hi=（H（key）+di

）MODm其中：i=1,2,…,s H(key)为哈希函数；m为哈希表长；di为增量序列，有下列三种取法：处理冲突的方法：开放地址法对冲突的地址序列：Hi=(H(key)+di)MODm中的增量di的三种取法：线性探测再散列二次探测再散列随机探测再散列1di=c

i，c为常量，最简单的情况c=12di=12,-12,22,-22,…,3di

是一组伪随机数列：这个数列是随机产生的固定数处理冲突的方法：开放地址法某哈希表表长为11，哈希函数为H(key)=keyMOD11，分别填入关键字为17，60，29和38的4个记录，按三种处理冲突的方法，将它填入表中若采用：线性探测再散列，则H1=(5+1)MOD11=6有冲突H2=(5+2)MOD11=7有冲突H3=(5+3)MOD11=8不冲突若采用：二次探测再散列，则H1=(5+1²)MOD11=6有冲突H2=(5-1²)MOD11=4不冲突若采用：随机探测再散列设伪随机数序列为9，4，3……，则：H1=(5+9)MOD11=3不冲突012345678910383838（1）H(17)=17MOD11=6不冲突（2）H(60)=60MOD11=5不冲突（3）H(29)=29MOD11=7不冲突（4）H(38)=38MOD11=5有冲突601729处理冲突的方法：开放地址法举例例012345678910给定关键字集合构造哈希表{19，12，25，14，55，69，82，31}设定哈希函数为H(key)=keyMOD11，若采用线性探测再散列处理冲突1912145569821112

3

2112531

012345678910191214556982321543213212531

哈希查找表的建立和查找举例例查找成功时的比较次数查找失败时的比较次数

下面我们用除留余数法的线性探测再散列，对开放地址法的哈希查找做个小结：

哈希函数：H(key)=keyMODp

产生冲突时的地址序列：Hi=(H(key)+di)MODm，其中di=i；

元素个数：n则：计算ASL成功时，其每个元素的查找概率Pi=1/n，ci是比较次数计算ASL失败时，其每个哈希地址的查找概率Pi=1/p，ci是从哈希地址到下一个空位置的位置个数

另外，我们前面的例子中，模值p是等于表长m的，如果表长m大于模值p时，该如何处理？请同学们考虑开放地址法的哈希查找小结将所有哈希地址相同的记录都链接在同一链表中

关键字{19,01,23,14,55,68,11,82,36}哈希函数为H(key)=keyMOD70123456

1436

01

23

116819

82

55ASL成功=（1×6+2×2+3×1）/9=13/9ASL失败=（1×4+2×1+3×1）/7=10/7处理冲突的方法：链地址法例141276819230123456789101112

^^^^^^^79^55^84^20^10^11^处理冲突的方法：链