1 /*题目是：  2 输入一段文字，然后两个两个为前缀单词，后一个单词为后缀。保存起来。  3 然后输入前缀（两个单词），按前缀后缀表随机输出直到结尾。  4   5 思路就是建立哈希表 以两个单词（两个字符数组）为key值。  6 哈希的编码方式是用ASCII码的总和。  7  */  8 #include<stdio.h>  9 #include<stdlib.h> 10 #include<string.h> 11 #include<time.h> 12 /*全局数据成员*/ 13  14 typedef struct wordNode{//文字节点 15     char* thisWord; //此节点单词 16     struct wordNode* next; //指向下一个单词节点 17 }wordNode; 18  19 typedef struct hashNode{//哈希表节点 20     char* Key[2]; //key值 21     int hasHowMany; //有多少个后缀 22     wordNode* wordlist; //后缀链表 23 }hashNode; 24  25 const int MaxWordSize=45; //最大单词长度 26 const int StringSize=1000; //最大单词个数 27 const int oneWordSize=sizeof(char)*MaxWordSize; //一个单词的占内存大小 28 hashNode hashTable[StringSize]; //哈希表 29  30 /*函数声明*/ 31 void initializeHashTable(hashNode* hashTable);//初始化哈希表 32 int countHashCode(char** headTwoWord);//根据Key计算哈希值 33 bool creatHashNode(int hashCode,char* key1,char* key2,char* thisWord);//设置一个hash节点 34 wordNode* creatWordNode(char* word);//创造一个单词节点 35 char* findSuffixByPrefix(char* firstWord,char* secondWord);//根据前缀找后缀 36 bool FindIfTrueHashCode(char* firstWord,char* secondWord,int hashCode,char* Suffix);//寻找是否有空位 37  38 /*主函数*/ 39 void main(){ 40     srand((unsigned int)time(NULL)); //随机数种子 41     initializeHashTable(hashTable); //初始化哈希表 42      43     int hashCode=0;//哈希值 44     int tempHasHowMany=0;//hasHowMany的临时寄存值 45     wordNode* tempWordNode=NULL;//临时的文字节点 46     char charTemp[MaxWordSize]; //当前单词寄存 47     char charTemp_1[MaxWordSize]="";//单词寄存1 48     char charTemp_2[MaxWordSize]="";//单词寄存2 49     char* tempHaHa[2]; //计算哈希值用的临时字符串数组 50     printf("请输入一段文字,请以一个单独的(end)作为结尾(注意是圆括号):\n"); 51     while(1){ 52         scanf("%s",charTemp); 53         if(!strcmp(charTemp_1,"")) {strcpy(charTemp_1,charTemp);continue;}//低级错误，continue写成了break 54         if(!strcmp(charTemp_2,"")) {strcpy(charTemp_2,charTemp);continue;}//临时前两个单词 55         tempHaHa[0]=charTemp_1; 56         tempHaHa[1]=charTemp_2; 57         hashCode=countHashCode(tempHaHa); 58         while(!creatHashNode(hashCode,charTemp_1,charTemp_2,charTemp)) //创建哈希节点，被占位返回false就到下一位继续创建 59             hashCode++; 60         printf("前缀%s %s\t\t后缀:%s\n",charTemp_1,charTemp_2,charTemp); 61         strcpy(charTemp_1,charTemp_2); 62         strcpy(charTemp_2,charTemp);//将单词往后传递 63  64         if(!strcmp(charTemp,"(end)")) break; 65     } 66  67     char temp[MaxWordSize]; 68     while(1) 69     { 70         printf("\n请输入表中的两词前缀:"); 71         scanf("%s%s",charTemp_1,charTemp_2); 72         if(!(findSuffixByPrefix(charTemp_1,charTemp_2)==NULL)) break; 73         else printf("没有这个前缀请重新输入:"); 74     } 75     printf("%s %s ",charTemp_1,charTemp_2); 76     do{//不断往后添加单词直到(end) 77         strcpy(temp,findSuffixByPrefix(charTemp_1,charTemp_2)); 78         strcpy(charTemp,temp); 79         printf("%s ",charTemp); 80         strcpy(charTemp_1,charTemp_2); 81         strcpy(charTemp_2,charTemp); 82     }while(strcmp(charTemp,"(end)")); 83     printf("\n"); 84     system("pause"); 85 } 86 /*流程函数*/ 87 void initializeHashTable(hashNode* hashTable){ 88     for(int i=0;i<StringSize;i++){ 89         hashTable[i].wordlist=NULL; 90         hashTable[i].Key[0]=NULL; 91         hashTable[i].Key[1]=NULL; 92         hashTable[i].hasHowMany=0; 93     } 94 } 95  96 /*工具函数*/ 97  98 char* findSuffixByPrefix(char* firstWord,char* secondWord){ 99     char* temp[2];100     char Suffix[MaxWordSize];101     int tempHashCode=0;102     temp[0]=firstWord;103     temp[1]=secondWord;104     tempHashCode=countHashCode(temp);105     while(!FindIfTrueHashCode(firstWord,secondWord,tempHashCode,Suffix))106     {107         tempHashCode++;108         if(tempHashCode>999||hashTable[tempHashCode].Key[0]==NULL)109             return NULL;110     }111     return Suffix;112 }113 114 bool FindIfTrueHashCode(char* firstWord,char* secondWord,int hashCode,char* Suffix){115     int tempHasHowMany;116     int randomSuffix;117     wordNode* tempWordNode;118     if(hashTable[hashCode].Key[0]!=firstWord||hashTable[hashCode].Key[0]!=firstWord){119         return false;120     }121     else122     {123         tempHasHowMany=hashTable[hashCode].hasHowMany;124         randomSuffix=rand()%tempHasHowMany;125         tempWordNode=hashTable[hashCode].wordlist;126         for(int i=0;i<randomSuffix;i++)127             tempWordNode=tempWordNode->next;128         strcpy(Suffix,tempWordNode->thisWord);129         return true;130     }131 }132 133 134 int countHashCode(char** headTwoWord){135     int countASCII=0;136     int j=0;137     char* temp;138     temp=headTwoWord[0]; //低级错误，一开始写的1139     for(int i=0;i<2;i++){140         while((*temp)!=‘\0‘){141             countASCII+=*temp;142             temp++;143         }144         temp=headTwoWord[1];145     }146     return countASCII%997;147 }148 149 bool creatHashNode(int hashCode,char* key1,char* key2,char* thisWord){150     int tempHasHowMany=0;151     wordNode* tempWordNode=NULL;152     if(hashTable[hashCode].Key[0]==NULL){ 153         hashTable[hashCode].Key[0]=key1;154         hashTable[hashCode].Key[1]=key2;155         hashTable[hashCode].wordlist=creatWordNode(thisWord);156         hashTable[hashCode].hasHowMany++;157         return true;158     }159     else if(hashTable[hashCode].Key[0]==key1&&hashTable[hashCode].Key[1]==key2){160         tempHasHowMany=hashTable[hashCode].hasHowMany;161         tempWordNode=hashTable[hashCode].wordlist;162 163         for(int i=0;i<tempHasHowMany-1;i++)164             tempWordNode=tempWordNode->next;165         tempWordNode->next=creatWordNode(thisWord);166         hashTable[hashCode].hasHowMany++;//刚开始 忘记自增了;167         return true;168     }169     else return false;170 }171 172 wordNode* creatWordNode(char* word){173     wordNode* temp=NULL;174     temp=(wordNode *)malloc(sizeof(wordNode));175     temp->next=NULL;176     temp->thisWord=(char *)malloc(sizeof(char));//初级错误，开始直接让word赋值给thisWord了。结果值跟着变。177     strcpy(temp->thisWord,word);178     return temp;179 }