[Código de diseño del curso de estructura de datos] escrito en lenguaje C, si la redacción es buena se sumarán 80 puntos, gracias]
{
unsigned int peso
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; * Matriz asignada dinámicamente para almacenar árboles de Huffman. */
typedef char **HuffmanCode; /* Matriz asignada dinámicamente para almacenar la tabla de códigos de Huffman*/
//* Buscar código de Huffman*/
# incluir "c1.h"
#include "c6-7.h"
#include" func6-1.c"
void HuffmanCoding(HuffmanTree * HT,HuffmanCode *HC,int *w,int n) /* Algoritmo 6.12 */
{ /* w almacena los pesos de n caracteres (todos > 0), construye el árbol Ha Huffman HT y encuentra n caracteres del código Huffman HC*/
int m,i,s1,s2,start;
unsigned c,f
HuffmanTree p; p>
char *cd;
if(n<=1)
retorno;
m=2* n-1; *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=*HT+1,i=1 ;i<=n;++i,+ +p,++w)
{
(*p).peso=*w
(*p).parent=0; p>
(*p).lchild=0;
(*p).rchild=0;
}
for(;i< =m;++i,++p)
(*p).parent=0;
for(i=n +1;i<=m;++i ) /* Crear un árbol de Huffman*/
{ /* Seleccione el nodo padre en HT[1 a i-1] como 0, con el peso más pequeño, dos nodos con números de serie s1 y s2*/
select(*HT,i-1,&s1,&s1,s2,s2,s2,s2) */
Seleccione(*HT,i-1,&s1, &s1,&s1,s2)/* Seleccione los dos nodos con el peso más pequeño.
(*HT)[s1].parent=(*HT)[s2].parent=i
(*HT)[i].lchild=s1; p>
p>
(*HT)[i].rchild=s2;
(*HT)[i].peso=(*HT)[s1].peso+(* HT)[s2] .weight;
}
.｝
/* Invertir el código Huffman de cada carácter desde la hoja hasta la raíz */
*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* Asigna un vector de puntero de cabeza para n codificaciones de caracteres (no se utiliza [0]) */
cd=(char*)malloc(n*sizeof(char)); /* Asignar espacio de trabajo para iniciar la codificación*/
cd[n-1]=' \0' ; /* Codificación del carácter final*/
for(i=1.i<=n;i++)
{ /* Huffman codificando carácter por carácter*/
start=n-1; /* posición del carácter final de codificación*/
for(c=i,f=(*HT)[i].parent;f!=0;c = f,f=(*HT)[f].parent)
/ * Codificación inversa de hoja a raíz*/
if((*HT)[f]. lchild ==c)
cd[--start]='0';
else
cd[--start]='1'; p>
(*HC)[i]=(char*)malloc(( n-start)*sizeof(char));
/* Asigna espacio para la codificación del i-ésimo carácter* /
strcpy((*HC)[i],&cd[start]); /* Copia la codificación (cadena) del cd a HC */
}
free(cd); /* Liberar el área de trabajo*/
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("Ingrese el número de pesos (>1): " )
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int)); "Ingrese %d número de pesos (entero) en orden:\n",n
for(i=0;i<=n-1;i++)
scanf("%d",w+i);
HuffmanCoding(&HT,&HC,w,n
for(i=1;i<=n;i++)
puts(HC[i]);
}
/* Recorrido no recursivo sin pila de árboles de Huffman para codificación Huffman* /
#include "c1.h"
#include "c6-7.h"
#include "func6-1.c"
void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC,int *w,int n) */
{ /* w save
El peso de n caracteres (todos 0), cree HuffmanTree HT y encuentre el HuffmanCode HC de n caracteres */
int m,i,s1,s2 /* Esta oración es la misma que algo6-; 1 .C es diferente. c */
unsigned c,cdlen /* Esta oración es diferente de algo6-1.
c */
HuffmanTree p;
char *cd;
if(n<=1)
retorno; >
m=2*n-1;
*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* Unidad 0 sin usar */
for(p=*HT+1,i=1;i<=n;++i,++p,++w)
{
(* p).peso=*w;
(*p).parent=0;
(*p).lchild=0; ).rchild=0;
}
for(;i<=m;++i,++p)
(*p).padre =0;
for(i=n+1 ;i<=m;++i) /* Crear árbol de Huffman*/
{ /* En HT[1 a i -1], seleccione dos nodos con el nodo principal 0, peso mínimo y números de secuencia s1 y s2*/
select(*HT,i-1,&s1,&s2); >(*HT)[s1].parent=(*HT)[s2].parent=i
(*HT)[i].lchild=s1; *HT)[i].rchild=s2;
(*HT)[i].peso=(*HT)[s1].peso+(*HT )[s2].peso; >
}
/* El siguiente es el algoritmo 6.13, que es un recorrido no recursivo sin pila del árbol de Huffman, utilizado para encontrar HuffmanCode, y es el mismo que el algoritmo 6.12 anterior * /
*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/ * Asignar un vector de puntero de cabeza ([0] no Usar) */
cd=(char*)malloc(n*sizeof(char));
c=m
cdlen=0; >
for(i=1;i<=m;++i )
(*HT)[i].weight=0; /* Se utiliza al atravesar el árbol de Huffman Crear indicador de estado de nodo */
mientras(c)
{
si((*HT)[c].peso==0)
{ /* a la izquierda*/
(*HT)[c].weight=1
if((*HT)[c].lchild!= 0)
{
c=(*HT)[c].lchild;
cd[cdlen++]='0';
else if((*HT)[c].rchild==0)
{ /* Registrar la codificación de caracteres en nodos hoja*/
(*HC)[c]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0'; strcpy((*HC)[ c],cd); /* Copiar codificación(cadena) */
}
}
else if( (* HT)[c].weight==1)
{ /* a la derecha*/
(*HT)[c].weight=2; p>if((*HT)[c].rchi
ld!=0)
{
c=(*HT)[c].rchild
cd[cdlen++]='1'; p> p>
}
}
else
{ /* HT[c].weight==2, return */
(*HT)[c].weight=0;
c=(*HT)[c].parent
-cdlen /* Devuelve el padre; nodo, codificación La longitud se reduce en 1 */
}
}
}
free(cd); >
}
void main()
{ /* El programa principal es el mismo que algo6-1.c*/
HuffmanTree HT;
HuffmanCode HC ;
int *w,n,i;
printf("Ingrese el número de pesos (>1):"); /p>
scanf(" %d",&n);
w=(int *)malloc(n*sizeof(int));
printf("Por favor ingrese %d número de pesos (entero) en orden:\n",n);
for(i=0;i<=n-1;i++)
scanf( "%d",w+i)
HuffmanCoding(&HT,&HC,w,n
for(i=1;i<=n;i++)
p>
pone(HC[ i]);
}