09第9章 查找

《09第9章 查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章查找基本概念静态查找表动态查找表哈希表基本概念查找表：由同一类型的数据元素（或记录）构成的集合。对查找表进行的操作有以下四种：查询某个特定的数据元素是否在查找表中。检索某个特定的数据元素的各种属性。在查找表中插入一个数据元素。从查找表中删除某个数据元素。静态查找表：对查找表只作前两种操作。动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。关键字：标志数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素。查找：根据给定的某个值，在查找表中确定是否存在一个数据元素其关键字等于给定值的记录或数据元素。平均查找长度ASL(Average

2、SearchLength)为：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值其中:n为表长Pi为查找表中第i个记录的概率Ci为找到该记录时，曾和给定比较过的关键字的个数。静态查找表顺序表的查找有序表的查找索引顺序表的查找顺序表的查找基本思想：从表的一端开始，顺序扫描线性表，依次用待查找的关键字值与线性表里各结点的关键字值逐个比较，若在表中找到了某个记录的关键字与待查找的关键字值相等，表明查找成功；如果找遍所有结点也没有找到与待查找的关键字值相等，则表明查找失败。01234567（a）初态40803060102025(b)K=80(returni=4)8040803060

3、10202501234567(c)K=90(returni=0)012345679040803060102025顺序查找的算法：intSearch_seq(SSTableST[],intn,intkey){inti=n;ST[0].key=key;while(ST[i].key!=key)i--;/*从表尾往前查*/returni;}监视哨使用了监视哨，在查找过程中，不用每一步都去判断是否查找结束。找到：返回元素在线性表中的存储位置；未找到：返回0。根据上述算法可知：查找成功时的平均查找次数为：ASL=(1+2+3+4+……+n)/n=(n+1)/2查找不成功时的比较次数为：n+1则顺序查

4、找的平均查找长度为：ASL==((n+1)/2+n+1)/2=(n+1)3/4顺序查找的优点：算法简单，无需排序，采用顺序和链式存储均可。缺点：平均查找长度较大。因此，当n较大时，不宜采用顺序查找。等概率查找的情况下折半查找基本思想：首先用要查找的关键字值与中间位置结点的关键字值相比较；比较结果如果相等，则查找完成；若不相等，再根据要查找的关键字值与该中间结点关键码值的大小来确定下一步查找在哪个子表中进行：如果待查关键字大于中间结点的关键字值，则应查找中间结点以后的子表，否则，查找中间结点以前的子表。ST.elemST.length例如:key=64的查找过程如下：lowhighmidlo

5、wmidhighmidlow指示查找区间的下界high指示查找区间的上界mid=(low+high)/2intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;if（EQ(key,ST.elem[mid].key))returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待

6、查元素}//Search_Bin折半查找判定树：折半查找过程可用二叉树来形象的描述，把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树，由此得到的二叉树，称为描述折半查找的判定树。实例：先看一个具体的情况，假设：n=11分析折半查找的平均查找长度6391425781011判定树12233334444优点:平均查找长度小缺点:要求表中元素按关键字排序。二分查找适用于那种一经建立就很少改动、而又经常需要查找的有序表，且限于线性存储结构。对于查找少而又需经常改动的线性表，可采用链表作存储结构。折半查找（二分法查找）分块查找基本思想：把线性表分成若干块，在每一

7、块中结点的存放是任意的，块与块之间必须排序；建立一个索引表，存放每块中最大的关键字值；查找时首先用要查找的关键字值在索引表中查找，确定应在哪一块中，然后再到相应的块中顺序查找。该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。索引表20538916111812852051362229538960726676块中的最大关