哈希表的用户管理系统

三大模块：

- 哈希表模块

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

- 用户管理模块

显示
增
删
改
查

- 文件模块

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

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,
	//就会访问结构体信息，而此时结构体是NULL
	memset(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为空，说明找到的是第一个节点
	//否则，改变前一个节点的pNext
	if(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所在位置pos
	int 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，

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

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

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

这篇好文章是转载于：学新通技术网