数据结构课程设计说明书-计算单词出现的频率

课程设计说明书课程名称：数据结构设计题目：计算单词出现的频率学院：计算机科学与信息工程学院课

程

设

计

任

务

书设计题目计算单词出现的频率学生姓名

所在院系计算机科学与信息工程专业、年级、班13级软件工程设计要求：当作者没有在文本上签名时，或者被认为其他人的作品时，需要确定文本作者的身份，可以使用单词频率分析这个工具。如果一直作家A创作了文本T1，文本T2经过仔细审查，其单词频率分布与T1十分相近，那么T2很有可能是由作者A创作的。不管这一方法在文学研究上的可靠性如何，我们都将编写一个程序扫描文本文件，并计算这一个文本中单词出现的频率。学生应完成的工作：1根据系统所需设计完成相关函数的构造2编译并且上机调试，得出正确的结论3结果分析4撰写实验报告5准备设计答辩参考文献阅读：1数据结构（c语言版），清华大学出版社2C++数据结构与算法（第四版），清华大学出版社3C++程序设计教程，清华大学出版社工作计划：1第一天：小组布置设计题目，说明进度安排2第二天：小组审题，查阅资料，进行设计前的必要资料的准备3第三天：程序编写，上机调试4第四天：同上5第五天：撰写实验报告

任务下达日期：

2015年

6

月

20

日任务完成日期：

2015年

6

月

26

日

指导教师（签名）：

学生（签名）：计算单词出现的频率摘要：树是一种比较重要的数据结构之一。在树型结构关系中，节点之间的关系不是任意的，数据元素之间是有一定关系的。本设计题目采用二叉树，运用“半张开”的技术来重新组织树。需要注意的是单词向根部移动时，需要改变所涉及及节点的连接关系，而不是将信息从一个节点传给它的父节点，再传给它的祖父节点。如果没有在树中找到单词，就为该单词创建一个新的叶节点，将其插入到树中。处理完所有单词后，对树进行中序遍历，计算所有节点的频率，再把这些频率级数加在一起并输出，作为树中单词个数和文件中单词个数的最后结果。关键词：树遍历组织树目录1.设计背景…………………51.1课程设计目………51.2题目要求…………52.设计方案…………………53.方案实施…………………54.结果与结论………………65.收获与致谢………………86.参考文献…………………97.附件………9.1.设计背景1.设计背景1.1课程设计目的通过本课程设计，加深对《数据结构与算法》课程所学知识的理解，熟练掌握和巩固C语言的基本知识和语法规范,培养调查研究、查阅技术文献、资料、手册以及编写技术文献的能力。学会编制结构清晰、风格良好的C语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。1.2题目要求课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。通过课程设计，巩固和加深对图等理论知识的理解；掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人动手能力，历练自身素质。2.设计方案设计方法问题的分析和结构的设计思路1）树的遍历和生成树求解的所有功能有：通过录入顶点个数和边数信息，采用两种图的两种存储结构：邻接矩阵、邻接表，输出邻接矩阵和邻接表；进行深度和广度优先遍历；普利姆算法和克鲁斯卡尔算法求解最小生成树；退出程序等功能。2）需要创建二叉树。3）选择合适的算法，实现数的遍历和生成树求解的各个功能。4）选择合适的变量，来表示树的相关信息。5）当信息出错时，程序应给错误信息提示，使程序设计得全面周密。3.方案实施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设计相应的函数方法，函数如下所示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完善相应函数体的具体代码实现4.结果与结论实验截图如下：1先输入文件名，然后它会打开文本文件读取录入内容图（1）：运行界面2文本文件内容如图2所示图（2）：文本内容3统计每个单词出现的次数并显示最后的结果图（3）：输出结果5.收获与致谢通过本次课程设计对树的各种操作，我们对数据结构的知识点都有了进一步的理解，更熟练的掌握了各种算法。在课程设计的过程中，我们小组成员之间，相互探讨，相互学习。我们把自己掌握熟练的东西发挥了出来，同时也对平时不是很精通的部分有了更深入的了解。在课程设计之初分派任务时，我们组长提倡我们每个组员都做一整套的设计内容，这是我们的压力，但同时也是我们的机会，虽然任务会比较多，但大家都能更多地掌握课本上的知识，是我们今年的收获更加丰富。这个过程中是我们查漏补缺的过程。结果也显示出我们组长是英明的，我相信我们每个人都收获到自己所需要的。在之前的实验中，很多都是照书本敲进电脑，但这个课程设计，是我们需要结合平时的知识去自主开发的，这对平时并没有多少经验的我无疑是很困难的，不过做完之后也使我对上机实验有了更牢固的掌握不论怎么说，在这个星期里，有忧心，有欢喜，有激动，让我们认识到了团队合作的重要性，体会到集体的力量，体会到要互帮互助才能最大的成功。谢谢我的小组成员们，谢谢我的郭老师！6.参考文献[1]数据结构（c语言版），清华大学出版社[2]C++数据结构与算法（第四版），清华大学出版社[3]C++程序设计教程，清华大学出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"<<