数据结构第9章查找研究.ppt

第九章 查找 　 * * 查找表（Search Table）是由一些具有相同可辨认特性的数据元素（或记录）构成的集合。 关键字（key）是数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。 主关键字唯一地标识一个元素， 次关键字识别若干元素 查找（searching）根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。 定义：查找过程中先后和给定值进行比较的关键字个数的期望值称作查找算法的平均查找长度(Average Search Length)。 查找表通常可分两类： 1.静态查找表 2.动态查找表 如何评价查找算法的时间效率？ 对查找表经常进行的操作有：　　（1）查询某个特定的数据元素是否在表中；　　（2）检索某个特定的数据元素的各种属性；　　（3）在查找表中插入一个数据元素；　　（4）从查找表中删除某个数据元素。 9.1 静态查找表 9.1.1 顺序表的查找 实现静态查找表的最简单的方法是以“顺序存储结构的线性表-顺序表”表示之 。 查找过程为：从第一个或最后一个数据元素起，逐个进行“比较”直至其中某个数据元素的关键字等于给定值为止。 缺点：其平均查找长度较大，特别是当表中记录数 n 很大时，查找效率较低。 优点：算法简单且适应面广，无论表中记录是否按关键字有序排列均可应用，而且，上述讨论对链式存储的线性表也同样适用。 9.1.2 有序表的查找 折半查找(Binary Search)又称二分查找 折半查找的过程为：给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间” 或 “后半个区间” 之后继续进行查找。 例如，在有序表(05,13,19,21,37,56,64,75,80,88,92)中查找关键字为21和85的数据元素。 算法 　　int Search_Bin ( SSTable ST, KeyType kval ) 　{　　// 在有序表ST中折半查找其关键字等于kval的数据元素，　　// 若找到，则函数值为该元素在表中的位置，否则为0。　　low = 1; high = ST.length; 　　　　　// 置区间初值　　while (low = high) {　　　mid = (low + high) / 2;　　　if ( kval == ST.elem[mid].key )　　　　return mid;　　　　　　　　　　 // 找到待查元素　　　else 　　　　if ( kval ST.elem[mid].key )　　　　　high = mid - 1; 　　　　　// 继续在前半区间内进行查找　　　　else low = mid + 1;　　　　// 继续在后半区间内进行查找　　} // while　　return 0; 　　　　　　　　　// 有序表中不存在待查元素　} // Search_Bin 9.1.3 索引顺序表的查找 线性表中的记录按关键字“分段有序” 称它为分块有序表)，同时，另建一个索引，由分块有序表和相应的索引构成一个索引顺序表， 索引表 13 7 1 86 48 22 53 86 49 74 58 60 48 24 38 44 42 33 20 9 8 13 12 22 最大关键字 起始地址 9.2动态查找表 9.2.1 动态查找表的类型定义 动态查找表的特点：在查找过程中尚需进行插入或删除的操作。因此，表示动态查找表的结构应不仅便于查找，还应便于插入和删除。 抽象数据类型动态查找表的定义参见教材P226-227 9.2.2 二叉查找树 一、二叉查找树的定义 二叉查找树或者是一棵空树；或者是具有如下特性的二叉树：　　（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值； 　　（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值； 　　（3）它的左、右子树也都分别是二叉查找树。 例如，下图所示是一棵二叉查找树 二叉链表作为二叉查找树的存储结构 typedef struct BiTNode {　　　　　// 结点结构 ElemType data;　　// 数据元素　struct BiTNode *lchild, *rchild; // 左右孩子指针　　} BiTNode, *BSTree; 例如，下图所示是不是一棵二叉查找树？ 　二、二叉查找树的查找算法 若二叉查找树为空，则查找不成功；否则　　1）若给定值等于根结点的关键字，则查