#includestdio.h
#includestring.h
#includestdlib.h
#includectype.h
int n;
struct node{
int w;
int flag;
char c;
struct node *plink,*llink,*rlink;
}*num[100],*root;
FILE *fp;
int t=0;
void main(void)
{
int i;
void settree(void); //建立树
void code(void); //对文件编码
void decode(void); // 译码
void disp(void);
root=(struct node*)malloc(sizeof(struct node));
puts("*******************哈夫曼编/译码器演示******************************");
while(1){
start:
while(scanf("%d",i)!=1)
while(getchar()!='\n')
continue;
puts("输入错误!");
puts("请重新输入！");
}
switch (i)
case 1:
settree();
break;
code();
decode();
disp();
exit(0);
default:
puts("输入错误！");
goto start;
void settree(void)
int i,j,k;
void go(struct node *);
void setcode(struct node *);//建立每一个字符的编码
void printtree(struct node *);
puts("输入字符集的大小：");
scanf("%d",n);
for(i=0;in;i++)
p=(struct node *)malloc(sizeof(struct node));
puts("请输入一个字符");
scanf("%c",p-c);
puts("请输入该字符的权值:");
scanf("%d",p-w);
p-plink=NULL;
p-rlink=NULL;
p-llink=NULL;
num[i]=p;
for(i=0;in-1;i++) //（递增）排序
for(j=i+1;jn;j++)
if(num[i]-wnum[j]-w)
tmp=num[i];
num[i]=num[j];
num[j]=tmp;
/*******************************开始建立树***********************/
num[n]=NULL; //结束标志
k=n;
while(num[1]!=NULL)
p1=num[0];
p-llink=p1;
p1-plink=p;
for(i=1;ik;i++)
num[i]=num[i+1];
k--;
num[0]=p;
for(i=0;ik-1;i++) //排序
for(j=i+1;jk;j++)
root=num[0];
/*建立完毕*/
/*写入文件,前序*/
if((fp=fopen("c:\\hfmtree.wxl","wb"))==NULL)
puts("文件打开错误！");
getchar();
setcode(root);
go(root);
fclose(fp);
void setcode(struct node *p)
if(p-llink==NULLp-rlink==NULL)
tmpcode[t]='\0';
strcpy(p-code,tmpcode);
else
tmpcode[t++]='0';
setcode(p-llink);
t--;
tmpcode[t++]='1';
setcode(p-rlink);
void go(struct node *p)
fputc('(',fp);
fputc(p-c,fp);
fputs(p-code,fp);
fputc(')',fp);
go(p-llink);
go(p-rlink);
void code(void)
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
t=0;
while((c=fgetc(fp1))!=')')
tmpcode[t++]=c;
rewind(fp1);
fclose(fp1);
void decode(void)
while((ch1=fgetc(fp1))!=EOF)
if(isalpha(ch1))
t1=0;
while((ch1=fgetc(fp1))!=')')
temp_1[t1++]=ch1;
temp_1[t1]='\0';
void disp(void)
int t;
if(ch1=='(')
ch1=fgetc(fp1);
tmp[t++]=ch1;
tmp[t]='\0';
这是以前写的,可是我不想加注释了,Huffman编码其实原理很简单的,你自己好好学下吧,一句一句注释也太夸张了啊.
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;
void Select(HuffmanTree HT,int n)
int i,j;
for(i=1;i=n;i++)
if(HT[i].parent==0)
{s1=i;
for(j=i+1;j=n;j++)
if(HT[j].parent==0)
if(HT[s1].weightHT[i].weight)
s1=i;
for(j=1;j=n;j++)
if(s1!=j)
int temp=s1;
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n)
char *cd;
int p;
int cdlen;
if (n=1) return;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
for (i=1; i=n; i++)
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
for (i=n+1; i=m; i++)
HT[i].weight=0;
//添加查看,便于调试
printf("构造过程显示：\n");
for(i=1;i=m;i++)
system("pause");
for(i=n+1;i=m;i++)
Select(HT,i-1);
for(j=1;j=i;j++)
*/
cd = (char *)malloc(n*sizeof(char));
p=m;
cdlen=0;
while(p)
if(HT[p].weight==0)
HT[p].weight=1;
if(HT[p].lchild!=0)
p=HT[p].lchild;
cd[cdlen++]='0';
else if(HT[p].rchild==0)
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd);
else if(HT[p].weight==1)
if(HT[p].rchild!=0)
p=HT[p].rchild;
cd[cdlen++]='1';
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
int main()
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入节点数：\n");
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("请输入节点的权值：\n");
scanf("%d",w[i]);
HuffmanCoding(HT,HC,w,n);
printf("输出编码：\n");
return 0;
#define MAXVALUE 1000//定义最大权值
#define MAXBIT 100//定义哈夫曼树中叶子结点个数
typedef struct
char data;//字符值
int num;//某个值的字符出现的次数
}TotalNode;
//统计结点,包括字符种类和出现次数
int num;//统计数组中含有的字符个数
}Total;
//统计结构体,包括统计数组和字符种类数
int num;//总字符数
}Message;
//信息结构体,包括字符数组和总字符数
typedef struct{
int num;//密码总数
}Locking;
//哈夫曼编码后的密文信息
char data;//字符
int weight;//权值
int parent;//双亲结点在数组HuffNode[]中的序号
int lchild;//左孩子结点在数组HuffNode[]中的序号
int rchild;//右孩子结点在数组HuffNode[]中的序号
}HNodetype;
//哈夫曼树结点类型,包括左右孩子,权值和信息
int bit[MAXBIT];
int start;
}HCodetype;
//哈夫曼编码结构体,包括编码数组和起始位
void reading_file(Message *message);//从文件中读取信息
int writing_file(Message *message);//将信息写进文件
void total_message(Message *message,Total *total);//统计信息中各字符的次数
void HaffmanTree(Total *total,HNodetype HuffNode[]);//构建哈夫曼树
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼编码
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//将编码规则写进文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//给文件信息加密编码
void writing_lock(Locking *locking);//将已编码信息写进文件
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//将已编码信息翻译过来并写进文
#include"Node_statement.h"
#includeiostream
#includefstream
#include "cstdlib"
using namespace std;
int i,j,choice,mark=0;//mark标记文件信息是否读入到内存中
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking-num=0;
total=new Total;
total-num=0;
message=new Message;
message-num=0;
//初始化变量
printf("┏ ┓\n");
printf("┣ haffman_code system ┫ \n");
printf("┗ ┛\n");
printf("\n\n");
choice=0;
printf("＃〓+〓〓〓〓〓+〓〓〓〓+〓〓〓〓+〓＃ \n ");
printf(" 0:go \n");
printf("※********** 1：从文件读取信息**********************※\n");
printf(" please input the choice ");
cinchoice;
switch(choice)
reading_file(message);//从文件中读取信息
mark=1;
if(mark==0)cout"请先从文件中读取信息!"endl;
first_function(HuffNode,HuffCode,total,message);
cout"编码规则为"endl;
for(i=0;itotal-num;i++)//显示编码规则
couttotal-tot[i].data" ";
for(j=HuffCode[i].start+1;jtotal-num;j++)
coutHuffCode[i].bit[j];
coutendl;
writing_file(message);//将信息写进文件
writing_HCode(HuffNode,HuffCode,total);//将编码规则写进文件
writing_lock(locking);//将已编码信息写进文件
writing_translate(locking,HuffCode,HuffNode,total);//将已编码信息翻译过来并写进文件
/**
打印haffman树
**/
system("PAUSE");
printf("data weight lchild rchild parent \n");
printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent);
void reading_file(Message *message)
绝对路径下读取a_test.txt file
message 中的num记录suoyou字符总数 ,放在nes【】中
equal to the buffer
int i=0;
char ch;
ifstream infile("a_test.txt",ios::in | ios::out);
if(!infile)//打开失败则结束
cout"打开a_test.txt文件失败"endl;
exit(1);
cout"读取文件成功"endl;
while(infile.get(ch) ch!='#')//读取字符直到遇到#
message-mes[i]=ch;
i++;
message-num=i;//记录总字符数
infile.close();//关闭文件
int writing_file(Message *message)
把从数组message 的信息write to disk,a_test1.txt to save
{ /*
ifstream outfile("a_test1.txt",ios::in ); //打开文件
if( !outfile )//打开失败则结束
cout"打开a_test1.txt文件失败"endl;
return -1;
for(i=0;imessage-num;i++)//写文件
outfile.put(message-mes[i]);
cout"信息写进文件成功"endl;
outfile.close();//关闭文件
return 0;*/
FILE *fp1=NULL;
if((fp1 = fopen("a_test1.txt","at"))==NULL)
printf("can't open the file\n");
for(i=0;imessage-num;i++)
fprintf(fp1,"%d ",message-mes[i]);
printf("文件写入成功!\n");
i=fclose(fp1);
if(i==0)
printf("文件关闭成功!\n");
printf("文件关闭失败!\n");
void total_message(Message *message,Total *total)
统计message中不同字符 的个数,和相同字符重复的次数,重复字符用mark标记,
total.tot[] 放不同字符,TotalNode 类型（char,num）
total.num 统计不同字符个数
使total这块内存空间有数据,
int i,j,mark;
for(i=0;imessage-num;i++)//遍历message中的所有字符信息
if(message-mes[i]!=' ')//字符不为空格时
mark=0;
for(j=0;jtotal-num;j++)//在total中搜索当前字符
if(total-tot[j].data==message-mes[i])//搜索到,则此字符次数加1,mark标志为1
total-tot[j].num++;
if(mark==0)//未搜索到,新建字符种类,保存进total中,字符类加1
total-tot[total-num].data=message-mes[i];
total-tot[total-num].num=1;
total-num++;
void HaffmanTree(Total *total,HNodetype HuffNode[])
/**create the haffman tree
不同字符个数为叶子节点个数对应书上的n,
相同字符的个数为其权值weight；
get HuffNode to store the tree
if(i=total-num-1)
HuffNode[i].data=total-tot[i].data;
HuffNode[i].weight=total-tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
for(i=0;itotal-num-1;i++)
if(HuffNode[j].parent==-1HuffNode[j].weightmin1)
min1=HuffNode[j].weight;
x1=j;
HuffNode[x1].parent=total-num+i;//修改亲人结点位置
HuffNode[total-num+i].lchild=x1;//左孩子比右孩子权值小
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/***
haffman to code (0,10,110,)
得到每个不同字符（叶子）的编码,
存贮在数组HuffCode【】中,bit[] store the char,start store the loction
int i,j,c,p;
HCodetype cd;
for(i=0;itotal-num;i++)//建立叶子结点个数的编码
cd.start=total-num-1;//起始位初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//从叶结点向上爬直到到达根结点
if(HuffNode[p].lchild==c)//左分支则为0
cd.bit[cd.start]=0;
cd.bit[cd.start]=1;//右分支则为1
cd.start--;//起始位向前移动
c=p;
p=HuffNode[p].parent;
for(j=cd.start+1;jtotal-num;j++)//保存求出的每个叶结点编码和起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
HuffNode[]to input the leaf
HuffCode[]to input the code
/*打开HCode文件,失败则结束.将信息写进文件*/
for(i=0;itotal-num;i++)
printf(" ");
printf("编码规则写进文件成功!\n");
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)
对messag操作,对所有字符加密,
结果存贮在数组locked[]中,locking 记录已经加密后的密文
int i,j,m;
for(i=0;imessage-num;i++)//把相同的不同的字符全部 遍历
if(message-mes[i]==' ')//碰到空格则以-1形式保存进locked数组中
locking-locked[locking-num]=-1;
locking-num++;
for(j=0;jtotal-num;j++)//从total中找到对应的字符
if(HuffNode[j].data==message-mes[i])
//找到在HuffNode 中对应字符,找到下标j
// 在HuffCode
for(m=HuffCode[j].start+1;mtotal-num;m++)///////// !
locking-locked[locking-num]=HuffCode[j].bit[m];//加密
void writing_lock(Locking *locking)
/*
for(i=0;ilocking-num;i++)
if(locking-locked[i]==-1)
printf("已编码信息写进文件成功!\n");
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
int i,j,mark[100],start[100],min,max;
for(i=0;itotal-num;i++)//start数组初始化
start[i]=HuffCode[i].start+1;//....
for(i=0;itotal-num;i++)//mark数组初始化
mark[i]=1;
min=0;
for(max=0;maxlocking-num;max++)//写文件
if(locking-locked[max]==-1)//碰到空格信息则直接输出空格
printf(" ");//把空格写到文件
min++;
for(i=min;i=max;i++)//查找从min开始到max的编码对应的信息
for(j=0;jtotal-num;j++)
if(start[j] == total-num+1)
mark[j]=0; //对应编码比所给编码短则不在比较
if(mark[j]==1locking-locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
mark[j]=0;
for(i=0;itotal-num;i++)//找到对应信息,则写进文件
if(mark[i]==1start[i]==total-num)
if(i!=total-num)
min=max+1;
start[i]=HuffCode[i].start+1;
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message)
total_message(message,total);//统计信息中各字符的出现次数
HaffmanTree(total,HuffNode);//构建哈夫曼树
HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼编码
这边什么是deflate?
①.）func NewReader(r io.Reader) io.ReadCloser
①.0）func (w *Writer) Write(data []byte) (n int, err error)
非常好的一个资源链接：
如果有很好的资源,欢迎在评论区留言分享
以上就是土嘎嘎小编为大家整理的go语言实现哈夫曼编码相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！