Huffman编码示例程序

#include
#include
#include
/*哈夫曼树结点*/
typedef struct _node
{
 int weight; /*权*/
 struct _node *lchild, *rchild;
}HNode, *PHNode;
/*将哈夫曼放入哈夫曼森林（指针数组），保持森林中各树根权值降序排列
trees: 哈夫曼森林，n：森林中已有树棵数，node：待加入的哈夫曼树
*/
void AddNode(PHNode* trees, int n, PHNode node)
{
 /*为给定结点寻找在森林中合适的位置*/
 while (n > 0 && node->weight > trees[n-1]->weight)
 {
  trees[n]=trees[n-1];
  n--;
 }
 trees[n] = node;
}
/*
根据给定权值，创建一棵哈夫曼树
ws为权值数组，以 0 作为结束标志
*/
PHNode CreateHuffmanTree(int* ws)
{
 int i, n=0;
 PHNode* trees;/*二叉树森林*/
 PHNode t1, t2, root;
 while (ws[n]) n++; /*获取仅值的个数*/
 trees = (PHNode*)malloc(sizeof(PHNode)*n); /*分配n个指针*/
 /*为给定权值创建一棵树，放入森林*/
 for (i = 0; i < n; i++)
 {
  root = (PHNode)malloc(sizeof(HNode));
  root->weight = ws[i];
  root->lchild = root->rchild = NULL;
  AddNode(trees, i, root);
 }
 
 while (n>1)
 {
  t1=trees[n-1];
  t2=trees[n-2];
  root = (PHNode)malloc(sizeof(HNode));
  root->weight = t1->weight + t2->weight;
  root->lchild = t1; root->rchild = t2;
  /*为新的树根找到合适的位置，插入到森林*/
  AddNode(trees, n-2, root);
  n--;
 }
 root = trees[0];
 free(trees);
 return root;
}
/*打印哈夫曼编码，返回哈夫曼树的PWL*/
int PrintCodes(PHNode root, char* code)
{
 char *newcode;
 int weight=0;
 int len = code ? strlen(code) : 0;
 if (!root->lchild&&!root->rchild) /*是叶结点，则输出结果*/
 {
  printf("%d /t%s/n", root->weight, code);
  return len * root->weight;
 }

 len++; /*新编码的长度*/
 /*将上级传递的编码code，加上一个'0'或'1'作为新编码*/
 newcode =(char*)malloc(len+1);
 if (code) strcpy(newcode, code);
 newcode[len] = '/0';
 /*左分支编码添加0*/
 newcode[len-1] = '0';
 weight += PrintCodes(root->lchild, newcode);
 /*右分支编码添加1*/
 newcode[len-1] = '1';
 weight += PrintCodes(root->rchild, newcode);
 free(newcode);
 return weight;
}
/*删除哈夫曼树*/
void DestoryTree(PHNode root)
{
 if (!root) return;
 DestoryTree(root->lchild);
 DestoryTree(root->rchild);
 free(root);
}

void main()
{
 PHNode root;
 int ws[100],i;
 while (1)
 {
  printf("请输入权值，以 0 结束/n");
  i = 0;
  do
  {
   scanf("%d", &ws[i]);
  }while(ws[i++]);
  if (!ws[0]) break; //直接输入0退出程序
  root = CreateHuffmanTree(ws);
  printf("/n权值/t编码/n");
  printf("/nPWL=%d/n", PrintCodes(root,NULL));
  DestoryTree(root);
  printf("/n");
 }
}

http://blog.csdn.net/yycec/article/details/3414751