República Bolivariana De Venezuela Ministerio Del Poder Popular Para La Defensa Universidad Nacional Experimental Politécnica De La Fuerza Armada Núcleo-apure

República Bolivariana de Venezuela Ministerio del Poder Popular Para La Defensa Universidad Nacional Experimental Politécnica de la Fuerza Armada Núcleo- Apure

Prof. Laryenso Gutiérrez

Bachilleres: - Génesis del Moral - Johana Lara - Massiel Rangel - Rubén Cabrera

San Fernando Apure, Junio de 2009

Listas Q

Z

R

U

Estructura de datos

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Tipos de listas Listas enlazadas simples

Listas doblemente enlazadas

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Listas enlazadas circulares:

Lista enlazadas circulares simples

Listas enlazadas doblemente circular:

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Diferencia entre los tipos de listas Arra y

Listas enlazadas vs arrays

Lista Enlazada

Indexado

O(1)

O(n)

Inserción / Eliminación al final

O(1)

O(1) or O(n)2

Inserción / Eliminación en la mitad

O(n)

O(1)

Persistencia

No

Simples sí

Localización

Buen a

Mala

Doblemente enlazadas vs simples enlazadas

Circulares enlazadas vs lineales enlazadas HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Ventajas y desventajas de las listas • Desarrollo de software • Teniendo una colección dinámica donde los elementos están siendo añadidos y eliminados

Desventajas Incrementan la complejidad Usar un fondo general de memoria, deja más memorias para otros datos, si la lista es más pequeña de lo esperado si muchos nodos son liberados. El crecimiento de un array HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Operaciones de las listas

Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden. Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato. Buscar: busca un elemento en la lista. Localizar: obtiene la posición del nodo en la lista. Vaciar: borra todos los elementos de la lista HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Implementación de las listas a base de apuntadores INICIO

…

… P

Nodo agregado después del nodo apuntador P al nuevo nodo

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

1 Q INICIO

2 3 …

… P

PASOS: 1. Crear un nuevo nodo con un apuntador auxiliar 2. Encadenar el nuevo nodo al siguiente nodo de P. 3. Apuntar el siguiente P al nuevo nodo.

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Implementación de listas dobles enlazadas Cada nodo apunta al siguiente y al anterior. Duplica el uso de la memoria necesaria para los punteros. Duplica el coste de manejo de punteros al insertar y eliminar. La eliminación se simplifica. No es necesario buscar el elemento anterior. HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Listas utilizando array de nodos Ejemplo: record Entry { integer next; // índice de la nueva entrada en el array integer prev; // entrada previa string name;

real balance;

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Las listas en lenguajes de programación 1. Se requiere un tipo de dato, que representa un nodo 2. En el lenguaje C++, se ofrece esta representación a través de un registro (struct). A continuación se muestran las dos opciones de representación en el lenguaje C++: Class

Struct Nodo

{public:

{

tipoinfo;

Tipoinfo info;

Nodo* sig;

Nodo* sig;

Nodo { sig = NULL;}

Nodo() { sig = NULL;}

Nodo ( tipoinfo dato)

Nodo ( tipoinfo dato)

{ info = dato; sig = NULL; }

{ info = dato; sig = NULL; }

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Almacenamiento de datos en una lista

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA

Gracias por su Atención El arte del vencer se aprende en las derrotas

HECHO POR: JOHANA LARA, GENESIS DE MORAL, MASSIEL RANGEL, RUBEN CABRERA