《数据结构C++版课程设计报告.doc》由会员分享，可在线阅读，更多相关《数据结构C++版课程设计报告.doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计报告姓 名： 学 号： 专 业： 联系电话： E m a il: 目录报告一 拼写检测器31.实验题目32.问题描述33.概要设计34.详细设计45.测试结果及分析66.源代码8报告一 拼写检测器1. 实验题目拼写检测器（Speller checker）2. 问题描述1. load the words in the dictionary file（加载字典文件） 2 .read the text file to be checked （读取被检测文件）3. look up each word from the text file in the dictionary （逐个单词的
2、检测其拼写）4. print out the misspelled words in alphabetical order with their line numbers.（按字典顺序打印出错误的单词及其行号）例如某被检测文件内容如下：显然第二行的laanguage和第六行的ammong拼写错误，输出应该：ammong 6laanguage 23. 概要设计（1） 字典存储结构选择由于所有的单词的长短不一，单词中字母重复的部分很多，如果用数组存储字典的话很浪费空间，所以考虑用树存储字典，相同部分只存储一次，每一棵树只存储相同字母开头的所有单词，从上往下，依次存储，孩子的脚标与字母对应（0-25
3、号树的树根分别存放A-Z，26-51号树的树根分别存放a-z，其孩子也是一样）。（2） 树的ADT 定义：ADT DTree数据对象：D=ai | ai属于ElemSet，i=1，2，n n=0数据关系：若D为空集，则树为空；若紧含一个数据元素，则数据关系为空，否则：1. D中仅有一个称为跟（root）的数据元素，关系R没有前驱。2. 除根结点外，其余结点划分m个互不相交的子集，对任意的子集Di，属于R。基本操作：InitTree(& T); /建立空树DestroyTree（& T）； /销毁树Root(T) ; /求树跟Insert（&T，x）； /将元素x插入树中Chile（T，x，i）
4、；/求x结点的第i个孩子ADT DTree（3） 排序存储结构选择若选用数组，排序的时间复杂度很高，其单词长短不一，选用链表。（4） 链表抽象数据定义ADT LinkList数据对象：D=ai| ai属于ElemSet，i=1，2，n n=0数据关系：R=|ai-1,ai属于D，i=1，2，n n=0基本操作：Init（&L）；/构造一个空链表InsertInOrder（&L，x）；/将元素插入有序表中使之仍然有序DisPlay（）；/输出结点信息ADT LinkList；（5） 其他函数1） 主函数main（）。2） 建字典函数CreateDTree（）。3） 检测拼写函数Checkspel
5、l（）。4. 详细设计树存储字典，每个单词的字母是一个结点，而链表存放单词及行号，用WordsLine结构体单词及行号，定义结点类ListNode、链表类LinkList、树结点类DTreeNode、树类DTree。（1） Stuctstruct WordsLine/结点类，存放错误的单词及其行号string word;int LineNumber;（2） 链表结点类class ListNode /结点类定义friend class LinkList; /声明链表类LinkList为友元类private: WordsLine data; /结点的数据域ListNode* next; /结点的后
6、继指针域，存放后继结点的地址public: ListNode();/构造函数 ListNode(const WordsLine e):data(e),next(NULL) /构造函数 WordsLine& GetData()return data; /返回结点的数据值 ListNode* GetNext()return next; /返回结点的指针值 void SetData(WordsLine & e)data=e; /设置结点的数据值 void SetNext(ListNode* ptr)next=ptr; /设置结点的指针值 void DisPlay();/输出结点的信息;（3） 链表类
7、class LinkList /链表类定义 friend class ListNode;private:ListNode *head; /链表的头指针public:LinkList()head=new ListNode(); /构造函数，建立带头结点的空链表LinkList(WordsLine& e)head=new ListNode(e); /构造函数LinkList()LinkListClear();delete head; /析构函数，删除单链表void LinkListClear();/将线性链表置为空表ListNode* Head()constreturn head;void Ins
8、ertInOrder(WordsLine wordsLine); /插入元素后使链表依然有序递增bool IsEmpty(void)constreturn head-next=NULL; void DisPlay();/输出所有结点信息;/-（4） 树结点类class DTreeNodefriend class DTree;char m_word; /每个单词的各个字母DTreeNode* (m_tp52);/52个孩子，指向个大小写字母public: DTreeNode(); /构造函数DTreeNode(char word);/构造函数DTreeNode(char word,DTreeNo
9、de *tp); /构造函数char Getm_word()return m_word; /返回结点元素DTreeNode*GetChild(char word);/返回当前结点指向字符word的孩子bool ExistNode(char word);/判断当前节点有无存放x的孩子;（5） 树类class DTreeprivate:DTreeNode* root;/树根public:DTree():root(NULL)/构造函数DTree(char word)root=new DTreeNode(word);/构造函数,构造以字母word为元素的根结点DTreeNode* GetRoot()r
10、eturn root;/返回根结点int GetPosition(char word);/返回待插入元素word的位置void InsertWord(char* word);/将单词word插入树中bool ExistWord(const char *word);/判断单词word是否存在;5. 测试结果及分析程序名为speller.exe，运行环境为Windows，在VC+6.0下测试通过。程序执行后显示：输入字典文件后：输入被测试文件：再从一个英文网站上copy一段，将一些单词故意改错进行测试：文件内容为：测试结果为：由测试可以看出，程序的拼写检测功能还是很强大（加载了4962个单词到词典
11、）6. 源代码/ListNode.h#ifndef HEAD_LINKNODE#define HEAD_LINKNODE/-#include/-using namespace std;/-class LinkList;struct WordsLine/结点类，存放错误的单词及其行号string word;int LineNumber;class ListNode /结点类定义friend class LinkList; /声明链表类LinkList为友元类private: WordsLine data; /结点的数据域 ListNode* next; /结点的后继指针域，存放后继结点的地址pu
12、blic: ListNode();/构造函数 ListNode(const WordsLine e):data(e),next(NULL) /构造函数 WordsLine& GetData()return data; /返回结点的数据值 ListNode* GetNext()return next; /返回结点的指针值 void SetData(WordsLine & e)data=e; /设置结点的数据值 void SetNext(ListNode* ptr)next=ptr; /设置结点的指针值 void DisPlay();/输出结点的信息;ListNode:ListNode()data
13、.LineNumber=0;next=NULL; void ListNode:DisPlay()coutdata.word data.LineNumberendl;#endif/=/LinkList.h#ifndef HEAD_LINKLIST#define HEAD_LINKLIST/-#include#includeListNode.h#include/-using namespace std;/-class LinkList /链表类定义 friend class ListNode;private:ListNode *head; /链表的头指针public:LinkList()head=
14、new ListNode(); /构造函数，建立带头结点的空链表LinkList(WordsLine& e)head=new ListNode(e); /构造函数LinkList()LinkListClear();delete head; /析构函数，删除单链表void LinkListClear();/将线性链表置为空表ListNode* Head()constreturn head;void InsertInOrder(WordsLine wordsLine); /插入元素后使链表依然有序递增bool IsEmpty(void)constreturn head-next=NULL; voi
15、d DisPlay();/输出所有结点信息;/-void LinkList:LinkListClear()ListNode *p,*q;p=head-next;while(p) q=p-next;delete p;p=q;head-next=NULL;void LinkList:InsertInOrder(WordsLine wordsLine)ListNode *s=new ListNode(wordsLine);ListNode *p=head;while(p-next)/寻找当wordsLine的单词刚好大于当前结点的单词的结点/如果找到刚好大于的结点，插入if(strcmp(s-dat
16、a.word.c_str(),p-next-data.word.c_str()next-next)p=p-next;else break;/插入s-next=p-next;p-next=s;void LinkList:DisPlay()/调用结点类的成员函数ListNode:DisPlay()ListNode *p=head-next;if(!p) /表空则表明所有单词拼写正确，不用输出，返回程序coutAll words are spelled correctly!endl;return; /否则输出错误的单词信息coutThe incorrectly spelled words in al
17、phabetical order with their linenumber are:endl;coutDisPlay();p=p-next;coutendl;#endif/=/ DTreeNode.h#includeusing namespace std;class DTree;class DTreeNodefriend class DTree;char m_word; /每个单词的各个字母DTreeNode* (m_tp52);/52个孩子，指向个大小写字母public: DTreeNode(); /构造函数DTreeNode(char word);/构造函数DTreeNode(char
18、word,DTreeNode *tp); /构造函数char Getm_word()return m_word; /返回结点元素DTreeNode*GetChild(char word);/返回当前结点指向字符word的孩子bool ExistNode(char word);/判断当前节点有无存放x的孩子;DTreeNode:DTreeNode()/构造函数m_word=0; for(int i=0;i52;i+) m_tpi=NULL;DTreeNode:DTreeNode(char word)/构造函数m_word=word;for(int i=0;i=A & word=A & word=
19、Z)?word%A:26+(word%a);return m_tpchild!=NULL;/DTree.h#include#include DTreeNode.husing namespace std;class DTreeprivate:DTreeNode* root;/树根public:DTree():root(NULL)/构造函数DTree(char word)root=new DTreeNode(word);/构造函数,构造以字母word为元素的根结点DTreeNode* GetRoot()return root;/返回根结点int GetPosition(char word);/返回
20、待插入元素word的位置void InsertWord(char* word);/将单词word插入树中bool ExistWord(const char *word);/判断单词word是否存在;void DTree:InsertWord(char* word)/将单词word插入树中，相同的树中重复部分只存一次if(!word | *word =0) return;if(root=NULL | root-m_word=0) root=new DTreeNode(*word);DTreeNode* tmp=root;if(tmp)word+;while(tmp)/将单词word从第一个字母开
21、始与root比较顺着相同/的结点走，直到下一个结点元素与单词下一个字母不同if(tmp-ExistNode(*word)tmp=tmp-GetChild(*word);word+;else break;while(word&*word!=0)/将所有没有的部分插入树中int child=(*word=A & *wordm_tpchild=new DTreeNode(*word);tmp=tmp-m_tpchild;word+;bool DTree:ExistWord(const char *word)/判断单词word是否存在DTreeNode* tmp=root;if(tmp&tmp-m_w
22、ord=(*word)/如果第一个字母与根结点值不同为falseword+;while(word&*word!=0&tmp&tmp-ExistNode(*word)/将单词word从第一个字母开始与root比较,顺着相同/的结点走，直到word结束且tmp!=0则为真tmp=tmp-GetChild(*word);word+;if(*word!=0) return false;else return true;else return false;/speller.cpp#include#include#include#include#includeDTree.h#includeLinkList
23、.h/-using namespace std;/-LinkList L;/用一个链表储存错误的单词（方便排序）/-DTree m_dTree52;/用一个数组存放所有树，下标与根结点字母对应/-void CreateDTree();/加载字典文件，创建字典void CheckSpell();/检测文档拼写，将错误的排序/-void main()CreateDTree();CheckSpell();L.DisPlay();/调用链表成员函数，将所有错误的单词信息输出system(pause);/暂停，便于用户查看屏幕上输出的错误单词的信息void CreateDTree()/加载字典文档/-s
24、tring file;cout请输入字典文件（包括完整路劲）:file;ifstream in(file.c_str();cout字典加载中请等待！ch) wordi=ch;i+;wordi=0;int pos_word;/定位单词存放在哪颗树中（先存大写字母开头的）/0-25号树的树根分别存放A-Z，-51号树的树根分别存放a-zpos_word=(*word=A & *word=Z)?*word%A:26+(*word%a);m_dTreepos_word.InsertWord(word);void CheckSpell()/加载被检测的文档/-string file;cout请输入要检测的文件（包括完整路劲）:file;ifstream in(file.c_str();cout拼写检测中请等待！s)char*tmp=(char*)s.c_str();/string转char*while(*tmp!=0)int flag=1;/用来标记当行string中是否含多个单词。为表示只有一个char*word=tmp;/指向while(*tmp=A&*tmp=a&*tmp=A & *word=A & *word=A&*tmp=a&*tmp=z) tmp+; /=