第10章 查找10.1 查找的基本概念本章小结10.2 线性表的查找10.3 树表的查找10.4 哈希表查找10.1 查找的基本概念被查找的对象是由一组记录组成的表或文件，而每个记录则由若干个数据项组成，并假设每个记录都有一个能惟一标识该记录的关键字在这种条件下，查找的定义是：给定一个值k，在含有n个记录的表中找出关键字等于k的记录若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息 采用何种查找方法?(1) 使用哪种数据结构来表示“表”，即表中记 录是按何种方式组织的2) 表中关键字的次序是对无序集合查找还 是对有序集合查找?若在查找的同时对表做修改运算(如插入和删 除)，则相应的表称之为动态查找表，否则称之为静态查找表 由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准平均查找长度ASL(Average Search Length)定义为：其中，n是查找表中记录的个数pi是查找第i个记录的概率，一般地，均认为每个记录的查找概率相 等，即pi=1/n(1≤i≤n)，ci是找到第i个记录所需进行的比较次数。
10.2 线性表的查找在表的组织方式中，线性表是最简单的一种三种性表上进行查找的方法：(1) 顺序查找(2) 二分查找(3) 分块查找因为不考虑在查找的同时对表做修改，故上述三种查找操作都是在静态查找表上实现的查找与数据的存储结构有关，线性表有顺序和链式两种存储结构本节只介绍以顺序表作为存储结构时实现的顺序查找算法定义被查找的顺序表类型定义如下：#define MAXL typedef struct {KeyType key; /*KeyType为关键字的数据类型*/InfoType data; /*其他数据*/} NodeType;typedef NodeType SeqList[MAXL]; /*顺序表类型*/ 10.2.1 顺序查找顺序查找是一种最简单的查找方法基本思路：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的记录，则查找失败例如，在关键字序列为{3，9，1，5，8，10，6，7，2，4}的线性表查找关键字为6的元素 顺序查找过程如下：开始: 3 9 1 5 8 10 6 7 2 4第1次比较: 3 9 1 5 8 10 6 7 2 4i=0第2次比较: 3 9 1 5 8 10 6 7 2 4i=1第3次比较: 3 9 1 5 8 10 6 7 2 4i=2第4次比较: 3 9 1 5 8 10 6 7 2 4i=3第5次比较: 3 9 1 5 8 10 6 7 2 4i=4第6次比较: 3 9 1 5 8 10 6 7 2 4i=5第7次比较: 3 9 1 5 8 10 6 7 2 4i=6查找成功，返回序号6顺序查找的算法如下(在顺序表R[0n-1]中查找关 键字为k的记录，成功时返回找到的记录位置，失败时 返回-1)：int SeqSearch(SeqList R，int n，KeyType k){ int i=0;while (i=n) return -1;else return i;}从顺序查找过程可以看到(不考虑越界比较ik) /*继续在R[lowmid-1]中查找*/high=mid-1;elselow=mid+1; /*继续在R[mid+1high]中查找*/}return -1;}二分查找过程可用二叉树来描述，我们把当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树，由此得到的二叉树，称为描述二分查找的判定树或比较树。
R[010]的二分查线的判定树(n=11) 5280369-∞～-112～345～678～9100～11～23～44～56～77～89～1010～∞===lchild，k);/*在左子树中递归查找*/elsereturn SearchBST(bt->rchild，k); /*在右子树中递归查找*/}50308020908540358832例如:二叉排序树查找关键字== 50 ,505035 ,503040355090 ,50809095 ,2. 二叉排序树的插入和生成在二叉排序树中插入一个新记录，要保证插入后仍满足BST性质其插入过程是：若二叉排序树T为空，则创建一个key域为k的结点，将它作为根结点；否则将k和根结点的关键字比较，若二者相等，则说明树中已有此关键字k，无须插入，直接返回0；若kkey，则将k插入根结点的左子树中，否则将它插入右子树中int InsertBST(BSTNode *p->key=k;p->lchild=p->rchild=NULL;return 1;}else if (k==p->key) /*存在相同关键字的结点，返回0*/return 0;else if (kkey) return InsertBST(p->lchild，k);/*插入到左子树中*/else return InsertBST(p->rchild，k); /*插入到右子树中*/}二叉排序树的生成，是从一个空树开始，每插入一个关键 字，就调用一次插入算法将它插入到当前已生成的二叉排序树 中。
从关键字数组A[0n-1]生成二叉排序树的算法CreatBST() 如下：BSTNode *CreatBST(KeyType A[]，int n) /*返回树根指针*/{ BSTNode *bt=NULL; /*初始时bt为空树*/int i=0;while (ikey) {f=f1; return(bt); } else if (kkey)return SearchBST1(bt->lchild, k, bt, f); /*在左子树中递归查找*/elsereturn SearchBST1(bt->rchild, k, bt, f); /*在右子树中递归查找*/ }显然，在二叉排序树上进行查找，若查找成功，则是从根记录出发走了一条从根到待查记录的路径；若查找不成功，则是从根记录出发走了一条从根到某个叶子的路径因此与二分查找类似，和关键字比较的次数不超过树的深度然而，二分查找法查找长度为n的有序表，其判定树是惟一的，而含有n个记录的二叉排序树却不惟一对于含有同样一组记录的表，由于记录插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同在二叉排序树上进行查找时的平均查找长度和二叉排序树的形态有关。
在最坏情况下，根据有序表生成的二叉排序树蜕化为一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查 找长度大约是log2n 根据关键字序列为{5,2,1,6,7,4,8,3,9} 和{1,2,3,4,5, 6,7, 8,9} 分别构造二叉排序树就平均时间性能而言，二叉排序树上的查找和二分查找差不多但就维护表的有序性而言，前者更有效，因为无须移动记录，只需修改指针即可完成对二叉排序树的插入和删除操作，且其平均的执行时间均为 O(log2n)例10.2 已知一组关键字为 {25，18，46，2，53，39， 32，4，74，67，60，11} 按表中的元素顺序依次插入 到一棵初始为空的二叉排序 树中，画出该二叉排序树， 并求在等概率的情况下查找 成功的平均查找长度解：生成的二叉排序树如右 图所示50 308020908540358832（1）被删除的结点是叶子结点 例如:被删关键字 = 2088其双亲结点中相应指针域的值改为“空”3. 二叉排序树的结点删除删除操作必须首先进行查找，假设在查找过程结束时，已 经保存了待删除结点及其双亲结点的地址。
指针变量p指向待删 除的结点，指针变量q指向待删除结点p的双亲结点删除过程 如下：(1) 若待删除的结点是叶子结点，直接删去该结点如图(a) 所示，直接删除结点9这是最简单的删除结点的情况 50 308020908540358832（2）被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为 “指向被删除结 点的左子树或右子树”被删关键字 = 40 80(2) 若待删除的结点只有左子树而无右子树根据二叉排序树的特点，可以直接将其左子树的根结点放在被删结点的位置如图(b)所示，*p作为*q的右子树根结点，要删除*p结点，只需将*p的左子树(其根结点为3)作为*q结点的右子树3) 若待删除的结点只有右子树而无左子树与(2)情况类似，可以直接将其右子树的根结点放在被删结点的位置如图(c)所示，*p作为*q的左子树根结点，要删除*p结点，只需将*p的右子树(其根结点为8)作为*q结点的右子树50308020908540358832（3）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再 删除该前驱结点被删结点前驱结点被删关键字 = 50(4) 若待删除的结点同时有左子树和右子树。
根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点或从其右子树 中选择关键字最小的结点放在被删去结点的位置上假如选取左 子树上关键字最大的结点，那么该结点一定是左子树的最右下结 点如图(d)所示，若要删除*p(其关键字为5)结点，找到其左子树 最右下结点4，它的双亲结点为2，用它代替*p结点，并将其原来 的左子树(其根结点为3)作为原来的双亲结点2的右子树删除二叉排序树结点的算法DeleteBST()如下(指针变量p指 向待删除的结点，指针变量q指向待删除结点*p的双亲结点)：void Delete1(BSTNode *p， BSTNode * if (r->rchild!=NULL)Delete1(p，r->rchild); /*递归找最右下结点*/ else /*找到了最右下结点*r*/ { p->key=r->key; /*将*r的关键字值赋给*p*/q=r; r=r->lchild; /*用*r的左子树的根结点取代*r的位置*/free(q); /*释放原*r的空间*/ }}void Delete(BSTNode *if (p->rchild==NULL) /**p结点没有右子树的情况*/{ q=p; p=p->lchild;/*其左子树的根结点放在被删结点的位置上*/free(q); }else if (p->lchild==NULL) /**p结点没有左子树*/{ q=p; p=p->rchild;/*将*p结点的右子树作为双亲结点的相应子树/free(q); }else Delete1(p，p->lchild);/**p结点既有左子树又有右子树的情况*/ }int DeleteBST(BSTNode */*空树删除失败*/else { if (kkey) return DeleteBST(bt->lchild，k);/*递归在左子树中删除为k的结点*/else if (k>bt->key) return DeleteBST(bt->rchild，k);/*递归在右子树中删除为k的结点*/else { Delete(bt); /*调用Delete(bt)函数删除*bt结点*/return 1;}}} p右子树为空树，则只需重接它的左子树。