| 7.9.3. Árbol de cadenas de texto | ||
|---|---|---|
 | 7.9. Actividades |  |
| 7.9.3. Árbol de cadenas de texto | ||
|---|---|---|
| | 7.9. Actividades | |
En un programa en C necesita almacenar un número indeterminado de palabras. La estructura de datos seleccionada es un árbol binario en el que cada nodo almacena una palabra. Además, el árbol tiene la propiedad de que la palabra almacenada en cada nodo sigue lexicograficamente a las del sub-arbol izquierdo, y precede a las del sub-arbol derecho. La siguiente figura muestra un ejemplo de esta estructura de datos.
La aplicación necesita manipular varios conjuntos de palabras independientes.
Define las estructuras de datos necesarias para manipular estos árboles.
Define los prototipos de las siguientes funciones:
Función que crea un nuevo conjunto vacío.
Función que busca una palabra en un conjunto y la devuelve (la palabra devuelta se puede modificar).
Función que añade una palabra en un árbol. Si ya existe, no hace nada.
Función que destruye un árbol entero.
Función que borra una palabra de un árbol.
Escribe el método main que contenga un
bucle y mediante la función getline lea de teclado una
cadena y la inserta en dos árboles. El programa se detiene cuando
getline devuelve el valor NULL.
Dividir el trabajo en equipos y que cada uno haga uno de
los métodos de búsqueda, inserción o borrado de todos los elementos. La
función strcmp recibe como parámetros dos enteros y
devuelve un número menor, igual o mayor que cero si la primera palabra
precede, es idéntica o antecede a la segunda respectivamente.
Implementar la función de borrado de una cadena.
Responder a las siguientes preguntas:
Si comparamos esta estructura de datos con una lista encadenada de palabras, ¿qué estructura ofrece una inserción de nuevas palabras más eficiente?
¿Cómo comparan estas dos estructuras con respecto a la búsqueda?
Dos árboles contienen exactamente las mismas palabras. ¿Quiere decir esto que tienen idéntica estructura?
Si en la aplicación C que utiliza estas funciones, el 99% de las operaciones que se ejecutan son de búsqueda de palabras, ¿qué mejora propondrías a la estructura de datos para ganar eficiencia?
| |  | |
| 7.9.2. Lista encadenada de enteros |  | 7.9.4. Uso de listas encadenadas |