數據結構c++課程設計報告--拼寫檢測器

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數：15 大?。?50.25KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構課程設計　　報告　　姓名： 　　學號： 　　專業(yè)：

2、 　　聯系電話： 　　E m a il: 　　報告一拼寫檢測器　　實驗題目<

3、p>　　拼寫檢測器（Speller checker）　　問題描述　　1. load the words in the dictionary file（加載字典文件） 　　2 .read the text file to be checked （讀取被檢測文件）</

4、p>　　3. look up each word from the text file in the dictionary （逐個單詞的檢測其拼寫）　　4. print out the misspelled words in alphabetical order with their line numbers.（按字典順序打印出錯誤的單詞及其行號）例如某被檢測文件內容

5、如下：　　顯然第二行的laanguage和第六行的ammong拼寫錯誤，輸出應該：　　ammong 6　　laanguage 2　　概要設計<b

6、>　　字典存儲結構選擇　　由于所有的單詞的長短不一，單詞中字母重復的部分很多，如果用數組存儲字典的話很浪費空間，所以考慮用樹存儲字典，相同部分只存儲一次，每一棵樹只存儲相同字母開頭的所有單詞，從上往下，依次存儲，孩子的腳標與字母對應（0-25號樹的樹根分別存放A-Z，26-51號樹的樹根分別存放a-z，其孩子也是一樣）。<

