Colección de e-readers

Estructuras Dinámicas

Makarena Donoso Pavez 2011 - I

INF 154 Laboratorio de Programación

Listas Contiguas

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

1

Estructuras Dinámicas
Una estructura de datos dinámica es aquella en la que el tamaño ocupado en memoria puede modificarse durante la ejecución del programa. De esta manera se pueden adquirir posicionesadicionales de memoria a medida que se necesiten durante la ejecución del programa y liberarlas cuando no se necesiten. Las variables que se crean y están disponibles durante la ejecución del programa se llaman variables continuas. Las estructuras de datos dinámicas se clasifican en lineales (listas, pilas y colas) y no lineales (árboles y grafos)

INF 154

Laboratorio de ProgramaciónProfesor. Makarena Donoso

Listas
Una lista es una colección de elementos organizados en secuencia que puede crecer y decrecer libremente y a cuyos elementos individuales se puede acceder, insertar y eliminar en cualquier posición. Las listas se clasifican en contiguas, enlazadas, circulares y doblemente enlazadas.

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

2Listas Contiguas
Los elementos de la lista se almacenan normalmente en posiciones consecutivas de memoria, es decir, almacenamiento secuencial, donde se define la constante longitud máxima (N), que determina el tamaño de la mayor lista que se puede tener Se implementan a través de arreglos, donde la inserción o eliminación de un elemento excepto en la cabecera o al final de la lista necesitará unatraslación de los elementos de la lista.
10
Índice 0

55
1

13
2

……..
…..

último elemento N-1

Lista

Espacio Libre
Límite superior

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

Listas Contiguas (2)
La declaración en C de una lista implementada por arreglos es la siguiente:

struct lista{ int elem[long_max]; int ultimo; }

ATENCIÓN: Estaimplementación guarda la posición (1..long_max) del ultimo elemento, y no su índice (0.. long_max-1).

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

3

Listas Contiguas (3)
Creación de lista contigua:
struct lista* Crear(){ struct lista* L = (struct lista*) malloc(sizeof(struct lista)); L-> ultimo=0; return L; }

ultimo
Posición 0 1 2 3 ….. long_max

……..
Índice 0 1 2….. long_max-1

Espacio Libre
INF 154 Laboratorio de Programación Profesor. Makarena Donoso

Listas Contiguas (4)
Inserción de una lista contigua:
struct lista* Insertar(int x, int pos, struct lista* L){ int q; if(L->ultimo>=long_max) printf(“lista llena”); else if((posL->ultimo)) printf(“posicion no existe”); else{ for (q=L->ultimo;q>=pos;q--) L->elem[q] = L->elem[q-1]; L->ultimo=L->ultimo+1;L->elem[q]=x; ultimo } return L; } pos 1 2 3 …..

long_max

10
Índice 0

55
1

13
2

……..
….. long_max-1

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

4

Listas Contiguas (5)
Eliminación de una lista contigua:
struct lista* Eliminar(int pos, struct lista* L){ if((posL->ultimo)) printf(“posicion no existe”); else{ L->ultimo=L->ultimo-1; for(q=pos;qultimo;q++) L->elem[q-1] = L->elem[q]; } return L; ultimo }
pos 1 2 3 ….. long_max

10
Índice 0

55
1

13
2

……..
….. long_max-1

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

Listas Contiguas (6)
Localización de un elemento en una lista contigua:
int Localizar(int x, struct lista* L){ int q; for (q=1;qultimo;q++){ if(L->elem[q-1]==x) return q; }/*elemento no encontrado*/ q=L->ultimo+1; return q;
}

ultimo
pos 1 2 3 ….. long_max

10
Índice 0

55
1

13
2

……..
….. long_max-1

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

5

Listas Enlazadas

INF 154

Laboratorio de Programación

Profesor. Makarena Donoso

Listas Enlazadas
Son mucho más flexibles que las listas contiguas, la inserción o...