基于哈希表的用户管理系统

三大模块：

- 哈希表模块

哈希函数
哈希表创建
哈希表销毁

- 用户管理模块

显示
增
删
改
查

- 文件模块

从文件导入用户信息
将用户信息导出至文件

1.哈希函数

//hash函数（质数除余法）
int Hash_Fun1(data_type key){int pos = key%P;return pos;}

主要思想是将待哈希的数据转化为一个整数，
然后将该整数与一个质数进行取余运算，
最终得到的余数就是该数据的哈希值。
具体实现流程如下：

1. 定义一个质数p，通常取一个较大的质数，以尽量减少哈希冲突的概率。

2. 对于待哈希的数据，例如一个字符串，可以将其转化为一个整数，一般使用ASCII码的值或Unicode码的值等方式将字符串转换为整数。

3. 将该整数与质数p进行取余运算，得到的余数即为该数据的哈希值。

   优点：简单、计算速度快，适用于键值分布比较均匀的场景，
   但如果哈希表中数据分布不均匀，容易导致哈希冲突，影响哈希表的性能。

//改进质数取余法（字符串转为哈希值）
int Hash_Fun(char* str){int hash = 0;while(*str){hash = hash * 31 + (*str++);}return hash%HASH_SIZE;
}

遍历字符，将其ASCII码值乘以质数31，

再加上前面所有字符的哈希值，

最后再对哈希值进行取余运算，得到最终的哈希值。

---

使用质数31作为哈希函数的乘数

可以使得哈希函数更加均匀地分布哈希值，避免冲突的概率更小。

31是一个质数，它的二进制表示为0001 1111。

乘以31相当于将数值左移5位再减去原值，即x * 31 = (x << 5) - x。

因此，使用31作为乘数可以有效地减少乘法操作的计算量，同时还能够使得哈希值更加分散。

2.创建哈希表

//创建哈希表
Hash* Creat_Hash(void){//1.定义Hash表的头，存储哈希表首地址和尺寸Hash* pHash = (Hash*)malloc(sizeof(Hash));if(NULL == pHash){perror("malloc error");return NULL;}memset(pHash, 0, sizeof(Hash));//2.pHash的两个成员需分别赋值//arr是一个指向数组的指针，数组名也是数组首地址，所以是**//本身的数据类型是LinkNode**,指向LinkNode*pHash->arr = (LinkNode**)malloc(sizeof(LinkNode*)*HASH_SIZE);//此处要对空间初始化，否则显示时会段错误，因为只要非NULL,//就会访问结构体信息，而此时结构体是NULLmemset(pHash->arr, 0, sizeof(LinkNode*)*HASH_SIZE);if(NULL == pHash->arr){perror("malloc error");return NULL;}pHash->count = HASH_SIZE;return pHash;
}

首先，申请一片空间（Hash* pHash）用于存储哈希表所在位置的首地址，

以及定义变量（int count）存储哈希表中链表的个数。

而后，再申请一片连续的空间存储链表首结点的地址，

连续空间大小为HASH_SIZEsizeof( LinkNode )，

HASH_SIZE是存储链表的数量。

最后，给结构体中的count赋值为HASH_SIZE。

3.销毁哈希表

//销毁所有用户信息,传入哈希表首地址的地址
int Destroy_Hash(Hash** pHash){//1.判断入参空否if(NULL == *pHash){return NULL_ERROR;}//2.遍历哈希表int i = 0;for( i=0; i<HASH_SIZE; i++ ){LinkNode* pTemp = (*pHash)->arr[i];  //定义临时指针来遍历哈希表while(pTemp != NULL){LinkNode* pDel = pTemp;          //删除指针来删除pTemp = pTemp->pNext;            //头删法，先连free(pDel);                      //后释放}}free((*pHash)->arr);  //释放存储顺表地址的空间(*pHash)->arr = NULL; free(*pHash);         //释放哈希表*pHash = NULL;return OK;
}

哈希表申请了三次空间，

第一次是哈希表本身，

第二次是顺表的空间，

第三次是添加新用户时，申请新结点。

释放空间时，要确保申请每个空间都被释放了。

因此，对顺表遍历的同时，也要对后面的链表遍历。