7、b>　　樹的ADT 定義：　　ADT DTree{　　數據對象：D=｛ai | ai屬于ElemSet，i=1，2，……，n n>=0｝　　數據關系：若D為空集，則樹為空；若緊含一個數據元素，則數據關系為空，否則：　　D中僅有一個稱為跟

8、（root）的數據元素，關系R沒有前驅。　　除根結點外，其余結點劃分m個互不相交的子集，對任意的子集Di，<root，xi>屬于R。　　基本操作：　　InitTree(& T);　　//建立空樹&

9、lt;/b>　　DestroyTree（& T）；　　//銷毀樹　　Root(T) ;　　//求樹跟

10、　Insert（&T，x）；　　//將元素x插入樹中　　Chile（T，x，i）；　　//求x結點的第i個孩子　?。鼳DT DTree　　排序存儲結構選擇&l

11、t;p>　　若選用數組，排序的時間復雜度很高，其單詞長短不一，選用鏈表。　　鏈表抽象數據定義　　ADT LinkList{　　數據對象：D=｛ai| ai屬于ElemSet，i=1，2，……，n n>=0｝　　數據關系：

12、R=｛<ai-1,ai>|ai-1,ai屬于D，i=1，2，……，n n>=0｝　　基本操作：　　Init（&L）；　　//構造一個空鏈表<p&

13、gt;　　InsertInOrder（&L，x）；　　//將元素插入有序表中使之仍然有序　　DisPlay（）；　　//輸出結點信息　　｝ADT LinkList；

14、　　其他函數　　主函數main（）。　　建字典函數CreateDTree（）。　　檢測拼寫函數Checkspell（）。　　詳細設計　　樹存儲字典，每個單詞的字母是一個結點

15、，而鏈表存放單詞及行號，用WordsLine結構體單詞及行號，定義結點類ListNode、鏈表類LinkList、樹結點類DTreeNode、樹類DTree。　　Stuct　　struct WordsLine　　{//結點類，存放錯誤的單詞及其行號&l

16、t;p>　　string word;　　int LineNumber;　　};　　鏈表結點類　　class ListNode //結點類定義<

17、p>　　{　　friend class LinkList; //聲明鏈表類LinkList為友元類　　private:　　WordsLine data; //結點的數據域　　ListN

18、ode* next; //結點的后繼指針域，存放后繼結點的地址　　public:　　ListNode();//構造函數　　ListNode(const WordsLine e):data(e),next(NULL){} //構造函數

19、;　　WordsLine& GetData(){return data;} //返回結點的數據值　　ListNode* GetNext(){return next;} //返回結點的指針值　　void SetData(WordsLine & e){data=e;} //設置結點的數據值<p&g

20、t;　　void SetNext(ListNode* ptr){next=ptr;} //設置結點的指針值　　void DisPlay();//輸出結點的信息　　};　　鏈表類　　class

21、LinkList //鏈表類定義　　{ 　　friend class ListNode;　　private:　　ListNode *head; //鏈表的頭指針<p&

22、gt;　　public:　　LinkList(){head=new ListNode();} //構造函數，建立帶頭結點的空鏈表　　LinkList(WordsLine& e){head=new ListNode(e);} //構造函數　　~LinkList(){

23、LinkListClear();delete head;} //析構函數，刪除單鏈表　　void LinkListClear();//將線性鏈表置為空表　　ListNode* Head()const{return head;}　　void InsertInOrder(WordsLine wordsLine);

24、 //插入元素后使鏈表依然有序遞增　　bool IsEmpty(void)const{return head->next==NULL;} 　　void DisPlay();//輸出所有結點信息　　};　　//----------

25、--------------------------　　樹結點類　　class DTreeNode　　{friend class DTree;　　char m_word; //每個單詞的各個字母<p&g

26、t;　　DTreeNode* (m_tp[52]);//52個孩子，指向個大小寫字母　　public: 　　DTreeNode(); //構造函數　　DTreeNode(char word);//構造函數　　DTreeNode(c

27、har word,DTreeNode *tp); //構造函數　　char Getm_word(){return m_word;} //返回結點元素　　DTreeNode*GetChild(char word);//返回當前結點指向字符word的孩子　　bool ExistNode(char word);//判斷

28、當前節(jié)點有無存放x的孩子　　};　　樹類　　class DTree　　{　　private:<

29、;/b>　　DTreeNode* root;//樹根　　public:　　DTree():root(NULL){}//構造函數　　DTree(char word){root=new DTreeNode(word);}//構造函數

30、,構造以字母word為元素的根結點　　DTreeNode* GetRoot(){return root;}//返回根結點　　int GetPosition(char word);//返回待插入元素word的位置　　void InsertWord(char* word);//將單詞word插入樹中

31、;　　bool ExistWord(const char *word);//判斷單詞word是否存在　　};　　測試結果及分析　　程序名為speller.exe，運行環(huán)境為Windows，在VC++6.0下測試通過。

32、程序執(zhí)行后顯示：　　輸入字典文件后：　　輸入被測試文件：　　再從一個英文網站上copy一段，將一些單詞故意改錯進行測試：　　文件內容為：

33、　　測試結果為：　　由測試可以看出，程序的拼寫檢測功能還是很強大（加載了4962個單詞到詞典）　　源代碼　　//ListNode.h　　#ifndef HEAD_LINKNOD

34、E　　#define HEAD_LINKNODE　　//---------------------------　　#include<iostream>　　//---------------------------　　u

35、sing namespace std;　　//-----------------------------　　class LinkList;　　struct WordsLine　　{//結點類，存放錯誤的單詞及其行號　　string

36、 word;　　int LineNumber;　　};　　class ListNode //結點類定義　　{　　friend class

37、 LinkList; //聲明鏈表類LinkList為友元類　　private:　　WordsLine data; //結點的數據域　　ListNode* next; //結點的后繼指針域，存放后繼結點的地址

38、;　　public:　　ListNode();//構造函數　　ListNode(const WordsLine e):data(e),next(NULL){} //構造函數　　WordsLine& GetData(){return data;} //返回結點的數據值</p&

39、gt;　　ListNode* GetNext(){return next;} //返回結點的指針值　　void SetData(WordsLine & e){data=e;} //設置結點的數據值　　void SetNext(ListNode* ptr){next=ptr;} //設置結點的指針值</p&

40、gt;　　void DisPlay();//輸出結點的信息　　};　　ListNode::ListNode()　　{　　data.LineNumber=0;

41、;　　next=NULL;　　} 　　void ListNode::DisPlay()　　{　　cout<<data.word<<" &

42、quot;<<data.LineNumber<<endl;　　}　　#endif　　//===================================　　//Lin

