Herramientas Informaticas

Mes: agosto 2012 Página 20 de 22

19.4. Cola Enlazada Mejorada

Nos gustaría una implementación del TAD Cola capaz de realizar todas las
operaciones en tiempo constante. Una forma de hacerlo es modificar la clase
Cola de modo que mantenga una referencia tanto al primero como al ultimo
nodo, como se muestra en la figura:

Sin título

 

La implementación de ColaMejorada es así:

   1: class ColaMejorada:

   2:     def __init__(self):

   3:         self.longitud = 0

   4:         self.cabeza = None

   5:         self.ultimo = None

   6:     def estaVacia(self):

   7:         return (self.longitud == 0)

 

Hasta ahora, el único cambio es el atributo ultimo. Se usa en los métodos
inserta y quita:

   1: class ColaMejorada:

   2: ...

   3: def inserta(self, carga):

   4:     nodo = Nodo(carga)

   5:     nodo.siguiente = None

   6:     if self.longitud == 0:

   7:         # si la lista esta vac³a, el nuevo nodo es cabeza y ultimo

   8:         self.cabeza = self.ultimo = nodo

   9:     else:

  10:         # encontrar el ultimo nodo

  11:         ultimo = self.ultimo

  12:         # añaadir el nuevo nodo

  13:         ultimo.siguiente = nodo

  14:         self.ultimo = nodo

  15:     self.longitud = self.longitud + 1

 

Como ultimo sigue el rastro del ultimo nodo, no necesitamos buscarlo. A causa
de esto, este metodo funciona en tiempo constante.

Debemos pagar un precio por esa velocidad. Tenemos que añadir un caso especial
a quita para apuntar ultimo a None cuando quitamos el ultimo nodo:

   1: class ColaMejorada:

   2: ...

   3:     def quita(self):

   4:         carga = self.cabeza.carga

   5:         self.cabeza = self.cabeza.siguiente

   6:         self.longitud = self.longitud - 1

   7:         if self.longitud == 0:

   8:         self.ultimo = None

   9:     return carga

 

Esta implementación es mas complicada que la de la Lista Enlazada, y es mas
difícil demostrar que es correcta. La ventaja es que hemos alcanzado la meta:
tanto inserta como quita son operaciones de tiempo constante.

 

 

Como ejercicio, escriba una implementación del TAD Cola usando
una lista de Python. Compare el rendimiento de esta implementación
con la de la ColaMejorada para varias longitudes de cola.

19.5. Cola priorizada

El TAD Cola Priorizada tiene el mismo interfaz que el TAD Cola, pero diferente semántica. De nuevo, el interfaz es:
__init __: Inicializa una cola vacía nueva.

inserta: Añade un nuevo elemento a la cola.

quita: Elimina y devuelve un elemento de la cola. El elemento devuelto es el de prioridad mas alta.

estaVacia: Comprueba si la cola esta vacía.

La diferencia semántica es que el elemento eliminado de la cola no es necesariamente el primero que se añadió. En su lugar, es el elemento con la prioridad mas alta. Lo que son las prioridades y como se comparan con las otras no se especifica en la implementación de la Cola Priorizada. Depende de los elementos de la cola.

Por ejemplo, si los elementos de la cola tienen nombres, podemos elegirlos en orden alfabético. Si son puntuaciones de bolos, podemos ir de mayor a menor, pero si son puntuaciones de golf, iremos de menor a mayor. Siempre que podamos
comparar los elementos de la cola, podremos encontrar y quitar el elemento con mayor prioridad.

Esta implementación de Cola Priorizada tiene como atributo una lista de Python que contiene los elementos de la cola.

   1: class ColaPriorizada:

   2:     def __init__(self):

   3:         self.elementos = []

   4:     def estaVacia(self):

   5:         return self.elementos == []

   6:     def inserta(self, elemento):

   7:         self.elementos.append(elemento)

 

