89.hash算法实现CSDN密码处理

 #define _CRT_SECURE_NO_WARNINGS
 #include <stdio.h>
 #include <stdlib.h>
 char path[] = "csdn.txt";
 //数据的行数
 #define N 6428633
 //字符串hash算法
 unsigned int BKDRHash(char *str); //hash链表结构体(结构体)
 struct   beitai
 {
     char *pstr;//存储字符串
     struct   beitai *pNext;//下一个节点
 }; //头结点
 struct info
 {
     struct   beitai *pbt;
 }; //保持所有头结点
 struct info *pall = NULL;

 //hasn算法
 unsigned int BKDRHash(char *str)
 {
     //和数据对应的位数有关
     unsigned int seed = ; // 31 131 1313 13131 131313 etc..
     unsigned int hash = ;     while (*str)
     {
         hash = hash * seed + (*str++);
     }     return (hash & 0x7FFFFFFF);
 }

 void changestr(char *str)
 {
     //备份地址
     char *pbak = str;
     //去除空格
     //下标
     int i = ;
     //游标
     int j = ;
     while ((str[i] = str[j++]) != '\0')
     {
         if (str[i] != ' ')
         {
             i++;
         }
     }
     //截断
     char *p1 = strstr(pbak, "#");
     if (p1 != NULL)
     {
         *p1 = '\0';
     }
 }

 void init()
 {     pall = malloc(N*sizeof(struct info));
     memset(pall, , N*sizeof(struct info));//清空     //打开文件
     FILE *pf = fopen(path, "r");
     for (int i = ; i < N; i++)
     {
         char str[] = {  };
         char strbak[] = {  };
         //读取一行
         fgets(str, , pf);
         //拷贝
         strcpy(strbak, str);
         //字符串处理
         changestr(str);
         //获取hash对应的数字
         unsigned int  data = BKDRHash(str);
         //进行取余
         unsigned int id = data %N;
         pall[id].pbt = addstr(pall[id].pbt, strbak);//找到链表节点，插入
     }
     fclose(pf);
 }

 //插入
 struct   beitai *addstr(struct   beitai *phead, char *str)
 {
     //开辟节点
     struct   beitai *pnew = calloc(, sizeof(struct   beitai));
     //获取字符串长度并开辟内存
     int length = strlen(str);
     pnew->pstr = calloc(length + , sizeof(char));
     //拷贝
     strcpy(pnew->pstr, str);
     //下一个结点为NULL
     pnew->pNext = NULL;
     //如果头结点为空
     if (phead==NULL)
     {
         phead = pnew;
     }
     //否则头部插入
     else
     {
         pnew->pNext = phead;
         phead = pnew;     }
     return phead;
 }

 //实现查询
 void find(struct   beitai *phead, char *findstr)
 {
     while (phead!=NULL)
     {
         char*ps = strstr(phead->pstr, findstr);
         if (ps!=NULL)
         {
             printf("%s", phead->pstr);//查找
         }
         phead = phead->pNext;
     }
 }

 int getN()
 {
     FILE *pf = fopen(path, "r");
     if (pf == NULL)
     {
         return -;
     }
     else
     {
         int i = ;
         while (!feof(pf))
         {
             char str[] = {  };
             fgets(str, , pf);//读取
             i++;
         }
         fclose(pf);
         return i;
     }
 }

 //主函数
 void main()
 {
     //初始化并载入内存
     init();
     //查询
     while ()
     {
         char str[] = {  };
         scanf("%s", str);
         unsigned int id = BKDRHash(str) % N;
         find(pall[id].pbt, str);
     }
     system("pause");
 }