Páginas

Estructura de Datos en Python



Hola queridos lectores, aquí les traigo algunas clases que se utilizan el el curso de Estructura de Datos, pero echas en python.

Sin mucho preambulo aqui les dejo el codigo

Cola.py

  1. class Cola:

  2. def __init__(self):

  3. self.cola=[]

  4. def vacia(self):

  5. if self.cola==[]:

  6. print "true"

  7. else:

  8. print "false"

  9. def primero(self):

  10. return self.cola[0]

  11. def inserta(self, elemento):

  12. self.cola.append(elemento)

  13. def suprime(self):

  14. del self.cola[0]



Lista.py
  1. class Lista:

  2. def __init__(self):

  3. self.lista=[]

  4. def fin(self):

  5. return self.lista[-1]

  6. def primero(self):

  7. return self.lista[0]

  8. def siguiente(self, posicion):

  9. return self.lista[posicion+1]

  10. def anterior(self, posicion):

  11. return self.lista[posicion-1]

  12. def vacia(self):

  13. if self.lista==[]:

  14. print "true"

  15. def recupera(self, posicion):

  16. e=self.lista[posicion]

  17. print e

  18. def longitud(self):

  19. return len(self.lista)

  20. def inserta(self, posicion, elemento ):

  21. self.lista.insert(posicion, elemento)

  22. def suprime(self, posicion):

  23. del self.lista[posicion]

  24. def ver(self):

  25. print self.lista



Pila.py
  1. class Pila:

  2. def __init__(self):

  3. self.pila=[]

  4. def vacia(self):

  5. if self.pila==[]:

  6. print "true"

  7. def tope(self):

  8. return self.pila[-1]

  9. def push(self, elemento):

  10. self.pila.append(elemento)

  11. def pop(self):

  12. return self.pila.pop()



También les dejo un ejercicio que utiliza Árbol Binario para ordenar palabras y buscarlas según lo que se ingresa:
se puede buscar palabras de una WEB (ingresando previamente la url) o de algún archivo TXT, solo es cuestión de ver la
implementación (iarbol.py)

Arbol.py
  1. class Arbol:

  2. '''

  3. Constructor de Arbol lo crea vacio

  4. '''

  5. def __init__(self, data):

  6. '''

  7. Constructor con parametros vacios

  8. '''

  9. self.izq = None

  10. self.drch = None

  11. self.data = data



  12. def Clista(self, data):

  13. '''

  14. creamos la lista en cada nodo segun las letras del alfabeto

  15. '''

  16. if data < self.data:

  17. if self.izq is None:

  18. self.izq = Arbol(data)

  19. else:

  20. self.izq.Clista(data)

  21. else:

  22. if self.drch is None:

  23. self.drch = Arbol(data)

  24. else:

  25. self.drch.Clista(data)

  26. def inserta(self, data):

  27. '''

  28. recorre el arbol comparando la primera letra con los nodos, y se inserta en el nodo correspondiente

  29. '''

  30. data=list(data)

  31. try:

  32. if data[0] < self.data[0]:

  33. #if self.izq is None:

  34. #self.izq = Arbol(data)

  35. self.izq.inserta(data)

  36. elif data[0] > self.data[0]:

  37. self.drch.inserta(data)

  38. elif data[0] == self.data[0]:

  39. self.data.append(data)

  40. except:

  41. a=-1



  42. def buscar(self, data):

  43. cont=0

  44. '''

  45. recorre el arbol y busca donde se encuentra la lista correspondiente

  46. '''

  47. data=list(data)

  48. try:

  49. if data[0] < self.data[0]:

  50. self.izq.buscar(data)

  51. elif data[0] > self.data[0]:

  52. self.drch.buscar(data)

  53. else:

  54. num=len(data)

  55. for i in range(len(self.data)):

  56. if data==self.data[i][0:num]:

  57. print i,">>",

  58. cont=cont+1

  59. print "".join(self.data[i])

  60. print "total de coincidencias: ",cont

  61. except:

  62. a=-1

  63. #else:

  64. #print self.data, parent.data ,self.izq.data

  65. def verArbol(self):

  66. '''

  67. imprime todo el arbol

  68. '''

  69. if self.izq:

  70. self.izq.verArbol()

  71. print self.data

  72. if self.drch:

  73. self.drch.verArbol()




iarbol.py
  1. '''





  2. GRACIAS DIOS!!! xfin T_T acabe

  3. '''



  4. import arbol,lista, urllib2, re

  5. #creo listasM

  6. listaM=lista.Lista()



  7. #MAIN

  8. lista = 'a b c d e f g h i j k l m n o p q r s t u v w x y z'

  9. #creo una lista con letras minusculas

  10. lista = lista.split(' ')

  11. # creo los nodos mayusculas

  12. #listaM=[]

  13. for i in range(len(lista)):

  14. listaM.push(lista[i].upper())

  15. #busco la raiz (la letra intermedia del abecedario)

  16. iraiz=len(lista)/2

  17. raiz=list(lista[iraiz])

  18. #creo la raiz del arbol

  19. arbol = arbol.Arbol(raiz)

  20. #creo las listas en los nodos

  21. for palabra in lista:

  22. if palabra!=raiz[0]:

  23. arbol.Clista(list(palabra))

  24. #inserto los nodos mayuscula

  25. for i in range(len(listaM.lista)):

  26. arbol.Clista(list(listaM.belemento(i)))

  27. #leo una pagina web

  28. web=raw_input("ingrese la pagina web que desea leer ( si desea leer un archivo local escriba local): ")

  29. if web=="local":

  30. archivo=open('Archivo.txt')

  31. archivo=archivo.read()

  32. a=archivo.split(' ')

  33. elif web.startswith('www'):

  34. archivo=urllib2.urlopen('http://'+web)

  35. archivo=archivo.read()

  36. a=re.findall(r'\w+',archivo)

  37. else:

  38. print "error D:"

  39. for i in range(len(a)-1):

  40. arbol.inserta(a[i])

  41. s="S"



  42. while(s=="S"):

  43. palabra=raw_input("ingrese palabra: ")

  44. arbol.buscar(palabra)

  45. s=raw_input("desea seguir?[S/N]: ").upper()

  46. print "usted salio del programa"





y una pequeña clase de nombre "lista.py" que como se darán cuenta no implementa las primitivas con los nombres comunes para el TAD lista , pero pueden checar y corregir para que se ajuste a lo que les pidan.
lista.py
  1. class Lista:

  2. def __init__(self):

  3. self.lista=[]

  4. def push(self, elemento):

  5. self.lista.append(elemento)

  6. def belemento(self, index):

  7. return self.lista[index]

  8. def pop(self):

  9. return self.lista.pop(-1)

  10. def esvacio(self):

  11. return (self.lista==[])


Como verán en el último ejercicio gracias a la magia de python, como diria Ider (un amigo que me dio la luz para comenzar) se pueden organizar las palabras jerárquicamente como si de números se tratara ( de mayor a menor) y facilitándonos la tarea en la organización del árbol binario.

Implementar los TDA en python es relativamente sencillo y pues solo es cuestión de dar una leida a la teoría, espero que les sirva esto.

0 comentarios:

Los mejores blog del mundo

Sigueme

Las mas bonitas