西工大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)TireTree

1、2011-2012年數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告學(xué)院： 班級(jí)： 姓名: 學(xué)號(hào)：郵箱：2012年1月5日課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告班 級(jí): 學(xué) 號(hào): 姓 名: E-mail: 日 期:實(shí)驗(yàn)題目: 字典樹(shù)實(shí)驗(yàn)?zāi)康模涸O(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)，建立字典樹(shù)，解決文件中單詞的搜索統(tǒng)計(jì)問(wèn)題。實(shí)驗(yàn)內(nèi)容：現(xiàn)在有一個(gè)英文字典（每個(gè)單詞都是由小寫(xiě)的'a'-'z'組成），單詞量很大，達(dá)到100多萬(wàn)的單詞，而且還有很多重復(fù)的單詞。此外，我們現(xiàn)在還有一些 Document，每個(gè)Document 包含一些英語(yǔ)單詞。 針對(duì)這個(gè)問(wèn)題，請(qǐng)你選擇合適的數(shù)據(jù)結(jié)構(gòu)，組織這些數(shù)據(jù)，使時(shí)間復(fù)雜度和空間復(fù)雜度盡可能低，并且解決下

2、面的問(wèn)題和分析自己算法的時(shí)間復(fù)雜度。 1）基本型問(wèn)題 （1）選擇合適的數(shù)據(jù)結(jié)構(gòu)，將所有的英文單詞生成一個(gè)字典Dictionary。 （2）給定一個(gè)單詞，判斷這個(gè)單詞是否在字典 Dictionary中。如果在單詞庫(kù)中，輸出這個(gè)單詞總共出現(xiàn)的次數(shù)。否則輸出NO。2）擴(kuò)展型問(wèn)題 （3）給定一個(gè)單詞，按字典序輸出字典 Dictionary 中所有以這個(gè)單詞為前綴的單詞。例如，如果字典 T=a,aa, aaa, b, ba, 如果你輸入 a,那么輸出應(yīng)該為a, aa, aaa。（4）給定一個(gè)單詞，輸出在Dictionary 中以這個(gè)單詞為前綴的單詞的出現(xiàn)頻率最高的10個(gè)單詞，對(duì)于具有相同出現(xiàn)次數(shù)的情況，

3、按照最近（即最后）插入的單詞優(yōu)先級(jí)比較高的原則輸出。（5）輸出Dictionary中出現(xiàn)次數(shù)最高的10個(gè)單詞。3）高級(jí)型問(wèn)題 （6）現(xiàn)在我們有一些Document，每個(gè)Document 由一些單詞組成，現(xiàn)在的問(wèn)題就是給你一個(gè)word，檢索出哪些 Document包含這個(gè) word，輸出這些Document的DocumentID（就如同搜索引擎一樣，即輸入一些關(guān)鍵字，然后檢索出和這些關(guān)鍵字相關(guān)的文檔）。（7）在第（6）問(wèn)中，我們只考慮了一個(gè)word 在哪些Document中的情況，我們進(jìn)一步考慮2個(gè)相鄰word的情況，檢索出同時(shí)包含這兩個(gè)相鄰word的DocumentID。4）挑戰(zhàn)型問(wèn)題 （8）

4、 現(xiàn)在我們?cè)賹?duì)（7）的問(wèn)題進(jìn)行擴(kuò)展，把（7）中的只檢索相鄰 2個(gè)word 推廣到可以檢索多個(gè)word（即連續(xù)的k個(gè)word，其中k>=2），檢索出同時(shí)包含k個(gè)連續(xù)word 的DocumentID。我解決了前六個(gè)問(wèn)題。一、需求分析1本程序演示中，程序自動(dòng)讀取目標(biāo)文件，生成需要的文件。2. 演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤(pán)上輸入相應(yīng)數(shù)據(jù)。3程序執(zhí)行的主要命令包括：（1）構(gòu)建棧；（2）構(gòu)造字典樹(shù)；（3）構(gòu)建文件數(shù)；（4）樹(shù)的查找；（5）結(jié)束。二 概要設(shè)計(jì)為實(shí)現(xiàn)上述算法，選擇字典樹(shù)為本程序的存儲(chǔ)結(jié)構(gòu)。1、本程序包括三個(gè)模塊：（1）主程序模塊

