一些常见数据结构的实现
链表的实现：
#单向链表
class Node():
"""
这个用于实现一个简单的单向链表
"""
def __init__(self, data, Node):
self.data = data
if Node is None:
self.end = 'null'
else:
self.Node = Node
a = Node(1,Node(2,Node(3,None)))#更新链表中的节点
a.Node.data = 3
二叉树的实现：
二叉查找树：对于任意节点，左子节点小于或等于当前节点，后者又小于所有右节点。
树的平衡：这意味着子树的深度不会超过一定值
二叉树遍历：中序，后序和前序
红黑树和平衡二叉树
单词查找树
#如下：
#添加后会变成下面这样
tree = ['A',#root
['B',['D',[],[]],['F',[],[]]],#左节点
['C',[],['E',[],[]]]#右节点
]#大概画成图是这样的
"""
A
B C
D F E
"""
def init_BTree(item):
return [item, [], []]
def insert_left(tree, item):
left_subTree = tree.pop(1)
if left_subTree:
tree.insert(1,[item, left_subTree, []])
else:
tree.insert(1,[item, [], []])
def insert_right(tree, item):
left_subTree = tree.pop(2)
if left_subTree:
tree.insert(2,[item, left_subTree, []])
else:
tree.insert(2,[item, [], []])
def get_left_child(tree):
return tree[1]
def get_right_child(tree):
return tree[2]#上述二叉树的实现
tree = init_BTree('A')
insert_left(tree, 'B')
insert_right(tree, 'C')
insert_left(get_left_child(tree), 'D')
insert_right(get_left_child(tree), 'F')
insert_left(get_right_child(tree), 'E')
insert_right(get_right_child(tree), 'G')
insert_right(get_right_child(tree), 'K')
#还是算比较麻烦的
class TreeNode():
"""
二叉树的实现
"""
def __init__(self, data):
self.data = data
self.left_child = None
self.right_child = None
def insert_left(self, data):
if self.left_child is None:
self.left_child = TreeNode(data)
else:
t = TreeNode(data)
t.left_child = self.left_child
self.left_child = t
def insert_right(self, data):
if self.right_child is None:
self.right_child = TreeNode(data)
else:
t = TreeNode(data)
t.right_child = self.right_child
self.right_child = t#栈的实现
class Stack():
"""
栈的实现，后进先出
"""
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):"""
注意为空怎么办
"""
if self.items:
return self.pop()
else:
return None
def peek(self):"""
这里一样要处理为空怎么办
"""
return self.items[-1]#队列的实现
class Queue():
"""
队列的实现，先进先出
"""
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
self.items.pop(0)#图结构的实现
#图结构的实现
#使用嵌套的字典,来解决
#如下的实现
# A -> B -> C -> D -> A
graph = {'A':['B'],
'B':['C'],
'C':['D'],
'D':['A']
}#key代表着节点，value则是代表着指向的值
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return False
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath:
return newpath
return False#发现所有路径和最短路径的方法一样
扩展性和存储限制
1.大胆假设
如果单台机器能够容纳的下所有数据
2.切合实际
合理拆分数据：
hash除余的方法，将数据分配在各个机器上，为了分布的均匀，可能考虑MD5，是的求出来的值均匀分布，但是这样会出现，一台机器坏了，数据需要重新计算。
所以可以把机器也MD5求值作为一部分，数据放在两台机器MD5值中间。为了解决不均匀问题，可以考虑，虚拟节点。
二分查找：
#给出测试样例
def binary_search(sorted_list, x):"""
实际挺复杂的
"""
high = len(sorted_list)
low = 0
while low <= high:
mid = (low + high)/2
assert low < mid < high
if sorted_list[mid] < x:
low = mid + 1
if sorted_list[mid] > x:
high = mid - 1
if sorted_list[mid] == x:
return mid
return False腾讯云开发者
