哈夫曼编码(c++实现)

C/C++语言基础

下载此实例

开发语言：C/C++
实例大小：1.98KB
下载次数：12
浏览次数：282
发布时间：2020-04-16
实例类别：C/C++语言基础
发布人：593451592
文件格式：.cpp
所需积分：2

实例介绍

[下载地址]

【实例简介】

【实例截图】

from clipboard

【核心代码】

#include<iostream>
#include<math.h>
#include<ctime>
#include<stdlib.h>
#include<windows.h>
#include<iomanip>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#pragma warning(disable : 4996)

using namespace std;

struct Huffman
{
int weight;
Huffman* left;
Huffman* right;
char code[512];
};

bool sort_by_weight(Huffman *a,Huffman *b)
{
    Huffman* node_1 = a;
    Huffman* node_2 = b;
    return a->weight < b->weight;
}

void create(Huffman*& root,int a[],int n)
{
vector<Huffman*> tree_node;

    for (int i = 0; i < n; i ) {
        Huffman* node = (Huffman*)malloc(sizeof(Huffman));
        node->weight = a[i];
        node->left = NULL;
        node->right = NULL;
        tree_node.push_back(node);
    }
    while (tree_node.size() > 0)
    {
        sort(tree_node.begin(), tree_node.end(),sort_by_weight);
        if (tree_node.size() == 1)
        {
            root = tree_node[0];
            tree_node.erase(tree_node.begin());
        }
        else
        {

            Huffman* node_1 = tree_node[0];
            Huffman* node_2 = tree_node[1];

tree_node.erase(tree_node.begin());
tree_node.erase(tree_node.begin());

            Huffman* node = (Huffman*)malloc(sizeof(Huffman));
            node->weight = node_1->weight node_2->weight;
            if (node_1->weight < node_2->weight)
            {
                node->left = node_1;
                node->right = node_2;
            }
            else
            {
                node->left = node_2;
                node->right = node_1;
            }
            tree_node.push_back(node);
        }
    }
}

void output_pre(Huffman* node)
{
    if (node != NULL)
    {
        cout << node->weight;
        if (node->left != NULL&& node->right != NULL)
        {
            cout << '(';
            output_pre(node->left);
            cout << ',';
            output_pre(node->right);
            cout << ')';
        }
        else if(node->left == NULL && node->right == NULL)
        {
            output_pre(node->left);
            output_pre(node->right);
        }
    }
}

void getcode(Huffman*& node,string a)
{
    if (node->left == NULL && node->right == NULL)
        cout << a << ' ';
    else
    {
        getcode(node->left, a '0');
        getcode(node->right, a '1');
    }
}

int getWPL(Huffman*& node,int height)
{
    int WPL = 0;
    if (node->left == NULL && node->right == NULL)
    {
        return node->weight * height;
    }
    else
    {
        height = height 1;
        int WPL;
        WPL = getWPL(node->left, height) getWPL(node->right, height);
        return WPL;
    }
}

int main() {
    Huffman* root = NULL;
    int N;
    cin >> N;
    int* num = new int[N];
    for (int i = 0; i < N; i )
    {
        cin >> num[i];
    }
    create(root, &num[0], N);
    int b = 0;
    cout << getWPL(root, b) << endl;
    create(root, &num[0], N);
    output_pre(root);
    cout << endl;
    string a;
    create(root, &num[0], N);
    getcode(root, a);
}

标签： 编码

实例下载地址