二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(2)

此外，还要考虑算法所需的附加存储空间以及算法本身的复杂程度等。为了讨论的方便，在本章中均假设结点是等长的，查找都是基于关键字的查找，且关键字都为正整数。以上假设是不失一般性的，因为，如果结点不等长，则可以讨论它的目录表；如果关键字不为正整数，则可以在关键字与正整数之间建立一一对应关系。9.2 线性表的查找在查找表的组织方式中，线性表是最简单的一种。本节主要介绍三种性表上进行查找的方法：顺序查找、折半查找和分块查找。9.2.1 顺序查找顺序查找 sequential search 是一种最基本、最简单的查找方法。其查找方法是：从表的一端开始，用给定的值与表中各结点的关键字逐个进行比较，直到或者找出相等的结点则查找成功；或者找遍所有结点都不相等则查找失败。顺序查找对线性表的结构本身没有特殊的要求，即表可以是顺序存储的，也可以是链接存储的；对表中的数据也没有排序要求。因此它具有很好的适应性，是一种经常采用的查找方法。存储结构描述和算法如下：const int MaxSize 100;typedef int keyType;typedef structkeyType key;infoType otherinfo;NodeType;NodeType R[MaxSize];keyType K;int n, i;在长度为n的线性表R[1‥n] 中查找关键字为K的元素，R[0]作为哨兵。

进入算法时，n个结点已存入表R[1‥n] 中，欲查找的给定值放在变量K中。算法的处理过程主要是从表的后端开始逐个向前进行搜索。算法结束时，返回i值作为查找的结果，查找成功时，返回找到的结点的位置，查找失败时返回值为0。算法9.1 顺序查找 C/C++ 程序：SeqSearch R, n, K int SeqSearch NodeType &R[ ], int n, KeyType K 1. R[0].key ← K; i ← n [ 准备 ] int i n;2. 循环，当R[i].key≠K时，执行 R[0].key K;i ← i-1 [ 在表中从后向前搜索 ] while R[i].key ! K i--;3. return i return i;4. [ 算法结束 ] ▌ 顺序查找的算法十分简单，但它的缺点是查找时间长，查找长度与表中结点个数n成正比。具体分析如下：若查找的关键字与表里第i个结点的关键字相等，则需要进行n-i+1次比较才能找到。设要查找的关键字性表中，并假设查找每个关键字的概率相同，即为 ，则对于成功查找的平均查找长度为从上式可知，对于成功查找的平均比较次数为表长的一半左右。

若要检索的关键字不在表中，则需要进行n +1次比较才能确定查找失败。假设被查找的关键字性表里 即查找成功 的概率为p，不性表里 查找失败 的概率为q 1- p，那么，把查找成功和查找失败的情况都考虑在内，则平均查找长度为ASL p + q n +1 p + 1- p n +1 1 - O n为了提高顺序查找的效率，可以对查找表 假定查找方法是从表的前端开始向后部进行搜索 做如下的改进：1. 当各结点的查找频率不等时，可以把查找频率高的结点放在表的前面，也就是使得i j时，pi ≥ pj，这样查找成功的平均查找长度就会小于表长的一半。2. 可按关键字值递增的顺序将结点排序，这样平均查找长度也会减小。因为这时不成功的查找就有可能不必把全部表搜索一遍，而只要比较到表中结点的关键字值大于所给定的查找条件K，就可断言表中不存在要找的结点。算法9.1对表的搜索方向是从后向前，请读者自行编写对表从前向后搜索的查找算法。9.2.2 折半查找折半查找 binary search 又称为二分法查找，它是一种效率较高的查找方法，但它要求被查找的线性表是顺序存储且表是按关键字排好序的。折半查找的基本方法是：在表首位置为low 1，表尾位置为high n的线性表中，先求出表的中间位置mid ，然后用给定的查找值K与R[mid].key进行比较。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-2.html