Programación de codificación Huffman en c++

Este es el código que escribí cuando estaba estudiando algoritmos en el pasado. Puedes cambiar ligeramente la interfaz, es decir, simplemente cambiar la entrada de lectura para cumplir con los requisitos de tu pregunta:

El código principal:

#ifndef _HUFFAM

#define _HUFFAM

#include

#include

#include

#include

usando el espacio de nombres std;

/********* *** *

Esta función de codificación de Huffman está escrita usando plantillas

Puede realizar codificación básica en algunos tipos como tipo int, tipo char y tipo cadena

****************/

plantilla

estructura TreeNode

{

TreeNode()

{

lchild=rchild=0;

}

int frecuencia;

T ch;

TreeNode *lchild;

TreeNode *rchild

};

// La función de operador sobrecargado que cambia la prioridad predeterminada de la cola de prioridad se sobrecarga como una función global

template

operador bool >(const TreeNode< T> & left ,const TreeNode &rigth)

{

return (left.frequrcy>rigth.frequrcy);

}

plantilla

TreeNode huffman(vector< TreeNode > &c)

{

size_t n=c. tamaño();

TreeNode huffamNode;

prioridad_queue, vector >, mayor > > q;

//Inserta todos los nodos en la cola de prioridad

for(int i=0;i(n);i++)

{

huffamNode=c[i];

//huffamNode.lchild=huffamNode.rchild=0;

q.push(huffamNode);

}

//Código central, proceso de construcción del árbol

for(int i=0;i(n-1);i++)

{

T

reeNode *tempNode=nuevo TreeNode;

TreeNode *xNode=nuevo TreeNode;

TreeNode *yNode=nuevo TreeNode< T>;

xNode->frequrcy=q.top().frequrcy;

xNode->ch=q.top().ch

xNode->lchild=q.top().lchild;

xNode->rchild=q.top().rchild

tempNode->lchild=xNode; >

q.pop();

yNode->frequrcy=q.top().frequrcy;

yNode->ch=q.top().ch;

yNode->lchild=q.top().lchild;

yNode->rchild=q.top().rchild

tempNode->; rchild=yNodo;

q.pop();

tempNode->frequrcy=xNodo->frecuencia+yNodo->frecuencia;

q.push( *tempNode);

}

return q.top();

}

// Función de codificación de salida, esta recursión I No me gusta el método, así que lo reescribí después de un tiempo

template

void printHufman(TreeNode *root,string s)

{

if(root->lchild!=0)

printHufman(root->lchild,s+"0");

if( root->rchild !=0)

printHufman(root->rchild,s+"1");

if(root->rchild==0&&root->lchild==0 )

cout<<"Objeto codificado"<ch<<" "<<"Frecuencia"<frequrcy<<" "<<"Codificado como"<

}

#endif _HUFFAM

Código de prueba:

#include

#include< vector>

#include

#include

#include"huff

am.h"

usando el espacio de nombres std;

int main()

{

//Datos de tipo de cadena de prueba, frecuencia It es la secuencia de Fibonacci

TreeNode w[6];

vector > v1;

w[0]. 1;

w[0].ch="sd";

w[1].frequrcy=1;

w[1]. "hjg";

w[2].frequrcy=2;

w[2].ch="jghg";

w[3 ]. frecuencia=3;

w[3].ch="jgh";

w[4].frequrcy=5;

w[4 ]. ch="ui";

w[5].frequrcy=8;

w[5].ch="lk";

copiar (w ,w+6,back_inserter(v1));

TreeNode re=huffman(v1);

cout<<"El resultado de la codificación es"<

printHufman(&re,"");

cout<

//La codificación según los datos del libro de texto es la siguiente

TreeNode v[6];

v[0].frequrcy=5;

v[0].ch=1;

v [1].frequrcy=9;

v[1].ch=3;

v[2].frequrcy=12;

v [2 ].ch=6;

v[3].frequrcy=45;

v[3].ch=4;

v[4 ]. frecuencia=16;

v[4].ch=2;

v[5].frequrcy=13;

v[5]. ch= 34;

vector> charv;

copiar(v,v+6,back_inserter(charv));

TreeNode< int> charre=huffman(charv);

cout<<"El resultado de la codificación es "<

printHufman(&charre,"");

devolver 0;

}