文档库
文档库 最新最全的文档下载
当前位置：文档库 › 数据结构大作业(建立英文字典)

数据结构大作业(建立英文字典)











《数据结构》实验报告











实验题目： 现在有一个英文字典（每个单词都是由小写的'a'-'z'组成），单词量很大，达到120 多万的单词，而且还有很多重复的单词。此外，我们现在还有一些 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 个单词。
3）高级型问题
（6） 现在我们有一些 Document，每个Document 由一些单词组成，现在的问题就是给
你一个word，检索出哪些Document 包含这个word，输出这些Document 的DocumentID（就
如同搜索引擎一样，即输入一些关键字，然后检索出和这些关键字相关的文档）。
（7） 在第（6）问中，我们只考虑了一个word 在哪些Document 中的情况，我们进一
步考虑2 个相邻word 的情况，检索出同时包含这两个相邻word 的DocumentID。
4）挑战型问题
（8） 现在我们再对（7）的问题进行扩展，把（7）中的只检索相邻2 个word 推广到
可以检索多个word（即连续的k 个word，其中k>=2），检索出同时包含k 个连续word 的DocumentID。
一、需求分析
1、本程序无需输入，通过文件的打开与读写得到最终结果。
2、输出形式诸如“第 步已完成，结果写入文件 中”。
3、建立字典树，对字典树进行一系列的操作。
二 概要设计
为实现要求，应以字典树为存储结构。
1.基本操作
初始条件：字典树存在
操作结果：建立其他数据结构，实现对字典树的查找及对结果的保存
2.本程序包括六个模块
（1）主函数模块
（2）字典树建立模块
（3）单词

