1.堆栈(pyStack.py)
class PyStack:
def __init__(self, size=20):
self.stack = []
self.size = size
self.top = -1
def setSize(self, size):
self.size = size
def push(self, element):
if self.isFull():
raise IndexError
else:
self.stack.append(element)
self.top += 1
def pop(self):
if self.isEmpty():
raise 'PyStackUnderflow'
else:
element = self.stack[-1]
self.top -= 1
del self.stack[-1]
return element
def getTop(self):
return self.top
def empty(self):
self.stack = []
self.top = -1
def isEmpty(self):
if self.top == -1:
return True
else:
return False
def isFull(self):
if self.top == self.size-1:
return True
else:
return False
if __name__ == '__main__':
stack = PyStack()
for i in range(10):
stack.push(i)
print('栈顶是：', stack.getTop())
for i in range(10):
print(stack.pop())
stack.empty()
for i in range(21):
stack.push(i)
2.队列(PyQueue.py)
class QueueException(Exception):
def __init__(self, info):
super(QueueException, self).__init__()
print('队列异常:', info)
class PyQueue:
def __init__(self, size=20):
self.queue = []
self.size = 20
self.end = -1
def setSize(self, size):
self.size = size
def inQueue(self, element):
if self.end < self.size-1:
self.queue.append(element)
self.end += 1
else:
raise QueueException('队尾越界')
def outQueue(self):
if self.end != -1:
element = self.queue[0]
self.queue = self.queue[1:]
self.end -= 1
return element
else:
raise QueueException('队头越界')
def getEndIndex(self):
return self.end
def empty(self):
self.queue = []
self.end = -1
if __name__ == '__main__':
queue = PyQueue()
for i in range(20):
queue.inQueue(str(i)*3)
print('队尾Index:', queue.getEndIndex())
for i in range(20):
print(queue.outQueue())
# queue.outQueue()
3.树(PyTree.py)
G = ['G', []] H = ['H', []] I = ['I', []] K = ['K', []] D = ['D', []] E = ['E', [G, H, I, K]] F = ['F', []] A = ['A', [D, E]] B = ['B', []] C = ['C', [F]] Root = ['Root', [A, B, C]] print(Root)
4.二叉树(pyBTree.py)
class BTree:
def __init__(self, value):
self.value = value
self.left = None
self.Right = None
def insertLeft(self, value):
self.left = BTree(value)
return self.left
def insertRight(self, value):
self.right = BTree(value)
return self.right
def show(self):
print(self.value)
if __name__ == '__main__':
Root = BTree('Root')
A = Root.insertLeft('A')
C = A.insertLeft('C')
D = A.insertRight('D')
F = D.insertLeft('F')
G = D.insertRight('G')
B = Root.insertRight('B')
E = B.insertRight('E')
Root.show()
Root.left.show()
Root.right.show()
Root.right.right.show()
5.二叉树的遍历(pyBTreeTraversal.py)
class BTree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insertLeft(self, value):
self.left = BTree(value)
return self.left
def insertRight(self, value):
self.right = BTree(value)
return self.right
def show(self):
print(self.value)
def preOrder(self):
self.show()
if self.left:
self.left.preOrder()
if self.right:
self.right.preOrder()
def inOrder(self):
if self.left:
self.left.inOrder()
self.show()
if self.right:
self.right.inOrder()
def postOrder(self):
if self.left:
self.left.postOrder()
if self.right:
self.right.postOrder()
self.show()
Root = BTree('Root')
A = Root.insertLeft('A')
C = A.insertLeft('C')
D = A.insertRight('D')
F = D.insertLeft('F')
G = D.insertRight('G')
B = Root.insertRight('B')
E = B.insertRight('E')
Root.postOrder()
6.图的构造以及路径查找(pyGraph.py)
注意：(list).sort(key=len)按长度排序
也可以写成sorted((list), key=len)
默认排序是index
Python3里的(list).sort()已不支持lambda表达式
def searchGraph(graph, start, end):
results = []
generatePath(graph, [start], end, results)
results.sort(key=len)
return results
def generatePath(graph, path, end, results):
state = path[-1]
if state==end:
results.append(path)
# path = []
else:
for arc in graph[state]:
if arc not in path:
generatePath(graph, path+[arc], end, results)
if __name__=='__main__':
Graph = {'A': ['B', 'C', 'D'],
'B': ['E'],
'C': ['D', 'F'],
'D': ['B', 'E', 'G'],
'E': [],
'F': ['D', 'G'],
'G': ['E']}
paths = searchGraph(Graph, 'A', 'D')
for i in paths:
print(i)