#include<iostream.h>
#include<string.h>
#define N 100
typedef struct
{
int wei //权值
int prt //父节点
int lch //左子节点
int rch// 右子节点
int tmp //中间变量，tmp=0 还未进行遍历 tmp=1 已近进行过向左遍历 tmp=2 已经进行过左右遍历 向上找到节点
char code[N]
}huffmantree
void input()
void print(huffmantree )
void select(huffmantree *HT,int n,int &i,int &j)
{
int k
i=1
while(HT[i].prt!=0)
{
i++
}
for(k=i+1k<=nk++)
{
if((HT[k].prt=0)&&(HT[k].wei <HT[i].wei))
i=k
}
j=1
while((j==i)||(HT[j].prt!=0))
{
j++
}
for(k=j+1k<=nk++)
{
if((HT[k].prt=0)&&k!=i&&HT[k].wei<HT[j].wei)
j=k
}
}
void huffman(int w[],huffmantree *HT,int n) //w存放n个字符的权值
{
int m=2*n-1
int i,k,j
huffmantree *p=0
for(p=HT+1,i=1i<=mi++,p++)
{
HT[i].prt=0
HT[i].lch=0
HT[i].rch=0
}
for(p=HT+1,i=1i<=ni++,p++)
{
HT[i].wei=w[i-1]
}
for(p=HT+n+1,i=n+1i<=mi++,p++)
{ HT[i].wei=0}
for(k=n+1k<=mk++)
{
select(HT,k-1,i,j) // 找最小值和次小值的位置
HT[i].prt=k,HT[j].prt=k // 找到i j 的父节点付给k
HT[k].lch=i,HT[k].rch=j // 父节点的左右指针分别指向i, j
HT[k].wei=HT[i].wei+HT[j].wei
}
}
void huffmancoding(huffmantree *HT,int n) //n个叶子结点的huffman编码 从根节点开始编码橡族
{
int BT=2*n-1
int m=BT
int l,r,p
char s1[100]="0",s2[100]="1"
for(int i=0i<=mi++)//中间变量赋初值
{ HT[i].tmp=0 }
strcpy(HT[m].code," ")
while(1)
{
l=HT[BT].lch
r=HT[BT].rch
p=HT[BT].prt
if(p==0&&HT[BT].tmp==2)
break
if(l==0||r==0)
{
HT[BT].tmp=2//如果是叶子结点则给中间变量赋值2向上返回一节结点
}
if(HT[BT].tmp==0) //未进行过遍历，开始向左遍历
{
HT[BT].tmp=1 //已经进行过向左遍历
l=HT[BT].lch
strcpy(HT[l].code,HT[BT].code)
strcat(HT[l].code,s1)
BT=l
}
else
if(HT[BT].tmp==1)
{
HT[BT].tmp=2
r=HT[BT].rch
strcpy(HT[r].code,HT[BT].code)
strcat(HT[r].code,s2)
BT=r
}
else if(HT[BT].tmp==2)
{
p=HT[BT].prt
BT=p
}
}
}
void print(huffmantree HT[],int n) //总共n个叶子节点
{
int i
cout<<"源码："<<endl
for(i=1i<=ni++)
cout<<HT[i].wei<<endl
cout<<"Huffman编码："<<endl
for(i=1i<=ni++)
{
cout<<HT[i].code<<endl
}
}
void input(int w[],int n)
{
int t,*p
int i=0
cout<<"对应的输入源码出现权值：(以-1结束)"<<endl
cin>>t
while(t>=0)
{
p=new int
*p=t
w[i]=*p
i++
cin>>t
}
}
void main()
{
int n,m
cout<<"输入源码个数："
cin>>n
int *w
w=new int[n+1]
input(w,n)
m=2*n-1
huffmantree *HT
HT=new huffmantree[m+1]
huffman(w,HT,n)
huffmancoding(HT,n)
print(HT,n)
delete w,HT
}
霍夫曼编码计算过程：无损数据压缩的熵编码。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而改凯腊达到无损压缩数据的目的。
例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比核滑特。
二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
霍夫曼编码历史：
1951年，霍夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报孙敏告题目是：查找最有效的二进制编码。
由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。
1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。
#include <stdio.h>#include <string.h>氏前察
/*
本题要求各函数的参数使用指针
假设字母a、b、c、d、e、歼茄f的霍夫曼编码分别是1、00、011、0100、01010、01011。那么字符串“abcdef”的编码显然就是字符串“10001101000101001011”。
（1）编写编码函数实现对字符串“abcdef”的编码，显示编码结果。
（2）编写译码函数对刚才得到的编码进行译码，显示译码结果。
（3）假设有一段编码“010111011010100100010010100”，请对其译码，并显示译码结果。
*/
char hufman[6][10] = {
{"a1"},
{"b00"},
{"c011"},
{"d0100"},
{"e01010"},
{"f01011"},
}
void code(char *src,char *dest)
{
int i
int len = 0
while(*src != '\0')
{
for(i=0i<6i++)
{
if(*src == hufman[i][0])
{
strcpy(dest + len,hufman[i]+1)
len += strlen(hufman[i]+1)
break
}
}
src ++
}
}
void decode(char *src,char *dest)
{
int i
int len = 0
while(*src != '\0')
{
for(i=0i<6i++)
{
if(strncmp(src,hufman[i]+1,strlen(hufman[i]+1)) == 0)
{
dest[len++] = hufman[i][0]
src += strlen(hufman[i]+1)
break
}
}
}
dest[len] 悔罩= 0
}
int main(int argc,char *argv[])
{
char *str = "abcdef"
char *str1 = "010111011010100100010010100"
char res[100] = {0}
char decodeRes[20]
code(str,res)
printf("%s\n",res)
decode(res,decodeRes)
printf("%s\n",decodeRes)
decode(str1,decodeRes)
printf("%s\n",decodeRes)
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）