数据结构次项目报告.pdfVIP

1问题分析和系统整体设计

1.1问题分析

接下来我们给自己问题是：

1)用什么样的数据结构保存每个词条对应的页码？

2)如何定义不同词条的顺序关系？

3)怎样快速的将词条排序

我们问题解决方案是：

1)用优先队列（堆结构）来保存每个词条对应的页码。用一种数学上闭区

间的形式来表示页码

2)定义一个带有__lt__的类（按要求分情况定义）保存词条的字符串，用一

个字典将这个类与优先队列对应起来。（其实完全可以自己定义符号、字

母转化为整数的函数，然后自定义散列函数，消解。不过既然python

给了字典的实现，所以就不那么麻烦了。）

3)将表中的词条压入优先队列，然后依次弹出得到的就是有序的关键字序

列。

1.2系统整体设计

我们基于上述问题分析中讨论出的相应结构的实现方式，根据项目要求，定

义了类Bracket来类比表示数学中闭区间用的方括号，定义了类Item来实现词

条的顺序比较，定义了类PageInf来实现整本书索引的排序。

定义函数main来实现一本书的索引生成的一般操作。主要包括两大环节：

首先整理和页码，然后将词条与对应页码输出

2数据结构和程序结构设计

2.1数据结构设计

1)页码的实现

我们自定义了Bracket的类，来类比数学中闭区间的方括号括号。这个类有

两个关键值：page和sigh。page表示这个括号代表的页码，sigh反映这是左括

号还是右括号。

2)一个词条对应页码的实现

之前考虑对每个词条一个大小为书的总页数的01表，表示该词条是否

在该页出现。这样能够使更新页码的操作在常量时间内完成。然而这样的设计在

输出时每个词条都需要整本书页码p的时间复杂度，保存时也需要p的空间复

杂度。而一个词条出现的索引相对于整本书的总页码是非常小的，这样的设计不

尽合理。

接着，我们就想到模拟数学中的闭区间。一个词条对应的页码就类似于有限

多个闭区间的并集，添加新的页码就相当于集合的求并。于是我们定义了Bracket。

有序过程是一个O(N^2)的时间复杂度过程，觉得排序过程的时间复杂度下

限时O(NlogN)，我们认为应该还有更优的数据结构。

我们我们并不需要在词条的更新过程中始终保持页码的顺序，只需要

在输出时顺序输出就好。于是我们决定使用基于堆的优先队列来实现这一结构，

这样，我们使得每个词条页码的整理操作的时间复杂度降低到了O(NlogN)。

3)所有词条的组织

我们定义了类Item实现词条的排序。定义方法priority来区分不同词条的

种类。定义casevalue方法返回当前词条的首字母信息。

2.2程序结构设计

1)项目模块的分划

整个项目分为四个类的定义和一个main函数。定义了类Bracket，

其中的方法__lt__用于确定括号的优先次序。定义了类Item：定义了其中的方法

priority反映的种类；__lt__来比较的优先级；casevalue来反映单

词类的首字母情况。在类PageInf中，我们定义了方法__str__用于实现相

应页码的输出。

在main中，调用个各类的方法。首先，从一个文件中索引命令通过gen

函数将输入的索引转化成为Bracket的有关参量。根据，将这些Bracket

的类对应的加入优先队列中。当索引更新完毕后，将所有的压入、弹出一

个优先队列，然后就顺序得到了相应的。再将和页码按指定形式输

出，完成项目要求工作。

3关键问题和算法

3.1关键问题1

如何将给出的索引命令转化为我们上述提及的Bracket的相关参数。

算法设计：