西工大数据结构课程设计TireTree

1、2011-2012年数据结构课程设计实验报告学院： 班级： 姓名: 学号：邮箱：2012年1月5日课程设计实验报告班 级: 学 号: 姓 名: E-mail: 日 期:实验题目: 字典树实验目的：设计合适的数据结构，建立字典树，解决文件中单词的搜索统计问题。实验内容：现在有一个英文字典（每个单词都是由小写的'a'-'z'组成），单词量很大，达到100多万的单词，而且还有很多重复的单词。此外，我们现在还有一些 Document，每个Document 包含一些英语单词。 针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下

2、面的问题和分析自己算法的时间复杂度。 1）基本型问题 （1）选择合适的数据结构，将所有的英文单词生成一个字典Dictionary。 （2）给定一个单词，判断这个单词是否在字典 Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO。2）扩展型问题 （3）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T=a,aa, aaa, b, ba, 如果你输入 a,那么输出应该为a, aa, aaa。（4）给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，

3、按照最近（即最后）插入的单词优先级比较高的原则输出。（5）输出Dictionary中出现次数最高的10个单词。3）高级型问题 （6）现在我们有一些Document，每个Document 由一些单词组成，现在的问题就是给你一个word，检索出哪些 Document包含这个 word，输出这些Document的DocumentID（就如同搜索引擎一样，即输入一些关键字，然后检索出和这些关键字相关的文档）。（7）在第（6）问中，我们只考虑了一个word 在哪些Document中的情况，我们进一步考虑2个相邻word的情况，检索出同时包含这两个相邻word的DocumentID。4）挑战型问题 （8）

4、 现在我们再对（7）的问题进行扩展，把（7）中的只检索相邻 2个word 推广到可以检索多个word（即连续的k个word，其中k>=2），检索出同时包含k个连续word 的DocumentID。我解决了前六个问题。一、需求分析1本程序演示中，程序自动读取目标文件，生成需要的文件。2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据。3程序执行的主要命令包括：（1）构建栈；（2）构造字典树；（3）构建文件数；（4）树的查找；（5）结束。二 概要设计为实现上述算法，选择字典树为本程序的存储结构。1、本程序包括三个模块：（1）主程序模块

5、；（2）构建栈模块；（3）构造字典树模块；（4）构建文件数模块；（5）树的遍历模块；2、模块调用关系图主程序模块构建栈模块构造字典树模块构建文件数模块树的遍历模块三 详细设计1、定义存储链表结构：（1）定义字典树与文件数结构：#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 /*树结点*/ char ch; int number; /*以该字符为结束的单词出现的个数*/struct TreeNode* pt26; /*指向后继的字母的26个指针*/; struct TreeNode *root;typedef struct TreeNode *Link_TreeNode;struct MAX_TEN /*存放出现频率最高的十个单词数据结构*/char STRING35;int count; /*字符串出现的次数*/int xiabao; /*字符数组位置的下标*/; struct MAX_TEN MAX10;struct MAX_TEN MIN;struc

7、t DocumentNode /*文件结点*/char ch; /*存放某个单词的一个字符*/int number; /*以该字符为结束的单词出现的个数*/struct DocumentNode* pt26; /*指向后继的字母的26个指针*/struct Locationn *next;/*连接以该字符为结束的单词所在的位置*/; typedef struct DocumentNode *Link_DocumentNode;Link_DocumentNode ROOT301; /*300个根节点指针,零号单元不用*/ struct Locationn /*单词在文件中的位置*/int num

8、; struct Locationn *next; ; struct WORD /*单词链表结构*/char strr35;struct WORD *next; typedef struct char *base;char *top;int stacksize;SQSTACK;SQSTACK S,T;2、每个模块的分析：（1）主程序模块：void main()printf("*基本型问题*n");CREAT_DicTree();/*第一题，读入vocabulary文件，建立存放单词的字典树*/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("*扩展型问题*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("*高级型问题*n");CREAT_DocumentTree();/*第六题，读入Document文件，建立存放文件的树*/printf("The Sixth problem has been solved,WordInDocument_Result.txt formedn");（2）构建栈模块：SQSTACK Creat() /*创建空栈*/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）构造字典树模块：Link_TreeNode creat() /*创建树结点，并返回指向该节点的指针*/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() /*创建字典树*/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）构建文件数模块：Link_DocumentNode CREAT()/*创建一个文件型的

16、数据结构结点，并返回指向该节点的指针*/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() /*读入文件，创建文件树*/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') /*处理每个单词*/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）程序使用的函数：

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、数据结构示意图：ROOT(a,b,c,d.z)(a,b,c,d.z)(a,b,c,d.z) 26个孩子 。每个树结点有26个孩子四 使用说明、测试分析及结果1、程序