查找算法
目前不断更新中,算法描述图有时间补上
//查找使用ASL平均查找长度来判断算法的性能 ASL=ΣPiCi (i∈[1,n])
//线性表的查找
template<class T>
class Search {
public:
//顺序查找:
//条件: 无
//思想:从后往前与要查找的值比较,设置一个哨兵简化算法
//查找成功的情况下 平均查找长度ASL=(n+1)n/2n=(n+1)/2
//查找不成功ASL=n+1
int SeqSearch(T a[],int n,T key){
int i;
a[0] = key; //设置哨兵,如果返回的值为0的话说明查找失败
for ( i = n; a[i] != key; i--);
return i;
}
//折半查找:
//条件: 关键码有序
//思想:设置变量low,high分别指向最高和最低值,令mid=(high+low)/2，将mid与key比较,可以根据大小判断位于哪个区域,逐渐缩小
//以十个元素为例,查找第5个元素需要比较1次,第2、8元素需要2次，1、3，6，9需要3次，4、7需要4次，可以将其看为一个完全二叉树，称为判定树
//那么深度与判定树的深度相同
//查找成功 Σj*2^(j-1)/n [1,h] (Σ2^t [1,h] <= n) 当n>50 ASL≈log2(n+1) - 1
//查找失败 ASL=log2 n + 1 注意:关键码排序即使最好的方法时间复杂度也是nlog2 n
int Search_Bin(T a[], int n, T key) { //非递归式
int low = 1;
int high = n;
while (low <= high) { //保证低位不大于高位,如果大于则查找失败返回0
int mid = (low + high) / 2; //找到最高与最低的中间值,并于key进行比较,如果大于则将低位改为mid+1,小于高位改为mid-1,类推
if (key == a[mid]) {
return mid;
}
else if (key < a[mid]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return 0;
}
int BinSearch(T r[], int low, int high, int k) { //递归式
if (low < high) { //通过low<high确定是否查找成功
int mid = (low + high) / 2;
if (r[mid] == k) {
return mid;
}
else if (r[mid] > k) { //通过比较中间值的高低来确定范围
return BinSearch(r, low, mid - 1,k);
}
else {
return BinSearch(r, mid + 1, high, k);
}
}
else{ //设置错误的返回码
return 0;
}
}
//分块查找:
//思想:设置一个索引表,索引表标明了一定范围的关键码,根据索引来确定范围,再在范围中进行顺序或折半查找
//将长为n的表分为b块,每块有s条记录
//如果使用顺序查找ASL = (n/s+s)/2+1
//折半查找log2(n/s+1)+s/2
//这部分源码有机会补上
};
//树表的查找
//二叉排序树:
//左孩子小于根节点,右孩子大于根节点,他的左右子树也是二叉排序树，按照树的中序遍历就可得到一个有序数列
//二叉排序树方便进行查找的元素的插入和删除
template<class T>
class Node {
public:
T data;
Node<T>* lch;
Node<T>* rch;
Node:lch(NULL), rch(NULL){};
};