|
|
|
|
|
|
|
Hemos visto ejemplos de atributos que hacen referencia a otros objetos, a los que llamamos referencias incrustadas (véase la Sección 12.8). Una estrutura de datos común, la lista enlazada, saca partido de esta característica.
Las listas enlazadas se componen de nodos, donde cada nodo contiene una referencia al próximo nodo de la lista. Además, cada nodo contiene una unidad de datos llamada carga
Podemos considerar una lista enlazada como una estructura de datos recursiva porque tiene una definición recursiva.
Una lista enlazada puede ser:
- la lista vacía, representada por None, o bien
- un nodo que contiene un objeto de carga y una referencia a una lista enlazada.
Las estructuras recursivas de datos nos llevan a métodos recursivos.
Como es habitual cuando se escribe una clase, comenzaremos con los métodos de inicialización y __str__, para poder comprobar el mecanismo básico de crear y mostrar el nuevo tipo:
class Nodo:
def __init__(self, carga=None, siguiente=None):
self.carga = carga
self.siguiente = siguiente
def __str__(self):
return str(self.carga)
Como es habitual, los parámetros para el método de inicialización son opcionales. Por defecto, la carga y el enlace, siguiente, se ponen a None.
La representación alfanumérica de un nodo es únicamente la de la carga. Como se puede pasar cualquier valor a la función str, podemos guardar cualquier valor en una lista.
Para comprobar la implementación en este punto, podemos crear un Nodoe imprimirlo:
>>> nodo = Nodo("prueba")
>>> print nodo
prueba
Para hacerlo más interesante, necesitaremos una lista que contenga más de un nodo:
>>> nodo1 = Nodo(1)
>>> nodo2 = Nodo(2)
>>> nodo3 = Nodo(3)
Este código crea tres nodos, pero aún no tenemos una lista porque los nodos todavía no están enlazados. El diagrama de estados tiene el siguiente aspecto:
Para enlazar los nodos, debemos hacer que el primer nodo haga referencia al segundo, y que éste haga referencia al tercero:
>>> nodo1.siguiente = nodo2
>>> nodo2.siguiente = nodo3
La referencia del tercer nodo será None, que indica que es el final de la lista. Ahora el diagrama de estados tendrá el siguiente aspecto:
Ahora ya sabe cómo crear nodos y enlazarlos en listas. Lo que podría estar menos claro es por qué.
Las listas son utiles porque aportan un modo de ensamblar múltiples objetos dentro de una única entidad, a veces llamada colección. En el ejemplo, el primer nodo de la lista sirve como referencia a la lista completa.
Para pasar la lista como parámetro, sólo tenemos que hacer referencia al primer nodo. Por ejemplo, la función imprimeLista toma como argumento un nodo simple. Empezando con la cabeza de la lista, imprime cada nodo hasta que llega al final.
def imprimeLista(nodo):
while nodo:
print nodo,
nodo = nodo.siguiente
print
Para llamar a este método, pasamos una referencia al primer nodo:
>>> imprimeLista(nodo1)
1 2 3
Dentro de imprimeLista tenemos una referencia al primer nodo de la lista, pero no hay una variable que haga referencia a los otros nodos. Tendremos que usar el valor de siguiente de cada nodo para acceder al siguiente nodo.
Para recorrer una lista enlazada es habitual usar la variable de un bucle como nodo para hacer referencia sucesivamente a cada uno de los nodos.
Este diagrama muestra el valor de lista y los valores que va tomando nodo:
Por convenio, las listas suelen imprimirse entre corchetes con comas entre los elementos, como [1, 2, 3]. Como ejercicio, modifique imprimeLista para que genere una salida con este formato.
Es natural expresar muchas operaciones con listas por medio de métodos recursivos. El siguiente ejemplo es un algoritmo recursivo para imprimir una lista hacia atrás:
Por supuesto, el paso 2, la llamada recursiva, supone que tenemos una
manera de imprimir una lista del revés. Pero si suponemos que la
llamada recursiva funciona el acto de fe entonces podemos estar
convencidos de que este algoritmo funciona.
Todo lo que necesitamos es un caso básico y una forma de demostrar que para cualquier lista podemos obtener el caso básico. Dada la definición recursiva de una lista, un caso básico natural es la lista vacía, representada por None:
def imprimeAlReves(lista):
if lista == None: return
cabeza = lista
cola = lista.siguiente
imprimeAlReves(cola)
print cabeza,
La primera línea maneja el caso inicial no haciendo nada. Las dos siguientes líneas dividen la lista en cabeza y cola. Las dos últimas líneas imprimen la lista. La coma que hay al final de la última línea evita que Python salte de línea después de imprimir un nodo.
Llamamos este método tal como antes invocamos a imprimeLista:
>>> imprimeAlReves(nodo1)
3 2 1
El resultado es una lista invertida.
Es posible que se pregunte por qué imprimeLista e imprimeAlRevesson funciones y no métodos de la clase Nodo. La razón es que queremos usar None para representar la lista vacía y no es legal llamar un método sobre None. Esta limitación resulta algo incómoda a la hora de escribir código para manipular listas con un estilo orientado a objetos puro.
¿Podemos demostrar que imprimeAlReves siempre acabará? En otras palabras, ¿siempre alcanzaremos el caso básico? De hecho, la respuesta es no. Algunas listas harán que el método no funcione.
No hay nada que impida a un nodo hacer referencia a un nodo anterior de la lista, incluido él mismo. Por ejemplo, esta figura muestra una lista con dos nodos, uno de los cuales apunta a sí mismo:
Si llamamos a imprimeLista sobre esta lista, entrará en un bucle infinito. Si llamamos a imprimeAlReves, lo hará de forma infinitamente recursiva. Eeste tipo de comportamiento da lugar a que sea muy difícil trabajar con listas infinitas.
Sin embargo, en ocasiones resultan útiles. Por ejemplo, podríamos representar un número como una lista de dígitos y usar una lista infinita para representar una fracción repetida.
A pesar de todo, es un problema que no podamos probar que imprimeListae imprimeAlReves puedan terminar correctamente. Lo mejor que podemos hacer es afirmar que "si la lista no contiene bucles, estos métodos podrán terminar". Este tipo de afirmaciones se conocen como condiciones previas. Imponen una restricción sobre uno de los parámetros y describen el comportamiento del método si la restricción se satisface. Veremos más ejemplos más adelante.
Una parte de imprimeAlReves podría habernos sorprendido:
cabeza = lista
cola = lista.siguiente
Después de la primera asignación, la cabeza y la cola tienen el mismo tipo y el mismo valor. Asi que, ¿para qué hemos creado un nueva variable?
La razón es que las dos variables desempeñan papeles diferentes. Pensamos en la cabeza como una referencia al primer nodo de la lista. Estos "papeles" no forman parte del programa, sino que están en la mente del programador.
En general no podemos decir con sólo mirar un programa qué papel desempeñará un variable. Esta ambigüedad puede ser útil, pero también puede dificultar la lectura del programa. A menudo usaremos nombres para las variables como nodo y lista para explicar cómo queremos usar una variable y a veces creamos variables adicionales para eliminar ambigüedades.
Podríamos haber escrito imprimeAlReves sin cabeza ni cola, que lo haría mas conciso, pero posiblemente menos claro:
def imprimeAlReves(lista) :
if lista == None : return
imprimeAlReves(lista.siguiente)
print lista,
Mirando esas dos llamadas, hemos de recordar que imprimeAlRevestrata sus argumentos como una colección y print los trata como a un sólo objeto.
El teorema fundamental de la ambigüedad indica que la ambigüedad que es inherente a una referencia a un nodo:
Una variable que hace apunta a nodo puede tratar a este nodo como un objeto o como el primero de una lista de nodos.
Hay dos formas de modificar una lista enlazada. Obviamente, podemos cambiar la carga de uno de los nodos, pero las operaciones más interesantes son las que añaden, quitan o reordenan los nodos.
Como ejemplo, escribamos un método que quite el segundo nodo de la lista y devuelva una referencia al nodo quitado:
def eliminaSegundo(lista):
if lista == None: return
primero = lista
segundo = lista.siguiente
# hacer que el primer noda apunte al tercero
primero.siguiente = segundo.siguiente
# separar el segundo nodo del resto de la lista
segundo.siguiente = None
return segundo
De nuevo, estamos usando variables temporales para hacer más legible el código. Así es como usamos este método:
>>> imprimeLista(nodo1)
1 2 3
>>> eliminado = elimnaSegundo(nodo1)
>>> imprimeLista(eliminado)
2
>>> imprimeLista(nodo1)
1 3
El diagrama de estado nos muestra el efecto de la operación:
¿Qué ocurriría si llamáramos a este método y pasáramos una lista de un único elemento (un singleton)? ¿Qué sucedería si pasáramos una lista vacía como argumento? ¿Hay una condición previa para este método? Si es así, sería algo razonable establecer un método para manejar una violación de la condición previa.
A menudo es útil dividir una operación de listas en dos métodos. Por ejemplo, para imprimir una lista invertida en el formato convencional [3, 2, 1] podemos usar el método imprimeAlReves para imprimir 3, 2, pero necesitaremos un método aparte para imprimir los corchetes y el primer nodo. Llamémoslo imprimeAlRevesBonito:
def imprimeAlRevesBonito(lista) :
print "[",
if lista != None :
cabeza = lista
cola = lista.siguiente
imprimeAlReves(cola)
print cabeza,
print "]",
De nuevo, vemos que es buena idea comprobar métodos como éste para ver si funcionan con casos especiales como una lista vacía o un singleton.
Cuando usamos este método en algún otro lugar del programa, llamamos directamente a imprimeAlRevesBonito, y éste llama a imprimeAlReves en nuestro lugar. En cierto modo, imprimeAlRevesBonito actúa como un envoltorio, y utiliza a imprimeAlReves como su ayudante.
Existen ciertos problemas delicados con la forma en que se implementaron las listas. Inviertiendo el orden de causa y efecto, propondremos primero una implementación alternativa y explicaremos luego los problemas que ésta 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 método 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 más 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, está 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 método 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 éste código para ver si maneja casos especiales. Por ejemplo, ¿qué ocurriría si la lista está unicialmente vacía?
Algunas listas están "bien construidas"; otras no. Por ejemplo, si una lista contiene un bucle, provocará 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 ListaEnlazada debería ser igual al número 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 práctica útil de la programación porque hace más 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 método 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 claro, de modo que no se realicen operaciones que dependan del invariante.
|
|
|
|
|
|
|