由于顺表的大小是确定的，用for循环遍历，

而链表则用while，定义一个临时指针来遍历、释放。

执行完嵌套的循环遍历后，

最后释放pHash->arr和pHash。

4.显示用户信息

//显示哈希表
int Display_Hash (Hash* pHash){//1.入参是否存在if(NULL == pHash){return NULL_ERROR;}//2.遍历显示printf("**************用户信息****************\n");int i = 0, j=1;for( i=0; i<HASH_SIZE; i++ ){LinkNode* pNode = pHash->arr[i];while(pNode != NULL){if( pNode->data.name!=NULL && pNode->data.password && pNode->data.mail){printf("用户%d:%s\t  密码:%s\t邮箱:%s\n", j++, \pNode->data.name, pNode->data.password, \pNode->data.mail);pNode = pNode->pNext;}}}printf("显示完毕！\n");return OK;
}

5.增加用户信息

//插入哈希表
int Insert_Hash(Hash* pHash, User_Inf item){//1.判断Hash表是否存在if(NULL == pHash){return NULL_ERROR;}//2.查找hash,若存在，返回无需插入if(Search_Hash(pHash, item.name) != NULL){printf("已存在，无需插入！\n");return NULL_ERROR;}//3.创建新节点pNew,并存入数据LinkNode* pNew = (LinkNode*)malloc(sizeof(LinkNode));if(NULL == pNew){perror("malloc error");return MALLOC_ERROR;}memset(pNew, 0, sizeof(LinkNode));pNew->data = item;//结构体可以直接赋值？//4.通过hash函数获得要存入的位置int pos = -1;pos = Hash_Fun(item.name);//5.将新节点，以头插方式插入hash表pNew->pNext = pHash->arr[pos];pHash->arr[pos] = pNew;return OK;
}

首先，调用查找函数，如果找到了，说明链表中有该用户，无需添加；

如果没有，则创建新结点，将用户信息存入后，

调用哈希函数获取存入的位置，采用头插法添加用户信息。

6.删除用户信息

//删除哈希表
int Del_Hash(Hash* pHash, char* user_name){//1.判断入参空否if(NULL == pHash){return NULL_ERROR;}//2.获得哈希值int pos = Hash_Fun(user_name);//3.遍历该位置上的链表LinkNode* pDel = pHash->arr[pos];//删除指针指向第一个结点LinkNode* pPre = NULL;//前继指针指向第二while(pDel != NULL ){if( 0 == strcmp(pDel->data.name, user_name) ){break;}pPre = pDel;pDel = pDel->pNext;}//4.若pDel为空，则要删除的不存在if(NULL == pDel){return NULL_ERROR;}//5.若pPre为空，说明找到的是第一个节点//否则，改变前一个节点的pNextif(NULL == pPre){pHash->arr[pos] = pDel->pNext;}else{pPre->pNext = pDel->pNext;}//打印删除结点信息printf("删除的是：\n");printf("用户名：%s\t密码：%s\t邮箱：%s\n", \pDel->data.name, pDel->data.password, pDel->data.mail);//6.释放结点free(pDel);pDel = NULL;return OK;
}

首先，定义两个指针，

LinkNode* pDel指向链表首节点，也就是pHash->arr[pos]中的地址（可能为NULL），

LinkNode* pPre是前驱结点，初始化为NULL。

而后，利用这两个指针对链表进行遍历：

从首结点开始strcmp需要的用户名，如果找到就跳出循环，

否则两个指针依次向后移动。

跳出循环有三种情况：

1. pDel为空，也就是没有该用户，退出程序。
2. 哈希值位置的第一个节点就是，pPre没有移动，还是NULL，此时用头删法进行删除操作，即顺序表中元素指向找到节点的下一节点（可能为空），再free。
3. 哈希值位置的链表有N个节点，在链表中间，或最后找到了，此时pDel指向的是需要删除的用户。先将pPre指向pDel后的结点，再free(pDel)，是最后一个结点也不影响

7.修改用户信息

