程序代码：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#define max 2147483647
using namespace std;
typedef struct Node
{
    int weight;
    int lchild,rchild,parent;
}node;


typedef struct ch
{
    int weight;
    char c;
}zf;

typedef struct
{
    int *base;
    int *top;
}stack;

int init(node *p,char *q)                //输入字符集以及权值
{
//    int i=0;
//    for(int i=0;i<2*n-1;i++)
//    {
//        p[i].lchild=p[i].rchild=p[i].parent=-1;
//    }
//    for(i=0;i<n;i++)
//    {
//        getchar();                                //消除\n或空格
//        q[i]=getchar();
//        getchar();                                //消除\n或空格
//        scanf("%d",&p[i].weight);
//    }
    int i,j,k=0,h,n=0; 
    string huffmanStr;
    cout<<"请输入需要进行哈夫曼编码的字符串："<<endl;
    getline(cin,huffmanStr);        //用于获取对空格的输入，getline函数遇车符结束输入 
    n = huffmanStr.length();
      cout << "字符串总共有字符" << n << "个" << endl;
  
    for(i=0;i<n;i++)
    {
        j=0,h=0;
        while(huffmanStr[i]!=huffmanStr[j])
            j++;
        if(j==i)
        {
            q[k]=huffmanStr[i];    //存储字符 
            cout<<"字符"<<q[k]<<"出现";
        }
        else
            continue;            //避免相同的字符重复输出，起到过滤的作用
        for(j=i;j<n;j++)
        {
            if(huffmanStr[j]==huffmanStr[i])
                h++;
        } 
        cout<<h<<"次"<<endl; 
        p[k].weight=h;    //存储权值 
        k++;    //叶子树 
        
             
    }
    
    for(i=0;i<2*k-1;i++)        //初始化哈夫曼树 
    {
        p[i].lchild=p[i].rchild=p[i].parent=-1;
    }
    for(i=k;i<2*k-1;i++)
    {
        p[i].weight=max;
    }
    return k;
}


int min1(node *p,int n,int position)        //返回数组中大于等于position的最小数的下标
{
    int k,i;                                            //存储数组中大于等于position的最小数的下标
    for(int i=0;i<2*n-1;i++)
    {
        if(i!=position&&p[i].parent==-1)
        {
            k=i;
            break;
        }
    }
    for(i=0;i<2*n-1;i++)
    {    
        if((p[i].weight>=p[position].weight)&&(p[i].weight<p[k].weight)&&i!=position&&p[i].parent==-1)
            k=i;
    }
//    printf("%d",k);
    return k;
}

int min(node *p,int n)        //返回数组中大于等于position的最小数的下标
{
    int k=0,i;                //存储数组中大于等于position的最小数的下标
    for(int i=0;i<2*n-1;i++)
    {
        if(p[i].parent==-1)        //随便选一个父节点为空的结点
        {
            k=i;
            break;
        }
    }
    for(i=0;i<2*n-1;i++)            //选择父节点为空的最小结点
    {    
        if((p[i].weight<p[k].weight)&&p[i].parent==-1)
            k=i;
    }
//    printf("%d",k);
    return k;
}

void build(node *p,int n)                        //建立哈夫曼编码
{
    int l1,l2;
    for(int i=0;i<n-1;i++)
    {
        l1=min(p,n);                            //取当前父节点为空的最小结点l1
        l2=min1(p,n,l1);                        //取除了l1的父节点为空的最小结点l2
        p[n+i].weight=p[l1].weight+p[l2].weight;            //构建关系    
        p[l1].parent=n+i;
        p[l2].parent=n+i;
        p[n+i].lchild=l1;
        p[n+i].rchild=l2;
    }
}





void code(node *p,char *q,int n)
{                        
    int *stack=(int *)malloc(sizeof(int)*n);                //初始化一个栈
    for(int i=0;i<n;i++)
    {
        int ch=i;                        //暂存本结点
        int top=0;                        //初始化栈顶指针
        while(p[ch].parent!=-1)
        {                        
            int par=p[ch].parent;                    //暂存父结点
            if(p[par].lchild==ch)
            {
                stack[top]=0;
                top++;
            }
            else
            {
                stack[top]=1;
                top++;
            }
            ch=par;
        }
        cout<<q[i];
        top--;
        while(top>=0)
        {
            cout<<stack[top];
            top--;
        }
        cout<<endl;
    }
}


void show(node *p,int n)
{
    for(int i=0;i<n*2-1;i++)
    {
        cout<<"node :"<<i<<"    w:"<<p[i].weight<<"  p:"<<p[i].parent<<"   cl:"<<p[i].lchild<<"   cr:"<<p[i].rchild<<endl;
    }
}


void decode(node *p,char *q,int n)            //输入01编码,最后以'#'结尾
{
    getchar();
    char c;
    node *nd;
    int i;
    while(1)
    {
        nd=&p[2*n-2];
        while((nd->lchild)!=-1)
        {
            c=getchar();
            if(c=='#')
                exit(1);
            if(c=='1')
                i=nd->rchild;
            else
                if(c=='0')
                    i=nd->lchild;
            nd=&p[i];
        }
            cout<<q[i];
    }

}

int main()
{
    int n=0;
    //scanf("%d",&n);
    node *p=(node *)malloc(sizeof(node)*(2*n-1));
    char *q=(char *)malloc(sizeof(node)*n);
    n=init(p,q);
    build(p,n);
    code(p,q,n);
//    min(p,n,0);
    show(p,n);
    decode(p,q,n);
    return 0;
}