View
14.208
Download
0
Category
Preview:
DESCRIPTION
Tema: Listas y Pilas Unidad Curricular: Desarrollo de Software Dirigido a: PNFSI Misión Sucre
Citation preview
Prof. Ing. Zamantha González Díaz Mayo, 2008
Prof. Ing. Zamantha González Díaz Mayo, 2008
Los datos físicos se encuentran asociados a un mecanismode datos, que controla la forma en la que la informaciónpuede ser accedida por los programas, existen principalmentecuatro tipos de estos mecanismos.
Que son :
Las colas Las pilas
Las listas Los árboles
º
Prof. Ing. Zamantha González Díaz Mayo, 2008
Cada uno de los métodos mencionados con anterioridadproporciona una solución a cada tipo de problema.Cada uno un dispositivo que realiza una operación dealmacenamiento y de recuperación de los datos dados.
Todos ellos tienen dos elementos en común, como es :
El almacenamiento
de datos
La recuperación
de datos
Prof. Ing. Zamantha González Díaz Mayo, 2008
Prof. Ing. Zamantha González Díaz Mayo, 2008
CONCEPTO DE LISTA
Es un conjunto de nodos cuyas propiedades estructurales
incluyen solo las posiciones lineales (unidimensionales) para ella se
definen operaciones como las siguientes:
.- Tener acceso a un nodo
.- Insertar y eliminar un nodo en la lista
.- combinar dos o mas listas en una
.- Dividir una lista en dos o mas listas
.- Determinar la cantidad de nodos en la lista
.- Ordenar la lista de acuerdo a un criterio
.- buscar un elemento bajo una condición.
Prof. Ing. Zamantha González Díaz Mayo, 2008
PILAS
Es un conjunto dinámico que
obedece el orden lifo
Las pilas es en las que todas las
inserciones y extracciones de
elementos se realizan por un solo
extremo, llamado el tope de la
pila.
primero
ultimo
Prof. Ing. Zamantha González Díaz Mayo, 2008
LAS SIMPLEMENTE ENLAZADAS
Contienen un enlace al elemento siguiente, las
doblemente enlazadas tanto al siguiente elemento como al
elemento anterior del la lista.
Una lista simplemente enlazada necesita que cada
elemento contenga un enlace con el siguiente elemento, cada
elemento consiste en una estructura de campos deinformación a punteros de enlace.
Prof. Ing. Zamantha González Díaz Mayo, 2008
LISTAS DOBLEMENTE ENLAZADAS.
Las listas doblemente enlazadas consisten en datos y
enlaces tanto al elemento siguiente como al elemento anterior.
Con lo que se consiguen dos grandes ventajas, primero la lista
se puede leer en cualquier dirección, la segunda es que se
pueden leer los enlaces hacia delante como hacia atrás, con lo
que si un enlace resulta no valido se puede reconstruir
utilizando el otro enlace.
Prof. Ing. Zamantha González Díaz Mayo, 2008
LISTAS CIRCULARES
Las listas son estructuras muy ricas y variadas. Hemos vistolas más simples; las listas lineales. Veamos ahora otros tipos de listas,
similares a las ya estudiadas; las listas circulares. Una lista lineal
enlazada circularmente, o simplemente una lista circular, es una lista enla que el puntero siguiente al "último" elemento apunta hacia el primer
elemento o nodo. En estas listas no existen ni primero ni últimos
elementos, aunque se debe elegir obligatoriamente un puntero para
referenciar la lista.
Esta lista presenta la gran ventaja de que cada nodo en una lista
circular es accesible evitando caer en un bucle infinito.
Prof. Ing. Zamantha González Díaz Mayo, 2008
EJEMPLO:
Las listas circulares tienen la característica de que el
ultimo elemento de la misma apunta al primero. en la
siguiente figura se mostrara un ejemplo de una lista
circular:
las operaciones en listas circulares son similares a las operaciones
en listas lineales , por lo tanto no se volverá a tratar cada una de
ellas.
En el caso de la operación de recorrido de las listas circulares , es
necesario que se debe aclarar que se debe considerar algún criterio
para detectar cuando se han visitado todos los nodos para evitar
caer en ciclos infinitos.
Prof. Ing. Zamantha González Díaz Mayo, 2008
PILAS
Estructura de datos en la que los elementos se añaden y
quitan solo por un extremo.
Una pila es lo contrario de una cola, ya que su acceso es de
tipo LIFO, el último que entra es el primero que sale.
Imaginar un montón de libros unos encima de otros y que
para acceder al segundo por arriba primero es necesario
coger el primero, su utilización principal es para el software
de sistemas, compiladores, intérpretes.
Prof. Ing. Zamantha González Díaz Mayo, 2008
ESPECIFICACIÓN FORMAL DEL TAD-PILA
Para definir el tipo de datos abstracto (TAD) pilas, no es
suficiente la estructura lógica. Debemos definir el conjunto
de operaciones que permita al usuario acceder y manipular
los elementos almacenados en una pila. Como las pilas es
una estructura dinámica, cambia conforme se añaden y
quitan elementos en esta.
Prof. Ing. Zamantha González Díaz Mayo, 2008
Prof. Ing. Zamantha González Díaz Mayo, 2008
IMPLEMENTACION DE PILAS CON ARREGLOS
Una pilas es una colección ordenada de objetos. En C,
arreglos permite almacenar colecciones ordenadas. Las
desventajas de implementar una pila mediante un
arreglo es que esta última es de tamaño fijo, mientras
que las pilas son de tamaño dinámico.
OPERACIONES DE UNA PILA
Las operaciones básicas de una pila son push (empuja,
meter) y pop (sacar)
_ Push: añade un nuevo elemento
_ Pop: elimina un nuevo elemento
Prof. Ing. Zamantha González Díaz Mayo, 2008
•Otra operaciones usualmente incluidas es el tipo de
datos adstrato pila son:
_ isEmpty (esta vacía): verifica si la pila es
esta vacía_ IsFull (esta Llena): verifica si la pila esta
llena Ejemplo
4 4
1
4
1
1
4
1
4
1
4
4
1
push(4) push(1) push(1) pop() push(4) pop()
Prof. Ing. Zamantha González Díaz Mayo, 2008
•Pila_Vacia: Consultar si la pila está vacía
•Pila_Llena: Consultar si la pila está llena
•Consultar_Pila: Consultar el contenido de la cima de la pila sin
sacar el elemento de la misma
El carácter dinámico de la pila se debe a que el tamaño de la
pila es variable, independientemente de la implementación.
Crea una pila
inicializándola como una
pila vacía
Prof. Ing. Zamantha González Díaz Mayo, 2008
Push: inserta un elemento en el top de la pila
Cada elemento al ser insertadoocupar siempre el top en la pila;12 en la imagen anterior y 15 enesta imagen.
Prof. Ing. Zamantha González Díaz Mayo, 2008
Los elementos han sido
insetados en este orden:
12, 15, 99, 1, 5, 33, 421, 53, 27,
82, 641, 66, 31, 41, 51
dado que el ultimo elemento fue
el 51 es el que ocupa el top en la
pila
Una característica de las pilas es
que son estructuras LIFO(last
input , first output), es decir el
ultimo en entrar sera el primero
en salir
Prof. Ing. Zamantha González Díaz Mayo, 2008
VARIABLES DINÁMICAS.
Existen una gran variedad de aplicaciones en las que no es
posible conocer a priori la dimensión de los datos que serán
necesarios, por lo que en dichos casos es necesario utilizar tipos
de datos DINÁMICOS. El inconveniente es que, muy
posiblemente, se ocupará memoria que puede ser necesaria para
otras variables. Las estructuras dinámicas se caracterizan porque
la reserva de memoria se realiza durante la ejecución del
programa pudiendo reservar y liberar posiciones de memoria
según sea necesario durante la ejecución del mismo
.
Prof. Ing. Zamantha González Díaz Mayo, 2008
DIRECCIONES DE MEMORIA:
La memoria interna del ordenador se organiza
mediante celdas numeradas o direccionadas consecutivamente.
Cada dato almacenado ocupará una de estas celdas (conjunto
de bytes adyacentes). El número de bytes que se requieren para
almacenar un dato depende de su tipo, así como del procesador
de la máquina.
Prof. Ing. Zamantha González Díaz Mayo, 2008
La declaración de un determinado dato indica, entre otras
cosas, que el compilador reservará automáticamente
memoria para almacenar dicho dato. El dato podrá ser
accedido si se conoce su localización o dirección de
memoria, ( nota ). La dirección del dato se corresponde con
la dirección de la casilla o celda de memoria que contiene
dicho dato. La dirección de una celda de memoria es una
identificación predeterminada por el hardware del
ordenador y no se puede modificar.
Prof. Ing. Zamantha González Díaz Mayo, 2008
Ejemplo: Sea la variable "a" que representa un dato de
tipo entero. Tras la declaración de dicha variable, int a,
el compilador reservará el número de bytes necesarios
a partir de una determinada dirección de la memoria:
DireccionesNombres de
variableContenido de variables
#387 vacio
#388 variable1 vacio
#389 A vacio
#390 variable3 vacio
#391 vacio
Prof. Ing. Zamantha González Díaz Mayo, 2008
Recommended