数据结构-散列表

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字对应一个存储位置。

采用自定义结构体存储用户的信息包括姓名、电话、住址。用户的电话号码作为该用户信息的关键字。代码如下：

#ifndef HASH_TABLE_H_
#define HASH_TABLE_H_

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

#define HASH_SIZE 12
#define NAME_SIZE 16
#define ADDRESS_SIZE 16

typedef struct{
	unsigned int tel;
	char name[NAME_SIZE];
	char address[ADDRESS_SIZE];
}person;

typedef struct{
	person elem[NAME_SIZE];
	int count;
}Hash,*Hash_Code;
 

void InitHashTable(Hash_Code h);
void SearchHash(Hash_Code h);
void Add_Person(Hash_Code h);
void Show_Person(Hash_Code h);
void Delet_Pereson(Hash_Code h);

#endif

1：初始化散列表：

//初始化散列表
void InitHashTable(Hash_Code h){
	h->count = 0;//用户个数初始化为0
	int i = 0;
	for (i = 0; i < HASH_SIZE; i++){
		h->elem[i].tel = 0;//把散列表中的用户电话均初始化为0
	}
}

2：添加用户，采用除模取余法为每个关键字找到对应的存储位置，当发生冲突时采用线性探测法为关键字继续寻找对应存储位置。代码如下：

//添加用户
void Add_Person(Hash_Code h){
	if (h->count == 12){
		printf("散列表已满，无法添加\n");
		return;
	}
	person p;
	printf("请输入用户电话号码：\n");
	scanf("%u", &p.tel);
	printf("请输入用户姓名：\n");
	scanf(" %s", p.name);
	printf("请输入用户住址:\n");
	scanf("%s", p.address);
	int addr = p.tel % HASH_SIZE;//除模取余法求存储位置
	while (h->elem[addr].tel != 0){//出现冲突
		addr = (addr + 1) % HASH_SIZE;//线性探测存储位置
	}
	if (h->elem[addr].tel == 0){
		h->elem[addr] = p;//添加联系人
		h->count++;
	}
}

2：查找用户，根据用户输入的电话号码继续采用除模取余法得到存储位置，访问该存储位置的用户信息的电话号码若不相同采用线性探测法为关键字继续寻找对应存储位置，当散列表中每个存储位置都访问后无与用户相匹配的信息则判断无该用户。代码如下：

//查找用户
void SearchHash(Hash_Code h){
	if (h->count == 0){
		printf("表为空，无法查找！\n");
		return;
	}
	printf("请输入要查找用户的电话号码：\n");
	unsigned int tele;
	scanf("%u", &tele);
	int addr = tele%HASH_SIZE;//除模取余法求存储位置
	int temp = addr;
	while (h->elem[addr].tel != tele){//出现冲突
		addr = (addr + 1) % HASH_SIZE;//线性探测存储位置
		if (addr == temp){//当遍历到起始存储位置，则表示整个散列表已全部遍历过
			printf("不存在该用户！\n");
			return;
		}
	}
	if (h->elem[addr].tel == tele){
		printf("用户姓名：%s\n", h->elem[addr].name);
		printf("用户电话：%u\n", h->elem[addr].tel);
		printf("用户住址：%s\n", h->elem[addr].address);
	}
}

3：显示全部用户信息：

//显示全部用户信息
void Show_Person(Hash_Code h){
	if (h->count == 0){
		printf("散列表为空！\n");
		return;
	}
	printf("共有%d个用户,用户信息如下：\n", h->count);
	int i = 0;
	for (i = 0; i < HASH_SIZE; i++){
		if (h->elem[i].tel != 0){
			printf("用户姓名：%s  ", h->elem[i].name);
			printf("用户电话：%u  ", h->elem[i].tel);
			printf("用户住址：%s  ", h->elem[i].address);
			printf("\n");
		}
	}
}

4：删除用户：

//删除用户
void Delet_Pereson(Hash_Code h){
    if (h->count == 0){
        printf("表为空！\n");
        return;
    }
    printf("请输入要删除用户的电话号码：\n");
    unsigned int tele;
    scanf("%u", &tele);
    int addr = tele%HASH_SIZE;//除模取余法求存储位置
    int temp = addr;
    while (h->elem[addr].tel != tele){//出现冲突
        addr = (addr + 1) % HASH_SIZE;//线性探测存储位置
        if (addr == temp){//当遍历到起始存储位置，则表示整个散列表已全部遍历过
            printf("不存在该用户！\n");
            return;
        }
    }
    if (h->elem[addr].tel == tele){
        h->elem[addr].tel = 0;
        h->count--;
    }
}

程序执行开始先将散列表中每个元素的关键字初识化为零，将添加联系人和查找联系人功能封装成函数体，每个函数体对应一个选项，将所有功能以索引的形式呈现给用户，当用户选择某一索引时，就执行当前索引对应的函数体。代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Hash_Table.h"
void Menue(){
	printf("______________\n");
	printf("1:添加用户\n");
	printf("2:查找用户\n");
	printf("3:显示全部用户信息\n");
	printf("4:删除用户\n");
	printf("0：退出\n");
}
int main(){
	Hash h;
	int num;
	InitHashTable(&h);
	int select = 0;
	int quit = 0;
	while (!quit){
		Menue();
		scanf("%d", &select);
		switch (select){
		case 1:
			Add_Person(&h);
			break;
		case 2:
			SearchHash(&h);
			break;
		case 3:
			Show_Person(&h);
			break;
		case 4:
			Delet_Pereson(&h);
			break;
		case 0:
			quit = 1;
			break;
		default:
			break;
		}
	}
	system("pause");
	return 0;
}