顺序
说明：
顺序查找适用于存储结构为顺序存储或链式存储的线性表。
基本思想：
顺序查找也称为线形查找，属于无序查找算法。从数据结构线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定K值进行比较，若相等则表示查找成功，若扫描结束仍旧没有找到关键字等于K的结点，则表示查找失败。
代码
#include<iostream>
using namespace std;
int SequenceSearch(int a[], int value, int n)
{
int i;
for (i = 0; i<n; i++)
if (a[i] == value)
return i;
return -1;
}
int main()
{
int a[] = { 2, 3, 5, 8, 6, 7, 9, 0 };
int key, index;
int n = sizeof(a) / sizeof(a[0]);
cout << "请输入待查找的值：" << endl;
cin >> key;
index = SequenceSearch(a, key, n);
if (index >= 0)
{
cout << "找到了" << endl;
}
else
{
cout << "没找到" << endl;
}
system("pause");
return 0;
二分
说明：
元素必须有序方能使用，无序则要先进行排序。
基本思想：
二分查找也叫折半查找，属于有序查找算法。用给定K值先与中间节点的关键字进行比较，中间节点把线性表分层两个子表，若相等则查找成功；若不相等，再根据K与中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找或查找结束没有发现表中有这样的结点。
代码
#include<iostream>
using namespace std;
//二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (a[mid] == value)
return mid;
if (a[mid]>value)
high = mid - 1;
if (a[mid]<value)
low = mid + 1;
}
return -1;
}
//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
int mid = low + (high - low) / 2;
if (a[mid] == value)
return mid;
if (a[mid]>value)
return BinarySearch2(a, value, low, mid - 1);
if (a[mid]<value)
return BinarySearch2(a, value, mid + 1, high);
}
int main()
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int key, len;
cout << "请键入KEY值：" << endl;
cin >> key;
len = sizeof(a) / sizeof(a[0]);
//int index = BinarySearch1(a, key, len);
int index = BinarySearch2(a, key, 0, len-1);
if (index >= 0) cout << "找到" << endl;
else cout << "没找到" << endl;
system("pause");
return 0;
}
插值
说明：
自适应的二分查找
基本思想：
插值查找是根据要查找的关键字Key与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值的计算公式：Key-arr[low]/arr[high]-arr[low]。
- mid的计算公式为：(high-low)*(key-arr[low])/(arr[high]-arr[low])，
- 对半查找（折半查找、二分查找）的mid=(high-low)/2。
- 这种mid的改变的好处是：对于表长较长，且关键字分布比较均匀，插值查找算法的平均性能要高于折半查找，但是如果关键字分布极不均匀，那么插值查找不如折半查找。
代码
#include <iostream>
using namespace std;
//插值查找法 arr数组，length 数组长度，key 查找的关键字
//返回查找值的下标 ，没查找到 返回-1
int Interpolation_Search(int *arr, int length, int key)
{
int low = 0;//低位下标
int high = length - 1;//高位下标
int mid;//中间值下标
while (low <= high)
{
mid = (high - low)*(key - arr[low]) / (arr[high] - arr[low]);//插值
if (key < arr[mid])
{
high = mid - 1;
}
else if (key > arr[mid])
{
low = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
int main()
{
int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int key;
cout << "请键入key值：" << endl;
cin >> key;
int index = Interpolation_Search(arr, 10, key);
if (index >= 0) cout << "找到了，index为" << index << endl;
else cout << "没找到" << endl;
system("pause");
return 0;
}
斐波那契
说明：
也是二分查找的一种提升算法
- 斐波那契是一种特殊的分割方法，和二分、插值本质上是一样的，都是分割方法；
- 利用了斐波那契数列特殊的性质，一个长度只要可以被黄金分割，那么分割后的片段仍然可以继续进行黄金分割，循环。
基本思想：
通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。
他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;
开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种
- 1）相等，mid位置的元素即为所求
- 2）>，low=mid+1,k-=2;
- 说明：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个，所以可以递归的应用斐波那契查找。
- 3）<，high=mid-1,k-=1。
- 说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。
代码
#include <iostream>
using namespace std;
#define MAXN 20
/*
*产生斐波那契数列
* */
void Fibonacci(int *f)
{
int i;
f[0] = 1;
f[1] = 1;
for (i = 2; i < MAXN; ++i)
f[i] = f[i - 2] + f[i - 1];
}
/*
* 查找
* */
int Fibonacci_Search(int *a, int key, int n)
{
int i, low = 0, high = n - 1;
int mid = 0;
int k = 0;
int F[MAXN];
Fibonacci(F);
while (n > F[k] - 1) //计算出n在斐波那契中的数列
++k;
for (i = n; i < F[k] - 1; ++i) //把数组补全
a[i] = a[high];
while (low <= high)
{
mid = low + F[k - 1] - 1; //根据斐波那契数列进行黄金分割
if (a[mid] > key)
{
high = mid - 1;
k = k - 1;
}
else if (a[mid] < key)
{
low = mid + 1;
k = k - 2;
}
else
{
if (mid <= high) //如果为真则找到相应的位置
return mid;
else
return -1;
}
}
return -1;
}
int main()
{
int a[MAXN] = { 5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57 };
int k, res = 0;
cout << "请输入要查找的数字:";
cin>>k;
res = Fibonacci_Search(a, k, 13);
if (res != -1)
cout << "在数组的第" << res + 1 << "个位置找到元素:" << k << endl;
else
cout << "未在数组中找到元素:" << k << endl;
system("pause");
return 0;
}
二叉查找树
说明：
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。
基本思想：
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
复杂度分析：
- 它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。
- 原因在于插入和删除元素的时候，树没有保持平衡（比如，我们查找上图（b）中的“93”，我们需要进行n次查找操作）。
- 我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。
#include<iostream>
#include <iomanip>//输出控制的头文件
using namespace std;
typedef struct Node{
int data;
struct Node *left, *right;
}BTNode;
//创建二叉树
BTNode *CreateBTtree(int a[], int n)
{
BTNode *root, *c, *pa=NULL, *p;
int i;
root = (BTNode *)malloc(sizeof(BTNode));
root->data = a[0];
root->left = root->right = NULL;
for (i = 1; i<n; i++)
{
p = (BTNode *)malloc(sizeof(BTNode));
p->left = p->right = NULL;
p->data = a[i];
c = root;
while (c)
{
pa = c;
if (c->data<p->data)
c = c->right;
else
c = c->left;
}
if (pa->data<p->data)
pa->right = p;
else
pa->left = p;
}
return root;
}
//前序遍历
void Forder(BTNode *root)
{
if (root)
{
//printf("%5d", root->data);
cout << setw(5) << root->data;
Forder(root->left);
Forder(root->right);
}
}
//中序遍历
void Inorder(BTNode *root)
{
if (root)
{
Inorder(root->left);
//printf("%5d", root->data);
cout << setw(5) << root->data;
Inorder(root->right);
}
}
//后序遍历
void Porder(BTNode *root)
{
if (root)
{
Porder(root->left);
Porder(root->right);
//printf("%5d", root->data);
cout << setw(5) << root->data;
}
}
BTNode *FindNode(BTNode *root, int key)
{
BTNode *p;
if (!root)
return NULL;
else if (root->data == key)
return root;
else if (key<root->data)
return FindNode(root->left, key);
else
return FindNode(root->right, key);
}
int main()
{
int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
BTNode *root, *p;
int key;
cout<<"任意键入一个key值：";
cin>>key;
root = CreateBTtree(a, 8);
//前序遍历
cout << "前序遍历为:";
Forder(root);
cout << endl;
//中序遍历
cout<<"中序遍历为:";
Inorder(root);
cout << endl;
//后序遍历
cout << "后序遍历为:";
Porder(root);
cout << endl;
p = FindNode(root, key);
//printf("地址为：%x\n", p);
cout << "地址为：" << p << endl;
system("pause");
return 0;
}
分块
说明
分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
基本思想
- 将n个数据元素"按块有序"划分为m块（m ≤ n）。
- 每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……
代码
//分块查找算法
#include <iostream>
using namespace std;
struct index //定义一个结构体用来分块
{
int key;
int start;
int end;
}index[4];
int search(int key, int a[]);
int main()
{
int i, j = -1, k, key;
int a[] = { 42, 63, 82, 89, 111, 146, 219, 254, 325, 336, 348, 795, 867, 951, 998 };
cout << "已知有一数组" << endl;
for (i = 0; i<15; i++)
cout << a[i] << " ";
cout << endl;
for (i = 0; i<3; i++) //3个块
{
index[i].start = j + 1;//确定每个块的起始值
j = j + 1;
index[i].end = j + 4;//确定每个块的结束值
j = j + 4;
index[i].key = a[j];//确定每个块范围中的元素最大值
}
cout << "请输入你要查找的数：" << endl;
cin >> key;
k = search(key, a);
if (k >= 0)
cout << "查找成功！你要找的数字在数组中的位置是：" << k + 1 << endl;
else
cout << "查找失败！你要找的数字不在数组中。" << endl;
system("pause");
return 0;
}
int search(int key, int a[])
{
int i, j;
i = 0;
while (i<3 && key>index[i].key)//确定在哪个块中
i++;
if (i >= 3)//大于分得的块数 返回0
return -1;
j = index[i].start;//j等于块范围的起始值
while (j <= index[i].end&&a[j] != key)//在确定的块内进行查找
j++;
if (j>index[i].end)//如果大于块范围的结束值 则说明没有要查找的数 j置-1
j = -1;
return j;
}
哈希
说明
我们使用一个下标范围比较大的数组来存储元素。
基本思想
可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
代码
#include<iostream>
using namespace std;
#define OK 1
#define HASHSIZE 7 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768
typedef int Status;
typedef struct
{
int *elem; /* 数据元素存储地址，动态分配数组 */
int count; /* 当前数据元素个数 */
}HashTable;
int m = 0; /* 散列表表长，全局变量 */
/*初始化*/
Status Init(HashTable *hashTable)
{
int i;
m = HASHSIZE;
hashTable->elem = (int *)malloc(m*sizeof(int)); //申请内存
hashTable->count = m;
for (i = 0; i<m; i++)
{
hashTable->elem[i] = NULLKEY;
}
return OK;
}
/*哈希函数(除留余数法)*/
int Hash(int data)
{
return data%m;
}
/*插入*/
void Insert(HashTable *hashTable, int data)
{
int hashAddress = Hash(data); //求哈希地址
//发生冲突
while (hashTable->elem[hashAddress] != NULLKEY)
{
//利用开放定址的线性探测法解决冲突
hashAddress = (++hashAddress) % m;
}
//插入值
hashTable->elem[hashAddress] = data;
}
/*查找*/
int Search(HashTable *hashTable, int data)
{
int hashAddress = Hash(data); //求哈希地址
//发生冲突
while (hashTable->elem[hashAddress] != data)
{
//利用开放定址的线性探测法解决冲突
hashAddress = (++hashAddress) % m;
if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data)) return -1;
}
//查找成功
return hashAddress;
}
/*打印结果*/
void Display(HashTable *hashTable)
{
int i;
cout << endl;
cout << "**********展示结果**********" << endl;
for (i = 0; i<hashTable->count; i++)
{
cout << hashTable->elem[i] << ",";
}
cout << endl;
cout << "**********展示完毕**********" << endl;
}
int main()
{
int i, j, result, key;
HashTable hashTable;
int arr[HASHSIZE] = { 13, 29, 27, 28, 26, 30, 38 };
cout << "***************哈希查找(C++版)***************" << endl;
//初始化哈希表
Init(&hashTable);
//插入数据
for (i = 0; i<HASHSIZE; i++)
{
Insert(&hashTable, arr[i]);
}
Display(&hashTable);
//查找数据
cout << "请键入key值：" << endl;
cin >> key;
result = Search(&hashTable, key);
if (result == -1) cout << "对不起，没有找到！" << endl;
else cout << key << "在哈希表中的位置是:" << result << endl;
getchar();
system("pause");
return 0;
}