西工大数据结构课程设计Tire Tree.pdfVIP

2011-2012年数据结构

课程设计实验报告

学院：

班级：

姓名:

学号：

邮箱：

2012年1月5日

《课程设计》实验报告

班级:学号:姓名:

E-mail:日期:

◎实验题目:字典树

◎实验目的：设计合适的数据结构，建立字典树，解决文件中单词的有哪些信誉好的足球投注网站统计问

题。

◎实验内容：现在有一个英文字典（每个单词都是由小写的a-z组成），单词

量很大，达到100多万的单词，而且还有很多重复的单词。

此外，我们现在还有一些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个单词。

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、定义存储链表结构：