第7章查找

静听沙漏 2012-01-08

展开全文

第7章查找

本章中介绍下列主要内容：
　　 1.静态查找表及查找算法：顺序查找、折半查找
　　 2.动态查找表及查找算法：二叉排序树
　　 3.哈希表及查找算法

第一节基本概念

查找表：用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。
静态查找表：若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。
动态查找表：若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。
关键字：是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的账号是主关键字，而姓名是次关键字。
查找：在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是"关键字值等于某个给定值"，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。
查找表的存储结构：查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。
查找算法的时间效率：查找过程的主要操作是关键字的比较，所以通常以"平均比较次数"来衡量查找算法的时间效率。

第二节静态查找

正如本章第一节所述：静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。
1．顺序查找
1.1 顺序查找的基本思想
顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。
1.2 顺序表的顺序查找
下面是顺序表的类型定义：
#define MAX_NUM 100 //用于定义表的长度
typedef struct elemtype{
keytype key;
anytype otherelem;
}Se_List[MAX_NUM],Se_Elem;
假设在查找表中，数据元素个数为n（n<MAX_NUM），并分别存放在数组的下标变量a[1]~a[n]中。
下面我们给出顺序查找的完整算法。
int seq_search (Se_List a，keytype k)
{//在顺序表中查找关键字值等于k的记录，
//若查找成功，返回该记录的位置下标序号，否则返回0
i=1;
while (i<=n && a[i].key != k) i++;
if (i<=n) retrun i;
else return 0;
}
改进算法：
int seq_search2 (Se_List a，keytype k)
{ //设置了监视哨的顺序表查找，查找关键字值等于指定值k的记录，
//若查找成功，返回记录存放位置的下标值，否则返回0
i=n ;
a[0].key=k ;
while ( a[i].key != k) i--;
return ( i ) ;
}
1.3 链表的顺序查找
链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。
链表的类型定义如下所示：
typedef struct linklist {
keytype key; //结点的关键字类型
anytype otherelem; //结点的其他成分
struct linklist *next; //指向链表结点的指针
}Link_Linklist,*Link;
将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。
对链表实现顺寻查找就是在有头结点的链式查找表中查找关键字值等于给定值的记录，若查找成功，返回指向相应结点的指针，否则返回空指针。
Link_Linklist *link_search (Link h , keytype k)
{//link为带头结点链表的头指针，查找关键字值等于k的记录，
//查找成功，返回指向找到的结点的指针，查找失败返回空指针
p=h->next;
while ((p!=NULL) && (p->key!=k)) p=p->next;
return p;
}
顺序查找算法简单，对表的结构无任何要求；但是执行效率较低，尤其当n较大时，不宜采用这种查找方法。
2．折半查找
2.1 折半查找的基本思想
折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或隆序）排列，也就是说折半查找只适用于对有序顺序表进行查找。
折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。
2.2 折半查找过程示例

2.3 折半查找算法
假设查找表存放在数组a的a[1]~a[n]中，且升序，查找关键字值为k。
折半查找的主要步骤为：
（1）置初始查找范围：low=1，high=n;
（2）求查找范围中间项：mid=(low+high)/2
（3）将指定的关键字值k与中间项a[mid].key比较
若相等，查找成功，找到的数据元素为此时mid 指向的位置；
若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1;
若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1;
（4）重复步骤（2）、（3）直到查找成功或查找范围空（low>high），即查找失败为止。
（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。
折半查找的完整算法如下：
int bin_search (Se_List a, keytype k)
{
low=1; high=n; //置初始查找范围的低、高端指针
while (low<=high)
{ mid=(low+high)/2; //计算中间项位置
if (k==a[mid].key) break; //找到，结束循环
else if (k< a[mid].key) high=mid-1; //给定值k小
else low=mid+1; //给定值k大
}
if (low<=high) return mid ; //查找成功
else return 0 ; //查找失败
}

第三节动态查找

1．二叉排序树
二叉排序树是一种常用的动态查找表，下面首先给出它的非递归形式。
二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：
（1）任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。
（2）任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。
二叉排序树也可以用递归的形式定义，即二叉排序树是一棵树，它或者为空，或者具有如下性质：
（1）若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。
（2）若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。
（3）它的左右子树都是二叉排序树。
例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的一棵二叉排序树如下图所示。