//修改用户信息
int Modify_Hash(Hash* pHash, char* Name){//1.判断入参空否if(NULL == pHash || NULL == Name){return NULL_ERROR;}//2.获取哈希值int pos = Hash_Fun(Name);//3.通过顺序表找到用户LinkNode* pTemp = pHash->arr[pos];while(pTemp != NULL){if( 0 == strcmp(pTemp->data.name, Name) ){printf("该用户信息如下：\n");printf("%s ", pTemp->data.name);printf("%s ", pTemp->data.password);printf("%s ", pTemp->data.mail);//	Del_Hash(pHash, pTemp->data.name);printf("\n输入新的用户信息\n");scanf("%s", pTemp->data.name);scanf("%s", pTemp->data.password);scanf("%s", pTemp->data.mail);//更改信息后，要将新的用户信息放到对应位置，并删除就结点，否则显示还会显示//	Insert_Hash(pHash, pTemp->data);return OK;}pTemp = pTemp->pNext;}//4.若pTemp为空，则未找到该用户if(NULL == pTemp){return EMPTY;}return -1;
}

首先，调用哈希函数获取存储该用户信息的位置，

而后定义一个临时指针用于遍历链表，

如果找到，提示输入新信息；

如果没找到，指针向后移动；

直到指向NULL，说明没有该用户。

8.查找某用户

//查找哈希表
LinkNode* Search_Hash(Hash* pHash, char* user_name){//1.判断hash表是否存在if(NULL == pHash){return NULL;}//2.通过hash函数获得user_name所在位置posint pos = Hash_Fun(user_name);//3.通过pos获得链表中的首地址LinkNode* pTemp = pHash->arr[pos];//4.遍历链表至找到该值while(pTemp != NULL){if( 0 == strcmp(user_name, pTemp->data.name)   {return pTemp;}pTemp = pTemp->pNext;}return NULL;
}

首先，调用哈希函数获取存储该用户信息的位置，

而后定义一个临时指针用于遍历链表，

如果找到，返回该指针；

如果没找到，指针向后移动；

直到指向NULL，说明没有该用户。

9.导出用户信息

//导出信息
int Output_Data(Hash* pHash, char* filename){//1.判断入参空否if(NULL == pHash || NULL == filename){return NULL_ERROR;}//2.打开文件FILE* fp = fopen(filename, "w");if(NULL == fp){perror("open error");return NULL_ERROR;}//3.遍历哈希表，存入信息int i = 0;for( i=0; i<HASH_SIZE; i++){LinkNode* pTemp = pHash->arr[i];while(pTemp != NULL){User_Inf user = pTemp->data;fprintf(fp, "用户名:%s  密码:%s   邮箱:%s\n", \user.name, user.password, user.mail);pTemp = pTemp->pNext;}}fclose(fp);return OK;
}

遍历整个哈希表，将其中的信息输出至指定文件中，

首先以只写方式打开指定文件，

如果不存在就创建一个，

每次写入信息时，清空上次的内容。

遍历每个结点时，调用fprintf函数将该名用户的信息输出至文件中，

末尾加上”\n”，最后关闭文件。

10.导入用户信息

//导入信息
int Input_Data(Hash* pHash, char* filename){//1.判断入参空否if(NULL == pHash || NULL == filename){return NULL_ERROR;}//2.打开文件FILE* fp = fopen(filename, "r");if(NULL == fp){perror("open error");return OPEN_ERROR;}//3.读取文件信息，文件中每行一个用户，信息间用空格隔开int MAX = 70;char Line[MAX];//缓冲区：存储按行读的信息while( fgets(Line, MAX, fp)){//从文件读取不为空,就一直取char Name[N];char Password[N];char Mail[N];//如果解析不出３个字符串，结束本次循环，继续下一次if( sscanf(Line, "%s %s %s",Name, Password, Mail) != 3){continue;}User_Inf user;strcpy(user.name, Name);strcpy(user.password, Password);strcpy(user.mail, Mail);//4.插入信息int ret = Insert_Hash(pHash, user);if(OK != ret){fclose(fp);return ret;}}fclose(fp);return OK;
}

首先，打开一个文件，调用fgets函数按行读取文件内容，

再调用sscanf将读取到的每行内容解析为三个字符串，

分别为name, password, mail，

并赋值给一个定义的结构体，

而后，调用增加用户函数将结构体信息添加到哈希表中，

如果插入错误就关闭文件。