43、kList.h　　#ifndef HEAD_LINKLIST　　#define HEAD_LINKLIST　　//----------------------------　　#include<iostream>　　#i

44、nclude"ListNode.h"　　#include<string>　　//---------------------------　　using namespace std;　　//-------------------------&l

45、t;/p>　　class LinkList //鏈表類定義　　{ 　　friend class ListNode;　　private:　　ListNode *head;

46、 //鏈表的頭指針　　public:　　LinkList(){head=new ListNode();} //構造函數，建立帶頭結點的空鏈表　　LinkList(WordsLine& e){head=new ListNode(e);} //構造函數</p&g

47、t;　　~LinkList(){LinkListClear();delete head;} //析構函數，刪除單鏈表　　void LinkListClear();//將線性鏈表置為空表　　ListNode* Head()const{return head;}　　void InsertIn

48、Order(WordsLine wordsLine); //插入元素后使鏈表依然有序遞增　　bool IsEmpty(void)const{return head->next==NULL;} 　　void DisPlay();//輸出所有結點信息　　};</p&g

49、t;　　//------------------------------------　　void LinkList::LinkListClear()　　{　　ListNode *p,*q;　　p=head->

50、;next;　　while(p) 　　{　　q=p->next;　　delete p;　　p=q;</

51、p>　　}　　head->next=NULL;　　}　　void LinkList::InsertInOrder(WordsLine wordsLine)<

52、b>　　{　　ListNode *s=new ListNode(wordsLine);　　ListNode *p=head;　　while(p->next)　　{//尋找當wordsLine的單詞剛好大于當前結點的單詞的結點</p&g

53、t;　　//如果找到剛好大于的結點，插入　　if(strcmp(s->data.word.c_str(),p->next->data.word.c_str())<0) break;　　else //否則當結點不空時后移，空的時候插入　　if(p->next-&g

54、t;next){p=p->next;}　　else break;　　}　　//插入　　s->next=p->next;　　p->n

55、ext=s;　　}　　void LinkList::DisPlay()　　{//調用結點類的成員函數ListNode::DisPlay()　　ListNode *p=head->next;

56、;　　if(!p) //表空則表明所有單詞拼寫正確，不用輸出，返回程序　　{cout<<"All words are spelled correctly!!!"<<endl;return;} 　　//否則輸出錯誤的單詞信息　　cout<<"The

57、incorrectly spelled words in alphabetical order with their linenumber are:"<<endl;　　cout<<endl;　　while(p)　　{<

58、/b>　　p->DisPlay();　　p=p->next;　　}　　cout<<endl;　　}&

59、lt;p>　　#endif　　//===================================　　// DTreeNode.h　　#include<iostream>　　using namespace st

60、d;　　class DTree;　　class DTreeNode　　{friend class DTree;　　char m_word; //每個單詞的各個字母　　DTreeNode* (m_tp[52]);//52個孩子，指

61、向個大小寫字母　　public: 　　DTreeNode(); //構造函數　　DTreeNode(char word);//構造函數　　DTreeNode(char word,DTreeNode *tp); //構造函數<

62、/p>　　char Getm_word(){return m_word;} //返回結點元素　　DTreeNode*GetChild(char word);//返回當前結點指向字符word的孩子　　bool ExistNode(char word);//判斷當前節(jié)點有無存放x的孩子&l

63、t;b>　　};　　DTreeNode::DTreeNode()　　{//構造函數　　m_word='\0';　　for(int i=0;i<52;i++) m_tp[i]=NULL;&

64、lt;/p>　　}　　DTreeNode::DTreeNode(char word)　　{//構造函數　　m_word=word;　　for(int i=0;i<

65、52;i++) m_tp[i]=NULL;　　}　　DTreeNode* DTreeNode::GetChild(char word)　　{//返回當前結點指向字符word的孩子　　int child=((word>='

66、A' && word<='Z')?word%'A':26+(word%'a'));　　return m_tp[child];　　}　　bool DTreeNode::ExistNode(char w

67、ord)　　{　　int child=((word>='A' && word<='Z')?word%'A':26+(word%'a'));　　return m_tp[child]!=N

68、ULL;　　}　　//DTree.h　　#include<iostream>　　#include "DTreeNode.h"

