计算机软件基础Thesoftwarebasicofcomputer主讲刘志强

1、计算机软件基础The software basic of computer计算机教学实验中心第6单元8/19/20221教学目标了解有关查找的基本概念查找的主要算法2教学要求通过本单元的学习，了解、掌握有关查找的：基本概念查找、平均查找长度主要查找算法顺序查找、折半查找、分块查找树表查找、哈希查找3本单元涉及的内容第3章3.1 什么是查找 3.2 顺序表查找3.3 树表查找3.4 哈希查找P90P1024一、基本概念查找查找表静态查找动态查找平均查找长度5查找查找 就是在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则，查找失败。查找表 是一组待查数据元素的集合。静态查找

2、是仅仅进行查询和检索操作，不改变查找表中数据元素间的逻辑关系的查找。动态查找 是除了进行查询和检索操作外，还对查找表进行插入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑关系。6平均查找长度平均查找长度 （ASL-Average Search Length） 在查找过程中，对每个结点记录中的关键字要进行反复比较，以确定其位置。因此，与关键字进行比较的平均次数，就成为平均查找长度。它是用来评价一个算法好坏的一个依据。对含有n个数据元素的查找表，查找成功时的平均查找长度为：ASL = Pi* Cini=1 Pi = 1i=1n 其中：Pi 为查找表中第i个数据元素的概率，且 Ci为查找第i

3、个数据元素时需比较的次数。 显然，Ci随查找过程及DS的不同而各异。7二、主要查找算法顺序查找折半查找分块查找树表查找哈希查找81、顺序查找算法思想： 最古老的算法。从第1个元素到最后1个元素，逐个进行比较。顺序查找是最简单、最普通的查找方法。查找表的存储结构：既适用于顺序存储结构也适用于链式存储结构 9算法描述查找操作步骤：step1 从第1个元素开始查找；step2 用待查关键字值与各结点（记录）的关键字值逐个进行比较；若找到相等的结点，则查找成功；否则，查找失败。10顺序查找算法框图i=0seq_search(A，n，key)A 待查表n 元素个数key 要找的值in&Ai!=key?Y

4、N查找key的循环显示“查找失败”返回开始i+Ai=key?YN显示“查找成功”11顺序查找算法3-1 seq_search(item , n , key ) int *item ,n , key ; int i=0 ; while ( i n & itemi != key ) i+; /* 查找key的循环 */ if (itemi= = key ) printf(“查找成功 !n”); return (i); else printf(“查找失败 !n”); return (-1); 示例12改进顺序查找算法框图i=0 ； An=keys_search_a(A，n，key)Ai!=key?Y

5、N查找key的循环显示“查找失败”返回开始i+i n?YN显示“查找成功”设置哨兵13顺序查找算法3-2（改进算法） seq_search_adv(item , n , key ) int *item ,n , key ; int i=0 ; itemn=key ; /* 设置哨兵 */ while ( itemi!= key ) i+; /* 查找key */ if ( i0) printf(“loc=%d,key=%dn”,loc,key); 示例15算法讨论平均查找长度ASL在等概率的情况下平均查找长度ASL在等概率的情况下i=1n12n+1ni=1nASL = Pi*Ci = (n-i

6、+1) =优点:对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可）无要求；当序列中的记录“基本有序”或N值较小时，是较好的算法；缺点：ASL较长讨论：能否减少比较次数，以提高效率。nASL 2例如，二分法等162、折半查找算法思想： 将有序数列的中点设置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。 即通过一次比较，将查找区间缩小一半。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，二分查找的先决条件是查找表中的数据元素必须有序。17算法描述算法步骤：step1 首先确定整个查找区间的中间位置， mid = （ left

7、 + right ）/ 2step2 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。Step3 对确定的缩小区域再按二分公式，重复上述步骤；最后，得到结果： 要么，查找成功， 要么，查找失败。存储结构用一维数组存放。18折半查找算法举例对给定数列（有序） 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找关键字值为30的数据元素。 第1次： 3，5，11，17，21，23，28，30，32，50 mid1= （1+10）/2 = 5 第2次： 23，28，30，32，50 m

