数据结构与算法分析：检索顺序查找

检索（查找）数据结构与算法1何谓查找表？查找表是由同一类型的数据元素(或记录)构成的集合。

由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。2对查找表经常进行的操作1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。3仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类4是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。关键字若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。5检索的方式精确匹配查询（exact-matchquery）模糊匹配查询（fuzzy-matchquery）范围查询（rangequery）6根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。

精确匹配查找若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。7检索的方法1.顺序表和线性表方法(lists,tables,arrays).2.根据关键码值直接访问方法(hashing)3.树索引方法.8

由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，

用另外一种结构来表示查找表。如何进行查找？查找的方法取决于查找表的结构。9查找方法目录基于顺序（线性）结构的查找基于有序顺序（线性）结构的查找10基于线性结构的检索11顺序检索问45是否已经保存？11132050323360459053477123456789101112位置值12ListFindFunction//ReturntrueiffKisinlistboolfind(List<int>&L,intK){

intit;for(L.setStart();L.getValue(it); L.next())if(K==it)returntrue;//Founditreturnfalse;//Notfound}Cost：对一个未排序的线性表进行顺序检索，在平均情况和最差情况下需要(n)13顺序检索（2）问保存的值中最大值是多少？11132050323360459053477123456789101112位置值11132050505060609090909014在数组中找最大值//Findlargestvalueint

largest(intarray[],intn){int

currlarge=0;//Largestvalueseenfor(inti=1;i<n;i++)//Foreachvalif(array[currlarge]<array[i])

currlarge=i;//Rememberposreturncurrlarge;//Returnlargest}15

定义：

查找算法的平均查找长度

(AverageSearchLength)

为确定记录在查找表中的位置，需和给定值

进行比较的关键字个数的期望值

其中:n

为表长，Pi

为查找表中第i个记录的概率，且，Ci为找到该记录时，曾和给定 值比较过的关键字的个数。分析顺序查找的时间性能16在等概率查找的情况下，

顺序表查找的平均查找长度为：对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn17

若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。在不等概率查找的情况下，ASLss

在

Pn≥Pn-1≥···≥P2≥P1时取极小值18顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。19基于有序顺序结构的检索20二分查找法问45是否已经保存？41113203233455053607790123456789101112位置值21BinarySearch//Returnpositionofelementinsorted//arrayofsizenwithvalueK.int

binary(intarray[],intn,intK){

intl=-1;

intr=n;//l,rarebeyondarrayboundswhile(l+1!=r){//Stopwhenl,rmeet

inti=(l+r)/2;//Checkmiddleif(K<array[i])r=i;//Lefthalfif(K==array[i])returni;//Founditif(K>array[i])l=i;//Righthalf}returnn;//Searchvaluenotinarray}22假设n=2h-1并且查找概率相等则

在n>50时，可得近似结果

一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。23字典检索检索一般不从辞典的中间开始。如果要查找的词以's'开头，查找者会估计到以's'开头的条目从词典的四分之三处开始。这样，他就会先翻到词典的四分之三处，然后根据所看到的内容决定接下来向哪里翻。也就是说，人们一般根据关键码值预期分布的知识“计算出”接下来向哪里翻。这种经过计算的二分法检索的形式称为词典检索(dictionarysearch)或者插值检索(interpolationsearch)24自组织线性表25根据访问频率排列列表根据估算的访问频率排列记录.执行顺序检索访问第一条记录的代价:1访问第二条记录的代价:2预期的检索代价:26例子(1)(1)每一条记录被访问的机会都相同.27例子(2)(2)指数频率28Zipf

分布应用:自然语言(如英语)中单词使用频率的分布.城市中的人口规模的分布,等.80/20规则:80%的访问都是对20%的记录进行的.当按照80/20规则分布时,29自组织线性表自组织线性表根据实际的记录访问模式在线性表中修改记录顺序.自组织线性表使用启发式规则决定如何重新排列线性表.这些启发式规则类似于管理缓冲池的规则.30启发式规则计数方法:为每条记录保存一个访问计数,而且一直按照这个顺序维护记录.(类似于缓冲池替代策略中的“最不频繁使用”LFU法.)移至前端法:如果找到一条记录就把它放到线性表的最前面,而把其他记录后退一个位置.转置:把找到的记录与它在线性表中的前一条记录交换位置.31例子假定有8条记录，其关键码值为A到H，而且最初以字母顺序排列 访问序列FDFGEGFAFGE（12次访问）线性表根据计数法组织最后结果FGDEABCH总代价是45次比较根据移至前端启发式规则最后结果EGFDABCH总代价是54次比较根据转置启发式规则最后结果ABFDGECH总代价是62次比较32文本压缩的例子应用:文本压缩.线性表是根据移至前端规则自组织的.如果单词前面已经出现，就传送这个单词在线性表中的位置.如果单词是第一次出现，就传送这个单词.ThecaronthelefthitthecarIleft.Thecaron3lefthit35I5.这种压缩方法的思想类似于Ziv-lempel编码算法.33集合的检索34集合的检索Fordensesets(smallrange,highpercentageofelementsinset).可以使用逻辑上的位操作.例子:为了寻找数字0到15之间奇素数集合,计算:0011010100010100&010101010101010135分块和索引（索引顺序查找）36分块查找的存储结构表分为b块，每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序”的。抽取各块中的最大关键字及其起始位置构成一个索引表,由于表R是分块有序的，所以索引表是一个递增有序表。

37分块查找的基本思想1）首先查找索引表

索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

2）然后在已确定的块中进行顺序查找

由于块内