Categoría: Sin categoría Página 45 de 51

Existen ciertos problemas delicados con la forma en que se implementaron las listas. Invirtiendo el orden de causa y efecto, propondremos primero una implementación alternativa y explicaremos luego los problemas que esta resuelve.

En primer lugar crearemos un nueva clase llamada ListaEnlazada. Sus atributos son un entero que contiene la longitud de la lista y una referencia al primer nodo. Los objetos ListaEnlazada sirven de asas para la manipulación de las
listas de los objetos de tipo Nodo:

class ListaEnlazada :
def __init__(self) :
self.longitud = 0
self.cabeza = None

Una ventaja de la clase ListaEnlazada es que suministra un marco natural para poner funciones-envoltorio como imprimeAlRevesBonito, que podemos convertir en un metodo de la clase ListaEnlazada:

class ListaEnlazada:
...
    def imprimeAlReves(self):
        print "[",
            if self.cabeza != None:
                self.cabeza.imprimeAlReves()
            print "]",
class Nodo:
...
    def imprimeAlReves(self):
        if self.siguiente != None:
            cola = self.siguiente
            cola.imprimeAlReves()
        print self.carga,

Para complicar un poco mas las cosas, renombramos imprimeAlRevesBonito.

Ahora hay dos métodos llamados imprimeAlReves: uno en la clase Nodo (el ayudante), y otro en la clase ListaEnlazada (el envoltorio). Cuando el envoltorio llama a self.cabeza.imprimeAlReves, esta llamando al ayudante, ya que
self.cabeza es un objeto de tipo Nodo.

Otra ventaja de la clase ListaEnlazada es que facilita la forma de añadir o quitar el primer elemento de una lista. Por ejemplo, agregaPrimero es un metodo para ListaEnlazada; toma un elemento de la carga como argumento y lo coloca en el principio de la lista:

class ListaEnlazada:
...
    def agregaPrimero(self, carga):
        nodo = Nodo(carga)
        nodo.siguiente = self.cabeza
        self.cabeza = nodo
        self.longitud = self.longitud + 1

Como suele ser usual, deberíamos comprobar este código para ver si maneja casos especiales.

Por ejemplo, que ocurriría si la lista esta inicialmente vacía?

17.10. Invariantes

Algunas listas están “bien construidas”; otras no. Por ejemplo, si una lista contiene un bucle, provocara que nuestros métodos se cuelguen, así que podríamos exigir que las listas no contengan bucles. Otro requisito es que el valor de el valor de longitud en el objeto de tipo Lista Enlazada deber³a ser igual al numero verdadero de nodos de la lista.

A este tipo de requisitos los llamaremos invariantes porque, idealmente deberían cumplirse en todos los objetos en todo momento. Especificar invariantes para objetos es una practica útil de la programación porque hace mas fácil demostrar la idoneidad del código, comprobar la integridad de las estructuras de datos y la detección de errores.

Una cosa que a veces confunde respecto a los invariantes es que en ocasiones son violados. Por ejemplo, en medio de agregaPrimero, después de añadir el nodo paro antes de incrementar la longitud, se viola el invariante. Se acepta este tipo de violación; de hecho, a menudo es imposible modificar un objeto sin violar un invariante durante al menos un corto espacio de tiempo. Normalmente, se exige que todo metodo que viole un invariante debe restablecerlo.

Si hay algún tramo significativo de código en el que el invariante se ve violado, es importante que los comentarios lo dejen

17.11. Glosario

referencia incrustada: Es una referencia almacenada en un atributo de un objeto.

lista enlazada: Estructura de datos que implementa una colección por medio de una secuencia de nodos enlazados.

nodo: Elemento de una lista, normalmente implementado como un objeto que contiene una referencia a otro objeto del mismo tipo.

carga: Datos contenidos en un nodo. enlace: Referencia incrustada usada para enlazar un objeto con otro.

condición previa: Afirmación que debe ser cierta para que un metodo funcione correctamente.

teorema fundamental de la ambiguedad: Una referencia a un nodo de una lista puede tratarse como un objeto individual o como el primero de una lista de nodos.
singleton: Lista enlazada con un solo nodo.

envoltorio: Metodo que actúa como mediador entre un metodo invocador y metodo ayudante, haciendo a menudo su invocación mas fácil o menos proclive a errores.

ayudante: Metodo al que no se invoca directamente por un metodo llamante sino por otro metodo para formar parte de una operación.

invariante: Afirmación que debería ser cierta para un objeto en todo momento (excepto tal vez cuando se esta modificando el objeto).

Capítulo 18

Pilas

18.1. Tipos abstractos de datos

Los tipos de datos vistos hasta ahora han sido todos concretos, en el sentido que se ha especificado su implementación completamente. Por ejemplo, la clase Carta representa un naipe por medio de dos enteros. Como dijimos, esa no es la única manera de representar una carta; existen muchas implementaciones
alternativas.

