数据结构查找技术静态查找表.ppt

若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。 在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1 时取极小值 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。 二、有序查找表 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。 折半查找 使用条件： 线性表中的记录必须按关键码有序； 必须采用顺序存储。 基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。 ST.elem ST.length 例如: key=64 的查找过程如下： low high mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2 int BinSearch1(int r[ ], int n, int k) { //数组r[1] ~ r[n]存放查找集合 low = 1; high = n; while (low = high) { mid = (low + high) / 2; if (k r[mid]) high = mid - 1; else if (k r[mid]) low = mid + 1; else return mid; } return 0; } 折半查找——非递归算法 int BinSearch1(int r[ ], int n, int k) { //数组r[1] ~ r[n]存放查找集合 low = 1; high = n; while (low = high) { mid = (low + high) / 2; if (k r[mid]) high = mid - 1; else if (k r[mid]) low = mid + 1; else return mid; } return 0; } 8.2 线性表的查找技术 折半查找——非递归算法 折半查找判定树 判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。 先看一个具体的情况，假设：n=11 分析折半查找的平均查找长度 6 3 9 1 4 2 5 7 8 10 11 判定树 1 2 2 3 3 3 3 4 4 4 4 具有n个结点的折半查找判定树的深度为 查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。 查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。 。 ? ? 1 log 2 + n 折半查找性能分析 三、索引顺序表的查找 以索引顺序表表示静态查找表，则查找函数可用分块查找来实现。 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。 索引顺序表的查找过程： 1）由索引确定记录所在区间； 2）在顺序表的某个区间内进行查找。 注意：索引可以根据查找表的特点来构造。 可见， 索引顺序查找的过程也是一个 “缩小区间”的查找过程。 分块查找方法描述 将n个数据元素“按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须“按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，依次类推，直至m块。 分块查找操作步骤 step1 先选取各块中的最大关键字构成一个索引表； step2 查找分两个部分：先对索引表进行二分查找或 顺序查找，以确定待查记录在哪一块中； 然后，