huffman(tree1)、huffmancode(code1,tree1)【c】.txt

本程序运用C语言中结构化程序的思想

#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");
 }
}