西工大数据结构课程设计Tire TreeWord格式.docx
《西工大数据结构课程设计Tire TreeWord格式.docx》由会员分享,可在线阅读,更多相关《西工大数据结构课程设计Tire TreeWord格式.docx(14页珍藏版)》请在冰点文库上搜索。
(3)给定一个单词,按字典序输出字典Dictionary中所有以这个单词为前缀的单词。
例如,如果字典T={a,aa,aaa,b,ba},如果你输入a,那么输出应该为{a,aa,aaa}。
(4)给定一个单词,输出在Dictionary中以这个单词为前缀的单词的出现频率最高的10个单词,对于具有相同出现次数的情况,按照最近(即最后)插入的单词优先级比较高的原则输出。
(5)输出Dictionary中出现次数最高的10个单词。
3)高级型问题
(6)现在我们有一些Document,每个Document由一些单词组成,现在的问题就是给你一个word,检索出哪些Document包含这个word,输出这些Document的DocumentID(就如同搜索引擎一样,即输入一些关键字,然后检索出和这些关键字相关的文档)。
(7)在第(6)问中,我们只考虑了一个word在哪些Document中的情况,我们进一步考虑2个相邻word的情况,检索出同时包含这两个相邻word的DocumentID。
4)挑战型问题
(8)现在我们再对(7)的问题进行扩展,把(7)中的只检索相邻2个word推广到可以检索多个word(即连续的k个word,其中k>
=2),检索出同时包含k个连续word的DocumentID。
我解决了前六个问题。
一、需求分析
1.本程序演示中,程序自动读取目标文件,生成需要的文件。
2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入相应数据。
3.程序执行的主要命令包括:
(1)构建栈;
(2)构造字典树;
(3)构建文件数;
(4)树的查找;
(5)结束。
二概要设计
为实现上述算法,选择字典树为本程序的存储结构。
1、本程序包括三个模块:
(1)主程序模块;
(2)构建栈模块;
(3)构造字典树模块;
(4)构建文件数模块;
(5)树的遍历模块;
2、模块调用关系图
主程序模块
构建栈模块
构造字典树模块
构建文件数模块
树的遍历模块
三详细设计
1、定义存储链表结构:
(1)定义字典树与文件数结构:
#include<
stdio.h>
string.h>
stdlib.h>
malloc.h>
#defineNULL0
#defineERROR-1
#definestack_in_size100
#definestackincrement10
structTreeNode/*树结点*/
{
charch;
intnumber;
/*以该字符为结束的单词出现的个数*/
structTreeNode*pt[26];
/*指向后继的字母的26个指针*/
};
structTreeNode*root;
typedefstructTreeNode*Link_TreeNode;
structMAX_TEN/*存放出现频率最高的十个单词数据结构*/
{
charSTRING[35];
intcount;
/*字符串出现的次数*/
intxiabao;
/*字符数组位置的下标*/
structMAX_TENMAX[10];
structMAX_TENMIN;
structDocumentNode/*文件结点*/
/*存放某个单词的一个字符*/
structDocumentNode*pt[26];
structLocationn*next;
/*连接以该字符为结束的单词所在的位置*/
typedefstructDocumentNode*Link_DocumentNode;
Link_DocumentNodeROOT[301];
/*300个根节点指针,零号单元不用*/
structLocationn/*单词在文件中的位置*/
intnum;
structWORD/*单词链表结构*/
charstrr[35];
structWORD*next;
typedefstruct
char*base;
char*top;
intstacksize;
}SQSTACK;
SQSTACKS,T;
2、每个模块的分析:
(1)主程序模块:
voidmain()
printf("
*****************基本型问题************************\n"
);
CREAT_DicTree();
/*第一题,读入vocabulary文件,建立存放单词的字典树*/
TheFirstproblemhasbeensolved,adictionarytreehasbeenbuildt\n"
OPEN_SearchWordInVocabulary();
/*第二题,生成SearchWordInVocabulary_Result.txt*/
TheSecondproblemhasbeensolved,SearchWordInVocabulary_Result.txtformed\n"
*****************扩展型问题************************\n"
OPEN_TotPrefixWord();
/*第三题,生成TotPrefixWord_Result.txt*/
TheThirdproblemhasbeensolved,TotPrefixWord_Result.txtformed\n"
OPEN_PrefixFrequence();
/*第四题,生成PrefixFrequence_Result.txt*/
TheForthproblemhasbeensolved,PrefixFrequence_Result.txtformed\n"
OPEN_MostFrequenceWord();
/*第五题,生成MostFrequenceWord.txt*/
TheFifthproblemhasbeensolved,MostFrequenceWord.txtformde\n"
*****************高级型问题************************\n"
CREAT_DocumentTree();
/*第六题,读入Document文件,建立存放文件的树*/
TheSixthproblemhasbeensolved,WordInDocument_Result.txtformed\n"
}
(2)构建栈模块:
SQSTACKCreat()/*创建空栈*/
SQSTACKs;
s.base=(char*)malloc(stack_in_size*sizeof(char));
s.top=s.base;
s.stacksize=stack_in_size;
returns;
}/*全局变量栈*/
charpop(SQSTACK&
s)/*出栈*/
chare;
if(s.top==s.base)returnERROR;
e=*(--s.top);
returne;
voidpush(SQSTACK&
s,chare)/*入栈*/
if(s.top-s.base>
=s.stacksize)
{s.base=(char*)realloc(s.base,
(s.stacksize+stackincrement)*sizeof(char));
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*s.top=e;
s.top=s.top+1;
intisempty(SQSTACKs)/*判断栈是否为空*/
if(s.base==s.top)
return1;
else
return0;
(3)构造字典树模块:
Link_TreeNodecreat()/*创建树结点,并返回指向该节点的指针*/
inti;
Link_TreeNodept;
pt=(Link_TreeNode)malloc(sizeof(TreeNode));
pt->
number=0;
for(i=0;
i<
26;
i++)
pt->
pt[i]=NULL;
returnpt;
voidCREAT_DicTree()/*创建字典树*/
root=creat();
Link_TreeNodeq;
FILE*fp;
char*p;
intctmp;
intjieshu;
charstr[35];
/*存放从文件中读入的单词*/
if((fp=fopen("
vocabulary.txt"
"
r"
))==NULL)
printf("
cannotopenvocabulary.txt\n"
while
(1)
{
jieshu=fscanf(fp,"
%s"
str);
/*从文件中读入字符串*/
q=root;
if(jieshu==-1)
break;
else
{
p=str;
while(*p!
='
\0'
)
{
ctmp=*p-97;
if(q->
pt[ctmp]!
=NULL)
q=q->
pt[ctmp];
else
{
q->
pt[ctmp]=creat();
ch=*p;
}
p++;
if(*p=='
)
{
number++;
break;
}
}
}
(4)构建文件数模块:
Link_DocumentNodeCREAT()/*创建一个文件型的数据结构结点,并返回指向该节点的指针*/
Link_DocumentNodep;
p=(Link_DocumentNode)malloc(sizeof(structDocumentNode));
p->
{
p->
next=NULL;
/*文件初始化*/
returnp;
voidCREAT_DocumentTree()/*读入文件,创建文件树*/
Link_DocumentNodeq;
structLocationn*LL;
intLocation;
/*定位单词在文章中的位置*/
intk;
Document.txt"
cannotopenDocument.txt\n"
/*文件中单词已读完*/
if(!
strcmp(str,"
Document"
))
{
fscanf(fp,"
%d"
&
k);
ROOT[k]=CREAT();
Location=1;
q=ROOT[k];
p=str;
while(*p!
)/*处理每个单词*/
ctmp=*p-97;
if(q->
q=q->
else
{
q->
pt[ctmp]=CREAT();
p++;
if(*p=='
next==NULL)
LL=(structLocationn*)malloc(sizeof(structLocationn));
LL->
num=Location;
next=LL;
Location++;
else
LL=q->
next;
while(LL->
next!
LL=LL->
next=(structLocationn*)malloc(sizeof(structLocationn));
LL=LL->
}
(5)程序使用的函数:
SQSTACKCreat()
s)
s,chare)
intisempty(SQSTACKs)
Link_TreeNodecreat()
voidCREAT_DicTree()
intSearch(charstr[],Link_TreeNoderoot)
Link_TreeNodeGet_Last_Link(charstr[])
boolOutPrint(Link_TreeNodep,FILE*fp)
voidRECHANGE_MIN(chartepp[],intcunt)
boolGOT_MAX_TEN(Link_TreeNodep)
Link_DocumentNodeCREAT()
voidCREAT_DocumentTree()
intSearch_Doc(charstr[],Link_DocumentNoderoot)
voidSORT_MAX_Ten()
structWORD*Creat_two_word_link(charstr1[],charstr2[])
structWORD*Creat_multi_word_link(intlength,FILE*fp)
voidSearch_Match_Word(structWORD*head,intlength,FILE*fp)
voidOPEN_SearchWordInVocabulary()
voidOPEN_TotPrefixWord()
voidOPEN_PrefixFrequence()
voidOPEN_MostFrequenceWord()
3、数据结构示意图:
‘
26个孩子
。
。
每个树结点有26个孩子
四使用说明、测试分析及结果
1、程序使用说明:
(1)本程序的运行环境为VC6.0。
(2)进入演示程序后即显示的提示信息:
输出:
*****************基本型问题************************
TheFirstproblemhasbeensolved,adictionarytreehasbeenbuildt
TheSecondproblemhasbeensolved,SearchWordInVocabulary_Result.txtformed
*****************扩展型问题************************
TheThirdproblemhasbeensolved,TotPrefixWord_Result.txtformed
TheForthproblemhasbeensolved,PrefixFrequence_Result.txtformed
TheFifthproblemhasbeensolved,MostFrequenceWord.txtformed
*****************高级型问题************************
TheSixthproblemhasbeensolved,WordInDocument_Result.txtformed
2、运行界面:
五、实验总结
这次实验题目涉及了数据结构学习中的多种结构,要求对各种数据的存储与处理的方法比较熟悉。
在实验中,由于这学期没有很认真的学习这门课,平常实验课写程序也不是很认真,以至于解决前两个问题还比较轻松,但是从三个问题开始我就遇到了很大困难,在数据的处理过程中遇到了不小的麻烦,导致后来调试的时候浪费了很多时间。
同时,程序的时间复杂度耗时,占用内存较大,这说明程序的结构不够灵巧,我会再次认真的自己学习这门课程,希望在以后的学习中能把程序写得更好。
教师评语:
实验成绩:
指导教师签名:
批阅日期: