12.18

写数据结构作业

7-1 哈夫曼树哈夫曼编码

输入一组整型权值，构建哈夫曼树，实现哈夫曼编码，并输出带权路径长度。

输入格式:

第一行输入叶子结点个数，接着依次输入权值。若叶子数为0或1，则输出error

输出格式:

输出哈夫曼编码，输出带权路径长度。

输入样例:

在这里给出一组输入。例如：

8

5 29 7 8 14 23 3 11

输出样例:

在这里给出相应的输出。例如：

5编码为0001

29编码为10

7编码为1110

8编码为1111

14编码为110

23编码为01

3编码为0000

11编码为001

WPL:271

一．实验内容

#include<iostream>

#include<cstring>

using namespace std;

typedef char **HuffmanCode;

//哈夫曼树：parent、lchild、rchild、weight

typedef struct

{

    int weight;

    int lchild,rchild,parent;

}HTNode,*HuffmanTree;

void min(HuffmanTree HT,int pos,int &s1,int &s2)

{//找到最小权值的两个下标信息

    s1=pos;s2=pos;//这个位置parent肯定为0

    for(int i=pos-1;i>=1;i--){

        if(HT[i].parent==0&&HT[i].weight<=HT[s1].weight)s1=i;//放个等于是想取下标小的后往前找

    }

    for(int i=pos-1;i>=1;i--)

        if(HT[i].parent==0&&HT[i].weight<=HT[s2].weight&&i!=s1)s2=i;

}

void CreatHT(HuffmanTree &HT,int n)

{//创建Huffman树

    if(n<=1)return;//**返回**

    int m=2*n-1;//总共2n-1个结点信息

    HT=new HTNode[m+1];

    for(int i=1;i<=m;++i)

    {

        HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;//所有设置为0

    }

    for(int i=1;i<=n;i++)//

        cin>>HT[i].weight;

    for(int i=n+1;i<=m;i++)

    {

        int s1,s2;//最小权值的下标信息s1,s2

        min(HT,i-1,s1,s2);

        HT[s1].parent=i;HT[s2].parent=i;

        HT[i].lchild=s1;HT[i].rchild=s2;

        HT[i].weight=HT[s1].weight+HT[s2].weight;

    }

}

void CreatHC(HuffmanTree HT,HuffmanCode &HC,int n)

{//创建哈夫曼编码:从结点-->根

    HC= new char*[n+1];//1-n所以n+1个

    char *cd=new char[n];

    cd[n-1]='\0';//**编码结束符**

    for(int i=1;i<=n;i++)//前面的是结点

    {   int start=n-1;

        int c=i,f=HT[i].parent;

        while(f!=0)//f=0是根结点

        {

            if(c==HT[f].lchild)cd[--start]='0';

            else cd[--start]='1';

            c=f;f=HT[c].parent;

        }

        HC[i]=new char[n-start];

        strcpy(HC[i],&cd[start]);//****

    }

    delete cd;

}

int main()

{//2n-1个结点

    HuffmanTree HT;

    HuffmanCode HC;

    int n,WPL=0,j;

    cin>>n;

    if(n>1){

        CreatHT(HT,n);

        CreatHC(HT,HC,n);

        for(int i=1;i<=n;i++)

        {

            cout<<HT[i].weight<<"编码为";

            for(j=0;HC[i][j]!='\0';j++)

                cout<<HC[i][j];

            WPL+=j*HT[i].weight;

            cout<<endl;

        }

        cout<<"WPL:"<<WPL;

    }

    else{

        cout<<"error";

    }

    return 0;

}