我编的程序如下
程序代码：
#include <dos.h>
#include <iostream>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 4 //哈希表的最大容量，与所采用的哈希函数有关
using namespace std;
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;
class H
{
public:
void ShowHash(HashTable H) //显示哈希表中的所有元素
{//显示哈希表所有元素及其所在位置
int i,j;
j=0;
for(i=0;i<MAXSIZE;i++) //显示哈希表中记录所在位置
if(H.elemflag[i]==HAVEKEY) //只显示标志为HAVEKEY(存放有记录)的元素
printf("%-4d",j++);
printf("\n");
for(i=0;i<MAXSIZE;i++) //显示哈希表中记录值
if(H.elemflag[i]==HAVEKEY)
printf("%-4d",H.elem[i]);
printf("\ncount:%d\n",H.count); //显示哈希表当前记录数
}
BOOL LookforHash(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; //查找不成功
}
hash(int kn) //哈希函数：H(key)=key MOD 11
{
return (kn%3);
}
void InitialHash(HashTable &H) //初始化哈希表 1111
{//哈希表初始化
int i;
H.count=0;
for(i=0;i<MAXSIZE;i++) H.elemflag[i]=NULLKEY;
}
BOOL InsertHash(HashTable &H,Record e)
{//查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回False
int p;
if(LookforHash(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(!LookforHash(H,e.keynum,p)) //表中不存在待删元素
return False;
else
{H.elemflag[p]=DELKEY; //设置标志为DELKEY，表明该元素已被删除
H.count--; //哈希表当前长度减一
return True;
}
}
};
void main()
{
H H1;
HashTable H; //声明哈希表H
char ch,j='y';
int position;
Record R;
BOOL temp;
//-------------------------程序说明-------------------------------
printf("这个程序将会展示怎样操作哈希表.\n");
printf("你可以输出，查找，插入，删除哈希表中的元素.\n");
//----------------------------------------------------------------
H1.InitialHash(H);
while(j!='n')
{
cout <<"1.输出\n"<<endl;
cout <<"2.查找\n"<<endl;
cout <<"3.插入\n"<<endl;
cout <<"4.删除\n"<<endl;
cout <<"5.退出\n"<<endl;
scanf(" %c",&ch); //输入操作选项
switch(ch)
{
case '1':if(H.count) H1.ShowHash(H); //哈希表不空
else cout <<"哈希表没有元素!"<<endl;
break;
case '2':if(!H.count) cout << "哈希表没有元素!" <<endl;//哈希表空
else {cout << "请输入关键字:" <<endl;
scanf("%d",&R.keynum); //输入待查记录的关键字
temp=H1.LookforHash(H,R.keynum,position);
//temp=True:记录查找成功；temp=False:没有找到待查记录
if(temp) cout << "元素的位置是:" <<position<<endl;//
}
break;
case '3':if(H.count==MAXSIZE) //哈希表已满
{cout << "哈希表已满!\n"<<endl;
break;
}
cout << "请输入要插入的元素:"<<endl;
scanf("%d",&R.keynum); //输入要插入的记录
temp=H1.InsertHash(H,R); //temp=True:记录插入成功temp=False:已存在关键字相同的记录
if(temp) cout << "插入成功!\n"<<endl;
else cout << "插入失败，已经存在相同的元素!\n"<<endl;
break;
case '4':cout << "请输入要删除元素的关键字:"<<endl;
scanf("%d",&R.keynum); //输入要删除记录的关键字
temp=H1.DeleteHash(H,R); //temp=True:记录删除成功temp=False:待删记录不存在
if(temp) cout << "元素删除成功!\n"<<endl;
else cout << "元素在哈希表中不存在!\n"<<endl;
break;
default: j='n';
}
}
cout << "程序结束!\n按任何键退出\n"<<endl;
getchar();
getchar();
}
2013-01-09 21:01
↖(^ω^)↗
