考研笔记-计算机之数据结构:集合结构-查找表(静态查找表)
- 2026-11-10 00:31:09
——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。
折半查找
基本思想：每次选择顺序存储的有序线性表的中间元素作为查找的待比较对象。
实现方法：①令low和high分别为查找区间的最低和最高索引，若
处的元素等于待查找元素，则查找成功，查找结束；否则执行②；②若
处的元素大于待查找元素，则令
，若
处的元素小于待查找元素，则令
，此时若
，则执行①，否则查找失败（此时
且high和low之间的位置是待查找元素应处的位置，因为每次low或high均是在
，即
的前提下进行的以下操作
或
），查找结束。
描述折半查找的判定树：描述折半查找的二叉树。判定树的叶子结点所在的层次之差至多为1（平衡二叉树），n个结点的判定树的深度和n个结点的完全二叉树的深度相同。n个记录的二叉判定树唯一（因为查找顺序是确定的，为折半查找）。描述折半查找的判定树的中序遍历序列按结点在查找表中的位序号有序。
静态最优查找树：使查找性能达到最佳的判定树，即其带权内路径长度之和PH值
取最小值的二叉树。其中n为二叉树上结点的个数（即有序表的长度）；
为第i个结点在二叉树上的层次数；结点的权
，其中
为结点的查找概率，c为某个常量（PH值和平均查找长度的比值，
）。
次优查找树：其带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小值。
次优查找树的构造方法
已知一个按关键字有序的记录序列
，其中
，每个记录相应的权值为
，则构造次优查找树的方法如下：
1）在序列
中取第i（l≤i≤h）个记录构造根结点ri，使得
取最小值（
）；
2）分别对子序列
和
，构造两棵次优查找树，并分别作为根结点ri的左子树和右子树。
3）由于在构造次优查找树的过程中，没有考察单个关键字的相应权值，则有可能出现被选为根的关键字的权值比与它相邻的关键字的权值小，此时应作适当的调整：选取临近的权值较大的关键字作次优查找树的根结点。
静态树表：用次优二叉树表示的静态查找表。
静态树表（次优查找树）的查找：类似折半查找。若次优查找树为空，则查找不成功，否则，首先将给定值key和其根结点的关键字相比，若相等，则查找成功该根结点的记录即为所求；否则将根据给定值key小于或大于根结点的关键字而分别在左子树或右子树中继续查找直至查找成功或查找不成功为止。
索引顺序表：包括表本身和由索引项组成的索引表。索引项包括两项，关键字项（其值为表内相应子表中的最大关键字）和指针项（指示相应子表的第一个记录在表中的位置），索引表各个索引项按关键字有序，则表分块有序，即索引表中后一索引项对应的子表中的所有记录的关键字均大于前一索引项对应的子表中的最大关键字，子表内各项无序。
文章合集：
点击下方公众号主页，关注以阅读更多文章
——可选择“【右上角···】→【在浏览器中打开】”进行横屏阅读。
