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

#include "stdafx.h"
#include "stdio.h"
#define N 50             //叶子结点数
#define M 2*N-1            //树中结点总数

typedef struct
{
    char data;            //结点值
    double weight;       //权值
    int parent;            //双亲结点
    int lchild;            //左孩子结点
    int rchild;            //右孩子结点
} HTNode;
typedef struct
{
    char cd[N];            //存放哈夫曼码
    int start;
} HCode;

//建立Huffman树
void CreateHT(HTNode ht[],int n)
{
    int i,k,lnode,rnode;
    double min1,min2;
    for (i=0;i<2*n-1;i++)                 //所有结点的相关域置初值-1
        ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
    for (i=n;i<2*n-1;i++){                //构造哈夫曼树
        min1=min2=33267;                 //lnode和rnode为最小权重的两个结点位置
        lnode=rnode=-1;
        for (k=0;k<=i-1;k++)
            if (ht[k].parent==-1)       //只在尚未构造二叉树的结点中查找
            {
                if (ht[k].weight<min1){
                    min2=min1;
                    rnode=lnode;
                    min1=ht[k].weight;
                    lnode=k;
                }
                else if (ht[k].weight<min2){
                    min2=ht[k].weight;
                    rnode=k;
                }
            }
        ht[i].weight=ht[lnode].weight+ht[rnode].weight;
        ht[i].lchild=lnode;
        ht[i].rchild=rnode;
        ht[lnode].parent=i;
        ht[rnode].parent=i;
    }
}


void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
    int i,f,c;
    HCode hc;
    for (i=0;i<n;i++){             //根据哈夫曼树求哈夫曼编码
        hc.start=n;c=i;
        f=ht[i].parent;
        while (f!=-1){           //循序直到树根结点
            if (ht[f].lchild==c)         //处理左孩子结点
                hc.cd[hc.start--]='0';
            else                        //处理右孩子结点
                hc.cd[hc.start--]='1';
            c=f;
            f=ht[f].parent;
        }
        hc.start++;                 //start指向哈夫曼编码最开始字符
        hcd[i]=hc;
    }
}

//输出哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
    int i,k;
    double sum=0,m=0;
    int j;
    printf("输出哈夫曼编码:\n");      
    for (i=0;i<n;i++){
        j=0;
        printf("   %c:",ht[i].data);
        for (k=hcd[i].start;k<=n;k++){
            printf("%c",hcd[i].cd[k]);
            j++;
        }
        m+=ht[i].weight;
        sum+=ht[i].weight*j;
        printf("\n");
    }
}

int main(int argc, char* argv[])
{
    int n=9,i;                     //n表示初始字符串的个数
    char str[]={'A','S','D','F','G','H','J','K','L'};      //数据
    double fnum[]={1,2,3,4,5,6,7,8,9};                 //权值
    HTNode ht[M];
    HCode hcd[N];
    for (i=0;i<n;i++)    {
        ht[i].data=str[i];
        ht[i].weight=fnum[i];
    }
    CreateHT(ht,n);
    CreateHCode(ht,hcd,n);
    DispHCode(ht,hcd,n);
    printf("\n");
}

能写一个用来压缩文件的算法吗？用huffman编码,谢谢~

lz你的代码有bug：
int n=5,i;                     //n表示初始字符串的个数
    char str[]={'A','b','c','d','e','f'};      //数据
    double fnum[]={4,2,2,1,1};  
结果为：
输出哈夫曼编码:
   A:11
   b:00
   c:01
   d:100
   e:101

请按任意键继续. . .
而A:应该只有一个码长
应该是判断最小权，与次小权那里错了

huffman编码是非唯一的。但是我就是构造不到上面的结果

//Huffman Code
#include <stdio.h>
#include <stdlib.h>
#define n 5
#define m 2*n-1
//位域结构体
typedef struct Bit
{//只能放0和1
unsigned int a:1;//放0或1
}Mybit;
typedef struct tree
{
    float weight;
    int lChild;
    int rChild;
    int parent;
    Mybit bit;
    struct tree()//初始化树
    {
        weight = 0.0;
        lChild = -1;
        rChild = -1;
        parent = -1;
        bit.a = 1;
    }
}Huffman;

typedef Mybit elemtype;//定义元素类型为一个结构体

typedef struct stack
{
    elemtype data[n-1];//
    int top;
}Stack;

void TowSmallNode(Huffman tree[],int k,int *lsmall, int *rsmall)
{
        int i = 0;
        int temp;
        *lsmall = *rsmall = -1;
        float minw1,minw2;
        minw1 = minw2 = 0x7fffffff;
       
        for (i = 0; i<k; i++)
        {
            if (tree[i].parent == -1)//没有parent的节点进行比较
            {
                if (minw1>=tree[i].weight)
                {
                   
                        minw2 = minw1;
                        minw1 = tree[i].weight;
                        *rsmall = *lsmall;
                        *lsmall = i;
                   
                }
                else if (minw2 > tree[i].weight)
                {
                    minw2 = tree[i].weight;
                    *rsmall = i;   
                }
            }
        }

   
}

void CreateTree(Huffman tree[])
{

    int i = 0;
    int lsmall = 0;
    int rsmall = 0;
    float w;
    printf("请输入消息的概率：\n");
    for (i = 0; i<n; i++)//输入叶子
    {
        scanf("%f", &w);
        tree[i].weight = w;
    }

    for (i=n; i<m; i++)//剩下的节点
    {
        TowSmallNode(tree,i, &lsmall, &rsmall);//找出最小权的两个标
        tree[i].lChild = lsmall;//左孩子
        tree[i].rChild = rsmall;//右孩子
        tree[i].weight = tree[lsmall].weight + tree[rsmall].weight;//两个最小权值相加
        tree[lsmall].parent = i;
        tree[rsmall].parent = i;
        tree[lsmall].bit.a = 0;//是左边的就放二进制的0
    }
}

