华北水利水电大学 数据结构 实验报告 2 0 1 3 ～2 0 1 4 学年 第 一 学期 级 计算机科学与技术专业 班级： 学号： 姓名： 实验三：哈夫曼编/译码器 一． 实验目的 掌握哈夫曼树编码原理 二．实验内容 根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码
基本要求： （1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树
对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码
（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）
（3）计算压缩比（选作） （4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串
（选作） 测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码
字符集D={
},出现频率为w={
} 三． 程序源代码 #include #include #include ///
数据结构的构造
typedef struct HTNode { int weight; int parent; int lchild; int rchild; HTNode(int w,int p,int l,int r) { weight=w; parent=p; lchild=l; rchild=r; } }HTNode,*HuffmanTree; typedef char ** HuffmanCode; typedef struct ///译码参照表 { char word; char* code; }LNode,*List; ///
选取最小和次小的