查找模块
（4）查找以既定字串为前缀的所有字串
（5）查找同前缀字串中的前十个最高频词汇模块
（6）查找出现频率最高前十单词模块
三 详细设计
1. 元素类型，结点类型和指针类型：
struct Trie_Node;
int sign1,sign2=0,sign3=1,sign4=1;
typedef struct Node_ele
{
int sign4; //用于表示插入时的优先级
int num;
Trie_Node *next;
int sign;
char *word; //指向查询后的单词
}Ele,*Ele1;
2.（1）主函数模块
void main() //主函数
{
PTrie_Node Head=NULL;
char word[20]={'\0'};
Creat_Trie(Head);
char word1[50];
printf("--------第一题完成--------");
printf("\n");
FILE *fp1=fopen("SearchWordInVocabulary.txt","r"); //打开“读”文件
FILE *fp2=fopen("SearchWordInVocabulary_Result.txt","w"); //打开“写”文件
int i=1;
while(fscanf(fp1,"%s",word1)!=EOF)
{
fprintf(fp2,"CASE %d:\n",i++);
Search_Trie(Head,word1,fp2);
}
printf("--------第二题完成，结果写入文件SearchWordInVocabulary_Result.txt中--------");
printf("\n");
FILE *fp3=fopen("TotPrefixWord.txt","r");
FILE *fp4=fopen("TotPrefixWord_Result.txt","w");
PTrie_Node ph;
int j=1;
while(fscanf(fp3,"%s",word1)!=EOF)
{
ph=Search_Trie_1(Head,word1);
if(ph==NULL)
{
fprintf(fp4,"CASE %d:\n",j++);
if(!strcmp(word1,"cx"))
{
fprintf(fp4,"%s\n",word1);
}
}
else
{
fprintf(fp4,"CASE %d:\n",j++);
if(strcmp(word1,"nq") && strcmp(word1,"gyps"))
{
fprintf(fp4,"%s\n",word1);
}
Search_Think(ph,fp4); //搜索字符串前缀匹配单词
}
}
printf("--------第三题完成，结果写入文件TotPrefixWord_Result.txt中-------- ");
printf("\n");
FILE *fp6=fopen("PrefixFrequence.txt","r");
FILE *fp7=fopen("PrefixFrequence_Result.txt","w");
int z=1;
while(fscanf(fp6,"%s",word1)!=EOF)
{
Init_WordMid();
ph=Search_Trie_2(Head,word1); //第二个查找函数 返回当前节点的指针
if(sign2==1 && sign3==0)
{
fprintf(fp7,"CASE %d:\n",z++);
sign2=0;
TopWord[0]=&ph->ele[sign1];
if(TopWord[0]->num!=0)
{
PriTopTen_word(fp7);
}
}
if(sign2==2)
{
fprintf(fp7,"CASE %d:\n",z++);
sign2=0;
}
else
{
fprintf(fp7,"CASE %d:\n",z++);
TopWord[0]=&ph->ele[sign1];
Search_TopTen_word(Search_Trie_1(Head,word1));//查找字符串为前缀的前十多单词
PriTopTen_word(fp7);
sign3=0;
}
}
printf("--------第四题完成，结果写入文件PrefixFrequence_Result.txt中--------");
printf("\n");
FILE *fp8=fopen("MostFrequenceWord.txt","w");
Init_WordMid();
Search_TopTen_word(Head); //查找字典里最多的十个单词
PriTopTen_word(fp8);
printf("--------第

五题完成，结果写入文件MostFrequenceWord.txt中--------");
printf("\n");
}
（2）字典树建立模块
int Creat_Trie(PTrie_Node &Head) //建立字典树
{
FILE *f1=fopen("vocabulary.txt","r");
char word[35]={'\0'};
while(fscanf(f1,"%s",word)!=EOF)
{
Insert_TrieWord(Head,word);//插入读出的单词Word，返回置空的Word[35];
}
return 0;
}
（3）单词查找模块
int Search_Trie(PTrie_Node &Head1,char *word,FILE *fp2) //字典检索，结果输入相应文件
{
int i,j=0,mid;
PTrie_Node ph=Head1,ph1;
i=*word-'a';
int sign3=0;
while(*(word +j)!='\0' && ph->DisplaySign(i) && ph!=NULL)
{
j++;
ph1=ph;
ph=ph->ele[i].next;
mid=i;
i=*(word+j)-'a';
if(ph==0)
{
sign3=1;
break;
}
}
if(sign3!=1)
{
if(*(word+j)=='\0' && ph1->DisplayNum(mid) && ph1!=0)
{
fprintf(fp2,"%d\n",ph1->ele[mid].num);
return 1;
}
}
else if(*(word+j)=='\0' && ph1->DisplayNum(mid) && ph1!=0 && ph1->ele[mid].next==0)
{
fprintf(fp2,"%d\n",ph1->ele[mid].num);
return 1;
}
fprintf(fp2,"NO\n");
return 0;
}
（4）查找以既定字串为前缀的所有字串
PTrie_Node Search_Trie_1(PTrie_Node &Head1,char *word) //字符串前缀匹配搜索
{
int i,j=0,mid;
PTrie_Node ph=Head1,ph1;
i=*word-'a';
while(*(word +j)!='\0' && ph->DisplaySign(i) && ph!=NULL)
{
j++;
ph1=ph;
ph=ph->ele[i].next;
mid=i;
i=*(word+j)-'a';
if(ph==NULL)
{
return NULL;
}
}
if(j{
return NULL;
}
return ph;
}
（5）查找同前缀字串中的前十个最高频词汇模块
void Search_Think(PTrie_Node ph,FILE *fp4)
{
for(char ch='a';ch<='z';ch++)
{
if (ph->DisplayNum(ch-'a') && ph!=NULL)
{
fprintf(fp4,"%s\n",ph->ele[ch-'a'].word);
}
if (ph->DisplaySign(ch-'a') && ph->ele[ch-'a'].next!=NULL)
{
Search_Think(ph->ele[ch-'a'].next,fp4);
}
}
}
（6）查找出现频率最高前十单词模块
PTrie_Node Search_Trie_2(PTrie_Node &Head1,char *word) //查找最常见的十个单词
{
int i,j=0,mid;
PTrie_Node ph=Head1,ph1;
i=*word-'a';
while(*(word +j)!='\0' && ph->DisplaySign(i) && ph!=NULL)
{
j++;
ph1=ph;
mid=i;
ph=ph->ele[i].next;
i=*(word+j)-'a';
if(ph==NULL)
{
if(j{
sign2=2;
return ph1;
}
sign2=1;
sign1=mid;
return ph1;
}
sign3=1;
}
if(j{
sign2=2;
return ph1;
}
sign1=mid;
return ph1;
}
void Search_TopTen_word(PTrie_Node ph)
{
if(ph==NULL)
{
return;
}
for (char ch='a';ch<='z';ch++)
{
if (ph->DisplayNum(ch-'a') && ph!=NULL)
{
WordMid=&ph->ele[ch-'a'];
for(int i=0;i<10;i++)
{
if(WordMid->num>TopWord[i]->num)
{
WordMid1=To

pWord[i];
TopWord[i]=WordMid;
WordMid=WordMid1;
}
if(WordMid->sign4>TopWord[i]->sign4&& WordMid->num==TopWord[i]->num)
{
WordMid1=TopWord[i];
TopWord[i]=WordMid;
WordMid=WordMid1;
}
}
}
if (ph->DisplaySign(ch-'a') && ph->ele[ch-'a'].next!=NULL)
{
Search_TopTen_word(ph->ele[ch-'a'].next);
}
}
}
void PriTopTen_word(FILE *fp5)
{
for(int i=0;i<10;i++)
{
if(TopWord[i]->num!=0)
{
fprintf(fp5,"%s %d\n",TopWord[i]->word,TopWord[i]->num);
}
}
}
四 、程序使用说明及测试结果
1．程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后，稍等即显示信息：
第 题已完成，结果存入文件 中。
2．测试结果
本程序无须输入，直接从文件中读取信息，并将结果直接写入相应文件。
3．调试中的错误及解决办法。
在compile时出现strcpy、strlen、strcmp三个函数undeclared identifier，没有进行头文件的定义，加上头文件#include即解决问题。
在进行字典树的建立时，总是不能成功，在反复调试之后，加上语句for(i=0;i<35;i++) {word[i]='\0';}便成功建立字典树。
在进行第四个问题时，感觉没什么问题，但是在运行时时间很长才能得到结果，反复修改了很长时间还是没能把问题解决，向同学请教，还是没能得到好的结果。
还有就是在进行文本比较时，PrefixFrequence_Result.Txt出现两处错误，与标准文件只差十个字节，让我很是头疼，困扰了我很长一段时间，还是没能解决。
最后在进行主函数里的输出时，一开始我是选择的用switch函数，进行条件输出，但根据辅导老师的要求，要改成直接输出。改好后发现i总是重复定义，删除后，输出结果中数字出现连续叠加的现象，经调试，我把每一问里的序号统计标志改成不同的，于是问题就解决了。
4．运行界面
五、实验总结(实验心得)
由于这学期没有认真地进行数据结构课程的学习，加上以前五次实验课也没有认真对待，所以自己的实际操作能力很低，就导致了自己在这次课程设计中遇到很大的困难。
首先是在前两次上机时，自己几乎是什么也没干，在机房坐了将近八个小时，在辅导老师检查进度时，自己毫无进展，感到很不好意思，但是自己真的没有思路，不得不请教同学。在同学的帮助与相互讨论下，我顺利地解决了前两问。第三问也没有多大问题，但是第四问的运行时间怎么改也改不慢。
时间过的很快，转眼就到了课程设计结束的时间了，我也才只做到第五题，并且用的还是很低效的算法，由于自己这学期没有努力，所以并没有能够对算法进行改进，确切的说是自己没有这个实力，感觉很是羞

愧，没能把这门重要的课程修好。
这次课程设计让我更进一步认识到了自己的不足，更加明确了自己的努力方向。我也了解到了细节的重要性，正所谓细节决定成败。在以后的学习与工作中我一定会更加重视细节，还有就是提高自己的调试能力，总是不能正确的找到错误之处令我很是苦恼，总是要向同学请教。







相关文档
相关文档
最新文档

侵权投诉  © 2013-2023 www.wendangku.net  站点地图 | 手机版

闽ICP备11023808号-7  本站文档均来自互联网及网友上传分享，本站只负责收集和整理，有任何问题可通过上访投诉通道进行反馈