Un tipo abstracto de datos, o TAD, especifica un conjunto de operaciones (o métodos) y la semántica de las operaciones(lo que hacen), pero no especifica

la implementación de las operaciones. Esto es lo hace lo abstracto.

Para que sirve?
Simplifica la tarea de especificar un algoritmo si se pueden indicar las operaciones necesarias sin preocuparse de como se ejecutaran dichas operaciones.
Como suelen existir muchas maneras de implementar un TAD, puede ser útil desarrollar un algoritmo que se pueda usar con cualquiera de las implementaciones posibles.
Los TADs mas conocidos, como el TAD Pila de este capítulo, se implementan a menudo en bibliotecas estándares de manera que se puedan escribir una vez y usarlas luego muchos programadores.
Las operaciones ejecutadas con TADs proporcionan un lenguaje de alto nivel común para desarrollar y hablar sobre algoritmos.

Cuando hablamos de TADs a menudo se hace la distinción entre el código que usa el TAD, el código cliente, y el código que implementa el TAD, el código proveedor.

18.2. El TAD Pila

En este capítulo se presentara un TAD común, la pila. Una pila es una colección, lo que significa que es una estructura de datos que contiene elementos múltiples.

Otras colecciones que se han visto son los diccionarios y las listas.

Un TAD se definido por medio de las operaciones que se pueden ejecutar sobre el, lo que se llama un interfaz. La interfaz para una pila consta de estas
operaciones:

__init__ : Inicializar una pila nueva y vacía.

push: Añadir un elemento a la pila.

pop: Extraer un elemento de la pila. El elemento devuelto siempre es el ultimo que se añadió.

isEmpty: Probar si la pila esta vacía.

A veces a una pila se la llama una estructura ultimo en entrar primero en salir” (last in, first out” en ingles), o LIFO, porque el elemento añadido en ultimo lugar es el primero que extraemos.

18.3. Como implementar pilas con listas de Python

Las operaciones sobre listas que posee Python son parecidas a las operaciones que definen a una pila. La interfaz no es exactamente la que debería de ser, pero se pueden desarrollar programas para convertir el TAD Pila a las operaciones predefinidas.

A este programa se lo llama implementación del TAD Pila. En general, una implementación es un conjunto de métodos que satisfacen los prerrequisitos sintácticos y semánticos de la interfaz.

He aquí una implementación de el TAD Pila que utiliza una lista Python:

class Pila :
    def __init__(self) :
        self.elementos = []
    def push(self, elemento) :
        self.elementos.append(elemento)
    def pop(self) :
        return self.elementos.pop()
    def isEmpty(self) :
        return (self.elementos == [])

Un objeto Pila contiene un atributo llamado elementos que es una lista de elementos en la pila. El metodo de inicialización pone una lista vacía en elementos.

Para meter un elemento nuevo en la pila, push lo apila en elementos. Para quitar un elemento de la pila, pop utiliza el metodo de lista homónimo para quitar y devolver el ultimo elemento de la lista.

Finalmente, para probar si la pila esta vacía, isEmpty (esta vacía) compara elementos con la lista vacía.

Una implementación como esta, en la cual los métodos consisten de llamadas a métodos existentes, se llama enchapado. En la vida real, un enchapado es una capa fina de madera de alta calidad que se utiliza en la fabricación de muebles para ocultar madera de baja calidad. Los científicos informáticos utilizan esta metáfora para describir una parte de un programa que esconde los detalles de una implementación y que provee una interfaz mas simple o mas estándar.

18.4. Uso de push y pop

Una pila es una estructura genérica de datos, lo significa que se puede a~nadir cualquier tipo de elementos a ella.

El ejemplo mete en la pila dos enteros y una cadena:

>>> s = Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")

Se pueden utilizar isEmpty y pop para quitar e imprimir todos los elementos en la pila:

   1: while not s.isEmpty() :
   2: print s.pop(),

La salida es + 45 54. En otras palabras, <se ha utilizado una pila para imprimir los elementos en orden inverso! Reconocemos que no es el formato estándar de impresión de listas, pero fue muy fácil usar una pila para lograrlo.

Compare estas líneas con la implementación de imprimeAlReves que vimos en la Sección 17.4. Existe un paralelo natural entre la versión recurrente de imprimeAlReves y el algoritmo de pila que acabamos de ver. La diferencia e que imprimeAlReves utiliza la pila de tiempo de ejecución para mantenerse al tanto de los nodos mientras recorre la lista y luego los imprime cuando regresa de la recursión. El algoritmo de pila hace lo mismo, pero utiliza un objeto Pila en vez de la pila de tiempo de ejecución.

18.5. Usar una pila para evaluar postfijo