profesor: josé miguel rubio l. - zeus.inf.ucv.clzeus.inf.ucv.cl/~jrubio/docs/2008-02/ici...

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)