//Compresor y Descompresor de Archivos utilizando el algoritmo de Huffman
#include <stdio.h>
#include <stdlib.h>
#include "iostream"
#include "string"
using namespace std;
typedef struct _nodo
{ unsigned char letra;
int frecuencia;
struct _nodo* sig;
struct _nodo* cero;
struct _nodo* uno;
} tipoNodo;
typedef struct _tabla
{ unsigned char letra;
unsigned long int bits;
unsigned char nbits;
struct _tabla* sig;
} tipoTabla;
typedef struct _nodo_D
{ char letra;
unsigned long int bits;
char nbits;
_nodo_D* cero;
_nodo_D* uno;
} tipoNodo_D;
tipoTabla* Tabla;
void Cuenta(tipoNodo** Lista, unsigned char c);
void Ordenar(tipoNodo** Lista);
void InsertarOrden(tipoNodo** Cabeza, tipoNodo* e);
void BorrarArbol(tipoNodo* n);
void CrearTabla(tipoNodo* n, int l, int v);
void InsertarTabla(unsigned char c, int l, int v);
void BorrarArbol_D(tipoNodo_D* n);
tipoTabla* BuscaCaracter(tipoTabla* Tabla, unsigned char c);
// Funcion principal para descomprimir archivos
int Descomprimir(int argc, char* argv[]) // Descomprimir
{ tipoNodo_D* Arbol; // Arbol de codificación
long int Longitud; // Longitud del archivo
int nElementos; // Elementos de árbol
unsigned long int bits; // bits que se van a usar en la decodificación
FILE* fe, * fs; // archivos (ficheros) de entrada y salida
tipoNodo_D* p, * q;// arboles
unsigned char a;
int i, j; // enteros que sirven como ramas
if (argc < 4)
{ printf("Usar:\n%s <fichero_entrada> <fichero_salida>\n", argv[0]); return 1;
}
// se crea un arbol con la información de la tabla
Arbol = (tipoNodo_D*)malloc(sizeof(tipoNodo_D));
Arbol->letra = 0;
Arbol->uno = Arbol->cero = NULL;
fopen_s(&fe, argv[2], "rb");//se abre el archivo
fread(&Longitud, sizeof(long int), 1, fe); // se lee el número de caracteres
fread(&nElementos, sizeof(int), 1, fe); // se lee el número de elementos
for (i = 0; i < nElementos; i++)
{ p = (tipoNodo_D*)malloc(sizeof(tipoNodo_D));
fread(&p->letra, sizeof(char), 1, fe);
fread(&p->bits, sizeof(unsigned long int), 1, fe);
fread(&p->nbits, sizeof(char), 1, fe);
p->cero = p->uno = NULL;
j = 1 << (p->nbits - 1);
q = Arbol;
while (j > 1)
{ if (p->bits & j)
if (q->uno) { q = q->uno;
}
else
{ q->uno = (tipoNodo_D*)malloc(sizeof(tipoNodo_D));
q = q->uno;
q->letra = 0;
q->uno = q->cero = NULL;
}
else //si hay 0 nodos
if (q->cero) { q = q->cero; //si existe se mueve a este
}
else //sino se crea
{ q->cero = (tipoNodo_D*)malloc(sizeof(tipoNodo_D));
q = q->cero;
q->letra = 0;
q->uno = q->cero = NULL;
}
j >>= 1; //se mueve al siguiente bit
}
if (p->bits & 1)
q->uno = p;
else
q->cero = p;//al final se evalúa si hay uno o cero arboles
}
//lee los bits del archivo
bits = 0;
fopen_s(&fs, argv[3], "w");
fread(&a, sizeof(char), 1, fe);
bits |= a;
bits <<= 8;
fread(&a, sizeof(char), 1, fe);
bits |= a;
bits <<= 8;
fread(&a, sizeof(char), 1, fe);
bits |= a;
bits <<= 8;
fread(&a, sizeof(char), 1, fe);
bits |= a;
j = 0;
q = Arbol;
do {//se hace hasta que se termine el archivo if (bits & 0x80000000) q = q->uno; else q = q->cero;
bits <<= 1;
j++;
if (8 == j)
{ i = fread(&a, sizeof(char), 1, fe);
bits |= a;
j = 0;
}
if (!q->uno && !q->cero)
{ putc(q->letra, fs);
Longitud--;
q = Arbol;
}
} while (Longitud);
fclose(fs);
fclose(fe);//se cierran los archivos
BorrarArbol_D(Arbol);
return 0;
}
int Comprimir(int argc, char* argv[]) // Compresion
{ tipoNodo* Lista;
tipoNodo* Arbol;
FILE* fe, * fs;
unsigned char c;
tipoNodo* p;
tipoTabla* t;
int nElementos;
long int Longitud = 0;
unsigned long int dWORD;
int nBits;
if (argc < 4)
{ printf("Usar:\n%s <fichero_entrada> <fichero_salida>\n", argv[0]); return 1;
}
Lista = NULL;
fopen_s(&fe, argv[2], "r");//se abre el archivo
do { c = fgetc(fe);
if (feof(fe))
{ break;
}
Longitud++;
Cuenta(&Lista, c); //establece la frecuencia con la que aparece un caracter
} while (1);
fclose(fe);
Ordenar(&Lista);
Arbol = Lista; //se crea el arbol
while (Arbol && Arbol->sig)
{ p = (tipoNodo*)malloc(sizeof(tipoNodo)); //se crea otro arbol
p->letra = 0;
p->uno = Arbol;
Arbol = Arbol->sig;
p->cero = Arbol;
Arbol = Arbol->sig;
p->frecuencia = p->uno->frecuencia +
p->cero->frecuencia;
InsertarOrden(&Arbol, p); //un nuevo nodo se inserta
}
Tabla = NULL;
CrearTabla(Arbol, 0, 0);
fopen_s(&fs, argv[3], "wb");
//se abre el archivo comprimido
fwrite(&Longitud, sizeof(long int), 1, fs);
nElementos = 0;
t = Tabla;
while (t)
{ nElementos++;
t = t->sig;
}
fwrite(&nElementos, sizeof(int), 1, fs);//se escriben el numero de elementos y la tabla en el archivo
t = Tabla;
while (t) // para que t dibuje
{ fwrite(&t->letra, sizeof(char), 1, fs);
fwrite(&t->bits, sizeof(unsigned long int), 1, fs);
fwrite(&t->nbits, sizeof(char), 1, fs);
t = t->sig;
}
fopen_s(&fe, argv[2], "r");//se abre el archivo a comprimir
dWORD = 0;
nBits = 0;//valores iniciales
do { c = fgetc(fe);
if (feof(fe))
{ break;
}
t = BuscaCaracter(Tabla, c); //se busca en la tabla
while (nBits + t->nbits > 32)
{ c = dWORD >> (nBits - 8); //saca los 8 bits mas pesados
fwrite(&c, sizeof(char), 1, fs);
nBits -= 8; //se eliminan para tener más espacio
}
dWORD <<= t->nbits;
dWORD |= t->bits;
nBits += t->nbits;
} while (1);
while (nBits > 0)
{ if (nBits >= 8) c = dWORD >> (nBits - 8);
else c = dWORD << (8 - nBits);
fwrite(&c, sizeof(char), 1, fs);
nBits -= 8;
}
fclose(fe);
fclose(fs); //se cierran los archivos
BorrarArbol(Arbol);
while (Tabla)
{ t = Tabla;
Tabla = t->sig;
free(t);
}
return 0;
}
//Funciones extra para comprimir
void Cuenta(tipoNodo** Lista, unsigned char c)
{ tipoNodo* p, * a, * q;
if (!*Lista)
{ *Lista = (tipoNodo*)malloc(sizeof(tipoNodo));
(*Lista)->letra = c;
(*Lista)->frecuencia = 1;
(*Lista)->sig = (*Lista)->cero = (*Lista)->uno = NULL;
}
else
{ p = *Lista;//el nodo apunta a lista
a = NULL;
while (p && p->letra < c)
{ a = p; //se guardan los elementos
p = p->sig; //se va al siguiente elemento
}
if (p && p->letra == c) p->frecuencia++;
else
{ // Insertar un elemento nuevo
q = (tipoNodo*)malloc(sizeof(tipoNodo)); //se inserta el nuevo elemento
q->letra = c;
q->frecuencia = 1;
q->cero = q->uno = NULL;
q->sig = p;
if (a) a->sig = q;
else *Lista = q;
}
}
}
void Ordenar(tipoNodo** Lista)
{ tipoNodo* Lista2, * a;
if (!*Lista) return; // si la lista esta vacía
Lista2 = *Lista;
*Lista = NULL;
while (Lista2)
{ a = Lista2;
Lista2 = a->sig;
InsertarOrden(Lista, a); //inserta los elementos en orden
}
}
void InsertarOrden(tipoNodo** Cabeza, tipoNodo* e) //funcion para insertar caracteres en ordden
{ tipoNodo* p, * a;
if (!*Cabeza)
{ *Cabeza = e;
(*Cabeza)->sig = NULL;
}
else
{
p = *Cabeza;
a = NULL;
while (p && p->frecuencia < e->frecuencia)
{ a = p; //se guarda el elemento
p = p->sig; //se avanza
}
e->sig = p;
if (a) a->sig = e;
else *Cabeza = e;
}
}
void CrearTabla(tipoNodo* n, int l, int v)//funcion para crear la tabla
{ if (n->uno) CrearTabla(n->uno, l + 1, (v << 1) | 1);
if (n->cero) CrearTabla(n->cero, l + 1, v << 1);
if (!n->uno && !n->cero) InsertarTabla(n->letra, l, v);
}
void InsertarTabla(unsigned char c, int l, int v) //para insertar la tabla
{ tipoTabla* t, * p, * a;
t = (tipoTabla*)malloc(sizeof(tipoTabla)); //se crea el elemento
t->letra = c;
t->bits = v;
t->nbits = l;
if (!Tabla) //si tabla es NULL
{ Tabla = t;
Tabla->sig = NULL;
}
else
p = Tabla;
a = NULL;
while (p && p->letra < t->letra)
{ a = p;
p = p->sig;
}
t->sig = p;
if (a) a->sig = t;
else Tabla = t;
}
}
tipoTabla* BuscaCaracter(tipoTabla* Tabla, unsigned char c) //se busca el caraccter hasta que se encuentra y este es retornado
{ tipoTabla* t;
t = Tabla;
while (t && t->letra != c) t = t->sig;
return t;
}
void BorrarArbol(tipoNodo* n)
{ if (n->cero) BorrarArbol(n->cero);
if (n->uno) BorrarArbol(n->uno);
free(n);
}
void BorrarArbol_D(tipoNodo_D* n)//misma lógica usada anteriormente pero para el descomprimir
{ if (n->cero) BorrarArbol_D(n->cero);
if (n->uno) BorrarArbol_D(n->uno);
free(n);
}
void main(int argc, char* argv[])
{ //en el main se mandan a llamar las funciones char opcion = argv[1][0];
if (opcion == 'e')
{ //si se introduce e entonces se debe comprimir Comprimir(argc, argv);
printf("Proceso de compresion finalizado"); }
else {//sino se descomprime Descomprimir(argc, argv);
printf("Proceso de descompresion finalizado"); }
}
Crear cuenta