哈夫曼树

版本一

#include <stdio.h>
#include<stdlib.h>

#define MAXBIT      100
#define MAXVALUE  10000
#define MAXLEAF     30
#define MAXNODE    MAXLEAF*2 -1

typedef struct
{
    int bit[MAXBIT];
    int start;
} HCodeType;        /* 编码结构体 */
typedef struct
{
    int weight;
    int parent;
    int lchild;
    int rchild;
    int value;
} HNodeType;        /* 结点结构体 */

/* 构造一颗哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
{
    /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
        x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
    int i, j, m1, m2, x1, x2;
    /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
    for (i=0; i<2*n-1; i++)
    {
        HuffNode[i].weight = 0;//权值
        HuffNode[i].parent =-1;
        HuffNode[i].lchild =-1;
        HuffNode[i].rchild =-1;
        HuffNode[i].value=i; //实际值，可根据情况替换为字母
    } /* end for */

    /* 输入 n 个叶子结点的权值 */
    for (i=0; i<n; i++)
    {
        printf ("Please input weight of leaf node %d: \n", i);
        scanf ("%d", &HuffNode[i].weight);
    } /* end for */

    /* 循环构造 Huffman 树 */
    for (i=0; i<n-1; i++)
    {
        m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
        x1=x2=0;
        /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
        for (j=0; j<n+i; j++)
        {
            if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
            {
                m2=m1;
                x2=x1;
                m1=HuffNode[j].weight;
                x1=j;
            }
            else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
            {
                m2=HuffNode[j].weight;
                x2=j;
            }
        } /* end for */
        /* 设置找到的两个子结点 x1、x2 的父结点信息 */
        HuffNode[x1].parent  = n+i;
        HuffNode[x2].parent  = n+i;
        HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
        HuffNode[n+i].lchild = x1;
        HuffNode[n+i].rchild = x2;

        printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
        printf ("\n");
    } /* end for */
    /*  for(i=0;i<n+2;i++)
      {
          printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
                    }*///测试
} /* end HuffmanTree */

//解码
void decodeing(char string[],HNodeType Buf[],int Num)
{
    int i,tmp=0,code[1024];
    int m=2*Num-1;
    char *nump;
    char num[1024];
    for(i=0; i<strlen(string); i++)
    {
        if(string[i]=='0')
            num[i]=0;
        else
            num[i]=1;
    }
    i=0;
    nump=&num[0];

    while(nump<(&num[strlen(string)]))
    {
        tmp=m-1;
        while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
        {

            if(*nump==0)
            {
                tmp=Buf[tmp].lchild ;
            }
            else tmp=Buf[tmp].rchild;
            nump++;

        }

        printf("%d",Buf[tmp].value);
    }


}


int main(void)
{

    HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
    HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
    int i, j, c, p, n;
    char pp[100];
    printf ("Please input n:\n");
    scanf ("%d", &n);
    HuffmanTree (HuffNode, n);


    for (i=0; i < n; i++)
    {
        cd.start = n-1;
        c = i;
        p = HuffNode[c].parent;
        while (p != -1)   /* 父结点存在 */
        {
            if (HuffNode[p].lchild == c)
                cd.bit[cd.start] = 0;
            else
                cd.bit[cd.start] = 1;
            cd.start--;        /* 求编码的低一位 */
            c=p;
            p=HuffNode[c].parent;    /* 设置下一循环条件 */
        } /* end while */

        /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
        for (j=cd.start+1; j<n; j++)
        {
            HuffCode[i].bit[j] = cd.bit[j];
        }
        HuffCode[i].start = cd.start;
    } /* end for */

    /* 输出已保存好的所有存在编码的哈夫曼编码 */
    for (i=0; i<n; i++)
    {
        printf ("%d 's Huffman code is: ", i);
        for (j=HuffCode[i].start+1; j < n; j++)
        {
            printf ("%d", HuffCode[i].bit[j]);
        }
        printf(" start:%d",HuffCode[i].start);

        printf ("\n");

    }
    /*    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            {
                 printf ("%d", HuffCode[i].bit[j]);
            }
            printf("\n");
            }*/
    printf("Decoding?Please Enter code:\n");
    scanf("%s",&pp);
    decodeing(pp,HuffNode,n);
    getch();
    return 0;
}

版本二