8、id2 = （6+10） /2 = 8leftrightmidleftrightmid19折半查找算法3-3 bin_search ( item , n ,key ) int *item, n, key; int left ,right , mid; left=0; right = n-1; while ( left right ) mid = ( left + right )/2 ; /* 计算中点位置 */ if ( key itemmid) left = mid + 1; /* 待查区间在右部 */ else printf ( “ Successful searchn”); return

9、 mid ; /* 查找成功 */ printf( “ Search failure n”); return -1; /* 查找失败 */ 20折半查找算法3-3主程序 #define “stdio.h” int num; main( ) int res, key ; int s10=1,3,5,7,9,11,13，15，17，19，21，23; res=b_search(s,12,7); if(res0) printf(res=%d , num=%dn,res+1,num); else printf(“search failuren”); 示例21算法讨论优点: ASL log2n;即每经过

10、一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。缺点：因要求有序，所以对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不大便利。考虑：能否一次比较抛弃更多的部分（即一次比较，使查找范围缩得更小），以达到提高效率的目的；？ 把两种方法（顺序查找和二分查找）结合起来，即取顺序查找简单和二分查找高效之所长，来达到提高效率的目的？223、分块查找分块查找又称索引顺序查找，这是顺序查找的一种改进方法。方法描述：将n个数据元素“按块有序”划分为m块（m n）。每一块中的结点不必有序，但块与块之间必须“按块有序”；即第1快中任一元素的关键字都必须小于第2块中

11、任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，。每个块中元素不一定是有序的。23分块查找算法描述step1 先选取各块中的最大关键字构成一个索引表；step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找。24分块查找举例有数列如下： 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47 按“块有序”分三块:(22,12,13,9,8),(33,42,44,38,24), (48,6,58,74,47)。选取每块中最大的关键字组成索引表22,44,74,查找关键字值为60的元素。

12、用二分法，确定在索引表中的位置为 mid=2，key值60与a2比较，60a2,取第3个块;在第3块中用顺序法查找,比较两次,就可以找出60的元素来。4422742212139833424438244860587447List1List2List325索引表结构定义#include stdio.htypedef struct int key; /* 块最大值 */ int link; /* 指向块入口地址 */ index;26分块查找逻辑框图i_s_search(ls,s,m,key,l)ls 索引表S 待查表M 块数key 要找的值l 块长度i=0ilsi.key?YN确定块的循环j=ls

13、i.link返回开始i+i m?YN显示“查找失败”块入口地址块内查找循环key!=sj且j在范围内?j+Y key=sj?N查找失败查找成功返回YN27index_seq_search.c子函数index_seq_search(index ls,int s,int m,int key,int l) int i,j; i=0; while(ilsi.key) i+; /* 确定在哪块查找 */ if(i=m) printf(“ Searching failuren); return(-1); else /* 否则，查找成功处理 */28分块查找子函数（续） j=lsi.link; /* 块入口

14、地址 */ while (key !=sj & (j-lsi.link)l) j+; if(key=sj&(j-lsi.link)l)/* 查找成功*/ printf(Successful searchn LOC(s%2d)=%dn,j,sj); return(j); else /* 查找失败 */ printf(Searching failuren); return(-1); /* 结束 */29分块查找主函数main() index ls5= 14,0,34,5 ,66,10,85,15,100,20 ; int a=8,4,3,2,14, 34,20,17,28,29 ,58,61,59

