PDF de programación - Listas, Pilas y Colas Estructura de Datos

Ingeniera de Sistemas: Luz Esperanza Espitia

Tutora de Estructura de datos.







Con relación a la Estructura

LISTA

 Indicar objetos reales que se puedan

modelar con dicha estructura.
 Listas de Ordenes de visitas (hospital…)

 Lista de aplicaciones

 Lista de pacientes





Definiciones de la misma

LISTA

 Una lista es una estructura de datos secuencial.





 Una manera de clasificarlas es por la forma de

acceder al siguiente elemento:


 - Lista densa: la propia estructura determina cuál es
el siguiente elemento de la lista. Ejemplo: un array.
- Lista enlazada: la posición del siguiente elemento
de la estructura la determina el elemento actual. Es
necesario almacenar al menos la posición de
memoria del primer elemento. Además es dinámica,
es decir, su tamaño cambia durante la ejecución del
programa.



Definiciones de la misma

LISTA

 Las Listas son secuencias de 0 o más elementos
de un tipo de datos almacenado en memoria. Son
estructuras lineales donde cada elemento de una
lista excepto el primero tiene un único predecesor
y cada elemento de la lista excepto el ultimo tiene
un sucesor.

 Gráficamente:








TAD que modele las LISTAS.

 Nombre: TAD Lista

 Invariante: n/a



 Operaciones:

 crearLista()

 */ Devuelve un valor del tipo pila preparado para ser usado y

que contiene un valor de pila vacía. Esta operación es la
misma que la de las listas generales.*/

Precondiciones: N=0

Pos condiciones: Lista creada







….TAD que modele las LISTAS.

 insertar(crearLista, x pos)
 */ mediante este método se insertan datos a la Lista ya

creada. Inserta elemento x en pos */

Precondiciones: pos != null
Pos condiciones: insertarLista completado (dato
insertado en Lista)






 */Retorna la posición del último elemento, en otras

FIN():

palabras el “fin” de la lista, también se puede considerar
con el tamaño de la lista. Sí la lista está vacía retorna una
posición invalida que podría ser -1. */

Pos condiciones: operación finalizada

 Precondiciones: n/A




….TAD que modele las LISTAS.

 Siguiente(pos)






*/con este método se Retorna pos + 1, si pos es
igual o mayor a FIN(), retorna FIN(). */
Precondiciones: pos != 0
Pos condiciones: retorna pos

 anterior(pos)




 limpiar(pos)





*/con este método se Retorna pos – 1. */
Precondiciones: pos != 0
Pos condiciones: retorna pos

*/Limpia la lista y Finaliza FIN()*/
Precondiciones: n…n+1, pos = 0
Pos condiciones: Lista vacia…

Relacionar el concepto de
VENTANA con el de Lista.



 Una ventana es un área visual, normalmente
de forma rectangular, que contiene algún tipo
de interfaz de usuario, mostrando la salida y
permitiendo la entrada de datos para uno de
varios procesos que se ejecutan
simultáneamente.


 Y un Consiste en una secuencia de nodos, en

los que se guardan campos de datos
arbitrarios y una o dos referencias (punteros)
al nodo anterior o posterior.


Relacionar el concepto de
VENTANA con el de Lista.

 El principal beneficio de las listas



enlazadas respecto a
los array convencionales es que el orden
de los elementos enlazados puede ser
diferente al orden de almacenamiento en
la memoria o el disco.


 La relación es que con ambos términos
nos referimos a manipulación de datos
sin importar el orden de los mismos, solo
el acceso y su modificación.

Describir las implementaciones de

Listas:

 Para representar en lenguaje C esta

estructura de datos se utilizarán punteros, un
tipo de datos que suministra el lenguaje. Se
representará una lista vacía con la constante
NULL. Se puede definir la lista enlazada de
la siguiente manera:
 struct lista
 {
 int clave;
 struct lista *sig;
 };


… Describir las implementaciones

de Listas:

 e1.- Vectores










 Utilizando una estructura de datos estática arreglo para

representar e implementar el TDA LISTAS. Asumamos que los
ELEMENTOS que contiene la LISTA son representados por el tipo
ENTERO. La cantidad de ELEMENTOS que puede contener la
LISTA tiene un máximo de n ELEMENTOS. Por lo que la
representación formal de este tipo se define de la siguiente
manera: Tipo LISTA= arreglo [1..n] de ENTEROS; VarL : LISTA;


… Describir las implementaciones

de Listas:

 Implementación Procedimiento: Operaciones básicas…



 LISTA_VACÏA (Var L :LISTA)

 var i : ENTERO;
 principio
 Para i := 1 hasta n hacer L[ i ]:= 0;
 fin;


 Función ES_VACÍA(L :LISTA) : LÓGICO

 principio
 Si L[ 1 ] = 0 entonces ES_VACÏA := Verdad
 Sino ES_VACÏA := Falso;
 Fin;


… Describir las implementaciones

