數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書-計(jì)算單詞出現(xiàn)的頻率

課程設(shè)計(jì)說明書課程名稱：數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目：計(jì)算單詞出現(xiàn)的頻率學(xué)院：計(jì)算機(jī)科學(xué)與信息工程學(xué)院課

程

設(shè)

計(jì)

任

務(wù)

書設(shè)計(jì)題目計(jì)算單詞出現(xiàn)的頻率學(xué)生姓名

所在院系計(jì)算機(jī)科學(xué)與信息工程專業(yè)、年級、班13級軟件工程設(shè)計(jì)要求：當(dāng)作者沒有在文本上簽名時(shí)，或者被認(rèn)為其他人的作品時(shí)，需要確定文本作者的身份，可以使用單詞頻率分析這個(gè)工具。如果一直作家A創(chuàng)作了文本T1，文本T2經(jīng)過仔細(xì)審查，其單詞頻率分布與T1十分相近，那么T2很有可能是由作者A創(chuàng)作的。不管這一方法在文學(xué)研究上的可靠性如何，我們都將編寫一個(gè)程序掃描文本文件，并計(jì)算這一個(gè)文本中單詞出現(xiàn)的頻率。學(xué)生應(yīng)完成的工作：1根據(jù)系統(tǒng)所需設(shè)計(jì)完成相關(guān)函數(shù)的構(gòu)造2編譯并且上機(jī)調(diào)試，得出正確的結(jié)論3結(jié)果分析4撰寫實(shí)驗(yàn)報(bào)告5準(zhǔn)備設(shè)計(jì)答辯參考文獻(xiàn)閱讀：1數(shù)據(jù)結(jié)構(gòu)（c語言版），清華大學(xué)出版社2C++數(shù)據(jù)結(jié)構(gòu)與算法（第四版），清華大學(xué)出版社3C++程序設(shè)計(jì)教程，清華大學(xué)出版社工作計(jì)劃：1第一天：小組布置設(shè)計(jì)題目，說明進(jìn)度安排2第二天：小組審題，查閱資料，進(jìn)行設(shè)計(jì)前的必要資料的準(zhǔn)備3第三天：程序編寫，上機(jī)調(diào)試4第四天：同上5第五天：撰寫實(shí)驗(yàn)報(bào)告

任務(wù)下達(dá)日期：

2015年

6

月

20

日任務(wù)完成日期：

2015年

6

月

26

日

指導(dǎo)教師（簽名）：

