数据结构 哈夫曼树的实验报告

软件学院设计性实验报告

专业：网络工程 年级/班级： 2013—2014学年第一学期 课程名称 数据结构 指导教师 本组成员 学号姓名 实验地点 实验时间 哈夫曼编/译码系统的设计与实现 实验类型 设计性 项目名称 一、实验目的 理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。

二、实验仪器或设备

学院提供公共机房，1台/学生微型计算机。

三、总体设计（设计原理、设计方案及流程等）

1． 问题描述：

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。 2．一个完整的系统应具有以下功能：

1）初始化（Initialzation）。从数据文件DataFile.dat中读入字符及每个字符的权值，建立哈夫曼树HuffTree；

2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.dat中的文本进行编码形成报文，将报文写在文件Code.txt中；

3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.dat中的代码进行解码形成原文，结果存入文件Textfile.txt中；

4）输出（Output）: 输出DataFile.dat中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.dat及其报文Code.txt；输出CodeFile.dat及其原文Textfile.txt；

要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.dat、ToBeTran.dat和CodeFile.dat三个文件，以保证系统的通用性。

四、实验步骤（包括主要步骤、代码分析等）

1）编写C语言程序 #include #include #include #include #include

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

河南师范大学软件学院

#define INFEASIBLE -1

typedef struct {

char data; int weight;

int parent,lchild,rchild; }HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *d,int *w,int n) //构造哈弗曼函数HT，构造编码HC

{

void select(HuffmanTree HT,int n,int &s1,int &s2); int m,c,f,j; HuffmanTree p; int i,s1,s2,start; char *cd;

m=2*n-1; //m为结点数，n为叶子数

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); p=HT; p++;

for(i=1;i<=n;i++,p++) //将叶子的值输入HT中 {

p->data=d[i]; //={*d,*w,0,0,0}; p->weight=w[i]; p->parent=0; p->lchild=0; p->rchild=0; }

for (i=n+1;i<=m;i++,p++) //={'#',0,0,0,0} {

p->data='#'; p->weight=0; p->parent=0; p->lchild=0; p->rchild=0;

} s1=1; s2=2;

for(i=n+1;i<=m;i++) //构建哈夫曼树 {

河南师范大学软件学院

select(HT,i-1,s1,s2); HT[i].lchild=s1; HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight; HT[s1].parent=i; HT[s2].parent=i; }

HC=(HuffmanCode)malloc((n+1)*sizeof(HuffmanTree)); //开辟空间，编码

cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\\0';

for (i=1;i<=n;++i)

{

start=n-1;

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) {

if(HT[f].lchild==c) cd[--start]='0'; else

cd[--start]='1'; }

HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]);

printf(\"%c的编码是：\ puts(HC[i]); }

free(cd); }

void select(HuffmanTree HT,int n,int &s1,int &s2) //小两数

{

int i,t; s1=1; s2=2;

while(HT[s1].parent!=0) s1++;

while((HT[s2].parent!=0)||(s1==s2)) s2++;

/*for(i=1;i<=n;i++)

河南师范大学软件学院

求最

{

if(HT[s1].weight>HT[i].weight&&HT[i].parent==0&&s2!=i) s1=i; }

if(HT[s1].weight>HT[s2].weight) {

t=s1; s1=s2; s2=t; }

for(i=1;i<=n;i++) {

if(s1!=i) {

if(HT[s2].weight>HT[i].weight&&HT[i].parent==0) s2=i; } }*/

for(i=1;i<=n;i++)

{

if(s1!=i&&i!=s2) {

if(HT[i].weightif(HT[s1].weightif(HT[i].weight} } }

void translation(HuffmanTree HT,int num)

{

char str[20]; int i,t=num;

printf(\"请输入由0或1组成的编码：\"); cin>>str;

河南师范大学软件学院

//t=HT; //t为树的指向各节点的指针 for(i=0;i<(strlen(str));i++) {

if(str[i]=='0') t=HT[t].lchild; else

if(str[i]=='1') t=HT[t].rchild; else {

printf(\"编码输入错误\"); break; }

if(!(HT[t].lchild&&HT[t].rchild)) {

printf(\"%c\ t=num; } }

printf(\"\\n\"); }

void main() {

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char d[],int w[],int n);

void translation(HuffmanTree HT,int num); HuffmanTree HT=NULL; HuffmanCode HC=NULL; char data,n,*p,*d; int *w,wei,i,num;

printf(\"please intput character number:\");

scanf(\"%d\

d=(char*)malloc((n+1)*sizeof(char)); w=(int *)malloc((n+1)*sizeof(int)); printf(\"请输入Huffman树中的字符：\\n\");

for(i=1;i<=n;i++) {

cin>>data; d[i]=data; }

printf(\"请输入%d次位权\\n:\

河南师范大学软件学院

for (i=1;i<=n;i++) {

cin>>wei; w[i]=wei; }

num=2*n-1;

HuffmanCoding(HT,HC,d,w,n); translation(HT,num); }

2）程序分析

此实验是构造哈夫曼树，求出哈夫曼编码然后输出

构造哈夫曼树的算法操作时选出两棵根节点的权值最小的一颗树的左右子树，且置新树的根节点的权值为其左右子树上根节点的权值之和，根据哈夫曼树求出带权路径的算法操作是用递归调用的方法。

在此实验的操作过程中要注意构造哈夫曼树的方法，因为在此操作的过程中用的的指针变量特别多，容易混淆。 3）运行结果举例

五、结果分析与总结

1)在做这个实验时前期要做很多准备，因为这个实验操作很复杂，虽然老师已经讲过了大致构思和算法思想，课本上也有相关算法及其伪代码，但翻译成C语言的过程要注意语法等原因，所以要查找一些资料。 2）对于不懂得地方要像其他同学虚心请教。

3）哈夫曼编码很考验编程者的细心程度，而且涉及的问题也很复杂，培养

河南师范大学软件学院

了我们的细心和耐心。

教师签名：

年 月 日

河南师范大学软件学院