實驗?zāi)康募耙?/b>
熟練掌握二分查找和索引查找算法
實驗原理
查找算法的實現(xiàn)
實驗環(huán)境（使用的軟件）
Visual?studio?2019
實驗方案設(shè)計
(1) 二分查找算法的實現(xiàn)
(2) 索引查找算法的實現(xiàn)
實驗過程
源.cpp
#include<iostream>
using namespace std;
typedef int keytype;
struct datatype
{
keytype key;
};
int BiSeach(datatype a[], int n, keytype key)
//在有序表a[0]--a[n-1]中二分查找關(guān)鍵碼為key的對象
//查找成功時返回該對象的下標(biāo)序號猫十；失敗時返回-1
{
int low = 0, high = n - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (a[mid].key == key) return mid;
else if (a[mid].key < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
typedef struct
{
keytype Key;
} elemtype;
typedef struct
{
keytype Key;
int Link;
} indextype;
int IndexSequelSearch(indextype ls[], elemtype s[], int m, int l, keytype Key)
/*分塊查找關(guān)鍵字為Key的記錄倒淫。索引表為ls[0]--ls[m-1], 順序表為s, 塊長為l*/
{
int i, j;
/*在索引表中順序查找*/
i = 0;
while (i < m && Key > ls[i].Key) i++;
if (i >= m) return -1;
else
{
/*在順序表中順序查找*/
j = ls[i].Link;
while (Key != s[j].Key && j - ls[i].Link < l)? j++;
if (Key == s[j].Key) return j;
else return -1;
}
}
int main()
{
datatype test[] = { 2,3,5,7,9,11,13,15,17,20 };
int n = 10, key = 11, i;
cout << "二分查找" << endl;
if ((i = BiSeach(test, n, key)) != -1)
cout << "查找成功! 該對象為第" << i << "個對象";
else? cout << "查找失敗! 該對象在對象集合中不存在";
cout << endl;
indextype ls[5] = { {14,0},{34,5},{66,10},{85,15},{100,20} };
elemtype Test[25] = { 8,14,6,9,10,22,34,18,19,31,40,38,54,66, 46,71,78,68,80,85,100,94,88,96,87 };
int m = 5, l = 6, Key = 87, u;
cout << "索引查找" << endl;
u = IndexSequelSearch(ls, Test, m, l, Key);
if (u != -1) cout << "查找成功窘行！該數(shù)據(jù)元素為第 %d 個記錄" << u << endl;
else cout << "n查找失旜晔邸汇荐！該數(shù)據(jù)元素在記錄集合中不存在" << endl;
return 0;
}
結(jié)論（結(jié)果）
