华北水利水电大学 数据结构 实验报告 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; ///.......选取最小和次小的...... void Select(HuffmanTree & HT,int num,int *s1,int *s2) { int i; for(i=1;i<=num;i++) { if(HT[i].parent==0) { *s1=i; break; } } for(i=1;i<=num;i++) { if(HT[i].parent==0) { if(HT[*s1].weight>HT[i].weight) *s1=i; } } for(i=1;i<=num;i++) { if(i==*s1) continue; if(HT[i].parent==0) { *s2=i; break; } } for(i=1;i<=num;i++) { if(HT[i].parent==0) { if(i==*s1) continue; if(HT[*s2].weight>=HT[i].weight) *s2=i; } } } ///..........哈夫曼树构造函数.......... void HuffmanTreeCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, int n) { int i,c,m,start; int f,s1,s2; char *cd; HuffmanTree p; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc(...