學(xué)生（簽名）：計(jì)算單詞出現(xiàn)的頻率摘要：樹是一種比較重要的數(shù)據(jù)結(jié)構(gòu)之一。在樹型結(jié)構(gòu)關(guān)系中，節(jié)點(diǎn)之間的關(guān)系不是任意的，數(shù)據(jù)元素之間是有一定關(guān)系的。本設(shè)計(jì)題目采用二叉樹，運(yùn)用“半張開”的技術(shù)來重新組織樹。需要注意的是單詞向根部移動時(shí)，需要改變所涉及及節(jié)點(diǎn)的連接關(guān)系，而不是將信息從一個(gè)節(jié)點(diǎn)傳給它的父節(jié)點(diǎn)，再傳給它的祖父節(jié)點(diǎn)。如果沒有在樹中找到單詞，就為該單詞創(chuàng)建一個(gè)新的葉節(jié)點(diǎn)，將其插入到樹中。處理完所有單詞后，對樹進(jìn)行中序遍歷，計(jì)算所有節(jié)點(diǎn)的頻率，再把這些頻率級數(shù)加在一起并輸出，作為樹中單詞個(gè)數(shù)和文件中單詞個(gè)數(shù)的最后結(jié)果。關(guān)鍵詞：樹遍歷組織樹目錄1.設(shè)計(jì)背景…………………51.1課程設(shè)計(jì)目………51.2題目要求…………52.設(shè)計(jì)方案…………………53.方案實(shí)施…………………54.結(jié)果與結(jié)論………………65.收獲與致謝………………86.參考文獻(xiàn)…………………97.附件………9.1.設(shè)計(jì)背景1.設(shè)計(jì)背景1.1課程設(shè)計(jì)目的通過本課程設(shè)計(jì)，加深對《數(shù)據(jù)結(jié)構(gòu)與算法》課程所學(xué)知識的理解，熟練掌握和鞏固C語言的基本知識和語法規(guī)范,培養(yǎng)調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料、手冊以及編寫技術(shù)文獻(xiàn)的能力。學(xué)會編制結(jié)構(gòu)清晰、風(fēng)格良好的C語言程序，從而具備利用計(jì)算機(jī)編程分析解決綜合性實(shí)際問題的初步能力。1.2題目要求課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實(shí)際問題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程。通過課程設(shè)計(jì)，鞏固和加深對圖等理論知識的理解；掌握包括問題描述、系統(tǒng)分析、設(shè)計(jì)建模、代碼實(shí)現(xiàn)、結(jié)果分析等的方法；提高利用計(jì)算機(jī)分析解決綜合性實(shí)際問題的基本能力；鍛煉個(gè)人動手能力，歷練自身素質(zhì)。2.設(shè)計(jì)方案設(shè)計(jì)方法問題的分析和結(jié)構(gòu)的設(shè)計(jì)思路1）樹的遍歷和生成樹求解的所有功能有：通過錄入頂點(diǎn)個(gè)數(shù)和邊數(shù)信息，采用兩種圖的兩種存儲結(jié)構(gòu)：鄰接矩陣、鄰接表，輸出鄰接矩陣和鄰接表；進(jìn)行深度和廣度優(yōu)先遍歷；普利姆算法和克魯斯卡爾算法求解最小生成樹；退出程序等功能。2）需要創(chuàng)建二叉樹。3）選擇合適的算法，實(shí)現(xiàn)數(shù)的遍歷和生成樹求解的各個(gè)功能。4）選擇合適的變量，來表示樹的相關(guān)信息。5）當(dāng)信息出錯(cuò)時(shí)，程序應(yīng)給錯(cuò)誤信息提示，使程序設(shè)計(jì)得全面周密。3.方案實(shí)施1樹的存儲定義如下template<classT>classSplayingNode{public:SplayingNode(){left=right=parent=0;}SplayingNode(constT&el,SplayingNode*l=0,SplayingNode*r=0,SplayingNode*p=0){info=el;left=l;right=r;parent=p;}Tinfo;SplayingNode*left,*right,*parent;};template<classT>classSplayTree{public:SplayTree(){root=0;}voidinorder(){inorder(root);}T*search(constT&);voidinsert(constT&);2設(shè)計(jì)相應(yīng)的函數(shù)方法，函數(shù)如下所示SplayingNode<T>*root;voidrotateR(SplayingNode<T>*);voidrotateL(SplayingNode<T>*);voidcontinueRotation(SplayingNode<T>*gr,SplayingNode<T>*par,SplayingNode<T>*ch,SplayingNode<T>*desc);voidsemisplay(SplayingNode<T>*);voidinorder(SplayingNode<T>*);voidvirtualvisit(SplayingNode<T>*)3完善相應(yīng)函數(shù)體的具體代碼實(shí)現(xiàn)4.結(jié)果與結(jié)論實(shí)驗(yàn)截圖如下：1先輸入文件名，然后它會打開文本文件讀取錄入內(nèi)容圖（1）：運(yùn)行界面2文本文件內(nèi)容如圖2所示圖（2）：文本內(nèi)容3統(tǒng)計(jì)每個(gè)單詞出現(xiàn)的次數(shù)并顯示最后的結(jié)果圖（3）：輸出結(jié)果5.收獲與致謝通過本次課程設(shè)計(jì)對樹的各種操作，我們對數(shù)據(jù)結(jié)構(gòu)的知識點(diǎn)都有了進(jìn)一步的理解，更熟練的掌握了各種算法。在課程設(shè)計(jì)的過程中，我們小組成員之間，相互探討，相互學(xué)習(xí)。我們把自己掌握熟練的東西發(fā)揮了出來，同時(shí)也對平時(shí)不是很精通的部分有了更深入的了解。在課程設(shè)計(jì)之初分派任務(wù)時(shí)，我們組長提倡我們每個(gè)組員都做一整套的設(shè)計(jì)內(nèi)容，這是我們的壓力，但同時(shí)也是我們的機(jī)會，雖然任務(wù)會比較多，但大家都能更多地掌握課本上的知識，是我們今年的收獲更加豐富。這個(gè)過程中是我們查漏補(bǔ)缺的過程。結(jié)果也顯示出我們組長是英明的，我相信我們每個(gè)人都收獲到自己所需要的。在之前的實(shí)驗(yàn)中，很多都是照書本敲進(jìn)電腦，但這個(gè)課程設(shè)計(jì)，是我們需要結(jié)合平時(shí)的知識去自主開發(fā)的，這對平時(shí)并沒有多少經(jīng)驗(yàn)的我無疑是很困難的，不過做完之后也使我對上機(jī)實(shí)驗(yàn)有了更牢固的掌握不論怎么說，在這個(gè)星期里，有憂心，有歡喜，有激動，讓我們認(rèn)識到了團(tuán)隊(duì)合作的重要性，體會到集體的力量，體會到要互幫互助才能最大的成功。謝謝我的小組成員們，謝謝我的郭老師！6.參考文獻(xiàn)[1]數(shù)據(jù)結(jié)構(gòu)（c語言版），清華大學(xué)出版社[2]C++數(shù)據(jù)結(jié)構(gòu)與算法（第四版），清華大學(xué)出版社[3]C++程序設(shè)計(jì)教程，清華大學(xué)出7.附件1genSplay.h代碼如下//****************************genSplay.h****************************//genericsplayingtreeclass#ifndefSPLAYING#defineSPLAYINGtemplate<classT>classSplayTree;template<classT>classSplayingNode{public:SplayingNode(){left=right=parent=0;}SplayingNode(constT&el,SplayingNode*l=0,SplayingNode*r=0,SplayingNode*p=0){info=el;left=l;right=r;parent=p;}Tinfo;SplayingNode*left,*right,*parent;};template<classT>classSplayTree{public:SplayTree(){root=0;}voidinorder(){inorder(root);}T*search(constT&);voidinsert(constT&);protected:SplayingNode<T>*root;voidrotateR(SplayingNode<T>*);voidrotateL(SplayingNode<T>*);voidcontinueRotation(SplayingNode<T>*gr,SplayingNode<T>*par,SplayingNode<T>*ch,SplayingNode<T>*desc);voidsemisplay(SplayingNode<T>*);voidinorder(SplayingNode<T>*);voidvirtualvisit(SplayingNode<T>*){}};template<classT>voidSplayTree<T>::continueRotation(SplayingNode<T>*gr,SplayingNode<T>*par,SplayingNode<T>*ch,SplayingNode<T>*desc){if(gr!=0){//ifphasagrandparent;if(gr->right==ch->parent)gr->right=ch;elsegr->left=ch;}elseroot=ch;if(desc!=0)desc->parent=par;par->parent=ch;ch->parent=gr;}template<classT>voidSplayTree<T>::rotateR(SplayingNode<T>*p){p->parent->left=p->right;p->right=p->parent;continueRotation(p->parent->parent,p->right,p,p->right->left);}template<classT>voidSplayTree<T>::rotateL(SplayingNode<T>*p){p->parent->right=p->left;p->left=p->parent;continueRotation(p->parent->parent,p->left,p,p->left->right);}template<classT>voidSplayTree<T>::semisplay(SplayingNode<T>*p){while(p!=root){if(p->parent->parent==0)//ifp'sparentistheroot;if(p->parent->left==p)rotateR(p);elserotateL(p);elseif(p->parent->left==p)//ifpisaleftchild;if(p->parent->parent->left==p->parent){rotateR(p->parent);p=p->parent;}else{rotateR(p);//rotatepanditsparent;rotateL(p);//rotatepanditsnewparent;}else//ifpisarigthchild;if(p->parent->parent->right==p->parent){rotateL(p->parent);p=p->parent;}else{rotateL(p);//rotatepanditsparent;rotateR(p);//rotatepanditsnewparent;}if(root==0)//updatetheroot;root=p;}}template<classT>T*SplayTree<T>::search(constT&el){SplayingNode<T>*p=root;while(p!=0)if(p->info==el){//ifelisinthetree,semisplay(p);//moveitupward;return&p->info;}elseif(el<p->info)p=p->left;elsep=p->right;return0;}template<classT>voidSplayTree<T>::insert(constT&el){SplayingNode<T>*p=root,*prev=0,*newNode;while(p!=0){//findaplaceforinsertinganewnode;prev=p;if(el<p->info)p=p->left;elsep=p->right;}if((newNode=newSplayingNode<T>(el,0,0,prev))==0){cerr<<"Noroomfornewnodes\n";exit(1);}if(root==0)//thetreeisempty;root=newNode;elseif(el<prev->info)prev->left=newNode;elseprev->right=newNode;}template<classT>voidSplayTree<T>::inorder(SplayingNode<T>*p){if(p!=0){inorder(p->left);visit(p);inorder(p->right);}}#endifSplay.cpp代碼如下#include<iostream>#include<fstream>#include<cctype>#include<cstring>#include<cstdlib>//exit()#include"genSplay.h"usingnamespacestd;classWord{public:Word(){freq=1;}intoperator==(constWord&ir)const{returnstrcmp(word,ir.word)==0;}intoperator<(constWord&ir)const{returnstrcmp(word,ir.word)<0;}private:char*word;intfreq;friendclassWordSplay;};classWordSplay:publicSplayTree<Word>{public:WordSplay(){differentWords=wordCnt=0;}voidrun(ifstream&,char*);private:intdifferentWords,//counterofdifferentwordsinatextfile;wordCnt;//counterofallwordsinthesamefile;voidvisit(SplayingNode<Word>*);};voidWordSplay::visit(SplayingNode<Word>*p){differentWords++;wordCnt+=p->info.freq;}voidWordSplay::run(ifstream&fIn,char*fileName){charch='',i;chars[100];Wordrec;while(!fIn.eof()){while(1)if(!fIn.eof()&&!isalpha(ch))//skipnonlettersfIn.get(ch);elsebreak;if(fIn.eof())//spacesattheendoffIn;break;for(i=0;!fIn.eof()&&isalpha(ch);i++){s[i]=toupper(ch);fIn.get(ch);}s[i]='\0';if(!(rec.word=newchar[strlen(s)+1])){cerr<<"Noroomfornewwords.\n";exit(1);}strcpy(rec.word,s);Word*p=search(rec);if(p==0)insert(rec);elsep->freq++;}inorder();cout<<"\n\nFile"<<