|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|