數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(字典序)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：10 大?。?23.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩9頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　2011-2012年數(shù)據(jù)結(jié)構(gòu)　　課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告　　學(xué)院：計(jì)算機(jī)學(xué)院　　班級(jí)：　　姓名:</

2、p>　　學(xué)號(hào)：　　郵箱：　　年月日　　《課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告　　◎?qū)嶒?yàn)題目: 字典序　　◎

3、實(shí)驗(yàn)?zāi)康模涸O(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)，建立字典樹，解決文件中單詞的搜索統(tǒng)計(jì)問題。　　◎?qū)嶒?yàn)內(nèi)容：現(xiàn)在有一個(gè)英文字典（每個(gè)單詞都是由小寫的'a'-'z'組成），單詞量很大，達(dá)到100多萬的單詞，而且還有很多重復(fù)的單詞。　　此外，我們現(xiàn)在還有一些 Document，每個(gè)Document 包含一些英語單詞。 &l

4、t;p>　　針對(duì)這個(gè)問題，請(qǐng)你選擇合適的數(shù)據(jù)結(jié)構(gòu)，組織這些數(shù)據(jù)，使時(shí)間復(fù)雜度和空間復(fù)雜度盡可能低，并且解決下面的問題和分析自己算法的時(shí)間復(fù)雜度。 　　1）基本型問題 　?。?）選擇合適的數(shù)據(jù)結(jié)構(gòu)，將所有的英文單詞生成一個(gè)字典Dictionary。 　?。?）給定一個(gè)單詞

5、，判斷這個(gè)單詞是否在字典 Dictionary中。如果在單詞庫中，輸出這個(gè)單詞總共出現(xiàn)的次數(shù)。否則輸出NO。　　2）擴(kuò)展型問題 　?。?）給定一個(gè)單詞，按字典序輸出字典 Dictionary 中所有以這個(gè)單詞為前綴的單詞。例如，如果字典 T={a,aa, aaa, b, ba}, 如果你輸入 a,那么輸出應(yīng)該為{a,

6、 aa, aaa}。　　（4）給定一個(gè)單詞，輸出在Dictionary 中以這個(gè)單詞為前綴的單詞的出現(xiàn)頻率最高的10個(gè)單詞，對(duì)于具有相同出現(xiàn)次數(shù)的情況，按照最近（即最后）插入的單詞優(yōu)先級(jí)比較高的原則輸出。　　（5）輸出Dictionary中出現(xiàn)次數(shù)最高的10個(gè)單詞。　　3）高級(jí)型問題 </

7、b>　　（6）現(xiàn)在我們有一些Document，每個(gè)Document 由一些單詞組成，現(xiàn)在的問題就是給你一個(gè)word，檢索出哪些 Document包含這個(gè) word，輸出這些Document的DocumentID（就如同搜索引擎一樣，即輸入一些關(guān)鍵字，然后檢索出和這些關(guān)鍵字相關(guān)的文檔）。　?。?）在第（6）問中，我們只考慮了一個(gè)word 在哪些Doc

8、ument中的情況，我們進(jìn)一步考慮2個(gè)相鄰word的情況，檢索出同時(shí)包含這兩個(gè)相鄰word的DocumentID。　　4）挑戰(zhàn)型問題 　?。?）現(xiàn)在我們?cè)賹?duì)（7）的問題進(jìn)行擴(kuò)展，把（7）中的只檢索相鄰 2個(gè)word 推廣到可以檢索多個(gè)word（即連續(xù)的k個(gè)word，其中k>=2），檢索出同時(shí)包含k個(gè)連續(xù)wor

9、d 的DocumentID。　　我解決了前六個(gè)問題。　　一、需求分析　　1．本程序演示中，程序自動(dòng)讀取目標(biāo)文件，生成需要的文件。　　2. 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入相

10、應(yīng)數(shù)據(jù)。　　3．程序執(zhí)行的主要命令包括：　?。?）構(gòu)建棧；（2）構(gòu)造字典樹；（3）構(gòu)建文件數(shù)；（4）樹的查找；（5）結(jié)束。　　二概要設(shè)計(jì)　　為實(shí)現(xiàn)上述算法，選擇字典樹為本程序的存儲(chǔ)結(jié)構(gòu)。

