问题描述：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工通信（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试设计一个哈夫曼编码系统。
基本要求：
(1) 从文件中读入字符集大小n，以及n个字符和n个权值。
(2) 构建哈夫曼树，对每个字符生成哈夫曼编码。
(3) 从文件中读入需编码的字符串，利用哈夫曼编码，对字符串进行编码，编码结果保存在文件。
一、 需求分析：
（1）、根据输入的字符和字符的权值建立哈夫曼树。
（2）、字符的数目和字符的权值由用户自己设定。
（3）、根据建立的哈夫曼树进行，编码和译码操作。
二、概要设计 ：
1. 哈夫曼树的定义
typedef struct{
char letter; //存储字符
int weight; //存储字符的权值
int parent; //父亲
int lchild; //左孩子
int rchild; //右孩子
}HTNode,*HuffmanTree;
2. 算定义的存储结构
//本结构存储哈夫曼树、编码等，便于后面的操作进行
typedef struct
{
HuffmanTree HT;
//动态分配数组存储哈夫曼编码表
HuffmanCode HC;
//记录输入字符的长度，编码和译码用到
int len;
char *c;//存储输入的字符
}Huf;
3. 一些操作函数
void setHuffmanTree(HuffmanTree &HT,char *str,int *w,int n)
建立哈夫曼树，str是存储输入字符的数组，w 是存储字符权值的数组，n为输入字符的数目
Huf setHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n,char *s)
为哈夫曼树编码，HT是已经建立的哈夫曼树，HC用于存储编码，民为字符的数目，s是存储字符的数组
Huf Initialization()
初始化函数
void Encoding(Huf huf)
编码函数
void Decoding(Huf huf)
译码函数
void Print()
打印代码文件的函数
void Treeprinting(Huf huf)
打印哈夫曼树的函数
4. 主函数
void main(){
根据不同的选择，执行特定的函数，完成操作
}
三、详细设计
核心程序为哈夫曼树的构建，实现该功能时，通过不断调用selecte（在已有的结点中选择双亲结点值为0，且权值最小的两个结点）函数查找构造哈夫曼树中的各个子树的结点，直到所有这种结点全部用完，即一颗哈夫曼树即构造完成。
1、 建立哈夫曼树及求哈夫曼编码
//初始化操作，接受输入，调用函数setHuffmanTree，//setHuffmanCode创建树并编码
Huf Initialization(){
HuffmanTree HT;
HuffmanCode HC;
char c[100];//存放输入的字符
int w[100];//存放字符的权值
int n;
cout<<"请输入字符的个数："<<endl;
cin>>n;
cout<<"请输入所有字符："<<endl;
gets(c);
for(int i=1;i<=n;i++){
cout<<"请输入第"<<i<<"个字符的权值："<<endl;
cin>>w[i];
}
//将数组c中的元素向右移动一位
for(int j=n-1;j>=0;j--)
{
c[j+1]=c[j];
}
// 调用setHuffmanTree函数
setHuffmanTree(HT,c,w,n);
//调用setHuffmanCode函数
Huf huf=setHuffmanCode(HT,HC,n,c);
return huf;
}
//选择权值最小的两个结点
void Select(HuffmanTree &HT,int s,int &s1,int &s2){
int j, k, i;
j=k=10000;
s1=s2=0;
for(i=1;i<=s;i++){
if(HT[i].parent==0){
if(HT[i].weight<j){
k=j;s2=s1;
j=HT[i].weight;
s1=i;
}
else if(HT[i].weight<k){
k=HT[i].weight;
s2=i;
}
}
}
}
//创建哈夫曼树函数的具体实现
void setHuffmanTree(HuffmanTree &HT,char *str,int *w,int n)
{
HuffmanTree p;
int m,i,s1,s2; //s1,s2是权值最小的两个结点的序号
m = 2*n-1; //一棵有N个叶子节点的哈夫曼树共有2*N-1个结点
//动态定义长度，0号单元未使用
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
//初始化
for(p=HT+1,i=1;i<=n;++i,++p){
p->letter = str[i]; p->weight = w[i];
(*p).parent = 0; p->lchild = 0; p->rchild = 0;
}
for(;i<=m;++i,++p){
p->weight=0; p->parent=0; p->lchild=0; p->rchild=0;
}
//建立哈夫曼树
for(i=n+1;i<=m;++i){
Select(HT,i-1,s1,s2); //此函数为自己定义用于选择出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;
}
// 将哈夫曼树写入到文件hufTree.dat中
FILE *huftree;
huftree=fopen("hufTree.dat","rt");
if(huftree==NULL)
{ huftree=fopen("hufTree.dat","wt");
for(i=1;i<=m;i++) fprintf(huftree,"%d %d %d %d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);//向文件中写入
rewind(huftree);
}
}
//从叶子到根结点逆向求每个字符的赫夫曼编码
Huf setHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n,char *s){
Huf huf;
// 分配n个字符编码的头指针向量
huf.c=(char *)malloc((n+1)*sizeof(char));
//将以输入的字符存储在huf的c中
for(int j=1;j<=n;j++){
huf.c[j]=s[j];}
int start = 1; char *cd; int f,c,i;
//分配n个字符编码的头指针向量
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
//临时的编码存储，作用是分配求编码的工作空间
cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0'; //编码结束符
//按已生成的哈夫曼树，逐个求哈夫曼编码并获得各个字符的哈夫曼编码
for(i=1;i<=n;++i){
start = n - 1; //编码结束符的位置
//从叶子到根逆向求编码
for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) if(HT[f].lchild == c) cd[--start] = '0';
else cd[--start] = '1';
//为第i个字符编码分配空间
HC[i] = (char *)malloc((n - start) * sizeof(char));
//从cd复制编码（串）到HC
strcpy(HC[i], &cd[start]);
}
//将HC,HT,n分别存储到结构体Huf中
huf.HC=HC;
huf.HT=HT;
huf.len=n;
free(cd); //释放工作空间
return huf;//返回值，供后面的操作使用}
2、 编码
//利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文//件codefile.dat中,如果正文中没有要编码的字符，则键盘读入
void Encoding(Huf huf)
{
int i=0,j=0,n;
char ch[10000];
//code为指向文件CodeFile.dat的指针，tbt为指向文件//ToBeTran的指针
FILE *code,*tbt;
n=huf.len;
tbt=fopen("ToBeTran.dat","rt");
//如果ToBeTran中没有要编码的字符，则键盘读入
//如果ToBeTran中有要编码的字符，则从文件读取
if(tbt==NULL)
{
printf("不存在文件ToBeTran.dat");
printf("\n请输入要进行编码的报文: ");
gets(ch);
printf("\n");
code=fopen("CodeFile.dat","wt+");
}
else
{
fscanf(tbt,"%s",&ch);
fclose(tbt);
code=fopen("CodeFile.dat","wt+");
}
// 将ch中的元素与哈夫曼树中的进行匹配，为字符串编码
while(ch[j])
{
for(i=1;i<=n;i++)
if(ch[j]==huf.HT[i].letter)
{ //将编码写入到文件中
fprintf(code,"%s",huf.HC[i]);
break;
}
j++;
}
rewind(code);
fclose(code);
printf("已进行编码，结果保存到文件CodeFile.dat中");
}
3、 译码
//利用已建好的哈夫曼树将文件对CodeFile.dat中的代码进行译码，//结果存入文件TextFile.dat 中
void Decoding(Huf huf)
{
HuffmanTree p;
int i,n,j=0;
char d[10000];
FILE *code;//指向CodeFile.dat的指针
n=huf.len;
code=fopen("CodeFile.dat","rt");
if(code==NULL)
{
printf("没有找到CodeFile.dat文件，先编码\n");
printf("输入哈夫曼码进行译码:");
scanf("%s",&d);
}
else
{
fscanf(code,"%s",d);
fclose(code);
}
code=fopen("TextFile.dat","wt+");
while(d[j])
{
p=&huf.HT[2*n-1];
//从根开始 找叶子节点进行译码
//简而言之就是遇到0向左，遇到一向右，直到找到叶子
while(p->lchild||p->rchild)
{
if(d[j]=='0')
{
i=p->lchild;
p=&huf.HT[i];
}
else
{ i=p->rchild;
p=&huf.HT[i]; }
j++;
}
printf("%c",huf.c[i]);
//将找到叶子节点的字符写入TextFile.dat
fprintf(code,"%c",huf.c[i]); }
fclose(code);
printf("译码成功，结果保存到文件TextFile.dat中");
}
4、 打印代码文件
//将文件CodeFile每行50个代码显示到终端
//将此字符形式的编码写入CodePrin中
void Print()
{
char ch;
//code是指向CodeFile的指针，codeprin是指向
//CodePrin的指针
FILE *code,*codeprin;
code=fopen("CodeFile.dat","r");
codeprin=fopen("CodePrin.dat","w");
//每行输出50个字符，将编码写进文件CodePrin中
for(int i=1;(ch=fgetc(code))!=EOF;i++)
{
if(i>=50){
printf("\n");
fputc('\n',codeprin);
i=1;
}
putchar(ch);
fputc(ch,codeprin);
}
fclose(codeprin);
fclose(code);
printf("\n已经写入到文件CodePrin.dat中\n");
}
5、 打印哈夫曼树
//输出哈夫曼树节点，权值，双亲，左孩子，右孩子
//前n个结点打出对应的字符
void Treeprinting(Huf huf)
{
int j,n;
FILE *tree;
tree=fopen("TreePrint.dat","w");
n=huf.len;
for (j=1; j<=n; j++){
printf("\n%4d(%c)%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild, huf.HT[j].rchild);
fprintf(tree,"\n%4d(%c)%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild, huf.HT[j].rchild);
}
for (int h=n+1; h<=2*n-1; h++){
printf("\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild, huf.HT[h].rchild);
fprintf(tree,"\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild, huf.HT[h].rchild);
}
fclose(tree);
}
6、 主函数
//通过不接收不同的输入，调用相应的函数
void main()
{Huf huf;
int num;
char input;
while(1){
cout<<"I:初始化"<<endl;
cout<<"E:编码"<<endl;
cout<<"D:译码"<<endl;
cout<<"P:印代码文件"<<endl;
cout<<"T:打印哈夫曼树"<<endl;
cout<<"Q:退出"<<endl<<endl;
cout<<"请输入你的选择：";
cin>>input;
if(input=='I'||input=='i'){
num=1;
}else if(input=='E'||input=='e'){
num=2;
}else if(input=='D'||input=='d'){
num=3;
}else if(input=='P'||input=='p'){
num=4;
}else if(input=='T'||input=='t'){
num=5;
}else if(input=='Q'||'q'){
num=6;
}else{
num=7;
}
switch(num){
case 1:
huf=Initialization();
getch(); break;
case 2:
Encoding(huf);
getch(); break;
case 3:
Decoding(huf);
getch(); break;
case 4:
Print();
getch(); break;
case 5:
Treeprinting(huf);
getch(); break;
case 6:
return;
default:
printf("选择有错，请重新选择\n");
getch(); break;
}}
}
四、调试分析
1. 开始时并未设计Huf这个结构体，但后来发现进行操作的时候很费力，在编写的过程中，就将后面要用到东西都放到这个结构体中了。可以说这个结构体是在编程过中不断完善的。
2. 在调试过程中发现有一些常犯的错误，如字母的拼写、结尾的分号等，在以后的编程过程中要避免这些错误。在写报告的同时还发现一些细节上的错误，如格式化输出的地方。
3. 由于缺乏MFC的知识，只是将哈夫曼树打印出来，没有将哈夫曼树以树的形式画出来。
4. Select算法的时间复杂度为O(n), setHuffmanTree的时间复杂度为O(n*n), setHuffmanCode的时间复杂度为O(n)。
五、测试结果
本实验的测试结果截图如下：
六、用户使用说明（可选）
1 、本程序的运行环境为windows 操作系统，执行文件为111.exe
2 、运行程序时
提示输入数据 并且输入数据然后回车就可以得到输出结果哈夫曼编码
3.此程序还具有译码功能。
七、实验心得（可选）
通过编写哈夫曼编码器算法及程序的调试，清楚的掌握了二叉树这种存储结构在解决一些问题时的应用和优点，但是在对二叉树进行操作时，尤其对树的编历具体用程序实现时还是不能完全掌握。
附录（实验代码）：
#include<iostream.h>
#include<windows.h>
#include<string.h>
#define MAX 99
char cha[MAX],str[MAX];
char hc[MAX-1][MAX];
int s1,s2; //设置全局变量，以便在select(函数)中返回两个变量
typedef struct //huffman树存储结构
{unsigned int weight;//权值字符出现的频率
int lchild,rchild,parent;
}huftree;
void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点
{int i;
for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;
for (i=1;i<=k;i++)
if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;
for (i=1; i<=k ; i++)
if (tree[i].parent==0 && i!=s1) break; s2=i;
for (i=1;i<=k;i++)
if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;
}
void huffman(huftree tree[],int *w,int n) //生成huffman树
{ int m,i;
if (n<=1) return;
m=2*n-1;
for (i=1;i<=n;i++)//将各个字符的频率权值作为森林中的每一棵子树
{ tree[i].weight=w[i]; tree[i].parent=0;
tree[i].lchild=0; tree[i].rchild=0; }
for (i=n+1;i<=m;i++)
{ tree[i].weight=0; tree[i].parent=0;
tree[i].lchild=0; tree[i].rchild=0; }
for (i=n+1;i<=m;i++)
{select(tree, i-1);
tree[s1].parent=i;
tree[s2].parent=i;
tree[i].lchild=s1;
tree[i].rchild=s2;
tree[i].weight =tree[s1]. weight+ tree[s2].weight;}
}
void huffmancode(huftree tree[],char code[],int n)//标记哈夫曼编码
{
int start,c,i,f;
code[n-1]='\0';
cout<<"各字符的哈夫曼编码为:"<<endl;
for(i=1;i<=n;i++)
{start=n-1;
for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)
{if(tree[f].lchild==c)code[--start]='0';
else code[--start]='1';}
strcpy(hc[i],&code[start]);
cout<<cha[i]<<"的哈夫曼编码为："<<hc[i]<<" "<<endl;
}
}
void tohuffmancode(int n)//将您从键盘上输入的字符转变为对应的哈夫曼编码
{int i=0,j;
cout<<endl<<"输入的字符串转化为哈夫曼编码为:"<<endl;
for (;str[i]!='\0';i++)
{j=0;
for(;str[i]!=cha[j]&&j<=n;) j++;
if (j<=n) cout<<hc[j];}
cout<<endl;
}
void decode(char ch[],huftree tree[],int n)//根据输入的01代码按所得的哈夫曼编码箅到对应的字符
{
int i,j,m;char b;
m=2*n-1;
i=m;
cout<<"请输入二进值数:"<<endl;
cin>>b;
cout<<"解码后的字符串为: "<<endl;
while(b!='\n') //遇到回车时，结束
{ if(b=='0')i=tree[i].lchild;//按输入的二进制码填入对应的哈夫曼树中，从而得到对应的编码
else if(b=='1') i=tree[i].rchild;
else if(b=='e') return;
else
{cout<<"输入的值非法，请重新输入："<<endl;goto L;}
if(tree[i].lchild==0)
{cout<<ch[i]<<" ";
j=i,i=m;
}
L:cin>>b;
}
if(tree[j].lchild!=0)
cout<<endl<<"ERROR"<<endl;
cout<<endl<<endl;
}
void main()
{ system("color ec");
int i=0,j=1,n;
int *w,weight[MAX],st[199]={0};
char code[MAX];
huftree tree[MAX];
w=weight;
cout<<"请输入一段字符串,按回车键结束"<<endl;
cin>>str;
system("pause");
for(;str[i]!='\0';i++) st[str[i]]++;
for(i=0;i<=199;i++) if (st[i]!=0) { cha[j]=i,weight[j]=st[i];j++;}
i=1;
for (n=j-2;i<j-1;i++)
cout<<cha[i]<<" 的权值为："<<weight[i]<<endl;
cout<<endl;
huffman(tree,w,n); //生成huffman树函数，w是存入各字符权值的数组首地址，n是输入字符的种类个数
huffmancode(tree,code,n); //标记哈夫曼编码函数
tohuffmancode(n); //将您从键盘上输入的字符转变为对应的哈夫曼编码函数
decode(cha,tree,n); //根据输入的01代码按所得的哈夫曼编码箅到对应的字符
}