Skip to content

Commit a835555

Browse files
hatinghating
committed
Initial commit
0 parents  commit a835555

27 files changed

Lines changed: 1203 additions & 0 deletions

‎.idea/IntroductionToAlgorithms.iml‎

Lines changed: 11 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/inspectionProfiles/Project_Default.xml‎

Lines changed: 12 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/inspectionProfiles/profiles_settings.xml‎

Lines changed: 7 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/misc.xml‎

Lines changed: 4 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/modules.xml‎

Lines changed: 8 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/vcs.xml‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎BinarySearch.py‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
import random
2+
3+
4+
def InsertionSort(A, n):
5+
for j in range(1, n):
6+
key = A[j]
7+
# Insert A[j] into the sorted sequence[1...j-1]
8+
i = j - 1
9+
while i >= 0 and A[i] > key:
10+
A[i + 1] = A[i]
11+
i = i - 1
12+
A[i + 1] = key
13+
return A
14+
15+
16+
def BinarySearch(A, p, r, key):
17+
if p >= r:
18+
return -1
19+
q = (p + r) / 2
20+
if A[q] == key:
21+
return q
22+
elif A[q] < key:
23+
return BinarySearch(A, q + 1, r, key)
24+
else:
25+
return BinarySearch(A, p, q, key)
26+
27+
28+
# Pre procedure.
29+
A = []
30+
s = random.randint(5, 100)
31+
for i in range(0, s):
32+
A.append(random.randint(0, 1000))
33+
A = InsertionSort(A, len(A))
34+
key = random.choice(A)
35+
36+
print "Now displaying BinarySearch."
37+
print A
38+
print key
39+
print BinarySearch(A, 0, len(A) - 1, key)

‎BinarySearchTree.py‎

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
import random
2+
3+
4+
class Tree:
5+
def __init__(self):
6+
self.l = None
7+
self.r = None
8+
self.k = None
9+
self.p = None
10+
11+
def Transplant(self, u, v):
12+
if u.p is None:
13+
u.k = v.k
14+
15+
elif u is u.p.l:
16+
u.p.l = v
17+
else:
18+
u.p.r = v
19+
if v.k is not None:
20+
v.p = u.p
21+
22+
def TreeDelete(self, z):
23+
24+
if z.l.k is None:
25+
self.Transplant(z, z.r)
26+
elif z.r.k is None:
27+
self.Transplant(z, z.l)
28+
else:
29+
y = z.r.TreeMinimum()
30+
if y.p is not z:
31+
self.Transplant(y, y.r)
32+
y.r = z.r
33+
y.r.p = y
34+
self.Transplant(z, y)
35+
y.l = z.l
36+
y.l.p = y
37+
38+
def Insert(self, T, i, P):
39+
if T.k == None:
40+
T.k = i
41+
T.p = P
42+
T.l = Tree()
43+
T.r = Tree()
44+
elif T.k > i:
45+
self.Insert(T.l, i, T)
46+
elif T.k < i:
47+
self.Insert(T.r, i, T)
48+
49+
def Sort(self, A):
50+
# random.shuffle(A) # This is use to get randomized Tree.
51+
for i in range(0, len(A)):
52+
self.Insert(self, A[i], None)
53+
54+
def InOrderTreeWalk(self, A):
55+
if self.k is not None:
56+
self.l.InOrderTreeWalk(A)
57+
A.append(self)
58+
self.r.InOrderTreeWalk(A)
59+
60+
def TreeSearch(self, k):
61+
if self.k == k or self.k is None:
62+
return self
63+
elif k < self.k:
64+
return self.l.TreeSearch(k)
65+
else:
66+
return self.r.TreeSearch(k)
67+
68+
def IterativeTreeSearch(self, k):
69+
while self.k is not None and self.k != k:
70+
if k < self.k:
71+
self = self.l
72+
else:
73+
self = self.r
74+
return self
75+
76+
def TreeMinimum(self):
77+
while self.l.k is not None:
78+
self = self.l
79+
return self
80+
81+
def TreeMaxinum(self):
82+
while self.r.k is not None:
83+
self = self.r
84+
return self
85+
86+
87+
A = []
88+
s = random.randint(5, 100)
89+
for i in range(0, s):
90+
A.append(random.randint(0, 1000))
91+
k = random.choice(A)
92+
t = Tree()
93+
t.Sort(A)
94+
A = []
95+
t.InOrderTreeWalk(A)
96+
print "Using InOrderWalk:", [A[i].k for i in range(0, len(A))]
97+
print "Using Recursion method to find ", k, " :", t.TreeSearch(k).k
98+
print "Using Interval method to find ", k, " :", t.IterativeTreeSearch(k).k
99+
print "Finding the Minimum elem :", t.TreeMinimum().k
100+
print "Finding the Maximum elem :", t.TreeMaxinum().k
101+
d = random.choice([A[i].k for i in range(len(A))])
102+
print "we are going to delete:",d
103+
t.TreeDelete(t.TreeSearch(d))
104+
B = []
105+
t.InOrderTreeWalk(B)
106+
print "After deletion:",[B[i].k for i in range(0, len(B))]

