1. Huffman树不是唯一的,这是因为在选择具有最小权值的2个节点时会出现权值相等的情况。
编码效率是不是一样的?不一样,但相差不大。
如何选择最小的?
2. 一组数,找最小的两个,算法的复杂度是O(n + ceil(log(n)) - 2),使用堆排序。
3. Huffman编码算法用于压缩。
程序如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedefstruct...{
unsignedintweight;
unsignedintparent;
unsignedintleft;
unsignedintright;
}HNode;
typedefchar**HCode;
voidselect(HNode*htree,inti,int&s1,int&s2)...{
for(intj=1;j<=i;j++)...{
if(htree[j].parent!=0)...{
continue;
}else...{
s1=j;
break;
}
}
for(j++;j<=i;j++)...{
if(htree[j].parent!=0)...{
continue;
}else...{
s2=j;
break;
}
}
if(htree[s1].weight>htree[s2].weight)...{
inttmp=s2;
s2=s1;
s1=tmp;
}
for(j=1;j<=i;j++)...{
if(htree[j].parent==0)...{
if(htree[j].weight<=htree[s2].weight)...{
if(htree[j].weight<htree[s1].weight)...{
s2=s1;
s1=j;
}else...{
if(j!=s1)...{
s2=j;
}
}
}
}
}
}
voidHuffmanCoding(HNode*htree,HCode&hcode,int*w,intn)...{
if(n<=1)...{
return;
}
intm=2*n-1;
inti=0;
htree=(HNode*)malloc(sizeof(HNode)*(m+1));
HNode*p=htree;
for(i=1;i<=n;i++)...{
p++;
(*p).weight=w[i-1];
(*p).parent=(*p).left=(*p).right=0;
}
for(;i<=m;i++)...{
p++;
(*p).weight=(*p).parent=(*p).left=(*p).right=0;
}
ints1=0,s2=0;
for(i=n+1;i<=m;i++)...{
select(htree,i-1,s1,s2);
htree[s1].parent=i;
htree[s2].parent=i;
htree[i].left=s1;
htree[i].right=s2;
htree[i].weight=htree[s1].weight+htree[s2].weight;
}
hcode=(HCode)malloc(sizeof(char*)*(n+1));
char*ch=(char*)malloc(n*sizeof(char));
ch[n-1]='
执行结果为:
Huffman编码为:
a:11111
b:10
c:1110
d:000
e:110
f:01
g:11110
h:001
1111110000110
abde
Pressanykeytocontinue
分享到:
相关推荐
数据结构: #define n 100 //叶子结点数 #define m 2*n-1 // Huffman树中结点总数 typedef struct { int weight; //权值 int lchild , rchild , parent; //左右孩子及双亲指针 }HTNode; //树中结点类型 typedef ...
本例实现了数据结构中的哈夫曼(huffman)算法, 完成编码与译码功能,附带本人的word设计。
韩英杰老师的数据结构中关于Huffman编码算法演示课件
Huffman树 及 Huffman编码 演示程序 以画图的方法形象的表示了树的构成,解决了普通控制台应用程序对树的结构表达不清的问题 编译器 VS2008
自己实现huffman树的代码,分享出来
非常适合大学数据结构课上使用。强烈推荐!~
数据结构C++ Huffman树的源代码,希望对大家有帮助
数据结构课程设计-huffman编码,用C语言编写,适用于清华大学等数据结构教程 huffman 赫夫曼编码 数据结构 课程设计 C语言
(1) 读入待编码的文字,统计各字符出现的频率 (2) 构造哈夫曼树 (3) 得到各字符的哈夫曼编码 (4) 对原文进行编码 (5) 发送、接收 (6) 还原(译码)收到的文字 (7) 利用哈夫曼树,从根到叶子读0、1序列...
字符文件统计字符出现频度,构造Huffman 树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件
一、实验三:Huffman编码(二叉树应用) 二、实验的目的和要求: 1.要求对文件进行Huffman编码的算法,以及对乙编码文件进行解码的算法,为简单起见,可以假设文件是存放在一个字符向量; 2.熟练掌握二叉树的应用;具体要求...
数据结构 用哈夫曼编码实现文件压缩 直接能用不用改 带有实验报告书
《数据结构与算法分析》课程设计报告,实现了Huffman编码
步骤: 1.用C语言实现二叉树的说明 2.输入n个权值,并生成n个二叉树 3.对n个二叉树逐步生成Huffman树 4.对Huffman树的每个叶子结点生成编码 5.输出叶子的编码,即输出每个权值及其对应的编码
Huffman树的编码和译码操作系统,包含两个头文件和对应的源文件,一个测试用的main源文件;欢迎大家学习和交流 1.我将访问的文件名以宏定义的方式放在源文件内,可以自行修改 默认: 读取huffman_test_file.txt---> ...
用HUffman编码,并实现压缩功能,有完整的文档,和结构图,是做课程设计弄的。
通过文件文件读入将huffman树以.dat文件形式保存,文件读出形式对树进行译码
数据结构课设,用c语言编写的单链表, 表达式求值, 二叉树 ,二叉排序树 ,Huffman编码,五个做成菜单,只有一个main函数