11、1、本程序包括三個(gè)模塊：　?。?）主程序模塊；　　（2）構(gòu)建棧模塊；　　（3）構(gòu)造字典樹模塊；　　（4）構(gòu)建文件數(shù)模塊；　　（5）樹的遍歷模塊；</

12、p>　　2、模塊調(diào)用關(guān)系圖　　三詳細(xì)設(shè)計(jì)　　1、定義存儲(chǔ)鏈表結(jié)構(gòu)：　?。?）定義字典樹與文件數(shù)結(jié)構(gòu)：　　#include<stdio.h></p&g

13、t;　　#include<string.h>　　#include<stdlib.h>　　#include<malloc.h>　　#define NULL 0　　#define ERROR -1

14、　　#define stack_in_size 100　　#define stackincrement 10　　struct TreeNode /*樹結(jié)點(diǎn)*/　　{ 　　char ch;

15、 　　int number; /*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/　　struct TreeNode* pt[26]; /*指向后繼的字母的26個(gè)指針*/　　}; 　　struct TreeNode *

16、root;　　typedef struct TreeNode *Link_TreeNode;　　struct MAX_TEN /*存放出現(xiàn)頻率最高的十個(gè)單詞數(shù)據(jù)結(jié)構(gòu)*/　　{　　char STRING[35];<

17、;/p>　　int count; /*字符串出現(xiàn)的次數(shù)*/　　int xiabao; /*字符數(shù)組位置的下標(biāo)*/　　}; 　　struct MAX_TEN MAX[10];&

18、lt;/p>　　struct MAX_TEN MIN;　　struct DocumentNode /*文件結(jié)點(diǎn)*/　　{　　char ch; /*存放某個(gè)單詞的一個(gè)字符*/</p

19、>　　int number; /*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/　　struct DocumentNode* pt[26]; /*指向后繼的字母的26個(gè)指針*/　　struct Locationn *next;/*連接以該字符為結(jié)束的單詞所在的位置*/<p

20、>　　}; 　　typedef struct DocumentNode *Link_DocumentNode;　　Link_DocumentNode ROOT[301]; /*300個(gè)根節(jié)點(diǎn)指針,零號(hào)單元不用*/ 　　struct Lo

21、cationn /*單詞在文件中的位置*/　　{　　int num; 　　struct Locationn *next; 　　};

22、 　　struct WORD /*單詞鏈表結(jié)構(gòu)*/　　{　　char strr[35];　　struct WORD *next;　　};

