Tad Arboles Y Tablas

ÍndicE


ANÁLISIS DEL PROGRAMA 3

DISEÑO DE LA APLICACIÓN 5

LISTADO DE CÓDIGO 7
➢ Producto.h………………………...………………………………………………………………................7
➢ Producto.cpp…………………….….…………………………………………………………….................8
➢ Palabra.h…………………………….……………………………………………………………………..10
➢ Palabra.cpp…………………….…………………………………………….…………………………….11
➢Precio.h…………………….………………...…………………………………………………………….13
➢ Precio.cpp…………….……………………………………………………………………………………14
➢ Nodo.h…………….………………………………………………...……………………………………..17
➢ Nodo.cpp……..…………………………………………………………………………………………….18
➢ ListaPalabras.h..………………………………………...………………………………………………….20
➢ ListaPalabras.cpp……..….…………………………………………………….……………………….….21
➢ ListaProductos.h..…….…….…………………………………………………….…………………….….22
➢ListaProductos.cpp……..……………………………………………………………………………….….23
➢ TablaHash.h……….……………………………………………………………………………………….25
➢ TalbaHash.cpp.…………………………………………………………………………………………….26
➢ Árbol.h………………….………………………………………………………………………………….27
➢ Árbol.cpp………….……………………………………………………………………………………….28
➢ Comando.h………..………………………………………………………………………………………..32
➢ Comando.cpp……..………………………………………………………………………………………..33
➢Main.cpp……………………………..…………………………………………………………………….36
➢ Makefile…………………………..……………………………………………………………………….37



INFORME DE DESAROLLO 37

CONCLUSIONES Y VALORACIONES PERSONALES 38
















Análisis del problema


En la implementación de la práctica aparecen diversos tipos abstractos de datos que se muestran a continuación:

• Producto: El TAD Producto se presenta al inicio de lapráctica, bajo la necesidad de representar un producto; su identificador, nombre, descripción y precio.
Las operaciones principales son las de leer y mostrar un producto.

• Lista de Productos: El TAD Lista Productos se implementa como estructura de almacenamiento de la clase Producto. Sus operaciones principales son las de insertar, la cual insertar un producto de forma ordenada por ID yeliminar un producto.

• Palabra: El TAD Palabra surge de la implementación de la búsqueda de productos. Este tipo se compone de la palabra y su número de apariciones en la lista de productos. Además, incluye una lista de punteros a Producto; por lo que cada palabra tiene una relación de los productos en los que aparece.

• Lista de Palabras: El TAD Lista Palabras se implementa comoestructura de listas enlazadas para el almacenamiento de la clase Palabra.

• Tablas de dispersión: El TAD Tabla Hash aparece para optimizar nuestra aplicación con una estructura más eficiente que una lista para el almacenamiento de las palabras. La tabla de dispersión que se implementa es de dispersión abierta, con un número máximo de cubetas de 2048. Se escoge este tipo de dispersión puestoque no se conoce de antemano el número de elementos que se insertan, y se podría incurrir en un malgasto de memoria si se fija un número de cubetas demasiado grande, o que faltase espacio si es demasiado pequeño. Los elementos que se almacenan en las cubetas son del tipo punteros a Lista Palabras, ya que los sinónimos deben almacenarse en la misma cubeta.
La opción poner el numero de cubetasen Potencia de 2 es que a bajo nivel se implementarían menos instrucciones a la hora de hacer el modulo, que si lo hacíamos con un valor primo.
También en este TAD nos vimos obligados a crear un método que nos gestione las intersecciones de varias listas, para cuando se consulta los productos que tienen varias palabras en común.

• Árbol AVL: El TAD Árbol es el que gestionara toda laestructura de nodos; partiendo desde un nodo raíz y apuntando a 2 nodos que a su vez se consideran subarboles del primero.
La gestión de la estructura del árbol se hace insertar Productos con un precio, si no existe un nodo con dicho precio se crea y se re-balancea el árbol, pero si existe solo se inserta en la...