cap v, listas.pdf

7/16/2019 Cap V, LISTAS.pdf

http://slidepdf.com/reader/full/cap-v-listaspdf 1/49

FACULTAD DE INGENIERÍA

ESCUELA DE INGENIERÍA ENSISTEMAS Y COMPUTACIÓN

ESTRUCTURA DE DATOS

Pamela Vásquez Costales



UNIDAD II

CAPÍTULO V

LISTAS



LISTAS

Objetivos

O Entender qué es una lista encadenada.O Describir el TDA lista encadenada.

O Comprender cómo se puede

representar una lista encadenada,tanto en memoria estática como enmemoria dinámica.



Objetivos

O Describir la forma en que se puedenimplementar las operaciones de

inserción de un elemento, eliminaciónde un elemento y desplegado de loselementos de una lista encadenada.

O

Identificar las características, ventajasy desventajas de una lista encadenadacircular.



Objetivos

O Identificar las características, ventajasy desventajas de una lista doblemente

encadenada y una lista doblementeencadenada circular.



¿Qué es una lista encadenada?

Es una estructura de datos que tieneuna organización lineal y se caracteriza

porque cada uno de sus elementos tieneque indicar dónde se encuentra el

siguiente elemento de la lista comoindica la siguiente figura; por lo tanto,es una abstracción de la representaciónpor ligas para una estructura de datos

lineal.



Una lista encadenada es un TDA que seconvierte en una opción pararepresentar otras estructuras de datos o

TDA.



Cada elemento de la lista se guarda enun nodo que contiene la información y

el valor que indica en dónde seencuentra el siguiente dato en la lista.



¿Cuál es la especificación lógica delTDA lista encadenada?



¿Cómo se utilizan la memoria

estática y la dinámica pararepresentar el TDA listaencadenada?

Una lista encadenada está formada porun conjunto de nodos ligados entre sí.Se denomina nodo de lista encadenada

al espacio de memoria que almacena unelemento de la lista y la dirección dondese encuentra el siguiente elemento de la

estructura como indica la figura:



Esquema de nodo para una lista

encadenada:



La lista encadenada puede representarseen memoria estática utilizando un

arreglo de nodos o, más común, conmemoria dinámica utilizando nodos

encadenados a través de apuntadores.



Cualquiera que sea la representaciónseleccionada debe existir un apuntadorprincipal, externo a la estructura, que

almacene la dirección del primer

elemento de la lista, ya que, a partir deél, se encadena el resto de loselementos (cada uno guarda la

dirección de su sucesor).



La siguiente figura muestra el esquemade una lista encadenada en memoria

estática:



La figura muestra el esquema de unalista encadenada equivalente en

memoria dinámica.



Cualquier operación que se efectúesobre una lista encadenada debe cuidar

el correcto encadenamiento de loselementos, ya que un apuntador mal

colocado provocará pérdidas en la listay afectará la integridad de la estructura.



¿Cómo se puede implementar unalista encadenada en lenguaje

C++??

La implementación de una listaencadenada requiere primero de un

tipo de dato que represente a un nodoque, a su vez, permita agrupar el

valor almacenado y la dirección delsiguiente elemento.



Las opciones para esta representación,que ofrece el lenguaje C++, son através de un objeto o un registro

(struct).

Dado que un nodo sirve para formaruna lista, es recomendable que en

cualquier representación seleccionadapara el nodo, se pueda tener acceso a

los elementos que lo conforman; esdecir, los atributos deben ser públicos.



A continuación se muestran las dosopciones de representación:



Una vez definido el tipo de dato de losnodos, la representación de la listaencadenada se especifica con un

apuntador al inicio de la lista, como se

muestra a continuación:



¿Cuáles son las situaciones típicasde implementación en una lista

encadenada?

Para visualizar las situaciones máscomunes de implementación de una lista

encadenada, se analizarán diversosejemplos.



Ejemplo:



¿Cuáles son las variantes de una

lista encadenada?Si se consideran las características deuna lista encadenada es posible generar

