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=)