第九章查找-欢迎光临青岛科技大学信息科学技术学院

第九章查找本章中介绍下列主要内容：静态查找表及查找算法：顺序查找、折半查找动态查找表及查找算法：二叉排序树哈希表及查找算法第一节基本概念查找表用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。动态查找表若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。关键字是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是关键字值等于某个给定值，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。查找表的存储结构查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以平均比较次数来衡量查找算法的时间效率。第二节静态查找正如本章第一节所述：静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。1．顺序查找1.1顺序查找的基本思想顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。1.2顺序表的顺序查找下面是顺序表的类型定义：#defineMAX_NUM100//用于定义表的长度typedefstructelemtype{keytypekey;anytypeotherelem;}Se_List[MAX_NUM],Se_Elem;假设在查找表中，数据元素个数为n（nMAX_NUM），并分别存放在数组的下标变量a[1]~a[n]中。下面我们给出顺序查找的完整算法。intseq_search(Se_Lista，keytypek){//在顺序表中查找关键字值等于k的记录，//若查找成功，返回该记录的位置下标序号，否则返回0i=1;while(i=n&&a[i].key!=k)i++;if(i=n)retruni;elsereturn0;}改进算法：intseq_search2(Se_Lista，keytypek){//设置了监视哨的顺序表查找，查找关键字值等于指定值k的记录，//若查找成功，返回记录存放位置的下标值，否则返回0i=n;a[0].key=k;while(a[i].key!=k)i--;return(i);}1.3链表的顺序查找链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。链表的类型定义如下所示：typedefstructlinklist{keytypekey;//结点的关键字类型anytypeotherelem;//结点的其他成分structlinklist*next;//指向链表结点的指针}Link_Linklist,*Link;将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。对链表实现顺寻查找就是在有头结点的链式查找表中查找关键字值等于给定值的记录，若查找成功，返回指向相应结点的指针，否则返回空指针。Link_Linklist*link_search(Linkh,keytypek){//link为带头结点链表的头指针，查找关键字值等于k的记录，//查找成功，返回指向找到的结点的指针，查找失败返回空指针p=h-next;while((p!=NULL)&&(p-key!=k))p=p-next;returnp;}顺序查找算法简单，对表的结构无任何要求；但是执行效率较低，尤其当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）直到查找成功或查找范围空（lowhigh），即查找失败为止。（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。折半查找的完整算法如下：intbin_search(Se_Lista,keytypek){low=1;high=n;//置初始查找范围的低、高端指针while(low=high){mid=(low+high)/2;//计算中间项位置if(k==a[mid].key)break;//找到，结束循环elseif(ka[mid].key)high=mid-1;//给定值k小elselow=mid+1;//给定值k大}if(low=high)returnmid;//查找成功elsereturn0;//查找失败}第三节动态查找1．二叉排序树二叉排序树是一种常用的动态查找表，下面首先给出它的非递归形式。二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：（1）任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。（2）任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。二叉排序树也可以用递归的形式定义，即二叉排序树是一棵树，它或者为空，或者具有如下性质：（1）若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。（2）若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。（3）它的左右子树都是二叉排序树。例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的一棵二叉排序树如图7-4所示。如果对上述二叉排序树进行中根遍历可以得到一个关键字有序序列（12,15,35,46,57,62,65,68,79），这是二叉排序树的一个重要特征，也正是由此将其称为二叉排序树。2．二叉排序树的查找二叉排序树的结构定义中可看到：一棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值，所以在二叉排序树中查找一个关键字值为k的结点的基本思想是：用给定值k与根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。二叉排序树查找的过程描述如下：（1）若二叉树为空树，则查找失败，（2）将给定值k与根结点的关键字值比较，若相等，则查找成功，（3）若根结点的关键字值小于给定值k，则在左子树中继续搜索，（4）否则，在右子树中继续查找。假定二叉排序树的链式存储结构的类型定义如下：typedefstructlinklist{keytypekey;anytypeotherelem;structlinklist*lchild；structlinklist*rchild;}Bin_Sort_Tree_Linklist,*Bin_Sort_Tree；二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：Bin_Sort_Tree_Linklist*bt_search(Bin_Sort_Treebt,keytypek){//在根指针为bt的二叉排序树上查找一个关键字值为k的结点，//若查找成功返回指向该结点的指针，否则返回空指针if(bt=NULL)||(bt-key==k)returnbt;elseif(kbt-key)returnbt_search(bt-lchild,k);//在左子树中搜索elsereturnbt_search(bt-rchild,k);//在右子树中搜索}这个过程也可以用非递归算法实现，算法描述如下：Bin_Sort_Tree_Linklist*bt_search1(Bin_Sort_Treebt,keytypek){p=bt;//指针p指向根结点，搜索从根结点开始while(p!=NULL&&p-key!=k){if(kp-key)p=p-lchild;elsep=p-rchild;}return(p);}3．二叉排序树的插入在一棵二叉排序树中插入一个结点可以用一个递归的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。下面是二叉排序树插入操作的递归算法。voidbt_insert1(Bin_Sort_Tree*bt,Bin_Sort_Tree_Linklist*pn){//在以bt为根的二叉排序树上插入一个由指针pn指向的新的结点if(*bt=NULL)*bt=pn;elseif(*bt-keypn-key)bt_insert1(&(*bt-lchild),pn);elseif(*bt-keypn-key)bt_insert1(&(*bt-rchild),pn);}这个算法也可以用非递归的形式实现，如下所示：voidbt_insert2(Bin_Sort_Tree*bt,Bin_Sort_Tree_Linklist*pn){p=bt;while(p!=NULL&&p-key!=pn-key){q=p;if(p-keypn-key)p=p-lchild;elsep=p-rchild;}if(p=NULL){if(q-keypn-key)q-lchild=pn;elseq-rchild=pn-key;