El metodo de inicializacion, estaVacia, e inserta son todos calcados de las operaciones sobre listas. El único metodo interesante es quita:

   1: class ColaPriorizada:

   2: ...

   3:     def quita(self):

   4:         maxi = 0

   5:         for i in range(1,len(self.elementos)):

   6:         if self.elementos[i] > self.elementos[maxi]:

   7:         maxi = i

   8:         elemento = self.elementos[maxi]

   9:         self.elementos[maxi:maxi+1] = []

  10:         return elemento

 

Al principio de cada iteración, maxi contiene el índice del elemento mas grande
(prioridad mas alta) que hemos visto hasta el momento. Cada vez que se com-
pleta el bucle, el programa compara el iésimo elemento con el campeón. Si el
nuevo elemento es mayor, el valor de maxi se fija a i.
Cuando la sentencia for completa su ejecución, maxi es el índice del elemento
mayor. Este elemento se elimina de la lista y se devuelve.

Vamos a probar la implementación:

   1: >>> c = ColaPriorizada()

   2: >>> c.inserta(11)

   3: >>> c.inserta(12)

   4: >>> c.inserta(14)

   5: >>> c.inserta(13)

   6: >>> while not c.estaVacia(): print c.quita() # ver cu¶al se quita

   7: 14

   8: 13

   9: 12

  10: 11

 

Si la cola contiene números o cadenas simples, se eliminan en orden numérico o alfabético, de mayor a menor. Python puede encontrar el entero o la cadena mayor porque puede compararlos usando los operadores de comparación internos.

Si la cola contiene un tipo de objeto, debe proporcionar un metodo __cmp__ . Cuando quita usa el operador > para comparar elementos, invoca al __cmp__ de uno de los elementos y le pasa el otro como parámetro. Siempre que el metodo __cmp__ trabaje adecuadamente, la Cola Priorizada funcionara.

 

 

 

 

 

19.6. La clase Golfista

Como ejemplo de un objeto con una definición inusual de prioridad, vamos a
implementar una clase llamada Golfista que mantiene los nombres y puntua-
ciones de golfistas. Como es habitual, empezamos por definir __init__ y __str__:

   1: class Golfista:

   2:     def __init__(self, nombre, puntos):

   3:         self.nombre = nombre

   4:         self.puntos = puntos

   5:     def __str__(self):

   6:         return "%-16s: %d" % (self.nombre, self.puntos)

 

__str__ usa el operador de formato para poner los nombres y las puntuaciones
en bonitas columnas.
A continuación definimos una versión de __cmp__ en la que la puntuación mas
baja tiene la prioridad mas alta. Como siempre, __cmp__ devuelve 1 si self es
mayor que” otro, -1 si self es menor que” otro, y 0 si son iguales.

   1: class Golfista:

   2: ...

   3:     def __cmp__(self, otro):

   4:         if self.puntos < otro.puntos: return 1 # menos es mas

   5: if      self.puntos > otro.puntos: return -1

   6:         return 0

 

Ya estamos listos para probar la cola priorizada con la clase Golfista:

   1: >>> tiger = Golfista("Tiger Woods", 61)

   2: >>> cabr = Golfista("Angel Cabrera", 72)

   3: >>> ola = Golfista("J.M. Olazabal", 69)

   4: >>> cp = ColaPriorizada()

   5: >>> cp.inserta(tiger)

   6: >>> cp.inserta(cabr)

   7: >>> cp.inserta(ola)

   8: >>> while not cp.estaVacia(): print cp.quita()

   9: Tiger Woods : 61

  10: J.M. Olazabal : 69

  11: Angel Cabrera : 72

 

Como ejercicio, escriba una implementación del TAD Cola Prio-
rizada usando una lista enlazada. Deber³a usted mantener la lista
ordenada de modo que la eliminación sea una operación de tiempo
constante. Compare el rendimiento de esta implementación con la
implementación con la lista de Python.

19.7. Glosario

cola: Un conjunto ordenado de objetos esperando un servicio de algún tipo.

Cola: Un TAD que ejecuta las operaciones que uno podría realizar sobre una cola.

Táctica de encolamiento: Las reglas que determinan que miembro de la cola será el próximo en eliminarse.

FIFO: “First In, First Out”, una táctica de encolamiento en la que el primer miembro en llegar es el primero en salir.

