哈希表 开放地址法解决冲突的算法

[c++]代码库

#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#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;
	char ch,j='y';
	int position;
	Record R;
	BOOL temp;
	textbackground ( 3 );
	textcolor ( 15 );
	clrscr();
	printf ( "This program will show how to operate to a HashTable.\n" );
	printf ( "You can display all elems,search a elem,\ninsert a elem,delete a elem.\n" );
	InitialHash ( H );
	while ( j!='n' )
	{
		printf ( "1.display\n" );
		printf ( "2.search\n" );
		printf ( "3.insert\n" );
		printf ( "4.delete\n" );
		printf ( "5.exit\n" );
		scanf ( " %c",&ch );
		switch ( ch )
		{
		case '1':
			if ( H.count ) PrintHash ( H );
			else printf ( "The HashTable has no elem!\n" );
			break;
		case '2':
			if ( !H.count ) printf ( "The HashTable has no elem!\n" );
			else
			{
				printf ( "Please input the keynum(int) of the elem to search:" );
				scanf ( "%d",&R.keynum );
				temp=SearchHash ( H,R.keynum,position );
				if ( temp ) printf ( "The position of the elem is %d\n",position );
				else printf ( "The elem isn't exist!\n" );
			}
			break;
		case '3':
			if ( H.count==MAXSIZE )
			{
				printf ( "The HashTable is full!\n" );
				break;
			}
			printf ( "Please input the elem(int) to insert:" );
			scanf ( "%d",&R.keynum );
			temp=InsertHash ( H,R );

			if ( temp ) printf ( "Sucess to insert the elem!\n" );
			else printf ( "Fail to insert the elem.The same elem has been exist!\n" );
			break;
		case '4':
			printf ( "Please input the keynum of the elem(int) to delet:" );
			scanf ( "%d",&R.keynum );
			temp=DeleteHash ( H,R );

			if ( temp ) printf ( "Sucess to delete the elem!\n" );
			else printf ( "The elem isn't exist in the HashTable!\n" );
			break;
		default:
			j='n';
		}
	}
	printf ( "The program is over!\nPress any key to shut off the window!\n" );
	getchar();
	getchar();
}
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 )
			printf ( "%-4d",i );
	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 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;
	}
}
BOOL DeleteHash ( HashTable &H,Record e )
{
	int p;
	if ( !SearchHash ( H,e.keynum,p ) )
		return False;
	else
	{
		H.elemflag[p]=DELKEY;
		H.count--;
		return True;
	}
}
int Hash ( int kn )
{
	return ( kn%11 );
}