实验2 查找算法的实现和应用 实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. 实验内容 1. 用二分查找法对查找表进行查找； 2. 建立二叉排序树并对该树进行查找； 3. 确定hash函数及冲突处理方法，建立一个hash表并实现查找。 1.二分查找 #include using namespace std; #define INVALID_INDEX -100 int IntCompare(const int& a, const int& b, void* param) { return a - b; } template 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 <<"请输入元素的个数："<> length; int* aArray = new int[length]; cout<<"请输入要输入的元素："<> aArray[i]; } cout<<"要查找的元素："<> key&&key != 'F'){ index = BinarySearch(aArray, length, key, IntCompare, NULL); if (index == INVALID_INDEX) { cout << "The element is not exist." << endl; } else { cout << "The element position is " << index << "." << endl; } delete aArray; } return 0; } 2 二叉排序树 #include #include #include using namespace std; typedef int keyType; typedef struct Node { keyType key; struct Node* left; struct Node* right; struct Node* parent;...
