數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二哈夫曼樹(shù)

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)報(bào)告實(shí)驗(yàn)二 哈夫曼編碼專業(yè)： 電信工程 班級(jí)： 電信1105 學(xué)號(hào)： U201113196 姓名： 劉航 完成日期：2012/10/28 1一、 實(shí)驗(yàn)?zāi)康?、 掌握哈夫曼樹(shù)的基本概念及所有的存儲(chǔ)結(jié)構(gòu)。2、 掌握哈夫曼樹(shù)的建立算法。3、 掌握哈夫曼樹(shù)的應(yīng)用（哈夫曼編碼和譯碼）。4、 掌握對(duì)文件的使用。二、 實(shí)驗(yàn)內(nèi)容：隨機(jī)產(chǎn)生10000個(gè)數(shù)字并寫(xiě)入一個(gè)文件夾中，分別統(tǒng)計(jì)其中0、1、2、3、4、5、6、7、8、9出現(xiàn)的頻率，并以各自的頻率為權(quán)值，為其建立哈夫曼樹(shù)，并對(duì)每個(gè)數(shù)字進(jìn)行哈夫曼編碼，要求有較好的人機(jī)交互過(guò)程。三、 程序源代碼：#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出現(xiàn)的次數(shù)；float wN+1;const int n=10;const int m=2*n-1;struct tre

3、e /哈夫曼樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)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文件的時(shí)候，打開(kāi)方式：ios:in。文件不存在則自動(dòng)創(chuàng)建stringstream sstr;fstream outfile;int temp;/設(shè)定隨機(jī)數(shù)種子srand(unsigned)ti

4、me(NULL);for(int i=0;i<10000;i+)/產(chǎn)生隨機(jī)數(shù)temp =rand()%10;/將隨機(jī)數(shù)放在流sstr中sstr<<temp<<endl;/打開(kāi)文件，如果文件存放，清空，如果不存在，新建一個(gè)文件outfile.open(fileName,ios:in|ios:trunc|ios:out);if(!outfile)cerr<<"Error opening "<<fileName<<" failedn"<<endl;/將生成的數(shù)寫(xiě)入文件outfile&

5、lt;<sstr.str();outfile.close();void Statistic_Data() /讀取文件字符，統(tǒng)計(jì)頻率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; /遍歷文件，依次讀取每個(gè)字符 while(outfile>>s) for(i=0;i<10;i+)if(s=bi) +ai; outfile.close(); int main()int i;cout<<"welcom!"<<endl;cout<<"已隨機(jī)產(chǎn)生10000個(gè)數(shù)字（0到9)并存入文件liuhang.txt"<&l

7、t;endl;Get_Randnum ();Statistic_Data();for(i=0;i<10;i+)cout<<"數(shù)字"<<i<<"出現(xiàn)的次數(shù)為："<<ai<<endl;cout<<endl;cout<<"建立哈夫曼樹(shù)并編碼"<<endl;for(i=0;i<N;i+)wi+1=ai/10000.0;/*for(i=1;i<=N;i+)cout<<wi<<endl;*/ /這段代碼用于檢驗(yàn)

8、數(shù)字出現(xiàn)的概率是否已經(jīng)正確統(tǒng)計(jì)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; /這段代碼用于檢驗(yàn)哈夫曼樹(shù)是否已經(jīng)正確建立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;<"數(shù)字"<<codei.ch<<"的權(quán)值為："<<hftreei.weight<<setw(5)<<" 編碼為：" for(int j=codei.start;j<=n;j+) cout<<codei.bitsj<<" " cout<<endl;四、運(yùn)行截圖： 五、困惑及建議我覺(jué)得這個(gè)程序的重點(diǎn)有兩個(gè)地方：第一，隨機(jī)產(chǎn)出數(shù)字，并存入文件。這一點(diǎn)我們上學(xué)期C語(yǔ)言中沒(méi)有講到，然后我重新自學(xué)了C+中關(guān)于文件的知識(shí)，但在應(yīng)用中依然出了很多問(wèn)題，比如對(duì)幾個(gè)文件類的使用感到困惑，如何遍