C++霍夫曼编码

暂时只实现了显示编码结果，求平均码长没有完成。

成都创新互联公司是一家集网站建设,铁力企业网站建设,铁力品牌网站建设,网站定制,铁力网站建设报价,网络营销,网络优化,铁力网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

#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;

}

霍夫曼编码 用c语言实现

以前写的，证明最优子结构，随便一本算法书上就有. #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;

}

}

哈夫曼编码 c++，输入字符和出现的概率，求输入的数据的Huffman树路径？要求代码！！！，急急急

这是我们大三做的一个上机题：

上机题：设电文字符集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());

}

Huffman编码C语言实现

说明：本程序是依据严蔚敏的数据结构（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）编码学习的重点和难点是什么

哈夫曼编码(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;

}

名称栏目：c语言霍夫曼函数 c语言阿克曼函数
本文路径：http://kswjz.com/article/dodhsoc.html