#include <stdio.h>
#include <string.h>
#pragma warning(disable:4996)
#define N 20
#define Bool int
#define True 1
#define False 0
typedef struct AddressBook
{
char _name[N];
char _sex[2];
int _age;
char _number[20];
char _adress[100];
}AB;
typedef struct HashTable
{
const AB* *mTbl; // 哈希表
int mSize; // 表尺寸
int mStep; // 冲突后的步进值
int mCmpCount; // 查找是记录查找次数(题目要求的没其他用)
}HashTable;
void AddPerson();//1、添加联系人信息
void DeletePerson();//2、删除指定联系人信息
void FindPerson();//3、查找指定联系人信息
void ChangePerson();//4、修改指定联系人信息
void PrintfAllPerson();//5、显示所有联系人信息
void ClearAllPerson();//6、清空所有联系人
void SortPersonByName();//7、以名字排序所有联系人
void FindPerson_hash(HashTable* table);//9.哈希查找人
void AddPerson(struct AddressBook * p, int& cnt)
{
AB* pTemp = p;
int i = 0;
char name[N];
char sex[2];
int age;
char number[20];
char address[100];
//for(i =0;i<cnt;i++){
// pTemp++;
//}
printf("Please enter name:");
scanf("%s", name);
strcpy(pTemp[cnt]._name, name);
printf("Please enter sex:");
scanf("%s", sex);
strcpy(pTemp[cnt]._sex, sex);
printf("Please enter age:");
scanf("%d", &age);
pTemp[cnt]._age = age;
printf("Please enter number:");
scanf("%s", &number);
strcpy(pTemp[cnt]._number, number);
printf("Please enter address:");
scanf("%s", address);
strcpy(pTemp[cnt]._adress, address);
cnt++;
printf("储存成功！\n");
}
void DeletePerson(AB* p, int& cnt)
{
AB* pTemp = p;
char ptempname[20];
printf("请输入想要删除联系人的名字：\n");
scanf("%s", ptempname);
for (int i = 0; i < cnt; i++){
if (strcmp(pTemp[i]._name, ptempname) == 0){
printf("这是第%d个联系人：\n", i + 1);
printf("姓名：%s\n", p[i]._name);
printf("性别：%s\n", p[i]._sex);
printf("年纪：%d\n", p[i]._age);
printf("电话：%s\n", p[i]._number);
printf("住址：%s\n", p[i]._adress);
}
}
printf("请输入想要更改联系人的编号：\n");
int number = 0;
scanf("%d", &number);
strcpy(p[number - 1]._name, p[cnt - 1]._name);
strcpy(p[number - 1]._sex, p[cnt - 1]._sex);
p[number - 1]._age = p[cnt - 1]._age;
strcpy(p[number - 1]._number, p[cnt - 1]._number);
strcpy(p[number - 1]._adress, p[cnt - 1]._adress);
cnt--;
printf("修改成功");
}
void FindPerson(AB* p, int cnt)
{
int flag = 0;
AB* pTemp = p;
char name[10];
printf("请输入你想要查询联系人的名字：");
scanf("%s", &name);
for (int i = 0; i <= cnt; i++){
if (strcmp(pTemp[i]._name, name) == 0){
flag = 1;
printf("姓名：%s\n", p[i]._name);
printf("性别：%s\n", p[i]._sex);
printf("年纪：%d\n", p[i]._age);
printf("电话：%s\n", p[i]._number);
printf("住址：%s\n", p[i]._adress);
}
}
if (flag == 0){
printf("没有此联系人，请重新输入！\n");
}
}
void ChangePerson(AB* p, int cnt)
{
AB* pTemp = p;
char name[10];
printf("请输入你想修改联系人的名字：");
scanf("%s", &name);
for (int i = 0; i <= cnt; i++){
if (strcmp(pTemp[i]._name, name) == 0){
printf("这是第%d个联系人：\n", i + 1);
printf("姓名：%s\n", p[i]._name);
printf("性别：%s\n", p[i]._sex);
printf("年纪：%d\n", p[i]._age);
printf("电话：%s\n", p[i]._number);
printf("住址：%s\n", p[i]._adress);
}
}
int num;
printf("请输入你要修改的联系人编号：");
scanf("%d", &num);
char name2[N];
char sex[2];
int age;
char number[20];
char address[100];
printf("Please enter new name:");
scanf("%s", name2);
strcpy(pTemp[num - 1]._name, name2);
printf("Please enter new sex:");
scanf("%s", sex);
strcpy(pTemp[num - 1]._sex, sex);
printf("Please enter new age:");
scanf("%d", &age);
pTemp[num - 1]._age = age;
printf("Please enter new number:");
scanf("%s", &number);
strcpy(pTemp[num - 1]._number, number);
printf("Please enter new address:");
scanf("%s", address);
strcpy(pTemp[num - 1]._adress, address);
printf("修改成功！");
}
void PrintfAllPerson(AB* p, int cnt)
{
AB* pTemp = p;
int i = 0;
if (cnt == 0){
printf("空通讯录！\n");
return;
}
for (i = 0; i < cnt; i++){
printf("第%d个联系人：\n", i + 1);
printf("姓名：%s\n", pTemp[i]._name);
printf("性别：%s\n", pTemp[i]._sex);
printf("年纪：%d\n", pTemp[i]._age);
printf("电话：%s\n", pTemp[i]._number);
printf("住址：%s\n", pTemp[i]._adress);
}
}
void ClearAllPerson(AB*& p, int& cnt)
{
int i = 0;
AB* pTemp = p;
for (i = 0; i < cnt; i++){
strcpy(p[i]._adress, " ");
p[i]._age = 0;
strcpy(p[i]._name, " ");
strcpy(p[i]._number, " ");
strcpy(p[i]._sex, " ");
}
printf("通讯录已清空！\n");
cnt = 0;
}
void swap(char* a, char* p)
{
char newname[N];
strcpy(newname, a);
strcpy(a, p);
strcpy(p, newname);
}
void SortPersonByName(AB* p, int cnt)
{
AB* pTemp = p;
for (int i = 0; i < cnt; i++){
for (int j = i; j < cnt; j++){
if (strcmp(pTemp[i]._name, pTemp[j]._name) >= 0){
swap(pTemp[i]._name, pTemp[j]._name);
}
}
}
printf("排序成功！\n");
}
void GUI()
{
printf("***************************************************\n");
printf("* 1、添加联系人 2、删除联系人 *\n");
printf("* 3、查找联系人 4、修改联系人 *\n");
printf("* 5、显示联系人 6、清空联系人 *\n");
printf("* 7、排序联系人 0、退出 *\n");
printf("* 8、创建哈希表 9、哈希查找电话 *\n");
printf("***************************************************\n");
}
void dtor(HashTable *table);// 哈希表构造器
void ctor(HashTable *table, int tableSize, int step);// 哈希表析构器
Bool insert_more(HashTable* table, AB abTbl[], int cnt);// 插入一堆
Bool insert_one(HashTable* table, const AB* ab);// 插入一个
Bool delete_one(HashTable* table, const char number[]);// 删除一个
int find_one(HashTable* table, const char number[]);// 返回hash表中的下标, 没找到返回 -1
int main()
{
struct AddressBook s[1000];
HashTable ht; ctor(&ht, 20, 3);
GUI();
int select = 0;
int cnt = 0;
if (FILE* fp = fopen("txl.txt", "rb")){
fread(&cnt, 1, sizeof(cnt), fp);
fread(s, 1, sizeof(AB)*cnt, fp);
fclose(fp);
}
Bool bHashOk = False;
AB* pCur = s;
while (select != EOF){
printf("请输入您的选择：");
scanf("%d", &select);
switch (select){
case 1:
AddPerson(pCur, cnt);
GUI();
continue;
case 2:
DeletePerson(pCur, cnt);
continue;
case 3:
FindPerson(pCur, cnt);
GUI();
continue;
case 4:
ChangePerson(pCur, cnt);
GUI();
continue;
case 5:
PrintfAllPerson(pCur, cnt);
GUI();
continue;
case 6:
ClearAllPerson(pCur, cnt);
GUI();
continue;
case 7:
SortPersonByName(pCur, cnt);
GUI();
continue;
case 8:
if (bHashOk){ dtor(&ht); ctor(&ht, 20, 3); }
bHashOk = insert_more(&ht, pCur, cnt);
GUI();
continue;
case 9:
if (bHashOk){
FindPerson_hash(&ht);
GUI();
}
else{
printf("没有构建哈希表!\n");
}
continue;
case 0:
printf("success exit!\n");
break;
default:
printf("Error input,please input the right number\n");
continue;
}
break;
}
dtor(&ht);
if (FILE* fp = fopen("txl.txt", "wb")){
fwrite(&cnt, 1, sizeof(cnt), fp);
fwrite(s, 1, sizeof(AB)*cnt, fp);
fclose(fp);
}
return 0;
}
void FindPerson_hash(HashTable* table)
{
char number[10];
printf("请输入你想要查询联系人的电话：");
scanf("%s", &number);
int idx = find_one(table, number);
if (idx != -1){
const AB* p = table->mTbl[idx];
printf("姓名：%s\n", p[0]._name);
printf("性别：%s\n", p[0]._sex);
printf("年纪：%d\n", p[0]._age);
printf("电话：%s\n", p[0]._number);
printf("住址：%s\n", p[0]._adress);
}
else{
printf("没有此联系人，请重新输入！\n");
}
}
//-----------hash-----------
#include <stdlib.h>
void dtor(HashTable *table)
{
//for (int i = table->mSize; i--;){
// if (const AB* p = table->mTbl[i])
// free((char*)p);
//}
free(table->mTbl);
}
void ctor(HashTable *table, int tableSize, int step)
{
table->mStep = step;
table->mSize = tableSize;
table->mTbl = (const AB* *)malloc(sizeof(const AB*)*tableSize);
memset(table->mTbl, 0, sizeof(const AB*)*tableSize);
}
//int calcHash(const char *key)
//{
// unsigned int nr = 1u, nr2 = 4u;
// while (char ch = *key++){
// nr ^= (((nr & 63u) + nr2)*((unsigned int)ch)) + (nr << 8);
// nr2 += 3u;
// }
// return (int)nr;
//}
//字符串哈希值计算
int calcHash(const char* str, int mod)
{
int mix = 0;
while (char ch = *str++){
int num = 0;
if (' ' == ch) num = 113;
else if ('a' <= ch && ch <= 'z') num = (int)(ch - 'a');
else if ('A' <= ch && ch <= 'Z') num = (int)(ch - 'A') + 26;
else if ('0' <= ch && ch <= '9') num = (int)(ch - '0') + 52;
else return 0;
mix <<= 6;
mix |= num;
mix %= mod;
}
return mix;
}
// 插入一个元素
Bool insert_one(HashTable* table, const AB* ab)
{
//哈希值计算
int hash = calcHash(ab->_number, table->mSize);
int head = hash % table->mSize;
int i = head;
// 冲突解决式插入
do{
if (table->mTbl[i] < (const AB*)2)
i = (i + table->mStep) % table->mSize;
else{
table->mTbl[i] = ab;
return True;
}
} while (head != i);
return False;
}
// 返回hash表中的下标, 没找到返回 -1
int find_one(HashTable* table, const char number[])
{
table->mCmpCount = 0;
int hash = calcHash(number, table->mSize);
int head = hash % table->mSize;
int i = head;
while (table->mTbl[i]){
table->mCmpCount++;
if ((table->mTbl[i] != (const AB*)1) &&
(strcmp(number, table->mTbl[i]->_number) == 0))
return i;
i = (i + table->mStep) % table->mSize;
if (head != i) break;
}
return -1;
}
// 删除一个元素
Bool delete_one(HashTable* table, const char number[])
{
int idx = find_one(table, number);
if (idx != -1){ table->mTbl[idx] = (const AB*)1; } // 标志为僵尸节点
return (Bool)(idx != -1);
}
// 调节哈希表尺寸
Bool resize(HashTable* table, int mulK)
{
// 构造
HashTable ht;
ctor(&ht, table->mSize * mulK, table->mStep);
// 插入新表中去
for (int i = table->mSize; i--;){
if (table->mTbl[i] < (const AB*)2) continue;
if (insert_one(&ht, table->mTbl[i])) continue;
dtor(&ht); return False;
}
// 清楚旧表
memset(table->mTbl, 0, sizeof(const char*)*table->mSize);
dtor(table);
table->mSize = ht.mSize;
table->mTbl = ht.mTbl;
return True;
}
Bool insert_more(HashTable* table, AB abTbl[], int cnt)
{
for (int i = 0; i < cnt; ++i){
if (!insert_one(table, &abTbl[i])){
int tryCnt = 8, mulK = 1;
do{
if (!resize(table, mulK *= 2)) continue;
if (!insert_one(table, &abTbl[i])) continue;
break;
} while (--tryCnt);
if (0 == tryCnt){
printf("hash function too bad, replace one\n");
return False;
}
}
}
return True;
}