高分悬赏 求高手帮忙写一个数据结构的关于折半和哈希的查找程序 有急用

Question

一．设计目的
1.理解查找的基本算法
2.掌握静态查找和动态查找的区别
3.掌握折半查找和哈希查找的基本思想及其算法
二．设计内容和要求：
1.设计一个选择式菜单。
查找子系统
******************************************************
* 1 ……折半查找 *
* 2 ……哈希查找 *
* 0 ……返回 *
******************************************************
请选择菜单号（0…2）：
2.分别实现折半查找和哈希查找。
3.哈希函数采用除留余数法，解决冲突的方法任选。

程序要有清晰的语言注释

Answer 1

#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
/*在一个已知有序队列中找出与给定关键字相同的数的具体位置。
原理是分别定义三个指针low、high、mid分别指向待查元素所在范围的下界和上界以及区间的中间位置，
即mid＝（low＋high）/2，让关键字与mid所指的数比较，
若等则查找成功并返回mid，若
关键字小于mid所指的数则high=mid-1，否则low=mid+1，
然后继续循环直到找出或找不到为止。
*/
int bsearch(int array[], int left, int right, int target);

#define MAXSIZE 12 //哈希表的最大容量，与所采用的哈希函数有关
enum BOOL{False,True};
enum HAVEORNOT{NULLKEY,HAVEKEY,DELKEY};
//哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除
typedef struct //定义哈希表的结构
{int elem[MAXSIZE]; //数据元素体
HAVEORNOT elemflag[MAXSIZE]; //元素状态标志，没有记录、有记录、有过记录但已被删除
int count; //哈希表中当前元素的个数
}HashTable;
typedef struct
{int keynum; //记录的数据域，只有关键字一项
}Record;
void InitialHash(HashTable&); //初始化哈希表
void PrintHash(HashTable); //显示哈希表中的所有元素
BOOL SearchHash(HashTable,int,int&); //在哈希表中查找元素
BOOL InsertHash(HashTable&,Record); //在哈希表中插入元素
BOOL DeleteHash(HashTable&,Record); //在哈希表中删除元素
int Hash(int); //哈希函数
void main()
{
HashTable H; //声明哈希表H
InitialHash(H);

Record r; //hash 元素

int a[MAXSIZE]; //二分查找

for(int i=0;i<MAXSIZE;i++)
{
a[i]=i;
r.keynum =i;
InsertHash(H,r);
}

cout<<"******************************************************"<<endl;
cout<<"* 1 ……折半查找 *"<<endl;
cout<<"* 2 ……哈希查找 *"<<endl;
cout<<"* 0 ……返回 *"<<endl;
cout<<"******************************************************"<<endl;
int t,k;
int j;//j为要查找的元素
int n=MAXSIZE;
cin>>t;
switch(t)
{
case 1:
cout<<"输入查找的数"<<endl;
cin>>j;
k=bsearch(a, 0, n, j);
if(k!= -1) cout<<k<<endl;
else cout<<"数不在"<<endl;
break;
case 2:
cout<<"输入查找的数"<<endl;
cin>>j;
int p;
k=SearchHash(H,j,p);
if(p) cout<<k<<" "<<endl;
else cout<<"数不在"<<endl;
break;
default: exit(1);//退出我不理解回到子菜单含义，你自己也可以补充。
}

}
void InitialHash(HashTable &H)
{//哈希表初始化
int i;
H.count=0;
for(i=0;i<MAXSIZE;i++) H.elemflag[i]=NULLKEY;
}
void PrintHash(HashTable H)
{//显示哈希表所有元素及其所在位置
int i;
for(i=0;i<MAXSIZE;i++) //显示哈希表中记录所在位置
if(H.elemflag[i]==HAVEKEY) //只显示标志为HAVEKEY(存放有记录)的元素
cout<<i<<" ";
cout<<endl;;
for(i=0;i<MAXSIZE;i++) //显示哈希表中记录值
if(H.elemflag[i]==HAVEKEY)
cout<<H.elem[i]<<" ";
cout<<endl<<H.count;//显示哈希表当前记录数
/*
printf("%-4d",H.elem[i]);
printf("\ncount:%d\n",H.count);*/

}
BOOL SearchHash(HashTable H,int k,int &p)
{//在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示
//待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并
//返回False
int p1;
p1=p=Hash(k); //求得哈希地址
while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p])
//该位置中填有记录并且关键字不相等
{p++; //冲突处理方法：线性探测再散列
if(p>=MAXSIZE) p=p%MAXSIZE; //循环搜索
if(p==p1) return False; //整个表已搜索完，没有找到待查元素
}
if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY) //查找成功，p指示待查元素位置
return True;
else return False; //查找不成功
}
BOOL InsertHash(HashTable &H,Record e)
{//查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回False
int p;
if(SearchHash(H,e.keynum,p)) //表中已有与e有相同关键字的元素
return False;
else
{H.elemflag[p]=HAVEKEY; //设置标志为HAVEKEY，表示该位置已有记录
H.elem[p]=e.keynum; //插入记录
H.count++; //哈希表当前长度加一
return True;
}
}
BOOL DeleteHash(HashTable &H,Record e)
{//在查找成功时删除待删元素e，并返回True，否则返回False
int p;
if(!SearchHash(H,e.keynum,p)) //表中不存在待删元素
return False;
else
{H.elemflag[p]=DELKEY; //设置标志为DELKEY，表明该元素已被删除
H.count--; //哈希表当前长度减一
return True;
}
}
int Hash(int kn)
{//哈希函数：H(key)=key MOD 11
return (kn%11);
}

int bsearch(int array[], int left, int right, int target)
{
while (left <= right)
{
int mid = (left+right)/2;
if (array[mid] == target) return mid;
else if (array[mid] > target) right=mid-1;
else left=mid +1;
}
return -1;
}