检索及基本算法.doc

一、线性表的检索1、 顺序检索顺序检索是一种最简单的基本检索方法。其基本思路为：从表的一端开始，用给定值逐个与表中各记录的关键字值比较。若找到某个关键字等于给定的记录，则检索成功，并给出该记录在表中的位置；若检索完整个表仍未找到关键字值等于给定值的记录，则检索失败，冰给出失败信息。顺序检索方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。在等概率的情况下顺序检索的平均检索长度为：ASL=(n+1)/22二分法检索二分法检索（Binary Search）,也称作折半检索。它要求检索表是用顺序存储结构表示，且数据元素的存放要按关键字值有序排列。二分法检索的基本思想是：在有序表中先取中间位置作为比较对象，若给定值与中间记录的关键字值相等，则检索成功；若给定值小于中间记录的关键字值，则在表的左半区查找；若给定值大于中间记录的关键字值，则在表的右半区查找。就这样经过一次的比较缩小一半的检索区间，在每一个检索区都是选取中间位置作为比较对象，不断地重复这样的检索过程直到检索成功，或者检索区间无记录时检索失败。二分法检索在检索成功时的平均检索长度维：，当n较大时，则可有如下近似结果：ASL=3黄金分割点检索 黄金分割点检索（Gold-partition Search），简称黄金分割点检索。它是里哦那个黄金分割数0.618把检索区间分为两个不等的区间。每次用给定值与黄金点上的记录的关键字比较，若相等检索成功，若给定值小于黄金点关键字值，继续在黄金点之前的区间检索；若给定值大于黄金点关键字值，继续在黄金点之后的区间检索。通过黄金点逐次缩小检索区间，直到检索成功，或区间已无记录检索失败时止。该算法的时间性能与二分法相比，在平均性能上优于二分法，但仍然是；在最坏情况下，每次比较之后都在较大的区间继续检索，比二分法差；在最坏的情况下，每次比较之后都在小区间继续检索，比二分法好。4.精算点检索所谓精算点检索（Precise Computing Search）,也称作插值检索。它是利用检索区间有序关键字值范围和给定值的大小比例关系估算出检索位置的一种检索方法。5.分块检索分块检索（Blocking Search），又称作索引检索，它是顺序检索的一种改进方法。其效率介于顺序检索和二分法检索之间。分块检索不要求检索表中所有记录关键值有序排列，但要求把检索表分成若干个块之后各块之间按关键字值大小有序。即分块检索要求检索表的特点是：块间有序，快内无序。所谓块间有序是指块间升序或块间降序。在块间升序时，每一块所有记录的关键字值均大于和该块相邻的前一块中最大的关键字值；在块间降序时，每一块中所有记录的关键字值均小于和该块相邻的前一块中最小的关键字值。若顺序检索确定所在的块，则分块检索的平均检索长度为：由此可知，ASL不仅与检索的长度n有关，而且和每一块中的记录个数s有关。二、树表的检索1.二叉检索树二叉检索树（Binary Search Tree），又称作二叉排序树（Binary Sort Tree）,它或者是一颗空树，或者是具有下列性质的二叉树:(1) 若左子树不空，则左子树上所有结点的值均小于根结点的值。(2) 若右子树不空，则右子树上所有结点的值均大于根结点的值。(3) 其左、右子树也都是二叉检索树。(4) 把检索表组织成一颗二叉检索树，其检索效率取决于树的形态。在最好的情况下，平均检索长度维log2n+1；在最差的情况下，平均检索长度为n+1;在一般情况下，平均检索长度为1+4log2n。2. B树和B+树B树是一种平衡的多路的检索树，是文件系统（包括大型数据库文件系统）中的一种重要的数据组织结构。三、哈希检索一种直接利用关键字值计算记录在检索表中的存储位置来进行检索的方法哈希(Hash)检索技术。哈希检索技术的初衷是组织理想状态的检索表。检索表的理想状态是：把记录的关键字值与记录在检索表中的存储位置建立起某种一对一的关系，这种一对一的关系可以用关于关键字的一个函数h(key)来表示，这样就可以不必进行关键字与给定值的比较，而是直接根据给定的关键字值来直接计算得到记录在检索表中的存储地址。在实际应用中，通常关键字的取值范围比哈希地址的取值范围要大得多，因而经过哈希函数h(key)变换后，可能会将不同的关键字值映射到同一个哈希地址上，称这种现象为地址冲突（Address Collision。一般情况下，地址冲突是不可避免的，只能通过选取合适的哈希函数尽可能减少这种冲突现象，而不可能做到完全避免这种冲突现象，所以哈希检索技术必须解决如下两个问题：（1） 如何选取一个计算简单且地址冲突尽可能少的哈希函数。（2） 在出现地址冲突时采用怎样的办法来消解冲突。常见的韩系函数构造方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、乘余取整法、随机数法。常用的地址冲突消解策略有：开放定址法；拉链法。一定义：哈希表是为了便于快速搜索而组织的键/值组合的集合。Hash Table是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。键/值对的集合。二优点：哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。三基本原理： 使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。六哈希表的不可避免冲突(collision)现象： 对不同的关键字可能得到同一个哈希地址 即key1key2，而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选