哈夫曼编译码的设计与实现实验报告

哈夫曼编/译码的设计与实现实验报告问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。基本要求（1） 接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。（2） 编码：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。（3） 译码：利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。（4） 打印编码规则：即字符与编码的一一对应关系。运行与调试（1）利用教科书中的数据调试程序。(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS-PROGRAM-IS-MY-FVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811615C:\TIHDOTS\systeB32XcMd-ekc请输入每■?■叶子结点的字母和枚■直（步如fl5j:-186A64B13C22D32E1B3F21G15114?157J1略L57M2RNR7063P15Q1R48S51180U23U8weight13211557fl2TTTTTTTTTTTTTrchild1111111111weight13211557fl2TTTTTTTTTTTTTrchild11111111111111111111parent49443236384635324U41273042424333274041C&C:\WINBOWS\.s!ysten32\c».d.ex:e*甘一-UM-1-14b▲21一23-1-13622一8-1-13123-181-13424——1-1-1282E——-1-133——1-1-128—27—2173928—224262929—427283038—929113131—17223Q3432—28273733—3116253734—3bJIN3部35一411363936—4532139375932334338-G7d3d4439——8635364540—9SR1S4fi41——1RR1994742—11412144743—122371548晶一13113848▼

实验小结通过这次实验，让我对于树的应用多了认识，在读取文件时，遇到的一些困难，不过在和同学交流的过程中，解决了这个问题，我觉的自己对于树及文件的应用又有了一些进步。通过这次实验，感觉收获很大。源程序//哈夫曼编译码的设计与实现.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#include<iostream>#include<fstream>#include<string>#defineMaxvalue10000#defineMAXBIT200usingnamespacestd;structnode{charletter;stringnum;};typedefstruct{charletter;intweight; 〃结点权值intparent;intlchild;intrchild;}HnodeType;typedefstruct{intbit[MAXBIT];intstart;}HcodeType;HnodeType*HaffmanTree(intn){HnodeType*HuffNode;HuffNode=newHnodeType[2*nT];inti,j;intm1,m2,x1,x2;for(i=0;i<2*n-1;i++) 〃数组HuffNode[]初始化{HuffNode[i].weight=0;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;cout<<"请输入每个叶子结点的字母和权值(形如A5)："<<endl;for(i=0;i<n;i++)cin>>HuffNode[i].letter>>HuffNode[i].weight; 〃输入n个叶子结点的权值for(i=0;i<n-1;i++) //构造哈夫曼树{m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j++) 〃选取最和次小两个权值{if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1){m2=m1;x2=x1;m1=HuffNode[j].weight;x1=j;}else{if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2){m2=HuffNode[j].weight;x2=j;}}}//将找出的两棵子树合并为一棵子树HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;}cout<<"weight"<<" lchild"<<" rchild"<<" parent"<<endl;for(i=0;i<2*n-1;i++)cout<<i<<"一"<<" "<<HuffNode[i].weight<<" "<<HuffNode[i].lchild<<”"<<HuffNode[i].rchild<<" "<<HuffNode[i].parent<<endl;ofstreamoutFile("hfmtree.dat”,ios::out);if(!outFile)cerr<<"文件打开失败！"<<endl;else{outFile<<"weight"<<" lchild"<<" rchild"<<"parent"<<endl;outFile<<i<<"一"<<" "<<HuffNode[i].weight<<”"<<HuffNode[i].lchild<<" "<<HuffNode[i].rchild<<”"<<HuffNode[i].parent<<endl;outFile.close();}returnHuffNode;}voidHaffmanCode(HnodeType*HuffNode,intn){HcodeType*HuffCode,cd;HuffCode=newHcodeType[2*nT];intc,p,i,j;for(i=0;i<n;i++){cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1){if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HuffNode[c].parent;}for(j=cd.start+1;j<n;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}for(i=0;i<n;i++){cout<<HuffNode[i].letter;for(j=HuffCode[i].start+1;j<n;j++)cout<<HuffCode[i].bit[j];cout<<endl;}ofstreamoutFile1("codefile.dat”,ios::out|ios::binary);if(!outFile1)cerr<<"文件打开失败！"<<endl;else{outFile1<<HuffNode[i].letter;for(j=HuffCode[i].start+1;j<n;j++)outFile1<<HuffCode[i].bit[j];outFile1<<endl;}outFile1.close();}}int_tmain(intargc,_TCHAR*argv[]){HnodeType*HuffNode;intn,i;cout<<"请输入叶子结点个数：”；cin>>n;if(cin.fail()){cout<<"输入有误！"<<endl;return0;}HuffNode=HaffmanTree(n);HaffmanCode(HuffNode,n);intnum;cout<<"请输入要加密的字母串的长度(空格也要计算在内)："；cin>>num;char*l1;charl;nodel2[27];l1=newchar[num];cout<<"请输入要加密的字母串(请用大写，如有空格请用“-”代替)：”;for(intn=0;n<num;n++)cin>>l1[n];ofstreamoutFile2("bianma.dat”,ios::out|ios::binary);if(!outFile2)cerr<<"文件打开失败！"<<endl;else{for(i=0;i<num;i++)outFile2<<l1[i];outFile2.close();}ifstreaminFile1("codefile.dat”,ios::in|ios::binary);ifstreaminFile2("bianma.dat”,ios::in|ios::binary);if(!inFile1)cerr<<"读取文件失败！"<<endl;if(!inFile2)cerr<<"读取文件失败！"<<endl;else{while(inFile2.peek()!=EOF){inFile2>>l;for(i=0;i<2*n-1;i++){inFile1>>l2[i].letter;inFile1>>l2[i].num;}for(i=0;i<n;i++){if(l2[i].letter==l)cout<<l2[i].num<<”";}}inFile1.close();inFile2.close();}delete[]l1;cout<<endl;inta;cout<<"请输入要进行译码的串的个数："；cin>>a;string*s;s=newstring[a];cout<<"请输入要解码的串(每输入一个串，请按一次【Enter】键)："<<endl;for(i=0;i<a;i++)cin>>s[i];ofstreamoutFile4("yima.dat”,ios::out);if(!outFile4)cerr<<"文件打开失败！"<<endl;else{for(i=0;i<a;i++)outFile4<<s[i]<<endl;outFile4.close();}ifstreaminFile3("codefile.dat”,ios::in|ios::binary);if(!inFile3)cerr<<"读取文件失败！"<<endl;else{for(i=0;i<2*n-1;i++){in