/* 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");
	}
}

/*