‎ChainingHash.py‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
import random
2+
3+
4+
def HashDelete(e, T, s):
5+
i1, i2 = HashSearch(e, T, s)
6+
T[i1].pop(i2)
7+
8+
9+
def HashSearch(e, T, s):
10+
for i in range(0, len(T[e % s])):
11+
if T[e % s][i] == e:
12+
return e % s, i
13+
return None
14+
15+
16+
def HashInsert(e, T, s):
17+
T[e % s].append(e)
18+
19+
20+
print "Now displaying Chaining Hash"
21+
s = 13
22+
A = []
23+
T = [[] for i in range(0, s)]
24+
t = random.randint(5, 100)
25+
for i in range(0, t):
26+
A.append(random.randint(0, 1000))
27+
for e in A:
28+
HashInsert(e, T, s)
29+
print T
30+
e = random.choice(A)
31+
32+
i1, i2 = HashSearch(e, T, s)
33+
print "The selected elem ", e, " is in Slot:", i1, " Position: ", i2
34+
HashDelete(e, T, s)
35+
print "After Deletion:"
36+
print T

‎Dijkstra.py‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
class Vertex:
2+
def __init__(self, key, adjacent):
3+
self.key = key
4+
self.adjacent = adjacent
5+
self.prev = None
6+
7+
8+
class Graph:
9+
def __init__(self):
10+
self.node = {}
11+
12+
def AddVertex(self, key, adjance=[], rank=[]):
13+
A = []
14+
if rank == []:
15+
rank = [1 for i in range(0, len(adjance))]
16+
for i in range(0, len(adjance)):
17+
A.append((self.node[adjance[i]], rank[i]))
18+
19+
self.node[key] = Vertex(key, A)
20+
21+
def AddEdge(self, u, v, r):
22+
for i in self.node[u].adjacent:
23+
if i[0].key == v:
24+
return False
25+
self.node[u].adjacent.append((self.node[v], r))
26+
27+
def Dijkstra(self, s, e):
28+
OPEN = []
29+
CLOSE = []
30+
OPEN.append((self.node[s], 0))
31+
self.Recursion(OPEN, CLOSE, e)
32+
RET = []
33+
i = self.node[e]
34+
while i != None:
35+
RET.append(i)
36+
i = i.prev
37+
RET.reverse()
38+
return RET
39+
40+
def Contains(self, list, e):
41+
for i in list:
42+
if i[0] == e:
43+
return i
44+
return False
45+
46+
def Recursion(self, OPEN, CLOSE, e):
47+
if self.Contains(CLOSE, e):
48+
return
49+
if len(OPEN) == 0:
50+
return
51+
i = OPEN.pop(0)
52+
CLOSE.append(i)
53+
for j in i[0].adjacent:
54+
if self.Contains(CLOSE, j[0]):
55+
continue
56+
con = self.Contains(OPEN, j[0])
57+
if con:
58+
if con[1] > i[1] + j[1]:
59+
OPEN.remove(con)
60+
else:
61+
continue
62+
j[0].prev = i[0]
63+
rank = i[1] + j[1]
64+
OPEN.append((j[0], rank))
65+
OPEN.sort(lambda x, y: cmp(x[1], y[1]))
66+
self.Recursion(OPEN, CLOSE, e)
67+
68+
69+
G = Graph()
70+
G.AddVertex("s")
71+
G.AddVertex("t")
72+
G.AddVertex("x")
73+
G.AddVertex("y")
74+
G.AddVertex("z")
75+
G.AddEdge("s", "t", 10)
76+
G.AddEdge("s", "y", 5)
77+
G.AddEdge("t", "x", 1)
78+
G.AddEdge("t", "y", 2)
79+
G.AddEdge("x", "z", 4)
80+
G.AddEdge("y", "t", 3)
81+
G.AddEdge("y", "x", 9)
82+
G.AddEdge("y", "z", 2)
83+
G.AddEdge("z", "s", 7)
84+
G.AddEdge("z", "x", 6)
85+
path = G.Dijkstra("s", "x")
86+
print [i.key for i in path]
87+
print "DEBUG"

0 commit comments

Comments
 (0)