实验2 查找算法的实现和应用
q 实验目的
1. 熟练掌握静态查找表的查找方法；
2. 熟练掌握动态查找表的查找方法;
3. 掌握hash表的技术.
q 实验内容
1. 用二分查找法对查找表进行查找；
2. 建立二叉排序树并对该树进行查找；
3. 确定hash函数及冲突处理方法，建立一个hash表并实现查找。
1.二分查找
#include <iostream>
using namespace std;
#define INVALID_INDEX -100
int IntCompare(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, 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 <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
typedef int keyType;
typedef struct Node
{
keyType key;
struct Node* left;
struct Node* right;
struct Node* parent;
}Node,*PNode;
void inseart(PNode* root, keyType key)
{
PNode p = (PNode)malloc(sizeof(Node));
p -> key = key;
p -> left = p -> right = p -> parent = NULL;
if((*root) == NULL)
{
*root = p;
return ;
}
if((*root)->left == NULL && (*root)->key > key)
{
p->parent=(*root);
(*root)->left=p;
return;
}
if((*root)->right == NULL && (*root)->key < key)
{
p->parent=(*root);
(*root)->right=p;
return;
}
if((*root) -> key > key)
{
inseart(&(*root) -> left, key);
}
else if((*root) -> key < key)
{
inseart(&(*root) -> right, key);
}
else
return ;
}
PNode search(PNode root,keyType key)
{
if(root == NULL)
{
return NULL;
}
if(key > root -> key)
{
return search(root -> right, key);
}
else if(key < root -> key)
{
return search(root -> left, key);
}
else
return root;
}
void create(PNode* root, keyType* keyArray, int length)
{
int i;
for(i = 0; i < length; i++)
{
inseart(root, keyArray[i]);
}
}
int main()
{
int i;
PNode root = NULL;
int a[100];
int n;
scanf("%d",&n);
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
create(&root, a,n);
int m;
while(~scanf("%d",&m)){
if(search(root,m) ->key){
printf("YES\n");
}
}
return 0;
}
3 hash
#include <iostream>
//#include <ctime>
#include <iomanip>
using namespace std;
enum Result{
ok = 2,
success = 1,
unsuccess = 0,
duplicate = -1,
fail = -2,
};
typedef int elemtype;
typedef struct{
elemtype* elem;
int count;
int sizeindex;
}hashTable;
void Inithash(hashTable &H, int n){
H.elem = new elemtype[n];
H.count = 0;
H.sizeindex = n;
for(int i = 0; i < n; i++)
{
H.elem[i] = 0;
}
}
int hash(elemtype K, int sizeindex)
{
int count = H.count;
int haAddr = K % sizeindex;
return haAddr;
}
int SearchHash(hashTable &H, elemtype K, int &haAddr, int &c)
{
int d = 1;
int sizeindex = H.sizeindex;
haAddr = hash(K, sizeindex);
while(H.elem[haAddr] != NULL && H.elem[haAddr] != K)
{
haAddr = (K % sizeindex + d) % sizeindex;
d++;
c++;
cout<<"产生冲突，解决中…………"<<endl;
if(c > H.sizeindex - 2)
{
cout<<"冲突次数过多，重新建立哈希表"<<endl;
break;
}
}
if(K == H.elem[haAddr])
{
cout<<"chenggong"<<endl;
return success;
}
else
{
cout<<"fail"<<endl;
return unsuccess;
}
}
int InsertHash(hashTable &H, elemtype e)
{
int collision = 0;
int haAddr = -1;
if(SearchHash(H, e, haAddr, collision) == success)
{
cout<<"存在该元素！！！"<<endl;
return duplicate;
}
else if(collision < H.sizeindex - 2)
{
H.elem[haAddr] = e;
H.count++;
cout<<"插入成功！！！"<<endl;
return ok;
}
else
{
cout<<"冲突次数过多，重新建立哈希表"<<endl;
return fail;
}
}
int hashsearch(hashTable &H, elemtype e)
{
int p = 0;
for(int i = 0; i < H.sizeindex; i++)
{
if(H.elem[i] == e)
{
//H.elem[i] == 0;
p = 1;
cout <<"hashaddress = "<<i<<endl;
if(p == 0)
return unsuccess;
else
return success;
}
}
}
void PrintHash(hashTable H)
{
int num = 1;
cout<<"哈希表为……！"<<endl;
for(int i = 0; i < H.sizeindex; i++)
{
if(num % 10 == 0)
cout <<endl;
if(H.elem[i] != NULL)
{
cout <<setw(5)<<H.elem[i];
num++;
}
else continue;
}
cout <<endl;
}
void Performance(hashTable &H){
//hashTable H;
int sizeindex;
cout <<哈希表容量为……！<<endl;
cin >>sizeindex;
Inithash(H, sizeindex);
int e = 1;
cout<<"输入插入元素，否则输入＇０＇"<<endl;
cin >>ｅ;
while(e != 0)
{
InsertHash(H, e);
cout<<"输入插入元素，否则输入＇０＇"<<endl;
cin >>e;
}
PrintHash(H);
int k = 1;
cout<<"输入要查找元素：";
//int k;
cin>>k;
hashsearch(H,k);
int status = hashsearch(H,K);
if(!status)
cout<<"该元素不存在"<<endl;
}
int main()
{
hashTable H;
Performance(H);
cin.get();
cin.get();
return 0;
}
第二篇：数据结构实验指导(实验五：查找算法)
实验五 查找算法
实验项目：必做：顺序查找、折半查找
选做：二叉查找树
实验类型: 验证性
实验内容：
顺序查找：用数组或链表实现，数据有序或无序均可；
折半查找：必须用数组实现，且数据有序；
注意：提交的实验报告要显示已有的数据元素、待查找的数据；应包含查找成功、不成功的情况。