基于哈希表的简单联系人查询系统

基于散列表数据结构，采用二次再散列的方法解决冲突，编写的联系人存储系统

HashTable

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 20
#define OK 1
#define FALSE 0

//定义存储个人信息的结构体 
typedef struct{
	char name[20];	//姓名 
	char phone[20];	//电话 
	char location[30];	//地址 
}Person;

//定义散列表HashTable
typedef struct{
	Person* array[MAXSIZE];	//存储联系人的动态数组 
	int count;		//当前表中元素总个数 
}HashTable; 

//将电话号码处理为key 
int GetKey(char phone[]){
	//将电话号码的每一位数字加起来即为key
	int key=0;
	int i=0;
	while(phone[i] != '\0') {
		key += phone[i]-'0';
		i++;
	}
//	printf("key = %d\n",key);
	return key;
} 
//散列函数 传入key返回存储的位置l=Hash(key) 
int Hash(int key){
	return key%19;	//采用除留余数法,由于表长为20,除数一般为小于或等于表长的最大质数，所以这里为19 
} 

//初始化散列表
HashTable* InitHashTable(){
	HashTable *hashTable = NULL;
	hashTable = (HashTable*)malloc(sizeof(HashTable));
	hashTable->count = 0;	//初始化时hash表中没有元素 
	int i;
	for(i=0;i<MAXSIZE;i++){
		hashTable->array[i] = NULL; //为每个位置的电话初始化为-1
	}
} 
//int Save()
//int HandleCollision(HashTable *hashTable,Person person,int loc){
//	
//}
//插入数据
int Insert(HashTable *hashTable,Person *person){
	int key = GetKey(person->phone);
	int loc = Hash(key);//获取在hash表中的位置
	 
	if(hashTable->array[loc] == NULL){
		//如果该位置为空，就将联系人存储到此处
		hashTable->array[loc] =  person;
		hashTable->count++;
		return OK;
	}else{
		//如果该位置不为空，则出现散列表冲突，采用二次探测再散列方式处理
		int j=1;
		int k=0;
		while(1){
			int newLoc = -1;
			if(k%2 == 0){
				newLoc = loc + j*j;
				k++;
			}else{
				newLoc = loc - j*j;
				j++;
				k++;
				if(newLoc < 0){
					//相减时要考虑负数，负数无法取模 
					continue;
				}
			}
			if(newLoc>MAXSIZE){
				//数组越界
				return FALSE; 
			}
			if(hashTable->array[newLoc] == NULL){
				//如果该位置为空，就将联系人存储到此处
				hashTable->array[newLoc] =  person;
				hashTable->count++;
				return OK;
			}
		}
	}	
} 

//查找数据
Person* Find(HashTable *hashTable,char phone[]){
	int loc = Hash(GetKey(phone));//获取在hash表中的位置
	if(hashTable->array[loc] == NULL){
		return NULL;
	} 
	if(!strcmp(hashTable->array[loc]->phone,phone)){
		//如果该位置的值等于查询的值，就将联系人返回 
		return hashTable->array[loc]; 
	}else{
		//出现散列表冲突，采用二次探测再散列方式处理
		int j=1;
		int k=0;
		while(1){
			int newLoc = -1;
			if(k%2 == 0){
				newLoc = loc + j*j;
				k++;
			}else{
				newLoc = loc - j*j;
				j++;
				k++;
				if(newLoc < 0){
					//相减时要考虑负数，负数无法取模 
					continue;
				}
			}
			if(newLoc>MAXSIZE || hashTable->array[newLoc] == NULL){
				//未找到联系人 
				return NULL;
			}
			
			if(!strcmp(hashTable->array[newLoc]->phone,phone)){
				//如果该位置的值等于查询的值，就将联系人返回 
				return hashTable->array[newLoc]; 
			}
		}
	}
}

//展示所有联系人,由于数组写死，所以最大存储为MAXSIZE，可自行升级为动态数组 
void ShowAll(HashTable *hashTable){
	if(hashTable){
		int i;
		printf("一共有%d条记录:\n",hashTable->count);
		for(i=0;i<MAXSIZE;i++){
			if(hashTable->array[i] != NULL){
				printf("姓名：%s\t电话：%s\t地址：%s\t\n",hashTable->array[i]->name,hashTable->array[i]->phone,hashTable->array[i]->location);
			}
		}
		printf("加载完毕！");
		system("pause");
	}else{
		printf("请先建立联系簙！");
		system("pause"); 
	}
}

void menu(){
  
  printf("\n请选择操作");
  printf("\n========================================");
  printf("\n|          1--建立联系簙               |");
  printf("\n|          2--添加联系人               |");
  printf("\n|          3--查找联系人               |");
  printf("\n|          4--显示所以联系人           |");
  printf("\n|          0--退出                     |");
  printf("\n========================================");
  printf("\n请输入菜单号(0-4)：");
} 

void main(){
	HashTable *hashTable = NULL;
	while(1){ 
		menu(); 
		int i; 
		scanf("%d",&i);
		if(i == 1){
			hashTable = InitHashTable();
			printf("建立成功！");
			system("pause");
		}else if(i == 2){
			if(hashTable == NULL){
				printf("请先建立联系簙！");
				system("pause"); 
				continue;
			}
			Person *p = NULL;
			p = (Person*)malloc(sizeof(Person));
			printf("输入电话号码："); 
			scanf("%s",p->phone);
			printf("输入姓名：");
			scanf("%s",p->name);
			printf("输入地址：");
			scanf("%s",p->location);
			
			Insert(hashTable,p);
			printf("添加成功!\n");
			printf("姓名：%s\t电话：%s\t地址：%s\t\n",p->name,p->phone,p->location);
			system("pause"); 
		} else if(i == 3){
			if(hashTable == NULL){
				printf("请先建立联系簙！");
				system("pause"); 
				continue;
			}
			char phone[20];
			printf("输入待查找号码：");
			scanf("%s",phone); 
			Person *findPerson = Find(hashTable,phone); 
			if(findPerson){
				printf("查询成功:\n"); 
				printf("姓名：%s\t电话：%s\t地址：%s\t\n",findPerson->name,findPerson->phone,findPerson->location);
				system("pause");
			}else{
				printf("未查询到该联系人！");
				system("pause");
			}
		  	
		}else if(i == 4){
			ShowAll(hashTable);
		}else if(i == 0){ 
		  	printf("成功退出系统！"); 
		  	break; 
		} else{
		   printf("指令错误！");
		   system("pause");
		}
	}
	return;
}