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); //递归查找右子树 }
