(Programación en lenguaje C) Diseño Codificación Huffman
Esta cosa usa árboles de Huffman. Necesito que hagas un dibujo, así que te lo explicaré aquí.
Ya conoces el árbol, a estos 8 caracteres les das 8 nodos (dibuja un círculo y escribe la probabilidad dentro). Luego busque los dos más pequeños (0,03 y 0,05) como nodos de hoja y colóquelos en la parte inferior del árbol. Luego obtenga un nuevo nodo como nodo padre de estas dos hojas. La probabilidad dentro es 0,08. Luego use este 0.08 para reemplazar 0.03 y 0.05, de modo que solo queden 7. Luego encuentre las dos probabilidades más pequeñas, repita estos pasos y finalmente obtenga un árbol. La probabilidad de seguir el nodo es 1. Luego marca todos los nodos y las conexiones entre ellos, marcando 0 para la dirección izquierda y 1 para la dirección derecha. Luego, para los 8 nodos hoja, se puede obtener un código (compuesto por 0 y 1) de arriba a abajo, que es la codificación de Huffman.
Esta es una estructura de datos. Lo más importante es que a continuación se encuentra el código para el árbol de Huffman (no es exactamente igual a su pregunta, es solo como referencia).
#include
#include
#include
# incluir
#define LEN 8
#define MAXLEAF 8 // Número máximo de nodos hoja
#define MAXNODE (MAXLEAF*2) -1
typedef float ElemType;
typedef struct /* esta estructura almacena la información del código */
{
int start ; /* Almacena la posición inicial del código de derecha a izquierda (bit alto a bit bajo) */
int bit[LEN] /* Almacena el código huffman*/
typedef HCode HuffCode[MAXLEAF];
typedef struct /* estructura de nodos del árbol huffman*/
{
int padre;
int LChild;
int RChild;
Peso ElemType;
}HNode;
typedef HNode Huffman [MAXLEAF*2-1];
void createHuffmanTree(Huffman h,int hojas,ElemType *peso)
{
int i,j ;
p> for(i=0;i { (h +i)->padre=-1; (h+i)->LChild=-1; (h+i)->RChild=-1; (h+i)->weight=0; } for(i=0;i { (h+i)->peso=*(peso+i); } /* El La hoja del ciclo anterior ha sido correcta, el siguiente bucle se utiliza para generar nuevas raíces * El número de nuevas raíces es n-1 */ para (i=0;i { ElemType m1, m2; int m1_pos, m2_pos; m1=m2=65536; /* m1 almacena el peso más pequeño m2 almacena el segundo peso más pequeño */ m1_pos=m2_pos=0 /* m1 almacena el peso más pequeño correspondiente al subíndice m2 almacena el segundo peso más pequeño correspondiente al siguiente Estándar */ for(j=0 ;j { if((h+j)->peso { m2=m1; m1=(h+j)->peso; m2_pos=m1_pos; m1_pos=j; } else if((h+j)->peso { m2=(h+j)->peso; m2_pos=j; } } (h+leaves+i)->parent=-1; // Genera una nueva raíz sin parent-1 (h+leaves+i)->LChild =m1_pos; // El subíndice del hijo izquierdo de la nueva raíz en la matriz (h+leaves+i)->RChild=m2_pos; /p > (h+m1_pos)->parent=leaves+i; // La posición principal de la raíz original (h+m2_pos)->parent=leaves+i; El padre de la posición raíz original (h+leaves+i)->weight=m2+m1 } } { int i,j,p,c; HCode hf; / *Comienza desde el nodo hoja y retrocede hacia arriba para calcular el código Huffman */ for(i=0;i { c =i; p=h[i].parent; hf.start=LEN-1; while( p!=-1) { if(h[p].LChild==c) { hf. bit[hf.start]= 0; } else { hf.bit[hf.start]=1 ; } --hf.start; > c=p; p=h[c].parent; } for(j=hf.start+1;j { código[i].bit[j]=hf.bit[j]; } código[i].start=hf.start+1; } } void printhuffmantree(Huffman h,int hojas) { int i; for(i=0;i { printf("peso=%-3.2f",h[i].peso); printf("parent=%-3d",h[i].parent); printf("LChild=%-3d",h[i].LChild); printf("RChild=%-3d\n",h[i].RChild); } } void printhuffcode(HuffCode hcode,char caracteres[]) { int i ,j; for(i=0;i { printf("codificación huffman de %c:" ,caracteres[i]); for(j=hcode[i].start;j { printf("% d",hcode[i].bit[j]); } printf("\n"); } } int main(void) { Huffman h; HuffCode hcode; char caracteres[]={"abcdef"}; /* Caracteres a codificar*/ ElemTypeweights[]={0.3,0.7,0.4,0.5,0.9,0.1} /* Caracteres que aparecen */ createHuffmanTree(h,strlen(caracteres),pesos); printhuffmantree(h,strlen(caracteres)); huffmancode(h, hcode ,sizeof(caracteres)); printhuffcode(hcode,caracteres); system("pausa"); devuelve 0; }