哈夫曼树实验报告.doc

闽江学院电子系
实验报告
学生姓名:
班级:
学号:
课程:算法与数据结构
实验题目:哈弗曼编/译码系统的设计与实现
实验地点:实验楼A210
三、实验目的:理解哈弗曼树的特征及其应用;在对哈夫曼树进行理解的基础上,构造哈夫曼树,并用构造的哈夫曼树进行编码和译码。
四、实验内容:
构建哈夫曼树,并用构造的哈夫曼树进行编码和译码。
五、实验环境(使用的软硬件):
Visual C++
六、实验步骤及操作:
++;
(Win32 Console Application),输入工程名称(HuffermanTree),点击“确定”,选择“An Empty Project”,点击完成。
++ Header File,输入文件名“huffermanpubuse”,点击“确定”,在显示的代码编辑区中输入如下程序:
#include<>
#include<>
#include<> /* malloc()等*/
#include<> /* INT_MAX 等*/
#include<> /* EOF(=^Z 或F6),NULL */
#include<> /* atoi() */
#include<> /* eof() */
#include<> /* floor(),ceil(),abs() */
#include<> /* exit() */
/* 函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math. h 中已定义OVERFLOW 的值为3,故去掉此行*/
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码,如OK 等*/
typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */
新建文件C/C++ Header File,输入文件名“huffermandef”,点击“确定”,在显示的代码编辑区中输入如下程序:
typedef struct
{char ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树*/
typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表*/
++ Header File,输入文件名“huffermandef”,点击“确定”,在显示的代码编辑区中输入如下程序:
int min1(HuffmanTree t,int i)
{ /* 函数void select()调用*/
int j,flag;
unsigned int k=UINT_MAX; /* 取k 为不小于可能的值*/
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}
void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1 为最小的两个值中序号小的那个*/
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,char *ch,int n) /* */
{ /* w 存放n 个字符的权值(均>0),构造赫夫曼树HT,并求出n 个字符的赫夫曼编码HC */
int m,i,j,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;i<=n;++i,++p,++w,+