|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
二分查找法:将按大小顺序排列好的数字存放在数组,我们将low,high分别初始化为0和数组下标最大值,mid=(low+high)/2,不断的比较mid指向的元素和待查找元素key的值,若mid>key,则使high=mid,重复之前步骤;反正low=mid,直至key与mid指向元素相等,或low=high。
插值查找:原理与二分查找类似,但是插值查找利用比例来找到mid的下一个位置,即
mid=low+(key-a[low])/(a[high]-key)*(high-low),来确定下一个mid,进行递归或者迭代。
斐波那契查找:该算法将数组元素不断地分为两个斐波那契数,如大小为13的数组则被分为5和8两个部分,然后比较key与a[5],以此不断地进行递归或者迭代,直至low=high或找到目标key的下标。当数组元素个数不足时,用最大值补足
- #include<cstdio>
- #include<cstdlib>
- #include<time.h>
- #include<iostream>
- using namespace std;
- class LIST
- {
- public:
- char name[10];
- int score,ID;
- };
- int key;
- int Input(LIST *&s)
- {
- cout << "input the numbers of students;";
- int n;
- cin >> n;
- s = new LIST[n];
- 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");
- }
复制代码 |
评分
-
查看全部评分
|