elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Top 20 herramientas Hacking más populares de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?  (Leído 1,489 veces)
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?
« en: 4 Enero 2017, 00:26 am »

¡Buenas!

He retomado un proyecto que empecé hace un tiempo sobre crear esctructuras de datos genéricas en C, y tengo alguna duda sobre qué tipo de dato debería devolver una búsqueda sobre una lista. La estructura contiene un puntero void* en el que se almacena el dato, y en un principio lo que estoy devolviendo en NULL si no encuentro el dato y void const* si lo encuentro para evitar modificar el dato (de momento estoy trabajando con listas ordenadas).

La cuestión es que este valor de retorno no da ningún tipo de información sobre la posicion que el elemento ocupa dentro de la lista, por lo que, por ejemplo, no se podría combinar una busqueda con la extracción de una sublista en caso de que haga falta seleccionar elementos dentro de un rango determinado. Si por el contrario utilizo un entero (lo más lógico sería un unsigned long) como valor de retorno, estaría limitando la cantidad de datos que se podrían almacenar al rango de valores de ese tipo de entero (un valor menos, teniendo en cuenta que tendría que escoger un valor de retorno, por ejemplo (unsigned long)(-1) para informar de que no ha habido ninguna coincidencia).

Otra alternativa sería buscar un elemento y devolver un puntero como comentaba antes, y en caso de que la búsqueda tuviese éxito utilizar una función que me devuelva la posición, pero seguiría existiendo la limitación sobre la cantidad máxima de datos que la lista podría contener.

Si alguna vez habéis trabajado con listas, ¿Cómo habéis enfocado el problema de la busqueda/posición de un elemento dentro de ésta?


« Última modificación: 4 Enero 2017, 00:30 am por do-while » En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
MAFUS


Desconectado Desconectado

Mensajes: 1.575



Ver Perfil
Re: Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?
« Respuesta #1 en: 4 Enero 2017, 19:19 pm »

¿Los elementos de la lista son todos iguales o puedes meter cualquier dato en ella?
La solución a la primera opción sería hacer una función que retornara dirección_elemento - dirección_raiz / tamaño_elemento.

Para la segunda gastarías un poco más de memoria y tiempo pues podrías generar un array dinámico con malloc y realloc de punteros a void* que sería tus elementos en la lista. Tus elementos sería otro tipo de dato que contendría un entero informando de su tamaño y un puntero a void* que apuntaría al dato en sí. Sí se complica un poco.
Para acelerar un poco las cosas podrías hacer bloques de 10 elementos (este número depende de lo rápido que crezca y decrezca tu lista). Cuándo fueras a introducir un datos más que el máximo de la lista haces un realloc y adquieres 10 posiciones más. A medida que vayas borrando vas dejando esas posiciones de la lsita a NULL, que te servirían para introducir más datos sin hacerla crecer; pero si has borrado más de 10 datos mueves los elementos a fin de compactarla y con realloc reduces la lista en 10 elementos.
Puedes encerrar dicha lista en un objeto donde podrías poner el tamaño real que tiene, el número de datos que tiene dentro. Así para moverte por ella podrías usar la típica notación de array y sabrías cuando parar. Cómo no puede haber un mayor número de posiciones de memoria que el que te marca un entero sin signo de la mayor palabra del procesador, y que nunca va a ser tan grande pues la compartes con el resto del sistema, pues lo tienes todo hecho.


En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.414


ASMático


Ver Perfil WWW
Re: Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?
« Respuesta #2 en: 4 Enero 2017, 23:39 pm »

Nunca he usado una lista queriendo saber la posición de los elementos. Para ello suelo escoger un array dinámico.

En cualquier caso, si quieres que la función de búsqueda retorne la posición, puedes hacer una estructura que almacene puntero al nodo y posición.

Si el conocer la posición es algo que usarás contadas veces, puedes hacer lo que comentas, de una función que diga la posición de un nodo en la lista.

Es tu lista, tú la usarás, y tú dirás cómo quieres que esté implementado. Lo más estándar que te puedo decir, es la implementación de la librería estándar, y ahí no te dice la posición. (Hay funciones que dan la posición dado un iterador, eso sí)
En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?
« Respuesta #3 en: 5 Enero 2017, 10:15 am »

¡Gracias por vuestras respuestas!

MAFUS, gracias por la idea, pero prefiero evitar el uso de vectores, la idea de la lista es que la posición de cada elemento puede estar en cualquier posición de la memoria y así evito la restricción que tendría un vector de utilizar posiciones consecutivas. Una reasignación del vector podría fallar en caso de no poder asignar suficientes posiciones consecutivas, con la lista tradicional bastaría con que hubiese espacio suficiente para un nodo más.

invancea96 es lo que había pensado, olvidarme de las posiciones.

También estoy pensando en utilizar un árbol valanceado de punteros a los nodos para apoyar las búsquedas, inserciones y eliminaciones. ¿Merece la pena el intercambio memoria/tiempo de ejecución? Recuerdo que de momento estoy con listas ordenadas, los elementos repetidos son consecutivos y el árbol tiene sentido para las tres operaciones, cuando implemente las listas "normales" en principio no habrá ningun orden y el árbol dejará de tener sentido a no ser que sea un árbol de listas y en cada nodo almacene una lista de los nodos de la lista en los que se repite cada elemento, y aún así solo serviría para búsquedas y eliminaciones.
« Última modificación: 5 Enero 2017, 10:29 am por do-while » En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
ivancea96


Desconectado Desconectado

Mensajes: 3.414


ASMático


Ver Perfil WWW
Re: Listas - ¿Cómo enfocaríais el valor de retorno de las búsquedas?
« Respuesta #4 en: 5 Enero 2017, 13:17 pm »

Puedes hacer todas las posibilidades :X
http://bigocheatsheet.com/#data-structures
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
_warn_unused_return_ pide retorno de valor en funcion void
Programación C/C++
Thelord 7 4,286 Último mensaje 9 Octubre 2010, 04:21 am
por Foxy Rider
[Duda] Valor de retorno main
Programación C/C++
apoeti 3 2,519 Último mensaje 12 Septiembre 2012, 16:16 pm
por apoeti
valor de Retorno
Programación C/C++
<<<-Basura->>> 3 1,827 Último mensaje 2 Enero 2014, 22:50 pm
por amchacon
Como procesa la maquina o el programa el valor de retorno??
Programación General
FKT 6 1,735 Último mensaje 9 Septiembre 2015, 16:43 pm
por FKT
Ayuda funciones con retorno de valor en C
Programación C/C++
omegadei 2 953 Último mensaje 21 Marzo 2018, 20:04 pm
por omegadei
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines