C++实现哈夫曼树及哈夫曼编码.rar

C++实现哈夫曼树及哈夫曼编码，代码简介https://blog.csdn.net/qq_41664447/article/details/90736442，C++源程序可直接运行

#include
#include
using namespace std;
//哈夫曼树的存储表示
typedef char ElemType;
typedef struct
{
    ElemType data;              //结点存的数据
    int weight;                 //结点的权值
    int parentlchildrchild;   //结点的双亲、左孩子、右孩子的下标
} HTNode*HuffmanTree;          //动态分配数组存储哈夫曼树
void Select（HuffmanTree HTint nint &s1int &s2）;
//构造哈夫曼树
/*算法步骤：
1.初始化：首先动态申请2n个单元，然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的双亲、左孩子、右孩子
的下标都初始化为0；最后再循环n次，输入前n个单元中叶子节点的权值
2.创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。
选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2；
删除是指将结点s1和s2的双亲改为非0；合并就是将s1和s2的权值和作为一个新结点的权值依次存入到数组的第n+1之后的单元中，
同时记录这个新结点左孩子的下标为s1，右孩子的下标为s2*/
void CreateHuffmanTree（HuffmanTree &HTint n）
{
    //构造哈夫曼树HT
    if（n<=1）
    {
        cout<<“HuffmanTree节点数输入错误！“<        return;
    }
    int m=2*n-1;
    int s1=1s2=1;
    HT=new HTNode[m+1];         //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
    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）     //输入前n个单元中叶子结点的权值（包括空格）
    {

        cout<<“请输入第“<        char c;//用来保存之前键入的回车键
        c=cin.get（）;
        HT[i].data=cin.get（）;
        cout<<“请输入第“<        cin>>HT[i].weight;
    }
    //--------------------------初始化工作结束，下面开始创建完整哈夫曼树
    for（int i=n+1; i<=m; ++i）
    {
        //通过n-1次的选择、删除、合并来创建哈夫曼树
        Select（HTi-1s1s2）;                       //在HT[k]（1<=k<=i-1）中选择两个其双亲域为0且权值最小的结点，并返回它们在HT中的序号s1和s2
        HT[s1].parent=i;
        HT[s2].parent=i;            //得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
        HT[i].lchild=s1;
        HT[i].rchild=s2;            //s1，s2分别作为i的左右孩子
        HT[i].weight=HT[s1].weight+HT[s2].weight;   //i的权值为左右孩子权值之和
    }
}
//在HT中选择两个其双亲域为0且权值最小的结点，返回它们在HT中的序号s1和s2
void Select（HuffmanTree HTint nint &s1int &s2）
{
    int i=1;//开始初始化wetmin1wetmin2，使用一个i往后找，HT[i].parent==0的结点
    int temp;
    int wetmin1wetmin2;
    //开始寻找前两个HT[i].parent==0的结点，给wetmin1wetmin2初始化
    while（HT[i].parent!=0）
        i++;
    wetmin1=HT[i].weight;
    s1=i;
    i++;
    while（HT[i].parent!=0）
        i++;
    wetmin2=HT[i].weight;
    s2=i;
    i++;//从初始值后面的结点开始遍历
    //初始化wetmin1wetmin2，将小的赋值给wetmin1
    if（wetmin1>wetmin2）
    {
        temp=wetmin2;
        wetmin2=wetmin1;
        wetmin1=temp;
        temp=s2;
        s2=s1;
        s1=temp;
    }
    for（i; i<=n; i++）
    {
        if（HT[i].parent==0&&HT[i].weight        {
            wetmin2=wetmin1;
            wetmin1=HT[i].weight;
            s2=s1;
            s1=i;
        }
        else if（HT[i].parent==0&&HT[i].weight        {
            wetmin2=HT[i].weight;
            s2=i;
        }
    }
}
//哈夫曼编码表的的存储表示
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
//根据哈夫曼树求哈夫曼编码
void CreateHuffmanCode（HuffmanTree HTHuffmanCode &HCint &n）
{
    //从叶子到根逆向求每个字符的哈夫曼编码，存储

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

    .CA....      9940  2019-06-01 01:35  C++实现哈夫曼树及哈夫曼编码\HuffmanTree.cpp

    .CA....   1053276  2019-06-01 01:18  C++实现哈夫曼树及哈夫曼编码\HuffmanTree.exe

    .CA....      9025  2019-06-01 01:18  C++实现哈夫曼树及哈夫曼编码\HuffmanTree.o

    .C.D...         0  2019-06-02 09:51  C++实现哈夫曼树及哈夫曼编码

----------- ---------  ---------- -----  ----

              1072241                    4