cola priorizada: Una táctica de encolamiento en la que cada miembro tiene una prioridad determinada por factores externos. El miembro con mayor prioridad es el primero en eliminarse.

Cola Priorizada: Un TAD que define las operaciones que se pueden realizar sobre una cola priorizada.

cola enlazada: Una implementación de una cola utilizando una lista enlazada.

tiempo constante: Una operación cuyo tiempo de ejecución no depende del tamaño de la estructura de datos.

tiempo lineal: Una operación cuyo tiempo de ejecución es función lineal del tamaño de la estructura de datos.

Árboles

Al igual que las listas enlazadas, los arboles están hechos de nodos. Un tipo
común de árbol es un árbol binario, en el que cada nodo contiene una referencia
a otros dos nodos (posiblemente nula). Nombramos a estas referencias como
subarboles izquierdo y derecho. Como los nodos de las listas, los nodos de los
arboles también contienen una carga. Un diagrama de estado de un árbol es así:

                            Sin título

 

Para evitar apelotonar las cosas en la figura, solemos omitir los Nones.

La parte superior del árbol (el nodo al que apunta tree) se llama raíz. Siguiendo con la metáfora del árbol, los otros nodos se llaman ramas y los nodos de los extremos con referencias nulas se llaman hojas. Puede parecer extraño que
dibujemos la figura con la raíz arriba y las hojas abajo, pero eso no es lo mas raro.

Para empeorar las cosas, los científicos informáticos añaden a la mezcla otra metáfora: el árbol genealógico. El nodo superior se llama a veces padre y los nodos a los que se refiere son sus hijos. Los nodos con el mismo padre se llaman hermanos.

Para terminar, tenemos un vocabulario geométrico para hablar sobre los arboles.

Ya hemos mencionado izquierda y derecha, pero también están arriba” (hacia el padre/raíz) y abajo” (hacia los hijos/hojas). También, todos los nodos que están a la misma distancia de la raíz forman un nivel del árbol.

Probablemente no sean necesarias las metáforas arbóreas para hablar de arboles, pero ahí están.

Igual que las listas enlazadas, los arboles son estructuras de datos recursivas

porque se definen recursivamente.
Un árbol es:

  • el árbol vacío, representado por None, o
  • un nodo que contiene una referencia a un objeto y dos referencias a arboles.

20.1. Crear árboles

El proceso de montar un árbol es similar al proceso de montar una lista enlazada.
Cada invocación del constructor crea un solo nodo.

   1: class Arbol:

   2:     def __init__(self, carga, izquierda=None, derecha=None):

   3:         self.carga = carga

   4:         self.izquierda = izquierda

   5:         self.derecha = derecha

   6:     def __str__(self):

   7:         return str(self.carga)

 

La carga puede ser de cualquier tipo, pero los parámetros izquierda y derecha
deben ser arboles.Tanto izquierda como derecha son opcionales; el valor por
omisión es None.

Para imprimir un nodo, simplemente imprimimos la carga.
Una forma de construir un árbol es del fondo hacia arriba.

Asigne primero los nodos hijos:

   1: izquierda = Arbol(2)

   2: derecha = Arbol(3)

 

Luego cree el nodo padre y vincúlelo a los hijos:

   1: arbol = Arbol(1, izquierda, derecha);

 

Podemos escribir este código mas concisamente anidando las invocaciones al
constructor:

   1: >>> arbol = Arbol(1, Arbol(2), Arbol(3))

 

En cualquier caso, el resultado es el árbol del principio del capítulo.

20.2. Recorrer árboles

Siempre que usted vea una nueva estructura de datos, su primera pregunta
debería ser: “¿Como la recorro?” La forma mas natural de recorrer un árbol
es recursivamente. Por ejemplo, si el árbol contiene enteros como carga, esta
función nos devuelve su suma:

   1: def total(arbol):

   2: if arbol == None: return 0

   3: return total(arbol.izquierda) + total(arbol.derecha) +

   4: arbol.carga

El caso base es el árbol vacío, que no tiene carga, así que la suma es 0. El
paso recursivo hace dos llamadas recursivas para hallar la suma de los arboles
hijos. Cuando terminan las llamadas recursivas, sumamos la carga del padre y
devolvemos el total.

