关于哈夫曼编码的构建（闲来写）

静如疯猫
2026-09-12 12:02:23
发布于：天津
6阅读
0回复
0点赞
//哈夫曼树 优先队列 自动排序
//数组模拟指针
#include<queue>
#include<vector>
#include<string>
#include<iostream>
using namespace std;

struct Htree
{
    int data;
    int left,right;
    int f;                                              //频率
}huff[1000];

struct comp                                             //31行那个
{
    bool operator()(int i,int j)
    {
        return huff[i].f>huff[j].f;
    }
};

void print(int root,string str)                         //65行
{
    if(huff[root].left==-1&&huff[root].right==-1)
    {
        cout<<huff[root].data<<" "<<str<<endl;
        return;
    }
    if (huff[root].left!=-1)
        print(huff[root].left,str+"0");
    
    if (huff[root].right!=-1)
        print(huff[root].right,str+"1");
    
}

void buildhuff(char data[],int f[],int size)
{
    for (int i = 0; i < size; i++)
    {
        huff[i].data=data[i];
        huff[i].f=f[i];
        huff[i].left=huff[i].right=-1;
    }
    priority_queue<int,vector<int>,comp> nodes;         //优先队列
    for (int i = 0; i < size; i++)
    {
        nodes.push(i);                                  //点->队列
    }
    
    for (int i = 0; i < size-1; i++)                    //构建哈夫曼("-1"留出最后一个点)
    {
        int min1=nodes.top();
        nodes.pop();
        int min2=nodes.top();
        nodes.pop();
        
        huff[size+1]={0,min1,min2,huff[min1].f+huff[min2].f};
        nodes.push(size+i);
    }
    print(nodes.top(),"")
}

int main()
{
    int f[1000]={/*待填or输入or程序写入*/};
    char a[1000]={/*待填or输入or程序写入*/};
    int size=sizeof(a);

    buildhuff(a,f,size);
    
    return 0;
}
有帮助，赞一个
去预览
0/2000
这里空空如也
热门讨论
