Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: iretchai en 7 Noviembre 2020, 14:49 pm



Título: COMPRESOR LZ78
Publicado por: iretchai en 7 Noviembre 2020, 14:49 pm
Hola buenas!
Necesito ayuda con el algoritmo de un programa (en C++) que tiene que hacer lo siguiente:

Un programa que, en primer lugar, lea de la entrada estándar (cin) una cadena
de caracteres, formada por aes y bes únicamente, y escriba en la salida estándar (cout) el
resultado de comprimirla conforme al algoritmo LZ78; esto es, una secuencia de números
enteros y caracteres (a, b) alternados.

Ejemplos de ejecución:
CIN    >> ababbabaaabaaabba
COUT << 0a0b1b2a4a3a1a2b1

El esquema que he pensado es el siguiente:

Hacer que el cursor señale al primer carácter de la cadena de entrada
inicializar el diccionario con la palabra vacía: w(0) = "" y npal = 1

Mientras quedan caracteres por tratar (el cursor señala a un carácter)

-- buscar la palabra w(i) más larga del diccionario que coincide con los
    primeros caracteres de la cadena a partir del señalado por el cursor

-- escribir en la salida el entero i

-- si quedan caracteres por tratar,
     -- sea c el carácter señalado por el cursor
     -- escribir en la salida el carácter c
     -- añadir al diccionario la palabra w(npal) = w(i)c
     -- npal = npal+1

NOTAS: El diccionario es un array bidimensional dicc [100] [100], para simular un array unidimensional de palabras.
            Se incluye la biblioteca <cstring> y hay que usar las funciones: strstr, strcpy, strlen, strcat.
            El cursor puede ser un puntero char *cursor=cadena o también se puede usar directamente cadena(i)




Título: Re: COMPRESOR LZ78
Publicado por: AlbertoBSD en 8 Noviembre 2020, 20:55 pm
No se hacen tareas.

Saludos!