数据结构大作业

数据结构大作业

一、 问题描述：单词检索

现在有一个英文字典（每个单词都是由小写的'a'-'z'组成） 单词量很大，达到 120 多万的单词，而且还有很多重复的单词。 此外，我们现在还有一些 Document，每个 Document 包含一些英语单词。 针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。

1）基本型问题

（1） 选择合适的数据结构，将所有的英文单词生成一个字典 Dictionary。

（2） 给定一个单词，判断这个单词是否在字典 Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出 NO

2）扩展型问题

（3） 给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T={a,aa, aaa, b, ba}, 如果你输入 a,那么输出应该为{a, aa, aaa}。

（4） 给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10 个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出。

（5） 输出 Dictionary 中出现次数最高的 10个单词。

（6） 现在我们有一些 Document，每个 Document 由一些单词组成，现在的问题就是给你一个 word， 检索出哪些 Document包含这个 word， 输出这些Document 的DocumentID （就如同搜索引擎一样，即输入一些关键字，然后检索出和这些关键字相关的文档） 。

（7） 在第（6）问中，我们只考虑了一个 word 在哪些 Document 中的情况，我们进一步考虑 2 个相邻 word 的情况，检索出同时包含这两个相邻 word 的 DocumentID。

二、需求分析：

对于（1）问，题目要求选择适当的数据结构将一百二十多万个英文单词生成一个字典。我采用经典字典树结构进行构造，每个节点包括频度，时间，和后继二十六个指针。其中频度为单词的频度，若该字母为单词的最后一个字母，则该字母的pin为该单词的频度，否则pin为零。时间为单词最后一次出现的次序，为（4）问服务。

对于（2）问，题目要求在字典里查询指定单词，若在字典中则输出在字典中出现的次数，否则输出NO。读入字母，根据字典树进行查找。若在字典树中存在最后一个字母，且最后一个字母的频度不为零，则该单词存在，出现次数即为该字母频度。否则，该单词不存在。

对于（3）问，题目要求查找以指定单词为前缀的所有单词，并输出所有单词，若不存在，什么也不输出。我使用数组存储前缀和以此前缀为前缀的单词。若在字典树中存在这样的前缀，则从此节点按照字典顺序遍历字典树，并输出所有以此为前缀的所有单词。若不存在这样的前缀，则什么也不输出。

对于（4）问，题目要求查找以指定单词为前缀的频度最高的十个单词，并按频度高低顺序输出。若频度相同，则按照最近（即最后）插入的单词优先级比较高的原则输出。若不满十个则全部输出。我采用Node T[10]存储频度最高的前十个单词，排序使用插入排序，对频度相同的单词，比较它们的time，若time比较大，则插到前面。

对于（5）问，题目要求输出字典中频度最高的十个单词。我采用Node Top[10]存储频度最高的前十个单词，遍历字典树，按照插入排序进行排序。

对于（6）问，题目要求在若干Document中查找指定单词，若存在该单词，则输出所在Document的ID，要求输出所有存在的ID。若不存在什么也不输出。由于（6）（7）（8）问与前五问使用的文件不相同，我在编写程序时，就把前五问与后面几问分开了。我同样采用了字典树结构进行存储Document中的单词，不过字母节点变成频度、坐标和二十六个后继指针。其中坐标为单词所在Document的ID和所在Document的第几个顺序。在此问中，按照字典树查找指定单词，并输出单词所在Document的ID。

对于（7）问，题目要求在Document中查找两个单词组成的词组。我先将读入的词组分成两个单词，分别在字典树中查找两个单词，得到两个单词的坐标。先比较两个单词的ID，若ID相同，则比较在Document中的顺序，若前后两个单词的顺序，后一个单词比前一个单词顺序大1，则输出该ID。否则不输出。

注:此题是我从网上搜的,原题一共八问,此处只做前七问.

三、 概要设计：

1、节点设计：

前五问：typedef struct TNode

{

struct TNode *point[26];

int pin;

int time;

}TNode;

//字典树节点，pin记录单词出现次数，time记录单词最后一次出现的次序

typedef struct Node

{

char k[40];

int flag;

int time;

}Node;

//用来存前缀最高的十个单词

