实验三哈夫曼编码.doc
文本预览下载声明
PAGE
第 PAGE 8 页 共 NUMPAGES 9 页
华北水利水电学院 数据结构 实验报告
2012～2013学年 第 一 学期 2010级 计算机科学与技术 专业
班级： 2010134 学号： 201013432 姓名： 蔡启林
实验三 树的应用
实验题目：
树的应用——哈夫曼编码
实验内容：
利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。
从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：
输出存放哈夫曼树的数组HT的初态和终态；
输出每个字符的哈夫曼编码；
输入由上述若干字符组成的字符串，对电文进行编码并输出；
（选作）输入电文的哈夫曼编码，进行译码并输出。
程序源代码：
#include stdio.h
#include string.h
#include stdlib.h
#include conio.h
#define MAXLEAF 100
struct HTNode
{
char letter;
int parent;
int lchild;
int rchild;
int weight;
};
struct ChNode
{
char letter;
int weight;
};
struct HCode
{
char code[MAXLEAF];
int m_start;
};
//创建哈夫曼树
void CreateHT(HTNode ht[],int n,ChNode s[])
{
int i,k,s1,s2;
int m1,m2;
for (i=0;i2*n-1;i++)
{
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].weight=0;
}
for (i=0;in;i++)
{
ht[i].letter=s[i].letter;
ht[i].weight=s[i].weight;
}
printf(哈夫曼树初态为:\n);
printf(data weight parent lchild rchild\n);
for (i=0;i2*n-1;i++)
{
printf(%-6c %-6d %-6d %-6d %-6d\n,ht[i].letter,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
}
for (i=n;i2*n-1;i++)
{
m1=m2=32767;
s1=s2=0;
for (k=0;k=i-1;k++)
{
if (ht[k].parent==0)
{
if (ht[k].weightm1)
{
m2=m1;
s2=s1;
m1=ht[k].weight;
s1=k;
}
else if (ht[k].weightm2)
{
m2=ht[k].weight;
s2=k;
}
}
}
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].weight=ht[s1].weight+ht[s2].weight;
ht[i].lchild=s1;
ht[i].rchild=s2;
}
printf(\n哈夫曼树终态为:\n);
printf(data weight parent lchild rchild\n);
for (i=0;i2*n-1;i++)
{
printf(%-6c %-6d %-6d %-6d %-6d\n,ht[i].letter,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
}
printf(\n);
}
//哈夫曼编码
void CreateCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,letter;
HCode hc;
for (i=0;in;i++)
{
hc.m_start=n-1;
letter=i;
f=ht[i].parent;
while(f!=-1)
{
if(ht[f].lchild==letter)
hc.code[hc.m_start--
显示全部