一些常见数据结构的实现

链表的实现:

#单向链表

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

原文发布于微信公众号 - 鸿的学习笔记(shujuxuexizhilu)

原文发表时间:2017-08-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

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

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

34870
来自专栏腾讯数据库技术

如何利用红黑树实现排名?

27730
来自专栏菩提树下的杨过

数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义 1、路径 Path 简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的...

29190
来自专栏Python小屋

Python求解一元二次方程根

本文使用Python实现一元二次方程求根公式,主要演示运算符和几个内置函数的用法,封面图片与本文内容无关。 def root(a, b, c, highmidd...

45340
来自专栏小二的折腾日记

LeetCode-34-Search-for-a-Range

在一个排序的数组中找到出现这个值的起点和重点。很容易想到的是二分查找了。复杂度为nlog(n)。思路如下,先二分查找,找到下界,如果下界lo的值不等于targe...

8330
来自专栏Petrichor的专栏

leetcode: 90. Subsets II

11830
来自专栏Golang语言社区

转--Go语言用堆排序的方法进行一千万个int随机数排序

上篇文章用的是quicksort方法排序,但是如果用快速排序法对重复率很高的slice排序的时候,时间复杂度会激增,速度相当慢 所以尝试了一下堆排序,实验结果,...

39370
来自专栏Bingo的深度学习杂货店

Q111 Minimum Depth of Binary Tree

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

27740
来自专栏程序生活

斯坦福tensorflow教程-实例代码简单代码关于占位符 placeholder与feed_dictvariable 变量

16330
来自专栏前端儿

重建二叉树

题目很简单,给你一棵二叉树的后序和中序序列,求出它的前序序列(So easy!)。

26110

扫码关注云+社区

领取腾讯云代金券