23、 　　typedef struct 　　{　　char *base;　　char *top;　　int stacksize;

24、;　　}SQSTACK;　　SQSTACK S,T;　　2、每個(gè)模塊的分析：　?。?）主程序模塊：　　void main()　　{<

25、;/b>　　printf("*****************基本型問題************************\n");　　CREAT_DicTree();/*第一題，讀入vocabulary文件，建立存放單詞的字典樹*/　　printf("The First pro

26、blem has been solved,a dictionary tree has been buildt\n");　　OPEN_SearchWordInVocabulary();/*第二題，生成SearchWordInVocabulary_Result.txt*/　　printf("The Second problem has b

27、een solved,SearchWordInVocabulary_Result.txt formed \n");　　printf("*****************擴(kuò)展型問題************************\n");　　OPEN_TotPrefixWord();/*第三題，生成TotPrefixWord_

28、Result.txt*/　　printf("The Third problem has been solved,TotPrefixWord_Result.txt formed \n");　　OPEN_PrefixFrequence();/*第四題，生成PrefixFrequence_Result.txt*/&l

29、t;p>　　printf("The Forth problem has been solved,PrefixFrequence_Result.txt formed \n");　　OPEN_MostFrequenceWord();/*第五題，生成MostFrequenceWord.txt*/　　printf("The F

30、ifth problem has been solved,MostFrequenceWord.txt formde\n");　　printf("*****************高級(jí)型問題************************\n");　　CREAT_DocumentTree();/*第六題，讀入Document文

31、件，建立存放文件的樹*/　　printf("The Sixth problem has been solved,WordInDocument_Result.txt formed\n");　　}　　（2）構(gòu)建棧模塊：&l

32、t;/p>　　SQSTACK Creat() /*創(chuàng)建空棧*/　　{　　SQSTACK s;　　s.base=(char*)malloc(stack_in_size*sizeof(char));

33、　　s.top=s.base;　　s.stacksize=stack_in_size;　　return s;　　} /*全局變量棧*/　　char pop(SQSTACK &

34、;s) /*出棧*/　　{ 　　char e;　　if(s.top==s.base)return ERROR;　　e=*(--s.top);　　return

35、 e;　　}　　void push(SQSTACK &s,char e) /*入棧*/　　{　　if(s.top-s.base>=s.stacksize)&l

36、t;/p>　　{s.base=(char*)realloc(s.base,　　(s.stacksize+stackincrement )*sizeof(char));　　s.top=s.base+s.stacksize;　　s.stacksize+=stackincrement;&l

37、t;/p>　　}　　*s.top=e;　　s.top=s.top+1;　　}　　int isempty(SQSTACK s)

38、 /*判斷棧是否為空*/　　{　　if(s.base==s.top)　　return 1;　　else &l

39、t;b>　　return 0;　　}　?。?）構(gòu)造字典樹模塊：　　Link_TreeNode creat() /*創(chuàng)建樹結(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針*/　　{</b&

40、gt;　　int i;　　Link_TreeNode pt;　　pt=(Link_TreeNode)malloc(sizeof(TreeNode));　　pt->number=0;　　f

41、or(i=0;i<26;i++)　　pt->pt[i]=NULL;　　return pt;　　}　　void CREAT_DicTree() /*創(chuàng)建字典樹*/

42、　　{　　root=creat();　　Link_TreeNode q;　　FILE *fp;　　char *p;&

43、lt;b>　　int ctmp;　　int jieshu;　　char str[35]; /*存放從文件中讀入的單詞*/　　if((fp=fopen("vocabulary.txt","r"))==NULL)</p&g

44、t;　　printf("cannot open vocabulary.txt\n");　　while(1)　　{ 　　jieshu=fscanf(fp,"%s",str)

45、;/*從文件中讀入字符串*/　　q=root; 　　if(jieshu==-1) 　　break; 　　else<

46、;p>　　{ 　　p=str;　　while(*p!='\0')　　{ 　　ctmp=*p-97;

47、　　if(q->pt[ctmp]!=NULL)　　q=q->pt[ctmp]; 　　else　　{ 　　q->pt[ctmp]=creat();

48、;　　q=q->pt[ctmp];　　q->ch=*p;　　}　　p++;　　if(*p=='\0')

49、 　　{　　q->number++;　　break;　　}　　}&

50、lt;/p>　　}　　} 　　}　?。?）構(gòu)建文件數(shù)模塊：　　Link_DocumentNode CREAT()/*創(chuàng)建一個(gè)文件

51、型的數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針*/　　{　　int i;　　Link_DocumentNode p;　　p=(Link_DocumentNode)malloc(sizeof(struct

52、 DocumentNode));　　p->number=0;　　for(i=0;i<26;i++)　　{　　p->pt[i]=NULL;　　}</b&

53、gt;　　p->next=NULL; /*文件初始化*/　　return p;　　}　　void CREAT_DocumentTree() /

54、*讀入文件，創(chuàng)建文件樹*/　　{　　Link_DocumentNode q;　　struct Locationn *LL;　　FILE *fp;<b

55、>　　char *p;　　int ctmp;　　int jieshu;　　int Location; /*定位單詞在文章中的位置*/　　int k;

56、 　　char str[35]; /*存放從文件中讀入的單詞*/　　if((fp=fopen("Document.txt","r"))==NULL)　　printf("cannot open Document.tx

57、t\n");　　while(1)　　{ 　　jieshu=fscanf(fp,"%s",str);　　if(jieshu==-1) <

58、/p>　　break; /*文件中單詞已讀完*/　　if(!strcmp(str,"Document"))　　{　　fscanf(fp,"%d",&k);

59、;　　ROOT[k]=CREAT();　　Location=1;　　fscanf(fp,"%s",str);　　}　　q=ROOT[k];<b&

60、gt;　　p=str;　　while(*p!='\0') /*處理每個(gè)單詞*/　　{　　ctmp=*p-97;　　if(q->pt[ctmp]!=NULL)</p

61、>　　q=q->pt[ctmp];　　else　　{　　q->pt[ctmp]=CREAT();　　q=q->pt[ctmp];

62、　　q->ch=*p;　　}　　p++;　　if(*p=='\0')　　{

63、;　　q->number++;　　if(q->next==NULL) 　　{　　LL=(struct Locationn *)malloc(sizeof(struct Locationn));<

64、;p>　　LL->num=Location;　　q->next=LL;　　LL->next=NULL;　　Location++;　　break;　　}

65、　　else 　　{ 　　LL=q->next;　　while(LL->next!=NULL)　　LL=LL->next;<

66、;/p>　　LL->next=(struct Locationn *)malloc(sizeof(struct Locationn));　　LL=LL->next;　　LL->next=NULL;　　LL->num=Location;&l

67、t;p>　　Location++;　　break;　　}　　} 　　}

68、　　} 　　}　　（5）程序使用的函數(shù)：　　SQSTACK Creat()　　char pop(SQSTACK &s)　　void push(S

69、QSTACK &s,char e)　　int isempty(SQSTACK s)　　Link_TreeNode creat()　　void CREAT_DicTree()　　int Search(char str[],Link_TreeNode root)<

70、;/p>　　Link_TreeNode Get_Last_Link(char str[])　　bool OutPrint(Link_TreeNode p,FILE *fp)　　void RECHANGE_MIN(char tepp[],int cunt)　　bool GOT_MAX_T

71、EN(Link_TreeNode p)　　Link_DocumentNode CREAT()　　void CREAT_DocumentTree()　　int Search_Doc(char str[],Link_DocumentNode root)　　void SORT_

72、MAX_Ten()　　struct WORD *Creat_two_word_link(char str1[],char str2[])　　struct WORD *Creat_multi_word_link(int length,FILE *fp)　　void Search_Match_Word(struct

73、WORD *head,int length,FILE *fp)　　void OPEN_SearchWordInVocabulary()　　void OPEN_TotPrefixWord()　　void OPEN_PrefixFrequence()　　void OPEN_M

74、ostFrequenceWord()　　void main()　　3、數(shù)據(jù)結(jié)構(gòu)示意圖：‘　　26個(gè)孩子　　。。。。。。　　每個(gè)樹結(jié)點(diǎn)有26個(gè)孩子</

75、p>　　四使用說明、測(cè)試分析及結(jié)果　　1、程序使用說明：　　（1）本程序的運(yùn)行環(huán)境為VC6.0。　?。?）進(jìn)入演示程序后即顯示的提示信息：　　輸出：

76、;　　*****************基本型問題************************　　The First problem has been solved,a dictionary tree has been buildt　　The Second problem has been solved,SearchWordIn

77、Vocabulary_Result.txt formed　　*****************擴(kuò)展型問題************************　　The Third problem has been solved,TotPrefixWord_Result.txt formed　　The Forth pr

78、oblem has been solved,PrefixFrequence_Result.txt formed　　The Fifth problem has been solved,MostFrequenceWord.txt formed　　*****************高級(jí)型問題************************

79、　　The Sixth problem has been solved,WordInDocument_Result.txt formed　　2、運(yùn)行界面：　　五、實(shí)驗(yàn)總結(jié)　　這次實(shí)驗(yàn)題目涉及了數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中的多種結(jié)構(gòu)，

80、要求對(duì)各種數(shù)據(jù)的存儲(chǔ)與處理的方法比較熟悉。在實(shí)驗(yàn)中，由于這學(xué)期沒有很認(rèn)真的學(xué)習(xí)這門課，平常實(shí)驗(yàn)課寫程序也不是很認(rèn)真，以至于解決前兩個(gè)問題還比較輕松，但是從三個(gè)問題開始我就遇到了很大困難，在數(shù)據(jù)的處理過程中遇到了不小的麻煩，導(dǎo)致后來調(diào)試的時(shí)候浪費(fèi)了很多時(shí)間。同時(shí)，程序的時(shí)間復(fù)雜度耗時(shí)，占用內(nèi)存較大，這說明程序的結(jié)構(gòu)不夠靈巧，我會(huì)再次認(rèn)真的自己學(xué)習(xí)這門課程，希望在以后的學(xué)習(xí)中能把程序?qū)懙酶谩?lt;/p><

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(字典序)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(字典序)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載