1、哈夫曼编码与译码 数据结构实验实验报告May 212015姓名：陈斌 学号：E11314079 专业：13计算机科学与技术数据结构 第四次实验学号 E* 专业 计算机科学与技术 姓名 陈 斌 实验日期 2015.05.21 教师签字 成绩 实 验 报 告【实验名称】 哈夫曼编/译码 【实验目的】 掌握哈弗曼编/译码算法。1.掌握Huffman 树的概念、特点和存储结构；2.掌握Huffman 树的构造方法；3.学会灵活运用Huffman 树解决编码问题。【实验内容】1.必做内容哈夫曼编码【问题描述】某报文中共出现n个字符，各字符出现频度依次为w1,w2,wn。要求设计一个不等长的编码方案，输出
2、每个字符对应的编码，使得该编码系统的空间效率最好。要求字符个数和相应的权值要从终端输入。 源代码：head.h: #include#include#include /malloc( )#include / INT ,MAX#include /EOF,NULL#include /atoi( )#include /eof( )#include /floor( ),ceil( ),abs( )#include /exit( )#include /cout,cin/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#defi
3、ne INFEASIBLE -1/OVERFLOW 在 math.h 中已定义为3typedef int Status;typedef int Boolean; / 布尔类型main.cpp:#include head.htypedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */* 求赫夫曼编码。实现算法6.12的程序 */int min1(H
4、uffmanTree &t,int i) /* 函数void select()调用 */ int j,flag; unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */ for(j=1;j=i;j+) if(tj.weightts2.weight) j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) /* 算法6.12 */ /* w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */ int m,i,s1,s2,star
5、t; unsigned c,f; HuffmanTree p; char *cd; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0号单元未用 */ for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iweight=0; p-parent=0; p-lchild=0; p-rchild=0; for(i=n+1;i=m;+i) /* 建赫夫曼树 */ /* 在HT1i-1中选择parent为0且weight最小的
6、两个结点,其序号分别为s1和s2 */ Select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /* 从叶子到根逆向求每个字符的赫夫曼编码 */ HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n个字符编码的头指针向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求编码的工作空间 */ cdn-1=0; /* 编码结束符 */
7、for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码 */ start=n-1; /* 编码结束符位置 */ for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /* 从叶子到根逆向求编码 */ if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); /* 为第i个字符编码分配空间 */ strcpy(HCi,&cdstart); /* 从cd复制编码(串)到HC */ free(cd); /* 释放工作空间 */void main()
8、 int n; HuffmanTree HT; HuffmanCode HC; do cout1):n=; cinn; while(n=1); int *w=(int*)malloc(n*sizeof(int); cout请依次输入n个权值(整型):endl; for(int i=0;i*(w+i); HuffmanCoding(HT,HC,w,n); cout赫夫曼编码为:endl; for(i=1;i=n;i+) cout*(w+i-1)t: HCiendl;运行结果：赫夫曼树的形状为： 2.选做内容哈夫曼译码【问题描述】在前面必做内容的基础上，实现哈弗曼译码算法，对给定的一组编码（要求从
9、终端输入），译出其对应的报文部分。源代码：head.h: #include#include#include /malloc( )#include / INT ,MAX#include /EOF,NULL#include /atoi( )#include /eof( )#include /floor( ),ceil( ),abs( )#include /exit( )#include /cout,cin/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/OVERFLOW 在
10、math.h 中已定义为3typedef int Status;typedef int Boolean; / 布尔类型main.cpp:#include head.h#define maxsize 100 /哈夫曼编码的最大位数typedef struct char ch; unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */* 求赫夫曼编码。实现算法6.12的程序
11、*/int min1(HuffmanTree &t,int i) /* 函数void select()调用 */ int j,flag; unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */ for(j=1;j=i;j+) if(tj.weightts2.weight) j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *ch,int *w,int n) /* 算法6.12修改 */ /* w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码H
12、C */ int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0号单元未用 */ for(p=HT+1,i=1;ich=*ch; p-weight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;ich=0; p-weight=0; p-parent=0; p-lchild=0; p-rchild=0; for(i=n+1;i=m;+i) /*
13、 建赫夫曼树 */ /* 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */ Select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; /* 从叶子到根逆向求每个字符的赫夫曼编码 */ HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n个字符编码的头指针向量(0不用) */ cd=(char*)malloc(n*sizeof(char
14、); /* 分配求编码的工作空间 */ cdn-1=0; /* 编码结束符 */ for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码 */ start=n-1; /* 编码结束符位置 */ for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /* 从叶子到根逆向求编码 */ if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); /* 为第i个字符编码分配空间 */ strcpy(HCi,&cdstart); /* 从cd复制编码(串
15、)到HC */ free(cd); /* 释放工作空间 */void HuffmanDecoding(HuffmanTree &HT,int n)/依次读入电文，根据哈夫曼树译码 int i,j=0,k=0,flag=0; char cmaxsize=0; char bmaxsize; char endflag=2; /电文结束标志取2 i=2*n-1; /从根结点开始往下搜索 printf(请输入译码(以2为结束标志):); gets(b); while(bj!=2) if(bj=0) i=HTi.lchild; /走向左孩子 else if(bj=1) i=HTi.rchild; /走向右
16、孩子 else cout输入译码有错.endl; flag=1; break; if(HTi.lchild=0) /HTk是叶结点 ck+=HTi.ch; ck=0; i=2*n-1; j+; if(HTi.lchild!=0 & i!=2*n-1 & bj=2) /译码读完，但尚未到叶子结点 cout输入译码有错.endl; else if(flag=0) printf(译码对应的报文为:); puts(c); void main() int n; HuffmanTree HT; HuffmanCode HC; do cout1):n=; cinn; while(n=1); int *w=(
17、int*)malloc(n*sizeof(int); char *c=(char *)malloc(n*sizeof(char); cout请依次输入n个字符及相应的权值(中间用空格隔开):endl; for(int i=0;i=n-1;i+) printf(输入第%d个字符和权值:,i+1); scanf(%c %d,c+i,w+i); getchar(); HuffmanCoding(HT,HC,c,w,n); cout赫夫曼编码为:endl; for(i=1;i=n;i+) cout*(c+i-1)t: HCiendl; coutendl; HuffmanDecoding(HT,n);/
18、依次读入电文，根据哈夫曼树译码运行结果：下面为译码输入错误的情况：【小结或讨论】通过本次实验，掌握了Huffman 树的概念、特点和存储结构；并且掌握了Huffman 树的构造方法；还学会了运用Huffman 树解决编码问题。能够用Huffman树实现编码和译码的功能。必做内容里，用每个字符对应的权值代替了该字符，因为在定义Huffman树的存储结构时，没有添加存储字符的数据域。这一点在选作内容里做了修改，可以在创建Huffman树的时候将权值连同字符一起输入。在译码过程中，可能面对输入的译码有错的情况，这时候要添加程序段判断是何种出错类型，并作出相应处理操作。比如有可能只输入了某个字符编码的前几位，这时候不能从Huffman树根结点访问到叶子结点，输入有错。还有一种情况，就是输入的译码前面的部分是正确的，但是后面出错了，这时候整个译码是错误的，不用将前面正确的报文输出，所以程序中定义了一个char型数组用来存放翻译过的译文，如果译文结束了都没有出错，就将该数组里面的内容输出，否则不输出。这里，在向char型数组里存放报文的时候，每存入一个就将该报文的下一个存储位置置为0，以保证最后输出的全是译码对应的报文。程序中是以字符2作为结束标记的，也可以以其他字符作为结束标记。
