TouGe-Huffman-Tree/SY1.cpp

//   /Users/zhangzhiqi/Library/Mobile Documents/M6HJR9W95L~com~textasticapp~textastic/Documents/CLionProjects/TouGe-Huffman-Tree/SY1.cpp
//   Copyright (c) 2022.
//   @Time    : 2022/4/30   16:27:25
//   @Author : 张稚琦
//   @Address: 湖北理工学院腾龙公寓 5620
//   @Email   : zhang@zhang.mba / zhangzhiqi828@gmail.com / zhangzhiqi@lh83.onmicrosoft.com / 2272358828@qq.com
//   @File      : SY1.cpp
//   @LastModified: 2022/4/30 下午4:25
//   @ProjectName : TouGe_Huffman_Tree

# include <stdio.h>
# include <iostream>
# include <string.h>
using namespace std;


typedef struct          //define structure HuffmanTree
{   int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **  HuffmanCode;

void Select(HuffmanTree HT,int end,int &s1,int &s2) ;//选出HT树到i为止，权值最小且parent为0的2个节点
void HuffmanTreeing(HuffmanTree &HT,int *w,int n);//构建哈夫曼树函数 

void output(HuffmanTree HT,int m);//输出哈夫曼树

int main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int n,i;
    int *w;
    scanf("%d",&n);
    w=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    HuffmanTreeing( HT , w  ,n  );
    cout<<"哈夫曼树:"<<endl;
    output(HT,2*n-1);
    return 0;
}

void Select(HuffmanTree HT,int end,int &s1,int &s2)
{   //选出HT树到i为止，权值最小且parent为0的2个节点
    //s1 is the least of HT[].weight
    //s2 is the second least of HT[].weight
    /********** Begin **********/
    int min1, min2;
    //遍历数组初始下标为 1
    int i = 1;
    //找到还没构建树的结点
    while(HT[i].parent != 0 && i <= end){
        i++;
    }
    min1 = HT[i].weight;
    s1 = i;

    i++;
    while(HT[i].parent != 0 && i <= end){
        i++;
    }
    //对找到的两个结点比较大小，min2为大的，min1为小的
    if(HT[i].weight < min1){
        min2 = min1;
        s2 = s1;
        min1 = HT[i].weight;
        s1 = i;
    }else{
        min2 = HT[i].weight;
        s2 = i;
    }
    //两个结点和后续的所有未构建成树的结点做比较
    for(int j=i+1; j <= end; j++)
    {
        //如果有父结点，直接跳过，进行下一个
        if(HT[j].parent != 0){
            continue;
        }
        //如果比最小的还小，将min2=min1，min1赋值新的结点的下标
        if(HT[j].weight < min1){
            min2 = min1;
            min1 = HT[j].weight;
            s2 = s1;
            s1 = j;
        }
            //如果介于两者之间，min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2){
            min2 = HT[j].weight;
            s2 = j;
        }
    }
    /********** End **********/
}


void HuffmanTreeing(HuffmanTree &HT,int *w,int n) //构建哈夫曼树函数
{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT
    /********** Begin **********/
    if(n<=1) return; // 如果只有一个编码就相当于0
    int m = 2*n-1; // 哈夫曼树总节点数，n就是叶子结点
    HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode)); // 0号位置不用
    HuffmanTree p = HT;
    // 初始化哈夫曼树中的所有结点
    for(int i = 1; i <= n; i++)
    {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->lchild = 0;
        (p+i)->rchild = 0;
    }
    //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
    for(int i = n+1; i <= m; i++)
    {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->lchild = 0;
        (p+i)->rchild = 0;
    }
    //构建哈夫曼树
    for(int i = n+1; i <= m; i++)
    {
        int s1, s2;
        Select(HT, i-1, s1, s2);
        (HT)[s1].parent = (HT)[s2].parent = i;
        (HT)[i].lchild = s1;
        (HT)[i].rchild = s2;
        (HT)[i].weight = (HT)[s1].weight + (HT)[s2].weight;
    }

    /********** End **********/
}


void output(HuffmanTree HT,int m)
{ //输出哈夫曼树
    for(int i=1;i<=m;++i)
    {
        cout<<"HT["<<i<<"] ="<<HT[i].weight<<"\t"<<HT[i]. parent<<"\t";
        cout<<"\t" <<HT[i]. lchild <<"\t" <<HT[i]. rchild<<endl;
    }
}