de Listas:

 Procedimiento Insertar (Var L :LISTA, p:

POSICIÓN, e : ENTERO)
 var i : ENTERO;
 principio
 Si L [p] <> 0 entonces mientras (i <=n) y ( L [i ] <> 0 )
 hacer
 principio
 sig := l[p]; l[i] := e; e := sig;
 fin;
 l [ i ] := e;
 fin;


… Describir las implementaciones

de Listas:

 e2.- Listas doblemente enlazadas



 Una lista enlazada es una de las estructuras de

datos fundamentales, y puede ser usada para implementar
otras estructuras de datos. Consiste en una secuencia
de nodos, en los que se guardan campos de datos arbitrarios
y una o dos referencias (punteros) al nodo anterior o posterior.


 El principal beneficio de las listas enlazadas respecto a

los array convencionales es que el orden de los elementos
enlazados puede ser diferente al orden de almacenamiento en
la memoria o el disco, permitiendo que el orden de recorrido
de la lista sea diferente al de almacenamiento.


… Describir las implementaciones

de Listas:

 Son listas que tienen un enlace con el elemento

siguiente y con el anterior. Una ventaja que tienen
es que pueden recorrerse en ambos sentidos, ya
sea para efectuar una operación con cada elemento
o para insertar/actualizar y borrar. La otra ventaja es
que las búsquedas son algo más rápidas puesto
que no hace falta hacer referencia al elemento
anterior. Su inconveniente es que ocupan más
memoria por nodo que una lista simple.




Mecanismos para implementar las

listas.



 En el lenguaje C se utiliza los llamados

punteros para representar esta
estructura de datos.


 En java se encuentra un paquete
completo en java.util de donde se
pueden utilizar las listas, como un tipo
abstracto de datos, este tipo de
estructura de datos también se utiliza a
partir y/o como una interfaz.




Con relación a la Estructura

PILA:

 Indicar objetos reales que se puedan

modelar con dicha estructura.

 Memoria de una pc

 Caja de objetos





 Definiciones de Pila.

Una pila es un caso especial de lista en la cual
todas las inserciones y supresiones tienen lugar
en un extremo determinado llamado tope.




Definiciones de Pila.

 A las pilas se les llama también listas LIFO (last-in

first-out) o listas “primero en entrar, primero en
salir”. En el TDA Pila no se definen operaciones
de posicionamiento en la pila. Esto es debido a
que todas las operaciones de acceso se realizan
en la misma posición, el tope de la pila.



TAD que modele las PILAS.

 Nombre: TAD Pila
 Invariante: n<>0
 Operaciones:



 crearPila()

 */ Devuelve un valor del tipo pila preparado para
ser usado y que contiene un valor de pila vacía.
Esta operación es la misma que la de las listas
generales.*/

 Precondiciones: N=0
 Pos condiciones: pila creada

 insertarPila(crearPila)

 */ mediante este método se insertan datos a la
pila ya creada. Con las pilas se usa el método
push para insertar*/

 Precondiciones: pila <> null
 Pos condiciones: insertarPila completado

(datos insertados en pila)



 borrarPila()

 */con este método se elmina cierta pila de datos

*/

 Precondiciones: pila <> null
 Pos condiciones: pila eliminada


Con relación a la Estructura

COLA:

Varias definiciones Cola.



 Una cola es una estructura de datos, caracterizada

por ser una secuencia de elementos en la que la
operación de inserción push se realiza por un
extremo y la operación de extracción pop por el otro.
También se le llama estructura FIFO (del inglés First
In First Out), debido a que el primer elemento en
entrar será también el primero en salir.


 Una cola es también una estructura de datos lineal

en donde las eliminaciones se realizan por uno de
sus extremos que normalmente se llama frente, y las
inserciones se realizan por el otro extremo que
normalmente se llama final. A estas estructuras se
les llama FIFO (First In First Out).



TAD que modele las COLAS.

 Nombre: TAD COLA
 Invariante: n/a
 Operaciones:



 crearCola()

 */ Devuelve un valor del tipo cola preparado

para ser usado y que contiene un valor de pila
vacía. Esta operación es la misma que la de las
listas generales.*/

 Precondiciones: N=0
 Pos condiciones: cola vacia creada


 insertarCola(crearCola)

 */ mediante este método se insertan datos a

la cola ya creada. */

 Precondiciones: cola <> null
 Pos condiciones: datos insertados en

cola, cola insertada.



 borrarCola()

 */con este método se elimina cierta cola de

datos */

 Precondiciones: cola != 0
 Pos condiciones: cola eliminada


Particularidades de un TAD COLA

con prioridades.

 Se introduce una forma de simular genericidad en



los TADs de Modula-2 mediante el uso del TAD
ITEM.


 En una cola de prioridad los elementos están

ordenados dependiendo de su prioridad, de manera
que esté disponible (para las operaciones Frente y
Extraer) el elemento de máxima prioridad. En caso
de igualdad se sigue la regla FIFO, de dos
elementos con igual prioridad sale primero el que
primero entró. Esto se puede conseguir bien
insertando ordena