main.cpp

哈夫曼树的计算方法 实验报告用程序

#include <iostream>
#define n 5
#define m 2*n-1
using namespace std;
struct HTNODE
{
    double weight;
    int lchild;
    int rchild;
    int parent;
};
typedef HTNODE HuffmanT[m];
void InitHT(HuffmanT T);
void SelectMin(HuffmanT T,int l,int &p1,int &p2);
void CreatHT(HuffmanT T);
void Output(HuffmanT T);
void Input(HuffmanT T);

int main()
{
    HuffmanT T;
    CreatHT(T);
    Output(T);
    cout << "Hello world!" << endl;
    return 0;
}
void InitHT(HuffmanT T)
{
    int i;
    for (i = 0;i < m;i++)
    {
        T[i].weight = 0;
        T[i].lchild = T[i].rchild = T[i].parent = -1;
    }
    Input(T);
}
void SelectMin(HuffmanT T,int l,int &p1,int &p2)
{
    int i,j;
    for (i = 0;i < l;i++)
        if (T[i].parent == -1)
        {
            p1 = i;
            break;
        }
    for (j = i+1;j < l;j++)
        if (T[j].parent == -1)
        {
            p2 = j;
            break;
        }
    for (i = 0;i < l;i++)
        if ((T[i].parent == -1)&&(T[p1].weight > T[i].weight)&&(p2 != i))
            p1 = i;
    for (i = 0;i < l;i++)
        if ((T[i].parent == -1)&&(T[p2].weight > T[i].weight)&&(p1 != i))
            p2 = i;
}
void CreatHT(HuffmanT T)
{
    int i,p1,p2;
    InitHT(T);
    for (i = n;i < m;i++)
    {
        SelectMin(T,i,p1,p2);
        T[p1].parent = T[p2].parent = i;
        T[i].lchild = p1;
        T[i].rchild = p2;
        T[i].weight = T[p1].weight + T[p2].weight;
    }
}
void Output(HuffmanT T)
{
    int i;
    for (i = 0;i < m;i++)
    {
        cout << T[i].weight << "\t";
        cout << T[i].parent << "\t";
        cout << T[i].lchild << "\t";
        cout << T[i].rchild << "\t"<<endl;

    }
}
void Input(HuffmanT T)
{
    int i;
    double x;
    for(i = 0;i < n;i++)
    {
        cin >> x;
        T[i].weight = x;
        }
    }