数据结构实验二哈夫曼树

1、数据结构上机报告实验二 哈夫曼编码专业： 电信工程 班级： 电信1105 学号： U201113196 姓名： 刘航 完成日期：2012/10/28 1一、 实验目的1、 掌握哈夫曼树的基本概念及所有的存储结构。2、 掌握哈夫曼树的建立算法。3、 掌握哈夫曼树的应用（哈夫曼编码和译码）。4、 掌握对文件的使用。二、 实验内容：随机产生10000个数字并写入一个文件夹中，分别统计其中0、1、2、3、4、5、6、7、8、9出现的频率，并以各自的频率为权值，为其建立哈夫曼树，并对每个数字进行哈夫曼编码，要求有较好的人机交互过程。三、 程序源代码：#include <iostream>#i

2、nclude <string>#include <sstream>#include <ctime>#include <fstream>#include<stdlib.h>#include<iomanip>using namespace std;#define N 10string fileName="liuhang.txt" /你要生成的文件的名字int aN=0; /按顺序存放0到9出现的次数；float wN+1;const int n=10;const int m=2*n-1;struct tre

3、e /哈夫曼树的节点结构float weight; int parent; int lch,rch; struct codetypeint bitsn+1; int start; char ch;tree hftreem+1;struct codetype coden+1;void creathuffmantree();void huffcode();void Get_Randnum () /下面open文件的时候，打开方式：ios:in。文件不存在则自动创建stringstream sstr;fstream outfile;int temp;/设定随机数种子srand(unsigned)ti

4、me(NULL);for(int i=0;i<10000;i+)/产生随机数temp =rand()%10;/将随机数放在流sstr中sstr<<temp<<endl;/打开文件，如果文件存放，清空，如果不存在，新建一个文件outfile.open(fileName,ios:in|ios:trunc|ios:out);if(!outfile)cerr<<"Error opening "<<fileName<<" failedn"<<endl;/将生成的数写入文件outfile&

5、lt;<sstr.str();outfile.close();void Statistic_Data() /读取文件字符，统计频率int i;string s;string b="0","1","2","3","4","5","6","7","8","9" fstream outfile; outfile.open(fileName,ios:in);if(!outfile)cerr<&

6、lt;"Error opening "<<fileName<<" failedn"<<endl; /遍历文件，依次读取每个字符 while(outfile>>s) for(i=0;i<10;i+)if(s=bi) +ai; outfile.close(); int main()int i;cout<<"welcom!"<<endl;cout<<"已随机产生10000个数字（0到9)并存入文件liuhang.txt"<&l

7、t;endl;Get_Randnum ();Statistic_Data();for(i=0;i<10;i+)cout<<"数字"<<i<<"出现的次数为："<<ai<<endl;cout<<endl;cout<<"建立哈夫曼树并编码"<<endl;for(i=0;i<N;i+)wi+1=ai/10000.0;/*for(i=1;i<=N;i+)cout<<wi<<endl;*/ /这段代码用于检验

8、数字出现的概率是否已经正确统计creathuffmantree(); huffcode(); return 0;void creathuffmantree() int i,j,p1,p2; float s1,s2; for(i=1;i<=m;i+) hftreei.parent=0; hftreei.lch=0; hftreei.rch=0; hftreei.weight=0; for(i=1;i<=n;i+) hftreei.weight=wi; for(i=n+1;i<=m;i+) p1=p2=0; s1=s2=32767; for(j=1;j<=i-1;j+) i

9、f(hftreej.parent=0) if(hftreej.weight<s1) s2=s1; s1=hftreej.weight; p2=p1; p1=j; else if(hftreej.weight<s2) s2=hftreej.weight;p2=j; hftreep1.parent=i; hftreep2.parent=i; hftreei.lch=p1; hftreei.rch=p2; hftreei.weight=hftreep1.weight+hftreep2.weight; /for(i=N+1;i<=2*N-1;i+)/cout<<hftre

10、ei.weight<<endl; /这段代码用于检验哈夫曼树是否已经正确建立void huffcode()codetype cd; int c,p; for(int i=1;i<=n;i+) cd.start=n+1; cd.ch=47+i; c=i; p=hftreei.parent; while(p!=0) cd.start-; if(hftreep.lch=c)cd.bitscd.start=0; else cd.bitscd.start=1; c=p; p=hftreep.parent; codei=cd; for(int i=1;i<=n;i+) cout&l

11、t;<"数字"<<codei.ch<<"的权值为："<<hftreei.weight<<setw(5)<<" 编码为：" for(int j=codei.start;j<=n;j+) cout<<codei.bitsj<<" " cout<<endl;四、运行截图： 五、困惑及建议我觉得这个程序的重点有两个地方：第一，随机产出数字，并存入文件。这一点我们上学期C语言中没有讲到，然后我重新自学了C+中关于文件的知识，但在应用中依然出了很多问题，比如对几个文件类的使用感到困惑，如何遍