python algorithms dataStructure

Estructura de datos en python

Posted by Carlos Ganoza on 23 Aug, 2011

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

sin mucho preambulo aqui les dejo el codigo:

cola.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Cola:

     def __init__(self):
        self.cola = []

     def vacia(self):
	    if self.cola==[]:
		    print "true"
	    else:
	        print "false"

     def primero(self):
	    return self.cola[0]

     def inserta(self, elemento):
	    self.cola.append(elemento)

     def suprime(self):
	    del self.cola[0]
lista.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Lista:
	def __init__(self):
		self.lista=[]

	def fin(self):
		return self.lista[-1]

	def primero(self):
		return self.lista[0]

	def siguiente(self, posicion):
		return self.lista[posicion+1]

	def anterior(self, posicion):
		return self.lista[posicion-1]

	def vacia(self):
		if self.lista==[]:
			print "true"
	def recupera(self, posicion):
		e=self.lista[posicion]
		print e

	def longitud(self):
		return len(self.lista)

	def inserta(self, posicion, elemento ):
		self.lista.insert(posicion, elemento)

	def suprime(self, posicion):
		del self.lista[posicion]

	def ver(self):
		print self.lista
pila.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Pila:
	def __init__(self):
		self.pila=[]

	def vacia(self):
		if self.pila==[]:
			print "true"

	def tope(self):
		return self.pila[-1]

	def push(self, elemento):
		self.pila.append(elemento)

	def pop(self):
		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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Arbol:
	'''
	Constructor de Arbol lo crea vacio
	'''
	def __init__(self, data):
		'''
		Constructor con parametros vacios
		'''
		self.izq = None
		self.drch = None
		self.data = data

	def Clista(self, data):
		'''
		creamos la lista en cada nodo segun las letras del alfabeto
		'''
		if data < self.data:
			if self.izq is None:
				self.izq = Arbol(data)
			else:
				self.izq.Clista(data)
		else:
			if self.drch is None:
				self.drch = Arbol(data)
			else:
				self.drch.Clista(data)

	def inserta(self, data):
		'''
		recorre el arbol comparando la primera letra con los nodos, y se inserta en     el  nodo correspondiente
		'''
		data=list(data)
		try:
			if data[0] < self.data[0]:
				self.izq.inserta(data)
			elif data[0] > self.data[0]:
				self.drch.inserta(data)
			elif data[0] == self.data[0]:
				self.data.append(data)
		except:
			a=-1

	def buscar(self, data):
		'''
		recorre el arbol y busca donde se encuentra la lista correspondiente
		'''
		cont=0
		data=list(data)
		try:
			if data[0] < self.data[0]:
				self.izq.buscar(data)
			elif data[0] > self.data[0]:
				self.drch.buscar(data)
			else:
				num=len(data)
			for i in range(len(self.data)):
				if data==self.data[i][0:num]:
					print i,">>",
					cont=cont+1
					print "".join(self.data[i])
			print "total de coincidencias: ",cont
		except:
			a=-1

	def verArbol(self):
		'''
		imprime todo el arbol
		'''
		if self.izq:
			self.izq.verArbol()
			print self.data
		if self.drch:
			self.drch.verArbol()
iarbol.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

'''
GRACIAS DIOS!!! xfin T_T acabe
'''
import arbol,lista, urllib2, re

#creo listasM

listaM=lista.Lista()

#MAIN

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'

#creo una lista con letras minusculas

lista = lista.split(' ')

# creo los nodos mayusculas

#listaM=[]

for i in range(len(lista)):
    listaM.push(lista[i].upper())
#busco la raiz (la letra intermedia del abecedario)
iraiz=len(lista)/2
raiz=list(lista[iraiz])

#creo la raiz del arbol
arbol = arbol.Arbol(raiz)
#creo las listas en los nodos

for palabra in lista:
	if palabra!=raiz[0]:
		arbol.Clista(list(palabra))
#inserto los nodos mayuscula
for i in range(len(listaM.lista)):
	arbol.Clista(list(listaM.belemento(i)))
#leo una pagina web
web=raw_input("ingrese la pagina web que desea leer ( si desea leer un archivo local escriba local): ")

if web=="local":
	archivo=open('Archivo.txt')
	archivo=archivo.read()
	a=archivo.split(' ')
elif web.startswith('www'):
	archivo=urllib2.urlopen('http://'+web)
	archivo=archivo.read()
	a=re.findall(r'\w+',archivo)
else:
	print "error D:"
for i in range(len(a)-1):
	arbol.inserta(a[i])
s="S"
while(s=="S"):
	palabra=raw_input("ingrese palabra: ")
	arbol.buscar(palabra)
	s=raw_input("desea seguir?[S/N]: ").upper()
	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
2
3
4
5
6
7
8
9
10
11
12

class Lista:
	def __init__(self):
		self.lista=[]
	def push(self, elemento):
		self.lista.append(elemento)
	def belemento(self, index):
		return self.lista[index]
	def pop(self):
		return self.lista.pop(-1)
	def esvacio(self):
		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.

Carlos Ganoza

I have more than 6 years of experience in the technology market, I have been involved in different aspects of software development, cybersecurity, and open-source. I ♥ python, the open-source, and I always enjoy learning new skills.