Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: _*p en 18 Febrero 2011, 20:35 pm


Título: [C] Split
Publicado por: _*p en 18 Febrero 2011, 20:35 pm
Que tal, hace un tiempo trato de buscar una función split como la gente y no la encuentro... Y tampoco se me ocurre la forma de hacerla...

La elaboración de la función no es muy complicada, solo basta almacenar los tokens devueltos por strtok() o strsep() en un array... Y luego devolverlos, la cabecera de la función sería algo así:

Código
  1. char **split( const char *s1, const char *s2 );

Supongamos que en el main tenemos declarado:

Código
  1. char **tokens;

La asignación sería:

Código
  1. tokens = split( cadena, delimitador );

Pero previamente se debería haber reservado espacio para los tokens, y he aquí el problema, ya que ¿cómo sabremos la cantidad de tokens? ¿y el tamaño de cada una de ellos?... Podríamos reservar un espacio constante, pero podríamos desperdiciar memoria, o caer en un "segmentation fault" si faltase... ¿Cómo hacen otros lenguajes para hacer eficiente esta función?

Título: Re: [C] Split
Publicado por: oxydec en 19 Febrero 2011, 04:54 am
Esto igual te sirve http://luauf.com/2008/05/17/funcion-split-en-c/ (http://luauf.com/2008/05/17/funcion-split-en-c/)

el problema es que hace mucho uso de realloc() lo que implica un alto coste computacional, en los comentarios alguien propone otro codigo mas corto pero asi mirandolo por encima diria que no es mucho mejor pues creo que tiene la misma o mas alta complejidad computacional.

De todos modos no creo que eso sea un error de su programacion sino de la forma en que esta planteado el problema, pues al tener que devolver un array de cadenas sera necesario recorrer varias veces la cadena original y/o usar muchas veces la funcion realloc().

Para soluciuonar eso se me ocurre cambiar el prototipo de la funcion para que en vez de devolver un array de cadenas devuelva una lista enlazada de cadenas.

Título: Re: [C] Split
Publicado por: _*p en 19 Febrero 2011, 05:33 am
EDITADO: Gracias por la página!
Justamente, estaba tratando de hacer y luego de leer un poco sobre punteros a punteros en c, y reservación de memoria llegué al siguiente código, pero tengo un problema:


Código
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. char **split ( const char *s1, const char *s2) {
  6.  
  7.     char **lista;
  8.     char *aux = s1;
  9.     char *token_Ptr;
  10.     int i = 0;
  11.  
  12.     lista = (char **) malloc (sizeof (char *));
  13.     token_Ptr = strtok(aux, s2);
  14.     lista[i] = token_Ptr;
  15.     while(token_Ptr != NULL)
  16.     {
  17.         lista = (char **)realloc(lista, sizeof(char*) * (i + 1));
  18.         token_Ptr = strtok(NULL, s2);
  19.         i++;
  20.         lista[i] = token_Ptr;
  21.     }
  22.     return lista;
  23. }
  24.  
  25. int main ( int argc , char *argv[]) {
  26.  
  27.     char **MILISTA;
  28.     int i;
  29.  
  30.     if (argc==2) {
  31.         printf ("Cadena: '%s'\n",argv[1]);
  32.         MILISTA= split(argv[1]," ");
  33.         i=0;
  34.         puts("----------------TOKENS------------");
  35.         while (MILISTA[i]!=NULL) {
  36.             printf("%s, " , MILISTA[i++]);
  37.         }
  38.         printf("\n");
  39.         puts("----------------FIN---------------");
  40.     }
  41.     return 0;
  42. }

Código:
facu@linux:~/projects/spliting/bin/Debug$ ./spliting "HOLA MUNDO COMO s"
Cadena: 'HOLA MUNDO COMO s'
*** glibc detected *** ./spliting: realloc(): invalid next size: 0x09e12008 ***
======= Backtrace: =========
/lib/libc.so.6(+0x6c501)[0x17c501]
/lib/libc.so.6(+0x71c6d)[0x181c6d]
/lib/libc.so.6(realloc+0xe3)[0x181f53]
./spliting[0x8048573]
./spliting[0x80485fa]
/lib/libc.so.6(__libc_start_main+0xe7)[0x126ce7]
./spliting[0x8048471]
======= Memory map: ========
00110000-00267000 r-xp 00000000 08:06 8526       /lib/libc-2.12.1.so
00267000-00269000 r--p 00157000 08:06 8526       /lib/libc-2.12.1.so
00269000-0026a000 rw-p 00159000 08:06 8526       /lib/libc-2.12.1.so
0026a000-0026d000 rw-p 00000000 00:00 0 
00573000-0058d000 r-xp 00000000 08:06 251        /lib/libgcc_s.so.1
0058d000-0058e000 r--p 00019000 08:06 251        /lib/libgcc_s.so.1
0058e000-0058f000 rw-p 0001a000 08:06 251        /lib/libgcc_s.so.1
0065a000-0065b000 r-xp 00000000 00:00 0          [vdso]
007f1000-00815000 r-xp 00000000 08:06 8577       /lib/libm-2.12.1.so
00815000-00816000 r--p 00023000 08:06 8577       /lib/libm-2.12.1.so
00816000-00817000 rw-p 00024000 08:06 8577       /lib/libm-2.12.1.so
00c2d000-00d0c000 r-xp 00000000 08:06 660319     /usr/lib/libstdc++.so.6.0.14
00d0c000-00d10000 r--p 000de000 08:06 660319     /usr/lib/libstdc++.so.6.0.14
00d10000-00d11000 rw-p 000e2000 08:06 660319     /usr/lib/libstdc++.so.6.0.14
00d11000-00d18000 rw-p 00000000 00:00 0 
00e86000-00ea2000 r-xp 00000000 08:06 8518       /lib/ld-2.12.1.so
00ea2000-00ea3000 r--p 0001b000 08:06 8518       /lib/ld-2.12.1.so
00ea3000-00ea4000 rw-p 0001c000 08:06 8518       /lib/ld-2.12.1.so
08048000-08049000 r-xp 00000000 08:08 262453     /home/facu/projects/spliting/bin/Debug/spliting
08049000-0804a000 r--p 00000000 08:08 262453     /home/facu/projects/spliting/bin/Debug/spliting
0804a000-0804b000 rw-p 00001000 08:08 262453     /home/facu/projects/spliting/bin/Debug/spliting
09e12000-09e33000 rw-p 00000000 00:00 0          [heap]
b7700000-b7721000 rw-p 00000000 00:00 0 
b7721000-b7800000 ---p 00000000 00:00 0 
b7870000-b7873000 rw-p 00000000 00:00 0 
b7888000-b788b000 rw-p 00000000 00:00 0 
bf834000-bf855000 rw-p 00000000 00:00 0          [stack]
Abortado

 :huh:

Título: Re: [C] Split
Publicado por: _*p en 19 Febrero 2011, 15:55 pm
Bien el problema radicaba en que estaba haciendo un realloc() en i+1, y luego de haber reservado la memoria, yo estaba haciendo un postincremento, con el cual asignaba a la lista una cadena en memoria que no estaba reservada... Basta cambiar el postincremento... Era cuestión de lógica  :rolleyes:


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines