listhash.c

该文件夹中包含了大部分经典的算法的源程序代码

/* file name: listhash.c */
/*哈希法：使用链地址法解决冲突*/

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

#define MAX_NUM 100  /*最大数据笔数*/
#define PRIME 97  /*MAX_NUM的质数*/
#define NOTEXISTED NULL
/*定义数据结构*/

typedef struct Person {
	long id;
	char name[21];
	struct Person *link;
} Student;

/*建立哈希链表*/
Student *Hashtab[MAX_NUM];
/*函数原形声明*/
long hashfun(long);
void insert();
void del();
Student *search(Student *,Student *);
void query();
void show();

void main()
{
	char *menu_prompt =
		"=== Hashing Table Program ==\n"
		"  1. Insert\n"
		"  2. Delete\n"
		"  3. Show\n"
		"  4. Search\n"
		"  5. Quit\n"
		"Please input a number : ";
	char menusele;
	int i;

	/*起始哈希链表，将各链表指向NULL*/
	for ( i = 0; i< MAX_NUM; i++)
		Hashtab[i] = NULL;

	do
	{
		printf("%s",menu_prompt);
		menusele = toupper(getche());
		puts("");
		switch (menusele)
		{
			case '1' :
				insert();
				break;
			case '2' :
				del();
				break;
			case '3' :
				show();
				break;
			case '4' :
				query();
				break;
			case '5' :
				puts("Bye Bye ^_^");
				break;
			default :
				puts("Invalid choice !!");
		}
	} while (menusele != '5' );
}

/*哈希函数 */
/*以除法运算求出记录应该存储的位置 */
long hashfun(long key)
{
	return ( key % PRIME );
}

void insert()
{
	Student  *newnode;
	long index;

	/*输入记录*/
	newnode = ( Student *)malloc(sizeof(Student));
	newnode->link = NULL;
	printf("Enter id : ");
	scanf("%ld",&newnode->id);
	printf("Enter Name : ");
	scanf("%s",newnode->name);

	/*利用哈希函数求得记录地址*/
	index = hashfun(newnode->id);
	/*判断该链表是否为空，若为空则建立链表*/
	if ( Hashtab[index] == NULL )
	{
		Hashtab[index] = newnode;
		printf("Node insert ok!\n");
	}
	else
	{
		/*查找节点是否在链表中，如未存在则将此节点加入链表首部*/
		if ((search(Hashtab[index],newnode)) == NOTEXISTED)
		{
			newnode->link = Hashtab[index];
			Hashtab[index] = newnode;
			printf("Node insert ok!\n");
		}
		else
			printf("Record existed...\n");
	}
}

/*