前言

Snipaste_2019-11-19_09-22-38.png
这是数据结构第六次的试验,主要讲解了哈夫曼树,哈夫曼编码和解码

运行结果

首先构造哈夫曼树,依次输入
A 12、C 14、E 34、R 23、W 13
然后输出哈夫曼树查看结果
Snipaste_2019-11-19_09-19-56.png
接着查看编码
Snipaste_2019-11-19_09-20-11.png
然后解码
Snipaste_2019-11-19_09-20-19.png

代码

#include <iostream>
using namespace std;
#define N 10 //定义最大叶子结点个数
#define M 2*N-1 //结点最大个数
#define MaxValue 100 //最大权值
//树结点
typedef struct{
    char HFch;
    int weight;
    int parent,lchild,rchild;
}HufmTree;
//哈夫曼编码结点
typedef struct {
    char bits[N];
    char ch;
}CodeType;

HufmTree HFtree[M+1];
CodeType HFcode[N+1];

void Creat_HuffMan(int n) {
    int i, j, pL, pR;
    int w1, w2;
    for (i = 1; i <= (2 * n - 1); i++) {
        HFtree[i].weight = 0;
        HFtree[i].parent = 0;
        HFtree[i].lchild = 0;
        HFtree[i].rchild = 0;
    }
    //输入权值和代表结点的字符
    for (i = 1; i <= n; i++) {
        cout << "\n请输入结点字符和对应的权值:\n";
        cin >> HFtree[i].HFch;
        cin >> HFtree[i].weight;
    }
    for (i = n + 1; i <= 2 * n - 1; i++) {
        pL = 0;
        pR = 0;
        w1 = w2 = MaxValue;
        //从前n个子叶结点中选择俩个权值最小的
        for (j = 1; j < i; j++){
            if (HFtree[j].parent == 0 && HFtree[j].weight < w1) {
                w2 = w1;
                w1 = HFtree[j].weight;
                pR = pL;
                pL = j;
            } else if (HFtree[j].parent == 0 && HFtree[j].weight < w2) {
                w2 = HFtree[j].weight;
                pR = j;
            }
        }
        HFtree[pL].parent = i;
        HFtree[i].HFch = '#';
        HFtree[pR].parent = i;
        HFtree[i].lchild = pL;
        HFtree[i].rchild = pR;
        HFtree[i].weight = HFtree[pL].weight + HFtree[pR].weight;
    }
}
//哈夫曼树编码
void HuffManCode(int n){
    int i,k,m,c,p;
    CodeType cd;
    cout<<endl;
    cd.bits[n-1]='\0';
    for(i=1;i<=n;i++){
        for(k=0;k<=n-2;k++)
            cd.bits[k]=' '; //临时编码字符串前n-1个置为空格
        m=n-2;
        c=i;
        cd.ch=HFtree[i].HFch;
        p=HFtree[i].parent;
        while (p!=0){
            if(HFtree[p].rchild==c)
                cd.bits[m--]='1';
            if(HFtree[p].lchild==c)
                cd.bits[m--]='0';
            c=p;
            p=HFtree[p].parent;
        }
        HFcode[i]=cd;
    }
    cout<<endl;
    for(i=1;i<=n;i++){
        cout<<"字符"<<HFcode[i].ch<<"的编码是:"<<HFcode[i].bits<<endl;
    }
}
//哈夫曼树编码
void Decode(int n){
    int s,j;
    char b[10];
    cout<<"\n请输入二进制数:";
    cin>>b;
    j=0;
    s=2*n-1;
    cout<<"\n以下是哈夫曼树编码解码的过程:\n";
    while(b[j]!='\0'){
        if(b[j]=='0'){
            cout<<s<<"->"; //从根结点开始输出
            s=HFtree[s].lchild;
        }
        else{
            cout<<s<<"->";
            s=HFtree[s].rchild;
        }
        if(HFtree[s].lchild==0){
            cout<<"解码结果为:"<<HFtree[s].HFch; //输出编码对应的字符
            break;
        }
        j++;
    }
}
//输出哈夫曼树
void OutHuffMan(int n){
    int i;
    cout<<"\n\n序号\t结点\t权值\t双亲\t左孩子\t右孩子\n";
    for(i=1;i<=2*n-1;i++)
        cout<<i<<"\t"<<HFtree[i].HFch<<"\t"<<HFtree[i].weight<<"\t"<<HFtree[i].parent<<"\t"<<HFtree[i].lchild<<"\t"<<HFtree[i].rchild<<endl;
}
int main() {
    int choice;
    int n;
    while(1){
        cout<<endl<<endl<<endl;
        cout<<"******************\n\n";
        cout<<"1.建立哈曼夫树\n";
        cout<<"2.输出哈曼夫树\n";
        cout<<"3.哈曼夫树编码\n";
        cout<<"4.哈曼夫树解码\n";
        cout<<"0.退出\n\n";
        cout<<"******************\n\n";
        cout<<"\n输入你选择的功能序号:";
        cin>>choice;
        if(choice<0||choice>4)
            return (0);
        switch(choice){
            case 1:
                cout<<"\n请输入需要编码的字符个数:\n";
                cin>>n;
                Creat_HuffMan(n);
                break;
            case 2:
                OutHuffMan(n);
                break;
            case 3:
                HuffManCode(n);
                break;
            case 4:
                Decode(n);
                break;
            case 0:
                cout<<"\n程序结束,按任意键返回!\n";
                exit(0);
            default:
                break;
        }
    }
    return 0;
}
Last modification:May 27th, 2020 at 02:06 pm
如果觉得我的文章对你有用,请随意赞赏