文档介绍：多媒体实验报告
实验一:Huffman编码
实验内容:
了解BMP图像的格式,实现BMP图片格式的数据域及文件头的分离
熟悉Huffman编码原理
用C语言使用Huffman编码算法对给定图像文件进行编码
设计思路
BMP文件的前54字节是与具体图像无关的文件头信息,进行哈夫曼编码时不需要对这部分进行编码。
哈夫曼编码基于图像统计特征的变长编码方法概率小的符号用较长的码字表示,概率大的符号用较短的码字表示。
霍夫曼编码的步骤:
根据待编码的符号串,统计各个符号的概率;
根据符号的概率统计特征,构建霍夫曼编码表,即计算每个符号的编码结果;
用得到的编码表对符号序列进行编码。
程序代码
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, *huffmantree;// 动态分配数组存储赫夫曼树
typedef char **huffmancode;// 动态分配数组存储赫夫曼编码表
int chengfang(int i)
{
int j,result=1;
for(j=0;j<i;j++)
{
result*=2;
}
return result;
}
void write_file(char temp[],FILE *fp2)
{
int i;
unsigned char result=0;
for(i=8;i>0;i--)
{
if(temp[8-i]!='0')
{
result+=chengfang(i-1);
}
}
strcpy(temp,temp+8);
fwrite(&result,1,1,fp2);
}
void select(huffmantree HT, unsigned int i, unsigned int *s1, unsigned int *s2)
{// s1为最小的两个值中序号小的那个
unsigned int j,temp;
for(j=1;j<=i;j++)
{
if(HT[j].parent==0)
{
*s2=j;
break;
}
}
for(;j<=i;j++)
{
if(HT[j].parent==0 && j!=*s2)
{
*s1=j;
break;
}
}
for(j=1;j<=i;j++)
{
if(HT[j].parent==0 && HT[j].weight < HT[*s1].weight && *s2!=j)
{
*s1=j;
}
}
for(j=1;j<=i;j++)
{
if(HT[j].parent==0 && HT[j].weight < HT[*s2].weight && *s1!=j)
{
*s2=j;
}
}
if(*s1>*s2)
{
temp=*s1;
*s1=*s2;
*s2=temp;
}
}
void huffmancoding(huffmantree &HT, huffmancode &HC,unsigned long int *w, unsigned int n)
{
// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
unsigned int s1,s2,start,c,f,i,m;// 0号单元未用
huffmantree p;
char *cd;
if (n<=1)
{
return;
}
m=2*n-1;
HT=(huffmantree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1; i<=n; ++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(; i<=m; ++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}