第 1 页 共 8 页 华北水利水电学院 数据结构 实验报告 2 0 1 2 ～2 0 1 3 学年 第 一 学期 2 0 1 0 级 计算机科学与技术 专业 班级： 2010134 学号： 201013432 姓名： 蔡启林 实验三 树的应用 一、 实验题目： 树的应用——哈夫曼编码 二、 实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求： 1． 输出存放哈夫曼树的数组 HT的初态和终态； 2． 输出每个字符的哈夫曼编码； 3． 输入由上述若干字符组成的字符串，对电文进行编码并输出； 4． （选作）输入电文的哈夫曼编码，进行译码并输出。 三、程序源代码： #include #include #include #include #define MAXLEAF 100 struct HTNode { char letter; int parent; int lchild; int rchild; int weight; }; struct ChNode { char letter; int weight; }; struct HCode { char code[MAXLEAF]; int m_start; }; //创建哈夫曼树 第 2 页 共 8 页 void CreateHT(HTNode ht[],int n,ChNode s[]) { int i,k,s1,s2; int m1,m2; for (i=0;i<2*n-1;i++) { ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; ht[i].weight=0; } for (i=0;i