如果对上述二叉排序树进行中根遍历可以得到一个关键字有序序列（12, 15, 35,46, 57,62,65,68,79），这是二叉排序树的一个重要特征，也正是由此将其称为"二叉排序树"。
2．二叉排序树的查找
二叉排序树的结构定义中可看到：一棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值，所以在二叉排序树中查找一个关键字值为k 的结点的基本思想是：用给定值k与根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。二叉排序树查找的过程描述如下：
（1）若二叉树为空树，则查找失败，
（2）将给定值k 与根结点的关键字值比较，若相等，则查找成功，
（3）若根结点的关键字值小于给定值k，则在左子树中继续搜索，
（4）否则，在右子树中继续查找。
假定二叉排序树的链式存储结构的类型定义如下：
typedef struct linklist {
keytype key;
anytype otherelem;
struct linklist *lchild；
struct linklist *rchild;
}Bin_Sort_Tree_Linklist,*Bin_Sort_Tree；
二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：
Bin_Sort_Tree_Linklist *bt_search(Bin_Sort_Tree bt , keytype k)
{ //在根指针为bt的二叉排序树上查找一个关键字值为k的结点，
//若查找成功返回指向该结点的指针，否则返回空指针
if ( bt = NULL ) || ( bt -> key == k ) return bt;
else if (k< bt -> key) return bt_search ( bt -> lchild , k ); //在左子树中搜索
else return bt_search ( bt -> rchild , k ); //在右子树中搜索
}
这个过程也可以用非递归算法实现，算法描述如下：
Bin_Sort_Tree_Linklist *bt_search1(Bin_Sort_Tree bt , keytype k)
{
p = bt; //指针p指向根结点，搜索从根结点开始
while ( p != NULL && p ->key != k )
{
if (k <p -> key ) p = p -> lchild;
else p = p -> rchild;
}
return ( p);
}
3．二叉排序树的插入
在一棵二叉排序树中插入一个结点可以用一个递归的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。
下面是二叉排序树插入操作的递归算法：
void bt_insert1(Bin_Sort_Tree *bt , Bin_Sort_Tree_Linklist *pn)
{ //在以bt为根的二叉排序树上插入一个由指针pn指向的新的结点
if ( *bt =NULL) *bt = pn ;
else if ( *bt -> key > pn->key ) bt_insert 1( &(*bt -> lchild) , pn ) ;
else if ( *bt -> key < pn -> key ) bt_insert1 ( &(*bt -> rchild) , pn) ;
}
这个算法也可以用非递归的形式实现，如下所示：
void bt_insert 2(Bin_Sort_Tree *bt , Bin_Sort_Tree_Linklist *pn)
{
p = bt;
while ( p != NULL && p -> key!= pn->key)
{ q = p;
if ( p ->key > pn->key ) p = p -> lchild;
else p = p -> rchild;
}
if ( p =NULL ) {
if ( q ->key > pn -> key ) q ->lchild = pn;
else q -> rchild =pn ->key;
}
}
利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树。
例如，由结点关键字序列（62, 15, 68, 46, 65, 12 , 57 , 79, 35）构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排序树中插入，在插入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过9次的查找和插入操作，建成由这9个结点组成的二叉排序树。
创建二叉排序树的算法如下：
Bin_Sort_Tree_Linklist *bt_bulid (Bin_Sort_Tree a , int n)
{ //在数组a的a[1]~a[n]单元中存放着将要构成二叉排序树的n个结点内容
bt = NULL ;
for ( i =1; i <= n;i++)
{
p = (Bin_Sort_Tree_Linklist *)malloc (sizeof (Bin_Sort_Tree_Linklist));
p ->key =a[i].key;
p -> otherelem= a[i].otherelem;;
p -> lchile = NULL;
p -> rchile = NULL;
bt_insert1( &bt , p);
}
return ( bt) ;
}
4. 二叉排序树的删除
下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的性质：
（1）若要删除的结点为叶子结点，可以直接进行删除。
（2）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。
（3）若要删除结点有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，与步骤⑵类似。
（4）若要删除结点的左右子树均非空，则首先找到要删除结点的右子树中关键字值最小的结点（即子树中最左结点），利用上面的方法将该结点从右子树中删除，并用它取代要删除结点的位置，这样处理的结果一定能够保证删除结点后二叉树的性质不变。

第四节哈希表

