数据结构实验2查找算法的实现与应用.docx

实验2 查找算法的实现和应用
实验目的
1. 熟练掌握静态查找表的查找方法;
2. 熟练掌握动态查找表的查找方法;
3. 掌握hash表的技术.
实验内容
用二分查找法对查找表进行查找;
建立二叉排序树并对该树进行查找;
确定hash函数及冲突处理方法,建立一个hash表并实现查找。

#include <iostream>
using namespace std;
#define INVALID_INDEX -100
int pare(const int& a, const int& b, void* param)
{
return a - b;
}
template<class T1, class T2>
int BinarySearch(const T1* theArray, int length, const T2& key, int (*compare)(const T1&, const T2&, void* param), void *param)
{
int indexRet = INVALID_INDEX;
int mid = length / 2;
int cmp = compare(theArray[mid], key, param);
if (cmp == 0)
{
indexRet = mid;
}
else if (length != 1)
{
if (cmp < 0 && length != 1)
{
indexRet = BinarySearch(theArray + mid, length - mid, key, compare,param);
if (indexRet != INVALID_INDEX)
{
indexRet += mid;
}
}
else
{
indexRet = BinarySearch(theArray, mid, key, compare, param);
}
}
return indexRet;
}
int main()
{
int length = 0;
int i = 0;
int key = 0;
int index = INVALID_INDEX;
cout <<"请输入元素的个数:"<<endl;
cin >> length;
int* aArray = new int[length];
cout<<"请输入要输入的元素:"<<endl;
for (i = 0; i < length; i++)
{
cin >> aArray[i];
}
cout<<"要查找的元素:"<<endl;
while(cin >> key&&key != 'F'){
index = BinarySearch(aArray, length, key, pare, NULL);
if (index == INVALID_INDEX)
{
cout << "The element is not exist." << endl;
}
else
{
cout << "The e