数 据 结 构 实验报告
实验题目：哈夫曼编/译码系统的设计与实现（该实验为设计性实验，共用6个学时）
实验要求：
1． 问题描述：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。
2． 一个完整的系统应具有以下功能：
1）初始化（Initialzation）。从数据文件DataFile.dat中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
2）编码（EnCoding）。用已建好的哈夫曼树,对文件ToBeTran.dat中的文本进行编码形成报文，将报文写在文件Code.txt中；
3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.dat中的代码进行译码形成原文，结果存入文件Textfile.txt中；
4）输出（Output）:输出ToBeTran.dat及其报文Code.txt；输出CodeFile.dat及其原文Textfile.txt；
[备注]：
1）数据文件DataFile.dat中，元素类型为（字符，权值） , DataFile.dat的建立可以根据用户输入的一段原文，通过统计出现的字符及各字符出现的次数（与出现的概率作用相同）而得到。另：为了使输出的哈夫曼树不太大，规定报文中只能出现A-H的8个字符，当然对程序稍加修改就可以对出现的所有可输和字符进行处理。
2）ToBeTran.dat中的内容由用户在程序执行时从键盘随机输入得到；
3）CodeFile.dat中的内容由用户在程序执行时从键盘随机输入得到；
DataFile.dat、ToBeTran.dat、CodeFile.dat在程序运行时建立是为了保证编/译码系统的通用性；
三．总的设计思想，及环境语言、工具等
总的设计思想：
1．根据实验要求，先创建文件DataFile.dat、ToBeTran.dat和CodeFile.dat；用下面三个函数实现；
void creatDataFile( )； //创建数据文件
void creatToBeTran( )；//创建原文文件
void creatCodeFile( )；//创建报文文件
2.从文件DataFile.dat中读出各字符及相应的权值，创建哈夫曼树HT；
3.根据构造的哈夫曼树，求相应字符的哈夫曼编码；
4．从文件ToBeTran.dat中读出要翻译的原文，将其翻译成译文存入文件Code.txt中
5．从文件CodeFile.dat中读出要翻译的报文，将其翻译成原文存入文件Textfile.txt中
环境语言：Windows下的Microsoft VC++
四、数据结构与模块说明
下面是编译码系统中所用的数据结构。
在这个系统中，哈夫曼树的存储结构采用顺序存储；其结点结构为：
程序中用到的头文件、类型定义及主要的函数原型如下：
#include"stdio.h"
#include"malloc.h"
#include"string.h"
#define char_num 8
typedef struct{ char ch ; int w;} DFileNode ;// 定义数据文件的元素类型
typedef struct //赫夫曼树和赫夫曼编码的存储表示
{
char ch; //相应字符
int weight;//字符的权值
int parent,lchild,rchild;//双亲、左、右孩子指针（下标）
char *next; // 指向该字符的编码的指针
}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
HuffmanTree HT;
void creatDataFile( )//创建数据文件
void creatToBeTran( )//创建原文文件
void creatCodeFile( )//创建报文文件
int min(HuffmanTree t,int i)；// 求无双亲且权值最小的结点，函数void select()调用
void select(HuffmanTree t,int i,int &s1,int &s2)；
// s1为最小的两个值中序号小的那个
void print_huff_tree(HuffmanTree HT ,int n)；
//输出哈夫曼树，在必要时调用以验证算法的正确性
void creatHuffmanTree( HuffmanTree &HT, int n)；
//创建含n叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中即初始化
void HuffmanCoding(HuffmanTree &HT,int n)；
//对有n个叶子结点的哈夫曼树上的叶子结点进行编码
void EnCoding()//编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中
void Decoding( )；//译码:对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt中void output( )；//输出原文和对应的译文；输出报文和对应的原文；
五、主要算法的设计与实现
void creatHuffmanTree( HuffmanTree &HT, int n)
{//创建含n叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中即初始化Initialzation
FILE *f1;
int m,i,s1,s2;
HuffmanTree p;
DFileNode s; //从文件中读数据时用；
m=2*n-1;
f1=fopen("DataFile.dat","rb");
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
printf("字符及相应的权值为：");
for(p=HT+1,i=1;i<=n;++i,++p)
{
fread(&s,1,sizeof(DFileNode),f1); //从文件中读一个数给s,构造叶子
printf("(%c,%d)",s.ch,s.w);
(*p).ch=s.ch;
(*p).weight=s.w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
(*p).next=NULL;
}
fclose(f1);
printf("\n");
for(;i<=m;++i,++p)
{ (*p).ch=' ';(*p).parent=0;(*p).lchild=0;(*p).rchild=0;(*p).next=NULL;}
for(i=n+1;i<=m;++i)//建n-1个分支结点
{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void HuffmanCoding(HuffmanTree &HT,int n)
//对有n个叶子结点的哈夫曼树上的叶子结点进行编码
{
char *cd;
int i,start,c,f;
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';
HT[i].next=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HT[i].next,&cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
void EnCoding()//编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中
{
FILE *f1, *f2;
char c;
int s,i;
f1=fopen("ToBeTran.dat","r");//打开文件ToBeTran.dat为了读
f2=fopen("Code.txt","w");//打开文件Code.txt为了写
// printf("原文：");
while(fread(&c,1,sizeof(char),f1))
{ i=1;
while(HT[i].ch!=c) i++;
//printf("%c",c);
fputs(HT[i].next,f2);
}
//printf("\n");
fclose(f1);
fclose(f2);
//f2=fopen("Code.txt","r");
//printf("译文：");
//while(fread(&c,1,sizeof(char),f2)) putchar(c);
//printf("\n");
fclose(f2);
}
void Decoding( )//译码:对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt中
{
FILE *f1, *f2;
char c;
int s,i,p;
f1=fopen("CodeFile.dat","rb");
f2=fopen("Textfile.txt","w");
//printf("报文：");
p=2*char_num-1; //P指向哈夫曼树的根
while(fread(&s,1,sizeof(int),f1))
{
// printf("%d",s);
if(s==0) p=HT[p].lchild; else p=HT[p].rchild;
if(HT[p].lchild==0)
{ c=HT[p].ch; fputc(c,f2); p=2*char_num-1; //让P重新指向哈夫曼树的根
}
}
printf("\n");
fclose(f1);
fclose(f2);
//f2=fopen("Textfile.txt","r");
//printf("原文：");
//while(fread(&c,1,sizeof(char),f2)) putchar(c);
//printf("\n");
//fclose(f2);
}
六、源程序
见电子稿(文件名为: .cpp ); //文件名由自己取
七、运行结果与运行情况
第一次运行：
创建数据文件DataFile.dat
请输入一段仅包含大写字母A--H的一段文字以#结束
ABCHHDHFGEHDBCHDGFA#
字符及每个字符出现的次数(字符，出现次数)
(A ,2) , (B ,2) , (C ,2) , (D ,3) , (E ,1) , (F ,2) , (G ,2) , (H ,5)
初始的哈夫曼树:
字符 权 值 双 亲 左孩子 右孩子 指向编码的指针
A 2 9 0 0 ->(null)
B 2 10 0 0 ->(null)
C 2 10 0 0 ->(null)
D 3 12 0 0 ->(null)
E 1 9 0 0 ->(null)
F 2 11 0 0 ->(null)
G 2 11 0 0 ->(null)
H 5 14 0 0 ->(null)
3 12 1 5 ->(null)
4 13 2 3 ->(null)
4 13 6 7 ->(null)
6 14 4 9 ->(null)
8 15 10 11 ->(null)
11 15 8 12 ->(null)
19 0 13 14 ->(null)
编码后的哈夫曼树:
字符 权 值 双 亲 左孩子 右孩子 指向编码的指针
A 2 9 0 0 ->1110
B 2 10 0 0 ->000
C 2 10 0 0 ->001
D 3 12 0 0 ->110
E 1 9 0 0 ->1111
F 2 11 0 0 ->010
G 2 11 0 0 ->011
H 5 14 0 0 ->10
3 12 1 5 ->(null)
4 13 2 3 ->(null)
4 13 6 7 ->(null)
6 14 4 9 ->(null)
8 15 10 11 ->(null)
11 15 8 12 ->(null)
19 0 13 14 ->(null)
字符A的编码为:1110 字符B的编码为:000 字符C的编码为:001
字符D的编码为:110 字符E的编码为:1111 字符F的编码为:010
字符G的编码为:011 字符H的编码为:10
创建原文文件,请输入一段仅包含大写字母A--H的一段文字作为原文以#结束
ABCGDBCHFE#
原文：ABCGDBCHFE
译文：1110000001011110000001100101111
创建报文文件,请输入一段仅包含0和1的一段文字作为原文以2作为结束标志.
输入报文中的第一个代码0或1（为整数类型)
0 0 0 0 1 1 1 0 0 1 0 1 0 2
0 0 0 0 1 1 1 0 0 1 0 1 0
报文:0000111001010
原文:BGHFH
第二次运行
创建数据文件DataFile.dat
请输入一段仅包含大写字母A--H的一段文字以#结束
AABABABABABAEGHF#
字符及每个字符出现的次数(字符，出现次数)
(A ,7) , (B ,5) , (C ,0) , (D ,0) , (E ,1) , (F ,1) , (G ,1) , (H ,1) ,
初始的哈夫曼树:
字符 权 值 双 亲 左孩子 右孩子 指向编码的指针
A 7 15 0 0 ->(null)
B 5 14 0 0 ->(null)
C 0 9 0 0 ->(null)
D 0 9 0 0 ->(null)
E 1 10 0 0 ->(null)
F 1 11 0 0 ->(null)
G 1 11 0 0 ->(null)
H 1 12 0 0 ->(null)
0 10 3 4 ->(null)
1 12 5 9 ->(null)
2 13 6 7 ->(null)
2 13 8 10 ->(null)
4 14 11 12 ->(null)
9 15 2 13 ->(null)
16 0 1 14 ->(null)
编码后的哈夫曼树:
字符 权 值 双 亲 左孩子 右孩子 指向编码的指针
A 7 15 0 0 ->0
B 5 14 0 0 ->10
C 0 9 0 0 ->111110
D 0 9 0 0 ->111111
E 1 10 0 0 ->11110
F 1 11 0 0 ->1100
G 1 11 0 0 ->1101
H 1 12 0 0 ->1110
0 10 3 4 ->(null)
1 12 5 9 ->(null)
2 13 6 7 ->(null)
2 13 8 10 ->(null)
4 14 11 12 ->(null)
9 15 2 13 ->(null)
16 0 1 14 ->(null)
字符A的编码为:0 字符B的编码为:10 字符C的编码为:111110
字符D的编码为:111111 字符E的编码为:11110 字符F的编码为:1100
字符G的编码为:1101 字符H的编码为:1110
创建原文文件,请输入一段仅包含大写字母A--H的一段文字作为原文以#结束
ABCBDGFBCGD#
原文：ABCBDGFBCGD
译文：0101111101011111111011100101111101101111111
创建报文文件,请输入一段仅包含0和1的一段文字作为原文以2作为结束标志.
输入报文中的第一个代码0或1（为整数类型)
0 0 0 1 0 1 0 1 0 1 0 0 0 2
0 0 0 1 0 1 0 1 0 1 0 0 0
报文:0001010101000
原文:AAABBBBAA
Press any key to continue
八、自我评析与总结
该实验做得比较成功，例如在编写调试程序时，并不是仅仅把目标局限在编译通过，执行有结果上。除了为了完成任务的模块外，另有测试输出哈夫曼树的代码print_huff_tree( )，输出文件内容的代码；在适当的地方调用它们，运行时可以看到验证编写程序的正确性；当运行通过并符合题中要求后将这一部分代码变成注释或删除。
通过本次实验，提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输出的重要性。编写大一点的程序，应先写出算法，再写程序，调试时一段一段调试；对于没有实现的操作用空操作代替，这样容易找出错误所在。最忌讳将所有代码写完后再调试，这样若程序有错误，太难找 。
需要特别强调的是：编写程序、调试程序不要仅局限于编译通过上，关键要出正确的结果，在必要的时候添加提示输出信息，是一种不错的选择。
该程序具有通用性，对于不同的输入都可进行处理。
若想对同一个编码方案进行编译码，只需在第一次运行时创建数据文件，当数据文件创建好后，仅需将源程序的主函数中调用创建数据文件函数creatDataFile( )的那个语句变为注释既可。
九、参考文献
1．蒋盛益 等编著 《数据结构学习指导与训练》 中国水利水电出版社
2．严蔚敏 吴伟民编著 《数据结构》 （Ｃ语言版） 清华大学出版社
3．严蔚敏 等编著 《数据结构习题集》（Ｃ语言版） 清华大学出版社
十、教师评语：