Tda listas

Algoritmos y Estructuras de Datos I

CAPITULO 2: TIPOS DE DATOS ABSTRACTOS Definición: Modelo matemático con una colección de operadores definidos sobre dichos modelos.

Beneficios de los TDA: Encapsulamiento: Definir en un solo lugar todas las instrucciones relevantes a ciertos aspectos del programa. Desacoplamiento de la programación: ya que los operadores están predefinidos, igual que lostipos de datos más complejos. Formalmente el TDA es una tripleta (D, F, A) con las siguientes componentes:

1. Un conjunto de dominios D. 2. Un conjunto de funciones sobre los dominios F. 3. Un conjunto de axiomas o propiedades definidas a partir de las funciones y elementos de los dominios A.

2.1 Tipo de datos abstracto Lista Las listas se componen de una colección de elementos organizadosen secuencia que pueden crecer y decrecer libremente y a cuyos elementos se puede acceder, insertar y eliminar en cualquier posición.
1

Algoritmos y Estructuras de Datos I

a1, a2, a3,…., an con n>=0 La principal propiedad de las listas se debe a su estructura lineal, los elementos pueden ser linealmente ordenados de acuerdo con su respectiva posición en la lista.

2.1.1 Definición del TDALista

Se definirán a continuación los dominios, las operaciones y axiomas que interesan para manejar las listas.

Dominio Se tiene los siguientes tipos de datos: L: Lista de objetos del tipo elemento. x: Objeto del tipo elemento. p: Objeto de tipo posición (depende de la implementación, usualmente es un entero).

El conjunto de dominios es: D ={Lista, dato, num_nat}

Donde: L∈ Lista. x∈dato (tipo elemento). p∈ num_nat

2

Algoritmos y Estructuras de Datos I

Funciones Se definen las siguientes funciones: 1. Insertar (x, p, L) => L: Insertar el elemento x en la posición p de la Lista L, poniendo los elementos siguientes a continuación. 2. Localizar (x, L) =>p: Entrega la posición de x en la lista L. 3. Recuperar (p, L) =>x: Entrega el elemento que está en la posición p enla Lista L. 4. Eliminar (p, L) =>L: Elimina el elemento de la posición p de la lista L. 5. Siguiente (p, L) =>p y Anterior (p, L) =>p: Devuelve la posición siguiente y anterior a p de L respectivamente. 6. Anular (L) =>L: Vacía la lista. 7. Primero (L) =>p: Entrega la primera posición de L. 8. Fin(L)=>p: Entrega la posición después del último elemento (n+1).

Axiomas Algunos axiomas que sepueden mencionar son: Localizar(x, Insertar(x, p, L)) = Si (x∉ L) entonces retornar p Recuperar(p, Insertar(x, p, L)) = x Recuperar(Fin(L),L)=error Eliminar(Fin(L),L)=error Anterior(Primero(L),L)=error

3

Algoritmos y Estructuras de Datos I

2.1.2 Implementaciones de las Listas

Existen 3 formas principales de implementar el tipo de dato abstracto lista: arreglos, punteros y cursores.

a)Implementación por arreglos En este caso los elementos se almacenan en celdas contiguas de un arreglo. En la parte no ocupada del arreglo se tiene espacio libre. Se define la constante longitud máxima, que determina el tamaño de la mayor lista que se procesa. 0 1 2 . . . Ultimo-1 Ultimo elemento Último Espacio Libre
Longitud Máxima

Propiedades de la implementación con arreglos: Fácil derecorrer Fácil de agregar y eliminar al final Complicado insertar y eliminar al medio de la lista. Tamaño máximo prefijado.
4

Algoritmos y Estructuras de Datos I

Declaraciones: #define long_max 200 struct lista { tipo_elem elem[long_max]; int ultimo; } Para crear una lista se usa la siguiente función, que genera una lista inicialmente vacía: struct lista *crear(){ struct lista *L=malloc(sizeof(struct lista)); L → ultimo=0; return L; }

5

Algoritmos y Estructuras de Datos I

Ejemplo: Insertar un elemento x en la posición p de la lista L

struct lista *insertar(tipo_elem x, int p, struct lista *L) { int q; if (L → ultimo >= long_max) printf(“Lista Llena”); else { if(pultimo+1) printf(“Posición no existe”); else { for(q=L → ultimo;q>=p;q--) L → elem[q]=L → elem[q-1]; L →...