《数据结构与算法》
课程设计说明书
题 目： 单词拼写检查器
学 院： 计算机科学与工程
专 业： 信息安全
姓 名： 李培聪
学 号： 1000360218
指导教师： 张瑞霞
2012年 0 9月08日
目 录
引言 1
1、系统概述 2
2、需求分析 2
3、详细设计 4
4、系统特色及关键技术 9
5、结论 8
参考文献 13
引言
开发背景
NotePad（记事本）是一个简单实用的文本编辑软件，它通过对TXT格式文件的操作来实现文本的创建和编辑。Windows操作系统为我们提供了一个功能完整的记事本程序，具有新建，打开，保存等系统功能与复制，粘贴，剪切，撤销，查找等基本编辑功能。然而，随着用户不断增强的对软件易用性的要求，需要记事本具有更友好的操作和功能。对于经常输入英文的用户，就迫切希望拥有一款可以对单词进行拼写检查和英文自动提示输入功能的记事本。于是，这样一款带有“英文助手”功能的增强型记事本程序应运而生。
设计目标
参照Windows记事本程序的相关设计，模仿着进行一款增强版的记事本程序。对原有的记事本功能进行改进，增加“拼写检查”与“英文自动提示输入”功能。具体目标如下：
（1）必须是图形界面，且与windows记事本保持相同界面风格。
（2）需要支持常规文档编辑
（3）具有英文单词的拼写检查能力。
（4）具有自动提示输入功能（仅限于英语单词）。
（5）实现某种数据结构，用于高效地访问字典中的单词。
运行演示
“拼写检查器”——一个增强的记事本软件
一、系统概述
带“英文助手”的增强版的记事本程序，是对原有的记事本功能进行改进，增加“拼写检查”与“英文自动提示输入”功能。原有的记事本程序仅实现基本的文字编辑功能，不够人性化。新系统将大大降低英文用户操作的复杂性，实现更多的功能，拼写检查功能极大地提高了英语文章通篇单词的准确性，自动提示功能极大地方便了用户的英文输入。“拼写检查”与“英文自动提示输入”功能作为记事本模块的子模块进行调用。当用户需要使用英文助手的时候，可以手动启用。这样既方便了英文输入用户的快捷输入，又不会对普通用户产生干扰。
软件采用高效的检索算法，使“拼写检查”与“英文自动提示输入”效率奇高，用户在使用时基本感受不出检索的时间代价。清爽的用户界面极大地提高了舒适性，令文本编辑用户倍感轻松。
二、需求分析
2.1 系统分析
2.1.1 任务
创建用户界面的记事本程序，风格模仿汽车空调工作原理windows记事本。主窗口进行文本文档的编辑，并且含有一组菜单。“拼写检查”与“英文自动提示输入”分别作为两个对话框进行子模块功能调用。需要附带一个强大的英文词典，以确保拼写检查的准确性。同时，要设计一种高效的数据结构来存放体积巨大的英文字典库，以确保单词检索的效率。
2.1.2 原则
系统性：程序是作为统一整体存在的，因此，系统设计中界面风格要一致，操作方法一致，系统的代码要统一。
可靠性：系统稳定性好，运行正确，对非法操作进行提示与控制。
高效性：保证时间复杂性尽可能小。
2.1.3 系统功能描述
新系统作为NotePad （记事本）的增强版，首先就必须拥有记事本的基础功能——记事本功能模块。
蟹膏是螃蟹的精子吗
对于记事本功能，有必要和原版记事本保持高度一致，具有如下功能：
（1）TXT文档的打开与保存。
（2）粘贴板的操作——“剪切”、“复制”、“粘贴”、“删除”。
（3）查找和替换。
（4）设置字体与自动换行
“拼写检查”功能作为子模块，以对话框的形式进行调用，具有如下功能：
（1）启动拼写检查时直接进行第一次检查。
（2）拼写检查对话框显现时，仍可以对文本文档进行编辑。
（3）在不关闭对话框的情况下可以对编辑后的文本进行“重新检查”。
（4）双击错误单词列表中的某个错误单词项目后，可以在文本编辑界面中自动定 位到选中的错误单词，并高亮显示。
“英文自动提示输入”功能也以对话框的形式进行实现，具有如下功能：
（1）输入单词的前缀部分，自动联想所有对应的后半部分，并显示在单词候选框 里面。
（2）双击候选框中单词自动将此单词插入到文本编辑界面的光标所在位置。
2.2 原理分析与数据需求
因为计算机并不具备判断“哪些单词正确，哪些单词错误”的能力，所以无法直接通过某些语句或函数调用来实现“拼写检查”与“英文自动提示输入”功能。假设计算机能够拥有地道的英国人的那种英文水平，那么我想也不需要有本程序的存在了。
如何让计算机去判断一个单词的拼写正确性，这正是本程序要解决的核心问题所在。以目前IT科技发展的现状来看，现在我们只能通过“把输入的单词与单词库每一个单词进行比较”这种方式来证明“这个单词是拼写正确的单词”。正因此，为确保准确性，我们需要一个强大的英文单词库资源的支持。为确保高效性，我们还需要一个合适的数据结构来存放单词库的数据以配合快速的检索算法。
考虑到方便后期对字典进行维护，我选择了以天山雪岭云杉林TXT文本格式保存字典数据，并把这个TXT文档作为项目的自定义资源封装到生成的EXE文件中。这样，程序就等于自带了一个“字典库”。这个“字典库”里存放了11万个英文单词，足以应对平时正常书写所包含的单词。
当我们进行“把输入的单词与单词库每一个单词进行比较”这种操作。将带来字符串的大量搜索操作。于是需要我们从数据结构的选择和算法的设计上下功夫确保检索效率。在这里我选用Trie树来存储英文词典。Trie树俗称字典树、单词查找树，是应对单词检索操作的最优秀数据结构。具体的数据结构与算法说明将在详细设计里给予详解。
2.3 开发环境
Microsoft Visual Studio 2008 SP1
With MFC
三、详细设计
本程序的设计严格遵循如下开发流程：
注：“分析系统需求”以及“收集资源”已经在之前给出，其中收集的字典资源存放在NotePad工程的res目录中。
3.1 数据结构
根据本程序的需求，对于大量的英文单词字符串的检索操作，我们需要使用Trie树这种数据结构。
Trie树，又称字典树、单词查找树、前缀树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie树利用字符串的公共前缀来节约存储空间，是一种用于快速检索的多叉树结构。其基本性质可以归纳为：
（1）根节点不包含字符，除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。
下图3-1是一个Trie结构的示意图：
由于本工程采用MFC创建，故采用类的形式定义抽象数据类型ADT：
class CTrieTree { private不同的的英文: struct CTrieTree_node //Trie树节点结构体作为Trie树类的内部成员 { char* data; //data将用来存放这个结点所对应的字符串 CTrieTree_node* branch[26]; //子树26声音笑貌个分别对应26个英文字母 CTrieTree_node(); }* root; public: CTrieTree():root(NULL){}; //Trie树类的构造函数 CTrieTree(CTrieTree& tr);心里的话 int inrt(char* word, char* entry); 文才武略//向Trie树里添加单词的方法 int arch( char* word, char* entry ); //在Trie树里查找单词是否存在的方法 int query( char* word, CListBox & lst ) ; //向CListBox动态添加单词的查询方法会议开场主持词 int traversal(CTrieTree_node *head, CListBox & lst); //用于query函数的节点遍历递归函数 }; |
|
这是本程序实现的Tire树类，其中有三个基础的重要操作，我们对它们进行彻底分析：
