C语言-哈夫曼编码实验报告
福 建 工 程 学 院
课 程: 数据结构
题 目: 哈夫曼编码和译码
专 业: 信息管理信息系统
班 级: 1002班
座 号: 15号
姓 名: 林左权
2011年 6月 27日
1
实验题目:哈夫曼编码和译码
一、要解决的问题
利用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这
要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双
工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
二、算法基本思想描述:
根据给定的字符和其中每个字符的频度,构造哈夫馒树,并输出字符集中每个字符的哈夫曼编码.将给定
的字符串根据其哈夫曼编码进行编码,并进行相应的译码.
三、设计
1. 数据结构的设计
(1)哈夫曼树的
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示
设计哈夫曼树的结构体(htnode),其中包含权重、左右孩子、父母和要编码的字符。用这个
结构体(htnode)定义个哈夫曼数组(hfmt[])。
迷宫定义如下:
typedef struct
{
int weight;
int lchild;
int rchild;
int parent;
char key;
}htnode;
typedef htnode hfmt[MAXLEN]; (2)对原始字符进行编码
初始化哈夫曼树(inithfmt)。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。 并显示出每个字符的编码。
1.void inithfmt(hfmt t)//对结构体进行初始化
2.void inputweight(hfmt t)//输入函数
3.void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数 4.void creathfmt(hfmt t)//创建哈夫曼树的函数
5.void phfmnode(hfmt t)//对字符进行初始编码
(3)对用户输入的字符进行编码
void encoding(hfmt t)//对用户输入的电文进行编码 {
char r[1000];//用来存储输入的字符串
int i,j;
printf("\n\n请输入需要编码的字符:");
gets(r);
printf("编码结果为:");
for(j=0;r[j]!='\0';j++)
for(i=0;i
清单
安全隐患排查清单下载最新工程量清单计量规则下载程序清单下载家私清单下载送货清单下载
:
#include
#include
#include
#define MAXLEN 100
typedef struct
{
int weight;
3
int lchild;
int rchild;
int parent;
char key;
}htnode;
typedef htnode hfmt[MAXLEN];
int n;
void inithfmt(hfmt t)//对结构体进行初始化 {
int i;
printf("\n");
printf("------------------------------------------------------------------\n");
printf("******************************输入区******************************\n");
printf("\n请输入n=");
scanf("%d",&n);
getchar();
for(i=0;i<2*n-1;i++)//对结构体进行初始化
{
t[i].weight=0;
t[i].lchild=-1;
t[i].rchild=-1;
t[i].parent=-1;
}
printf("\n");
}
void inputweight(hfmt t)//输入函数
{
int w;//w表示权值
int i;
char k;//k表示获取的字符
for(i=0;it[j].weight)
{
min1=t[j].weight;
*p1=j;
}
for(j=0;j<=i;j++)//选择次小权值字符的下标还回
if(t[j].parent==-1)
if(min2>t[j].weight && j!=(*p1))//注意 j!=(*p1))
{
min2=t[j].weight;
*p2=j;
}
}
void creathfmt(hfmt t)//创建哈夫曼树的函数
{
int i,p1,p2;
inithfmt(t);
inputweight(t);
for(i=n;i<2*n-1;i++)
{
selectmin(t,i-1,&p1,&p2);
t[p1].parent=i;
t[p2].parent=i;
t[i].lchild=p1;
t[i].rchild=p2;
t[i].weight=t[p1].weight+t[p2].weight;
}
}
void printhfmt(hfmt t)//打印哈夫曼树
{
int i;
5
printf("------------------------------------------------------------------\n");
printf("**********************哈夫曼编数结构:*****************************\n");
printf("\t\t权重\t父母\t左孩子\t右孩子\t字符\t");
for(i=0;i<2*n-1;i++)
{
printf("\n");
printf("\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,
t[i].key);
}
printf("\n------------------------------------------------------------------\n")
;
printf("\n\n"); }
void hfmtpath(hfmt t,int i,int j)//编码的重要哈夫曼树路径递归算法 {
int a,b;
a=i;
b=j=t[i].parent;
if(t[j].parent!=-1)
{
i=j;
hfmtpath(t,i,j);
}
if(t[b].lchild==a)
printf("0");
else
printf("1");
}
void phfmnode(hfmt t)//对字符进行初始编码
{
int i,j,a;
printf("\n------------------------------------------------------------------\n")
;
printf("**************************哈夫曼编码
6
******************************");
for(i=0;i
本文档为【C语言-哈夫曼编码实验报告】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。