问题 J: 赫夫曼编码
题目描述
赫夫曼编码能够产生最短的报文。以报文“ABCDABCDABCABDABAA”为例,A编为0,B对应10,C对应110,D对应111,整体的报文长度为35位二进制。相比于定长的ASCII码,压缩比达到了18*8/35=4.1。
输入
输入有一系列的字符串组成,每个字符串占据一行。字符串仅包含大写字母和下划线。字符串“END”<wbr></wbr>表示处理结束,不应对其处理。
输出
对每一个字符串,输出其ASCII编码的比特位长度,赫夫曼编码的比特位长度,以及二者之比,精确到小数点后一位。
样例输入
ABCDABCDABCABDABAA<wbr></wbr>
AAAAAAAAAAAAAAAAAA
END
样例输出
144 35 4.1<wbr></wbr>
144 18 8.0
我费了九牛二虎之力,最终做了出来,代码如下,以作纪念:
#include <stdio.h>
#include<string.h>
#define N 100
#define MAX 1000
#define OK 1
typedef struct //huffman节点
{
char data;
int weight;//权值
int parent;//记录父结点下标
int lchild;//左孩子
int rchild;//右孩子
}HTNode;
int CreateHT(HTNode ht[],int n)//构造huffman树的代码没有一点错误
{
int i,k,lnode,rnode;
int min1,min2;
for(i=0;i<2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for(i=n;i<2*n-1;i++)
{
min1=min2=32767;
lnode=rnode=-1;//lnode和rnode为最小权重的两个节点的位置
for(k=0;k<=i-1;k++)
if(ht[k].parent==-1)//只在尚未构造二叉树的结点中查找
{
if(ht[k].weight<min1)//在节点中找到两个最小的,min1和min2记录下标
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;//记录下最小权重的下标
}
else if(ht[k].weight<min2)
{
min2=ht[k].weight;
rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;//更新父结点以及子节点的下标
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
return OK;
}
int AddNum(HTNode ht[],int hcd[],int k)
{
int i,f;
if(k==1)//结点分两种情况,一种是只有一个结点
{
hcd[0]=1;
return 0;
}
else//另一种是大于等于两个结点
{ for(i=0;i<k;i++)
{
hcd[i]=0;
f=ht[i].parent;
while(f!=-1)//向上回溯寻找父结点,直至找到整棵树的根节点
{
hcd[i]++;//父结点不为空,那数目就自增1(Huffman编码长度增1)
f=ht[f].parent;
}
}
}
return OK;
}
int main()
{
char str1[MAX];
HTNode node[MAX];
int hcd[MAX];//用于记录每个编码的长度
int i,j,k,m;
float s;
while(1)
{
k=0;
scanf("%s",str1);
if(strcmp(str1,"END")==0) continue;
for(i=0;str1[i]!='\0';i++)
{
node[i].weight=0;
for(j=0;j<k;j++)//从第一位开始搜索,如果找到了相同的字符,那么该字符权值增1
if(node[j].data==str1[i])
{
node[j].weight=node[j].weight+1;
break;//找到了就不必再循环,读下一个字符
}
if(j==k)//没找到,就加入node数组
{
node[k].data=str1[i];
node[k].weight=node[k].weight+1;
k++;
}
}//最后得到的k为字符的种类数目
m=i;//记录下i的值,i为输入的总字符的个数
CreateHT(node,k);//构建一棵Huffman树
AddNum(node,hcd,k);//获取个个字符HUffman编码的长度
for(i=0,s=0.0;i<k;i++)
s=s+hcd[i]*node[i].weight;//获取用Huffman编码时总字符长度
printf("%d %.0f %.1f\n",m*8,s,m*8/s);
}
return 0;
}
分享到:
相关推荐
包含代码 课程设计说明书 题目是赫夫曼 一块打包
《数据结构课程设计》赫夫曼编码实验报告本人做的,仅供参考!!!
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行...试为这样的信息收发站设计一个哈夫曼编/译码系统。
《数据结构课程设计》赫夫曼编码实验报告.pdf
而这次我们的课程设计对编码译码的要求不是太高,只是将大写字母或小写字母转化成二进制编码,或将二进编码转化成大写字母或小写字母,虽然功能有一点局限,但也是一次成功的尝试,能满足一般的需求
赫夫曼树构建 赫夫曼编码 数据结构 C语言 动画 用C语言动画演示赫夫曼树的构建以及赫夫曼编码的实现
赫夫曼编码赫夫曼编码赫夫曼编码赫夫曼编码赫夫曼编码赫夫曼编码
本人本科期间学习数据结构写的实验,内容如下 1、输入一段报文,例如: CAST CAST SAT AT A TASA ... 2、建赫夫曼树,并输出各个字符的赫夫曼编码 3、输入编码01100……,能准确翻译成报文 4、要求有菜单。
进行赫夫曼编码类的设计并实现,包括以下功能
数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码 数据结构 严蔚敏 赫夫曼编码
哈弗曼 数据结构课程设计实验报告(赫夫曼编码).doc
一、实验目的 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性,以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容 赫夫曼树的算法。
华中科技大学数据结构试验——赫夫曼编码实验
根据严蔚敏数据结构书上的伪码实现的赫夫曼编码译码程序。对26个英文字母加上逗号,句号,空格以及回车进行赫夫曼编码。然后对给定的txt文件(英文文章)进行赫夫曼编码和译码。
数据结构 赫夫曼树 C++ 课程作业。 现在看来很简单的一些代码
课程设计作业,里面用C语言写的,供大家参考。算法和思想也在里面
赫夫曼树是树的一个非常重要的应用。又称最优二叉树,从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。树的路径长度是从树根到结点路径长度之和。所以重要的就是如何...
利用赫夫曼树的编码思想,构造一个完整的赫夫曼编码系统。源代码还附赠了详细的PPT讲解。 ①从键盘读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树,然后对赫夫曼树进行编码,输出结果。 ②使用上述字符集创建...
问题描述:对任意输入的一段英文,为每个字符编制其相应的赫夫曼编码;并利用该编码为任意输入的0、1序列进行解码. 基本要求:一个完整的系统应具有以下功能: (1)初始化 从终端读入一段英文字符,统计每个字符...