(BST)-举例存储结构.ppt

* Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算 对象：表、文件等。其中每个结点（记录）由多个数据项构成，假设每个结点有1个能唯一标识该结点的key。 定义：给定1个值K，在含有n个结点的表中找出关键字等于K的结点，若找到（查找成功），则返回该结点信息或它在表中的位置；否则（查找失败），返回相关指示信息。 分类： 查找过程中是否修改表？动态查找、静态查找 查找过程是否均在内存中进行？内部查找、外部查找 * §9.1 基本概念 效率：与存储结构、文件状态（有序、无序）有关 平均查找长度(ASL)，即平均的比较次数，作为衡量查找效率的标准： Pi：查找第i个结点的概率 Ci：查找第i个结点的比较次数 设Pi＝1/n, 1≤i≤n 约定：typedef int KeyType; * § 9.2 线性表的查找 对象：用线性表作为表的组织形式。 分类：静态查找、内部查找 方式：顺序查找、二分查找、分块查找 ＃define n 100// §9.2.1 顺序查找 基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的结点的Key与给定值K进行比较，若当前扫描到结点Key＝K，则查找成功返回；若扫描完整个表后，仍未找到，则查找失败。 适用范围：顺序表、链表 算法： * §9.2.1 顺序查找 typedef struct{ KeyType key; InfoType otherinfo; //应用相关 }NodeType, SeqList[n+1]; //0号单元作为哨兵 int SeqSearch( SeqList R, KeyType K) { //在R[1..n]中查找，成功时返回结点位置，失败时返回0 int n; R[0].key=K; //设置哨兵 for ( i=n; R[i].key != K; i-- ); //从后往前找 return i; //若i为0，则失败 } * §9.2.1 顺序查找 哨兵的作用 for中省略了下标越界i=1判定,节约了约一半时间 时间分析 成功：ASLss=(n+1)/2，key的平均比较次数约为表长的一半 失败：n+1次比较 优缺点 优点：简单，对存储结构、Key之间的关系均无特殊要求 缺点：效率低，当n较大时不宜用 * § 9.2.2 二分（折半）查找 适用范围：顺序表、有序 基本思想（分治法） （1）设R[low..high] 是当前查找区间，首先确定该区间的中点 位置：mid= (low+high)/2 //整除 （2）将待查的K值与R[mid]比较， ① K＝R[mid].key：查找成功，返回位置mid ② K＜R[mid].key：则左子表R[low..mid-1]是新的查找区间 ③ K＞R[mid],key：则右子表R[mid+1..high]是新的查找区间 初始的查找区间是R[1..n]，每次查找比较K和中间点元素，若查找成功则返回；否则当前查找区间缩小一半，直至当前查找区间为空时查找失败。 * § 9.2.2 二分（折半）查找 算法： int BinSearch( SeqList R, KeyType K ) { int mid, low=1, high=n; while ( low high ) { //当前查找区间R[low..high]非空 mid= (low+high)/2； //整除 if ( R[mid].key==K ）return mid; //成功返回位置mid if ( K＜R[mid].key ) //两个子问题求解其中的一个 high=mid-1; //在左区间中查找 else low=mid+1；//在右区间中查找 } // endwhile return 0; //当前查找区间为空时失败 } * 查找过程 判定(比较)树：分析查找