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