20.3. Árboles de expresión

Un árbol es un forma natural de representar la estructura de una expresión.
Al contrario que otras notaciones, puede representar el calculo de forma no
ambigua. Por ejemplo, la expresión infija 1 + 2 * 3 es ambigua a no ser que
sepamos que la multiplicación se realiza antes que la suma.

Este árbol de expresión representa el mismo calculo:

Sin título

 

Los nodos de un árbol de expresión pueden ser operandos como 1 y 2 u operado-
res como + y *. Los operandos son nodos hojas; los nodos operadores contienen
referencias a sus operandos. (Todos estos operadores son binarios, lo que sig-
nifica que tienen exactamente dos operandos.)Así podemos construir este árbol:

1: >>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))

Mirando la figura, no hay duda del orden de las operaciones; la multiplicación
se realiza antes para calcular el segundo operando de la suma.

Los arboles de expresión tienen muchos usos. El ejemplo de este capítulo usa
arboles para traducir expresiones a postfijo, prefijo e infijo. Arboles similares se
usan dentro de los compiladores para analizar, optimizar y traducir programas.

20.4. Recorrido de un árbol

Podemos recorrer un árbol de expresión e imprimir el contenido así:

   1: def imprimeArbol(arbol):

   2:     if arbol == None: return

   3:         print arbol.carga,

   4:         imprimeArbol(arbol.izquierda)

   5:         imprimeArbol(arbol.derecha)

En otras palabras, para imprimir un árbol imprima primero el contenido de la raíz, luego el subárbol izquierdo entero y después el subárbol derecho entero.

Esta forma de recorrer un árbol se llama orden prefijo, porque el contenido de la raíz aparece antes del contenido de los hijos.

La salida del ejemplo anterior es:

   1: >>> arbol = Arbol('+', Arbol(1), Arbol('*', Arbol(2), Arbol(3)))

   2: >>> imprimeArbol(arbol)

   3: + 1 * 2 3

Este formato es diferente tanto del postfijo como del infijo; es otra notación llamada prefija, en la que los operadores aparecen delante de sus operandos.

Puede sospechar que si recorre el árbol en un orden diferente obtendrá la expresión en una notación diferente. Por ejemplo, si imprime primero los subárboles
y luego la raíz, tendrá:

   1: def imprimeArbolPostfijo(arbol):

   2:     if arbol == None: return

   3:         imprimeArbolPostfijo(arbol.izquierda)

   4:         imprimeArbolPostfijo(arbol.derecha)

   5:         print arbol.carga

¡El resultado, 1 2 3 * +, esta en notación posfija! Este orden de recorrido se llama orden postfijo.

Finalmente, para recorrer un árbol en orden infijo, usted imprime el árbol izquierdo, luego la raíz y después el árbol  derecho:

   1: def imprimeArbolInfijo(arbol):

   2:     if arbol == None: return

   3:         imprimeArbolInfijo(arbol.izquierda)

   4:         print arbol.carga,

   5:         imprimeArbolInfijo(arbol.derecha)

 

El resultado es 1 + 2 * 3, que es la expresión en notación infija.

Para ser justos debemos señalar que hemos omitido una importante complicación. A veces, al escribir una expresión infija, debemos usar paréntesis para preservar el orden de las operaciones. De modo que una exploración de orden infijo no es suficiente para generar una expresión infija.

No obstante, con unas pequeñas mejoras, el árbol de expresión y los tres recorridos nos dan una forma general de traducir expresiones de un formato a otro.

Como ejercicio, modifique imprimeArbolInfijo de modo que pon-
ga entre paréntesis cada operador con sus operandos. >La salida es
correcta y sin ambigüedades? >Se necesitan siempre los paréntesis?

 

Si hacemos un recorrido en orden infijo y tomamos nota de en que nivel del árbol estamos, podemos generar una representación grafica de un árbol:

   1: def imprimeArbolSangrado(arbol, nivel=0):

   2:     if arbol == None: return

   3:         imprimeArbolSangrado(arbol.derecha, nivel+1)

   4:         print ' '*nivel + str(arbol.carga)

   5:         imprimeArbolSangrado(arbol.izquierda, nivel+1)

 

