第七章 搜索结构
搜索的基本概念
所谓搜索，就是在数据集合中寻找满足某种 条件的数据对象。搜索的结果通常有两种可能：搜索成功、搜索不成功。
关键码：可以标识一个记录的某个数据项。
键值：关键码的值。
主关键码：可以唯一地标识一个记录的关键码。
次关键码：不能唯一地标识一个记录的关键码
查找的基本概念
静态搜索：不涉及插入和删除操作的搜索 。
动态搜索：涉及插入和删除操作的搜索。
静态搜索适用于：搜索集合一经生成，便只对其进行 搜索，而不进行插入和删除操作，或经过一段时间的 搜索之后，集中地进行插入和删除等修改操作；
动态搜索适用于：查找与插入和删除操作在同一个阶 段进行，例如当查找成功时，要删除查找到的记录， 当查找不成功时，要插入被查找的记录。
搜索结构 ：面向搜索操作的数据结构 ，即搜索基于的 数据结构。 集合中元素之间不存在明显的组织规律，不便查找。
线性表：适用于静态搜索，主要采用顺序搜索技术 和折半搜索技术。
树表：适用于动态搜索，主要采用二叉排序树的搜 索技术。
散列表：静态查找和动态查找均适用，主要采用散 列技术。
搜索算法的性能
搜索算法时间性能通过关键码的比较次数来度量。
关键码的比较次数与哪些因素有关呢？
平均搜索长度：将搜索算法进行的关键码的比较次数 的数学期望值定义为平均搜索长度，即：
ASL=求和(i从1到n) Pi*Ci
其中：n：问题规模，查找集合中的记录个数；Pi：搜索第i个记录的概率； Ci：搜索第i个记录所需的关键码的比较次数。
Ci取决于算法；pi与算法无关，取决于具体应用。如果pi 是已知的，则平均查找长度只是问题规模的函数。
线性表的搜索技术
静态搜索表
在静态搜索表中，数据元素存放于数组中，利 用数组元素的下标作为数据元素的存放地址。 搜索算法根据给定值 k，在数组中进行搜索。 直到找到 k 在数组中的存放位置或可确定在数 组中找不到 k 为止。
//数据表与搜索表的类定义
#include <iostream.h>
#include <assert.h>
const int defaultSize = 100;
template <class E, class K>
class dataList; //数据表类的前视定义
template <class E, class K >
class dataNode
{ //数据表中结点类的定义
friend class dataList<E, K>;//声明其友元类为dataList
private:
K key; //关键码域
E other; //其他域（视问题而定）
public:
dataNode (const K x) : key(x) { } //构造函数
K getKey() const { return key; } //读取关键码
void setKey (K x) { key = x; } //修改关键码
};
template <class E, class K >
class dataList { //数据表类定义
protected: dataNode<E, K> *Element; //数据表存储数组
int ArraySize, CurrentSize; //数组最大长度和当前长度
顺序搜索（Sequential Search）
顺序搜索主要用于在线性表中搜索。
顺序用各元素的关键码与给定值 x 进行比较 。技巧：把待查关键字key存入表头或表尾（俗称 “哨兵”），这样可以加快执行速度。
顺序查找 （线性查找）
基本思想：从线性表的一端向另一端逐个将关键码与 给定值进行比较，若相等，则查找成功，给出该记录 在表中的位置；若整个表检测完仍未找到与给定值相 等的关键码，则查找失败，给出失败信息。
//顺序查找 （线性查找）
int SeqSearch1(int r[ ], int n, int k)
//数组r[1] ~ r[n]存放查找集合
{
i = n;
while (i>0 &&r[i] != k)
i--;
return i;
}
改进的顺序查找
基本思想：设置“哨兵”。哨兵就是待查值，将它放 在查找方向的尽头处，免去了在查找过程中每一次比 较后都要判断查找位置是否越界，从而提高查找速度
//改进的顺序查找
int SeqSearch2(int r[ ], int n, int k)
//数组r[1] ~ r[n]存放查找集合
{
r[0] = k;
i = n;
while (r[i] != k)
i--;
return i;
}
ASL=O(n)
顺序查找的缺点：
平均查找长度较大，特别是当待查找集合中元素较多 时，查找效率较低。
顺序查找的优点：
算法简单而且使用面广。
对表中记录的存储没有任何要求，顺序存储和链接 存储均可；
对表中记录的有序性也没有要求，无论记录是否按 关键码有序均可。
基于有序顺序表的折半搜索
哨兵法当N很大时，搜索的效率很低。
如果把顺序表的元素按其关键码从小到大 排列，则可以采取效率更高的搜索算法。
折半搜索
使用条件：
线性表中的记录必须按关键码有序；
必须采用顺序存储。
基本思想：
折半搜索时, 先求位于搜索区间正中的对 象的下标mid，用其关键码与给定值x比较:
Element[mid].key == x，搜索成功；
Element[mid].key > x，把搜索区间缩小到表的前半部分，继续折半搜索；
Element[mid].key < x，把搜索区间缩小 到表的后半部分，继续折半搜索。
//折半查找——非递归算法
int BinSearch1(int r[ ], int n, int k)
{ //数组r[1] ~ r[n]存放查找集合
low = 1; high = n;
while (low <= high)
{
mid = (low + high) / 2;
if (k < r[mid]) high = mid - 1;
else if (k > r[mid]) low = mid + 1;
else return mid;
}
return 0;
}
//折半查找——递归算法
int BinSearch2(int r[ ], int low, int high, int k)
{ //数组r[1] ~ r[n]存放查找集合
if (low > high) return 0;
else {
mid = (low + high) / 2;
if (k < r[mid])
return BinSearch2(r, low, mid-1, k);
else if (k > r[mid])
return BinSearch2(r, mid+1, high, k);
else return mid;
}
}
折半搜索性能分析
若设 n = 2h-1，则描述折半搜索的判定树是 高度为 h的满二叉树。
n=2h -1, h = log（2） ｜ (n+1) ︱。
搜索成功：在表中查找任一记录的过程，即是折半查 找判定树中从根结点到该记录结点的路径，和给定值 的比较次数等于该记录结点在树中的层数。
搜索不成功：查找失败的过程就是走了一条从根结 点到外部结点的路径，和给定值进行的关键码的比 较次数等于该路径上内部结点的个数。
ASLsucc=log（2）（n+1）-1
动态查找表
特点：表结构在查找过程中动态生成。
要求：对于给定值key,若表中存在其关键字等于 key的记录，则查找成功返回； 否则插入或删除关键字等于key的记录。
典型的动态表———二叉搜索树(二叉排序树)
树表的搜索技术
二叉搜索树 ( Binary Search Tree )
定义
二叉搜索树或者是一棵空树，或者是具 有下列性质的二叉树：
所有结点的关键码互不相同。
左子树（如果非空）上所有结点的关键 码都小于根结点的关键码。
右子树（如果非空）上所有结点的关键 码都大于根结点的关键码。
左子树和右子树也是二叉搜索树。
二叉搜索树例
结点左子树上所 有关键码小于结 点关键码；
右子树上所有关 键码大于结点关 键码；
如果对一棵二叉搜索树进行中序遍历，可以按从小到大 的顺序，将各结点关键码排列起来，所以也称二叉搜索 树为二叉排序树。
二叉搜索树的类定义用二叉链表作为它的存储表示，许多 操作的实现与二叉树类似。
#include <iostream.h>
#include <stdlib.h>
template <class E, class K>
struct BSTNode { //二叉树结点类
E data; //数据域
BSTNode<E, K> *left, *right; //左子女和右子女
BSTNode() { left = NULL; right = NULL; }
BSTNode (const E d, BSTNode<E, K> *L = NULL, BSTNode<E, K> *R = NULL) { data = d; left = L; right = R;}
～BSTNode() {} //析构函数
void setData (E d) { data = d; } //修改
E getData() { return data; } //提取
bool operator < (const E& x) //重载：判小于
{ return data.key < x.key; }
bool operator > (const E& x) //重载：判大于
{ return data.key > x.key; }
bool operator == (const E& x) //重载：判等于
{ return data.key == x.key; }
};
template <class E, class K>
class BST { //二叉搜索树类定义
private:
BSTNode<E, K> *root; //根指针
K RefValue; //输入停止标志
public:
BST() { root = NULL; } //构造函数
BST(K value); //构造函数
～BST() {}; //析构函数
bool Search (const K x) const //搜索
{ return Search(x,root) != NULL; }
BST<E, K>& operator = (const BST<E, K>& R); //重载：赋值
void makeEmpty() //置空
{ makeEmpty (root); root = NULL;}
void PrintTree() const { PrintTree (root); } //输出
E Min() { return Min(root)->data; } //求最小
E Max() { return Max(root)->data; } //求最大
bool Insert (const E& e1) //插入新元素
{ return Insert(e1, root);}
bool Remove (const K x)
{ return Remove(x, root);} //删除含x的结点
private:
BSTNode<E, K> * Search (const K x, BSTNode<E, K> *ptr); //递归：搜索
void makeEmpty (BSTNode<E, K> *& ptr); //递归：置空
void PrintTree (BSTNode<E, K> *ptr) const; //递归：打印
BSTNode<E, K> * (const BSTNode<E, K> *ptr); //递归：复制
BSTNode<E, K>* Min (BSTNode<E, K>* ptr); //递归：求最小
BSTNode<E, K>* Max (BSTNode<E, K>* ptr); //递归：求最大
bool Insert (const E& e1, BSTNode<E, K>*& ptr); //递归：插入
bool Remove (const K x, BSTNode<E, K>*& ptr); //递归：删除
};
二叉搜索树的搜索算法
在二叉搜索树上进行搜索，是一个从根结点开始，递 归进行比较判等的过程。
假设想要在二叉搜索树中搜索关键码为 x 的元素，搜 索过程从根结点开始。
如果根指针为NULL，则搜索不成功；否则用给定值 x 与根结点的关键码进行比较：
若给定值等于根结点关键码，则搜索成功
若小于根结点的关键码，则搜索左子树；
否则。递归搜索根结点的右子树。
template<class E, class K>
BSTNode<E, K>* BST<E, K>:: Search (const K x, BSTNode<E, K> *ptr)
{ //私有递归函数：在以ptr为根的二叉搜索树中搜 //索含x的结点。若找到，则函数返回该结点的
//地址，否则函数返回NULL值。
if (ptr == NULL) return NULL;
else if (x < ptr->data) return Search(x, ptr->left);
else if (x > ptr->data) return Search(x, ptr->right);
else return ptr; //搜索成功
};
template<class E, class K>
BSTNode<E, K>* BST<E, K>:: Search (const K x, BSTNode<E, K> *ptr) {
//非递归函数：作为对比，在当前以ptr为根的二
//叉搜索树中搜索含x的结点。若找到，则函数返
//回该结点的地址，否则函数返回NULL值。
if (ptr == NULL) return NULL;
BSTNode<E, K>* temp = ptr;
while (temp != NULL)
{
if (x == temp->data) return temp;
if (x < temp->data) temp = temp->left;
else temp = temp->right;
}
return NULL;
};
搜索过程是从根结点开始，沿某条路径自 上而下逐层比较判等的过程。
搜索成功，搜索指针将停留在树上某个结 点；
搜索不成功，搜索指针将走到树上某 个结点的空子树。
设树的高度为h，最多比较次数不超过h。
二叉搜索树的插入算法
为了向二叉搜索树中插入一个新元素，必须 先检查这个元素是否在树中已经存在。
在插入之前，先使用搜索算法在树中检查要 插入元素有还是没有。
如果搜索成功，说明树中已经有这个元素， 不再插入；
如果搜索不成功，说明树中原来没有关键 码等于给定值的结点，把新元素加到搜索 操作停止的地方。
二叉搜索树的插入
每次结点的插入，都要 从根结点出发搜索插入 位置，然后把新结点作为叶结点插入。
利用二叉搜索树的插入算法，可以很方 便地建立二叉搜索树。
template <class E, class K>
bool BST<E, K>::Insert (const E& e1, BSTNode<E, K> *& ptr)
{ //注意参数形式
if (ptr == NULL)
{ //新结点作为叶结点插入
ptr = new BstNode<E, K>(e1); //创建新结点
if (ptr == NULL){ cerr << "Out of space" << endl; exit(1); }
return true;
}
else if (e1 < ptr->data) return Insert (e1, ptr->left);
else if (e1 > ptr->data) return Insert (e1, ptr->right);
else return false; //x已在树中,不再插入
};
template <class E, class K> BST<E, K>::BST (K value)
{ //输入一个元素序列, 建立一棵二叉搜索树
E x;
root = NULL; RefValue = value; //置空树
cin >> x; //输入数据
while ( x.key != RefValue) { //RefValue是一个输入结束标志
Insert (x, root); cin >> x; //插入，再输入数据
}
};
//二叉搜索树插入的非递归方法
#include<iostream>
using namespace std;
typedef struct Binode
{
int data;
Binode *l, *r;
}Binode,*Bitree;
void insert(Bitree & t, int i){
Bitree p =t, parent;
while (p != NULL)
{
if (i > p->data){ parent=p;p = p->r;}
else if (i < p->data) {parent=p;p = p->l;}
else if (i == p->data) return; }
p=new Binode;
p->data = i;
p->l = NULL;
p->r = NULL;
if(t==NULL) t=p;
else
if(parent->data<i) parent->r= p;
else parent->l=p;
}
int main(){
Bitree t = NULL;
int n, k, i;
cin >> n>> k;
while (n--)
{ cin >> i;
insert(t, i);
cout<<i<<" is inserted";
}
二叉搜索树的删除
在二叉排序树上删除某个结点之后，仍然保持二叉排 序树的特性。
分三种情况讨论：
被删除的结点是叶子； 操作：将双亲结点中相应指针域的值改为空。
被删除的结点只有左子树或者只有右子树； 操作：将双亲结点的相应指针域的值指向被删除 结点的左子树（或右子树）。
被删除的结点既有左子树，也有右子树。 操作：被删结点左、右子树都不为空，以其左子树中的最大值结点（或右子树中的最小 值结点）替代之，再来处理这个结点的删除问题。
template <class E, class K>
bool BST<E, K>::Remove (const K x, BstNode<E, K> *& ptr)
{ //在以 ptr 为根的二叉搜索树中删除含 x 的结点
BstNode<E, K> *temp;
if (ptr != NULL) {
if (x < ptr->data)
return Remove (x, ptr->left); //在左子树中执行删除
else if (x > ptr->data)
return Remove (x, ptr->right); //在右子树中执行删除
else if (ptr->left != NULL && ptr->right != NULL)
{ //ptr指示关键码为x的结点，它有两个子女
temp = ptr->right; //到右子树搜寻中序下第一个结点
while (temp->left != NULL)
temp = temp->left;
ptr->data = temp->data; //用该结点数据代替根结点数据
return Remove (ptr->data, ptr->right);
}
else { //ptr指示关键码为x的结点有一个子女
temp = ptr;
if (ptr->left == NULL) ptr = ptr->right;
else ptr = ptr->left;
delete temp;
return true;
}
}
return false;
};
注意在删除算法参数表引用型指针参数的使用
二叉搜索树性能分析
对于有 n 个关键码的集合，其关键码有 n! 种 不同排列，可构成不同二叉搜索树有 ( 1/(n+1) )*C 2n,n
同样 3 个数据{ 1, 2, 3 }，输入顺序不同，建立 起来的二叉搜索树的形态也不同。这直接影响 到二叉搜索树的搜索性能。
如果输入序列选得不好，会建立起一棵单支树， 使得二叉搜索树的高度达到最大。
在二叉搜索树中加入外结点，形成判定树。外 结点表示失败结点，内结点表示搜索树中已有 的数据。
这样的判定树即为扩充的二叉搜索树。
一般把平均搜索长度达到最小的扩充的二叉搜 索树称作最优二叉搜索树。
在相等搜索概率的情形下，所有内部、外部结 点的搜索概率都相等，视它们的权值都为 1。 同时，第 k 层有 2^(k-1)个结点，k = 1, 2, ... 。则 有 n 个内部结点的扩充二叉搜索树的内部路径 长度 I 至少等于序列
0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, … 的前 n 项的和。
因此，最优二叉搜索树的搜索成功的平均搜索 长度和搜索不成功的平均搜索长度分别为:
(2) 不相等搜索概率的情形
不相等搜索概率情形下的最优二叉搜索树可能不同于完全二叉树的形态。考虑在不相等搜索概率情形下如何构造最优二叉搜索树。要构造最优二叉搜索树，必须先构造它的左子树和右子树，它们也是最优二叉搜索树。
构造最优二叉搜索树的方法就是自底向上逐步构造的方法。
构造的步骤
第一步，构造只有一个内部结点的最优搜索树：T[0] [1]，T[1] [2]，…，T[n-1] [n]。
在T[i-1] [i] (1 i n) 中只包含关键码 key[i]。其代价分别是 C[i-1] [i] = W[i-1] [i]。另外设立一 个数组 R[0..n] [0..n] 存放各最优二叉搜索树的根。R[0] [1] = 1, R[1] [2] = 2, … , R[n-1] [n] = n。
第二步, 构造有两个内部结点的最优二叉搜索树：T[0] [2], T[1] [3], …, T[n-2] [n]。在T[i-2] [i] 中包含两个关键码 { key[i-1], key[i] }。其代价取分别以 key[i-1], key[i] 做根时计算出的 C[i-2] [i] 中的小者。
第三步，第四步，…，构造有 3 个内部结点，有 4 个内部结点，… 的最优二叉搜索树。
最后构造出包含有 n 个内部结点的最优二叉搜索树。对于这样的最优二叉搜索树，若设根为 k，则根 k 的值存于 R[0] [n] 中，其代价存于 C[0] [n] 中，左子树的根存于 R[0] [k-1] 中，右子树的根存于 R[k] [n] 中。
散列表的搜索技术
具体内容见第六章笔记
//线性探查法的搜索算法，函数返回找到位置。
//若返回负数可能是空位，若为-TableSize则失败。
Find ( const Type & x ) {
int i = FindPos ( x ), j = i;
while ( ht[j].info != Empty && ht[j].Element != x ){
j = ( j + 1 ) % TableSize;
if ( j == i ) return -TableSize;
}
if ( ht[j].info == Active ) return j;
else -j;
}
线性探查方法容易产生“堆积”，不同探查序列的关键码占据可用的空桶，为寻找某一关键码需要经历不同的探查序列，导致搜索时间增加。
//循链搜索的算法
template <class Type>
Type *HashTable<Type>:: Find ( const Type & x,)
{
int j = HashFunc ( x, buckets );
ListPtr<Type> *p = ht[j];
while ( p != NULL )
if ( p→key == x ) return & p→key;
else p = p→link;
return 0;
}