c语言哈夫曼函数 哈夫曼树及哈夫曼编码的算法实现c语言

怎么样用c语言程序编码哈夫曼树？

#includestdio.h

#includestdlib.h

#includestring.h

#include ctype.h

#includelimits.h

int function1(char ch,char *s)

{

int i;

for(i=0; s[i]!='\0'; i++)

{

if(ch==s[i])return 0;

}

return 1;

}

typedef struct

{

unsigned int weight;

unsigned int parent,lchild,rchild;

} HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树

typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表

// algo6-1.cpp 求赫夫曼编码。实现算法6.12c语言哈夫曼函数的程序

int min(HuffmanTree t,int i)

{

// 函数void select()调用

int j,flag;

unsigned int k=UINT_MAX; // 取k为不小于可能c语言哈夫曼函数的值

for(j=1; j=i; j++)

if(t[j].weightkt[j].parent==0)

k=t[j].weight,flag=j;

t[flag].parent=1;

return flag;

}

void select(HuffmanTree t,int i,int s1,int s2)

{

// s1为最小c语言哈夫曼函数的两个值中序号小c语言哈夫曼函数的那个

s1=min(t,i);

s2=min(t,i);

/* if(s1s2)

{

j=s1;

s1=s2;

s2=j;

}*/

}

void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n) // 算法6.12

{

// w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC

int m,i,s1,s2,start;

unsigned c,f;

HuffmanTree p;

char *cd;

if(n=1)

return;

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用

for(p=HT+1,i=1; i=n; ++i,++p,++w)

{

(*p).weight=*w;

(*p).parent=0;

(*p).lchild=0;

(*p).rchild=0;

}

for(; i=m; ++i,++p)

(*p).parent=0;

for(i=n+1; i=m; ++i) // 建赫夫曼树

{

// 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2

select(HT,i-1,s1,s2);

HT[s1].parent=HT[s2].parent=i;

HT[i].rchild=s1;

HT[i].lchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);

}

// 从叶子到根逆向求每个字符的赫夫曼编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));

// 分配n个字符编码的头指针向量([0]不用)

cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间

cd[n-1]='\0'; // 编码结束符

for(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]='1';

else

cd[--start]='0';

HC[i]=(char*)malloc((n-start)*sizeof(char));

// 为第i个字符编码分配空间

strcpy(HC[i],cd); // 从cd复制编码(串)到HC

}

free(cd); // 释放工作空间

}

void swap1(int *a ,int *b)

{

int t;

t=*a;

*a=*b;

*b=t;

}

void swap2(char *a,char *b)

{

char ch;

ch=*a;

*a=*b;

*b=ch;

}

int main(void)

{

HuffmanTree HT;

HuffmanCode HC;

char *s1,*s2;

int i,j=0,n,count,*m,t,flag=1;

scanf("%d",n);

getchar();

s1=(char*)malloc((n+n)*sizeof(char));

s2=(char*)malloc(n*sizeof(char));

memset(s2,'\0',n*sizeof(char));

gets(s1);

count=strlen(s1);

for(i=0; icount; i++)

{

if(!isspace(*(s1+i)))

{

if(function1(*(s1+i),s2))

{

*(s2+j)=*(s1+i);

j++;

}

}

else;

}

m=(int*)malloc(j*sizeof(int));

for(i=0; ij; i++)

*(m+i)=0;

for(t=0; tj; t++)

{

for(i=0; icount; i++)

{

if(*(s2+t)==*(s1+i))

*(m+t)+=1;

}

}

for(i=0;ij;i++)

while(flag)

{

flag = 0;

for (t=0; tj-1; t++)

{

if(*(m+t)*(m+t+1))

{

swap1(m+t,m+t+1);

swap2(s2+t,s2+t+1);

flag=1;

}

}

}

HuffmanCoding(HT,HC,m,j);

for(i=1,t=0; i=j; i++,t++)

{

printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);

}

return 0;

}

C语言哈夫曼数的问题

#include stdlib.h

#include string.h

//////////////////////////////////////////////////////////////////////////////

/*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/

typedef struct{

int weight;

char ch; //增加一个域用于存放该节点的字符

int parent,lchild,rchild;

}HTNode,*HuffmanTree;

typedef char **HuffmanCode; //指向赫夫曼编码的指针

//////////////////////////////////////////////////////////////////////////////

/*本程序用到的函数原型*/

void welcome(); //打印操作选择界面

void HuffmanCoding(HuffmanTree ,char *,int *,int);//建立赫夫曼树的算法

