9.2 静态查找表

01顺序表的查找

1、顺序查找（Sequential Search）的查找过程为：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录。

2、反之若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。

3、衡量一个算法的好坏的量度有3条：时间复杂度、空间复杂度和算法的其他性能。

4、对于查找算法来说，通常只需要一个或几个辅助空间。

5、为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。

6、顺序查找的缺点是平均查找长度较大，查找效率较低。然而，它有很大的优点是：算法简单且适应面广。

02有序表的查找

1、以有序表表示静态查找表时，Search函数可用折半查找来实现。

2、折半查找（Binary Search）的查找过程是：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

03静态树表的查找

1、称PH值取最小的二叉树为静态最优查找树（Static Optimal Search Tree）。

2、构造一棵二叉树，使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小，称这类二叉树为次优查找树。

04索引顺序表的查找

1、若以索引顺序表表示静态查找表，则Search函数可用分块查找来实现。

2、分块查找又称索引顺序查找，这是顺序查找的一种改进方法。

C语言 | 统计捐款人数及捐款​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/338773063