diversas variantes de gran utilidad.

Entre las más comunes se encuentran:O Listas encadenadas circulares

O Listas doblemente encadenadas

O Listas doblemente encadenadascirculares

O Listas con múltiples encadenamientos



¿Cómo es una lista encadenadacircular?

Es una ligera variante de la listaencadenada lineal; se obtiene al

considerar el "primer" nodo de la listacomo el sucesor del último nodo,

almacenando la dirección del primerelemento en el campo de dirección del

último, en lugar de almacenar ladirección nula.



Al realizar esta modificación se generaautomáticamente un círculo, donde

realmente ya no existe ni el primero niun último elemento.



Características generales de unalista circular

O Es necesario mantener un apuntadorgeneral a la estructura (Lista), aunque

ya no apunte obligatoriamente alprimer elemento.

O La dirección nula no existe en la lista,excepto cuando la lista está vacía.

O Si la lista contiene un solo elemento, elcampo de dirección apuntará a esemismo nodo.



O Como la lista es un círculo, es posiblellegar a cualquier nodo de la lista apartir de cualquiera de sus nodos, loque es imposible en una lista lineal

como indica la figura: Esquema de unalista encadenada circular.



Código en lenguaje C++ de lasinstrucciones que sirven para desplegar la

información de una lista circular:

Observe la importancia de validar el casoextremo de la lista vacía, y de controlar

con un ciclo do...while el desplegado de lainformación.



¿Cómo es una lista doblementeencadenada?

Este tipo de listas se utilizan cuando la

aplicación sobre una lista encadenadadebe recorrer la lista en ambos sentidos,

algo imposible de realizar en una listaencadenada lineal y, aunque es posible

hacerlo en una lista circular, resulta muyineficiente.



Características generales de unalista doblemente encadenada

O Se requiere mantener un apuntador

general a la estructura (Lista), a pesarde que los nodos conocen a supredecesor y a su sucesor. No esnecesario que lista apunte al primer

elemento de la lista, ya que siempre sepodrá llegar a él como indica la figura:



Esquema de una lista doblementeencadenada



O Cada nodo requiere almacenar, ademásdel elemento, dos direcciones: la delpredecesor y la del sucesor.

O El movimiento de apuntadores puede

hacerse en ambas direcciones.



Los nodos de una lista doblementeencadenada se definirían de la siguiente

manera en el lenguaje C++:



La eliminación del nodo señalado por elapuntador P en una lista doblemente

encadenada, requerirá de las siguientesinstrucciones en lenguaje C++:



La inserción de un nodo después delnodo señalado por el apuntador P enuna lista doblemente encadenada,

requerirá de las siguientes instrucciones

en lenguaje C++:



¿Cómo es una lista doblementeencadenada circular?

En este tipo de listas, cada nodo

almacena la dirección de su sucesor y desu predecesor. No existe un inicio ni un

final.



Características generales de una

lista circular doblemente enca-denada circular

O Se requiere mantener un apuntadorgeneral a la estructura (Lista), a pesarde que los nodos conocen a supredecesor y a su sucesor. Este

apuntador puede guardar la direcciónde cualquier nodo de la lista comoindica la figura:



Esquema de una lista doblemente

encadenada circular



O Cada nodo requiere almacenar, además

del elemento, dos direcciones (la delpredecesor y la del sucesor).

O La dirección nula no existe en la lista,

excepto cuando está vacía.O Si la lista contiene un elemento, el

campo de dirección apuntará a esemismo nodo.

O El movimiento de apuntadores puedehacerse en ambas direcciones.



¿Cómo es una lista con múltiplesencadenamientos?

Esta variante permite mezclar listas que

contienen diferentes elementos. Loanterior se logra cuando los nodosalmacenan la dirección de otra lista

como indica la figura.



Esquema de una lista con múltiples

encadenamientos

Estas mezclas pueden llegar a ser tancomplejas como la aplicación lo requiera.

cap v, listas.pdf

Documents