Ayuda para escoger una estructura de datos apropiada

Estado
Cerrado para nuevas respuestas.
B

bo0m3r4n9

Lanero Regular
6 Sep 2003
39
Tengo una pregunta acerca de cómo hacer mejor una cosa…….. resulta que tengo un archivo “diccionario.txt” de aprox. 60000 definiciones; y tengo que ordenarlo de dos formas y medir cuanto se demora en cada una; bubblesort y quicksort. En cualquiera de los dos casos, primero debo cargar todo el diccionario a memoria, no? Ahora, la pregunta es, que estructura de datos utilizo para almacenarlo?? En java yo diría de una que un array de Strings, o de pronto un Vector, en fin…. Pero resulta que debo hacerlo en C++, en donde hay mas posibilidades….. les pregunto como lo harían…… acaso una matriz de caracteres??? Declarándola como “ char** ” (o estoy miando fuera y lejos del tiesto??) o “char [] []” (en este ultimo caso necesitaría conocer el número total de definiciones?? Y también el máximo número de caracteres que podría tener una definición??)

Y otra pregunta.... existe algun método en la STDLIB que me permita comparar dos string para ver cual de las dos es menor (cual iría primero si las organizara alfabeticamente)??

Thanx a lot!!!
 
Por partes:

No, no es necesario cargarlo todo en memoria, se puede realizar accediendo al archivo varias veces, pero se demoraria mucho

Las funciones para trabajar con strings estan en .... string.h, para compararlas, creo que es strcmp()

Yo personalmente lo haria con una lista ... ah no, es muy complejo cuano se reorganizan ...... con un array de char * deberia funcionar
 
no estoy muy segfuro... pero deberias de utilizar memoria dinamica... Listas dobles por ejemplo... no?

PD. No es que sepa mucho de C++ pero hago esta respuesta con el fin de obtener ayuda también... Para tu problema yo apuntaría más bien a la memoria dinámica.... Entonces pienso que lo mejor es por listas o por otra estructura que uno como programador considere la más adecuada según el problema...
 
char midiccionario[60000][maximo_tamano_de_palabra] ;

if (strcmp(midiccionario, midiccionario[j]) > 0)
... blah blah blah

qsort(midiccionario[0], maximo_tamano_de_palabra, 60000, strcmp) ;

PD. Irse por listas dinamicas no es recomendable por los metodos de ordenamiento que esta utilizando, ahora me da pereza mirar como funcionan ese par de metodos, pero si mi memoria no me falla (vi eso en 1990) ambos son basados en la posicion del elemento dentro del arreglo (arreglo[posicion]) por lo tanto con listas se sacaria un ojo. De todas formas ud es el que estaba en la clase y debio poner mas cuidado ;)
 
No seria pasar el fichero de texto a una base de datos como la de access, y luego mediante el c++ crear un objeto y ligarlo a la base de datos? Por lo menos creo que es mejor.
 
Tambien puede:

struct {
char palabra[tamano_de_palabra] ;
char definicion[tamano_de_definicion] ;
} diccionario[60000] ;

Por que me imagino que tiene que meter las definiciones tambien.
 
Texto Originalmente Escrito por Krieg
Tambien puede:

struct {
char palabra[tamano_de_palabra] ;
char definicion[tamano_de_definicion] ;
} diccionario[60000] ;

Por que me imagino que tiene que meter las definiciones tambien.
Haz clic para expandir...

Ojo, creo que este codigo solo le funciona si usa un compilador de 32bits, si esta usando un o de 16 bits, el Turbo C por ejemplo, le manda un error de estructura muy grande.
 
Pues yo estoy de acuerdo con JulianD, creo que lo mejor es usar una lista doblemente enlazada ya que a medida que vas ordenando las palabras solamente debes mover los dos punteros de cada palabra para cambiarla de posicion y seria mas eficiente que por ejemplo tratar de mover una palabra al principio del diccionario.
 
Texto Originalmente Escrito por atk_pantera
Pues yo estoy de acuerdo con JulianD, creo que lo mejor es usar una lista doblemente enlazada ya que a medida que vas ordenando las palabras solamente debes mover los dos punteros de cada palabra para cambiarla de posicion y seria mas eficiente que por ejemplo tratar de mover una palabra al principio del diccionario.
Haz clic para expandir...

Totalmente en desacuerdo, una lista doblemente enlazada (o simplemente enlazada) es muy lenta para indexarla, acuerdense que el algoritmo del qsort requiere indexar mucho elemento i-1, etc ... se acuerdan? ... un array es una eleccion mas eficiente.

Entonces para accesar el elemento 5 de la lista enlazada toca hacer un recorrido, el array referencia de una al elemento.
 
Texto Originalmente Escrito por El_Rulas
Totalmente en desacuerdo, una lista doblemente enlazada (o simplemente enlazada) es muy lenta para indexarla, acuerdense que el algoritmo del qsort requiere indexar mucho elemento i-1, etc ... se acuerdan? ... un array es una eleccion mas eficiente.

Entonces para accesar el elemento 5 de la lista enlazada toca hacer un recorrido, el array referencia de una al elemento.
Haz clic para expandir...


Correcto. Es que esta gente no lee lo que uno dice.

A ver como intercambia la posicion 33.648 con la 56.724 en una lista.

for (ptr = p33.648 ; ptr = ptr->next ; ptr != p56724) ;

juassssssss
 
A menos que el algoritmo deje de ser quick sort y se convierta en slow sort.
 
Estado
Cerrado para nuevas respuestas.

Los últimos mensajes

Los últimos temas

Arriba Pie
Atrás