數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告示例

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告班級(jí): 姓名:陳進(jìn)文 學(xué)號(hào):2009302448 E-mail:日期:2010.1.4實(shí)驗(yàn)題目: 單詞（詞組）檢索。實(shí)驗(yàn)?zāi)康模涸谟谑箤W(xué)生對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)容易理解、掌握，并有助于在實(shí)際編程過程中應(yīng)用。鍛煉學(xué)生算法書寫、上機(jī)實(shí)習(xí)規(guī)范、程序調(diào)試技巧、設(shè)計(jì)說明書的整理等方面的內(nèi)容，為以后從事編寫復(fù)雜軟件及軟件開發(fā)工作打下基礎(chǔ)。實(shí)驗(yàn)內(nèi)容：該題目是對(duì)字符串和文件方面知識(shí)的運(yùn)用，對(duì)英文文章實(shí)現(xiàn)查找、插入、刪除、替換、定位等操作。對(duì)英文文章單詞(詞組)實(shí)現(xiàn)字符串模式匹配算法和文件操作算法。 (一) 需求分析1本課程設(shè)計(jì)程序中，有一個(gè)英文字典（每個(gè)單詞都是由小寫的'a'-

2、'z'組成），單詞量很大，達(dá)到120 多萬的單詞，而且還有很多重復(fù)的單詞。此外，我們現(xiàn)在還有一些 Document，每個(gè)Document 包含一些英語單詞。針對(duì)這個(gè)問題，請(qǐng)你選擇合適的數(shù)據(jù)結(jié)構(gòu)，組織這些數(shù)據(jù)，使時(shí)間復(fù)雜度和空間復(fù)雜度2演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“結(jié)束信息”之后，由用戶在相應(yīng)文件中檢驗(yàn)結(jié)果是否正確。3程序執(zhí)行的命令包括：（1）將所有英文單詞生成一個(gè)字典Dictionary；（2）判斷單詞是否在字典中，如果在單詞庫中，輸出這個(gè)單詞總共出現(xiàn)的次數(shù)，否則輸出NO，檢索結(jié)果存儲(chǔ)在SearchWordInvocabulary_Result.t

3、xt文件夾中；（3）給定一個(gè)單詞，按字典序輸出字典Dictionary 中所有以這個(gè)單詞為前綴的單詞，檢索結(jié)果儲(chǔ)存在TotPrefixWord_Result.txt 文件夾中；（4）給定一個(gè)單詞，輸出在 Dictionary 中以這個(gè)單詞為前綴的單詞的出現(xiàn)頻率最高的10 個(gè)單詞，對(duì)于具有相同出現(xiàn)次數(shù)的情況，按照最近（即最后）插入的單詞優(yōu)先級(jí)比較高的原則輸出，檢索結(jié)果儲(chǔ)存PrefixFrequence_Result.txt 文件；（5）輸出 Dictionary 中出現(xiàn)次數(shù)最高的10 個(gè)單詞,檢索結(jié)果存儲(chǔ)在MostFrequenceWord.txt 文件中；（6）輸入一個(gè)word, 檢索出哪些D

4、ocument 包含這個(gè)word，輸出這些Document 的DocumentID,檢索結(jié)果存儲(chǔ)在WordInDocument_Result.txt文件中；（7）在第六問基礎(chǔ)上，檢索出同時(shí)包含兩個(gè)相鄰word 的DocumentID，檢索結(jié)果存儲(chǔ)在TwoWordInDocument_Result.txt文件中；（8）在第七問基礎(chǔ)上，檢索多個(gè)word的DocumentID，檢索結(jié)果存儲(chǔ)在MultiWordInDocument_Result.txt文件中。4測(cè)試數(shù)據(jù)Vocabulary 文件夾下的vocabulary.txt 是英文字典的數(shù)據(jù)總共有120 多萬個(gè)單詞，即問題（1）（5）中單詞庫。D