1．哈希表的概念
前面介绍的静态查找表和动态查找表的特点是：为了从查找表中找到关键字值等于某个值的记录，都要经过一系列的关键字比较，以确定待查记录的存储位置或查找失败，查找所需时间总是与比较次数有关。
如果将记录的存储位置与它的关键字之间建立一个确定的关系H，使每个关键字和一个唯一的存储位置对应，在查找时，只需要根据对应关系计算出给定的关键字值k对应的值H(k)，就可以得到记录的存储位置，这就是本节将要介绍的哈希表查找方法的基本思想。
哈希函数：我们将记录的关键字值与记录的存储位置对应起来的关系H称为哈希函数，H(k)的结果称为哈希地址。
哈希表：是根据哈希函数建立的表，其基本思想是：以记录的关键字值为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容。当对记录进行查找时，再根据给定的关键字值，用同一个哈希函数计算出给定关键字值对应的存储地址，随后进行访问。所以哈希表即是一种存储形式，又是一种查找方法，通常将这种查找方法称为哈希查找。
冲突：有时可能会出现不同的关键字值其哈希函数计算的哈希地址相同的情况，然而同一个存储位置不可能存储两个记录，我们将这种情况称为冲突，具有相同函数值的关键字值称为同义词。在实际应用中冲突是不可能完全避免的，人们通过实践总结出了多种减少冲突及解决冲突的方法。下面我们将简要地介绍一下。
2. 哈希函数的构造
建立哈希表，关键是构造哈希函数。其原则是尽可能地使任意一组关键字的哈希地址均匀地分布在整个地址空间中，即用任意关键字作为哈希函数的自变量其计算结果随机分布，以便减少冲突的发生可能性。
常用的哈希函数的构造方法有：
（1）直接定址法
取关键字或关键字的某个线性函数为哈希地址。即
H(key)=key 或 H(key)=a*key+b
其中a，b为常数，调整 a与b的值可以使哈希地址取值范围与存储空间范围一致。
（2）质数取余法
取关键字被某个不大于哈希表表长n的质数m整除后所得余数为哈希地址。即
H(key)=key % m (m<n，设其中n为哈希表长)。
质数取余法计算简单，适用范围大，但是整数m的选择很重要，如果选择不当，会产生较多同义词，使哈希表中有较多的冲突。
（3）平方取中法
取关键字平方后的中间几位为哈希地址。由于平方后的中间几位数与原关键字的每一位数字都相关，只要原关键字的分布是随机的，以平方后的中间几位数作为哈希地址一定也是随机分布。
（4）折叠法
把关键字折叠成位数相同的几部分，然后取这几部分的叠加作为哈希地址。在关键字位数较多，且每一位上数字的分布基本均匀时，采用折叠法，得到的哈希地址比较均匀。
3. 解决冲突的方法
常用的处理冲突的方法有：
（1）开放定址法
当发生冲突时，在冲突位置的前后附近寻找可以存放记录的空闲单元。用此法解决冲突，要产生一个探测序列，沿着此序列去寻找可以存放记录的空闲单元。最简单的探测序列产生方法是进行线性探测，即当发生冲突时，从发生冲突的存储位置的下一个存储位置开始依次顺序探测空闲单元。
（2）链地址法
将所有关键字是同义词的记录链接成一个线性链表，将其链头链接在由哈希函数确定的哈希地址所指示的存储单元中。
（3）再哈希法
当发生冲突时，用另一个哈希函数再计算另一个哈希地址，如果再发生冲突，再使用另一个哈希函数，直至不发生冲突为止。这种方法要求预先要设置一个哈希函数的序列。
（4）溢出区法除基本的存储区外（称为基本表），另外建立一个公共溢出区（称为溢出表），当发生冲突时，记录可以存入这个公共溢出区。
4. 哈希表查找及其分析
哈希表的查找过程与哈希表的构造过程基本一致，对于给定的关键字值k，按照建表时设定的哈希函数求得哈希地址；若哈希地址所指位置已有记录，并且其关键字值不等于给定值k, 则根据建表时设定的冲突处理方法求得同义词的下一地址，直到求得的哈希地址所指位置为空闲或其中记录的关键字值等于给定值k为止；如果求得的哈希地址对应的内存空间为空闲，则查找失败；如果求得的哈希地址对应的内存空间中的记录关键字值等于给定值k，则查找成功。
上述查找过程可以描述如下：
（1）计算出给定关键字值对应的哈希地址addr=H(k);
（2）while( (addr中不空)&&(addr 中关键字值!=k))
按冲突处理方法求得下一地址addr;
（3）如果 (addr 中为空)，则查找失败，返回失败信息；
（4）否则查找成功，并返回地址addr；
在处理冲突方法相同的哈希表中，其平均查找时间，还依赖于哈希表的装填因子，哈希表的装填因子为：