69、;　　using namespace std;　　class DTree　　{　　private:　　DTreeNode* root;//樹根<b&

70、gt;　　public:　　DTree():root(NULL){}//構造函數　　DTree(char word){root=new DTreeNode(word);}//構造函數,構造以字母word為元素的根結點　　DTreeNode* GetRoot(){return root;}//返

71、回根結點　　int GetPosition(char word);//返回待插入元素word的位置　　void InsertWord(char* word);//將單詞word插入樹中　　bool ExistWord(const char *word);//判斷單詞word是否存在<

72、p>　　};　　void DTree::InsertWord(char* word)　　{//將單詞word插入樹中，相同的樹中重復部分只存一次　　if(!word || *word =='\0') return;

73、;　　if(root==NULL || root->m_word=='\0') root=new DTreeNode(*word);　　DTreeNode* tmp=root;　　if(tmp)　　{</p&g

74、t;　　word++;　　while(tmp)　　{//將單詞word從第一個字母開始與root比較順著相同　　//的結點走，直到下一個結點元素與單詞下一個字母不同　　if(tmp->ExistNode(*

75、word))　　{　　tmp=tmp->GetChild(*word);　　word++;　　}　　else

76、break;　　}　　while(word&&*word!='\0')　　{//將所有沒有的部分插入樹中　　int child=((*word>='A' && *w

77、ord<='Z')?*word%'A':26+(*word%'a'));　　tmp->m_tp[child]=new DTreeNode(*word);　　tmp=tmp->m_tp[child];　　word++;</b&

78、gt;　　}　　}　　}　　bool DTree::ExistWord(const char *word)　　{//

79、判斷單詞word是否存在　　DTreeNode* tmp=root;　　if(tmp&&tmp->m_word==(*word))　　{//如果第一個字母與根結點值不同為false　　word++;</p&

80、gt;　　while(word&&*word!='\0'&&tmp&&tmp->ExistNode(*word))　　{//將單詞word從第一個字母開始與root比較,順著相同　　//的結點走，直到word結束且tmp!=0則為真<

81、p>　　tmp=tmp->GetChild(*word);　　word++;　　}　　if(*word!='\0') return false;　　else retur

82、n true;　　}　　else return false;　　}　　//speller.cpp　　#include<iostream><

83、;/p>　　#include<fstream>　　#include<sstream>　　#include<string>　　#include"DTree.h"　　#include"

84、;LinkList.h"　　//-----------------------　　using namespace std;　　//-----------------------　　LinkList L;//用一個鏈表儲存錯誤的單詞（方便排序）

85、　　//---------------------------　　DTree m_dTree[52];//用一個數組存放所有樹，下標與根結點字母對應　　//--------------------------　　void CreateDTree();//加載字典文件，創(chuàng)建字典</p&g

86、t;　　void CheckSpell();//檢測文檔拼寫，將錯誤的排序　　//---------------------　　void main()　　{　　CreateDTree();

87、　　CheckSpell();　　L.DisPlay();//調用鏈表成員函數，將所有錯誤的單詞信息輸出　　system("pause");//暫停，便于用戶查看屏幕上輸出的錯誤單詞的信息　　}