#include<iostream>
#include<cstring>
#include<cstdlib>
#define MAX_MA 1000
#define MAX_ZF 100
using namespace std;

//哈夫曼树的储存表示
typedef struct
{
    int weight;  //结点的权值
    int parent, lchild, rchild;//双亲，左孩子，右孩子的下标
}HTNode,*HuffmanTree;  //动态分配数组来储存哈夫曼树的结点

//哈夫曼编码表的储存表示
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码

//返回两个双亲域为0且权值最小的点的下标
void Select(HuffmanTree HT, int n, int &s1, int &s2)
{
    /*n代表HT数组的长度
    */

   //前两个for循环找所有结点中权值最小的点（字符）
    for (int i = 1; i <= n; i++)
    {//利用for循环找出一个双亲为0的结点
        if (HT[i].parent == 0)
        {
            s1 = i;//s1初始化为i
            break;//找到一个后立即退出循环
        }
    }
    for (int i = 1; i <= n; i++)
    {/*利用for循环找到所有结点（字符）权值最小的一个
     并且保证该结点的双亲为0*/
        if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
            s1 = i;
    }
    //后两个for循环所有结点中权值第二小的点（字符）
    for (int i = 1; i <= n; i++)
    {//利用for循环找出一个双亲为0的结点，并且不能是s1
        if (HT[i].parent == 0 && i != s1)
        {
            s2 = i;//s2初始化为i
            break;//找到一个后立即退出循环
        }
    }

    for (int i = 1; i <= n; i++)
    {/*利用for循环找到所有结点（字符）权值第二小的一个，
     该结点满足不能是s1且双亲是0*/
        if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
            s2 = i;
    }
}

//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int n)
{
/*-----------初始化工作-------------------------*/
    if (n <= 1)
        return;
    int m = 2 * n - 1;
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; ++i)
    {//将1~m号单元中的双亲，左孩子，右孩子的下标都初始化为0
        HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> HT[i].weight;//输入前n个单元中叶子结点的权值
    }
/*-----------创建工作---------------------------*/
    int s1,s2;
    for (int i = n + 1; i <= m; ++i)
    {//通过n-1次的选择，删除，合并来构造哈夫曼树
        Select(HT, i - 1, s1, s2);
        /*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/
        /*将s1,s2的双亲域由0改为i
        (相当于把这两个结点删除了，这两个结点不再参与Select()函数)*/
        HT[s1].parent = i;
        HT[s2].parent = i;
        //s1,与s2分别作为i的左右孩子
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        //结点i的权值为s1,s2权值之和
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

//从叶子到根逆向求每个字符的哈夫曼编码，储存在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
    HC = new char*[n + 1];//分配储存n个字符编码的编码表空间
    char *cd = new char[n];//分配临时存储字符编码的动态空间
    cd[n - 1] = '\0';//编码结束符
    for (int i = 1; i <= n; i++)//逐个求字符编码
    {
        int start = n - 1;//start 开始指向最后，即编码结束符位置
        int c = i;
        int f = HT[c].parent;//f指向结点c的双亲
        while (f != 0)//从叶子结点开始回溯，直到根结点
        {
            --start;//回溯一次，start向前指向一个位置
            if (HT[f].lchild == c) cd[start] = '0';//结点c是f的左孩子，则cd[start] = 0;
            else cd[start] = '1';//否则c是f的右孩子，cd[start] = 1
            c = f;
            f = HT[f].parent;//继续向上回溯
        }
        HC[i] = new char[n - start];//为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);//把求得编码的首地址从cd[start]复制到HC的当前行中
    }
    delete cd;
}

