数据结构课程设计最终报告.doc

数据结构实验报告实验题目： 现在有一个英文字典（每个单词都是由小写的a-z组成），单词量很大，达到120 多万的单词，而且还有很多重复的单词。此外，我们现在还有一些 Document，每个Document 包含一些英语单词。针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。实验目的：在本次课程设计中，希望同学们根据自己所学的知识，查找相关的资料，构造合适的数据结构，尽自己最大的努力解决这些问题，从而使自己学到更多新的知识。实验内容：1）基本型问题（1） 选择合适的数据结构，将所有的英文单词生成一个字典 Dictionary。（2） 给定一个单词，判断这个单词是否在字典 Dictionary 中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO2）扩展型问题（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_eleint sign4; /用于表示插入时的优先级int num;Trie_Node *next; int sign;char *word; /指向查询后的单词Ele,*Ele1;2.（1）主函数模块void main() /主函数PTrie_Node Head=NULL;char word20=0; Creat_Trie(Head);char word150;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,%sn,word1);elsefprintf(fp4,CASE %d:n,j+);if(strcmp(word1,nq) & strcmp(word1,gyps)fprintf(fp4,%sn,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;TopWord0=&ph-elesign1;if(TopWord0-num!=0)PriTopTen_word(fp7);if(sign2=2)fprintf(fp7,CASE %d:n,z+);sign2=0;elsefprintf(fp7,CASE %d:n,z+);TopWord0=&ph-elesign1;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 word35=0;while(fscanf(f1,%s,word)!=EOF)Insert_TrieWord(Head,word);/插入读出的单词Word，返回置空的Word35;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-elei.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,%dn,ph1-elemid.num);return 1;else if(*(word+j)=0 & ph1-DisplayNum(mid) & ph1!=0 & ph1-elemid.next=0)fprintf(fp2,%dn,ph1-elemid.num);return 1; fprintf(fp2,NOn); 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-elei.next;mid=i;i=*(word+j)-a;if(ph=NULL)return NULL;if(jstrlen(word)return NULL;return ph;（5）查找同前缀字串中的前十个最高频词汇模块void Search_Think(PTrie_Node ph,FILE *fp4)for(char ch=a;chDisplayNum(ch-a) & ph!=NULL)fprintf(fp4,%sn,ph-elech-a.word);if (ph-DisplaySign(ch-a) & ph-elech-a.next!=NULL)Search_Think(ph-elech-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-elei.next;i=*(word+j)-a;if(ph=NULL)if(jstrlen(word)sign2=2;return ph1;sign2=1;sign1=mid;return ph1;sign3=1;if(jstrlen(word)sign2=2;return ph1;sign1=mid;return ph1;void Search_TopTen_word(PTrie_Node ph)if(ph=NULL)return;for (char ch=a;chDisplayNum(ch-a) & ph!=NULL)WordMid=&ph-elech-a;for(int i=0;inumTopWordi-num)WordMid1=TopWordi;TopWordi=WordMid;WordMid=WordMid1;if(WordMid-sign4TopWordi-sign4& WordMid-num=TopWordi-num)WordMid1=TopWordi;TopWordi=WordMid;WordMid=WordMid1;if (ph-DisplaySign(ch-a) & ph-elech-a.next!=NULL)Search_TopTen_word(ph-elech-a.next);void PriTopTen_word(FILE *fp5)for(int i=0;inum!=0)fprintf(fp5,%s %dn,TopWordi-word,TopWordi-num);四 、程序使用说明及测试结果1程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后，稍等即显示信息：第 题已完成，结果存入文件 中。2测试结果本程序无须输入，直接从文件中读取信息，并将结果直接写入相应文件。3调试中的错误及解决办法。在compile时出现strcpy、strlen、strcmp三个函数undeclared identifier，没有进行头文件的定义，加上头文件#include即解决问题。在进行字典树的建立时，总是不能成功，在反复调试之后，加上语句for(i=0;i35;i+) wordi=0;便成功建立字典树。在进行第四个问题时，感觉没什么问题，但是在运行时时间很长才能得到结果，反复修改了很长时间还是没能把问题解决，向同学请教，还是没能得到好的结果。还有就是在进行文本比较时，PrefixFrequence_Result.Txt出现两处错误，与标准文件只差十个字节，让我很是头疼，困扰了我很长一段时间，还是没能解决。最后在进行主函数里的输出时，一开始我是选择的用switch函数，进行条件输出，但根据辅导老师的要求，要改成直接输出。改好后发现i总是重复定义，删除后，输出结果中数字出现连续叠加的现象，经调试，我把每一问里的序号统计标志改成不同的，于是问题就解决了。4运行界面五、实验总结(实验心得)由于这学期没有认真地进行数据结构课程的学习，加上以前五次实验课也没有认真对待，所以自己的实际操作能力很低，就导致了自己在这次课程设计中遇到很大的困难。首先是在前两次上机时，自己几乎是什么也没干，在机房坐了将近八个小时，在辅导老师检查进度时，自己毫无进展，感到很不好意思，但是