Constructoras de tads

Constructoras de tads

de Ana Cichero Mildwurf -
Número de respuestas: 1

Buenas,

Capaz le estoy errando al foro...   Pero al mirar todo junto, parciales, exámenes, tareas hechas, prácticos tengo dudas respecto a cómo crear las estructuras vacías.

En la tarea:

Suponiendo definidos rep_estructura  y estructura_t , las operaciones de crear_estructura_vacia especificaban:  " Devuelve un estructura_t vacía (sin elementos) "

La duda era si había que  devolver la estructura vacía (sin elementos), o si devolver directamente null.  
((Esto a su vez implicaba al insertar contemplar aparte el caso inicial)) 
¿Cuál era la mejor opción ?

Sobre todo respecto a los tad árboles y listas, veo estudiando  los prácticos de estos tads , que aparecen como constructoras unas "cons" o "snoc" que justamente usan el paso inductivo para construir, ejemplo en un ab de elementos nat:

función consArbol : que crea un árbol no vacío a partir de un natural y otros dos árboles

 Si nos pidieran especificar e implementar abb por ejemplo ¿ Es lo mismo en el devolver vacío retornar null y hacer  new rep_estructura al insertar, que  devolver una estructura vacía  (sin elementos)  y luego insertar sobre la estructura creada ?

Espero que se entiendan las preguntas.    Gracias :)


En respuesta a Ana Cichero Mildwurf

Re: Constructoras de tads

de Fernando Fernandez -

Lo más importante es NO hacer una identificación de colección vacía con NULL. Que una colección sea vacía significa lo que ahí dice, que no tenga elementos.

Algunos ejemplos:

- Una pila no acotada se podría implementar con nodos enlazados y la pila vacía podría ser NULL.

- En general, una secuencia de nodos encadenados, ordenada o no, con la cual se puede implementar por ejemplo conjunto, mapping o lista con posiciones podría ser NULL si es vacía.

- En un árbol genérico (no es completo, no es acotado) es probable que convenga que el valor de la variable sea NULL.

Podría no serlo si además de mantener los nodos interesa algún otro dato, como por ejemplo la cantidad de nodos de todo el árbol (pero no de los subárboles), o un puntero a algún nodo especial distinto de la raíz. En este caso podría convenir que la variable de tipo árbol sea (un puntero a) una cabecera con un puntero a la raíz y el o los otros campos de interés. Al crear el árbol se podría crear la cabecera y por lo tanto nunca ser NULL.

Pero, repito, lo estándar es asignar NULL al crear el árbol.

- En una estructura acotada como un heap conviene pedir el arreglo de tamaño adecuado al crear el heap. Asignarle NULL inicialmente y esperar a la primera inserción para crear el arreglo con el objetivo de no ocupar memoria de manera innecesaria no parece de mucho provecho.

- Incluso en estructuras cuyo tamaño no es acotado puede convenir que no se asigne NULL al crearla. Por ejemplo, en cadena sugeríamos que se implementara con una cabecera con punteros al inicio y al final y que esa cabecera se creara al crear la cadena.

Esto lo vimos extensamente en clase pero es probable que haya una clase de consulta y podamos volver a verlo ahí.