funcion en C

[Dana]

soy nueva en el forum y espero q puedan ayudarme con lo
siguiente :

escribir una funcion que acepte un string
el string contiene letras,sifras, *
cada cadena esta separada con #
la funcion debe "devolver " /return el largo de la sub cadena mas larga que es polindrome(se lee de la misma manera de los lados )
ejemplos :
abc#1221#abc**#121#235**/n {1221 es el polindrome } la funcion devolvera el numero 4 q es el largo de esa cadena


gracias y espero vuestra ayuda
talvez un algoritmo de como poder resolver ...


chau ....

--
Dana

-----------------------------------------------------------------------
Ver este tema: http://www.softwaremix.net/viewtopic-415302.htm

Enviado desde http://www.softwaremix.net

[Oscar Garcia]

El Sat, 23 Jul 2005 02:28:11 +0200, Dana

Post by Dana
escribir una funcion que acepte un string
el string contiene letras,sifras, * .
cada cadena esta separada con #
la funcion debe "devolver " /return el largo de la sub cadena mas larga que es polindrome(se lee de la misma manera de los lados )
abc#1221#abc**#121#235**/n {1221 es el polindrome } la funcion devolvera el numero 4 q es el largo de esa cadena .

Supongo que conocerás el dicho "divide y vencerás".

En vez de hacerlo todo en una función procura dividir las tareas en
distintas funciones.

Funciones:
* Dividir la cadena en subcadenas usando # como separador.
* Averiguar si una cadena es o no palíndromo.
* Averiguar la longitud de la cadena en caso de ser palíndromo.

La última es trivial y se corresponde con la función en C strlen.

La primera la podríamos implementar devolviendo la cadena mediante
listas o bien un array de punteros a cadenas, etc... Pero ya que no
necesitamos obligatoriamente almacenar en memoria las cadenas, podemos
obviar este paso y usar un "truco" en su lugar.

Dejando ese tema a parte veamos cómo quedaría la función que propones
tras dividirla en diferentes funciones a su vez:

// Devolverá -1 en caso de no existir ningún palíndromo
int log_palindromo(char *cadena, char separador) {
lista_cadenas *lista_de_cadenas, *actual;
int salida = -1;

// Obtenemos las cadenas en una lista simplemente enlazada
lista_de_cadenas = separa_cadena(cadena, separador);

// Buscamos en cada una de las cadenas si es o no un palíndromo
// Se podría reducir el for, pero lo dejo "extendido" para una mejor
// lectura
for (actual = lista_cadenas;
actual != NULL;
actual = siguiente_cadena(actual)) {
if (es_palindromo(siguiente->cadena)) {
salida = strlen(siguiente->cadena);
}
}
return salida;
}

Ahora el problema se reduce a crear una función que averigue si una
cadena es o no un palíndromo y a dos funciones que manejen listas de
cadenas.

Post by Dana
gracias y espero vuestra ayuda
talvez un algoritmo de como poder resolver ....

De nada.

[Oscar Garcia]

El Sat, 23 Jul 2005 09:55:30 +0200, Oscar Garcia

Post by Oscar Garcia
int log_palindromo(char *cadena, char separador) {
lista_cadenas *lista_de_cadenas, *actual;
int salida = -1;

Añadimos una entrada para la longitud de la cadena actual:
int longitud;

Post by Oscar Garcia
if (es_palindromo(siguiente->cadena)) {
salida = strlen(siguiente->cadena);
}

Cambiamos "salida = strlen(siguiente->cadena);" por:
if ((longitud = strlen(siguiente->cadena)) > salida) {
salida = longitud;
}

Me olvidé del sencillo algoritmo de comprobación de "si es mayor que
el máximo anterior" ;)

Otro saludo.
P.D.: Ahora te toca implementar el resto de funciones. Si tienes
problemas con alguna crea un hilo nuevo con el nuevo problema.

[Oscar Garcia]

El Sat, 23 Jul 2005 09:55:30 +0200, Oscar Garcia
<***@terra.es> escribió:
Una vez más he olvidado algo: crear y liberar los recursos de la lista

Post by Oscar Garcia
// Obtenemos las cadenas en una lista simplemente enlazada
lista_de_cadenas = separa_cadena(cadena, separador);

cadena = crear_eslabon();
// Obtenemos las cadenas en una lista simplemente enlazada
lista_de_cadenas = separa_cadena(cadena, separador);

Post by Oscar Garcia
return salida;
}

liberar_lista(lista_de_cadenas);
return salida;
}

Para ir ayudándote (por si no has visto en metodología de la
programación la implementación de listas) te ayudo con ese tema y dejo
de tu mano sólo la comprobación de si es o no un palíndromo y la
función que divida la cadena en subcadenas ;):

// Definimos una lista de un único sentido (enlazada simple)
typedef struct {
void *siguiente;
char *cadena;
} lista_cadenas;

Creamos la función que crea cadenas (el eslabón final ;):

lista_cadenas crear_eslabon() {
lista_cadenas *inicial;

inicial = malloc (sizeof (lista_cadenas));
if (inicial) {
inicial->cadena = inicial->siguiente = NULL;
}
}

Definimos la función "siguiente_cadena":

lista_cadenas siguiente_cadena (lista_cadenas *actual) {
return (lista_cadenas *)actual->siguiente;
}

Y la función que libera recursos:

void liberar_lista(lista_cadenas *lista) {
lista_cadenas *proxima;

// Por cada eslabón de la cadena libero la memoria
// usada por la cadena y por el eslabón en sí.
while (lista != NULL) {
proxima = siguiente_cadena(lista);
free(lista->cadena);
free(lista);
lista = proxima;
}
}

lista_cadenas insertar_eslabon(lista_cadenas *lista, char *cadena) {
lista_cadenas *nuevo = crear_eslabon();

if (nuevo) {
nuevo->siguiente = lista->siguiente;
nuevo->cadena = lista->cadena;
lista->siguiente = (void *)nuevo;
lista->cadena = malloc(strlen(cadena));
if (lista->cadena) {
strcpy(lista->cadena, cadena);
} else return NULL;
}
return nuevo;
}

Como puedes ver es una lista LIFO.

Basta con llamar a "insertar_eslabon" cada vez que encuentres una
cadena para insertar dicha cadena en la lista de la forma:

insertar_eslabon(cadena);

El valor de retorno siempre suelo usarlo porque soy escrupuloso con la
falta de memoria y los estragos que pueden producirse en caso de que
ocurra.

Un saludo.

[Oscar Garcia]

El Sat, 23 Jul 2005 09:55:30 +0200, Oscar Garcia

Post by Oscar Garcia
if (es_palindromo(siguiente->cadena)) {

Otro último detalle antes de que me llaméis "pesado" es que para
encapsular fielmente la lista debería haber usado otra función llamada
(por ejemplo) obtener_cadena:

if (es_palindromo(obtener_cadena(siguiente))) {

Donde:

char *obtener_cadena (lista_cadena *lista) {
return lista->cadena;
}

Y por último quedaría decir que lo que he implementado más que una
lista ha sido una pila.

Un saludo de nuevo (espero que sea el último por el momento x).

[Pedro Maicas]

Post by Dana
gracias y espero vuestra ayuda
talvez un algoritmo de como poder resolver ....

Lo mejor en estos casos es que alguien te de el
problema resuelto (yo voy a intentar hacerlo), así
no aprendes a resolverlo por tí misma y en un futuro
no podrás hacernos competencia en el trabajo, lo cual
es bueno para nosotros :-)

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//entrada => puntero a un buffer de caracteres donde está el string
// ojo ! el proceso modifica el buffer de entrada
int max_len_palindromo(char *buffer)
{
int max_len = 0;
int i, len;
char *q;

while(buffer){
q = strchr(buffer, '#');
if(q) *q++ = 0;
len = strlen(buffer);
if(len > max_len){
for(i=0;i<len/2;i++){
if(buffer[i] != buffer[len-1-i]) break;
}
if(i == len/2) max_len = len;
}
buffer = q;
}
return max_len;
}


cómo me gusta el C !





Saludos :-) -Pedro-

http://www.maicas.net/

e-mail en www.maicas.net

[Oscar Garcia]

Post by Pedro Maicas
Lo mejor en estos casos es que alguien te de el
problema resuelto (yo voy a intentar hacerlo)

Hombre, así me dejas mal. Yo intentando enseñar metodología para que
cuando tenga problemas que resolver más grandes pueda resolverlos de
forma eficiente y vas y me planchas (en el buen sentido de la palabra
:).

Me gusta ser limpio y transparente, de modo que propongo un par de
cambios al código:

Donde tienes:
if(q) *q = 0;
len = strlen(buffer);
if(len > max_len){

Y donde tienes:
}
*q++ = '#';
buffer = q;
}
return max_len;

Post by Pedro Maicas
cómo me gusta el C !

Ya somos dos (aunque yo hablaría de la programación en general :).

Un saludo y que se den bien las vacaciones.

[Oscar Garcia]

El Sat, 23 Jul 2005 19:24:50 +0200, Oscar Garcia

Post by Oscar Garcia
}
*q++ = '#';
buffer = q;
}
return max_len;

Joer con los fallos :/ creo que estoy ya demasiado viejo:

if (q) *q++ = '#';

Si no, en la última palabra cargaría con un precioso core dump a mis
espaldas x(

Un saludo.