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)
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)