//哈夫曼译码
void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)
{
    /*
    HT是已经创建好的哈夫曼树
    a[]用来传入二进制编码
    b[]用来记录译出的字符
    zf[]是与哈夫曼树的叶子对应的字符（叶子下标与字符下标对应）
    n是字符个数，相当于zf[]数组得长度
    */

    int q = 2*n-1;//q初始化为根结点的下标
    int k = 0;//记录存储译出字符数组的下标
    int i = 0;
    for (i = 0; a[i] != '\0';i++)
    {//for循环结束条件是读入的字符是结束符（二进制编码）
        //此代码块用来判断读入的二进制字符是0还是1
        if (a[i] == '0')
        {/*读入0，把根结点(HT[q])的左孩子的下标值赋给q
         下次循环的时候把HT[q]的左孩子作为新的根结点*/
            q = HT[q].lchild;
        }
        else if (a[i] == '1')
        {
            q = HT[q].rchild;
        }
        //此代码块用来判断HT[q]是否为叶子结点
        if (HT[q].lchild == 0 && HT[q].rchild == 0)
        {/*是叶子结点，说明已经译出一个字符
        该字符的下标就是找到的叶子结点的下标*/
            b[k++] = zf[q];//把下标为q的字符赋给字符数组b[]
            q = 2 * n - 1;//初始化q为根结点的下标
            //继续译下一个字符的时候从哈夫曼树的根结点开始
        }
    }
    /*译码完成之后，用来记录译出字符的数组由于没有结束符输出的
    时候回报错，故紧接着把一个结束符加到数组最后*/
    b[k] = '\0';
}
//菜单函数
void menu()
{
    cout << endl;
    cout << "       ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;
    cout << "       ┃      ★★★★★★★哈夫曼编码与译码★★★★★★★        ┃" << endl;
    cout << "       ┃                   1.  创建哈夫曼树                       ┃" << endl;
    cout << "       ┃                   2.  进行哈夫曼编码                     ┃" << endl;
    cout << "       ┃                   3.  进行哈夫曼译码                     ┃" << endl;
    cout << "       ┃                   4.  退出程序                           ┃" << endl;
    cout << "       ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;
    cout << "                       <><注意：空格字符用'- '代替><>" << endl;
    cout << endl;
}
int  main()
{
    int falg;//记录要编码的字符个数
    char a[MAX_MA];//储存输入的二进制字符
    char b[MAX_ZF];//存储译出的字符
    char zf[MAX_ZF];//储存要编码的字符
    HuffmanTree HT = NULL;//初始化树为空数
    HuffmanCode HC = NULL;//初始化编码表为空表
    menu();
    while (true)
    {
        int num;
        cout << "<><请选择功能(1-创建 2-编码 3-译码 4-退出)><>: ";
            cin >> num;
            switch (num)
            {
            case 1 :
                cout << "<><请输入字符个数><>:";
                cin >> falg;
                //动态申请falg个长度的字符数组，用来存储要编码的字符
                /*char *zf = new char[falg];*/
                cout << "<><请依次输入" << falg << "个字符:><>: ";
                for (int i = 1; i <= falg; i++)
                    cin >> zf[i];
                cout << "<><请依次输入" << falg << "个字符的权值><>: ";
                CreateHuffmanTree(HT, falg);//调用创建哈夫曼树的函数
                cout << endl;
                cout << "<><创建哈夫曼成功！,下面是该哈夫曼树的参数输出><>：" << endl;
                cout << endl;
                cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "双亲" << "\t" << "左孩子" << "\t" << "右孩子" << endl;
                for (int i = 1; i <= falg * 2 - 1; i++)
                {
                    cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << HT[i].rchild << endl;
                }
                cout << endl;
                break;
            case 2:
                CreatHuffmanCode(HT, HC, falg);//调用创建哈夫曼编码表的函数
                cout << endl;
                cout << "<><生成哈夫曼编码表成功！,下面是该编码表的输出><>：" << endl;
                cout << endl;
                cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "编码" << endl;
                for (int i = 1; i <= falg; i++)
                {
                    cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HC[i] << endl;
                }
                cout << endl;
                break;
            case 3:
                cout << "<><请输入想要翻译的一串二进制编码><>：";
                /*这样可以动态的直接输入一串二进制编码，
                因为这样输入时最后系统会自动加一个结束符*/
                cin >> a;
                TranCode(HT, a, zf, b, falg);//调用译码的函数，
                 /*这样可以直接把数组b输出，因为最后有
                 在数组b添加输出时遇到结束符会结束输出*/
                cout << endl;
                cout << "<><译码成功！翻译结果为><>：" << b << endl;
                cout << endl;
                break;
            case 4:
                cout << endl;
                cout << "<><退出成功！><>" << endl;
                exit(0);
            default:
                break;
            }
    }
    return 0;
}


//实验数据
/*
1
8
A B C D E F G H
5 29 7 8 14 23 3 11
2
3
1001001
4
*/