void select(HuffmanTree HT,int j,int *s1,int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点

void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树

void Coding(); //编码

void Decoding(); //译码

void Print_code(); //打印译码好的代码文件

void Print_tree(); //以凹凸表形式打印哈夫曼树

int Read_tree(HuffmanTree ); //从文件中读入赫夫曼树

void find(HuffmanTree HT,char *code,char *text,int i,int m);//译码时根据01字符串寻找相应叶子节点的递归算法

void Convert_tree(unsigned char T[100][100],int s,int *i,int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树

HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间

int n=0; //全局变量，存放赫夫曼树叶子结点的数目

int main()

{

char select;

while(1)

{

welcome();

scanf("%c",select);

switch(select)

{

case 'i':

case 'I':Init();break;

case 'c':

case 'C':Coding();break;

case 'd':

case 'D':Decoding();break;

case 'p':

case 'P':Print_code();break;

case 't':

case 'T':Print_tree();break;

case 'e':

case 'E':exit(1);

default :printf("Input error!\n");

}

getchar();

}

return 0;

}

void welcome() //打印操作选择界面

{

printf("*-----------------------------------------------------*\n");

printf("| What do you want to do? |\n");

printf("|-----------------------------------------------------|\n");

printf("| |\n");

printf("| I--------------------------Init the Huffman tree. |\n");

printf("| C--------------------------Code your file. |\n");

printf("| D--------------------------Decode the code. |\n");

printf("| P--------------------------Print the codefile. |\n");

printf("| T--------------------------Print the Huffman tree. |\n");

printf("| |\n");

printf("*-----------------------------------------------------*\n");

}

//////////////////////////////////////////////////////////////////////////////////////

/*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/

void Init()

{

FILE *fp;

int i,n,w[52]; //w数组存放n个字符的权值

char character[52]; //存放n个字符

printf("\n输入字符个数 n:");

scanf("%d",n); //输入字符集大小

printf("输入%d个字符及其对应的权值:\n",n);

for (i=0;in;i++)

{

char b=getchar();

scanf("%c",character[i]);

scanf("%d",w[i]); //输入n个字符和对应的权值

}

HuffmanCoding(HT,character,w,n); //建立赫夫曼树

if((fp=fopen("hfmtree.txt","w"))==NULL)

printf("Open file hfmtree.txt error!\n");

for (i=1;i=2*n-1;i++)

{

if(fwrite(HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中

printf("File write error!\n");

}

printf("\n建立赫夫曼树成功，已将其存于文件hfmtree.txt中\n");

fclose(fp);

}

///////////////////////////////////////////////////////////////////////////////////

//////建立赫夫曼树的算法///////////////////////////////////////////////////////////

void HuffmanCoding(HuffmanTree HT,char *character,int *w,int n)

{

int m,i,s1,s2;

HuffmanTree p;

if(n=1) return;

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

for(p=HT+1,i=1;i=n;++i,++p,++character,++w)

for(;i=m;++i,++p)

for(i=n+1;i=m;++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;

}

}

///////////////////////////////////////////////////////////////////////////////

/*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/

void select(HuffmanTree HT,int j,int *s1,int *s2)

{

int i;

//找weight最小的结点

for (i=1;i=j;i++)

if (HT[i].parent==0)

for (;i=j;i++)

if ((HT[i].parent==0)(HT[i].weightHT[*s1].weight))

*s1=i;

HT[*s1].parent=1;

//找weight次小的结点

for (i=1;i=j;i++)

if (HT[i].parent==0)

for (;i=j;i++)

if ((HT[i].parent==0)(i!=*s1)(HT[i].weightHT[*s2].weight))

*s2=i;

}

///////////////////////////////////////////////////////////////////////////////

/*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/

void Coding()

{

FILE *fp,*fw;

int i,f,c,start;

char *cd;

HuffmanCode HC;

if(n==0)

n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

/////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中

{

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));

cd=(char *)malloc(n*sizeof(char));

cd[n-1]='\0';

for(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));

strcpy(HC[i],cd);

}

free(cd);

}

/////////////////////////////////////////////////////////////////////////////////////

if((fp=fopen("tobetrans.txt","rb"))==NULL)

printf("Open file tobetrans.txt error!\n");

if((fw=fopen("codefile.txt","wb+"))==NULL)

printf("Open file codefile.txt error!\n");

char temp;

fscanf(fp,"%c",temp); //从文件读入第一个字符

while(!feof(fp))

{

for(i=1;i=n;i++)

if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置

for(int r=0;HC[i][r]!='\0';r++) //将字符对应的编码存入文件

fputc(HC[i][r],fw);

fscanf(fp,"%c",temp); //从文件读入下一个字符

}

fclose(fw);

fclose(fp);

printf("\n对文件hfmtree.txt编码成功,结果已存入codefile.txt中。\n\n");

}

/////////////////////////////////////////////////////////////////////////

/*将文件codefile中的代码进行译码，结果存入文件textfile中*/

void Decoding()

{

FILE *fp,*fw;

int m,i;

char *code,*text,*p;

if(n==0)

n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

if((fp=fopen("codefile.txt","rb"))==NULL)

printf("Open file codefile.txt error!\n");

if((fw=fopen("textfile.txt","wb+"))==NULL)

printf("Open file textfile.txt error!\n");

code=(char *)malloc(sizeof(char));

fscanf(fp,"%c",code); //从文件读入一个字符

for(i=1;!feof(fp);i++)

{

code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空间

fscanf(fp,"%c",code[i]); //从文件读入下一个字符

}

code[i-1]='\0';

/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中

text=(char *)malloc(100*sizeof(char));

p=text;

m=2*n-1;

if(*code=='0')

find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找

else

find(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找

for(i=0;p[i]!='\0';i++) //把译码好的字符存入文件textfile.txt中

fputc(p[i],fw);

fclose(fp);

fclose(fw);

printf("\n对codefile.txt文件译码成功，结果已存入textfile.txt文件。\n\n");

}

//////////////////////////////////////////////////////////////////////////////////////////////////////

/*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/

void Print_code()

{

FILE *fp,*fw;

char temp;

int i;

if((fp=fopen("codefile.txt","rb"))==NULL)

printf("Open file codefile.txt error!\n");

if((fw=fopen("codeprint.txt","wb+"))==NULL)

printf("Open file codeprint.txt error!\n");

printf("\n文件codefi1e以紧凑格式显示如下:\n");

fscanf(fp,"%c",temp); //从文件读入一个字符

for (i=1;!feof(fp);i++)

{

printf("%c",temp);

if(i%50==0) printf("\n");

fputc(temp,fw); //将该字符存入文件codeprint.txt中

fscanf(fp,"%c",temp); //从文件读入一个字符

}

printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n");

fclose(fp);

fclose(fw);

}

//////////////////////////////////////////////////////////////////////////////////////////////////

/*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/

void Print_tree()

{

unsigned char T[100][100];

int i,j,m=0;

FILE *fp;

if(n==0)

n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

Convert_tree(T,0,m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中

if((fp=fopen("treeprint.txt","wb+"))==NULL)

printf("Open file treeprint.txt error!\n");

printf("\n以凹凸表形式打印已建好的赫夫曼树：\n");

for(i=1;i=2*n-1;i++)

{

for (j=0;T[i][j]!=0;j++)

{

if(T[i][j]==' ')

else

}

printf("\n");

}

fclose(fp);

printf("\n此字符形式的哈夫曼树已写入文件treeprint.txt中.\n\n");

}

//////////////////////////////////////////////////////////////////////////////////

/*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/

int Read_tree(HuffmanTree HT)

{

FILE *fp;

int i,n;

HT=(HuffmanTree)malloc(sizeof(HTNode));

if((fp=fopen("hfmtree.txt","r"))==NULL)

printf("Open file hfmtree.txt error!\n");

for (i=1;!feof(fp);i++)

{

HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空间

fread(HT[i],sizeof(HTNode),1,fp); //读入一个节点信息

}

fclose(fp);

n=(i-1)/2;

return n;

}

////////////////////////////////////////////////////////////////

/*译码时根据01字符串寻找相应叶子节点的递归算法*/

void find(HuffmanTree HT,char *code,char *text,int i,int m)

{

if(*code!='\0') //若译码未结束

{

code++;

if(HT[i].lchild==0HT[i].rchild==0) //若找到叶子节点

{

*text=HT[i].ch; //将叶子节点的字符存入text中

text++;

if((*code=='0'))

find(HT,code,text,HT[m].lchild,m); //继续从根节点的左子树找

else

find(HT,code,text,HT[m].rchild,m); //继续从根节点的右子树找

}

else //如果不是叶子节点

if(*code=='0')

find(HT,code,text,HT[i].lchild,m); //从该节点的左子树去找

else

find(HT,code,text,HT[i].rchild,m); //从该节点的右子树去找

}

else

*text='\0'; //译码结束

}

////////////////////////////////////////////////////////////////////////

/*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/

void Convert_tree(unsigned char T[100][100],int s,int *i,int j)

{

int k,l;

l=++(*i);

for(k=0;ks;k++)

T[l][k]=' ';

T[l][k]=HT[j].weight;

if(HT[j].lchild)

Convert_tree(T,s+1,i,HT[j].lchild);

if(HT[j].rchild)

Convert_tree(T,s+1,i,HT[j].rchild);

T[l][++k]='\0';

}

为了您的安全，请只打开来源可靠的网址

打开网站 取消

来自:

另外,团IDC网上有许多产品团购,便宜有口碑

有人可以帮我注释一段关于用c语言实现哈夫曼树的代码吗？

在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如

JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点

的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。

树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)  ，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。 可以证明哈夫曼树的WPL是最小的。

哈夫曼编码步骤：

一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）

二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

四、重复二和三两步，直到集合F中只有一棵二叉树为止。

简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：

请点击输入图片描述

虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图：

请点击输入图片描述

再依次建立哈夫曼树，如下图：

请点击输入图片描述

其中各个权值替换对应的字符即为下图：

请点击输入图片描述

所以各字符对应的编码为：A-11,B-10,C-00,D-011,E-010

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。

C语言代码实现：

/*-------------------------------------------------------------------------

* Name:   哈夫曼编码源代码。

* Date:   2011.04.16

* Author: Jeffrey Hill+Jezze(解码部分)

* 在 Win-TC 下测试通过

* 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中

*           自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在

*           父结点左侧，则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。

*------------------------------------------------------------------------*/

#include stdio.h

#includestdlib.h

#define MAXBIT      100

#define MAXVALUE  10000

#define MAXLEAF     30

#define MAXNODE    MAXLEAF*2 -1

typedef struct

{

int bit[MAXBIT];

int start;

} HCodeType;        /* 编码结构体 */

typedef struct

{

int weight;

int parent;

int lchild;

int rchild;

int value;

} HNodeType;        /* 结点结构体 */

/* 构造一颗哈夫曼树 */

void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)

{

/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，

x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/

int i, j, m1, m2, x1, x2;

/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */

for (i=0; i2*n-1; i++)

{

HuffNode[i].weight = 0;//权值

HuffNode[i].parent =-1;

HuffNode[i].lchild =-1;

HuffNode[i].rchild =-1;

HuffNode[i].value=i; //实际值，可根据情况替换为字母

} /* end for */

/* 输入 n 个叶子结点的权值 */

for (i=0; in; i++)

{

printf ("Please input weight of leaf node %d: \n", i);

scanf ("%d", HuffNode[i].weight);

} /* end for */

/* 循环构造 Huffman 树 */

for (i=0; in-1; i++)

{

m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */

x1=x2=0;

/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */

for (j=0; jn+i; j++)

{

if (HuffNode[j].weight m1 HuffNode[j].parent==-1)

{

m2=m1;

x2=x1;

m1=HuffNode[j].weight;

x1=j;

}

else if (HuffNode[j].weight m2 HuffNode[j].parent==-1)

{

m2=HuffNode[j].weight;

x2=j;

}

} /* end for */

/* 设置找到的两个子结点 x1、x2 的父结点信息 */

HuffNode[x1].parent  = n+i;

HuffNode[x2].parent  = n+i;

HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;

HuffNode[n+i].lchild = x1;

HuffNode[n+i].rchild = x2;

printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */

printf ("\n");

} /* end for */

/*  for(i=0;in+2;i++)

{

printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);

}*///测试

} /* end HuffmanTree */

//解码

void decodeing(char string[],HNodeType Buf[],int Num)

{

int i,tmp=0,code[1024];

int m=2*Num-1;

char *nump;

char num[1024];

for(i=0;istrlen(string);i++)

{

if(string[i]=='0')

num[i]=0;

else

num[i]=1;

}

i=0;

nump=num[0];

while(nump(num[strlen(string)]))

{tmp=m-1;

while((Buf[tmp].lchild!=-1)(Buf[tmp].rchild!=-1))

{

if(*nump==0)

{

tmp=Buf[tmp].lchild ;

}

else tmp=Buf[tmp].rchild;

nump++;

}

printf("%d",Buf[tmp].value);

}

}

int main(void)

{

HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */

HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */

int i, j, c, p, n;

char pp[100];

printf ("Please input n:\n");

scanf ("%d", n);

HuffmanTree (HuffNode, n);

for (i=0; i n; i++)

{

cd.start = n-1;

c = i;

p = HuffNode[c].parent;

while (p != -1)   /* 父结点存在 */

{

if (HuffNode[p].lchild == c)

cd.bit[cd.start] = 0;

else

cd.bit[cd.start] = 1;

cd.start--;        /* 求编码的低一位 */

c=p;

p=HuffNode[c].parent;    /* 设置下一循环条件 */

} /* end while */

/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */

for (j=cd.start+1; jn; j++)

{ HuffCode[i].bit[j] = cd.bit[j];}

HuffCode[i].start = cd.start;

} /* end for */

/* 输出已保存好的所有存在编码的哈夫曼编码 */

for (i=0; in; i++)

{

printf ("%d 's Huffman code is: ", i);

for (j=HuffCode[i].start+1; j n; j++)

{

printf ("%d", HuffCode[i].bit[j]);

}

printf(" start:%d",HuffCode[i].start);

printf ("\n");

}

/*    for(i=0;in;i++){

for(j=0;jn;j++)

{

printf ("%d", HuffCode[i].bit[j]);

}

printf("\n");

}*/

printf("Decoding?Please Enter code:\n");

scanf("%s",pp);

decodeing(pp,HuffNode,n);

getch();

return 0;

}

C语言编写哈夫曼树

// huffman.cpp : Defines the entry point for the console application.

//

#include iostream.h

#include stdio.h

#include string.h

const long wordnum = 1000;//最大不同单词数

const long code_len = wordnum/10;

const long wordlen = 30;//单词最长长度

const long codemax = 10000;//最大haffuman编码长度

const long wordmax = 10000;//最大单词数

//str类定义

class str

{

public:

str();

bool operator(str obj);//运算符重载方便对strc语言哈夫曼函数的排序使用二分搜索模板

bool operator(str obj);

str operator=(char p[]);

str operator++(int);//重载后缀方式的＋＋

char *getword();

long getfre();

protected:

private:

char word[wordlen];

long frequence;

};

str::str()

{

frequence = 0;

}

//以下为重载str类中的运算符

bool str::operator(str obj)

{

if(strcmp(word,obj.word) 0)

return true;

else

return false;

}

bool str::operator(str obj)

{

if(strcmp(word,obj.word) 0)

return true;

else

return false;

}

str str::operator=(char p[])

{

strcpy(word,p);

return *this;

}

str str::operator++(int x)

{

frequence ++;

return *this;

}

char * str::getword()

{

return word;

}

long str::getfre()

{

return frequence;

}

//str类定义结束

//Node类定义

class Node

{

public:

Node();

bool operator(Node obj);//运算符重载方便对Node的排序使用堆模板

bool operator=(Node obj);

bool operator(Node obj);

Node operator=(str obj);

Node operator+(Node obj);

Node *leftp();//类外获取指向当前节点的孩子的指针

Node *rightp();

char *getword(Node *p);//类外获取节点信息

long getfrequence();

protected:

private:

char word[wordlen];

long frequence;

Node *left, *right;

};

Node::Node()

{

strcpy(word,"NULL");

left = NULL;

right = NULL;

}

//以下为重载Node类中的运算符

bool Node::operator(Node obj)

{

if(frequence obj.frequence)

return true;

else

return false;

}

bool Node::operator=(Node obj)

{

if(frequence = obj.frequence)

return true;

else

return false;

}

bool Node::operator(Node obj)

{

if(frequence obj.frequence)

return true;

else

return false;

}

Node Node::operator+(Node obj)

{

Node sum;

sum.frequence = frequence + obj.frequence;//指针指向c语言哈夫曼函数了NULL

sum.left = this;

sum.right = obj;

return sum;

}

Node Node::operator=(str obj)

{

strcpy(word,obj.getword());

frequence = obj.getfre();

return *this;

}

Node * Node::leftp()

{

return left;

}

Node * Node::rightp()

{

return right;

}

char * Node::getword(Node *p)

{

return p-word;

}

long Node::getfrequence()

{

return frequence;

}

//Node类定义结束

//str类专门用于统计词频使用c语言哈夫曼函数，Node则用于构造huffman树c语言哈夫曼函数，由于两者使用的key不同，前者是word的字典序

//后者是词频，于是使用了两个类来实现。

class huffman

{

public:

huffman();

templatetypename entry

friend bool binarysearch(entry list[wordnum],entry target,long bottom,long top,long position);

templatetypename entry

friend void buidheap(entry a[wordnum], long number);

templatetypename entry

friend void heapify(entry a[wordnum], long high, long low);

templatetypename entry

friend void swap(entry a[wordnum], long i, long j);

bool Stat();

void Encode();

bool Decode(char code[]);

Node update(long end);

void produce_code();

void Inorder(Node *current, char currentcode[], long num);

protected:

private:

Node SortedNode[wordnum];//从中产生huffman树

char NodeCode[wordnum][wordnum/10];//相应编码

Node root;

bool sign;//用于标记是否已经建立了huffman树

long n;//叶子节点个数

};

huffman::huffman()

{

sign = false;

}

//二分用于统计词频

templatetypename entry

bool binarysearch(entry list[wordnum], entry target, long bottom, long top, long position)

{

while(bottom = top)

{

position = (bottom + top)/2;

if(list[position] target)

bottom = position + 1;

else if(list[position] target)

top = position - 1;

else

return true;

}

return false;

}

//建立最小堆及调整为最小堆

templatetypename entry

void swap(entry a[wordnum], long i, long j)

{

entry s;

s = a[i];

a[i] = a[j];

a[j] = s;

}

templatetypename entry

void buidheap(entry a[wordnum], long number)

{

long i ,j;

for(i = number/2; i = 1; i--)

{

j = i;

while(j = number/2)

{

if(a[j] a[2*j] || (a[j] a[2*j + 1] 2*j + 1 = number))

{

if(a[2*j] a[2*j + 1] 2*j + 1 = number)

{

swap(a, j, 2*j+1);

j = 2*j + 1;

}

else

{

swap(a, j ,2*j);

j = 2*j;

}

}

else

break;

}

}

}

templatetypename entry

void heapify(entry a[wordnum], long high, long low)

{

long j = low;

while(j = high/2)

{

if(a[j] a[2*j] a[j] a[2*j + 1])

{

if(a[2*j] a[2*j + 1] 2*j + 1 = high)

{

swap(a, j, 2*j+1);

j = 2*j + 1;

}

else if(2*j = high)

{

swap(a, j, 2*j);

j = 2*j;

}

}

else if(a[j] = a[2*j] a[j] a[2*j + 1] 2*j + 1 = high)

{

swap(a, j, 2*j+1);

j = 2*j + 1;

}

else if(a[j] = a[2*j + 1] a[j] a[2*j] 2*j = high)

{

swap(a, j, 2*j);

j = 2*j;

}

else

break;

}

}

//词频统计函数Stat()

bool huffman::Stat()

{

long i,position;

char p[wordmax],*get;

str s[wordnum],current;

n = 0;

while(gets(p) != NULL strcmp(p,"@") != 0)

{

get = strtok(p," ,.!/-:;?");

while(get != NULL)

{

current = get;

if(binarysearch(s,current,0,n,position) == true n wordnum - 1)

s[position] ++;

else

{

n ++;

if(n wordnum - 1)

{

if(s[position] current current.getfre() s[position].getfre())

position ++;

for(i = n; i = position; i --)

s[i+1] = s[i];

s[position] = current;

s[position] ++;

}

}

get = strtok(NULL," ,.!/-:;?");

}

}

for(i = 1; i = n i wordnum; i ++)

SortedNode[i] = s[i-1];

if(n wordnum)

return true;

else

{

n = wordnum - 1;

return false;

}

}

//建立huffman树函数

void huffman::Encode()

{

int i;

sign = true;

buidheap(SortedNode,n);

for(i = 1; i n; i ++)

root = update(n-i+1);

}

Node huffman::update(long end)

{

Node *p,*q;

Node newNode;

p = new Node;

q = new Node;

*p = SortedNode[1];

swap(SortedNode,1,end);

heapify(SortedNode,end-1,1);//取出了一个最小元，然后将堆进行了调整

*q = SortedNode[1];

newNode = *p + *q;

SortedNode[1] = newNode;

heapify(SortedNode,end-1,1);//又取出最小元，并且把新节点赋为SortedNode[1]，调整了堆

return SortedNode[1];

}

//解码函数

bool huffman::Decode(char code[codemax])

{

int i;

Node *find = root;

Node *l = NULL,*r = NULL;

bool flag = true;

if(sign == true)

{

for(i = 0; code[i] != '\0' flag == true; i ++)

{

l = find-leftp();

r = find-rightp();

if(code[i] == '0' l != NULL)

find = l;

else if(code[i] == '1' r != NULL)

find = r;

else flag = false;

if(find-leftp() == NULL find-rightp() == NULL)

{

printf("%s ",find-getword(find));

find = root;

}

}

if(!((find-leftp() == NULL find-rightp() == NULL) || find == root))

{

cout "There are some wrong codes in th input!" endl;

flag = false;

}

}

else

flag = false;

return flag;

}

void huffman::Inorder(Node *current, char currentcode[], long num)

{

Node *l, *r;

char cl[code_len], cr[code_len];

if(current != NULL)

{

l = current-leftp();

r = current-rightp();

strcpy(cl,currentcode);

strcat(cl,"0");

strcpy(cr,currentcode);

strcat(cr,"1");

Inorder(l, cl, num);

if(l == NULL r == NULL)

{

SortedNode[num] = *current;

strcpy(NodeCode[num],currentcode);

num ++;

}

Inorder(r, cr, num);

}

}

void huffman::produce_code()//利用中序遍历来得到相应的编码

{

char current[code_len] = "";

long num = 1;

Inorder(root, current,num);

for(long i = 1; i = n; i ++)

{

cout SortedNode[i].getword(SortedNode[i]) "----" NodeCode[i]" " ;

if(i%3 == 0) cout endl;

}

}

int main()

{

huffman test;

char code[codemax];

char order;

cout "显示编码(Show)" " " "解码(Decode)" " " "退出(Quit)" endl;

cout "Input the passage, to end with a single @ in a single line:" endl;

test.Stat();

test.Encode();

cout "Encoded!" endl;

while(cin order)

{

if(order == 's' || order == 'S')

{

test.produce_code();

cout "Produced!" endl;

}

else if(order == 'd' || order == 'D')

{

cout "Input the codes:" endl;

cin code;

while(test.Decode(code))

cin code;

}

else if(order == 'q' || order == 'Q')

break;

}

return 0;

}

求哈夫曼编译器 C语言代码

// huffman.cpp : Defines the entry point for the console application.

//

#include iostream.h

#include stdio.h

#include string.h

const long wordnum = 1000;//最大不同单词数

const long code_len = wordnum/10;

const long wordlen = 30;//单词最长长度

const long codemax = 10000;//最大haffuman编码长度

const long wordmax = 10000;//最大单词数

//str类定义

class str

{

public:

str();

bool operator(str obj);//运算符重载方便对str的排序使用二分搜索模板

bool operator(str obj);

str operator=(char p[]);

str operator++(int);//重载后缀方式的＋＋

char *getword();

long getfre();

protected:

private:

char word[wordlen];

long frequence;

};

str::str()

{

frequence = 0;

}

//以下为重载str类中的运算符

bool str::operator(str obj)

{

if(strcmp(word,obj.word) 0)

return true;

else

return false;

}

bool str::operator(str obj)

{

if(strcmp(word,obj.word) 0)

return true;

else

return false;

}

str str::operator=(char p[])

{

strcpy(word,p);

return *this;

}

str str::operator++(int x)

{

frequence ++;

return *this;

}

char * str::getword()

{

return word;

}

long str::getfre()

{

return frequence;

}

//str类定义结束

//Node类定义

class Node

{

public:

Node();

bool operator(Node obj);//运算符重载方便对Node的排序使用堆模板

bool operator=(Node obj);

bool operator(Node obj);

Node operator=(str obj);

Node operator+(Node obj);

Node *leftp();//类外获取指向当前节点的孩子的指针

Node *rightp();

char *getword(Node *p);//类外获取节点信息

long getfrequence();

protected:

private:

char word[wordlen];

long frequence;

Node *left, *right;

};

Node::Node()

{

strcpy(word,"NULL");

left = NULL;

right = NULL;

}

//以下为重载Node类中的运算符

bool Node::operator(Node obj)

{

if(frequence obj.frequence)

return true;

else

return false;

}

bool Node::operator=(Node obj)

{

if(frequence = obj.frequence)

return true;

else

return false;

}

bool Node::operator(Node obj)

{

if(frequence obj.frequence)

return true;

else

return false;

}

Node Node::operator+(Node obj)

{

Node sum;

sum.frequence = frequence + obj.frequence;//指针指向了NULL

sum.left = this;

sum.right = obj;

return sum;

}

Node Node::operator=(str obj)

{

strcpy(word,obj.getword());

frequence = obj.getfre();

return *this;

}

Node * Node::leftp()

{

return left;

}

Node * Node::rightp()

{

return right;

}

char * Node::getword(Node *p)

{

return p-word;

}

long Node::getfrequence()

{

return frequence;

}

//Node类定义结束

//str类专门用于统计词频使用，Node则用于构造huffman树，由于两者使用的key不同，前者是word的字典序

//后者是词频，于是使用了两个类来实现。

class huffman

{

public:

huffman();

templatetypename entry

friend bool binarysearch(entry list[wordnum],entry target,long bottom,long top,long position);

templatetypename entry

friend void buidheap(entry a[wordnum], long number);

templatetypename entry

friend void heapify(entry a[wordnum], long high, long low);

templatetypename entry

friend void swap(entry a[wordnum], long i, long j);

bool Stat();

void Encode();

bool Decode(char code[]);

Node update(long end);

void produce_code();

void Inorder(Node *current, char currentcode[], long num);

protected:

private:

Node SortedNode[wordnum];//从中产生huffman树

char NodeCode[wordnum][wordnum/10];//相应编码

Node root;

bool sign;//用于标记是否已经建立了huffman树

long n;//叶子节点个数

};

huffman::huffman()

{

sign = false;

}

//二分用于统计词频

templatetypename entry

bool binarysearch(entry list[wordnum], entry target, long bottom, long top, long position)

{

while(bottom = top)

{

position = (bottom + top)/2;

if(list[position] target)

bottom = position + 1;

else if(list[position] target)

top = position - 1;

else

return true;

}

return false;

}

//建立最小堆及调整为最小堆

templatetypename entry

void swap(entry a[wordnum], long i, long j)

{

entry s;

s = a[i];

a[i] = a[j];

a[j] = s;

}

templatetypename entry

void buidheap(entry a[wordnum], long number)

{

long i ,j;

for(i = number/2; i = 1; i--)

{

j = i;

while(j = number/2)

{

if(a[j] a[2*j] || (a[j] a[2*j + 1] 2*j + 1 = number))

{

if(a[2*j] a[2*j + 1] 2*j + 1 = number)

{

swap(a, j, 2*j+1);

j = 2*j + 1;

}

else

{

swap(a, j ,2*j);

j = 2*j;

}

}

else

break;

}

}

}

templatetypename entry

void heapify(entry a[wordnum], long high, long low)

{

long j = low;

while(j = high/2)

{

if(a[j] a[2*j] a[j] a[2*j + 1])

{

if(a[2*j] a[2*j + 1] 2*j + 1 = high)

{

swap(a, j, 2*j+1);

j = 2*j + 1;

}

else if(2*j = high)

{

swap(a, j, 2*j);

j = 2*j;

}

}

else if(a[j] = a[2*j] a[j] a[2*j + 1] 2*j + 1 = high)

{

swap(a, j, 2*j+1);

j = 2*j + 1;

}

else if(a[j] = a[2*j + 1] a[j] a[2*j] 2*j = high)

{

swap(a, j, 2*j);

j = 2*j;

}

else

break;

}

}

//词频统计函数Stat()

bool huffman::Stat()

{

long i,position;

char p[wordmax],*get;

str s[wordnum],current;

n = 0;

while(gets(p) != NULL strcmp(p,"@") != 0)

{

get = strtok(p," ,.!/-:;?");

while(get != NULL)

{

current = get;

if(binarysearch(s,current,0,n,position) == true n wordnum - 1)

s[position] ++;

else

{

n ++;

if(n wordnum - 1)

{

if(s[position] current current.getfre() s[position].getfre())

position ++;

for(i = n; i = position; i --)

s[i+1] = s[i];

s[position] = current;

s[position] ++;

}

}

get = strtok(NULL," ,.!/-:;?");

}

}

for(i = 1; i = n i wordnum; i ++)

SortedNode[i] = s[i-1];

if(n wordnum)

return true;

else

{

n = wordnum - 1;

return false;

}

}

//建立huffman树函数

void huffman::Encode()

{

int i;

sign = true;

buidheap(SortedNode,n);

for(i = 1; i n; i ++)

root = update(n-i+1);

}

Node huffman::update(long end)

{

Node *p,*q;

Node newNode;

p = new Node;

q = new Node;

*p = SortedNode[1];

swap(SortedNode,1,end);

heapify(SortedNode,end-1,1);//取出了一个最小元，然后将堆进行了调整

*q = SortedNode[1];

newNode = *p + *q;

SortedNode[1] = newNode;

heapify(SortedNode,end-1,1);//又取出最小元，并且把新节点赋为SortedNode[1]，调整了堆

return SortedNode[1];

}

//解码函数

bool huffman::Decode(char code[codemax])

{

int i;

Node *find = root;

Node *l = NULL,*r = NULL;

bool flag = true;

if(sign == true)

{

for(i = 0; code[i] != '\0' flag == true; i ++)

{

l = find-leftp();

r = find-rightp();

if(code[i] == '0' l != NULL)

find = l;

else if(code[i] == '1' r != NULL)

find = r;

else flag = false;

if(find-leftp() == NULL find-rightp() == NULL)

{

printf("%s ",find-getword(find));

find = root;

}

}

if(!((find-leftp() == NULL find-rightp() == NULL) || find == root))

{

cout "There are some wrong codes in th input!" endl;

flag = false;

}

}

else

flag = false;

return flag;

}

void huffman::Inorder(Node *current, char currentcode[], long num)

{

Node *l, *r;

char cl[code_len], cr[code_len];

if(current != NULL)

{

l = current-leftp();

r = current-rightp();

strcpy(cl,currentcode);

strcat(cl,"0");

strcpy(cr,currentcode);

strcat(cr,"1");

Inorder(l, cl, num);

if(l == NULL r == NULL)

{

SortedNode[num] = *current;

strcpy(NodeCode[num],currentcode);

num ++;

}

Inorder(r, cr, num);

}

}

void huffman::produce_code()//利用中序遍历来得到相应的编码

{

char current[code_len] = "";

long num = 1;

Inorder(root, current,num);

for(long i = 1; i = n; i ++)

{

cout SortedNode[i].getword(SortedNode[i]) "----" NodeCode[i]" " ;

if(i%3 == 0) cout endl;

}

}

int main()

{

huffman test;

char code[codemax];

char order;

cout "显示编码(Show)" " " "解码(Decode)" " " "退出(Quit)" endl;

cout "Input the passage, to end with a single @ in a single line:" endl;

test.Stat();

test.Encode();

cout "Encoded!" endl;

while(cin order)

{

if(order == 's' || order == 'S')

{

test.produce_code();

cout "Produced!" endl;

}

else if(order == 'd' || order == 'D')

{

cout "Input the codes:" endl;

cin code;

while(test.Decode(code))

cin code;

}

else if(order == 'q' || order == 'Q')

break;

}

return 0;

}

关于c语言哈夫曼函数和哈夫曼树及哈夫曼编码的算法实现c语言的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。