哈夫曼编码及译码 数据结构实验

1、实验报告五月 212015姓名：陈斌 学号：E11314079 专业：13计算机科学与技术数据结构 第四次实验学号 E11314079 专业 计算机科学与技术 姓名 陈 斌 实验日期 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#define INF

3、EASIBLE -1/OVERFLOW 在 math.h 中已定义为3typedef int Status;typedef int Boolean; / 布尔类型main.cpp:#include head.htypedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */* 求赫夫曼编码。实现算法6.12的程序 */int min1(HuffmanTr

4、ee &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,start;unsigned c,f

5、;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最小的两个结点,其序号分别为s1和s2 */ Select(HT,

6、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; /* 编码结束符 */for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码 */ sta

7、rt=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()int n;HuffmanTree HT;HuffmanCode HC;d

8、ocout1):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;运行结果：赫夫曼树的形状为： 101010101029231110014187532. 选做内容哈夫曼译码【问题描述】在前面必做内容的基础上，实现哈弗曼译码算法，对给定的一组编码（要求从终端输入），译出其对应的报文部分。源代码：hea

9、d.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 在 math.h 中已定义为3typedef int

10、 Status;typedef int Boolean; / 布尔类型main.cpp:#include head.h#define maxsize 100/哈夫曼编码的最大位数typedef structchar ch;unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */* 求赫夫曼编码。实现算法6.12的程序 */int min1(HuffmanTree &t,in

11、t 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个字符的赫夫曼编码HC */int m,i,s1,s2,start;unsigned

12、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) /* 建赫夫曼树 */ /* 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为

13、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; /* 编码结束符 */for(i=1;i=n;i+) /

14、* 逐个字符求赫夫曼编码 */ 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 HuffmanDecoding(HuffmanT

15、ree &HT,int n)/依次读入电文，根据哈夫曼树译码int i,j=0,k=0,flag=0;char cmaxsize=0;char bmaxsize;char endflag=2; /电文结束标志取2i=2*n-1; /从根结点开始往下搜索printf(请输入译码(以2为结束标志):);gets(b);while(bj!=2)if(bj=0)i=HTi.lchild; /走向左孩子else if(bj=1)i=HTi.rchild; /走向右孩子else cout输入译码有错.endl;flag=1;break;if(HTi.lchild=0) /HTk是叶结点ck+=HTi.ch

16、;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;docout1):n=;cinn;while(n=1);int *w=(int*)malloc(n*sizeof(int);char *c=(char *)malloc(n*sizeof(char);cout请依次输入n个字符及相应的权值(中间用空格隔开):

17、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);/依次读入电文，根据哈夫曼树译码运行结果：下面为译码输入错误的情况：【小结或讨论】通过本次实验，掌握了Huffman 树的概念、特点和存储结构；并且掌握了Huffman 树的构造方法；还学会了运用Huffman 树解决编码问题。能够用Huffman树实现编码和译码的功能。必做内容里，用每个字符对应的权值代替了该字符，因为在定义Huffman树的存储结构时，没有添加存储字符的数据域。这一点在选作内容里做了修改，可以在创建Huffman树的时候将权值连同字符一起输入。在译码过程中，可能面对输入的译码有错的情况，这时候要添加程序段判断是