数据结构实验报告
班级： 姓名： 学号：
实验三
一．实验内容：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。
一个完整的系统应具有以下功能： （1） I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符
和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2） E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件
hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 （3） D：译码（Decoding）。利用已经建好的哈夫曼树将文件CodeFile中的代
码进行译码，结果存入文件TextFile中。 （4） P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，
每行50个代码，同时将此字符形式的编码写入文件CodePrint中。 T：打印哈夫曼树（Tree printing）。将已经在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
二．实验目的
（1） 掌握二叉树的存储结构及其相关操作。
（2） 掌握构造哈夫曼树的基本思想，及其编码/译码过程。
三．程序清单 #include
//定义赫夫曼树结点的结构体 typedef struct{
char ch; //增加一个域，存放该节点的字符 int weight;
int parent,lchild,rchild; }HTNode,*HuffmanTree;
typedef char **HuffmanCode; //指向赫夫曼编码的指针
void tips(); //打印操作选择界面
void HuffmanCoding(HuffmanTree &,char *,int *,int); //建立赫夫曼树的算法
void select(HuffmanTree HT,int j,int *x,int *y); //从已建好的赫夫曼树中选择parent为0，weight最小的两个结点 void Init();
void Coding(); //编码
void Decoding(); //译码
void Print_code(); //打印译码好的代码 void Print_tree(); //打印哈夫曼树
int Read_tree(HuffmanTree &); //从文件中读入赫夫曼树
void find(HuffmanTree &HT,char *code,char *text,int i,int m); //译码时根据01字符串寻找相应叶子节点的递归算法
void Convert_tree(unsigned char T[100][100],int s,int *i,int j); //将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树
HuffmanTree HT; //全局变量
int n=0; //全局变量，存放赫夫曼树叶子结点的数目
int main() {
printf(\班级：中法121 姓名：郝雨微 学号：122887\\n\
char select;
while(1) {
tips();
scanf(\
switch(select) //选择操作，根据不同的序号选择不同的操作 {
case 'I':Init(); break;
case 'E':Coding(); break;
case 'D':Decoding(); break;
case 'P':Print_code(); break;
case 'T':Print_tree(); break;
case 'Q':exit(1);
default :printf(\ }