六七问：typedef struct node

{

int pos;

struct node *next1;

}node;

//存储单词在文件的位置

typedef struct Node

{

int id;

struct node *node1;

struct Node *next;

}Node;

//存储单词在文件的ID

typedef struct TNode

{

struct TNode *point[26];

int pin;

struct Node *loc;

}TNode;

//字典树节点

2、主函数:

一至五问：void main()

{

int i;

TNode *root;

root=(struct TNode *)malloc(sizeof (struct TNode));

for (i=0;i<26;i++)

{

root->point[i]=NULL;

}

printf("程序开始运行\n\n打开文件“vocabulary.txt”开始生成字典\n");

CreateTree(root);

printf("生成字典成功\n第一问解决\n\n\n打开文件“SearchWordInVocabulary.txt”\n开始查找单词\n");

Search(root);

printf("查找结束\n结果保存在文件“SearchWordInVocabulary_Result.txt”\n第二问解决\n\n\n打开文件“TotPrefixWord.txt”\n开始查找前缀单词\n");

Prefix(root);

printf("查找结束\n结果保存在文件“TotPrefixWord_Result.txt”\n第三问解决\n\n\n打开文件“PrefixFrequence.txt”\n开始查找前缀出现频率最高的十个单词\n");

Prefixqueue(root);

printf("查找结束\n结果保存在文件“PrefixFrequence_Result.txt”\n第四问解决\n\n\n开始查找频率最高的十个单词\n");

MostFrequence(root);

printf("查找结束\n结果保存在文件“MostFrequenceWord.txt”\n前五问解决\n\n\n");

}

六七问：void main()

{

int i;

TNode *root;

root=(struct TNode *)malloc(sizeof (struct TNode));

for (i=0;i<26;i++)

{

root->point[i]=NULL;

}

printf("程序开始运行\n\n\n打开文件“Document.txt”\n开始构造字典\n");

Create(root);

printf("字典构造结束\n打开文件“WordInDocument.txt\n开始在文件中查找单词\n");

SearchWord(root);

printf("查找结束\n结果保存在文件“WordInDocument_Result.txt”\n第六问解决\n\n\n打开文件“TwoWordInDocument.txt”\n开始在文件中查找连续的两个单词\n");

SearchTwoWord(root);

printf("查找结束\n结果保存在文件“TwoWordInDocument_Result.txt”\n第七问解决\n\n\n");

}

四、详细分析(对函数的一些注释)

一至五问：

（1） void CreateTree(TNode *root)

注：（1）读入单词，构造字典树

（2） void Search(TNode *root)

注：（2）读入要查找的单词进行查找，若在字典中存在，则输出频度。否则输出NO

（3） void Printf(TNode *item,FILE *fp2,char *a,int k)

（4） void Prefix(TNode *root)

注：（4）查找指定前缀，若存在，则在（3）中进行输出以该单词为前缀的所有单词；若不存在，什么也不输出

（5） void Printf1(TNode *item,char *a,int k,Node *T)

（6） void Prefixqueue(TNode *root)

注：（6）查找指定前缀，若存在，则在（5）中进行排序并输出频度最高的十个单词；否则什么也不输出

（7） void Most(TNode *item,int i,Node *Top,char *a)

（8） void MostFrequence(TNode *root)

注：（7）（8）遍历整个字典树，将字典中频度最高的十个单词全部输出

六七问：

（1） void Create(TNode *root)

注：（1）读入Document里面的单词，构建字典树

（2） void SearchWord(TNode *root)

注：（2）查找单词，若存在，则输出所有存在该单词的文件的ID，否则，什么也不输出

（3） Node * Search(TNode *root,char *a)

（4） void SearchTwoWord(TNode *root)

注： （4）将词组分成两个单词，在（3）中分别进行查找，再对两个单词所在文件的ID求交，然后在相同的ID下判断位置是否相邻。若相邻，则输出ID，否则什么也不输出

五、 使用说明：

本函数运行环境为dos操作系统。

六、 测试结果：

第一问：

第二问：

第三问：

第四问：

第五问：

第六问：

第七问：

本文来源：https://www.2haoxitong.net/k/doc/5ce3021aa300a6c30c229f94.html