數(shù)據(jù)結(jié)構(gòu)C++版課程設(shè)計(jì)報(bào)告

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告姓名：學(xué)號(hào)：專業(yè)：聯(lián)系電話：Email:

目錄報(bào)告一拼寫檢測器 31. 實(shí)驗(yàn)題目 32. 問題描述 33. 概要設(shè)計(jì) 34. 詳細(xì)設(shè)計(jì) 45. 測試結(jié)果及分析 66. 源代碼 8

報(bào)告一拼寫檢測器實(shí)驗(yàn)題目拼寫檢測器（Spellerchecker）問題描述1.loadthewordsinthedictionaryfile（加載字典文件）2.readthetextfiletobechecked（讀取被檢測文件）3.lookupeachwordfromthetextfileinthedictionary（逐個(gè)單詞的檢測其拼寫）4.printoutthemisspelledwordsinalphabeticalorderwiththeirlinenumbers.（按字典順序打印出錯(cuò)誤的單詞及其行號(hào)）例如某被檢測文件內(nèi)容如下：顯然第二行的laanguage和第六行的ammong拼寫錯(cuò)誤，輸出應(yīng)該：ammong6laanguage2概要設(shè)計(jì)字典存儲(chǔ)結(jié)構(gòu)選擇由于所有的單詞的長短不一，單詞中字母重復(fù)的部分很多，如果用數(shù)組存儲(chǔ)字典的話很浪費(fèi)空間，所以考慮用樹存儲(chǔ)字典，相同部分只存儲(chǔ)一次，每一棵樹只存儲(chǔ)相同字母開頭的所有單詞，從上往下，依次存儲(chǔ)，孩子的腳標(biāo)與字母對(duì)應(yīng)（0-25號(hào)樹的樹根分別存放A-Z，26-51號(hào)樹的樹根分別存放a-z，其孩子也是一樣）。樹的ADT定義：ADTDTree{數(shù)據(jù)對(duì)象：D=｛ai|ai屬于ElemSet，i=1，2，……，nn>=0｝數(shù)據(jù)關(guān)系：若D為空集，則樹為空；若緊含一個(gè)數(shù)據(jù)元素，則數(shù)據(jù)關(guān)系為空，否則：D中僅有一個(gè)稱為跟（root）的數(shù)據(jù)元素，關(guān)系R沒有前驅(qū)。除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)劃分m個(gè)互不相交的子集，對(duì)任意的子集Di，<root，xi>屬于R?；静僮鳎篒nitTree(&T);//建立空樹DestroyTree（&T）；//銷毀樹Root(T);//求樹跟Insert（&T，x）；//將元素x插入樹中Chile（T，x，i）；//求x結(jié)點(diǎn)的第i個(gè)孩子｝ADTDTree排序存儲(chǔ)結(jié)構(gòu)選擇若選用數(shù)組，排序的時(shí)間復(fù)雜度很高，其單詞長短不一，選用鏈表。鏈表抽象數(shù)據(jù)定義ADTLinkList{數(shù)據(jù)對(duì)象：D=｛ai|ai屬于ElemSet，i=1，2，……，nn>=0｝數(shù)據(jù)關(guān)系：R=｛<ai-1,ai>|ai-1,ai屬于D，i=1，2，……，nn>=0｝基本操作：Init（&L）；//構(gòu)造一個(gè)空鏈表InsertInOrder（&L，x）；//將元素插入有序表中使之仍然有序DisPlay（）；//輸出結(jié)點(diǎn)信息｝ADTLinkList；其他函數(shù)主函數(shù)main（）。建字典函數(shù)CreateDTree（）。檢測拼寫函數(shù)Checkspell（）。詳細(xì)設(shè)計(jì)樹存儲(chǔ)字典，每個(gè)單詞的字母是一個(gè)結(jié)點(diǎn)，而鏈表存放單詞及行號(hào)，用WordsLine結(jié)構(gòu)體單詞及行號(hào)，定義結(jié)點(diǎn)類ListNode、鏈表類LinkList、樹結(jié)點(diǎn)類DTreeNode、樹類DTree。StuctstructWordsLine{//結(jié)點(diǎn)類，存放錯(cuò)誤的單詞及其行號(hào) stringword; intLineNumber;};鏈表結(jié)點(diǎn)類classListNode//結(jié)點(diǎn)類定義{friendclassLinkList;//聲明鏈表類LinkList為友元類private:WordsLinedata;//結(jié)點(diǎn)的數(shù)據(jù)域ListNode*next;//結(jié)點(diǎn)的后繼指針域，存放后繼結(jié)點(diǎn)的地址public:ListNode();//構(gòu)造函數(shù) ListNode(constWordsLinee):data(e),next(NULL){}//構(gòu)造函數(shù) WordsLine&GetData(){returndata;}//返回結(jié)點(diǎn)的數(shù)據(jù)值ListNode*GetNext(){returnnext;} //返回結(jié)點(diǎn)的指針值 voidSetData(WordsLine&e){data=e;}//設(shè)置結(jié)點(diǎn)的數(shù)據(jù)值 voidSetNext(ListNode*ptr){next=ptr;}//設(shè)置結(jié)點(diǎn)的指針值 voidDisPlay();//輸出結(jié)點(diǎn)的信息};鏈表類classLinkList//鏈表類定義{friendclassListNode;private: ListNode*head;//鏈表的頭指針public: LinkList(){head=newListNode();}//構(gòu)造函數(shù)，建立帶頭結(jié)點(diǎn)的空鏈表 LinkList(WordsLine&e){head=newListNode(e);}//構(gòu)造函數(shù) ~LinkList(){LinkListClear();deletehead;}//析構(gòu)函數(shù)，刪除單鏈表 voidLinkListClear(); //將線性鏈表置為空表 ListNode*Head()const{returnhead;} voidInsertInOrder(WordsLinewordsLine);//插入元素后使鏈表依然有序遞增 boolIsEmpty(void)const{returnhead->next==NULL;} voidDisPlay();//輸出所有結(jié)點(diǎn)信息};//樹結(jié)點(diǎn)類classDTreeNode{friendclassDTree; charm_word;//每個(gè)單詞的各個(gè)字母 DTreeNode*(m_tp[52]);//52個(gè)孩子，指向個(gè)大小寫字母public: DTreeNode();//構(gòu)造函數(shù) DTreeNode(charword);//構(gòu)造函數(shù) DTreeNode(charword,DTreeNode*tp);//構(gòu)造函數(shù) charGetm_word(){returnm_word;}//返回結(jié)點(diǎn)元素 DTreeNode*GetChild(charword);//返回當(dāng)前結(jié)點(diǎn)指向字符word的孩子 boolExistNode(charword);//判斷當(dāng)前節(jié)點(diǎn)有無存放x的孩子};樹類classDTree{private: DTreeNode*root;//樹根public: DTree():root(NULL){}//構(gòu)造函數(shù) DTree(charword){root=newDTreeNode(word);}//構(gòu)造函數(shù),構(gòu)造以字母word為元素的根結(jié)點(diǎn) DTreeNode*GetRoot(){returnroot;}//返回根結(jié)點(diǎn) intGetPosition(charword);//返回待插入元素word的位置 voidInsertWord(char*word);//將單詞word插入樹中 boolExistWord(constchar*word);//判斷單詞word是否存在};測試結(jié)果及分析程序名為speller.exe，運(yùn)行環(huán)境為Windows，在VC++6.0下測試通過。程序執(zhí)行后顯示：輸入字典文件后：輸入被測試文件：再從一個(gè)英文網(wǎng)站上copy一段，將一些單詞故意改錯(cuò)進(jìn)行測試：文件內(nèi)容為：測試結(jié)果為：由測試可以看出，程序的拼寫檢測功能還是很強(qiáng)大（加載了4962個(gè)單詞到詞典）源代碼//ListNode.h#ifndefHEAD_LINKNODE#defineHEAD_LINKNODE//#include<iostream>//usingnamespacestd;//classLinkList;structWordsLine{//結(jié)點(diǎn)類，存放錯(cuò)誤的單詞及其行號(hào) stringword; intLineNumber;};classListNode//結(jié)點(diǎn)類定義{friendclassLinkList;//聲明鏈表類LinkList為友元類private:WordsLinedata;//結(jié)點(diǎn)的數(shù)據(jù)域 ListNode*next;//結(jié)點(diǎn)的后繼指針域，存放后繼結(jié)點(diǎn)的地址public:ListNode();//構(gòu)造函數(shù) ListNode(constWordsLinee):data(e),next(NULL){}//構(gòu)造函數(shù) WordsLine&GetData(){returndata;}//返回結(jié)點(diǎn)的數(shù)據(jù)值ListNode*GetNext(){returnnext;} //返回結(jié)點(diǎn)的指針值 voidSetData(WordsLine&e){data=e;}//設(shè)置結(jié)點(diǎn)的數(shù)據(jù)值 voidSetNext(ListNode*ptr){next=ptr;}//設(shè)置結(jié)點(diǎn)的指針值 voidDisPlay();//輸出結(jié)點(diǎn)的信息};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();}//構(gòu)造函數(shù)，建立帶頭結(jié)點(diǎn)的空鏈表 LinkList(WordsLine&e){head=newListNode(e);}//構(gòu)造函數(shù) ~LinkList(){LinkListClear();deletehead;}//析構(gòu)函數(shù)，刪除單鏈表 voidLinkListClear(); //將線性鏈表置為空表 ListNode*Head()const{returnhead;} voidInsertInOrder(WordsLinewordsLine);//插入元素后使鏈表依然有序遞增 boolIsEmpty(void)const{returnhead->next==NULL;} voidDisPlay();//輸出所有結(jié)點(diǎn)信息};//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) {//尋找當(dāng)wordsLine的單詞剛好大于當(dāng)前結(jié)點(diǎn)的單詞的結(jié)點(diǎn) //如果找到剛好大于的結(jié)點(diǎn)，插入 if(strcmp(s->data.word.c_str(),p->next->data.word.c_str())<0)break; else//否則當(dāng)結(jié)點(diǎn)不空時(shí)后移，空的時(shí)候插入 if(p->next->next){p=p->next;} elsebreak; } //插入 s->next=p->next; p->next=s;}voidLinkList::DisPlay(){//調(diào)用結(jié)點(diǎn)類的成員函數(shù)ListNode::DisPlay() ListNode*p=head->next; if(!p)//表空則表明所有單詞拼寫正確，不用輸出，返回程序 {cout<<"Allwordsarespelledcorrectly!!!"<<endl;return;} //否則輸出錯(cuò)誤的單詞信息 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;//每個(gè)單詞的各個(gè)字母 DTreeNode*(m_tp[52]);//52個(gè)孩子，指向個(gè)大小寫字母public: DTreeNode();//構(gòu)造函數(shù) DTreeNode(charword);//構(gòu)造函數(shù) DTreeNode(charword,DTreeNode*tp);//構(gòu)造函數(shù) charGetm_word(){returnm_word;}//返回結(jié)點(diǎn)元素 DTreeNode*GetChild(charword);//返回當(dāng)前結(jié)點(diǎn)指向字符word的孩子 boolExistNode(charword);//判斷當(dāng)前節(jié)點(diǎn)有無存放x的孩子};DTreeNode::DTreeNode(){//構(gòu)造函數(shù) m_word='\0';for(inti=0;i<52;i++)m_tp[i]=NULL;}DTreeNode::DTreeNode(charword){//構(gòu)造函數(shù) m_word=word; for(inti=0;i<52;i++)m_tp[i]=NULL;}DTreeNode*DTreeNode::GetChild(charword){//返回當(dāng)前結(jié)點(diǎn)指向字符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){}//構(gòu)造函數(shù) DTree(charword){root=newDTreeNode(word);}//構(gòu)造函數(shù),構(gòu)造以字母word為元素的根結(jié)點(diǎn) DTreeNode*GetRoot(){returnroot;}//返回根結(jié)點(diǎn) intGetPosition(charword);//返回待插入元素word的位置 voidInsertWord(char*word);//將單詞word插入樹中 boolExistWord(constchar*word);//判斷單詞word是否存在};voidDTree::InsertWord(char*word){//將單詞word插入樹中，相同的樹中重復(fù)部分只存一次 if(!word||*word=='\0')return; if(root==NULL||root->m_word=='\0')root=newDTreeNode(*word); DTreeNode*tmp=root; if(tmp) { word++; while(tmp) {//將單詞word從第一個(gè)字母開始與root比較順著相同 //的結(jié)點(diǎn)走，直到下一個(gè)結(jié)點(diǎn)元素與單詞下一個(gè)字母不同 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)) {//如果第一個(gè)字母與根結(jié)點(diǎn)值不同為false word++; while(word&&*word!='\0'&&tmp&&tmp->ExistNode(*word)) {//將單詞word從第一個(gè)字母開始與root比較,順著相同 //的結(jié)點(diǎn)走，直到word結(jié)束且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"http://usingnamespacestd;//LinkListL;//用一個(gè)鏈表儲(chǔ)存錯(cuò)誤的單詞（方便排序）//DTreem_dTree[52];//用一個(gè)數(shù)組存放所有樹，下標(biāo)與根結(jié)點(diǎn)字母對(duì)應(yīng)//voidCreateDTree();//加載字典文件，創(chuàng)建字典voidCheckSpell();//檢測文檔拼寫，將錯(cuò)誤的排序//voidmain(){ CreateDTree(); CheckSpell(); L.DisPlay();//調(diào)用鏈表成員函數(shù)，將所有錯(cuò)誤的單詞信息輸出 system("pause");//暫停，便于用戶查看屏幕上輸出的錯(cuò)誤單詞的信息}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號(hào)樹的樹根分別存放A-Z，-51號(hào)樹的樹根分別存放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++;//每讀一行，行數(shù)加 istringstreamsin(s); while(sin>>s) { char*tmp=(char*)s.c_str();//string轉(zhuǎn)char* while(*tmp!='\0') { intflag=1;//用來標(biāo)記當(dāng)行string中是否含多個(gè)單詞。為表示只有一個(gè) char*word=tmp;//指向 while((*tmp>='A'&&*tmp<='Z')||(*tmp>='a'&&*tmp<='z')) {//直到當(dāng)前單詞完，獲得完整的一個(gè)單詞 ++tmp; } //以下代碼執(zhí)行如下工作 // //進(jìn)行檢測。如果單詞在字典中不存在則拼寫錯(cuò)誤，將單詞及其行號(hào)入鏈表排序 //（用鏈表將