88、　void CreateDTree()　　{　　//加載字典文檔　　//--------------------------　　string file;

89、　cout<<"請輸入字典文件（包括完整路勁）:"<<endl;　　cin>>file;　　ifstream in(file.c_str());　　cout<<"字典加載中……請等待?。。?quot;<<endl;</

90、p>　　//--------------------------　　for(string s;getline(in,s);)　　{　　char word[30];　　istringstream sin(s)

91、;　　char ch;int i=0;　　while(sin>>ch) 　　{　　word[i]=ch;　　i++;&

92、lt;p>　　}　　word[i]='\0';　　int pos_word;//定位單詞存放在哪顆樹中（先存大寫字母開頭的）　　//0-25號樹的樹根分別存放A-Z，-51號樹的樹根分別存放a-z　　pos_wo

93、rd=((*word>='A' && *word<='Z')?*word%'A':26+(*word%'a'));　　m_dTree[pos_word].InsertWord(word);　　}<

94、p>　　}　　void CheckSpell()　　{　　//加載被檢測的文檔　　//--------------------------　　str

95、ing file;　　cout<<"請輸入要檢測的文件（包括完整路勁）:"<<endl;　　cin>>file;　　ifstream in(file.c_str());　　cout<<"拼寫檢測

96、中……請等待?。?！"<<endl;　　//--------------------------　　int LineNumber=0;　　for(string s;getline(in,s);)　　{</p&

97、gt;　　LineNumber++;//每讀一行，行數加　　istringstream sin(s);　　while(sin>>s)　　{　　char*tmp=(char*)s.c_str();//s

98、tring轉char*　　while(*tmp!='\0')　　{　　int flag=1;//用來標記當行string中是否含多個單詞。為表示只有一個　　char*word=tmp;//指向&

99、lt;p>　　while((*tmp>='A'&&*tmp<='Z')||(*tmp>='a'&&*tmp<='z'))　　{//直到當前單詞完，獲得完整的一個單詞　　++tmp;<

100、/p>　　}　　//以下代碼執(zhí)行如下工作　　//-----------------------------------　　//進行檢測。如果單詞在字典中不存在則拼寫錯誤，將單詞及其行號入鏈表排序　　//（用

101、鏈表將錯誤單詞按字母順序排序）,最后將所有錯誤單詞輸出　　//如果當前行未結束，表明是遇到標點，當前單詞結束，設置當前單詞結束　　//（后面可能仍然還有單詞）然后進入下一個單詞　　//如果字符串結束（當前行當前單詞以后沒有單詞）　　//則開始下一行<

102、;/b>　　//-------------------------------------　　if(*tmp!='\0')　　{//如果當前行未結束　　flag=0;

103、*tmp='\0';//設置當前單詞結束　　}　　int pos_word;//定位單詞存放在哪顆樹中　　bool big=false;　　pos_word=((*word>='A' &&

104、amp; *word<='Z')?(*word%'A'):(26+(*word%'a')));　　if(!m_dTree[pos_word].ExistWord(word))　　{//單詞在字典中不存在　　if((*word>='A' &

105、amp;& *word<='Z'))　　{//將單詞的第一個大寫字母轉換成小寫的再檢測　　char*tmp=word;　　*tmp=*tmp+32;//首字母轉換成小寫的　　pos_word=26+(*tmp%'a');<

106、;/p>　　big=m_dTree[pos_word].ExistWord(tmp);　　}　　if(!big)　　{//當單詞大小寫都不存在的的時候，拼寫錯誤，入鏈表排序<p&g

107、t;　　WordsLine wordsLine;//結構體，存放單詞和所在行號　　wordsLine.LineNumber=LineNumber;　　wordsLine.word=word;　　L.InsertInOrder(wordsLine);//調用鏈表的成員函數排序

108、;　　}　　}　　if(flag) break;//如果當前行結束,則開始下一行　　else 　　{

109、　　tmp++;//如果當前行未結束,則進入下一個單詞(先過濾掉標點)　　while(*tmp!='\0'&&!((*tmp>='A'&&*tmp<='Z')||(*tmp>='a'&&*tmp<='z'))) </p

110、>　　tmp++; 　　}　　}　　}　　}</

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數據結構c++課程設計報告--拼寫檢測器

文檔簡介

溫馨提示

最新文檔

評論

數據結構c++課程設計報告--拼寫檢測器

文檔簡介

溫馨提示

最新文檔

評論

免費下載