4 斐波那契查找
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1；开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1).
算法思路：
相等，mid位置的元素即为所求
大于，low=mid+1,k-=2;
小于，high=mid-1,k-=1。
说明：
low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。
代码：
#include "stdafx.h"
#include <memory>
#include <iostream>
using namespace std;
const int max_size=20;//斐波那契数组的长度
/*构造一个斐波那契数组*/
void Fibonacci(int * F)
{
F[0]=0;
F[1]=1;
for(int i=2;i<max_size;++i)
F[i]=F[i-1]+F[i-2];
}
/*定义斐波那契查找法*/
int FibonacciSearch(int *a, int n, int key) //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
int low=0;
int high=n-1;
int F[max_size];
Fibonacci(F);//构造一个斐波那契数组F
int k=0;
while(n>F[k]-1)//计算n位于斐波那契数列的位置
++k;
int * temp;//将数组a扩展到F[k]-1的长度
temp=new int [F[k]-1];
memcpy(temp,a,n*sizeof(int));
for(int i=n;i<F[k]-1;++i)
temp[i]=a[n-1];
while(low<=high)
{
int mid=low+F[k-1]-1;
if(key<temp[mid])
{
high=mid-1;
k-=1;
}
else if(key>temp[mid])
{
low=mid+1;
k-=2;
}
else
{
if(mid<n)
return mid; //若相等则说明mid即为查找到的位置
else
return n-1; //若mid>=n则说明是扩展的数值,返回n-1
}
}
delete [] temp;
return 0;
}
int main()
{
int a[] = {0,1,4,35,47,53,62,78,88,99};
int key=47;
int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
if(index == 0)
{
cout<<"没有找到"<<key;
}
else
{
cout<<key<<" 的位置是:"<<index;
}
return 0;
}
5 哈希查找
哈希表：
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
"直接定址"与"解决冲突"是哈希表的两大特点。
哈希函数：
规则：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。
如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
用给定的哈希函数构造哈希表；
根据选择的冲突处理方法(常见方法：拉链法和线性探测法)解决地址冲突；
在哈希表的基础上执行哈希查找；
#include<stdio.h>
#include<stdlib.h>
#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1
#define MAXNUM 9999 // 用于初始化哈希表的记录 key
typedef int Status;
typedef int KeyType;
// 哈希表中的记录类型
typedef struct
{
KeyType key;
}RcdType;
// 哈希表类型
typedef struct
{
RcdType *rcd;
int size;
int count;
int *tag;
}HashTable;
// 哈希表每次重建增长后的大小
int hashsize[] = { 11, 31, 61, 127, 251, 503 };
int index = 0;
// 初始哈希表
Status InitHashTable(HashTable &H, int size)
{
int i;
H.rcd = (RcdType *)malloc(sizeof(RcdType)*size);
H.tag = (int *)malloc(sizeof(int)*size);
if (NULL == H.rcd || NULL == H.tag) return OVERFLOW;
KeyType maxNum = MAXNUM;
for (i = 0; i < size; i++)
{
H.tag[i] = 0;
H.rcd[i].key = maxNum;
}
H.size = size;
H.count = 0;
return OK;
}
// 哈希函数：除留余数法
int Hash(KeyType key, int m)
{
return (3 * key) % m;
}
// 处理哈希冲突：线性探测
void collision(int &p, int m)
{
p = (p + 1) % m;
}
// 在哈希表中查询
Status SearchHash(HashTable H, KeyType key, int &p, int &c)
{
p = Hash(key, H.size);
int h = p;
c = 0;
while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p])
{
collision(p, H.size); c++;
}
if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS;
else return UNSUCCESS;
}
//打印哈希表
void printHash(HashTable H)
{
int i;
printf("key : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.rcd[i].key);
printf("\n");
printf("tag : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.tag[i]);
printf("\n\n");
}
// 函数声明：插入哈希表
Status InsertHash(HashTable &H, KeyType key);
// 重建哈希表
Status recreateHash(HashTable &H)
{
RcdType *orcd;
int *otag, osize, i;
orcd = H.rcd;
otag = H.tag;
osize = H.size;
InitHashTable(H, hashsize[index++]);
//把所有元素，按照新哈希函数放到新表中
for (i = 0; i < osize; i++)
{
if (1 == otag[i])
{
InsertHash(H, orcd[i].key);
}
}
return OK;
}
// 插入哈希表
Status InsertHash(HashTable &H, KeyType key)
{
int p, c;
if (UNSUCCESS == SearchHash(H, key, p, c))
{ //没有相同key
if (c*1.0 / H.size < 0.5)
{ //冲突次数未达到上线
//插入代码
H.rcd[p].key = key;
H.tag[p] = 1;
H.count++;
return SUCCESS;
}
else recreateHash(H); //重构哈希表
}
return UNSUCCESS;
}
// 删除哈希表
Status DeleteHash(HashTable &H, KeyType key)
{
int p, c;
if (SUCCESS == SearchHash(H, key, p, c))
{
//删除代码
H.tag[p] = -1;
H.count--;
return SUCCESS;
}
else return UNSUCCESS;
}
int main()
{
printf("-----哈希表-----\n");
HashTable H;
int i;
int size = 11;
KeyType array[8] = { 22, 41, 53, 46, 30, 13, 12, 67 };
KeyType key;
//初始化哈希表
printf("初始化哈希表\n");
if (SUCCESS == InitHashTable(H, hashsize[index++])) printf("初始化成功\n");
//插入哈希表
printf("插入哈希表\n");
for (i = 0; i <= 7; i++)
{
key = array[i];
InsertHash(H, key);
printHash(H);
}
//删除哈希表
printf("删除哈希表中key为12的元素\n");
int p, c;
if (SUCCESS == DeleteHash(H, 12))
{
printf("删除成功，此时哈希表为：\n");
printHash(H);
}
//查询哈希表
printf("查询哈希表中key为67的元素\n");
if (SUCCESS == SearchHash(H, 67, p, c)) printf("查询成功\n");
//再次插入，测试哈希表的重建
printf("再次插入，测试哈希表的重建：\n");
KeyType array1[8] = { 27, 47, 57, 47, 37, 17, 93, 67 };
for (i = 0; i <= 7; i++)
{
key = array1[i];
InsertHash(H, key);
printHash(H);
}
getchar();
return 0;
}
6 二叉树查找
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
若b是空树，则搜索失败：
若x等于b的根节点的数据域之值，则查找成功：
若x小于b的根节点的数据域之值，则搜索左子树：
查找右子树。
递归和非递归
//非递归查找算法
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p)
{
//查找函数返回指向关键字值为key的结点指针，不存在则返回NULL
p=NULL;
while(T!=NULL&&key!=T->data)
{
p=T; //指向被查找结点的双亲
if(key<T->data)
T=T->lchild; //查找左子树
else
T=T->rchild; //查找右子树
}
return T;
}
//递归算法
Status Search_BST(BiTree T, int key, BiTree f, BiTree *p)
{
//查找BST中是否存在key，f指向T双亲，其初始值为NULL
//若查找成功，指针p指向数据元素结点，返回true；
//若失败，p指向查找路径上访问的最后一个结点并返回false
if(!T)
{
*p=f;
return false;
}
else if(key==T->data)
{ //查找成功
*p=T;
return true;
}
else if(key<T->data)
return Search_BST(T->lchild,key,T,p); //递归查找左子树
else
return Search_BST(T->rchild,key,T,p); //递归查找右子树
}
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)