暂时只实现了显示编码结果，求平均码长没有完成。
成都创新互联公司是一家集网站建设,铁力企业网站建设,铁力品牌网站建设,网站定制,铁力网站建设报价,网络营销,网络优化,铁力网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
#include iostream
using namespace std;
/*
* 霍夫曼树结构
*/
class HuffmanTree
{
public:
unsigned int Weight, Parent, lChild, rChild;
};
typedef char **HuffmanCode;
/*
* 从结点集合中选出权值最小的两个结点
* 将值分别赋给s1和s2
*/
void Select(HuffmanTree* HT,int Count,int *s2,int *s1)
{
unsigned int temp1=0;
unsigned int temp2=0;
unsigned int temp3;
for(int i=1;i=Count;i++)
{
if(HT[i].Parent==0)
{
if(temp1==0)
{
temp1=HT[i].Weight;
(*s1)=i;
}
else
{
if(temp2==0)
{
temp2=HT[i].Weight;
(*s2)=i;
if(temp2temp1)
{
temp3=temp2;
temp2=temp1;
temp1=temp3;
temp3=(*s2);
(*s2)=(*s1);
(*s1)=temp3;
}
}
else
{
if(HT[i].Weighttemp1)
{
temp2=temp1;
temp1=HT[i].Weight;
(*s2)=(*s1);
(*s1)=i;
}
if(HT[i].Weighttemp1HT[i].Weighttemp2)
{
temp2=HT[i].Weight;
(*s2)=i;
}
}
}
}
}
}
/*
* 霍夫曼编码函数
*/
void HuffmanCoding(HuffmanTree * HT,
HuffmanCode * HC,
int *Weight,
int Count)
{
int i;
int s1,s2;
int TotalLength;
char* cd;
unsigned int c;
unsigned int f;
int start;
if(Count=1) return;
TotalLength=Count*2-1;
HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];
for(i=1;i=Count;i++)
{
HT[i].Parent=0;
HT[i].rChild=0;
HT[i].lChild=0;
HT[i].Weight=(*Weight);
Weight++;
}
for(i=Count+1;i=TotalLength;i++)
{
HT[i].Weight=0;
HT[i].Parent=0;
HT[i].lChild=0;
HT[i].rChild=0;
}
//建造霍夫曼树
for(i=Count+1;i=TotalLength;++i)
{
Select(HT, i-1, s1, s2);
HT[s1].Parent = i;
HT[s2].Parent = i;
HT[i].lChild = s1;
HT[i].rChild = s2;
HT[i].Weight = HT[s1].Weight + HT[s2].Weight;
}
//输出霍夫曼编码
(*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
cd = new char[Count*sizeof(char)];
cd[Count-1]='\0';
for(i=1;i=Count;++i)
{
start=Count-1;
for(c = i,f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent)
{
if(HT[f].lChild == c)
cd[--start]='0';
else
cd[--start]='1';
(*HC)[i] = new char [(Count-start)*sizeof(char)];
strcpy((*HC)[i], cd);
}
}
delete [] HT;
delete [] cd;
}
/*
* 在字符串中查找某个字符
* 如果找到，则返回其位置
*/
int LookFor(char *str, char letter, int count)
{
int i;
for(i=0;icount;i++)
{
if(str[i]==letter) return i;
}
return -1;
}
void OutputWeight(char *Data,int Length,
char **WhatLetter,
int **Weight,int *Count)
{
int i;
char* Letter = new char[Length];
int* LetterCount = new int[Length];
int AllCount=0;
int Index;
int Sum=0;
float Persent=0;
for(i=0;iLength;i++)
{
if(i==0)
{
Letter[0]=Data[i];
LetterCount[0]=1;
AllCount++;
}
else
{
Index=LookFor(Letter,Data[i],AllCount);
if(Index==-1)
{
Letter[AllCount]=Data[i];
LetterCount[AllCount]=1;
AllCount++;
}
else
{
LetterCount[Index]++;
}
}
}
for(i=0;iAllCount;i++)
{
Sum=Sum+LetterCount[i];
}
(*Weight) = new int[AllCount];
(*WhatLetter) = new char[AllCount];
for(i=0;iAllCount;i++)
{
Persent=(float)LetterCount[i]/(float)Sum;
(*Weight)[i]=(int)(100*Persent);
(*WhatLetter)[i]=Letter[i];
}
(*Count)=AllCount;
delete [] Letter;
delete [] LetterCount;
}
int main()
{
HuffmanTree * HT = NULL;
HuffmanCode HC;
char Data[100];
char *WhatLetter;
int *Weight;
int Count;
cout"请输入一行文本数据:"endl;
cinData;
coutendl;
OutputWeight(Data,strlen(Data),
WhatLetter,
Weight,
Count);
HuffmanCoding(HT, HC, Weight, Count);
cout"字符出现频率编码结果"endl;
for(int i = 0; iCount; i++)
{
coutWhatLetter[i]" ";
coutWeight[i]"%\t";
coutHC[i+1]endl;
}
coutendl;
system("pause");
return 0;
}
以前写的，证明最优子结构，随便一本算法书上就有. #includestdio.h
#includestdlib.h
#define NIL -2
#define Size_Max_bm 30
#define left(i) (2*(i)+1)
#define right(i) (2*(i)+2)
#define swap(a,b) {cjys t;t=(a);(a)=(b);(b)=t;}
#define parent(i) ((i)%2?((i)-1)/2:((i)-2)/2)typedef struct cjys
{
char sj;
int pl;
struct cjys *left;
struct cjys *right;
}cjys;typedef struct cjdl
{
int size;
int leapsize;
cjys *p;
}cjdl;
cjys *fpnn(void);
void input(cjdl *p);
cjys *fpnn(void);
void zxdwh(cjys *p, int i, int leapsize);
void rd(cjdl *p, cjys tp);
cjys cd(cjdl *p);
void hbs(cjdl *p);
cjys *cjs(cjdl *p);
void bls(cjys *p,int *jl, int i);
void disp(char *tp, cjys *p);int main()
{
cjdl p;
char x[255];
cjys *re=NULL;
int jl[Size_Max_bm];
input(p);
re=cjs(p);
printf("对照编码图为:\n");
bls(re,jl,0);
freopen("CON","r",stdin);
printf("输入Huffman码(VLC):");
scanf("%s",x);
disp(x,re);
system("pause");
}
void input(cjdl *p)
{
int i;
cjys *tp;
tp=fpnn();
printf("输入字母个数:");
scanf("%d", p-size);
p-p=malloc(sizeof(cjys)*p-size);
p-leapsize=0;
for(i = 0; i p-size;i++)
{
printf("输入第%d字母:",i+1),scanf(" %c",tp-sj);
printf("输入出现次数(频率整数):"),scanf("%d",tp-pl);
rd(p,*tp);
}
free(tp);
}
cjys *fpnn(void)
{
cjys *p=NULL;
p=malloc(sizeof(cjys));
p-left=NULL;
p-right=NULL;
return p;
} void zxdwh(cjys *p, int i, int leapsize)
{
int l=left(i), r=right(i), mini=i;
if(lleapsize p[l].plp[mini].pl)
mini=l;
if(rleapsize p[r].plp[mini].pl)
mini=r;
if(mini != i)
{
swap(p[i],p[mini]);
zxdwh(p,mini,leapsize);
}
}
void rd(cjdl *p, cjys tp)
{
if(p-leapsize == p-size)
{
printf("队列已满!");
exit(0);
}
p-p[p-leapsize]=tp;
int j=p-leapsize,k=parent(j);
while(k=0 p-p[j].pl p-p[k].pl)
{
swap(p-p[j],p-p[k]);
j=k;
k=parent(j);
}
p-leapsize++;
}
cjys cd(cjdl *p)
{
if(p-leapsize == 0)
{
printf("队列已空!");
exit(0);
}
cjys tp=p-p[0];
p-leapsize--;
p-p[0]=p-p[p-leapsize];
zxdwh(p-p,0,p-leapsize);
return tp;
}
void hbs(cjdl *p)
{
cjys *p1=NULL, *p2=NULL;
cjys tp;
p1=fpnn();
p2=fpnn();
*p1=cd(p);
*p2=cd(p);
tp.left=p1;
tp.right=p2;
tp.pl=p1-pl+p2-pl;
tp.sj=NIL;
rd(p,tp);
}cjys *cjs(cjdl *p)
{
int i, n=p-leapsize;
cjys *tp=NULL;
tp=fpnn();
for(i = 0; i n-1; i++)
hbs(p);
*tp=p-p[0];
return tp;
}
void bls(cjys *p, int *jl, int i)
{
if(p == NULL)
return;
if(p-sj!=NIL)
{
int i2;
printf("%c:",p-sj);
for(i2 = 0; i2 i; i2++)
printf("%d",jl[i2]);
printf("\n");
}
jl[i]=0;
bls(p-left,jl,i+1);
jl[i]=1;
bls(p-right,jl,i+1);
}
void disp(char *tp, cjys *p)
{
cjys *ttp=NULL;
int pd=0;
while(1)
{
ttp=p;
while(1)
{
if(ttp-sj != NIL)
{
printf("%c",ttp-sj);
break;
}
if(*tp == '\0')
{
pd=1;
break;
}
if(*tp++ == '0' )
ttp=ttp-left;
else
ttp=ttp-right;
}
if(pd)
break;
}
}
这是我们大三做的一个上机题：
上机题：设电文字符集D及各字符出现的概率F如下：
D={a，b，c，d，e，f，g，h}（字符数n=8）
F={5，29，7，8，14，23，3，11}(%)
编写完成下列功能的程序：
①构造关于F的Huffman树；
②求出并打印D总各字符的Huffman编码。
程序结构： 类型说明；
构造Huffman树的函数：Huffman_tree(H[m+1])；
求Huffman编码的函数：Huffman_code(code[n+1])；
main()
{ 变量说明；
输入字符集D及频率F；
调用Huffman_tree(H)；
调用Huffman_code(code)；
打印编码；Y继续，N退出}
运行后，输入8个字符（中间不能有空格，否则将空格视为字符处理），然后输入概率（整数，空格或回车分隔。如果要支持浮点数，要改程序）然后Enter，出现构造的霍夫曼节点和编码，程序如下
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 8
#define M 2*N-1
#define MAX 32767
typedef char datatype;
typedef struct
{
int wi;
char data;
int Parent,Lchild,Rchild;
}huffm;
typedef struct
{
char bits[N+1];
int start;
char ch;
}ctype;
void Huffman_tree(huffm H[M+1])
{
int i,j,p1,p2;
int w,s1,s2;
for(i=1;i=M;i++)
{
H[i].wi=MAX;
H[i].Parent=0;
H[i].Lchild=H[i].Rchild=0;
}
printf("please enter the weight:\n");
for(i=1;i=N;i++)
{
scanf("%d",H[i].wi);
}
for(i=N+1;i=M;i++)
{
p1=p2=0;
s1=s2=MAX;
for(j=1;j=M;j++)
if(H[j].Parent==0)
if(H[j].wis1)
{
s2=s1;
s1=H[j].wi;
p2=p1; p1=j;
}
else if(H[j].wis2) {s2=H[j].wi; p2=j;}
H[p1].Parent=H[p2].Parent=i;
H[i].Lchild=p1;
H[i].Rchild=p2;
H[i].wi=H[p1].wi+H[p2].wi;
}
printf("Number\tParent\tLchild\tRchild\n");
for(i=1;i=M;i++)
printf("%d\t%d\t%d\t%d\n",i,H[i].Parent,H[i].Lchild,H[i].Rchild);
}
void Huffman_code(ctype code[N+1])
{
int i,j,p,s;
char c[N];
huffm H[M+1];
ctype md;
printf("please enter char:\n");
/* for(i=1;i=N;i++)
{
scanf("%c",c);
H[i].data=code[i].ch=c;
}
*/
scanf("%s",c);
for(i=1;i=N;i++)H[i].data=code[i].ch=c[i-1];
Huffman_tree(H);
for(i=1;i=N;i++)
{
md.ch=code[i].ch;
md.start=N+1;
s=i;
p=H[i].Parent;
while(p!=0)
{
md.start--;
if(H[p].Lchild==s)
md.bits[md.start]='1';
else
md.bits[md.start]='0';
s=p;
p=H[p].Parent;
}
code[i]=md;
}
printf("print the code:\n");
for(i=1;i=N;i++)
printf("%c\t",code[i].ch);
printf("\n");
for(i=1;i=N;i++)
{
for(j=code[i].start;j=N;j++)
printf("%c",code[i].bits[j]);
printf("\t");
}
printf("\n");
}
int Continue()
{ char c;
getchar();
printf("continue? y/n\n");
c=getchar();
if(c=='y') return 1;
else return 0;
}
main()
{
do{
/* huffm H[M+1]; */
ctype code[N+1];
Huffman_code(code);
}while(Continue());
}
说明：本程序是依据严蔚敏的数据结构（C语言版）上的代码实现的。
#pragmaonce
#includestdio.h
#includetchar.h
#includestdlib.h
#define MAX 100
typedefstruct{ //节点
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedefchar **HuffmanCode; //字符串数组，用于存储叶子节点的编码
void SelectMinNode(HuffmanTree HT, int m, int i1, int i2) //找出权值最小的两个节点对应的数组下标
{
HuffmanTree p = HT;
int s1, s2;
s1 = s2 = MAX;
i1 = i2 = 1;
for(int i=1; i=m; i++)
{
if(!(p+i)-parent)
{
if((p+i)-weight s1)
{
i2 = i;
s1 = (p+i)-weight ;
}
}
}
for(int i=1; i=m; i++)
{
if(!(p+i)-parent i!=i2)
{
if((p+i)-weight s2)
{
i1 = i;
s2 = (p+i)-weight ;
}
}
}
}
void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制
{
char *c1, *c2;
c1 = p;
while(q != '\0')
{
*c1 = q;
c1++;
start++;
}
*c1 = q;//别忘了将‘\n’复制过来
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n)
{ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数
int i, i1, i2, m;
HuffmanTree p;
if(n=1) return;
m = 2 * n -1; //n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //数组首元素不使用，故多分配一个空间
p = HT + 1;
for(i=1;i=n;++i,++p,++w) //n个叶子节点初始化
{
p-weight = *w;
p-lchild = 0;
p-rchild = 0;
p-parent = 0;
}
for(;i=m;++i,++p) //非叶子节点初始化
{
p-weight = 0;
p-lchild = 0;
p-rchild = 0;
p-parent = 0;
}
for(i=n+1;i=m;++i) //对非叶子节点重新计算
{
SelectMinNode(HT, i-1, i1, i2);
HT[i1].parent = i;
HT[i2].parent = i;
HT[i].lchild = i1;
HT[i].rchild = i2;
HT[i].weight = HT[i1].weight + HT[i2].weight ;
}
///从叶子节点到根节点求赫夫曼编码
char* cd;
int start, c, f;
HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字符指针数组，同样多分配一个
cd = (char*)malloc(n*sizeof(char)); //零时变量，用于存储当前叶子节点的赫夫曼编码
cd[n-1] = '\0';
for(int i=1; i=n; i++)
{
start = n-1;
for(c=i,f=HT[i].parent; f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
}
HC[i] = (char*)malloc((n-start)*sizeof(char));
StrCopy(HC[i], cd, start); //将存储的编码copy给HC的第i个数组
}
free(cd);
}
void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各节点的赫夫曼编码
{
HuffmanCode p;
for(int i=1; i=n; i++)
{
p = HC;
printf("The weight %d HuffmanCode is: ", HT[i]);
while(*p[i]!='\0')
{
printf("%c",*p[i]);
p[i]++;
}
printf("\n");
}
}
void main()
{
int n = 8;
HuffmanTree HT;
HuffmanCode HC;
int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信号源的概率分布，即P={p0, p1,…, pK-1}
HuffmanCoding(HT, HC, a, n);
PrintHuffmanCode(HT, HC, n);
system("pause");}
哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
本文描述在网上能够找到的最简单，最快速的哈夫曼编码。本方法不使用任何扩展动态库，比如STL或者组件。只使用简单的C函数，比如：memset，memmove，qsort，malloc，realloc和memcpy。
因此，大家都会发现，理解甚至修改这个编码都是很容易的。
背景
哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
编码使用
我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。
bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *pDes, int nDesLen);
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *pDes, int nDesLen);
要点说明
速度
为了让它(huffman.cpp)快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。
压缩
压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount 256; nCount++)
nodes[nCount].byAscii = nCount;
然后，计算在输入缓冲区数据中，每个ASCII码出现的频率：
for(nCount = 0; nCount nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然后，根据频率进行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
现在，构造哈夫曼树，获取每个ASCII码对应的位序列：
int nNodeCount = GetHuffmanTree(nodes);
构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。
// parent node
pNode = nodes[nParentNode++];
// pop first child
pNode-pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode-pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode-pLeft-pParent = pNode-pRight-pParent = pNode;
// adjust parent frequency
pNode-nFrequency = pNode-pLeft-nFrequency + pNode-pRight-nFrequency;
这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex3)) |=
nodes[pSrc[nCount]].dwCode (nDesIndex7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex3): 3 以8位为界限右移后到达右边字节的前面
(nDesIndex7): 7 得到最高位.
注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。
解压缩
解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex3)))(nSrcIndex7);
pNode = pRoot;
while(pNode-pLeft)
{
pNode = (nCode1) ? pNode-pRight : pNode-pLeft;
nCode = 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode-byAscii;
}
重庆分公司
重庆分公司
