用c 解决统计字母频率并编码的问题

用C++解决统计字母频率并编码的问题摘要本次课程主要解决如何统计一段英文中各字母出现的频率，并用哈夫曼树进行编码的问题。在课程设计中，系统开发平台为WindowsXP，程序设计语言采用VisualC++，程序运行平台为WindowsXP。在本程序中，任意输入一段长度有限的英文，程序将自动统计其中各字母出现的次数并计算其在整个英文中的频率。然后应用哈夫曼树原理对各字母及相应的频率进行优化编码。在设计过程中，采用了面向对象的设计方案解决问题的方法。在编码完成后，程序通过调试运行，初步实现了设计目标，基本上达到了设计要求。并且经过适当完善后，可以应用到其它关键领域。关键词程序设计；数据结构；统计次数；频率；哈夫曼；C++；编码1引言针对当前我国高等教育的发展形势以及为了适应21世纪人才培养的需要，培养具有特色的计算机人才，学生在校期间的课程设计项目已变成一个重要的教育手段。学生在课程设计的过程中，既可以学到新的知识，又可以增加本身的动手能力，以学生自己的求学，代替老师的讲学。因此，课程设计对于深化我国高等学校的教学改革是一件十分有意义的事。这次的课程设计主要解决如何统计一段英文中各字母出现的频率，并用哈夫曼树进行编码的问题。在程序设计的初期，构思用何种数据结构保存数据，用什么算法进行统计计算是一个非常重要的问题。经过反复思考筛选，得到本程序的数据结构。在程序开发设计过程中，本人选择系统开发平台为WindowsXP,程序运行平台为WindowsXP.设计语言采用VisualC++。在程序开发中期，如何进行函数之间的参数传递，采用何种方式传递，怎样精程序实现步骤，也耗费了开发者相当长的时间。最后的调试运行，是最艰难的工作。选择边缘数据进行调试是调试程序的一般方法，该程序也采用此方法。经过初步的调试运行，基本实现要设计要求。并且在得到适当的完善后，可以运用于其它关键领域。计算机在进行编码时，有等长编码和不等长编码两种。等长编码对于使用频率相同的字符来说，具有节省空间的好处。如果字符的使用频率大不相同，则使用不等长编码。哈夫曼树对于不等长编码，具有非常大的优势，对于出现频率高的字符，尽量采用长度短的编码，对于出现频率较高的字符，可适当采用较长的编码。这样，会获得很好的空间效率。这个思想是今天广泛使用的文件压缩技术的核心。在程序中主要设计的两个基本功能，分别为统计功能和编码功能。任意输入一段长度有限的英文，程序中会自动统计其中各个字母出现的次数，并计算其在整个英文中的频率。然后将计算结果传递给编码函数，编码函数根据哈夫曼树原理对各个字母及其相应的频率进行优化编码。最终结果保存在程序设计初期设计的数据结构数组中，便于文件压缩保存。本程序经规划、设计、编码到运行实现，无一不渗透着制作者辛劳的汗水。但由于本人经验和学识有限，定有很多不足之处，希望能得到各位老师以及其他高手的指教修订，使程序不断完善。2设计思路与方案2.1课程设计目的在进行程序设计或者通信时，经常通过给每一个字符标记一个单独的代码来表示一组字符，我们称之为编码。例如，标准ASCII码把每个字符分别用一个7位的二进制数表示，这种方法使用最少的位表示了所有ASCII码中的128个字符。假设所有代码都等长，则表示n个不同的字符需要[log2n]位，这称之为等长编码。如果每个字符的使用频率相等，等长编码是空间效率最高的方法。如果字符出现频率不同，则等长编码则会浪费大部分的空间。为了能更好地节资源及空间，可以采用不等长编码。本课程采用的是哈夫曼树编码2.2课程设计原理对于不等长编码，如果设计得不合理，可能出现多种译码方式，会给译码带来困难。因此，设计不等长编码时，还必须考虑译码的惟一性。如果一组编码中任一编码都不是其他任何一个编码的前缀，我们称这组编码为前缀编码(prefixcode).前缀编码保证了编码被解时不会有多种可能。哈夫曼树可用于构造最短的不等长编码方案，具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在字符串中出现的频率为{w1,w2,…,wn},以d1，d2，…，dn作为叶子结点，w1,w2,…,wn作为叶子结点的权值，构造一棵哈夫曼编码树，规定只夫曼编码树的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0和1的序列便成为该叶子结点对应字符的编码，称为哈夫曼编码。在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，所以采用哈夫曼树构造的编码是一种能便字符串的编码总长度最短的的不等长编码。由于哈夫曼编码树的每个字符结点都是叶子结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的惟一性。2.3课程设计内容本次的课程设计涉及的内容主要是：用键盘任意输入一段长度有限的英文字母；用数据结构的相关方法统计其中各个字母在文中出现的频率；将各字母及相应的频率按一定的算法进行哈夫曼编码；将编码后的具体信息输出，使程序功能更加清晰明了；2.4设计预计耗费时间本次课程设计从9月1日开始，预计：用两天的时间进行数据结构的构思；用三天的时间进行功能函数的规划；用三天时间进行具体编码；用七天时间进行程序的调试运行；总计耗时一十五天。如果不出意外，可以在规定时间内完成任务。3详细设计与实现3.1需求分析本课程设计要解决三个问题：如何统计一段英文中各字母的出现频率；如何用哈夫曼编码树对上述频率进行编码；如何将进行哈夫曼编码结点的具体信息输出。3.2设计程序在设计程序初期，必须构思适合上述需求的数据结构进行存储。在本程序中，设置了一个数组huff[2n-1]用来保存哈夫曼树中各结点的信息，数组元素的结点数据类型如图2-1所示：weightlchildrchildparent图3-1哈夫曼树的结点结构其中，weight是权值域，保存该结点的权值；lchild是指针域（游标），保存该结点的左孩子结点在数组中的下标；rchild是指针域（游标），保存该结点的右孩子结点在数组中的下标；parent是指针域（游标），保存该结点的双亲结点在数组中的下标。为了判定一个结点是否已经加入到哈夫曼树中，可通过parent域的值来确定。初始parent域的值为-1，当某结点加入到树中时，该结点parent域的值为其双亲结点在数组中的下标。设计完所需的数据类型，中期的任务是声明实现需求功能的函数，在程序定义的statistic类中，声明了五个成员函数，其具体名称和功能如表2-1所示：表3-1实现统计编码的函数函数声明功能声明voidhufftree(intn)数据初始化，并将保存哈夫曼树结点的数组中所有元素的游标值赋为-1；voidhuffcombine(intn)将选出的两个最小权值的结点进行合并，共进行2n-1次；intaccount(charenglish[])根据输入的英文统计各字母出现频率；voidoutput(intn)输出各结点具体信息；intsearch(intn)寻找当前未合并的结点中权值最小的结点。对于如何实现这些函数的功能，是本程序设计的关键。首先是进行字母统计。在intaccount(charenglish[])中，采用switch程序分支的方法，将在数组中读到的各字母进行分类统计，并相加得出总数。然后根据公式letter[locate2]*100/sum计算出各字母的出现频率，将结果保存在数组frequency[locate1]中。统计完各字母的出现频率后，要对其频率进行哈夫曼编码。在函数voidhuffcombine(intn)中，调用intsearch(intn)函数将初始化后的各结点进行最小权值搜寻，将得到的两个结点进行合并得到一个新结点，其权值为当前两个最小权值结点的权值之和，并赋予他们父子关系。总共进行2n-1次。设叶子结点的权值集合为W={2，3，4，5}的哈夫曼树的构造过程如图2-2所示：345523455254543232(a)第一步(b)第二步1414953295325943254559432545(c)第三步(d)第四步图3-2哈夫曼树的建立过程将合并后形成的哈夫曼树各结点的主要信息输出，调用intsearch(intn)函数，用setiosflags(ios::left)成员函数让输出数据左对齐，并设字段宽度为10，可达到整齐的输出效果。3.3编码通过数据结构和函数原型的设计，已基本上完成了对程序的架构和功能的分析描述。具体的编码是一个比较繁琐的过程。本程序定义了一个头文件statistic.h、一个函数定义文件statistic.cpp以及一个主程序执行文件statisticmain.cpp。在头文件中定义了huffnode数据结构和statistic类（类中函数声明见表2-1）。statistic.cpp文件则对类中的函数进行了具体功能的定义。最后由主程序statisticmain.cpp调用功能函数，完成了程序设计初期的功能要求。4程序调试运行程序的调试运行是程序设计中耗时最长且难度最大的一个环节。程序调试的效率要根据程序开发者的开发经验而定。本人在该程序的开发过程中，也遇到了一系列棘手的问题，主要如下：根据设计编码后，编译通过，但是连接出个很多错误，经观察，错误个数和定义的函数个数相同，猜测这不是函数内部语法问题，而是外部问题。根据之前的编程经验，在头文件中定义的数据结构和类之前增加了模板。编译时发生一个错误，找到错误后将它先进行注释，编译通过，连接通过。如图3-1所示：Structhuffnode{Intweight;Intlchild,rchild,parent;};Template<classT>Structhuffnode{Intweight;Intlchild,rchild,parent;}图4-1调试过程（2）定义了一个含有模板的数据结构后，在接下声明的类中定义变量时发生编译错误，在查阅相关书籍后发现，在数据类型后要标记<T>符号。如图3-2所示：huffnodehuff[]huffnode<T>huff[]图4-2(3)至此，程序的编译和连接都已经通过。运行程序，按提示输入一段英文后，程序非法中断。由此判断，程序的算法存在错误的地方。在程序的第一个函数前标注，使程序由此一步一步运行。通过一遍遍地运行调试，发现在哈夫曼树结点权值的赋值上存在很大的不足，竟将频率为0的值也赋了进来，当即改正过来。编译连接，运行程序，程序仍然非法中断。仍按上述方法进行调试，发现在最小权值的搜寻上也存在着错误，修正后，程序正常运行。（4）在程序设计之前，我并没有想到设计有关哈夫曼树结点的信息输出。但在程序调试运行成功之后，发现无法让用户明白程序运行先后的差别，无法得知程序是否得到了正确的结果。于是，本课程设计结束之前，又添加了显示编码后哈夫曼树结点具体信息这个功能。使程序更加人性化，明了化。（5）程序运行界面如图4-3所示：图4-3运行界面5异常处理程序在执行时经常会出现一些违反设计期望的异常情况（如除零），过去的解决方法是利用操作系统中断代为处理。由于这种解决方法强行中止了应用程序的运行，一些大型的应用系统的开发人员提出，可以在允许的范围内由应用程序自身来处理一般性的程序运行错误。C++语言异常处理由三个部分构成。异常检测的触发、异常检测的捕获和异常检测的处理。它们分别对应了“try”、“throw”和“catch”三个关键字。这三者的关系如图4-1所示。图5-1C++异常处理流程图被throw语句扔出的数据实际上被压入了相应层的catch语句所对应的堆栈内，最后才被catch语句捕获到的。当try语句出现嵌套时，情况可能会更加复杂。在本程序中，try语句为：statistic<int>pra;//定义statistic类对象；intlength;length=pra.account(english);//得到不同出现频率字母的个数; pra.hufftree(length);//数据初始化，游标初始化；pra.huffcombine(length-1);//进行2n-1次合并；cout<<"-------pleaseoutputeverynodeinformation:--------"<<endl;pra.output(length);//输出各结点信息；当(strlen(english))>maxsize，即输入的英文长度超过定义的最大长度时，抛出异常throw0，程序跳出try范围，否则继续处理。当运行到catch(int)时跳过继续执行其后的语句；catch(int)在捕获异常消息的类型后，对其进行处理。处理语句为：cout<<"theparagraphisoverlong!"<<endl;异常处理完毕后，程序不会自动终止，而是继续处理catch子句之后的语句，本程序在返回主函数类型后，结束程序。6结束语这次的课程设计，从9月1日开始初期的规划，到9月13日程序顺利地通过运行，历时13天。比预估计的时间15天，提前了两天完成。在这期间，前期的数据结构及函数功能的规划耗费了一定长的时间，但主要的时间是用在了程序最后的调试运行上。通过这个程序设计，不难发现，面向对象的程序设计方法思路和人们日常生活中处理问题的思路是相似的。运用面向对象的程序设计方法，设计者的任务包括两个方面：一是设计所需的各种类和对象，即决定把哪些数据和操作封装在一起；二是考虑看样子向有关对象发送消息，以完成所需的任务。在本程序中，设计了一个数据类型huffnode和一个模板类statistic，在类中声明了五个功能函数，并将这些函数及相应的数据成员封装在一起，形成了一个黑盒，用户不需要知道盒子里面的构造，只需知道如何调用这些函数，以实现其需求。程序通过参数的形式向各个成员函数发送用户消息，成员在函数接收到消息后，对实参进行相应运算，返回运算结果。最后，输出用户所要的具体信息。在这次在课程设计中，我遇到了很多困难，其中不乏一些极其微末的细节问题。比如模板的格式问题等等。它们消耗了我大量的时间和精力去寻找问题所在。在困难面前，我曾一度地想要放弃，但最终在查阅了大量书籍和相关资料后，找到问题的关键，解决了难题。总结经验，吸取教训，我在这次的课程设计中学到了很多，解决了之前一直不曾明白的问题，亲自动手能力也得到了大大的增强。在此，我非常感谢一直在身边帮助我的同学们，当然还有我们数据结构的指导老师的敦敦教诲。由于本人能力有限，因此本程序还有很多的不足之处，希望大家不吝赐教，使它更加完善。参考文献[1] 谭浩强.C++程序设计.北京：清华大学出版社，2006[2] 王红梅，胡明，王涛.数据结构(C++版).北京：清华大学出版社,2007[3] F.BrokkenandK.Kubat.C++Annotations.Version4.4.0m，ICCE，UniversityofGroningen，Netherlands，1990.250～[4] 周晓聪，李文军，李师贤.面向对象程序设计——实践与提高.中山大学计算机科学学院讲义，1999[5] 粟利民，孙强.如何用VC++和VisualFoxpro进行ActiveX数据通讯.程序太平洋网站，/Info/38/Info15372/：2005-5-28附录：结构化设计源程序列表//程序名称：统计编码//程序功能：采用结构化方法设计程序，实现统计一段英文中各字母的出现频率，并对//其进行哈夫曼树编码的功能。//程序作者：林魁//最后修改日期：2008-9-13//头文件，函数声明；#ifndefstatistic_h#definestatistic_h#include<cstring>#include<iostream>#include<iomanip>usingnamespacestd;//////////////////////////////////////////////////////////////////////////////////////////////constintmaxsize=500;//宏定义///////////////////////////////////////////////////////////////////////////////////////////////////template<classT>//定义哈夫曼结点数据结构;structhuffnode{intweight;//权值intparent,lchild,rchild;//光标,指向数组下标;};//////////////////////////////////////////////////////////////////////////////////////////////template<classT>classstatistic{public:voidhufftree(intn); //初始化哈夫曼树结点的游标；;voidhuffcombine(intn); //合并形成哈夫曼树;intaccount(charenglish[]); //计算各英文字母的出现次数以及出现频率;voidoutput(intn);//输出各结点信息;private:huffnode<T>huff[51]; //保存哈夫曼树结点;intsearch(intn); //寻找数组中两个最小权值的结点下标;intfrequency[26]; //保存字母出现频率;};///////////////////////////////////////////////////////////////////////////////////////////////////////////////#endif//函数定义文件#include"statistic.h"///////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>intstatistic<T>::account(charenglish[]){if((strlen(english))>maxsize)throw0;//如果输入英文超出最大长度,抛出异常;intletter[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};intlocate=0,locate1=0,locate2=0;intsum=0,zero=0;//字母出现总次数及出现为0的次数赋初值0；while(english[locate]!='\0'&&locate<maxsize)//当不超过总长度和实际长度时；{switch(english[locate])//统计各英文字母的出现次数;{case'a':letter[0]++;break;case'b':letter[1]++;break;case'c':letter[2]++;break; case'd':letter[3]++;break; case'e':letter[4]++;break; case'f':letter[5]++;break; case'g':letter[6]++;break; case'h':letter[7]++;break; case'i':letter[8]++;break; case'j':letter[9]++;break; case'k':letter[10]++;break; case'l':letter[11]++;break; case'm':letter[12]++;break; case'n':letter[13]++;break; case'o':letter[14]++;break; case'p':letter[15]++;break; case'q':letter[16]++;break; case'r':letter[17]++;break; case's':letter[18]++;break; case't':letter[19]++;break; case'u':letter[20]++;break; case'v':letter[21]++;break; case'w':letter[22]++;break; case'x':letter[23]++;break; case'y':letter[24]++;break; case'z':letter[25]++;break; default:break;//其它字符不纳入计算；}locate++;}for(locate=0;locate<26;locate++){sum=sum+letter[locate];//统计各字母出现的总次数;}for(;locate2<26;locate1++,locate2++){frequency[locate1]=letter[locate2]*100/sum;//计算各字母出现的频率;if(frequency[locate1]==0){zero++;//统计出现次数为0的字母的个数;locate1--; //当字母频率为0时不纳入统计编码范围;}}return26-zero;//返回实际出现不同字母的个数;}/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>voidstatistic<T>::hufftree(intn){inti;for(i=0;i<2*n-1;i++)//初始化哈夫曼数组中各元素的光标值;{huff[i].parent=-1;huff[i].lchild=-1;huff[i].rchild=-1;}for(i=0;i<n;i++){huff[i].weight=frequency[i];//给哈夫曼结点数组中前N个元素的权置给定权值;}}///////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>intstatistic<T>::search(intn){inti,p,min;p=n+1;//将当前哈夫曼数组的最后一个元素的下一个地址赋给p;while(huff[n].parent!=-1&&n>=0)//当结点已合并时,跳到下一个;{n--;}if(n<0)return100;//查找失败时返回100;else{min=n;//给min下标赋初值n;for(i=n-1;i!=-1;i--){if(huff[i].parent==-1){if(huff[i].weight<huff[min].weight)min=i;//如果当前结点的权值比huff[min]中的权值小,则将当前结点的下标赋给min;}}huff[min].parent=p;//指定当前结点父亲结点的下标;returnmin;//返回最小权值结点的下标;}}////////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>voidstatistic<T>::huffcombine(intn){inti,j;i=search(n);//取当前最小权值结点的下标；j=search(n);//同上；if(j!=100){huff[n+1].weight=huff[i].weight+huff[j].weight;//两个最小权值结点的权值相加,得到父亲结点的权值;huff[n+1].lchild=i;huff[n+1].rchild=j;n++;huffcombine(n);//进行下一轮合并;}else{huff[i].parent=-1;//保证根结点的父亲结点下标为-1;cout<<"combineend"<<endl;//合并结束标志；}}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////