5、；（2）構(gòu)建棧模塊；（3）構(gòu)造字典樹(shù)模塊；（4）構(gòu)建文件數(shù)模塊；（5）樹(shù)的遍歷模塊；2、模塊調(diào)用關(guān)系圖主程序模塊構(gòu)建棧模塊構(gòu)造字典樹(shù)模塊構(gòu)建文件數(shù)模塊樹(shù)的遍歷模塊三 詳細(xì)設(shè)計(jì)1、定義存儲(chǔ)鏈表結(jié)構(gòu)：（1）定義字典樹(shù)與文件數(shù)結(jié)構(gòu)：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#define NULL 0#define ERROR -1#define stack_in_size 100#define stackincrement 10struct TreeN

6、ode /*樹(shù)結(jié)點(diǎn)*/ char ch; int number; /*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/struct TreeNode* pt26; /*指向后繼的字母的26個(gè)指針*/; struct TreeNode *root;typedef struct TreeNode *Link_TreeNode;struct MAX_TEN /*存放出現(xiàn)頻率最高的十個(gè)單詞數(shù)據(jù)結(jié)構(gòu)*/char STRING35;int count; /*字符串出現(xiàn)的次數(shù)*/int xiabao; /*字符數(shù)組位置的下標(biāo)*/; struct MAX_TEN MAX10;struct MAX_TEN MIN;struc

7、t DocumentNode /*文件結(jié)點(diǎn)*/char ch; /*存放某個(gè)單詞的一個(gè)字符*/int number; /*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/struct DocumentNode* pt26; /*指向后繼的字母的26個(gè)指針*/struct Locationn *next;/*連接以該字符為結(jié)束的單詞所在的位置*/; typedef struct DocumentNode *Link_DocumentNode;Link_DocumentNode ROOT301; /*300個(gè)根節(jié)點(diǎn)指針,零號(hào)單元不用*/ struct Locationn /*單詞在文件中的位置*/int num

