《数据结构与算法》——简单查找
二分查找法：将按大小顺序排列好的数字存放在数组，我们将low，high分别初始化为0和数组下标最大值，mid=(low+high)/2,不断的比较mid指向的元素和待查找元素key的值，若mid>key，则使high=mid，重复之前步骤；反正low=mid，直至key与mid指向元素相等，或low=high。插值查找：原理与二分查找类似，但是插值查找利用比例来找到mid的下一个位置，即
mid=low+(key-a)/(a-key)*(high-low)，来确定下一个mid，进行递归或者迭代。
斐波那契查找：该算法将数组元素不断地分为两个斐波那契数，如大小为13的数组则被分为5和8两个部分，然后比较key与a，以此不断地进行递归或者迭代，直至low=high或找到目标key的下标。当数组元素个数不足时，用最大值补足
#include<cstdio>
#include<cstdlib>
#include<time.h>
#include<iostream>
using namespace std;
class LIST
{
public:
char name;
int score,ID;
};
int key;
int Input(LIST *&s)
{
cout << "input the numbers of students；";
int n;
cin >> n;
s = new LIST;
printf("input the student's name,ID numbers,score:\n");
for (int i = 0; i < n; i++)
{
cin >> (s+i)->ID >> (s + i)->name >> (s + i)->score;
}
return n;
}
void Binary_search(LIST *s,int low,int high)
{
int mid = (high + low) / 2;
int k = (s - mid)->ID;
if (low == high)
{
cout << "no such student" << endl;
return;
}
if (key < (s - mid)->ID)
{
cout << (s - mid)->ID << endl;
Binary_search(s, mid+1, high);
}
else if (key > (s - mid)->ID)
{
cout << (s - mid)->ID << endl;
Binary_search(s, low, mid);
}
else if (key == (s - mid)->ID)
{
cout << "ID:" << (s + mid)->ID << "name:" << (s + mid)->name << "score:" << (s + mid)->score << endl;
}
}
void Inter_search(LIST *s, int low, int high)
{
int mid = low + (key - (s + low)->ID) / ((s + high)->ID - (s + low)->ID + 1);
if (low == high)
{
cout << "no such student" << endl;
return;
}
if (key > (s + mid)->ID)
{
Binary_search(s, mid, high);
}
else if (key < (s + mid)->ID)
{
Binary_search(s, low, mid);
}
else if (key == (s + mid)->ID)
{
cout << "ID:" << (s + mid)->ID << "name:" << (s + mid)->name << "score:" << (s + mid)->score << endl;
}
}
int Fabonacci(int n)
{
int a = 1, b = 1;
int result = 1;
while (1)
{
if (n > result&&n < a + b)
{
return a ;
}
else if(n>a+b)
{
result = a + b;
b = a;
a = result;
}
else if (n == a + b)
{
return result;
}
else if (n == result)
{
return b;
}
}
}
void Fabonacci_search(LIST *s, int low,int high)
{
int mid = Fabonacci(high-low)-1;
//判断是否有不存在的可能
if (key < (s + mid + low )->ID)
{
Fabonacci_search(s, low, mid);
}
else if(key > (s + mid + low)->ID)
{
Fabonacci_search(s, mid+1, high);
}
else if (key == (s + mid + low )->ID)
{
cout << "ID:" << (s + mid )->ID << " name:" << (s + mid )->name << " score:" << (s + mid )->score << endl;
}
}
int main()
{
LIST *s;
int n;
clock_t start,end;
n=Input(s);
int choice=1;
cout << "input the target ID number:";
cin >> key;
while (choice)
{
printf("1——>二分查找\n2——>差值查找\n3——>斐波那契查找\n0——>结束程序\n");
printf("input your choice:");
scanf_s("%d", &choice);
switch(choice)
{
case 1:
start = clock();
Binary_search(s,0,n);
end = clock();
cout << "used time is " << (double)(end - start)/ CLOCKS_PER_SEC << endl;
break;
case 2:
start = clock();
Inter_search(s,0,n);
end = clock();
cout << "used time is " << (double)(end - start) / CLOCKS_PER_SEC << endl;
break;
case 3:
start = clock();
Fabonacci_search(s,0,n);
end = clock();
cout << "used time is " << (double)(end - start) / CLOCKS_PER_SEC << endl;
break;
case 0:
break;
default:
cout << "Wrong!"<<endl;
break;
}
}
system("PAUSE");
}
页:
[1]