Páginas

Estructura de Datos en Python

13:40 | Publicado por Dr. NeoX


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



  13. def Clista(self, data):

  14. '''

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

  16. '''

  17. if data < self.data:

  18. if self.izq is None:

  19. self.izq = Arbol(data)

  20. else:

  21. self.izq.Clista(data)

  22. else:

  23. if self.drch is None:

  24. self.drch = Arbol(data)

  25. else:

  26. self.drch.Clista(data)

  27. def inserta(self, data):

  28. '''

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

  30. '''

  31. data=list(data)

  32. try:

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

  34. #if self.izq is None:

  35. #self.izq = Arbol(data)

  36. self.izq.inserta(data)

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

  38. self.drch.inserta(data)

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

  40. self.data.append(data)

  41. except:

  42. a=-1



  44. def buscar(self, data):

  45. cont=0

  46. '''

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

  48. '''

  49. data=list(data)

  50. try:

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

  52. self.izq.buscar(data)

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

  54. self.drch.buscar(data)

  55. else:

  56. num=len(data)

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

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

  59. print i,">>",

  60. cont=cont+1

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

  62. print "total de coincidencias: ",cont

  63. except:

  64. a=-1

  65. #else:

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

  67. def verArbol(self):

  68. '''

  69. imprime todo el arbol

  70. '''

  71. if self.izq:

  72. self.izq.verArbol()

  73. print self.data

  74. if self.drch:

  75. self.drch.verArbol()




iarbol.py
  1. '''





  4. GRACIAS DIOS!!! xfin T_T acabe

  5. '''



  7. import arbol,lista, urllib2, re

  8. #creo listasM

  9. listaM=lista.Lista()



  11. #MAIN

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

  13. #creo una lista con letras minusculas

  14. lista = lista.split(' ')

  15. # creo los nodos mayusculas

  16. #listaM=[]

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

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

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

  20. iraiz=len(lista)/2

  21. raiz=list(lista[iraiz])

  22. #creo la raiz del arbol

  23. arbol = arbol.Arbol(raiz)

  24. #creo las listas en los nodos

  25. for palabra in lista:

  26. if palabra!=raiz[0]:

  27. arbol.Clista(list(palabra))

  28. #inserto los nodos mayuscula

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

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

  31. #leo una pagina web

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

  33. if web=="local":

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

  35. archivo=archivo.read()

  36. a=archivo.split(' ')

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

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

  39. archivo=archivo.read()

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

  41. else:

  42. print "error D:"

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

  44. arbol.inserta(a[i])

  45. s="S"



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

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

  49. arbol.buscar(palabra)

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

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

Etiquetas: , , ,

0 comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)

Los mejores blog del mundo

Sigueme

Las mas bonitas