/*闭散列表的建立、查找、插入、删除*/
#include <stdio.h>
#define NIL -1 //假设关键字为非负整数
#define DEL -2
typedef int KeyType;
KeyType HashTable[13]; //便于验证算法,关键字个数假定为不超过13,哈希表长定为13
//关键字插入函数
void InsertHashTable(KeyType k)
{
for(int i=0; i<13; i++)
if( NIL == HashTable[(k%13+i)%13] || DEL == HashTable[(k%13+i)%13] ) {
HashTable[(k%13+i)%13] = k;
break;
}
}
//哈希表的查找操作,查找成功则返回下表,否则返回-1
int HashSearch(KeyType k)
{
int i = 0;
while( i<13 ) {
if( k == HashTable[((k%13)+i)%13] )
return ((k%13)+i)%13;
else if( NIL == HashTable[((k%13)+i)%13] )
return -1;
i++;
}
if( 13 == i )
return -1;
}
//创建哈希表
void CreateHashTable()
{
int n;
KeyType key;
for(int i=0; i<13; i++)
HashTable[i] = NIL;
printf("请输入关键字的个数:\n");
scanf("%d", &n);
printf("请输入%d个关键字的值:\n", n);
for(i=0; i<n; i++) {
scanf("%d", &key);
if( -1 == HashSearch( key ) )
InsertHashTable( key );
}
}
//哈希表的删除操作
void DeleteHashTable(KeyType k)
{
int index = HashSearch( k );
if( -1 == index )
printf("无此关键字!\n");
else
HashTable[index] = DEL;
}
//打印哈希表
void PrintHashTable( void )
{
printf("当前哈希表存储的关键字为:\n");
for( int i=0; i<13; i++ )
printf("%d ", HashTable[i]);
printf("\n");
}
int main()
{
KeyType k;
CreateHashTable();
PrintHashTable();
printf("请输入要插入的关键字:\n");
scanf("%d", &k);
InsertHashTable( k );
PrintHashTable();
printf("请输入要删除的关键字:\n");
scanf("%d", &k);
DeleteHashTable( k );
PrintHashTable();
printf("请输入要查找的关键字:\n");
scanf("%d", &k);
if( -1 != HashSearch( k ) )
printf("当前表的位置%d处查找到该关键字!\n", HashSearch( k )+1);
else
printf("无此关键字!\n");
return 0;
}
测试数据以及测试结果