Programacion De Listas

LISTAS 2002
GRUPO # 22
Alumnos: Aguilar Elba Barrios Miguel Camacho Yaquelin Ponce Rodríguez Jhonny

ESTRUCTURAS DE DATOS

TEMA 5 Estructura de datos Lista

Tema 5. Estructura de datos Lista

E04. Estructuras de datos I

ÍNDICE
5.1. Definición ............................................................................................................3 5.2. El TAD Lista.......................................................................................................3 5.3. Implementaciones del tipo Lista..........................................................................5 5.3.1. Implementación estática mediante un vector ........................................5 5.3.2. Implementación dinámica de una lista con enlace simple ....................8 5.3.3.Implementación dinámica como lista doblemente enlazada ...............17 5.4. TAD's relacionados con la Lista........................................................................20 5.4.1. TAD Lista Ordenada ...........................................................................20 5.4.2. TAD Multilista ....................................................................................23 5.5. Ejercicios...........................................................................................................24

BIBLIOGRAFÍA
• (Joyanes y Zahonero, 1998), Cap. 5 y 6. • (Joyanes y Zahonero, 1999), Cap. 4. • (Dale y Lilly, 1989), Cap. 6 y 7. • (Horowitz y Sahni, 1994).

OBJETIVOS
• Conocer el concepto, funcionamiento y utilidad del tipo Lista. • Conocer el TAD Lista y sus operacionesasociadas. • Saber implementar una lista mediante variables estáticas. • Saber implementar una lista mediante variables dinámicas. Conocer distintas implementaciones dinámicas del tipo, utilizando simple y doble enlace. • Conocer el TAD Lista ordenada y su implementación mediante variables dinámicas. • Conocer el concepto y utilidad de las multilistas.

Tema 5. Estructura de datos Lista

E04.Estructuras de datos I

5.1. Definición
Al igual que ocurría en el caso de la pila y la cola, estamos bastante familiarizados con el concepto de lista. Si pensamos por ejemplo en una lista de la compra, o en una guía telefónica, estamos manejando listas. En el primero de los casos, los elementos no tienen porque estar ordenados por su valor, mientras en el segundo se ordenan según un índice alfabético.No obstante, en ambos casos estamos hablando de listas de elementos. En el caso de las estructuras de datos, definiremos una lista del siguiente modo: Definición Una lista es un conjunto ordenado de elementos homogéneos en la que no hay restricciones de acceso, la introducción y borrado de elementos puede realizarse en cualquier posición de la misma. Junto con la pila y la cola, la lista formaparte de lo que se denominan estructuras lineales. Intuitivamente son estructuras en los que los distintos elementos se sitúan en línea, de ahí su nombre. Dicho de otro modo, cada elemento de una estructura lineal, salvo el primero y el último, tan sólo tiene un anterior y un siguiente. La diferencia entre estos tres tipos de estructuras lineales radica en las restricciones impuestas en el acceso alos elementos. • En una pila los elementos tan sólo pueden añadirse y borrarse por uno de sus extremos. • En una cola, los elementos se añaden por un extremo y se borran por el otro. • En una lista, los elementos pueden añadirse y borrarse en cualquier posición, no sólo en los extremos. De un modo más formal, una lista es un triplete ( P,R,v ) en donde: • P: es un conjunto de posiciones, enparticular un conjunto de posiciones que contienen datos en la lista. • R: es una relación de orden sobre el conjunto P. Los elementos se sitúan en línea (orden), no se ordenan sus valores. • v: es una función de evaluación, que para cada posición P define el valor del dato almacenada en la misma.

5.2. El TAD Lista
En este apartado vamos a ver una posible definición del TAD Lista. En este caso...