lunes, 13 de octubre de 2008

TDA Lista

Eddy [delvalle@otepr.co.cu]

Hola equipo de BlackHat esta vez traigo algo básico, que todo buen programador medianamente decente debe conocer. Es la implementación del tipo de dato abstracto (TDA) lista con una lista simplemente enlazada y además con el cálculo de el orden de cada uno de los algoritmos con la notación asintótica para el caso peor, de la que ya CHenry habló anteriormente.


Primero vamos a describir la implementación del TDA Nodo Simple, este tiene que tener un valor o una referencia a este y una referencia al nodo que lo sucede.

Clase Node

Nombre de Atributo Descripción
value Referencia al valor del nodo.
next Referencia al siguiente nodo.

 

Nombre de Método Descripción Orden del Algoritmo
__init__ Constructor de la clase. Se le pasan como parámetros opcionales la referencia a su valor y la referencia al siguiente nodo. O(1)
__str__ Convierte a cadena de caracteres el valor referenciado por el nodo. O(1)

Ahora echemos un vistazo a la descripción de la implementación del TDA Lista.

Clase SimpleLinkedList

Nombre de Atributo Descripción
__count Contador que indica la cantidad de elementos en la lista.
__headNode Referencia al nodo cabeza de la lista
__lastNode Referencia al nodo final de la lista
__iterCursor Referencia al nodo en el que se está iterando en ese instante en la lista

 

Nombre de Método Descripción Orden del Algoritmo
__init__ Constructor de la clase. O(1)
__getitem__ Indexador para conocer el valor de un elemento. Recibe como parámetro un entero el cual es la posición del elemento del que se desea conocer el valor. Devuelve una copia del valor de ese elemento O(n)
__setitem__ Indexador para establecer el valor de un elemento. Recibe como parámetro un entero y una referencia a un valor. El entero es la posición donde se desea establecer el valor. O(n)
__delitem__ Elimina un elemento de la lista. Recibe como parámetro la posición que se va a eliminar. O(n)
__add__ Sobrecarga del operador +. Toma como parámetro otra lista simplemente enlazada y devuelve una nueva lista la cual es el resultado de la concatenación de las dos lista O(n)
__str__ Se ejecuta cuando el objeto es convertido a cadena de caracteres, este método genera una cadena de caracteres con cada uno de los valores de los nodos de la lista convertidos a cadena. O(n)
__iter__ Permite a la clase ser iterada por ciclos como el for.
Para que la clase pueda ser iterada simultaneamete por varios ciclos a la vez este método devuelve una copia del objeto.
O(1)
next Devuelve el elemento de la lista sobre el cual se está iterando y avanza al siguiente. En caso de llegar al fin de la lista este método levanta una excepción para detener las iteraciones O(1)
__AdvanceTo Devuelve un nodo de la lista, el cual se corresponde con el índice que se le pasó al método O(n)
Join Empata dos listas, la actual y la que se le pasa como parámetro. Creando una sola lista y los nombres de las listas ahora referencian a la misma lista. O(1)
Add Agrega un nuevo elemento a la lista. O(1)
Clear Limpia la lista y la deja vacía. O(1)
LocateFirst Devuelva la posición de la primera ocurrencia en la lista del valor que se le pasa como parámetro. O(n)
Locate Devuelve una lista con las posiciones donde ocurre el valor que se le pasa como parámetro en la lista. O(n)
Insert Inserta en la lista un nuevo elemento con el valor y la posición que se le pasan como parámetros O(n)
Reverse Invierte el orden de los elementos de la lista, la pone "patas arriba". O(n)
QSort Ordena la lista de menor a mayor usando el algoritmo de ordenamiento QuickSort O(n log(n))


Ahora pasamos a ver la implementación en Python:
Nota: La implementación se encuentra en la sección de Códigos



Artículos relacionados


No hay comentarios: