1、 20112011- -20122012 年数据结构年数据结构 课程设计实验报告课程设计实验报告 学院：计算机学院 班级： 姓名: 学号： 邮箱： 年月日 课程设计实验报告课程设计实验报告 实验实验题题目目: : 字典序字典序 实验目的：实验目的：设计合适的数据结构，建立字典树，解决文件中单词的搜索统计问 题。 实验内容：实验内容：现在有一个英文字典（每个单词都是由小写的a-z组成） ，单词 量很大，达到 100 多万的单词，而且还有很多重复的单词。 此外，我们现在还有一些 Document，每个 Document 包含一些英语单词。 针对这个问题，请你选择合适的数据结构，组织这些数据，使时间
2、复杂度和空间 复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。 1 1）基本型问题）基本型问题 （1）选择合适的数据结构，将所有的英文单词生成一个字典 Dictionary。 （2）给定一个单词，判断这个单词是否在字典 Dictionary 中。如果在单词库 中，输出这个单词总共出现的次数。否则输出 NO。 2 2）扩展型问题）扩展型问题 （3）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀 的单词。例如，如果字典 T=a,aa, aaa, b, ba, 如果你输入 a,那么输出应该 为a, aa, aaa。 （4）给定一个单词，输出在 Dictio
3、nary 中以这个单词为前缀的单词的出现频 率最高的 10 个单词，对于具有相同出现次数的情况，按照最近（即最后）插入 的单词优先级比较高的原则输出。 （5）输出 Dictionary 中出现次数最高的 10 个单词。 3 3）高级型问题）高级型问题 （6）现在我们有一些 Document，每个 Document 由一些单词组成，现在的问题 就是给你一个 word，检索出哪些 Document 包含这个 word，输出这些 Document 的 DocumentID（就如同搜索引擎一样，即输入一些关键字，然后检索出和这些 关键字相关的文档） 。 （7）在第（6）问中，我们只考虑了一个 word
4、 在哪些 Document 中的情况，我 们进一步考虑 2 个相邻 word 的情况，检索出同时包含这两个相邻 word 的 DocumentID。 4 4）挑战型问题）挑战型问题 （8） 现在我们再对 （7） 的问题进行扩展， 把（7） 中的只检索相邻 2 个 word 推 广到可以检索多个 word（即连续的 k 个 word，其中 k=2） ，检索出同时包含 k 个连续 word 的 DocumentID。 我解决了前六个问题。 一、需求分析一、需求分析 1本程序演示中，程序自动读取目标文件，生成需要的文件。 2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信 息”
5、之后，由用户在键盘上输入相应数据。 3程序执行的主要命令包括： （1）构建栈；（2）构造字典树；（3）构建文件数；（4）树的查找；（5） 结束。 二二 概要设计概要设计 为实现上述算法，选择字典树为本程序的存储结构。 1、本程序包括三个模块： （1）主程序模块； （2）构建栈模块； （3）构造字典树模块； （4）构建文件数模块； （5）树的遍历模块； 2、模块调用关系图 主程序模块 构建栈模块 构造字典树模块 构建文件数模块 树的遍历模块 三三 详细设计详细设计 1、定义存储链表结构： （1）定义字典树与文件数结构： #include #include #include #include #d
6、efine NULL 0 #define ERROR -1 #define stack_in_size 100 #define stackincrement 10 struct TreeNode /*树结点*/ 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; struc