El parámetro nivel lleva la cuenta de donde estamos en el árbol. Por omisión,
inicialmente es 0. Cada vez que hacemos una llamada recursiva, pasamos nivel+1
porque el nivel del hijo es siempre uno mayor que el del padre. Sangramos cada
elemento con dos espacios por nivel. El resultado del árbol de ejemplo es:

   1: >>> imprimeArbolSangrado(arbol)

   2:     3

   3:    *

   4:   2

   5:  +

   6:   1

 

Si mira la salida de lado, vera una versión simplificada de la figura original.

20.5. Construir un árbol de expresión

En esta sección analizamos expresiones infijas y formamos los correspondientes arboles de expresión. Por ejemplo, la expresión (3+7)*9 nos da el siguiente árbol:

Sin título 

Fíjese en que hemos simplificando el diagrama omitiendo los nombres de los atributos.

El analizador que vamos a escribir maneja expresiones que incluyen números, paréntesis y los operadores + y *.

Suponemos que la cadena de entrada ya ha sido tokenizada y almacenada en una lista de Python. La lista de tokens d (3+7)*9 es:

[‘(‘, 3, ‘+’, 7, ‘)’, ‘*’, 9, ‘fin’]

El token fin es útil para evitar que el analizador lea mas allá del final de la lista.

A modo de ejercicio, escriba una función que tome una cadena conteniendo una expresión y devuelva una lista de tokens.

La primera función que vamos a escribir es tomaToken, que toma como parámetros una lista de tokens y el token que esperamos. Compara el token esperado con el primer token de la lista: si coinciden, elimina el token de la lista y devuelve
verdadero, en caso contrario, devuelve falso:

   1: def tomaToken(listaToken, esperado):

   2:     if listaToken[0] == esperado:

   3:         del listaToken[0]

   4:         return 1

   5:     else:

   6:         return 0

Como listaToken apunta a un objeto mutable, los cambios hechos aquí son visibles para cualquier otra variable que apunte al mismo objeto.

La siguiente función, obtieneNumero, maneja operandos. Si el siguiente token de listaToken es un numero, obtieneNumero lo elimina y devuelve un nodo hoja que contiene el numero; en caso contrario, devuelve None.

   1: def obtieneNumero(listaToken):

   2:     x = listaToken[0]

   3:     if type(x) != type(0): return None

   4:         del listaToken[0]

   5:     return Arbol (x, None, None)

Antes de seguir, debemos probar obtieneNumero aisladamente. Asignamos una lista de números a listaToken, extraemos el primero, imprimimos el resultado e imprimimos lo que quede de la lista de tokens:

   1: >>> listaToken = [9, 11, 'fin']

   2: >>> x = obtieneNumero(listaToken)

   3: >>> imprimeArbolPostfijo(x)

   4: 9

   5: >>> print listaToken

   6: [11, 'fin']

El siguiente metodo que necesitamos es obtieneProducto, que construye un árbol de expresión para productos. Un producto simple tiene dos números como
operandos, como 3 * 7.

Aquí tenemos una versión de obtieneProducto que maneja productos simples.

   1: def obtieneProducto(listaToken):

   2:     a = obtieneNumero(listaToken)

   3:     if tomaToken(listaToken, '*'):

   4:         b = obtieneNumero(listaToken)

   5:         return Arbol ('*', a, b)

   6:     else:

   7:         return a

Suponiendo que obtieneNumero se ejecuta con éxito y devuelve un árbol simple, asignamos el primer operando a a. Si el siguiente carácter es *, obtenemos el segundo numero y construimos un árbol de expresión con a, b, y el operador.

Si el siguiente carácter es cualquier otra cosa, simplemente devolvemos el nodo hoja con a. Veamos dos ejemplos:

   1: >>> listaToken = [9, '*', 11, 'fin']

   2: >>> arbol = obtieneProducto(listaToken)

   3: >>> imprimeArbolPostfijo(arbol)

   4: 9 11 *

   5: >>> listaToken = [9, '+', 11, 'fin']

   6: >>> arbol = obtieneProducto(listaToken)

   7: >>> imprimeArbolPostfijo(arbol)

   8: 9