5、ocument 文件夾下的document.txt 是用于（6），（7）,（8）題中的Document 數(shù)據(jù)。并和正確結(jié)果進(jìn)行比較。 (二) 概要設(shè)計(jì)為了實(shí)現(xiàn)上述操作，基本上應(yīng)以字典樹和文件為存儲(chǔ)結(jié)構(gòu)。1   基本操作：typedef struct tree typedef struct tr  操作結(jié)果：定義字典樹結(jié)構(gòu)，若成功就為樹分配了存儲(chǔ)空間2 本程序包含四部分：（1）基本型問題；（2）擴(kuò)展型問題；（3）高級(jí)型問題；（4）挑戰(zhàn)型問題。 (三) 詳細(xì)設(shè)計(jì)1元素類型，結(jié)點(diǎn)類型和指針類型：typedef struct tree int elem;stru

6、ct 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每個(gè)模塊的分析：（1）基本型問題：void buildtree(jd *root,FILE *fp) jd *p,*q; char ch;int i=

7、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

8、->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)

9、 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）擴(kuò)展型問題；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

10、,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->dat

11、a!=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 prin

12、ts1(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(d>9) 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-

13、>rchild !=NULL) if(p!=T) prints1(root,p->rchild,T,w,fa);（3）高級(jí)型問題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-;

14、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(d>9) break;if(wd=N

15、ULL) 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）挑戰(zhàn)型問題（5）主函數(shù)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("

16、;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("字典樹建立完成，已存入相應(yīng)文件!nn");fclose(fp);ff=fopen("SearchWordInVocabulary.txt",

17、"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);bre

18、ak;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("第二問查找完成，已存入相應(yīng)文件!nn"); fp=f

19、open("TotPrefixWord.txt","r");fa=fopen("TotPrefixWord_Result.txt","w");TotPrefixWord(root,fp,fa);fclose(fp);fclose(fa);printf("第三問查找完成，已存入相應(yīng)文件!nn");fp=fopen("PrefixFrequence.txt","r");fa=fopen("PrefixFrequence_Result.txt"

20、;,"w");PrefixFrequence(root,fp,fa);fclose(fp);fclose(fa);printf("第四問查找完成，已存入相應(yīng)文件!nn");fa=fopen("MostFrequenceWord.txt","w");for(u=0;u<10;u+) ssu=NULL;so=root;MostFrequenceWord1(root,so,ss,fa); for(u=0;u<10;u+) if(ssu!=NULL)MostFrequenceWord2(n,root,ssu,f

21、a);fclose(fa);printf("第五問查找完成，已存入相應(yīng)文件!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("第六問查找完成，已存入相應(yīng)文

22、件!nn");3完整的程序：#include<stdio.h>#include<stdlib.h>#include<string.h>#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

23、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&a

24、mp;&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->

25、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->weigh

26、t!=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

27、=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)whi

28、le(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,

29、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(d>9) break; if(wd=NULL) wd=p; else for(t=8;t>=d;t-) wt+1=wt; wd=p; p=s;if(p->lchi

30、ld !=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;k<10;k+) wk=NULL;k=1;p=root; q=root;ch=fgetc(fp);while(ch!=EOF)while(ch!='n')wh

31、ile(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;prints1(root,q,T,w,fa); for(s=0;s

32、<10;s+) if(ws!=NULL)MostFrequenceWord2(n,root,ws,fa);k+;p=root;q=root;ch=fgetc(fp); for(s=0;s<10;s+) ws=NULL;s=0;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(d>9) break;if(wd=NULL) wd=

33、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",

34、"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("字典樹建立完成，已存入相應(yīng)文件!nn");fclose(fp);ff=fopen("SearchWordInVocabulary.txt","r");fa=fope

35、n("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

36、=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("第二問查找完成，已存入相應(yīng)文件!nn"); fp=fopen("TotPrefixWord.txt&qu