哈夫曼树-课程设计报告

数据结构课程设计报告题目：哈夫曼树及其应用学生姓名：刘昶志学号：1021111609班级：10211116指导教师：张军2012年6目录需求分析说明~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~3总体设计~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~4详细设计~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~5实现局部~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~7程序测试~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~9总结~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~10一．需求分析说明设计目的：熟悉树的各种存储结构及其特点。掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。设计内容数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼〔Huffman〕编码原理是一种利用二叉树实现的编码原理哈夫曼〔Huffman〕编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。在信息传递时，希望长度能尽可能短，即采用最短码。哈夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。二．总体设计哈夫曼树编/译码系统哈夫曼树编/译码系统初始化初始化退出重新建立哈夫曼树重新建立哈夫曼树编码编码打印编码译码〔1〕.初始化：提示初始化界面→提示各字符及其权值将存放在hfmTree中→以字母出现次数为权值建立哈弗曼树→弹出选择菜单进行进一步操作；〔2〕.编码：弹出编码界面→读取文件→提示输入要编码的字符串→对文本进行哈弗曼编码并输出编码→保存编码文件；〔3〕.译码：弹出译码界面→利用建立好的哈弗曼树进行译码→将译码输出→保存译码文件；三．详细设计1.数据结构设计#include<iostream.h>//包含的库函数#include<string.h>#include<iomanip.h>constintn=6;//叶子数目constintm=2*n-1;//森林中树的棵树constintc=4;classtree{public:chardata;intweight;//权值intparent;//双亲intlch,rch;//左右孩子voidcreathafumantree();//建立哈夫曼树voideditcode();//编码函数voidtrancode(charb[],intmax);//译码函数};2．算法设计哈夫曼树编码算法：输入字符，权值算法：输入一些字符,然后再输入相对应数量的权值,建哈夫曼树,然后进行编码,并得到相对应的哈夫曼编码。voidtree::editcode(){//编码inti,j,k,f,count=0;intcode[n+1][c+1];for(i=1;i<=n;i++)for(j=1;j<=c;j++)code[i][j]=2;for(i=1;i<=n;i++){k=1;j=hftree[i].parent;f=i;while(j!=0){if(hftree[j].lch==f){code[i][k++]=0;}else{code[i][k++]=1;}j=hftree[j].parent; f=hftree[f].parent;}}cout<<endl;for(i=1;i<=n;i++){cout<<"权值为"<<hftree[i].weight<<"的编码为:"<<"";for(j=c;j>=1;j--){if(code[i][j]!=2){cout<<code[i][j]<<"";count+=1;}}cout<<endl;} count=count/n;cout<<"平均编码的长度为:"<<count<<endl;}哈夫曼树译码算法：译码：弹出译码界面→利用建立好的哈弗曼树进行译码→将译码输出→保存译码文件voidtree::trancode(charb[],intmax){//译码inti=0;intj=m;cout<<"该段代码编译为:"<<endl;while(b[i]!='\0'){if(b[i]=='0')j=hftree[j].lch;elsej=hftree[j].rch;if(hftree[j].lch==0&&hftree[j].rch==0){cout<<hftree[j].weight;j=m;}i++;}}四．实现局部classtree{public:chardata;intweight;//权值intparent;//双亲intlch,rch;//左右孩子voidcreathafumantree();//建立哈夫曼树voideditcode();//编码函数voidtrancode(charb[],intmax);//译码函数};voidtree::editcode(){//编码inti,j,k,f,count=0;intcode[n+1][c+1];for(i=1;i<=n;i++)for(j=1;j<=c;j++)code[i][j]=2;for(i=1;i<=n;i++){k=1;j=hftree[i].parent;f=i;while(j!=0){if(hftree[j].lch==f){code[i][k++]=0;}else{code[i][k++]=1;}j=hftree[j].parent; f=hftree[f].parent;}}cout<<endl;for(i=1;i<=n;i++){cout<<"权值为"<<hftree[i].weight<<"的编码为:"<<"";for(j=c;j>=1;j--){if(code[i][j]!=2){cout<<code[i][j]<<"";count+=1;}}cout<<endl;} count=count/n;cout<<"平均编码的长度为:"<<count<<endl;}voidtree::trancode(charb[],intmax){//译码inti=0;intj=m;cout<<"该段代码编译为:"<<endl;while(b[i]!='\0'){if(b[i]=='0')j=hftree[j].lch;elsej=hftree[j].rch;if(hftree[j].lch==0&&hftree[j].rch==0){cout<<hftree[j].weight;j=m;}i++;}}五．程序测试1.menu菜单图2.输入各值并生成编码图3.输入编码生成译码图六．总结1.设计体会当刚拿到程序课题时，一看，感觉都挺容易的，都是我们学过的一些内容，应该很容易完成，于是就从中选了一个哈夫曼树的应用。结果一作才知道，并不如我们想的那么容易。对于建立哈夫曼树，创立哈夫曼编码等算法，总是因一点不对而编译不成功。2.心得体会通过数据结构课程设计，我的c++语言水平有了比拟大的提高，其中c++语言关于类的操作理解的比以前深刻不少。另外是数据结构方面的提高，对哈夫曼树的构造，及哈夫曼码方面也有不少的提高。在工程中也出现了很多的问题，最大的问题就是对程序设计框架结构的不了解，在实现代码与功能的连接时经常会出现各种不同的错误，在实现一些功能时系