数据结构C++版课程设计报告

数据结构课程设计报告姓名：学号：专业：联系电话：Email:

目录报告一拼写检测器 31. 实验题目 32. 问题描述 33. 概要设计 34. 详细设计 45. 测试结果及分析 66. 源代码 8

报告一拼写检测器实验题目拼写检测器（Spellerchecker）问题描述1.loadthewordsinthedictionaryfile（加载字典文件）2.readthetextfiletobechecked（读取被检测文件）3.lookupeachwordfromthetextfileinthedictionary（逐个单词的检测其拼写）4.printoutthemisspelledwordsinalphabeticalorderwiththeirlinenumbers.（按字典顺序打印出错误的单词及其行号）例如某被检测文件内容如下：显然第二行的laanguage和第六行的ammong拼写错误，输出应该：ammong6laanguage2概要设计字典存储结构选择由于所有的单词的长短不一，单词中字母重复的部分很多，如果用数组存储字典的话很浪费空间，所以考虑用树存储字典，相同部分只存储一次，每一棵树只存储相同字母开头的所有单词，从上往下，依次存储，孩子的脚标与字母对应（0-25号树的树根分别存放A-Z，26-51号树的树根分别存放a-z，其孩子也是一样）。树的ADT定义：ADTDTree{数据对象：D=｛ai|ai属于ElemSet，i=1，2，……，nn>=0｝数据关系：若D为空集，则树为空；若紧含一个数据元素，则数据关系为空，否则：D中仅有一个称为跟（root）的数据元素，关系R没有前驱。除根结点外，其余结点划分m个互不相交的子集，对任意的子集Di，<root，xi>属于R。基本操作：InitTree(&T);//建立空树DestroyTree（&T）；//销毁树Root(T);//求树跟Insert（&T，x）；//将元素x插入树中Chile（T，x，i）；//求x结点的第i个孩子｝ADTDTree排序存储结构选择若选用数组，排序的时间复杂度很高，其单词长短不一，选用链表。链表抽象数据定义ADTLinkList{数据对象：D=｛ai|ai属于ElemSet，i=1，2，……，nn>=0｝数据关系：R=｛<ai-1,ai>|ai-1,ai属于D，i=1，2，……，nn>=0｝基本操作：Init（&L）；//构造一个空链表InsertInOrder（&L，x）；//将元素插入有序表中使之仍然有序DisPlay（）；//输出结点信息｝ADTLinkList；其他函数主函数main（）。建字典函数CreateDTree（）。检测拼写函数Checkspell（）。详细设计树存储字典，每个单词的字母是一个结点，而链表存放单词及行号，用WordsLine结构体单词及行号，定义结点类ListNode、链表类LinkList、树结点类DTreeNode、树类DTree。StuctstructWordsLine{//结点类，存放错误的单词及其行号 stringword; intLineNumber;};链表结点类classListNode//结点类定义{friendclassLinkList;//声明链表类LinkList为友元类private:WordsLinedata;//结点的数据域ListNode*next;//结点的后继指针域，存放后继结点的地址public:ListNode();//构造函数 ListNode(constWordsLinee):data(e),next(NULL){}//构造函数 WordsLine&GetData(){returndata;}//返回结点的数据值ListNode*GetNext(){returnnext;} //返回结点的指针值 voidSetData(WordsLine&e){data=e;}//设置结点的数据值 voidSetNext(ListNode*ptr){next=ptr;}//设置结点的指针值 voidDisPlay();//输出结点的信息};链表类classLinkList//链表类定义{friendclassListNode;private: ListNode*head;//链表的头指针public: LinkList(){head=newListNode();}//构造函数，建立带头结点的空链表 LinkList(WordsLine&e){head=newListNode(e);}//构造函数 ~LinkList(){LinkListClear();deletehead;}//析构函数，删除单链表 voidLinkListClear(); //将线性链表置为空表 ListNode*Head()const{returnhead;} voidInsertInOrder(WordsLinewordsLine);//插入元素后使链表依然有序递增 boolIsEmpty(void)const{returnhead->next==NULL;} voidDisPlay();//输出所有结点信息};//树结点类classDTreeNode{friendclassDTree; charm_word;//每个单词的各个字母 DTreeNode*(m_tp[52]);//52个孩子，指向个大小写字母public: DTreeNode();//构造函数 DTreeNode(charword);//构造函数 DTreeNode(charword,DTreeNode*tp);//构造函数 charGetm_word(){returnm_word;}//返回结点元素 DTreeNode*GetChild(charword);//返回当前结点指向字符word的孩子 boolExistNode(charword);//判断当前节点有无存放x的孩子};树类classDTree{private: DTreeNode*root;//树根public: DTree():root(NULL){}//构造函数 DTree(charword){root=newDTreeNode(word);}//构造函数,构造以字母word为元素的根结点 DTreeNode*GetRoot(){returnroot;}//返回根结点 intGetPosition(charword);//返回待插入元素word的位置 voidInsertWord(char*word);//将单词word插入树中 boolExistWord(constchar*word);//判断单词word是否存在};测试结果及分析程序名为speller.exe，运行环境为Windows，在VC++6.0下测试通过。程序执行后显示：输入字典文件后：输入被测试文件：再从一个英文网站上copy一段，将一些单词故意改错进行测试：文件内容为：测试结果为：由测试可以看出，程序的拼写检测功能还是很强大（加载了4962个单词到词典）源代码//ListNode.h#ifndefHEAD_LINKNODE#defineHEAD_LINKNODE//#include<iostream>//usingnamespacestd;//classLinkList;structWordsLine{//结点类，存放错误的单词及其行号 stringword; intLineNumber;};classListNode//结点类定义{friendclassLinkList;//声明链表类LinkList为友元类private:WordsLinedata;//结点的数据域 ListNode*next;//结点的后继指针域，存放后继结点的地址public:ListNode();//构造函数 ListNode(constWordsLinee):data(e),next(NULL){}//构造函数 WordsLine&GetData(){returndata;}//返回结点的数据值ListNode*GetNext(){returnnext;} //返回结点的指针值 voidSetData(WordsLine&e){data=e;}//设置结点的数据值 voidSetNext(ListNode*ptr){next=ptr;}//设置结点的指针值 voidDisPlay();//输出结点的信息};ListNode::ListNode(){ data.LineNumber=0; next=NULL;}voidListNode::DisPlay(){ cout<<data.word<<""<<data.LineNumber<<endl;}#endif//===================================//LinkList.h#ifndefHEAD_LINKLIST#defineHEAD_LINKLIST//#include<iostream>#include"ListNode.h"#include<string>//usingnamespacestd;//classLinkList//链表类定义{friendclassListNode;private: ListNode*head;//链表的头指针public: LinkList(){head=newListNode();}//构造函数，建立带头结点的空链表 LinkList(WordsLine&e){head=newListNode(e);}//构造函数 ~LinkList(){LinkListClear();deletehead;}//析构函数，删除单链表 voidLinkListClear(); //将线性链表置为空表 ListNode*Head()const{returnhead;} voidInsertInOrder(WordsLinewordsLine);//插入元素后使链表依然有序递增 boolIsEmpty(void)const{returnhead->next==NULL;} voidDisPlay();//输出所有结点信息};//voidLinkList::LinkListClear(){ ListNode*p,*q; p=head->next; while(p) { q=p->next; deletep; p=q; } head->next=NULL;}voidLinkList::InsertInOrder(WordsLinewordsLine){ ListNode*s=newListNode(wordsLine); ListNode*p=head; while(p->next) {//寻找当wordsLine的单词刚好大于当前结点的单词的结点 //如果找到刚好大于的结点，插入 if(strcmp(s->data.word.c_str(),p->next->data.word.c_str())<0)break; else//否则当结点不空时后移，空的时候插入 if(p->next->next){p=p->next;} elsebreak; } //插入 s->next=p->next; p->next=s;}voidLinkList::DisPlay(){//调用结点类的成员函数ListNode::DisPlay() ListNode*p=head->next; if(!p)//表空则表明所有单词拼写正确，不用输出，返回程序 {cout<<"Allwordsarespelledcorrectly!!!"<<endl;return;} //否则输出错误的单词信息 cout<<"Theincorrectlyspelledwordsinalphabeticalorderwiththeirlinenumberare:"<<endl; cout<<endl; while(p) { p->DisPlay(); p=p->next; } cout<<endl;}#endif//===================================//DTreeNode.h#include<iostream>usingnamespacestd;classDTree;classDTreeNode{friendclassDTree; charm_word;//每个单词的各个字母 DTreeNode*(m_tp[52]);//52个孩子，指向个大小写字母public: DTreeNode();//构造函数 DTreeNode(charword);//构造函数 DTreeNode(charword,DTreeNode*tp);//构造函数 charGetm_word(){returnm_word;}//返回结点元素 DTreeNode*GetChild(charword);//返回当前结点指向字符word的孩子 boolExistNode(charword);//判断当前节点有无存放x的孩子};DTreeNode::DTreeNode(){//构造函数 m_word='\0';for(inti=0;i<52;i++)m_tp[i]=NULL;}DTreeNode::DTreeNode(charword){//构造函数 m_word=word; for(inti=0;i<52;i++)m_tp[i]=NULL;}DTreeNode*DTreeNode::GetChild(charword){//返回当前结点指向字符word的孩子 intchild=((word>='A'&&word<='Z')?word%'A':26+(word%'a')); returnm_tp[child];}boolDTreeNode::ExistNode(charword){ intchild=((word>='A'&&word<='Z')?word%'A':26+(word%'a')); returnm_tp[child]!=NULL;}//DTree.h#include<iostream>#include"DTreeNode.h"usingnamespacestd;classDTree{private: DTreeNode*root;//树根public: DTree():root(NULL){}//构造函数 DTree(charword){root=newDTreeNode(word);}//构造函数,构造以字母word为元素的根结点 DTreeNode*GetRoot(){returnroot;}//返回根结点 intGetPosition(charword);//返回待插入元素word的位置 voidInsertWord(char*word);//将单词word插入树中 boolExistWord(constchar*word);//判断单词word是否存在};voidDTree::InsertWord(char*word){//将单词word插入树中，相同的树中重复部分只存一次 if(!word||*word=='\0')return; if(root==NULL||root->m_word=='\0')root=newDTreeNode(*word); DTreeNode*tmp=root; if(tmp) { word++; while(tmp) {//将单词word从第一个字母开始与root比较顺着相同 //的结点走，直到下一个结点元素与单词下一个字母不同 if(tmp->ExistNode(*word)) { tmp=tmp->GetChild(*word); word++; } elsebreak; } while(word&&*word!='\0') {//将所有没有的部分插入树中 intchild=((*word>='A'&&*word<='Z')?*word%'A':26+(*word%'a')); tmp->m_tp[child]=newDTreeNode(*word); tmp=tmp->m_tp[child]; word++; } }}boolDTree::ExistWord(constchar*word){//判断单词word是否存在 DTreeNode*tmp=root; if(tmp&&tmp->m_word==(*word)) {//如果第一个字母与根结点值不同为false word++; while(word&&*word!='\0'&&tmp&&tmp->ExistNode(*word)) {//将单词word从第一个字母开始与root比较,顺着相同 //的结点走，直到word结束且tmp!=0则为真 tmp=tmp->GetChild(*word); word++; } if(*word!='\0')returnfalse; elsereturntrue; } elsereturnfalse;}//speller.cpp#include<iostream>#include<fstream>#include<sstream>#include<string>#include"DTree.h"#include"LinkList.h"//usingnamespacestd;//LinkListL;//用一个链表储存错误的单词（方便排序）//DTreem_dTree[52];//用一个数组存放所有树，下标与根结点字母对应//voidCreateDTree();//加载字典文件，创建字典voidCheckSpell();//检测文档拼写，将错误的排序//voidmain(){ CreateDTree(); CheckSpell(); L.DisPlay();//调用链表成员函数，将所有错误的单词信息输出 system("pause");//暂停，便于用户查看屏幕上输出的错误单词的信息}voidCreateDTree(){ //加载字典文档 // stringfile; cout<<"请输入字典文件（包括完整路劲）:"<<endl; cin>>file; ifstreamin(file.c_str()); cout<<"字典加载中……请等待！！！"<<endl; // for(strings;getline(in,s);) { charword[30]; istringstreamsin(s); charch;inti=0; while(sin>>ch) { word[i]=ch; i++; } word[i]='\0'; intpos_word;//定位单词存放在哪颗树中（先存大写字母开头的） //0-25号树的树根分别存放A-Z，-51号树的树根分别存放a-z pos_word=((*word>='A'&&*word<='Z')?*word%'A':26+(*word%'a')); m_dTree[pos_word].InsertWord(word); }}voidCheckSpell(){ //加载被检测的文档 // stringfile; cout<<"请输入要检测的文件（包括完整路劲）:"<<endl; cin>>file; ifstreamin(file.c_str()); cout<<"拼写检测中……请等待！！！"<<endl; // intLineNumber=0; for(strings;getline(in,s);) { LineNumber++;//每读一行，行数加 istringstreamsin(s); while(sin>>s) { char*tmp=(char*)s.c_str();//string转char* while(*tmp!='\0') { intflag=1;//用来标记当行string中是否含多个单词。为表示只有一个 char*word=tmp;//指向 while((*tmp>='A'&&*tmp<='Z')||(*tmp>='a'&&*tmp<='z')) {//直到当前单词完，获得完整的一个单词 ++tmp; } //以下代码执行如下工作 // //进行检测。如果单词在字典中不存在则拼写错误，将单词及其行号入链表排序 //（用链表将