当前位置:文档之家› 哈夫曼树编码译码实验报告

哈夫曼树编码译码实验报告

for(p=HT+1,i=1;i<=n;++i,++p,++w,++ch)
{
(*p).ch=*ch;
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
{(*p).ch='*';
(*p).parent=0;
2.将哈夫曼树存储结构定义放在一个头文件:取名为huffermandef.h。
typedef struct
{char ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /*动态分配数组存储赫夫曼树*/
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2因为在math. h中已定义OVERFLOW的值为3,故去掉此行*/
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等*/
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
编写主程序,实现对各不同的算法调用。
五、实验环境(使用的软件):
Visaul C+6.0
六、实验步骤及操作:
打开VC++6.0创建工程/Win32 Console Application,输入工程名:哈夫曼树,新建三个.h文件一个.cpp文件
1.将一些常量定义,系统函数原型声明和类型(Status)重定义,结果状态代码等放在一个头文件中:取名为huffermanpubuse.h。
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/*函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
{ /* 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) /*算法6.12 */
2.编码,用已建好的哈夫曼树,对文件ToBeTran.data中的文本进行编码形成报文,将报文写在文件Code.text中;
3.译码,利用已建好的哈夫曼树,对文件Code中的代码进行解码形成原文,结果存入文件Text中;
4.输出,输出Data中出现的字符以及各字符出现的频度(或概率);输出ToBeTran.data及其报文Code.text;输出Code及其原文Text。
}
for(i=n+1,j=1;i<=m;++i,j++) /*建赫夫曼树*/
{ /*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
select(HT,i-1,&s1,&s2);
printf("第%d次比较min1与min2:%d %d",j,HT[s1].weight,HT[s2].weight);
实验报告
一、实验题目:哈夫曼编/译码系及其应用
二、实验地点:
三、实验目的:
1.掌握哈夫曼树的概念、存储结构
2.掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算
3.熟练掌握二叉树的应用
四、实验内容:
实现哈夫曼树的生成,完成哈夫曼编/译码的输出。
1.初始化,从数据文件Data中读入字符及每个字符的权值,建立哈夫曼树HuffTree;
/*分配n个字符编码的头指针向量([0]不用) */
cd=(char*)malloc(n*sizeof(char)); /*分配求编码的工作空间*/
{ /* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC */
int m,i,j,s1,s2,start;
unsቤተ መጻሕፍቲ ባይዱgned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用*/
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)
typedef char **HuffmanCode; /*动态分配数组存储赫夫曼编码表*/
3.将哈夫曼树的基本操作算法也集中放在一个文件之中,取名为huffermanalgo.h。
int min1(HuffmanTree t,int i)
{ /*函数void select()调用*/
int j,flag;
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等*/
#include<limits.h> /* INT_MAX等*/
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
printf("\n");
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/*从叶子到根逆向求每个字符的赫夫曼编码*/
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
相关主题