数据结构实验报告示例.doc

数据结构课程设计实验报告班级:10010901 姓名:陈进文 学号:2009302448 E-mail:861887303日期:2010.1.4实验题目: 单词（词组）检索。实验目的：在于使学生对复杂的数据结构容易理解、掌握，并有助于在实际编程过程中应用。锻炼学生算法书写、上机实习规范、程序调试技巧、设计说明书的整理等方面的内容，为以后从事编写复杂软件及软件开发工作打下基础。实验内容：该题目是对字符串和文件方面知识的运用，对英文文章实现查找、插入、删除、替换、定位等操作。对英文文章单词(词组)实现字符串模式匹配算法和文件操作算法。 (一) 需求分析1本课程设计程序中，有一个英文字典（每个单词都是由小写的a-z组成），单词量很大，达到120 多万的单词，而且还有很多重复的单词。此外，我们现在还有一些 Document，每个Document 包含一些英语单词。针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“结束信息”之后，由用户在相应文件中检验结果是否正确。3程序执行的命令包括：（1）将所有英文单词生成一个字典Dictionary；（2）判断单词是否在字典中，如果在单词库中，输出这个单词总共出现的次数，否则输出NO，检索结果存储在SearchWordInvocabulary_Result.txt文件夹中；（3）给定一个单词，按字典序输出字典Dictionary 中所有以这个单词为前缀的单词，检索结果储存在TotPrefixWord_Result.txt 文件夹中；（4）给定一个单词，输出在 Dictionary 中以这个单词为前缀的单词的出现频率最高的10 个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出，检索结果储存PrefixFrequence_Result.txt 文件；（5）输出 Dictionary 中出现次数最高的10 个单词,检索结果存储在MostFrequenceWord.txt 文件中；（6）输入一个word, 检索出哪些Document 包含这个word，输出这些Document 的DocumentID,检索结果存储在WordInDocument_Result.txt文件中；（7）在第六问基础上，检索出同时包含两个相邻word 的DocumentID，检索结果存储在TwoWordInDocument_Result.txt文件中；（8）在第七问基础上，检索多个word的DocumentID，检索结果存储在MultiWordInDocument_Result.txt文件中。4测试数据Vocabulary 文件夹下的vocabulary.txt 是英文字典的数据总共有120 多万个单词，即问题（1）（5）中单词库。Document 文件夹下的document.txt 是用于（6），（7）,（8）题中的Document 数据。并和正确结果进行比较。 (二) 概要设计为了实现上述操作，基本上应以字典树和文件为存储结构。1 基本操作：typedef struct tree typedef struct tr 操作结果：定义字典树结构，若成功就为树分配了存储空间2 本程序包含四部分：（1）基本型问题；（2）扩展型问题；（3）高级型问题；（4）挑战型问题。(三) 详细设计1元素类型，结点类型和指针类型：typedef struct tree int elem;struct tree *next;num;typedef struct trchar data;int weight; struct tr *lchild,*rchild,*parent;num *na;jd;jd *p,*q,*root,*root1,*ss10,*so;int s=0;int k,u,n=0;FILE *fp,*fa,*ff;char a,ch; 2每个模块的分析：（1）基本型问题：void buildtree(jd *root,FILE *fp) jd *p,*q; char ch;int i=0; p=root;q=root;ch=fgetc(fp);while(ch!=EOF) if(ch!=n) if(p-lchild=NULL) p-lchild =(jd *)malloc(sizeof(jd); q=p; p=p-lchild ; p-parent =q; p-data =ch; p-weight =0; p-lchild=NULL; p-rchild=NULL; ch=fgetc(fp); else q=p;p=p-lchild ; while(p!=NULL&p-data!=ch) q=p;p=p-rchild ; if(p=NULL) p=(jd *)malloc(sizeof(jd); q-rchild=p; p-parent =q; p-rchild =NULL; p-lchild =NULL; p-weight =0; p-data =ch; ch=fgetc(fp); else if(ch=n) p-weight+; p=root;q=root; ch=fgetc(fp); while(p!=NULL&p-data!=ch) q=p;p=p-rchild ; if(p=NULL) p =(jd *)malloc(sizeof(jd); q-rchild=p ; p-parent =q; p-rchild =NULL; p-lchild =NULL; p-weight =0; p-data =ch; ch=fgetc(fp); （2）扩展型问题；void prints(jd *root,jd *p,jd *T,FILE *fa)jd *s;int n=1; s=p;if(p-weight !=0) MostFrequenceWord2(n,root,p,fa); p=s;if(p-lchild!=NULL) prints(root,p-lchild,T,fa);if(p-rchild!=NULL) if(p!=T) prints(root,p-rchild,T,fa);void TotPrefixWord(jd *root,FILE *fp,FILE *fa)char ch;jd *p,*q,*T;int k=1,s=0;p=root;q=root;ch=fgetc(fp);while(ch!=EOF)while(ch!=n)while(p!=NULL&p-data!=ch) q=p;p=p-rchild ;if(p=NULL)fprintf(fa,CASE %d:n,k);s=1;while(ch!=n)ch=fgetc(fp);break;else if(p-data=ch)q=p;p=p-lchild ;ch=fgetc(fp);if(ch=EOF) break;if(s=0)fprintf(fa,CASE %d:n,k);T=q;prints(root,q,T,fa);s=0;k+;p=root;q=root;ch=fgetc(fp);void prints1(jd *root,jd *p,jd *T,jd *w10,FILE *fa) jd *q,*s;s=p;q=p;int t=0,d;if(p-weight!=0) d=0; while(wd!=NULL&wd-weight p-weight ) d+; if(d9) break; if(wd=NULL) wd=p; else for(t=8;t=d;t-) wt+1=wt; wd=p; p=s;if(p-lchild !=NULL) prints1(root,p-lchild ,T,w,fa);if(p-rchild !=NULL) if(p!=T) prints1(root,p-rchild,T,w,fa);（3）高级型问题a. void MostFrequenceWord2(int n,jd *root,jd *p,FILE *fa) int t=0,d=0;char dcMAX;jd *q,*s;q=p;s=p;if(p-weight!=0) dct=p-data;t+;q=p;p=p-parent;while(p!=NULL)if(p-lchild =q) dct=p-data;t+;q=p;p=p-parent ;t-;while(t=0) fprintf(fa,%c,dct);t-;if(n=0) fprintf(fa, %d,s-weight);fprintf(fa,n);b. void MostFrequenceWord1(jd *root,jd *p,jd *w10,FILE *fa)int t=0,d;if(p-weight!=0)d=0;while(wd!=NULL&wd-weight p-weight ) d+;if(d9) break;if(wd=NULL) wd=p;else for(t=8;t=d;t-) wt+1=wt;wd=p;if(p-lchild !=NULL) MostFrequenceWord1(root,p-lchild,w,fa);if(p-rchild !=NULL) MostFrequenceWord1(root,p-rchild,w,fa);（4）挑战型问题（5）主函数void main()jd *p,*q,*root,*root1,*ss10,*so;int s=0;int k,u,n=0;FILE *fp,*fa,*ff;char a,ch;fp=fopen(vocabulary.txt,r); ch=fgetc(fp); root=(jd *)malloc(sizeof(jd);root-data=ch;root-lchild =NULL;root-weight =0;root-rchild =NULL;root-parent =NULL;buildtree(root,fp);printf(字典树建立完成，已存入相应文件!nn);fclose(fp);ff=fopen(SearchWordInVocabulary.txt,r);fa=fopen(SearchWordInVocabulary_Result.txt,w);a=fgetc(ff); p=root; q=root; k=1;while(a!=EOF)while(a!=n)while(p!=NULL&p-data!=a) q=p;p=p-rchild;if(p=NULL) fprintf(fa,CASE %d:nNOn,k);s=1;while(a!=n) a=fgetc(ff);break;else if(p-data =a) q=p;p=p-lchild;a=fgetc(ff);if(a=EOF)break; if(s=0) if(q-weight=0)fprintf(fa,CASE %d:nNOn,k);s=1;else fprintf(fa,CASE %d:n%dn,k,q-weight); p=root;q=root;s=0;k+; a=fgetc(ff);fclose(fa);fclose(ff);printf(第二问查找完成，已存入相应文件!nn); fp=fopen(TotPrefixWord.txt,r);fa=fopen(TotPrefixWord_Result.txt,w);TotPrefixWord(root,fp,fa);fclose(fp);fclose(fa);printf(第三问查找完成，已存入相应文件!nn);fp=fopen(PrefixFrequence.txt,r);fa=fopen(PrefixFrequence_Result.txt,w);PrefixFrequence(root,fp,fa);fclose(fp);fclose(fa);printf(第四问查找完成，已存入相应文件!nn);fa=fopen(MostFrequenceWord.txt,w);for(u=0;u10;u+) ssu=NULL;so=root;MostFrequenceWord1(root,so,ss,fa); for(u=0;u10;u+) if(ssu!=NULL)MostFrequenceWord2(n,root,ssu,fa);fclose(fa);printf(第五问查找完成，已存入相应文件!nn); fp=fopen(Document.txt,r);ff=fopen(WordInDocument.txt,r);fa=fopen(WordInDocument_Result.txt,w);buildtree(root1,fp);fclose(fp);fclose(fa);fclose(ff);printf(第六问查找完成，已存入相应文件!nn);3完整的程序：#include#include#include#define OK 1#define MAX 40typedef struct tree int elem;struct tree *next;num;typedef struct trchar data;int weight; struct tr *lchild,*rchild,*parent;num *na;jd;void buildtree(jd *root,FILE *fp) jd *p,*q; char ch;int i=0; p=root;q=root;ch=fgetc(fp);while(ch!=EOF) if(ch!=n) if(p-lchild=NULL) p-lchild =(jd *)malloc(sizeof(jd); q=p; p=p-lchild ; p-parent =q; p-data =ch; p-weight =0; p-lchild=NULL; p-rchild=NULL; ch=fgetc(fp); else q=p;p=p-lchild ; while(p!=NULL&p-data!=ch) q=p;p=p-rchild ; if(p=NULL) p=(jd *)malloc(sizeof(jd); q-rchild=p; p-parent =q; p-rchild =NULL; p-lchild =NULL; p-weight =0; p-data =ch; ch=fgetc(fp); else if(ch=n) p-weight+; p=root;q=root; ch=fgetc(fp); while(p!=NULL&p-data!=ch) q=p;p=p-rchild ; if(p=NULL) p =(jd *)malloc(sizeof(jd); q-rchild=p ; p-parent =q; p-rchild =NULL; p-lchild =NULL; p-weight =0; p-data =ch; ch=fgetc(fp); void MostFrequenceWord2(int n,jd *root,jd *p,FILE *fa) int t=0,d=0;char dcMAX;jd *q,*s;q=p;s=p;if(p-weight!=0) dct=p-data;t+;q=p;p=p-parent;while(p!=NULL)if(p-lchild =q) dct=p-data;t+;q=p;p=p-parent ;t-;while(t=0) fprintf(fa,%c,dct);t-;if(n=0) fprintf(fa, %d,s-weight);fprintf(fa,n);void prints(jd *root,jd *p,jd *T,FILE *fa)jd *s;int n=1; s=p;if(p-weight !=0) MostFrequenceWord2(n,root,p,fa); p=s;if(p-lchild!=NULL) prints(root,p-lchild,T,fa);if(p-rchild!=NULL) if(p!=T) prints(root,p-rchild,T,fa);void TotPrefixWord(jd *root,FILE *fp,FILE *fa)char ch;jd *p,*q,*T;int k=1,s=0;p=root;q=root;ch=fgetc(fp);while(ch!=EOF)while(ch!=n)while(p!=NULL&p-data!=ch) q=p;p=p-rchild ;if(p=NULL)fprintf(fa,CASE %d:n,k);s=1;while(ch!=n)ch=fgetc(fp);break;else if(p-data=ch)q=p;p=p-lchild ;ch=fgetc(fp);if(ch=EOF) break;if(s=0)fprintf(fa,CASE %d:n,k);T=q;prints(root,q,T,fa);s=0;k+;p=root;q=root;ch=fgetc(fp);void prints1(jd *root,jd *p,jd *T,jd *w10,FILE *fa) jd *q,*s;s=p;q=p;int t=0,d;if(p-weight!=0) d=0; while(wd!=NULL&wd-weight p-weight ) d+; if(d9) break; if(wd=NULL) wd=p; else for(t=8;t=d;t-) wt+1=wt; wd=p; p=s;if(p-lchild !=NULL) prints1(root,p-lchild ,T,w,fa);if(p-rchild !=NULL) if(p!=T) prints1(root,p-rchild,T,w,fa);void PrefixFrequence(jd *root,FILE *fp,FILE *fa)char ch;jd *p,*q,*T,*w10;int k=1,s=0,n=0;for(k=0;kdata!=ch) q=p;p=p-rchild ;if(p=NULL)fprintf(fa,CASE %d:n,k);s=1;while(ch!=n)ch=fgetc(fp);break;else if(p-data=ch)q=p;p=p-lchild ;ch=fgetc(fp);if(ch=EOF) break;if(s=0)fprintf(fa,CASE %d:n,k);T=q;prints1(root,q,T,w,fa); for(s=0;s10;s+) if(ws!=NULL)MostFrequenceWord2(n,root,ws,fa);k+;p=root;q=root;ch=fgetc(fp); for(s=0;sweight!=0)d=0;while(wd!=NULL&wd-weight p-weight ) d+;if(d9) break;if(wd=NULL) wd=p;else for(t=8;t=d;t-) wt+1=wt;wd=p;if(p-lchild !=NULL) MostFrequenceWord1(root,p-lchild,w,fa);if(p-rchild !=NULL) MostFrequenceWord1(root,p-rchild,w,fa);void main()jd *p,*q,*root,*root1,*ss10,*so;int s=0;int k,u,n=0;FILE *fp,*fa,*ff;char a,ch;fp=fopen(vocabulary.txt,r); ch=fgetc(fp); root=(jd *)malloc(sizeof(jd);root-data=ch;root-lchild =NULL;root-weight =0;root-rchild =NULL;root-parent =NULL;buildtree(root,fp);printf(字典树建立完成，已存入相应文件!nn);fclose(fp);ff=fopen(SearchWordInVocabulary.txt,r);fa=fopen(SearchWordInVocabulary_Result.txt,w);a=fgetc(ff); p=root; q=root; k=1;while(a!=EOF)while(a!=n)while(p!=NULL&p-data!=a) q=p;p=p-rchild;if(p=NULL) fprintf(fa,CASE %d:nNOn,k);s=1;while(a!=n) a=fgetc(ff);break;else if(p-data =a) q=p;p=p-lchild;a=fgetc(ff);if(a=EOF)break; if(s=0) if(q-weight=0)fprintf(fa,CASE %d:nNOn,k);s=1;else fprintf(fa,CASE %d:n%dn,k,q-weight); p=root;q=root;s=0;k+; a=fgetc(ff);fclose(fa);fclose(ff);printf(