C++哈弗曼編碼實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)集中上機(jī)試驗(yàn)報(bào)告學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)：班級(jí)：姓名：2010-12-題目：哈弗曼編碼需求分析：I：初始化。從文件讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立Huffman樹，。E：編碼〔encoding〕。利用以建好的HuffmanTree〔如不在內(nèi)在，那么從文件hfmzifu中讀入〕，對(duì)用戶給定文件中正文進(jìn)行編碼，然后將結(jié)果存入用戶給定文件中。D：譯碼(decoding)。利用已建好的HuffmanTree對(duì)輸入的文件中的代碼進(jìn)行譯碼，結(jié)果存入用戶給定文件中。T：印HuffmanTree。將已在內(nèi)在中的HuffmanTree以直觀的方式顯示在終端上。詳細(xì)設(shè)計(jì)源文件：Huffmantree.cpp函數(shù)有主函數(shù)main()；求最小的權(quán)值minl(HuffmanTi);選擇函數(shù)Silect(HuffmanTreet,inti,int*s1,int*s2);哈弗曼編碼函數(shù)HuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn)；源程序#include<iostream>#include<fstream>#include<cstring>usingnamespacestd;typedefstruct{ intweight;intparent;intlchild;intrchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;intminl(HuffmanTreet,inti);voidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn);voidselect(HuffmanTreet,inti,int*s1,int*s2);//--------------------------------------------------------------------------voidmain(){HuffmanTreeHT;HuffmanCodeHC;ifstreamin("hfmzifu.txt");int*w,n,i;cout<<"從文件hfmzifu.txt輸入字符的個(gè)數(shù),字符，權(quán)值,#代表空格"<<endl;in>>n;char*ch;ch=(char*)malloc((n+1)*sizeof(char));w=(int*)malloc(n*sizeof(int));for(i=0;i<n;i++){in>>ch[i+1];in>>w[i];}//給w賦值。HuffmanCoding(&HT,&HC,w,n);//建哈弗曼樹cout<<"--------------------------------------------------------"<<endl; cout<<"請(qǐng)選擇操作："<<endl; cout<<"1:輸出哈弗曼樹;"<<endl;cout<<"2:從Myinput文件中讀取字符然后編碼存入codemyinput文件中;"<<endl;cout<<"3:從codemyinput讀取編碼輸入到頻幕上;"<<endl;cout<<"4:將codemyinput讀取編碼譯碼后存盤;"<<endl;cout<<"0:退出系統(tǒng)?。。?！"<<endl;cout<<"請(qǐng)輸入你的選擇："<<endl;while(true){intc;cin>>c;if(c==0) { cout<<"退出系統(tǒng)！"<<endl;break; }while(c>4||c<0) {cout<<"你輸入有誤請(qǐng)重新輸入："<<endl;cin>>c; }fstreamfile;ofstreamoutfile;ifstreamprintfile;ifstreamcodefile;ofstreamMyoutput; if(c==1) {cout<<"哈弗曼樹為:"<<endl; cout<<endl;for(i=1;i<=n;i++) {cout<<ch[i]<<"的編碼是："<<HC[i]<<endl; } }//------------從Myinput文件中讀取字符然后編碼存入codemyinput文件中--------------if(c==2) {file.open("Myinput.txt",ios::in);//從文件Myinput中讀取字符。outfile.open("codemyinput.txt",ios::out);//將讀取出的字符進(jìn)行編碼存入codemyinput文件中去、charread;cout<<"從Myinput文件中讀取的數(shù)據(jù)為："<<endl;while(!file.eof()) {file.get(read);cout<<read;for(i=1;i<=n;i++) {if(ch[i]==read)//outfile<<read<<"的哈弗曼編碼為："; {outfile<<HC[i];//將對(duì)應(yīng)字符的編碼輸出到文件中。break; } }if(i>n) {outfile<<read; } }//讀取文件完畢outfile.close();file.close();cout<<"\n______________________"<<endl; }//-------------從codemyinput讀取編碼輸入到頻幕上。----------------if(c==3) {printfile.open("codemyinput.txt",ios::in);intcount=0;charc;cout<<"\n這些字母對(duì)應(yīng)的哈夫曼編碼是："<<endl;while(!printfile.eof()) {printfile.get(c);cout<<c;if(count%77==0&&count!=0) {cout<<endl; }count++; }cout<<endl;printfile.close(); }//----------------將codemyinput讀取編碼譯碼后存盤--------------------------if(c==4) { codefile.open("codemyinput.txt",ios::in);Myoutput.open("Myoutput.txt",ios::out);intflag=2*n-1;charread;codefile.get(read);while(!codefile.eof())//cout<<read; {if(read=='0'||read=='1') {while(true) {if(flag>=1&&flag<=n)//判斷停止的條件 {Myoutput<<ch[flag];break; }elseif(read=='0') {flag=HT[flag].lchild; }else {flag=HT[flag].rchild; }codefile.get(read); }//while }//ifelse {Myoutput<<read;codefile.get(read); }flag=2*n-1; }//whilecodefile.close();Myoutput.close(); cout<<"編碼譯碼已存入文件Myoutput中!"<<endl;}//if}//while循環(huán)結(jié)束的括號(hào)。}intminl(HuffmanTreet,inti){inta,j,flag;intk=1000;for(a=1;a<=i;a++) {if(!t[a].parent) {flag=a;break; } }for(j=a;j<=i;j++) {if(t[j].parent==0&&t[j].weight<k) {k=t[j].weight;flag=j; } }t[flag].parent=1;returnflag;}//-----------------------------------------------------------------voidSelect(HuffmanTreet,inti,int*s1,int*s2){intj;*s1=minl(t,i);*s2=minl(t,i);if(*s1>*s2) {j=*s1;*s1=*s2;*s2=j; }}voidHuffmanCoding(HuffmanTree*HT,HuffmanCode*HC,int*w,intn){ if(n<=1)return;ints1,s2,start;char*cd=NULL;intm=2*n-1;*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));HuffmanTreep;inti,c,f;for(p=(*HT)+1,i=1;i<=n;i++,p++,w++) {(*p).weight=*w;(*p).parent=0;(*p).rchild=0;(*p).lchild=0; }for(;i<=m;i++,p++) {(*p).weight=0;(*p).parent=0;(*p).rchild=0;(*p).lchild=0; }for(i=n+1;i<=m;i++) { Select(*HT,i-1,&s1,&s2);//找出兩個(gè)權(quán)值最小的節(jié)點(diǎn)s1,s2.(*HT)[s1].parent=i;(*HT)[s2].parent=i;(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight; }//----從葉子到根逆向求每個(gè)字符的哈弗曼編碼----(*HC)=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;i++) {start=