数据结构
栈
class Stack(object):
"""栈"""
def __init__(self):
self.items = []
def is_empty(self):
"""是否为空"""
return self.items == []
def push(self, item):
"""加入元素"""
self.items.append(item)
def pop(self):
"""移除元素"""
return self.items.pop()
def peek(self):
"""栈顶元素"""
return self.items[len(self.items)-1]
def size(self):
"""栈的元素数"""
return len(self.items)
if __name__ == "__main__":
stack = Stack()
stack.push("A")
stack.push("B")
stack.push("C")
print(stack.size())
print(stack.peek())
print(stack.pop())
print(stack.pop())
print(stack.pop())
队列
class Queue(object):
"""队列"""
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self, item):
"""进队列"""
self.items.insert(0,item)
def dequeue(self):
"""出队列"""
return self.items.pop()
def size(self):
"""队列元素数"""
return len(self.items)
if __name__ == "__main__":
q = Queue()
q.enqueue("A")
q.enqueue("B")
q.enqueue("C")
print(q.size())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
链表
class Node(object):
"""
节点类
"""
def __init__(self, value):
self.pre = None
self.value = value
self.next = None
class DoublyLinkedList(object):
"""
双向链表类
"""
def __init__(self):
"""
初始化链表
"""
head = Node(None)
tail = Node(None)
self.head = head
self.tail = tail
self.head.next = self.tail
self.tail.pre = self.head
@property
def length(self):
"""
获取链表长度
:return:
"""
length = 0
node = self.head
while node.next != self.tail:
length += 1
node = node.next
return length
def print(self):
"""
打印
:return:
"""
if self.length == 0:
print('Nothing')
else:
node = self.head.next
print('[', end='')
while node.next != self.tail:
print(node.value, ', ', end='')
node = node.next
print('%s]' % node.value)
def append(self, value):
"""
表尾添加节点
:return:
"""
node = Node(value)
pre = self.tail.pre
# 两点之间进行双双链接
pre.next = node
node.pre = pre
node.next = self.tail
self.tail.pre = node
return node
def get(self, index):
"""
获取节点
:param index:
:return:
"""
if index < 0 or index > self.length:
print('Index错误，索引越界')
return None
else:
node = self.head.next
while index:
node = node.next
index -= 1
return node
def insert(self, index, value):
"""
插入
:param index:
:param value:
:return:
"""
if index < 0 or index > self.length:
print('Index 错误, 索引越界')
next_node = self.get(index)
# 开始插入
node = Node(value)
pre_node = next_node.pre
pre_node.next = node
node.pre = pre_node
node.next = next_node
next_node.pre = node
return node
def delete(self, index):
"""
删除节点
:param index:
:return:
"""
node = self.get(index)
if node:
node.pre.next = node.next
node.next.pre = node.pre
return True
else:
return False
def reverse(self):
"""
反转链表
:return:
1.node.next --> node.pre
node.pre --> node.next
2.head.next --> None
tail.pre --> None
3.head-->tail
tail-->head
"""
pre_head = self.head
tail = self.tail
# 调用递归，对每个节点进行交换位置
def reverse(pre_node, node):
if node:
next_node = node.next
node.next = pre_node
pre_node.pre = node
if pre_node is self.head:
pre_node.next = None
if node is self.tail:
node.pre = None
return reverse(node, next_node)
else:
self.head = tail
self.tail = pre_head
return reverse(self.head, self.head.next)
def clear(self):
"""
清空链表
:return:
"""
self.head.next = self.tail
self.tail.pre = self.head
if __name__ == '__main__':
l = DoublyLinkedList()
# 测试在表尾添加节点
l.append(3)
l.append(4)
l.append(5)
l.print()
# 测试get
i = 0
print('第', i, '个元素为: ', l.get(i).value)
# 测试索引插入
print('索引插入...')
l.insert(1, 7)
l.insert(0, 8)
l.print()
# 测试删除节点
print('删除节点...')
l.delete(0)
l.delete(3)
l.print()
# 测试反转
print('反转...')
l.reverse()
l.print()
# 测试清空
print('清空...')
l.clear()
l.print()
# 测试长度
print('链表长度为: ', l.length)
双向队列
class Deque(object):
"""双端队列"""
def __init__(self):
self.items = []
def is_empty(self):
"""判断队列是否为空"""
return self.items == []
def add_front(self, item):
"""在队头添加元素"""
self.items.insert(0,item)
def add_rear(self, item):
"""在队尾添加元素"""
self.items.append(item)
def remove_front(self):
"""从队头删除元素"""
return self.items.pop(0)
def remove_rear(self):
"""从队尾删除元素"""
return self.items.pop()
def size(self):
"""返回队列大小"""
return len(self.items)
if __name__ == "__main__":
deque = Deque()
deque.add_front(1)
deque.add_front(2)
deque.add_rear(3)
deque.add_rear(4)
print(deque.size())
print(deque.remove_front())
print(deque.remove_front())
print(deque.remove_rear())
print(deque.remove_rear())
树
class Node:
def __init__(self,root="NIL",left=None,right=None):
self.root = root
self.left = left
self.right = right
self.out_list_temp = []
class Tree(Node):
def build(self,node_list):
root = node_list.pop(0)
if root == "NIL":
tree = None
else:
tree = Tree(root)
tree.left = self.build(node_list)
tree.right = self.build(node_list)
return tree
def preorder_traversal(self,tree):
if (tree.root != None):
self.out_list_temp.append(tree.root)
if tree.left != None:
self.preorder_traversal(tree.left)
if tree.right != None:
self.preorder_traversal(tree.right)
return self.out_list_temp
def preorder_traversal_print(self,tree):
print(self.preorder_traversal(tree))
self.out_list_temp = []
def inorder_traversal(self,tree):
if tree.left != None:
self.inorder_traversal(tree.left)
if (tree.root != None):
self.out_list_temp.append(tree.root)
if tree.right != None:
self.inorder_traversal(tree.right)
return self.out_list_temp
def inorder_traversal_print(self,tree):
print(self.inorder_traversal(tree))
self.out_list_temp = []
def postorder_traversal(self,tree):
if tree.left != None:
self.postorder_traversal(tree.left)
if tree.right != None:
self.postorder_traversal(tree.right)
if (tree.root != None):
self.out_list_temp.append(tree.root)
return self.out_list_temp
def postorder_traversal_print(self,tree):
print(self.postorder_traversal(tree))
self.out_list_temp = []
if __name__ == '__main__':
node_list = [1,4,2,'NIL','NIL',5,'NIL','NIL',3,'NIL',6,7,'NIL','NIL','NIL']
tree = Tree()
my_tree = tree.build(node_list)
tree.preorder_traversal_print(my_tree)
tree.inorder_traversal_print(my_tree)
tree.postorder_traversal_print(my_tree)
图
class Graph(object):
def __init__(self,graph):
self.graph=graph
def find_path(self, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not self.graph.__contains__(start):
return None
for node in graph[start]:
if node not in path:
newpath = self.find_path(node, end, path)
if newpath: return newpath
return None
def find_all_paths(self,start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not self.graph.__contains__(start):
return []
paths = []
for node in self.graph[start]:
if node not in path:
newpaths = self.find_all_paths(node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
def find_shortest_path(self, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not self.graph.__contains__(start):
return None
shortest = None
for node in self.graph[start]:
if node not in path:
newpath = self.find_shortest_path(node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
if __name__ == "__main__":
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C','F'],
'E': ['F'],
'F': ['C']}
obj=Graph(graph)
#print(obj.find_all_paths('A','C'))
#print(obj.find_all_paths('A','A'))
print(obj.find_all_paths('B','A'))
算法
回溯法
动态规划，贪心算法，分治算法
链表
堆
图
树
双指针
