二分查找
1 #!/usr/bin/python
2 # -*- coding: UTF-8 -*-
3 # added by kangye, dependent on python27
4
5 def BinarySearch(l,key):
6 low=
0
7 high=len(l)-1
8 i=
0
9 while(low <=
high):
10 i = i+1
11 mid = low + ((high-low)>>1
)
12 if(l[mid] <
key):
13 low = mid + 1
14 elif (l[mid] >
key):
15 high = mid -1
16 else:
17 print "use %d times" %
i
18 return mid
19 return -1
20
21 if __name__ ==
"__main__":
22 l=[1,4,5,6,7,8,9,44,333,2233
]
23 print l
24 print BinarySearch(l,4
)
25 print BinarySearch(l,44
)
26 print BinarySearch(l,8
)
27 print BinarySearch(l,2233
)
28 print BinarySearch(l,77)
B树
1 #!/usr/bin/python
2 # -*- coding: UTF-8 -*-
3 # added by kangye, dependent on python27
4
5 class BTree:
6 def __init__(self,value):
7 self.left=
None
8 self.data=
value
9 self.right=
None
10
11 def insertLeft(self,value):
12 self.left=
BTree(value)
13 return self.left
14
15 def insertRight(self,value):
16 self.right=
BTree(value)
17 return self.right
18
19 def show(self):
20 print self.data
21
22 def preorder(node):
23 if node.data:
24 node.show()
25 if node.left:
26 preorder(node.left)
27 if node.right:
28 preorder(node.right)
29
30 def inorder(node):
31 if node.data:
32 if node.left:
33 inorder(node.left)
34 node.show()
35 if node.right:
36 inorder(node.right)
37
38 def postorder(node):
39 if node.data:
40 if node.left:
41 postorder(node.left)
42 if node.right:
43 postorder(node.right)
44 node.show()
45
46 if __name__ ==
"__main__":
47
48 Root=BTree(
"root")
49 A=Root.insertLeft(
"A")
50 C=A.insertLeft(
"C")
51 D=C.insertRight(
"D")
52 F=D.insertLeft(
"F")
53 G=D.insertRight(
"G")
54 B=Root.insertRight(
"B")
55 E=B.insertRight(
"E")
56
57 print "pre-traversal"
58 preorder(Root)
59
60 print "in-traversal"
61 inorder(Root)
62
63 print "post-traversal"
64 postorder(Root)
65
66
图
1 #!/usr/bin/python
2 # -*- coding: UTF-8 -*-
3 # added by kangye, dependent on python27
4
5 def searchGraph(graph,start,end):
6 results=
[]
7 generatePath(graph,[start],end,results)
8 results.sort(
lambda x,y:cmp(len(x),len(y)))
9 return results
10
11 def generatePath(graph,path,end,results):
12 state=path[-1
]
13 if state ==
end:
14 results.append(path)
15 else:
16 for arc
in graph[state]:
17 if arc
not in path:
18 generatePath(graph,path+
[arc],end,results)
19
20
21 if __name__ ==
"__main__":
22 Graph=
{
23 'A':[
'B',
'C',
'D'],
24 'B':[
'E'],
25 'C':[
'D',
'F'],
26 'D':[
'B',
'E',
'G'],
27 'E':[],
28 'F':[
'D',
'G'],
29 'G':[
'E']
30 }
31 r = searchGraph(Graph,
'A',
'D')
32 print "A to D"
33 for i
in r:
34 print i
35
36 r=searchGraph(Graph,
'A',
'E')
37 print "A to E"
38 for i
in r:
39 print i
队列
1 #!/usr/bin/python
2 # -*- coding: UTF-8 -*-
3 # added by kangye, dependent on python27
4
5 class Queue:
6 def __init__(self,size=20
):
7 self.queue=
[]
8 self.size=
size
9 self.end=-1
10
11 def setSize(self,size):
12 self.size=
size
13
14 def In(self,element):
15 if self.end < self.size -1
:
16 self.queue.append(element)
17 self.end = self.end + 1
18 else:
19 raise "QueueFull"
20
21 def Out(self):
22 if self.end != -1
:
23 element =
self.queue[0]
24 self.queue=self.queue[1
:]
25 self.end = self.end-1
26 return element
27 else:
28 raise "QueueEmpty"
29
30 def End(self):
31 return self.end
32
33 def empty(self):
34 self.queue=
[]
35 self.end=-1
36
37 if __name__ ==
"__main__":
38
39 queue=
Queue()
40 for i
in range(10
):
41 queue.In(i)
42 print queue.End()
43
44 for i
in range(10
):
45 print queue.Out()
46
47
栈
1 #!/usr/bin/python
2 # -*- coding: UTF-8 -*-
3 # added by kangye, dependent on python27
4
5 class Stack:
6 def __init__(self,size=20
):
7 self.stack=
[]
8 self.size=
size;
9 self.top= -1
10
11 def setSize(self,size):
12 self.size=
size;
13
14 def push(self,element):
15 if self.isFull():
16 raise "StackOverflow"
17 else:
18 self.stack.append(element)
19 self.top = self.top + 1
20
21 def pop(self):
22 if self.isEmpty():
23 raise "StackUnderflow"
24 else:
25 element=self.stack[-1
]
26 self.top=self.top-1
;
27 del self.stack[-1
]
28 return element
29
30 def Top(self):
31 return self.top
32
33 def empty(self):
34 self.stack=
[]
35 self.top=-1
36
37 def isEmpty(self):
38 if self.top == -1
:
39 return True
40 else:
41 return False
42
43 def isFull(self):
44 if self.top == self.size-1
:
45 return True
46 else:
47 return False
48
49 if __name__ ==
"__main__":
50
51 stack=
Stack()
52
53 for i
in range(10
):
54 stack.push(i)
55 print stack.Top()
56
57 for i
in range(10
):
58 print stack.pop()
59
60 stack.empty()
61 print stack.Top()
62
63
转载于:https://www.cnblogs.com/kangye1014/p/5036783.html
