软件应用技术基础：查找算法VIP免费

1/92.7查找2.7.1查找的基本概念查找的定义：给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录；否则输出查找不成功信息。2.7.2线性查找线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。如图2.68和图2.692.7.3对分查找又称为跳跃式查找，假设记录是按关键字递增有序排列的，对分查找的基本思想是：先找到“中间记录”，比较其关键字与给定值K相等，则查找成功；如果关键字小于给定值K则说明被查找记录必在前半区间中；反之则在后半区间中。这样把搜索区间缩小了一半，继续进行查找。在算法中，设置一个下界指示器low和一个上界指示器high，它们分别指向待查文件搜索区间的头、尾。由low和high的值可以计算出“中间记录”位置，由mid表示。设顺序表r[1:n]的关键字项为r[i].key(1≤i≤n)将K值r[mid].key比较：若r[mid].key=K2/9查找成功若r[mid].key＞K令high=mid-1，继续查找若r[mid].key＜K令low=mid+1，继续查找若low＞high查找不成功假设记录的关键字为（5，13，17，42，46，55，70，94），现分别用K为55和12进行查找，查找过程如图2.70所示，其中(a)为K=55，查找成功；(b)为K=12，查找失败。对分查找算法如下：BINSERRCH(r,n,K)1.low←1;high←n//上下界指示器赋初值//2.while(lowr[mid].key:low←mid+17.Knil)do3.case4.K=data(p):{查找成功;return}5.Kdata(p):{q←p;p←Rchild(p)}//继续向右搜索//7.end(case)8.end(while)9.GET(s);data(s)←K;Lchild(s)←nil;Rchild(s)←nil;//查找不成功,生成一个新结点s,插入到二叉排序中//4/910.case11.t=nil:p←s;//插入结点为根结点//12.Kdata(q):Rchild(q)←s14.end(case)15.return2.7.4哈希表技术及其查找1.哈希表哈希查找的基本思想是：通过对给定值作某种运算，直接求得关键字等于给定值的记录在文件中的位置。这就要求在建立文件时，对记录的关键字和她的存储位置之间建立一个确定的对应关系。设关键字key与存储位置见的对应关系为H(key)，若用一维数组来存放文件，则H(key)即为数组的下标。称函数H为哈希（hash）函数，H（key）为哈希地址，这个一维数组称为哈希表。例如以学生姓名为关键字的记录集合{Wang,Li,Zhao,Shen,Gao,Fung,Bai,Chang,Ren,Ma}，若采用关键字中第一个字母表中的序号作为哈希函数，则可以构成一个哈希表如图2.74所示5/92.构造哈希函数的集中方法(1)数字分析法将不均匀的数字删除，然后根据存储空间的大小来决定数字的数目。例如有7个学生的学号为542422241542813678542228171542389671542541577542885376542193552第1，2，3位的数值太不均匀，删去；第8位中数值7出现次数太多，删去；假设存储空间为1000，则可选取第4，6，7位作为起存储地址，分别为422，836，281，396，515，853，135。(2)平方取中法如果一组关键字在每一位上对某些数字的重复频率都很高，用数字分析法很难得到均匀的哈希函数。平方取中法首先求关键字的平方值，通过平方扩大差别，然后再选取其中几位作为哈希地址。例如一组关键字（0100，1100，1200，1160，2060...