单词（词组）检索
现在有一个英文字典（每个单词都是由小写的'a'-'z'组成） ，单词量很大，达到 100 多万的单词，而且还有很多重复的单词。
此外，我们现在还有一些 Document，每个 Document 包含一些英语单词。
针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度
尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。
1）基本型问题
（1）选择合适的数据结构，将所有的英文单词生成一个字典 Dictionary。
（2）给定一个单词，判断这个单词是否在字典 Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出 NO扩展：
2）扩展型问题
（3）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T={a,aa, aaa, b, ba}, 如果你输入 a,那么输出应该为{a, aa, aaa}。
（4）给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出。
（5）输出 Dictionary 中出现次数最高的 10个单词。
程序所能达到的功能：
（1）建立字典树
（1）查找给定单词的出现频率
（3）输出以给定单词为前缀的所有单词
（4）及其中频率最高的十个单词
（5）全部单词里频率最高的十个单词
//一下圈记的都是得事先存入工程文件夹的tex文档
#include<stdio.h> #include<string.h> #include<malloc.h> #include<time.h> FILE *out;//设置全局变量，用于递归程序 FILE *f2; long num2=1; struct TrieNode { char c; char word[50]; struct TrieNode *next[26]; long count; }; typedef struct { char pl[50]; long mount; }PINLV; typedef PINLV pinlv[10]; pinlv b;//设置全局变量，用于递归程序 void chushihua(TrieNode *&p) { int i; (*p).c='#'; for(i=0;i<50;i++) p->word[i]=' '; //strcpy(p->word,"root"); for(i=0;i<26;i++) p->next[i]=NULL; p->count=0; } //建立字典树 struct TrieNode* JLTrieNode(TrieNode *root,char s[50]) { int i,j; struct TrieNode *q,*p; q=root; for(i=0;s[i]!=' ';i++) { if(q->next[s[i]-'a']!=NULL) q=q->next[s[i]-'a']; else { p=(struct TrieNode *)malloc(sizeof(struct TrieNode)); q->next[s[i]-'a']=p; p->c=s[i]; p->count=0;//初始化节点值 for(j=0;j<50;j++) p->word[j]=' '; for(j=0;j<26;j++) p->next[j]=NULL; q=q->next[s[i]-'a']; } } q->count++; strcpy(q->word,s); return root; } //(3)输出以单词***为前缀的所有单词**************3333333333333333333333 void digui3(struct TrieNode *q) { int i; struct TrieNode *p; for(i=0;i<26;i++) { p=q->next[i]; if(p!=NULL) { if((*p).count!=0) //*********** { //printf("%s ",(*p).word); //（若q为根节点，则可以用于遍历整个字典树） fprintf(f2,"%s ",(*p).word); } digui3(p); } } } //(4,5)递归遍历，获得频率最高的单词*********3333333333333333333333 void digui5(struct TrieNode *q, pinlv &a) { int i,j,k; struct TrieNode *p; for(i=0;i<26;i++) { p=q->next[i]; if(p!=NULL) { if((*p).count!=0) //*********** { //*****将频率最高的10个单词记录在a[j].pl中********444444444444444444444444*/ for(j=0;j<10;j++) { if((*p).count>=a[j].mount) { for(k=9;k>=j+1;k--) { strcpy(a[k].pl,a[k-1].pl); a[k].mount=a[k-1].mount; } strcpy(a[j].pl,(*p).word); a[j].mount=(*p).count; break; } } //********4444444444444444444444444444*555555555555555555555555********/ } digui5(p,a); } } } //查找单词的出现次数（频率） void chazhao2(struct TrieNode *root,char str[50]) { int i,j; struct TrieNode *q; q=root; for(i=0;str[i]!=' ';i++)//根据str在树中搜索：是否存在这个单词 { if(q->next[str[i]-'a']!=NULL) q=q->next[str[i]-'a']; else { fprintf(f2,"CASE %d: NO ",num2); break; } //如果单词还未遍历结束(str[i]!=' ')，就指向了NULL,说明该单词不在“文档”中(即不在字典树中) } if(str[i]==' ') { if(q->count!=0) fprintf(f2,"CASE %d: %d ",num2,q->count); else fprintf(f2,"CASE %d: NO ",num2); } } //(第3问)**输出以单词str[]为前缀的单词********* void chazhao3(struct TrieNode *root,char str[50]) { int i,j; struct TrieNode *q; q=root; for(i=0;str[i]!=' ';i++)//根据str在树中搜索：是否存在这个单词 { if(q->next[str[i]-'a']!=NULL) q=q->next[str[i]-'a']; else { break; } //如果单词还未遍历结束(str[i]!=' ')，就指向了NULL,说明该单词不在“文档”中(即不在字典树中) } if(str[i]==' ') { //printf("文档中以单词%s为前缀的单词有: ",str); if(q->count!=0) fprintf(f2,"%s ",(*q).word); digui3(q);//(3,4问)在递归程序中输出以单词str[]为前缀的所有单词，并且记录以单词str为前缀的频率最高的10个单词为单词于pinlv a中 } } //(第4问)输出以单词str为前缀的频率最高的10个单词为单词****************************************/ void chazhao4(struct TrieNode *root,char str[50]) { int i,j; pinlv a;//(第4问)************************** for(i=0;i<10;i++)//对字符数组pinlv a进行初始化(pinlv a中存放以***为前缀的频率最高的10个单词) { for(j=0;j<50;j++) a[i].pl[j]=' '; a[i].mount=0; } struct TrieNode *q; q=root; for(i=0;str[i]!=' ';i++)//根据str在树中搜索：是否存在这个单词 { if(q->next[str[i]-'a']!=NULL) q=q->next[str[i]-'a']; else break; //如果单词还未遍历结束(str[i]!=' ')，就指向了NULL,说明该单词不在“文档”中(即不在字典树中) } if(str[i]==' ') { strcpy(a[0].pl,(*q).word); a[0].mount=(*q).count; digui5(q,a);//在递归程序中输出以单词str[]为前缀的所有单词，并且记录以单词str为前缀的频率最高的10个单词为单词于pinlv a中 //printf(" 以单词%s为前缀的频率最高的10个单词为单词: ",str); for(i=0;i<10;i++) { if(a[i].mount!=0) { fprintf(f2,"%s ",a[i].pl); fprintf(f2,"%d ",a[i].mount); } } } } int main() { int i,k; FILE *fp; /***********************测试建树的时间***********************************/ double duration; clock_t start= clock();//******运行时间测试开始 //(第1问)建立字典树 struct TrieNode *root; char s[50]={' '}; fp=fopen("vocabulary.txt","r"); root=(struct TrieNode *)malloc(sizeof(struct TrieNode)); chushihua(root);//初始化头结点指针 while(!feof(fp))//从文档中换行读取数据 { fscanf(fp,"%s",s); root=JLTrieNode(root,s); }; fclose(fp); clock_t finish = clock();//*****运行时间测试结束 duration = (double)(finish-start);//CLOCKS_PER_SEC; printf( "建树时间为: %5.3f ms ",duration ); /**************************************************************************/ //(第2问)单词***的个数 char str[50]={' '};//存放要查找的单词 fp=fopen("(2)SearchWordInVocabulary.txt","r"); f2= fopen("(2)SearchWordInVocabulary_Result.txt","w"); while(!feof(fp))//从文档中换行读取数据 { fscanf(fp,"%s",str); chazhao2(root,str); for(i=0;i<50;i++) str[i]=' '; num2++; }; fclose(fp); fclose(f2); num2=1; //(第3问)以单词***为前缀的所有单词 fp=fopen("(3)TotPrefixWord.txt","r"); f2= fopen("(3)TotPrefixWord_Result.txt","w"); while(!feof(fp))//从文档中换行读取数据 { fscanf(fp,"%s",str); if(str[0]!=' ') { fprintf(f2,"CASE %d: ",num2); chazhao3(root,str); } for(i=0;i<50;i++) str[i]=' '; num2++; } fclose(fp); fclose(f2); num2=1; //(第4问)以单词***为前缀的单词的出现频率最高的10个单词 fp=fopen("(4)PrefixFrequence.txt","r"); f2= fopen("(4)PrefixFrequence_Result.txt","w"); while(!feof(fp))//从文档中换行读取数据 { fscanf(fp,"%s",str); if(str[0]!=' ') { fprintf(f2,"CASE %d: ",num2); chazhao4(root,str); } for(i=0;i<50;i++) str[i]=' '; num2++; } fclose(fp); fclose(f2); num2=1; //(第5问)在递归算法中将频率最高的10个单词记录在b[j].pl中 for(i=0;i<10;i++)//对字符数组pinlv b进行初始化(pinlv b 存放频率最高的十个单词及其频率) { for(k=0;k<50;k++) b[i].pl[k]=' '; b[i].mount=0; } digui5(root,b); //输出全部单词中频率最高的10个单词到文件中 fp=fopen("(5)MostFrequenceWord.txt","w"); for(i=0;i<10;i++) //fprintf(fp,"(%d)%-10s %d ",i,b[i].pl,b[i].mount); fprintf(fp,"%s %d ",b[i].pl,b[i].mount); fclose(fp); return 0; }