2 Listas Enlazadas Resumen PDF

Preview

Summary

Listas Enlazadas, Estructura de Datos...

Description

VARIABLE PUNTERO Y LISTAS ENLAZADAS Variable puntero 

Una variable puntero es una variable cuyo valor es una dirección de una posición de memoria.



Una variable tipo puntero contiene la dirección de la posición de otra variable.



Las estructuras dinámicas de datos son generado a partir de un tipo de dato conocido con el nombre de puntero o de referencia.



Un dato puntero almacena una dirección o referencia a un dato propiamente dicho.



Por lo tanto, debe distinguirse claramente entre un dato puntero y el dato al cual éste apunta.

b DIRECCIÓN 2014 2014

5

b



void main(){ int a; int* b; b = &a; //El puntero 'b' apunta a 'a'. }

a

La principal ventaja que presenta manejar este tipo de datos es que se pueden adquirir posiciones de memoria a medida que se necesitan, y liberarlas cuando ya no se requieran. De esta manera se pueden crear estructuras dinámicas que se expandan o se contraigan, según se les agregue o elimine elementos.



El dinamismo de estas estructuras soluciona el problema de decidir cuál es la cantidad óptima de memoria que debe reservarse para un problema dado

Listas enlazadas



Una lista es una colección de elementos llamados generalmente nodos. El orden entre los nodos se establece por medio de punteros, es decir, direcciones o referencias a otros nodos. Información DECLARAR nodo CREA (P) P^.INFO:= ‘PÉREZ’ P^.LIGA:= Null

Liga

struct nodo { char info[40]; struct nodo *liga; };

1

En general, un nodo consta de dos partes:



Un campo INFORMACIÓN que será del tipo de datos que se quiera almacenar en la lista



Un campo liga, de tipo puntero, que se utiliza para establecer la liga o el enlace con otro nodo de la lista. Si el nodo fuera el último de la lista, este campo tendrá como valor: NIL (vacío). Al emplearse el campo liga para relacionar dos nodos, no será necesario almacenar físicamente a los nodos en espacios contiguos.

Operaciones con listas enlazadas Las operaciones que pueden llevarse a cabo en una lista son:



Recorrido de la lista



Inserción de un elemento



Borrado de una elemento



Búsqueda de un elemento

Listas enlazadas circulares Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero. Las operaciones en listas circulares son similares a las operaciones en listas lineales. En el caso de la operación de recorrido de listas circulares, es necesario aclarar que se debe considerar algún criterio para detectar cuándo se han visitado todos los nodos para evitar caer en ciclos infinitos. Una posible solución consiste en usar un nodo extra, llamado nodo cabecera, para indicar el inicio de la lista. Este nodo contendrá información especial, de tal manera que se distinga de los demás y así podrá hacer referencia al principio de la lista.

Ventajas 

facilita la implementación de este tipo de estructura ya que no se necesita utilizar el puntero nulo y, por tanto, todos los punteros contienen dirección válida.

Listas doblemente enlazadas Una lista doblemente ligada es una colección de nodos, en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (LIGAIZQ) y otro a su sucesor (LIGADER). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.

2

Cada nodo tiene un predecesor, por lo que el primer nodo o es un caso especial. PTR_IZQ

INFORMACIÓN

PTR_DER

P

F García

Pérez

López

Santos

NI

NI

L

L Para tener un fácil acceso a la información de la lista es recomendable usar dos punteros, P y F, que apunten al primero y último nodo de la lista respectivamente. Operaciones con listas doblemente enlazadas Las operaciones que pueden llevarse a cabo con este tipo de estructuras son: 

recorrido de la lista



inserción de un elemento



borrado de un elemento



búsqueda de un elemento

Listas Doblemente Ligadas Circulares En las listas doblemente ligadas circulares, el campo liga izquierda del primer nodo de la lista apunta al último, y el campo liga derecha de éste apunta al primero.

P

P

3

Hasta aquí se han estudiado las principales características de la estructura tipo lista, considerando todas sus variantes:

Lineales Simplemente ligadas Circulares Lineales Doblemente ligadas Circulares

Aplicaciones Dos de las aplicaciones más conocidas de listas son: 

Representación de polinomios



Resolución de colisiones (hash)

En general puede decirse que las listas son muy útiles para aquellas aplicaciones en las cuales se necesite dinamismo en el crecimiento y reducción de las estructuras de datos.

Desarrolle el siguiente cuestionario 1. Mencione y Dibuje gráficamente los cuatro tipos de listas 2. Cuáles son la aplicaciones de las listas? 3. Menciones las operaciones generales que se realizan con la listas 4. Cómo se soluciona evitar caer en ciclos infinito en una lista enlazada circular.

4...