勤思考研数据结构讲义查找.docVIP

查找 有关概念 查找表，静态查找表（只进行“查找”），动态查找表（可“查找”，“插入”，“删除”）。 关键字，平均查找长度 pi第i个关键字出现的概率，ci比较的关键字的个数。 静态查找表，顺序查找表，折半查找表，静态树表，次优查找树，索引顺序表。 动态查找表，二叉排序树，平衡二叉树（AVL树），B-树，B+树，键树，哈希表。 顺序查找 思路 按顺序逐个比较，直到找到或找不到。 算法 程序，要灵活应用。 例如：在数组a的前n个元素中查找x int Search ( int a[], int n, int x ) { for ( i=n-1; i=0; i-- ) if ( a[i]==x ) return i; return -1; // -1表示找不到 } 编程技巧：所有执行路径都要有正确的返回值，不要忘记最后那个return语句。 应试技巧：题目要求不明确时，按照方便的方法做，用适当的注释说明。 分析 顺序查找特点：思路简单(逐个比较)，适用面广(对查找表没有特殊要求)。 平均查找长度 一般在等概率情况下，查找成功时，平均查找长度 思路：假设对每个元素进行1次查找，共进行n次查找，计算出进行比较的关键字的个数，然后除以查找次数n，就求得平均查找长度。 例：10个元素的表等概率情况下查找成功时的平均查找长度 判定树 判定树是一种描述查找中比较过程的直观形式，每个关键字所在层次就是其查找长度，有利于分析查找过程。顺序查找的判定树是一棵深度为n的单分支的树。课本上顺序查找从an开始，当然也可以从a1开始。 时间复杂度 从平均查找长度看顺序查找的时间复杂度是O(n)。 折半查找 思路 待查找的表必须是有序的，先从中间开始比较，比较一次至少抛弃一半元素，逐渐缩小范围，直到查找成功或失败。 算法 要熟练掌握该算法。设a[]升序有序，有以下算法： int BinarySearch ( DataType a[], int n, DataType x ) { low = 0; high = n-1; while ( low = high ) { mid = ( low + high )/2; // 折半 if ( a[mid]==x ) return mid; // 找到 else if ( xa[mid] ) // x位于低半区 [low..mid-1] high = mid – 1; else // x位于高半区 [mid+1..high] low = mid + 1; } return -1; // -1表示未找到 } 或者有递归版本： int BinarySearch ( DataType a[], int low, int high, DataType x ) { if ( lowhigh ) return -1; // 查找失败 mid = (low+high)/2; // 折半 if ( a[mid]==x ) return mid; // 找到 else if ( xa[mid] ) return BinarySearch (a, low, mid-1, x); else return BinarySearch (a, mid+1, high, x); } 另外，程序可有多种写法。 例：a[]递减有序，折半查找，请填空。 int bs ( T a[], int n, T x ) { i = n-1; j = 0; while (____a____) { m = ____b____; if (____c____) return m; // succeeded else if (____d____) i = ____e____; else ____f____; } return -1; // not found } 分析 特点：速度很快，要求查找表是有序的，而且随机访问(以便计算折半的下标)。所以，链表不能进行折半查找(但可以采用二叉排序树等形式进行快速的查找)。 判定树 折半查找的判定树类似于完全二叉树，叶子结点所在层次之差最多为1，其深度为。 查找过程就是走了一条从根到该结点的路径。 如：表长n=10的有序表折半查找的判定树如下。 平均查找长度 结论：等概率查找成功时的平均查找长度 分析方法：对等概率情况，假设查找n次，且每个查找1次，共比较关键字c次，则平均c/n次。 例：表长为n = 10，平均查找长度如下。 时间复杂度 结论：O(logn)，根据