Huffman 编码

陕西科技大学实验报告
班级： 学号：姓名： 实验组别：
实验日期： 报告日期： 成绩：
报告内容：（目的和要求、原理、步骤、数据、计算、小结等）
实验名称：Huffman 编码

一、实验目的
(1) 进一步熟悉Huffman 编码过程。
(2) 掌握高级语言程序的设计和调试技术

二、实验设备
计算机及相关软件（如C,C++,PASCAL,VC,DELPHI等等）。
三、实验要求
(1) 输入：信源符号个数r、信源的概率分布
P
(2) 输出：每个信源符号对应的Huffman 编码的码字。

四、实验原理（流程图）：

五、实验数据（源代码）：
#include
#include
附页
2
#define MaxValue 1000 /*初始设定的权值最大值*/
#define MaxBit 10 /*初始设定的最大编码位数*/
#define MaxN 10 /*初始设定的最大结点个数*/
typedef struct
{
int weight; /*权值*/
int flag; /*标记*/
int parent; /*双亲结点下标*/
int leftChild; /*左孩子下标*/
int rightChild; /*右孩子下标*/
}HaffNode;
typedef struct
{
int bit[MaxN]; /*数组*/
int start; /*编码的起始下标*/
int weight; /*字符的权值*/
}Code;
void Haffman(int weight[], int n, HaffNode haffTree[])
{
int i, j, m1, m2, x1, x2;
for(i = 0; i < 2 * n - 1 ; i++)
{
if(i < n) haffTree[i].weight = weight[i];
else haffTree[i].weight = 0;
haffTree[i].parent = -1;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1;
}
for(i = 0;i < n-1;i++)
{
m1 = m2 = MaxValue;
x1 = x2 = 0;
for(j = 0; j < n+i;j++)
{
if(haffTree[j].weight < m1 && haffTree[j].flag == 0)
{
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
}
else if(haffTree[j].weight < m2 && haffTree[j].flag == 0)
{
附页
3
m2 = haffTree[j].weight;
x2 = j;
}
}
haffTree[x1].parent = n+i;
haffTree[x2].parent = n+i;
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild = x1;
haffTree[n+i].rightChild = x2;
}
}
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
{
Code *cd = (Code *)malloc(sizeof(Code));
int i, j, child, parent;
for(i = 0; i < n; i++)
{
cd->start = n-1; /*不等长编码的最后一位为n-1*/
cd->weight = haffTree[i].weight; /*取得编码对应的权值*/
child = i;
parent = haffTree[child].parent;
while(parent != -1)
{
if(haffTree[parent].leftChild == child)
cd->bit[cd->start] = 0; /*左孩子结点编码0*/
else
cd->bit[cd->start] = 1; /*右孩子结点编码1*/
cd->start--;
child = parent;
parent = haffTree[child].parent;
}

for(j = cd->start+1; j < n; j++)
haffCode[i].bit[j] = cd->bit[j];
haffCode[i].start = cd->start + 1; /*保存叶结点编码的起
始位*/
haffCode[i].weight = cd->weight; /*保存叶结点对应的权
值*/
}
}
void main(void)
{
附页
4
int i, j, n = 4;
int weight[] = {4,3,2,1};
char p[4];
printf("请输入四个信源符号:");
for(i=0;i<4;i++)
scanf("%c",&p[i]);
HaffNode *myHaffTree = (HaffNode
*)malloc(sizeof(HaffNode)*(2*n+1));
Code *myHaffCode = (Code *)malloc(sizeof(Code)*n);
if(n > MaxN)
{
printf("给出的n越界，修改MaxN!\n");
exit(1);
}
Haffman(weight, n, myHaffTree);
HaffmanCode(myHaffTree, n, myHaffCode);
/*输出每个叶结点的哈夫曼编码*/
for(i = 0; i < n; i++)
{ printf("信源符号是:%c",p[i]);
printf(" 概率为: %d/10 信源符号编码为: ",
myHaffCode[i].weight);
for(j = myHaffCode[i].start; j < n; j++)
printf("%d", myHaffCode[i].bit[j]);
printf("\n");
}
}

六、程序运行结果：

七、实验小结：
通过本次实验，使我对Huffman 编码有了进一步的了解，掌握了霍夫曼编
码的过程，在做的过程中，遇到了很多问题，在同学和老师的帮助下，算出了最
后的结果，Huffman 编码的思想就是让概率越大的，或是权值越大的其对应的码
字越短。