一些常见数据结构的实现

#单向链表

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，是的求出来的值均匀分布，但是这样会出现，一台机器坏了，数据需要重新计算。

#给出测试样例

`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```

251 篇文章33 人订阅

0 条评论

相关文章

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王：我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

34870

27730

29190

45340

8330

11830

39370

Q111 Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

27740

16330

26110