资源描述：
《软件技术基础：查找算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途2.7查找２.7.1查找的基本概念查找的定义：给定一个值K，在含有ｎ个记录的文件中进行搜索，寻找一个关键字值等于K的记录,如找到则输出该记录;否则输出查找不成功信息。2．7．2线性查找线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始,逐个比较记录的关键字，直到和给定的K值相等,则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。如图2.68和图2.６9２.7.3对分查找又称为跳跃式查找,假设记录是按关键字递增有序排列的，对分查找的基本思想是：先找到“中间记录”,比较其关键字与给定值Ｋ相等,则查找成功;如果关键字小于给定值Ｋ则说明
2、被查找记录必在前半区间中;反之则在后半区间中。这样把搜索区间缩小了一半，继续进行查找。在算法中，设置一个下界指示器ｌoｗ和一个上界指示器high,它们分别指向待查文件搜索区间的头、尾。由low和hiｇh的值可以计算出“中间记录”位置，由mid表示。设顺序表r［1:n]的关键字项为r[i]．kｅy(１≤i≤n）将K值ｒ[ｍid］．ｋｅｙ比较:若r[mid]．key=K 查找成功 若r[mid］.ｋeｙ>K 令high=miｄ-1，继续查找 若r［ｍid]．keｙ<Ｋ 令low=mｉd+1，继续查找若loｗ＞hiｇh 查找不成功假设记录的关键字为（５,1３,1７，42,４6,55,７０
3、,94），现分别用K为5５和１2进行查找，查找过程如图2．7０所示,其中（ａ)为K=55,查找成功；(ｂ)为K=12,查找失败。个人收集整理勿做商业用途对分查找算法如下：BＩNSＥRRCH(r,n，Ｋ）1.loｗ←1;ｈiｇh←n／/上下界指示器赋初值//2.while (low＜ｈiｇh）ｄo３.mid←（lｏw+ｈiｇh)diｖ2 ／／ div为整除/／4.cａsｅ5.Ｋ=r[ｍiｄ］.ｋｅy:{查找成功;return}6.K＞r［mid］.ｋey:low←mid+１7.K＜r[ｍid].key: high←miｄ-18.end(caｓe)9.eｎd（while)10.retｕｒn ２.7
4、.4分块查找分块查找又称索引顺序查找,它要求文件中的记录关键字“分块有序”个人收集整理勿做商业用途,即文件可按关键字分为若干块,且前一块中最大的关键字小于后一块中最小的关键字，而每一块内的关键字则不一定有序。基本思想为：先将各块中的最大关键字构成一个索引表,由于文件是分块有序的因此索引表是递增有序的。查找过程分两步进行，第一步先对索引表进行对分或顺序查找,以确定记录在哪一块;第二步在所在块中进行顺序查找。如图２.72所示２．7.5二叉排序树查找BＳＴＳEＡRＣH（Ｋ,t)//K为查找给定值，t为根结点指针/／１.p←t／/p为查找过程中进行扫描的指针//2.ｗhile(p<>ｎil） do3.
5、ｃａsｅ４.K=ｄata（ｐ):{查找成功；retｕrn}5.K＜daｔa(p)：{ｑ←p;ｐ←Lcｈｉld(p)} //继续向左搜索//6.Ｋ>data(p）:{q←p;p←Rｃhild(p)} //继续向右搜索/／7.ｅｎｄ（case）８.end(ｗhile)9.GET（ｓ); dａta(ｓ)←K；Lchilｄ（ｓ)←ｎil;Rｃhｉld(s)←nil;／／查找不成功，生成一个新结点s,插入到二叉排序中／/１0.casｅ11.t＝nil：p←s;//插入结点为根结点//１2.K＜data(ｑ):L ｃhild(q)←s13．K>data(q): R ｃhilｄ(q)←s14．ｅnd（cas
6、e)15.ｒeturn２.7.４哈希表技术及其查找个人收集整理勿做商业用途1.哈希表哈希查找的基本思想是：通过对给定值作某种运算,直接求得关键字等于给定值的记录在文件中的位置。这就要求在建立文件时，对记录的关键字和她的存储位置之间建立一个确定的对应关系。设关键字ｋｅy与存储位置见的对应关系为H(key),若用一维数组来存放文件,则H(key)即为数组的下标。称函数H为哈希（hash)函数,H(ｋey)为哈希地址,这个一维数组称为哈希表。例如以学生姓名为关键字的记录集合｛Ｗａng,Li,Ｚhaｏ, Ｓhen,Ｇaｏ,Ｆunｇ,Bai,Cｈang, Rｅn,Ｍa}，若采用关键字中第一个字母表中的序
7、号作为哈希函数，则可以构成一个哈希表如图2.74所示2.构造哈希函数的集中方法(1)数字分析法将不均匀的数字删除，然后根据存储空间的大小来决定数字的数目。例如有7个学生的学号为5４2４２ 2２４1542 8１36785４２２2８１7１54２ ３8 9671５4２5415７75４2885３765421９3552个人收集整理勿做商业用途第1,2,3位的数值太不均匀，删去；第8位中数值7出现次数太多,删
