Post on 03-Oct-2018
Profesor: José Miguel Rubio L.
Magíster © en Ingeniería InformáticaIngeniero Civil en InformáticaLicenciado en Ciencias de la IngenieríaTécnico en Programación
Oficina: 3-20e-mail 1: jose.rubio.l@ucv.cle-mail 2: jrubio@inf.ucv.cl
ICI 142Fundamentos de Programación
Estructuras Lineales de Datos
Índice
• Abstracción de datos
• Utilización de un TDA
• Tipos de estructura de datos
lineales
• Listas
• Pilas
• Colas
Abstracción de datos
• La abstracción nos permite simplificar el análisis y resolución
de un problema separando las características que son
relevantes de aquellas que no lo son.
• Una abstracción de datos, también denominada tipo de dato
abstracto, es un nuevo tipo de dato más un conjunto de
operaciones que permiten manipular objetos de dicho tipo.
• La utilización de los TDA da lugar a programas que son:
– más legibles
– más fáciles de mantener
– y más fáciles de modificar.
Utilización de un TDA
• Para poder utilizar un TDA, sin saber como está
representado internamente, es necesario disponer de
su especificación.
• Un TDA se divide en dos partes:
– Especificación.
– Implementación.
Tipos de estructura de datos lineales
• Listas
• Pilas
• Colas
• Estas estructuras de datos pueden ser:
– Estáticas (implementado con arreglos) o
– Dinámicas (implementado con listas enlazadas).
Listas
• Son estructuras de datos secuenciales de 0 o más
elementos de un tipo dado almacenados en memoria.
• Son estructuras lineales, donde cada elemento de la
lista, excepto el primero, tiene un único predecesor y
cada elemento de la lista, excepto el último, tiene un
único sucesor.
• El número de elementos de la lista se llama longitud.
Si tiene 0 elementos se llama lista vacía.
Listas
• En una lista podemos añadir nuevos elementos o
suprimirlos en cualquier posición.
• Ejemplo implementado con arreglo:
Tipos de listas
• No enlazada (arreglo)
• Enlazada (objetos)
• Doblemente enlazada (anterior apunta al siguiente y
viceversa)
• Circular (el último apunta al primero)
• A la vez pueden estar:
– Ordenada
– No ordenada
Operaciones sobre Listas
• Algunas operaciones son:
– Inserción
– Supresión
– Recorrido
– Ordenación
– Búsqueda
– Consulta
Operaciones sobre Listas
Aplicación de las listas
• Las listas son comunes en la vida diaria: listas de
alumnos, listas de clientes, listas de espera, listas de
distribución de correo, etc.
• Las listas son estructuras de datos muy útiles para los
casos en los que se quiere almacenar información de la
que no se conoce su tamaño con antelación.
Aplicación de las listas
• También son valiosas para las situaciones en las que
el volumen de datos se puede incrementar o
decrementar dinámicamente durante la ejecución del
programa.
• Cuando aplicamos restricciones de acceso a las listas
tenemos pilas y colas que son listas especiales.
Listas Enlazadas
• Una lista enlazada está formada por una colección de
elementos (denominados nodos) tales que cada uno
de ellos almacena dos valores: un valor de la lista y
un puntero o referencia que indica la posición del
nodo que contiene el siguiente valor de la lista.
• Es necesario almacenar al menos la posición del
primer elemento.
• Es dinámica, su tamaño puede cambiar durante la
ejecución del programa.
Nodos de una lista enlazada
• Una lista enlazada es una sucesión de nodos en la
que a partir de un nodo se puede acceder al que
ocupa la siguiente posición en la lista.
• Esta característica nos indica que el acceso a las
listas es secuencial y no indexado, por lo que para
acceder al último elemento de la lista hay que
recorrer los n-1 elementos previos (n es el tamaño de
la lista).
Nodos de una lista enlazada
• Para que un nodo pueda acceder al siguiente y la
lista no se rompa en varias listas cada nodo tiene que
tener un puntero que guarde la dirección de memoria
que ocupa el siguiente elemento.
• De esta forma un nodo se podría representar esquemáticamente así:
• En el campo información se almacena el objeto a guardar y nodo siguiente mantendrá la conexión con el siguiente nodo.
Esquema de una lista enlazada
Información
Nodo siguiente
Información
Nodo siguiente
Información
Nodo siguiente
Información
Nodo siguiente
Lista doblemente enlazada
• 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.
Lista doblemente enlazada
• Son listas en el que el último elemento tiene una
referencia (enlace) con el primer elemento
(cabecera).
• Pueden ser listas simples o doblemente circulares.
Listas circulares (enlazadas)
Pilas
• Es un tipo lineal de datos, secuencia de
elementos de un tipo, una estructura tipo LIFO
(Last In First Out) último en entrar primero en
salir.
• Son un subconjunto de las listas, en donde las
eliminaciones e inserciones se dan en un solo
extremo, de manera tal que, el último elemento
es el único accesible.
Pilas
• Operaciones básicas:
–– Crear la estructuraCrear la estructura
–– InsertarInsertar
–– EliminarEliminar
–– Obtener un elementoObtener un elemento
–– VacVacííarar
–– Mostrar los elementosMostrar los elementos
Aplicaciones de las pilas
• Compiladores (parsers: reconocedores sintácticos de los
compiladores).
• Programación de sistemas (para registrar llamadas a
subprogramas, y recuperar los datos anteriores, o
recuperar los parámetros).
• Recuperación de elementos en orden inverso al que
fueron colocados (en un depósito, una pila de
contenedores, sillas, etc. ).
• Convertir notación infija a posfija o prefija.
• Implementación de recursividad.
Notación polaca (postfija)
• Para evaluar la expresión aritmética:
según la prioridad de los operadores y el uso de los paréntesis, se sigue el indicado con las flechas.
• Para eliminar esta dificultad, se hace una traducción de las expresiones aritméticas a notación postfija, que se llama también notación de cadena polaca (denominada así en honor del matemático polaco Lukasiewicsz, quién la originó).
Notación polaca (postfija)
• Esta notación tiene la ventaja de que las operaciones aparecen en el orden en que se efectúan realmente la evaluación.
• La idea básica detrás de la notación de cadenas polacas es que los operadores se escriben al final y no en medio de las expresiones. De manera que A + B se escribiría como A B +.
• En esta forma, el operador + se considera como una orden para sumar los valores de las dos variables que lo preceden inmediatamente.
Notación polaca (postfija)
• Un ejemplo puede ser:
• La clave de la traducción de notación infija a posfija
es la prioridad de los operadores: ( ), + -, * /, ^.
Notación postfija
• Reglas básicas para convertir expresiones infijas a postfijas:1. Si el elemento es un ‘ (‘ se coloca directamente en la pila de operadores.
2. Si el elemento es un ‘ )’ , los operadores de la pila se transfieren uno a uno, al extremo derecho de la expresión posfija hasta llegar a un ‘ (‘ . Este se saca pero no va a la salida.
3. Si el elemento localizado es una variable, se coloca inmediatamente en el extremo derecho de la expresión posfija que se estácreando.
4. Si el elemento es un operador y es de menor precedencia que el operador en la pila, el operador de la pila se saca y va a la salida, continuando de esta manera hasta encontrar un ‘ (‘ o hasta que el operador de la pila sea de menor precedencia. Cuando esto ocurre, el operador en turno se apila.
Conversión infija a postfija
• Ecuación cuadrática
• En infija
( b + ( b ^ 2 – 4 * a * c ) ^ ( 1 / 2 ) ) / ( 2 * a )
• En postfija
b b 2 ^ 4 a c * * - 1 2 / ^ + 2 a * /
Algoritmo para evaluar una expresión postfija
1. Implementar la pila
2. Repetir hasta encontrar el fin de la expresión
postfija
– Tomar un carácter.
– Si el carácter es un operando colocarlo en la pila.
– Si el carácter es un operador entonces sacar los dos
valores del tope de la pila (operando2 operando1),
aplicar el operador (operando1 operador operando2) y
colocar el resultado en el nuevo tope de la pila.
Recursividad
• Algoritmo para hallar el factorial de un número mediante pilasleer n;mientras n > 1
pila.apilar (n);n = n-1;
fin mientrasfactorial = 1;mientras pila no está vacía
factorial = factorial * pila.desapilar ();fin mientras
Encapsulación en pilas y colas
• Al igual que con las colas, la implementación de las
pilas suele encapsularse, es decir, basta con conocer
las operaciones de manipulación de la pila para poder
usarla, olvidando su implementación interna.
Colas
• Es un tipo de dato lineal con estructura FIFO (First
In, First Out), el primero que entra es el primero que
sale.
• Las colas son un subconjunto de las listas, en
donde las eliminaciones se dan al comienzo de la
lista y las inserciones al final.
• Los elementos se procesan en el orden como se
reciben (similar a la cola de impresión en redes).
Colas
• Operaciones básicas:
–– Crear la estructuraCrear la estructura
–– InsertarInsertar
–– EliminarEliminar
–– Obtener un elementoObtener un elemento
–– VacVacííarar
–– Mostrar los elementosMostrar los elementos
Aplicaciones de las colas
• Las colas, al igual que las pilas, resultan de aplicación habitual en muchos problemas informáticos.
• Su utilización es infinita, desde la simulación de una cola formada frente a un cajero automático, hasta la cola de impresión.
• Quizás la aplicación más común de las colas es la organización de tareas de un ordenador. Los procesos forman colas para la utilización de los recursos de un sistema computacional.
Como manipular las estructuras de datoslineales
• Idealmente una estructura de datos debe ser
manipulada únicamente por procedimientos propios
(encapsulación).
– Ejemplo: Una lista requiere de un top, pop y un push
– La estructura de datos y sus primitivas de manejo
constituyen la estructura abstracta de datos (TDA)