8、; struct Locationn *next; ; struct WORD /*單詞鏈表結(jié)構(gòu)*/char strr35;struct WORD *next; typedef struct char *base;char *top;int stacksize;SQSTACK;SQSTACK S,T;2、每個(gè)模塊的分析：（1）主程序模塊：void main()printf("*基本型問(wèn)題*n");CREAT_DicTree();/*第一題，讀入vocabulary文件，建立存放單詞的字典樹(shù)*/printf("The First problem has been s

9、olved,a dictionary tree has been buildtn");OPEN_SearchWordInVocabulary();/*第二題，生成SearchWordInVocabulary_Result.txt*/printf("The Second problem has been solved,SearchWordInVocabulary_Result.txt formed n");printf("*擴(kuò)展型問(wèn)題*n");OPEN_TotPrefixWord();/*第三題，生成TotPrefixWord_Result.tx

10、t*/printf("The Third problem has been solved,TotPrefixWord_Result.txt formed n");OPEN_PrefixFrequence();/*第四題，生成PrefixFrequence_Result.txt*/printf("The Forth problem has been solved,PrefixFrequence_Result.txt formed n");OPEN_MostFrequenceWord();/*第五題，生成MostFrequenceWord.txt*/prin

11、tf("The Fifth problem has been solved,MostFrequenceWord.txt formden");printf("*高級(jí)型問(wèn)題*n");CREAT_DocumentTree();/*第六題，讀入Document文件，建立存放文件的樹(shù)*/printf("The Sixth problem has been solved,WordInDocument_Result.txt formedn");（2）構(gòu)建棧模塊：SQSTACK Creat() /*創(chuàng)建空棧*/SQSTACK s;s.base=(ch

12、ar*)malloc(stack_in_size*sizeof(char);s.top=s.base;s.stacksize=stack_in_size;return s; /*全局變量棧*/char pop(SQSTACK &s) /*出棧*/ char e;if(s.top=s.base)return ERROR;e=*(-s.top);return e;void push(SQSTACK &s,char e) /*入棧*/if(s.top-s.base>=s.stacksize)s.base=(char*)realloc(s.base,(s.stacksize+st

13、ackincrement )*sizeof(char);s.top=s.base+s.stacksize;s.stacksize+=stackincrement;*s.top=e;s.top=s.top+1;int isempty(SQSTACK s) /*判斷棧是否為空*/if(s.base=s.top)return 1;else return 0;（3）構(gòu)造字典樹(shù)模塊：Link_TreeNode creat() /*創(chuàng)建樹(shù)結(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針*/int i;Link_TreeNode pt;pt=(Link_TreeNode)malloc(sizeof(TreeNode);pt-&

14、gt;number=0;for(i=0;i<26;i+)pt->pti=NULL;return pt;void CREAT_DicTree() /*創(chuàng)建字典樹(shù)*/root=creat();Link_TreeNode q;FILE *fp;char *p;int ctmp;int jieshu;char str35; /*存放從文件中讀入的單詞*/if(fp=fopen("vocabulary.txt","r")=NULL)printf("cannot open vocabulary.txtn");while(1) jies

15、hu=fscanf(fp,"%s",str);/*從文件中讀入字符串*/q=root; if(jieshu=-1) break; else p=str;while(*p!='0') ctmp=*p-97;if(q->ptctmp!=NULL)q=q->ptctmp; else q->ptctmp=creat();q=q->ptctmp;q->ch=*p;p+;if(*p='0') q->number+;break; （4）構(gòu)建文件數(shù)模塊：Link_DocumentNode CREAT()/*創(chuàng)建一個(gè)文件型的

16、數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針*/int i;Link_DocumentNode p;p=(Link_DocumentNode)malloc(sizeof(struct DocumentNode);p->number=0;for(i=0;i<26;i+)p->pti=NULL;p->next=NULL; /*文件初始化*/return p;void CREAT_DocumentTree() /*讀入文件，創(chuàng)建文件樹(shù)*/Link_DocumentNode q;struct Locationn *LL;FILE *fp;char *p;int ctmp;int jie

17、shu;int Location; /*定位單詞在文章中的位置*/int k; char str35; /*存放從文件中讀入的單詞*/if(fp=fopen("Document.txt","r")=NULL)printf("cannot open Document.txtn");while(1) jieshu=fscanf(fp,"%s",str);if(jieshu=-1) break; /*文件中單詞已讀完*/if(!strcmp(str,"Document")fscanf(fp,"

18、;%d",&k);ROOTk=CREAT();Location=1;fscanf(fp,"%s",str);q=ROOTk;p=str;while(*p!='0') /*處理每個(gè)單詞*/ctmp=*p-97;if(q->ptctmp!=NULL)q=q->ptctmp;elseq->ptctmp=CREAT();q=q->ptctmp;q->ch=*p;p+;if(*p='0') q->number+;if(q->next=NULL) LL=(struct Locationn *)m

19、alloc(sizeof(struct Locationn);LL->num=Location;q->next=LL;LL->next=NULL;Location+;break;else LL=q->next;while(LL->next!=NULL)LL=LL->next;LL->next=(struct Locationn *)malloc(sizeof(struct Locationn);LL=LL->next;LL->next=NULL;LL->num=Location;Location+;break; （5）程序使用的函數(shù)：

20、SQSTACK Creat()char pop(SQSTACK &s)void push(SQSTACK &s,char e)int isempty(SQSTACK s)Link_TreeNode creat()void CREAT_DicTree()int Search(char str,Link_TreeNode root)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

21、EN(Link_TreeNode p)Link_DocumentNode CREAT()void CREAT_DocumentTree()int Search_Doc(char str,Link_DocumentNode root)void SORT_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 WORD *head,int length,FILE *fp)void OPEN_SearchWordInVocabulary()void OPEN_TotPrefixWord()void OPEN_PrefixFrequence()void OPEN_MostFrequenceWord()void main()3、數(shù)據(jù)結(jié)構(gòu)示意圖：ROOT(a,b,c,d.z)(a,b,c,d.z)(a,b,c,d.z) 26個(gè)孩子 。每個(gè)樹(shù)結(jié)點(diǎn)有26個(gè)孩子四 使用說(shuō)明、測(cè)試分析及結(jié)果1、程序