El segundo ejemplo implica que entendemos un operando suelto como un tipo de producto. Esta definición de producto” es contraria a la intuición, pero resulta ser útil.

Ahora tenemos que vernos las con productos compuestos, como 3 * 5 * 13.

Tratamos esta expresión como un producto de productos, es decir, 3 * (5 *13). El árbol resultante es:

Sin título2

Con un pequeño cambio en obtieneProducto podemos manejar productos arbitrariamente largos:

   1: def obtieneProducto(listaToken):

   2:     a = obtieneNumero(listaToken)

   3:     if tomaToken(listaToken, '*'):

   4:         b = obtieneProducto(listaToken) # cambiamos esta l¶³nea

   5:         return Arbol ('*', a, b)

   6:     else:

   7:         return a

En otras palabras, un producto puede ser bien un operando aislado o un árbol con * en su raíz, un numero en la derecha y un producto en la izquierda. Este tipo de definición recursiva deber³a empezar a resultar familiar.

Comprobemos la nueva versión con un producto compuesto:

   1: >>> listaToken = [2, '*', 3, '*', 5 , '*', 7, 'fin']

   2: >>> arbol = obtieneProducto(listaToken)

   3: >>> imprimeArbolPostfijo(arbol)

   4: 2 3 5 7 * * *

Ahora añadiremos la capacidad de analizar sumas. De nuevo, usamos una definición poco intuitiva de suma”. Para nosotros, una suma puede ser un árbol con + en la ra³z, un producto en la izquierda y una suma en la derecha. O también, una suma puede ser simplemente un producto.

Si quiere seguir adelante con esta definición, tiene una bonita propiedad: podemos representar cualquier expresión (sin paréntesis) como una suma de productos. Esta propiedad es la base de nuestro algoritmo de analisis.

obtieneSuma intenta construir un árbol con un producto en la izquierda y una suma en la derecha. Pero si no encuentra un +, simplemente construye un producto.

   1: def obtieneSuma(listaToken):

   2:     a = obtieneProducto(listaToken)

   3:     if tomaToken(listaToken, '+'):

   4:         b = obtieneSuma(listaToken)

   5:         return Arbol ('+', a, b)

   6:     else:

   7:         return a

 

Vamos a probarla con 9 * 11 + 5 * 7:

   1: >>> listaToken = [9, '*', 11, '+', 5, '*', 7, 'fin']

   2: >>> arbol = obtieneSuma(listaToken)

   3: >>> imprimeArbolPostfijo(arbol)

   4: 9 11 * 5 7 * +

 

Ya casi hemos acabado, pero todavía tenemos que manejar los paréntesis.

En cualquier lugar de una expresión donde puede haber un numero, puede haber también una suma entera entre paréntesis. Solo necesitamos modificar
obtieneNumero para manejar subexpresiones:

 

   1: def obtieneNumero(listaToken):

   2:     if tomaToken(listaToken, '('):

   3:         x = obtieneSuma(listaToken) # obtiene la subexpresi¶on

   4:         tomaToken(listaToken, ')') # quita el cierre de par¶entesis

   5:         return x

   6:     else:

   7:         x = listaToken[0]

   8:     if type(x) != type(0): return None

   9:         listaToken[0:1] = []

  10:         return Arbol (x, None, None)

 

Vamos a probar este código con 9 * (11 + 5) * 7:

   1: >>> listaToken = [9, '*', '(', 11, '+', 5, ')', '*', 7, 'fin']

   2: >>> arbol = obtieneSuma(listaToken)

   3: >>> imprimeArbolPostfijo(arbol)

   4: 9 11 5 + 7 * *

El analizador manejo correctamente los paréntesis; la suma ocurre antes de la multiplicación.

En la versión final del programa, sería bueno dar a obtieneNumero un nombre mas descriptivo de su nueva función.

Página 20 de 22

Creado con WordPress & Tema de Anders Norén