15、,66,48, 81,80,79,83,69,89,100,96,86,87; int i,j=0,key; for(i=0;ileft = 0;r-right = 0;r-info = info ;非根结点infoinfo?Yt=r-leftt=r-rightN调用本函数root?返回YNr-left=0r-right=0root-left=r或root-right=r37 查询二叉排序树算法框图开始Search_btree(root，key) root 根指针 key 要找的值!rootY显示“空树”返回Nroot-info!=key循环keyinfo?root=root-leftroot

16、=root-rightroot=0?NY查找成功,显示返回显示“失败”root!=0?循环结束?NY38 打印算法框图开始print_btree(root，l ) root 根指针 l 起始点距离r=0?YN调用自身打印左子打印当前结点值调用自身打印右子返回39 主程序Btree.C#include “stdio.h” struct tree char info; struct tree *left,*right; main ( ) char *s,*c,key=; struct tree *create_btree(),*search_btree(),*root=0; do printf(“

17、Enter a letter:”); gets(s); if (!root) root=create_btree(root,root,*s); else create_btrr(root,root,*s); while (*s) ;40 主程序Btree.C(续） print_btree(root,0); key=1; while ( key) printf(“Enter a key to find:”); scanf(“%s”,&c); key=search_btree(root,c); printf(“press to continuen”); /* Btree.C 结束 */ 41生成二

18、叉排序树程序 struct tree create_btree(root,r,info) struct tree *root,*r; char info; if (r = = 0 ) r=malloc(sizeof(struct tree); if ( r = = 0) printf(“Out of memoryn”); exit(0); r-left= 0; r-right=0; r-info=info; if (root) if(infoinfo) root - left=r; else root-right=r; else r-right=0; r-left = 0; return r;

19、 /* if = = 0 接下页 */42生成二叉排序树程序（续） if (info info) create_btree(r,r-left,info); if(info=r-info) create_btree(r,r-right,info); /* create_btree(root,r,info) */43打印二叉排序树程序print_btree(r,l)struct tree *r;int l; int i; if (r = = 0) return ; print_tree(r-left,l+1); for(i=0;iinfo); print_btree(r-right,l+1); 4

20、4 struct tree *search_btree(root,key) struct tree *root; char key; if (!root) printf(“Emptu btreen”);return root; while(root-info!=key) /* 查找key 的循环 */ if(keyinfo) root=root-left; /* 沿左路查找 */ else root=root-right; /* 沿右路查找 */ if(root= =0) /* 到叶结点也没找到 */ printf(“Search Failuren”); break ; if (root !=

21、0) /* 查找成功 */ printf(“Successful searchn key=%cn”,root-info); return root ;查询二叉排序树程序示例45程序输入输入： 输出： h b d d p e r h b p e r 46 举例对数列10，18，3，4，9，13，25，生成二叉排序树如右；查找关键字值25。25比较根结点值10，走右路，再与18进行比较，走右路，最后与25进行比较，相等，查找成功。比较了3次。若查找35，则与10、18、25 分别进行比较后仍没找到相等 元素，查找失败，也比较了三次。1039418132547算法讨论二叉排序树查找的 ASL log

22、2n。若其平衡特性较好的话，ASL与折半查找相同。二叉排序树是动态生成的，其特性随插入结点的先后次序的不同而改变，为防止其蜕化为单枝树，要进行平衡化处理。二叉排序树因采用链表结构，需要辅助存储空间。上述方法都是建立比较基础上的，还有其它类型的方法吗？485、哈希（hash）查找哈希查找也称为散列查找。它不同于前面介绍的几种查找方法。上述方法都是把查找建立在比较的基础上，而哈希查找则是通过计算存储地址的方法进行查找的。计算是计算机的特点之一，因此，建立在计算基础上的哈希查找是一种快速查找方法。49哈希查找的基本概念哈希表 由哈希函数的值组成的表。哈希查找是建立在哈希表的基础上，它是线性表的一种重

23、要存储方式和检索方法。在哈希表中可以实现对数据元素的快速检索。哈希函数 哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为： Addr = H（key）建立哈希函数的原则均匀性 H（key）的值均匀分布在哈希表中；简单 以提高地址计算的速度。 50哈希函数常用的构造方法数字分析法平方取中法折叠法除留余数法（求模取余法）直接定址法51数字分析法当关键字的位数比存储区地址码位数多时，可合理选择关键字的某几位组成的哈希地址。选取的原则： 尽量避免计算出的地址有冲突。举例： 学校的电话号码是7位十进制数，学校的程

24、控交换机是3000门。但经分析不难得出： 0XXX 266 8XXX 9XXX 前3位是相同的，第4位分别为“0、8、9”，这样一来，正好可以表示3000个不同的电话号码。 H（KEY）= Right（telenum，4）52平方取中法取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不知道关键字的全部情况，取其中的哪几位也不一定合适，在这种情况下，取一个数平方后的中间几位数作哈希地址。取的位数由表长决定。例如，3288，平方后是“”，取后4位为哈希地址，即“0944”。53折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部

25、分的叠加和（舍去进位）作为哈希地址。关键字位数很多，且每一位上数字分布大致均匀时，可采用折叠法。举例：某资料室藏书近万册。采用国际标准图书编号（ISBN），每个编号10位十进制数字。可用折叠法构造一个4位数的哈希函数。 例如： 书号为： 0 - 4 4 2 - 2 0 5 8 6 - 4 5 8 6 4 4 2 2 0 H（key）= 0088 0 4+）1 0 0 8 854除留余数法（求模取余法）取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。 H（key） = key MOD p 这是一种最简单，也是最常用的构造哈希函数的方法。举例，32834872 ，哈希表长为4位十进制

26、数。 P值可取小于9999的数，例如，取5000； H（KEY）= 32834872 MOD 5000 = 4872由经验得知： 通常选p为小于哈希表长的最大素数。55直接定址法取关键字或关键字的某个线性函数值为哈希地址，即： H（key） = key H（key） = a * key + b （a，b为常数）例如 ： 在1100岁的人口统计表中，年龄作为关键字，哈希函数取关键字本身。再如 ： 解放后出生人口统计表中，年份作为关键字，哈希函数取为： H（key）= key +（ -1948）地址年份人数 01 02 42194919501990. 4319913000350025002300.

27、56选择哈希函数的标准哈希函数计算所需要的时间关键字的长度哈希表的长度关键字的分布情况记录的查找频率57冲突及冲突处理在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址的现象称为冲突。即关键字K1 K2， 但哈希函数值 H（K1）= H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。处理冲突是建立哈希表过程中不可缺少的一部分。处理冲突有两种方法：开放地址法链地址法58处理冲突 开放地址法当发生地址冲突后，求解下一个地址用 Hi =( H（key）+di） MOD m i=1,2,k(k m-1) 其中: H(key)为哈希函数

28、,m为哈希表长度,di为增量序列。增量序列的不同取法，又构成不同的开放地址法。 线性探测再散列 di=1,2,m-1 二次探测再散列 di=12 , -12, 22, -22, ,+k2, -k2(k m/2)59处理冲突 链地址法当发生地址冲突后,将所有函数值相同的记录连成一个单链表。60哈希查找操作步骤用给定的哈希函数构造哈希表根据选择的冲突处理方法解决地址冲突在哈希表的基础上执行哈希查找61建立哈希表建立哈希表操作步骤：step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。step2 根据选择的冲突

29、处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。 62举例对给定数列 22,41,53,46,30,13,1,67 ,建立哈希表。表长取9,即08。哈希函数设定为: H(key) = key MOD 8 ,用线性探测解决冲突 Hi=(H(key)+di) MOD m ,di=1,2,m-1。取22，计算H（22）=6，该地址空，可用；取41，计算H（41）=1，该地址空，可用； 0 1 2 3 4 5 6 7 82222 0 1 2 3 4 5 6 7 841比较次数： 1 163举例（续一）取53，计算 H（53）= 5，该地址空，可用；取46，计算 H（46）= 6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（6+1）MOD 8 = 7， 该地址空，可用；2241 0 1 2 3 4 5 6 7 853224153460 1 2 3 4 5 6 7 8 比较次数： 1 1 1 比较次数： 1 1 1 264举例（续二）取30，计算 H（30）= 6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（6+1）MOD 8 = 7， 该地址冲突，再用线性探测法计算下