软考软件设计师专题讲义九：数据结构相关算法

　　3.2查找算法

　　查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点。

　　按查找的条件分类：

　　u 有按结点的关键码查找;

　　u 关键码以外的其他数据项查找;

　　u 其他数据项的组合查找;

　　按查找数据在内存或外存：分内存查找和外存查找。

　　按查找目的：

　　u 查找如果只是为了确定指定条件的结点存在与否，成为静态查找;

　　u 查找是为确定结点的插入位置或为了删除找到的结点，称为动态查找。

　　这里简单介绍几种常见的查找方法。

　　u 顺序存储线性表的查找

　　这是最常见的查找方式。结点集合按线性表组织，采用顺序存储方式，结点只含关键码，并且是整数。如果线性表无序，则采用顺序查找，即从线性表的一端开始逐一查找。而如果线性表有序，则可以使用顺序查找、二分法查找或插值查找。

　　u 分块查找

　　分块查找的过程分两步，先用二分法在索引表中查索引项，确定要查的结点在哪一块。然后，再在相应块内顺序查找。

　　u 链接存储线性表的查找

　　对于链接存储线性表的查找只能从链表的首结点开始顺序查找。同样对于无序的链表和有序的链表查找方法不同。

　　动态查找表的不同表示方法：

　　二叉排序树(二叉查找树)：或者是一棵空树，或者是具有下列性质的一棵树：

　　u 若左子树不空，则左子树上的所有节点的值都小于根节点的值;

　　u 若右子树不空，则右子树上的所有节点的值都大于根节点的值;

　　u 它的左右子树也分别是二叉排序树;

　　二叉排序树的查找分析：在随机的情况下，其平均查找长度为1+4logn;

　　平衡二叉树：或者是棵空树，或者是具有下列性质的二叉树：

　　u 它的左子树和右子树都是平衡二叉树;

　　u 左子树和右子树的深度之差不会超过1;

　　平衡二叉树的查找分析：在查找过程中和给定值进行比较的关键字个数不超过树的深度，，因此其平均查找的时间复杂度是O(logn);

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总