前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一些常见数据结构的实现

一些常见数据结构的实现

作者头像
哒呵呵
发布2018-08-06 15:12:13
1680
发布2018-08-06 15:12:13
举报
文章被收录于专栏:鸿的学习笔记

链表的实现:

#单向链表

class Node():

"""

这个用于实现一个简单的单向链表

"""

代码语言:javascript
复制
    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

二叉树的实现:

二叉查找树:对于任意节点,左子节点小于或等于当前节点,后者又小于所有右节点。

树的平衡:这意味着子树的深度不会超过一定值

二叉树遍历:中序,后序和前序

红黑树和平衡二叉树

单词查找树

#如下:

#添加后会变成下面这样

代码语言:javascript
复制
tree = ['A',#root
        ['B',['D',[],[]],['F',[],[]]],#左节点
        ['C',[],['E',[],[]]]#右节点
        ]

#大概画成图是这样的

"""

A

B C

D F E

"""

代码语言:javascript
复制
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():

"""

二叉树的实现

"""

代码语言:javascript
复制
    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():

"""

栈的实现,后进先出

"""

代码语言:javascript
复制
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):

"""

注意为空怎么办

"""

代码语言:javascript
复制
        if self.items:            
            return self.pop()
        else:
            return None
    def peek(self):

"""

这里一样要处理为空怎么办

"""

代码语言:javascript
复制
        return self.items[-1]

#队列的实现

class Queue():

"""

队列的实现,先进先出

"""

代码语言:javascript
复制
    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

代码语言:javascript
复制
graph = {'A':['B'],
       'B':['C'],
       'C':['D'],
       'D':['A']
       }

#key代表着节点,value则是代表着指向的值

代码语言:javascript
复制
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值中间。为了解决不均匀问题,可以考虑,虚拟节点。

二分查找:

#给出测试样例

代码语言:javascript
复制
def binary_search(sorted_list, x):

"""

实际挺复杂的

"""

代码语言:javascript
复制
    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
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2017-08-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 鸿的学习笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档