6.2.cpp

实现哈希表的建立,插入等功能,并用初留余数法构造,处理冲突

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define  maxsize       20
enum BOOL{FALSE,TRUR};
enum HAVEORNOT{NULLKEY,HAVEKEY};
typedef struct
{
	int elem[maxsize];
	HAVEORNOT elemflag[maxsize];
	int count;
}HashTable;
typedef struct
{
	int keynum;
}Record;
void InitHash(HashTable&);
void PrintHash(HashTable);
BOOL SearchHash(HashTable,int,int&);
BOOL InsertHash(HashTable&,Record);
int Hash(int);
void main()
{
	HashTable H;
	char ch,j='y';
	int position;
	Record R;
	BOOL temp;
	textbackground(3);
	textcolor(15);
	InitHash(H);
	while(j!='n')
	{
		cout<<"1.打印哈希表"<<endl;
		cout<<"2.查找人名"<<endl;
		cout<<"3.插入人名"<<endl;
		cout<<"4.退出"<<endl;
		cin>>ch;
		case'1':
			if(H.count)
				PrintHash(H);
			else
				cout<<"这个哈希表是空的."<<endl;
			break;
		case'2':
			if(!H.count)
				cout<<"这个哈希表是空的."<<endl;
			else
			{
				cout<<"请输入要查找的元素:";
				cin>>R.keynum;
				temp=SearchHash(H,R.keynum,positiom);
                if(temp)
					cout<<"这个元素的位置是:"<<position<<endl;
				else
					cout<<"这个元素不存在."<<endl;
			}
			break;
		case'3':
			if(H.count==maxsize)
			{
				cout<<"这个哈希表已满."<<endl;
				break;
			}
			cout<<"请输入要插入的元素内容:";
			cin>>R.keynum;
			temp=InsertHash(H,R);
			if(temp)
				cout<<"记录插入成功."<<endl;
			else
				cout<<"已存在关键字相同的记录."<<endl;
			break;
		default:
			j='\n';
	}
	cout<<"程序结束."<<endl;
	getchar();
	getchar();
}
void InitHash(HashTable &H)
{
	int i;
	H.count=0;
	for(i=0;i)


void PrintHash(HashTable H)
	{
		int i;
		for(i=0;iif(H.elemflag[i]==HAVEKEY)
			cout<<i;
		cout<<endl;
		for(i=0;iif(H.elemflag[i]==HAVEKEY)
			cout<<H.elem[i];
		cout<<"count:"<<count<<endl;   //显示哈希表当前记录数
	}
BOOL SearchHash(HashTable H,int k,int &p)
{
	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)
		return TRUE;
	else
		return FALSE;
}
BOOL InsertHash(HashTable &H,Record e)
{
	int p;
	if(SearchHash(H,e.keynum,p))
		return FALSE;
	else
	{
		H.elemflag[p]=HAVEKEY;
		H.elem[p]=e.keynum;
		H.count++;
		return TRUE;
	}
}
int Hash(int kn)
{
	return(kn%11);
}