<<数据结构>>课程设计>>>>
数据结构课程设计报告
一、设计题目:单词(词组)检索
现在有一个英文字典(每个单词都是由小写的'a'-'z'组成)单词量很大,达到100多万的单词,而且还有很多重复的单词。此外,我们现在还有一些Document,每个Document包含一些英语单词。针对这个问题,请你选择合适的数据结构,组织这些数据,使时间复杂度和空间复杂度尽可能低,并且解决下面的问题和分析自己算法的时间复杂度。1)基本型问题
(1)选择合适的数据结构,将所有的英文单词生成一个字典Dictionary。
(2)给定一个单词,判断这个单词是否在字典Dictionary中。如果在单词库中,输出这个单词总共出现的次数。否则输出NO。
2)扩展型问题
(3)给定一个单词,按字典序输出字典Dictionary中所有以这个单词为前缀的单词。例如,如果字典T={a,aa,aaa,b,ba},如果你输入a,那么输出应该为{a,aa,aaa}。
-1-
<<数据结构>>课程设计>>>>
(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)问,题目要求选择适当的数据结构将一百二十多万个英
文单词生成一个字典。我采用经典字典树结构进行构造,每个节点包括频度,时间,和后继二十六个指针。其中频度为单词的频度,若该字母为单词的最后一个字母,则该字母的pin为该单词的频度,否则
-2-
<<数据结构>>课程设计>>>>
pin为零。时间为单词最后一次出现的次序,为(4)问服务。