yi.cpp

huffman 编码,能过该程序,你可以轻松的进行哈夫曼编码

#include <stdio.h> 
#define N 7 /*叶子数目,需要时更改此值即可*/ 
#define M 2*N-1 /*节点总数*/ 

typedef struct 
{ 
char bits[N];/*编码存储，位串*/ 
int start; /*编码在位串中的位置*/ 
}codetype; 

typedef struct 
{ 
float weight; 
int lchild,rchild,parent; 
}hufmtree; 

void HUFFMAN(tree1) 
hufmtree tree1[]; 
{ 
int i,j,p1,p2; 
float small1,small2,f; 
hufmtree *tree; 
tree=tree1; 
for(i=0;i<M;i++) /*初始化*/ 
{ 
tree[i].parent=0; 
tree[i].lchild=0; 
tree[i].rchild=0; 
tree[i].weight=0.0; 
} 
printf("please input a possible data weight:\n"); /*输入信源数据*/ 
for(i=0;i<N;i++) /*输入前n个节点的权值*/ 
{ 
scanf("%f",&f); 
tree[i].weight=f; 
} 
for(i=N;i<M;i++) /* 进行n-1次合并，产生n-1个新的节点*/ 
{ 
p1=0,p2=0; 
small1=1;small2=1; 
for(j=0;j<=i-1;j++) /*从所有的节点中，选出两个权值最小的根节点*/ 
if(tree[j].parent==0) /*parent值为0，则显示根节点，否则便是非根节点*/ 
if(tree[j].weight<small1) 
{ 
small2=small1; /*改变最小权，次小权及对应的位置*/ 
small1=tree[j].weight; 
p2=p1; /*p1、p2记住这两个根节点在向量tree中的下标*/ 
p1=j; 
} 
else if(tree[j].weight<small2) 
{ 
small2=tree[j].weight;/*次小权及位置*/ 
p2=j; 
} 
tree[p1].parent=i+1; /*节点分量与下标之间差值为1*/ 
tree[p2].parent=i+1; /*节点的标号i+1*/ 
tree[i].lchild=p1+1; /*最小值根节点是新节点的左孩子，分量标号是其下标加1*/ 
tree[i].rchild=p2+1; /*次小权根节点是新节点的右孩子*/ 
tree[i].weight=tree[p1].weight+tree[p2].weight; 
} 
}/*HUFFMANTREE()*/ 

void HUFFMANCODE(code1,tree1) /*根据哈夫曼树求出哈夫曼编码*/ 
codetype code1[]; /*求出的哈夫曼编码所在*/ 
hufmtree tree1[];/*已知的哈夫曼树*/ 
{ 
int i,j,c,p; 
codetype cd;/*缓冲变量*/ 
codetype *code; 
hufmtree *tree; 
code=code1; 
tree=tree1; 
for(i=0;i<N;i++) 
{ 
cd.start=N; 
c=i+1; /*从叶节点出发向上回溯*/ 
p=tree[i].parent;/*tree[p-1]是tree[i]的双亲*/ 
while(p!=0) 
{ 
cd.start--; 
if(tree[p-1].lchild==c) 
cd.bits[cd.start]='0'; /*tree[i]是左子树。生成代码'0'*/ 
else 
cd.bits[cd.start]='1'; /*否则tree[i]是右子树。生成代码'1'*/ 
c=p; 
p=tree[p-1].parent; 
} 
code[i]=cd; /*第i+1个字符的编码存入code[i]*/ 
} 
} /*HUFFMANCODE*/ 

#include "stdio.h" 
main() 
{ 
int k1,k2; 
hufmtree tree_fina[M]; 
hufmtree *p11=tree_fina; 
codetype code_fina[N]; 
codetype *p21=code_fina; 
HUFFMAN(p11); /*建立huffman树*/ 
HUFFMANCODE(p21,p11); /*haffman码*/ 
for(k1=0;k1<N;k1++) /*输出编码*/ 
{ 
printf("number %d haffmancode: ",k1+1); 
for(k2=code_fina[k1].start;k2<N;k2++) 
printf(" %c",code_fina[k1].bits[k2]); 
printf("\n"); 
} 
}