Estructuras de Datos I - TDA Lista Modelo

Vista previa del material en texto

Estructuras de Datos I
Lista Modelo
Tipo de dato abstracto (TDA)
ADT (Abstract Data Type)
Es un tipo de dato que se comporta conforme un conjunto de valores y un conjunto de operaciones.
La definición de un TDA solo hace el qué pero no hace mención del cómo, no especifica que algoritmos se implementan ni como se va a organizar los datos en memoria.
Se le llama abstracto porque nos da un modelo diferente a la implementación, es el proceso de proporcionar lo esencial y ocultar los detalles.
Lista
Es un tipo de dato abstracto que almacena información, de manera continua, del mismo tipo de datos, los elementos dentro de la lista no necesariamente pueden estar ordenados.
Los elementos de la lista pueden ser insertados en cualquier parte de la lista, así mismo, la eliminación de algún elemento de la lista puede efectuarse en cualquier parte de la misma, siempre y cuando se reasignen los elementos para cumplir con el almacenamiento continuo.
Declaración de una lista
La lista, deberá contener los siguientes métodos, también es recomendable que algunos regresen información (en su materia de Programación vieron FUNCIONES, es algo parecido).
	Operación	Regresa
	Inicializa	Nada
	Vacía	Booleano
	Llena *	Booleano
	Inserta	Nada
	Elimina	Nada
	Primero	Posición
	Ultimo	Posición
	Anterior	Posición
	Siguiente	Posición
	Busca	Posición
	Recupera	Elemento
	Ordena	Nada
	Imprime	Nada
	Anula	Nada
Métodos de Lista
Inicializa: Este método se asegura que la lista esta vacía y lista para ser utilizada, solo se llama una vez pues su función es dejar la lista en funcionamiento. Recibe la lista que se inicializará. No devuelve nada.
Vacía: Este método se asegura que la lista no tenga ningún elemento dentro. Recibe la lista a revisar. Devuelve VERDADERO si la lista esta vacía, si encuentra un o mas elementos devuelve FALSO.
Llena: Este método hace lo contrario a vacía, se asegura que la lista este completamente llena. Recibe la lista a revisar. Devuelve VERDADERO si la lista ya llego a su limite de elementos y en caso contrario, es decir, que exista al menos una posición libre, devuelve FALSO.
Métodos de Lista
Inserta: Este método coloca un elemento dentro de la lista, cuidando el almacenamiento continuo, dará error si la lista se encuentra llena. Recibe la lista, el elemento a insertar y la posición en la que se quiere insertar. No devuelve nada.
Elimina: Este método borra un elemento de la lista, reasignando los elementos que tiene delante y atrás para cuidar la continuidad de almacenamiento, da error si el elemento no se encuentra dentro o si la posición es invalida. Recibe la posición del elemento a eliminar y la lista donde esta ese elemento. No regresa nada.
Métodos de Lista
Primero: Este método revisa y almacena el primer elemento de la lista. Recibe la lista. Devuelve la posición del primer elemento y si la lista esta vacía da error.
Ultimo: Este método revisa y almacena el ultimo elemento de la lista. Recibe la lista. Devuelve la posición del ultimo elemento y si la lista esta vacía da error.
Anterior: Este método revisa y almacena el elemento anterior a una posición dada. Recibe la lista y una posición. Devuelve la posición anterior a la dada y da error si la lista esta vacía.
Siguiente: Este método revisa y almacena el elemento siguiente a una posición dada. Recibe la lista y una posición. Devuelve la posición siguiente a la dada y da error si la lista esta vacía.
Métodos de Lista
Busca: Este método revisa y determina la posición de un elemento, da error si no se encuentra o si la lista esta vacía. Recibe una posición y una lista. Devuelve la posición del elemento dentro de la lista.
Recupera: Este método recupera el elemento dado de la lista, da error si no se encuentra el elemento o la lista esta vacía. Recibe una posición y una lista. Devuelve un elemento.
Ordena: Este método ordena la lista. Recibe la lista. No devuelve nada.
Imprime: Este método imprime todos los elementos de la lista, da error si la lista esta vacía. Recibe una lista. No devuelve nada.
Anula: Elimina todos los elementos de la lista. Recibe una lista. No devuelve nada.
Información extra
TYPEDEF
Lo que realiza esta palabra reservada es cambiarle el nombre a un tipo de dato existente, ejemplo:
typedef int ENTERO;
Ahora la palabra reservada int se podrá utilizar si usamos la palabra ENTERO en su lugar.