学步园

/*开散列表的插入、查找、删除算法的实现*/

#include <stdio.h>
#include <stdlib.h>

#define M 13  //表长定为13
typedef int KeyType;
typedef struct KeyNode {
	KeyType key;
	struct KeyNode *next;
}KeyNode;
KeyNode *HashTable[M];

//关键字查找函数
int HashSearch(KeyType k)
{
	int index = k%M;
	KeyNode *p;
	p = HashTable[index];
	while( NULL != p ) {
		if( k == p->key )
			return index;
		p = p->next;
	}
	return -1;
}

//关键字插入函数
void InsertHashTable( KeyType k )
{
	KeyNode *p, *q;
	int index = k%M;
	q = HashTable[index];
	if( -1 == HashSearch( k ) ) {
		p = (KeyNode *)malloc(sizeof(KeyNode));
		p->key = k;
		HashTable[index] = p;
		p->next = q;
	}
}

//创建Hash表函数
void CreateHashTable()
{
	int i;
	int k;
	for(i=0; i<M; i++)
		HashTable[i] = NULL;
	printf("请输入关键字(以-1结束输入):\n");
	scanf("%d", &k);
	while( -1 != k ) {
		InsertHashTable( k );
		scanf("%d", &k);
	}
}

//删除关键字函数
void DeleteKey( KeyType k )
{
	int index = HashSearch( k );
	if( -1 != index ) {
		KeyNode *p, *q;
		q = p = HashTable[index];
		while( k != p->key ) {
			q = p;
			p = p->next;
		}
		if( q == p )  //删除第一个结点
			HashTable[index] = p->next ;
		else
			q->next = p->next ;
		free(p);
	}
	else
		printf("无此关键字!");
}

//打印Hash表
void PrintHashTable()
{
	printf("当前的Hash表为:\n");
	KeyNode *p;
	for(int i=0; i<13; i++) {
		p = HashTable[i];
		printf("HashTable[%d]: ", i);
		while( NULL != p ) {
			printf("%d ", p->key );
			p = p->next ;
		}
		printf("\n");
	}
}

int main()
{
	KeyType k;
	CreateHashTable();
	PrintHashTable();

	printf("请输入要插入的关键字:\n");
	scanf("%d", &k);
	InsertHashTable( k );
	PrintHashTable();

	printf("请输入要删除的关键字:\n");
	scanf("%d", &k);
	DeleteKey( k );
	PrintHashTable();

	printf("请输入要查找的关键字:\n");
	scanf("%d", &k);
	if( -1 != HashSearch( k ) )
		printf("当前Hash表的位置%d处查找到该关键字!\n", HashSearch( k ));
	else 
		printf("无此关键字!\n");

	return 0;
}

测试数据以及测试结果