哈夫曼编/译码的设计与实现实验报告问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发编写一个哈夫曼码的编/译码系统。
基本要求（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。
（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。
（3）译码：利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。
（4）打印编码规则：即字符与编码的一一对应关系。
运行与调试（1）利用教科书中的数据调试程序。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS-PROGRAM-IS-MY-FA VORITE”。
字符 A B C D E F G H I J K L M 频度186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 1实验小结通过这次实验，让我对于树的应用多了认识，在读取文件时，遇到的一些困难，不过在和同学交流的过程中，解决了这个问题，我觉的自己对于树及文件的应用又有了一些进步。
通过这次实验，感觉收获很大。
源程序// 哈夫曼编译码的设计与实现.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"#include<iostream>#include<fstream>#include<string>#define Maxvalue 10000#define MAXBIT 200using namespace std;struct node{char letter;string num;};typedef struct{char letter;int weight; //结点权值int parent;int lchild;int rchild;}HnodeType;typedef struct{int bit[MAXBIT];int start;}HcodeType;HnodeType *HaffmanTree(int n){HnodeType *HuffNode;HuffNode=new HnodeType[2*n-1];int i,j;int m1,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;ofstream outFile("hfmtree.dat",ios::out);if(!outFile)cerr<<"文件打开失败！"<<endl;else{outFile<<" weight"<<" lchild"<<" rchild"<<"parent"<<endl;for(i=0;i<2*n-1;i++)outFile<<i<<"--"<<" "<<HuffNode[i].weight<<""<<HuffNode[i].lchild<<" "<<HuffNode[i].rchild<<""<<HuffNode[i].parent<<endl;outFile.close();}return HuffNode;}void HaffmanCode(HnodeType *HuffNode,int n){HcodeType *HuffCode,cd;HuffCode=new HcodeType[2*n-1];int c,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;}ofstream outFile1("codefile.dat",ios::out|ios::binary);if(!outFile1)cerr<<"文件打开失败！"<<endl;else{for(i=0;i<n;i++){outFile1<<HuffNode[i].letter;for(j=HuffCode[i].start+1;j<n;j++)outFile1<<HuffCode[i].bit[j];outFile1<<endl;}outFile1.close();}}int _tmain(int argc, _TCHAR* argv[]){HnodeType *HuffNode;int n,i;cout<<"请输入叶子结点个数：";cin>>n;if(cin.fail()){cout<<"输入有误！"<<endl;return 0;}HuffNode=HaffmanTree(n);HaffmanCode(HuffNode,n);int num;cout<<"请输入要加密的字母串的长度（空格也要计算在内）：";cin>>num;char *l1;char l;node l2[27];l1=new char[num];cout<<"请输入要加密的字母串（请用大写，如有空格请用“-”代替）：";for(int n=0;n<num;n++)cin>>l1[n];ofstream outFile2("bianma.dat",ios::out|ios::binary);if(!outFile2)cerr<<"文件打开失败！"<<endl;else{for(i=0;i<num;i++)outFile2<<l1[i];outFile2.close();}ifstream inFile1("codefile.dat",ios::in|ios::binary);ifstream inFile2("bianma.dat",ios::in|ios::binary);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;int a;cout<<"请输入要进行译码的串的个数：";cin>>a;string *s;s=new string[a];cout<<"请输入要解码的串（每输入一个串，请按一次【Enter】键）："<<endl; for(i=0;i<a;i++)cin>>s[i];ofstream outFile4("yima.dat",ios::out);if(!outFile4)cerr<<"文件打开失败！"<<endl;else{for(i=0;i<a;i++)outFile4<<s[i]<<endl;outFile4.close();}ifstream inFile3("codefile.dat",ios::in|ios::binary);cerr<<"读取文件失败！"<<endl;else{for(i=0;i<2*n-1;i++){inFile3>>l2[i].letter;inFile3>>l2[i].num;}ifstream inFile4("yima.dat",ios::in);if(!inFile4)cerr<<"读取文件失败！"<<endl;else{for(int j=0;j<a;j++)inFile4>>s[j];}for(int j=0;j<a;j++){for(i=0;i<n;i++){if(l2[i].num==s[j])cout<<l2[i].letter;}}inFile3.close();}return 0;}。