//置空栈
void setNull(Stack *s)
{
    s ->top = -1;
return ;
}
//进栈
void push(Stack *s, elemtype x)
{
    s ->top++;
    s ->data[s->top] = x;
    return;
}
//出栈
elemtype pop(Stack *s)
{
    s ->top--;
    return (s ->data[s->top+1]);
}
//
int main()
{
    Huffman tree[m];
    CreateTree(tree);
    int i =0;
    int k;
    Stack *s = (Stack*)malloc(sizeof(Stack));//分配栈空间
    for (i =0 ; i<n; i++)
    {
        k = i;
        setNull(s);//置栈为空
        while(tree[k].parent !=-1)
        {
           
            push(s, tree[k].bit);//进栈
            k = tree[k].parent ;
        }
        //出栈
        printf("消息的概率为%.2f的二进制码为:",tree[i].weight);
        while(s->top != -1)
        {
            printf("%d", pop(s).a);//输出二进制码
        }
            printf("\n");
    }
    free(s);//释放空间
return 0;
}

你能解决这个BUG么，我测试了下我的，也是这个结果。
    貌似用手动编码也是这个结果。。

//以前写过的.你参考一下.
#include   <stdio.h>   
  #include   <string.h>   
  #include   <stdlib.h>   
  #include   <malloc.h>   
  #include   <conio.h>   
   
  typedef   struct   {   
  unsigned   int   weight;   
  unsigned   int   parent,lchild,rchild;   
  }   HTNode,*HuffmanTree;   
   
  typedef   char   **HuffmanCode; /*用来存放哈夫曼编码*/     
  typedef   struct   {   
  unsigned   int   s1;   
  unsigned   int   s2;   
  }   MinCode;   
   
  void   Error(char   *message);   
  HuffmanCode   HuffmanCoding(HuffmanTree   HT,HuffmanCode   HC,unsigned   int   *w,unsigned   int   n);   
  MinCode   Select(HuffmanTree   HT,unsigned   int   n);   
   
  void   Error(char   *message)   
  {   
  fprintf(stderr,"Error:%s\n",message);   
  exit(1);   
  }   
   
  HuffmanCode   HuffmanCoding(HuffmanTree   HT,HuffmanCode   HC,unsigned   int   *w,unsigned   int   n)   
  {   /*构造哈弗曼树ht,哈夫曼树的编码存放在hc中*/
  unsigned   int   i,s1=0,s2=0;   
  HuffmanTree   p;   
  char   *cd;   
  unsigned   int   f,c,start,m;   
  MinCode   min;   
  if(n<=1)   Error("Code   too   small!");   
  m=2*n-1;   
  HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*第0个单元未用*/  
  for(p=HT,i=0;i<=n;i++,p++,w++)  /*初始化N个叶子结点*/
  {   
  p->weight=*w;   
  p->parent=0;   
  p->lchild=0;   
  p->rchild=0;   
  }   
  for(;i<=m;i++,p++)   /*将n-1个非叶子结点的双亲结点初始化为0*/
  {   
  p->weight=0;   
  p->parent=0;   
  p->lchild=0;   
  p->rchild=0;   
  }   
  for(i=n+1;i<=m;i++)   
  {   
  min=Select(HT,i-1);   
  s1=min.s1;   
  s2=min.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;   
  }   
  printf("HT   List:\n");   
  printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");   
  for(i=1;i<=m;i++)   
  printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",   
  i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);  
/*从叶子结点到根结点求每个字符的哈夫曼编码*/
  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[start]);   
  }   
  free(cd);   
  return   HC;   
  }   
   
  MinCode   Select(HuffmanTree   HT,unsigned   int   n)   
  {   
  unsigned   int   min,secmin;   
  unsigned   int   temp;   
  unsigned   int   i,s1,s2,tempi;   
  MinCode   code;   
  s1=1;s2=1;   
  for(i=1;i<=n;i++)   
  if(HT[i].parent==0)   
  {   
  min=HT[i].weight;   
  s1=i;   
  break;   
  }   
  tempi=i++;   
  for(;i<=n;i++)   
  if(HT[i].weight<min&&HT[i].parent==0)   
  {   
  min=HT[i].weight;   
  s1=i;   
  }   
  for(i=tempi;i<=n;i++)   
  if(HT[i].parent==0&&i!=s1)   
  {   
  secmin=HT[i].weight;   
  s2=i;   
  break;   
  }   
  for(i=1;i<=n;i++)   
  if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)   
  {   
  secmin=HT[i].weight;   
  s2=i;   
  }   
  if(s1>s2)   
  {   
  temp=s1;   
  s1=s2;   
  s2=temp;   
  }   
  code.s1=s1;   
  code.s2=s2;   
  return   code;   
  }   
   
  void   main()   
  {   
  HuffmanTree   HT=NULL;   
  HuffmanCode   HC=NULL;   
  unsigned   int   *w=NULL;   
  unsigned   int   i,n;   
  printf("Input   n:\n");   
  scanf("%d",&n);   
  w=(unsigned   int   *)malloc((n+1)*sizeof(unsigned   int   *)); /*w为n个字符的权值*/  
  w[0]=0;   
  printf("Enter   weight:\n");   
  for(i=1;i<=n;i++)   
  {   
  printf("w[%d]=",i);   
  scanf("%d",&w[i]);   
  }   
  HC=HuffmanCoding(HT,HC,w,n);   
  printf("HuffmanCode:\n");   
  printf("Number\t\tWeight\t\tCode\n");   
  for(i=1;i<=n;i++)   
  printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);   
   
  }