Data Structures in Python

Posted by Carlos Ganoza on 23 Aug, 2011

Hi Dear readers, here I bring to you, some implementations of the data structure’s course, but with python.
In my University it’s used java for this course, but I wanted to use python
because right now is my prefeer language.

So, lets go!

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

class Queue:

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

def is_empty(self):
if self.queue==[]:
return True
else:
return False

def peek(self):
return self.queue[0]

def enqueue(self, element):
self.queue.append(element)

def dequeue(self):
del self.queue[0]
list.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 List:
def __init__(self):
self.list=[]

def last(self):
return self.list[-1]

def first(self):
return self.list[0]

def next(self, position):
return self.list[position+1]

def previous(self, position):
return self.list[position-1]

def is_empty(self):
if self.list==[]:
print "true"
def get(self, position):
e=self.list[position]
return e

def lenght(self):
return len(self.list)

def push(self, position, elemento ):
self.list.insert(position, elemento)

def remove(self, position):
del self.list[position]

def show(self):
return self.list
stack.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Stack:
def __init__(self):
self.stack=[]

def is_empty(self):
if self.stack==[]:
return True
retrun False

def last(self):
return self.stack[-1]

def push(self, element):
self.stack.append(element)

def pop(self):
return self.stack.pop()

Also, here I leave an exercise using Binary Search Tree for to order words and search it.
Is posible search words from a web(if do you to enter the url) or some txt file, only do you shoud see the implementation tree_implementation.py

tree.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
74
75
class Tree:
'''
Tree constructor (create it empty)
'''

def __init__(self, data):
'''
constructor
'''
self.left = None
self.right = None
self.data = data

def create_node(self, data):
'''
we create node as a list according to the letters of the alphabet.
'''
if data < self.data:
if self.left is None:
self.left = Tree(data)
else:
self.left.create_node(data)
else:
if self.right is None:
self.right = Tree(data)
else:
self.right.create_node(data)

def insert(self, data):
'''
Go through the tree comparing the first letter with the nodes, and inserted into the corresponding node.
'''
data = list(data)
try:
if data[0] < self.data[0]:
self.left.insert(data)
elif data[0] > self.data[0]:
self.right.insert(data)
elif data[0] == self.data[0]:
self.data.append(data)
except:
a = -1

def lookup(self, data):
'''
Go through the tree and find where the corresponding list.
'''
cont = 0
data = list(data)
try:
if data[0] < self.data[0]:
self.left.lookup(data)
elif data[0] > self.data[0]:
self.right.lookup(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 of coincidences: ", cont
except:
a = -1

def show(self):
'''
print the tree.
'''
if self.left:
self.left.show()
print self.data
if self.right:
self.right.show()
print self.data
tree_implementation.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

'''
THANKS GOD!!!
'''

import urllib2, re

list_uppercase = []

list_lowercase = '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'

# create the list of lowercase letters

list_lowercase = list_lowercase.split(' ')

# create the list of uppercase letters

for i in range(len(list_lowercase)):
list_uppercase.append(list_lowercase[i].upper())
# search the root
root = len(list_lowercase) / 2
root = list(list_lowercase[root])

# create the root of tree
tree = Tree(root)

# create the list on the nodes
for letter in list_lowercase:
if letter != root[0]:
tree.create_node(list(letter))
# insert the nodes
for i in range(len(list_uppercase)):
tree.create_node(list(list_uppercase[i]))
# read the web
web = raw_input("Enter the web page do you want to read (if you want to read a local file write local):")

if web == "local":
file = open('file.txt')
file = file.read()
a = file.split(' ')
elif web.startswith('www'):
file = urllib2.urlopen('http://' + web)
file = file.read()
a = re.findall(r'\w+', file)
else:
print "error D:"
for i in range(len(a) - 1):
print a[i]
tree.insert(a[i])
s = "Y"
print tree.show()
while s == "Y":
word = raw_input("enter the letter or word: ")
tree.lookup(word)
s = raw_input("do you want to follow?[Y/N]: ").upper()
print "you left the program"

As you will see in the last exercise thanks to the magic of python, as Ider would say (a friend who gave me the light to start) you can organize the words hierarchically as if they were numbers (from major to minor) and facilitating the task in The organization of the binary tree.

Implementing ADT in python is relatively simple and it is only a matter of reading the theory, I hope this helps.


Carlos Ganoza

Software engineer with more than 6 years of experience, I have been involved in different aspects of software development, InfoSec and open-source. I <3 Python.