Python数据结构

发表于 | 更新于 | 分类于 | 阅读次数：

1.实现一个队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# 首先获取节点，包含next指针和该节点位置上元素的值
class Node(object):
    def __init__(self, val):
        self.next = None
        self.val = val


class Queue(object):
    def __init__(self):
        self.first = None
        self.last = None

    # 进队操作
    def enter(self, n):
        # 实例节点
        n = Node(n)
        # 进队之前先判断队列是否为空，即判断first是否为None
        if self.first == None:
            # 此时last==first==n
            self.first = n
            self.last = self.first
        else:
            # 将last的指针设置为n，值设置为n
            self.last.next = n
            self.last = n

    # 出队
    def quit(self):
        if self.first == None:
            return None
        else:
            tmp = self.first.val
            self.first = self.first.next
        return tmp

    # 保存队列元素到列表
    def allQuit(self):
        Lists = []
        while self.first != None:
            Lists.append(self.first.val)
            self.first = self.first.next
        return Lists


if __name__ == '__main__':
    q = Queue()
    q.enter(1)
    q.enter(2)
    q.enter(3)
    # print(q.quit())
    # print(q.quit())
    # print(q.quit())
    # print(q.quit())

    print(q.allQuit())

参考博客园

2.实现一个堆栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Stack(object):
    def __init__(self):
        self.top = None

    # 获取栈顶的值
    def peek(self):
        if self.top != None:
            return self.top.val
        else:
            return None

    # 入栈操作
    def push(self, n):
        n = Node(n)  # 实例化节点
        n.next = self.top
        self.top = n
        return n.val

    # 出栈操作
    def pop(self):
        if self.top == None:
            return None
        else:
            tmp = self.top.val
            # return self.top.val
            self.top = self.top.next  # 栈顶元素下移一位
            return tmp
if __name__ == '__main__':
    s = Stack()
    # s.peek()
    s.push(1)
    print(s.peek())
    s.push(2)
    print(s.peek())
    s.push(3)
    print(s.peek())
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

参考

3.用Python实现一个单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
"""节点类"""


class Node(object):
    def __init__(self, data):
        self.data = data
        self.nex = None

def __init__(self):
    """初始化链表"""
    self.head = None

def __len__(self):
    pre = self.head
    length = 0
    while pre:
        length += 1
        pre = pre.nex
    return length

"""追加节点"""

def append(self, data):
    """
    1.head 为none :head-->node
    2.tail.nex-->node
    :param data:
    :return:
    """
    node = Node(data)
    if self.head is None:
        self.head = node
    else:
        pre = self.head
        while pre.nex:
            pre = pre.nex
        pre.nex = node
# 获取节点
def get(self, index):
    """
    :param index:
    :return:
    """
    index = index if index >= 0 else len(self) + index
    if len(self) < index or index < 0:
        return None
    pre = self.head
    while index:
        pre = pre.nex
        index -= 1
    return pre
"""设置节点"""

def set(self, index, data):
    node = self.get(index)
    if node:
        node.data = data
    return node
"""插入节点"""

def insert(self, index, data):
    """
    1.index 插入节点位置包括正负数
    2.找到index-1-->pre_node的节点
    3.pre_node.next-->node
      node.next-->pre_node.next.next
    4.head
    :param index:
    :param data:
    :return:
    """
    node = Node(data)
    if abs(index + 1) > len(self):
        return False
    index = index if index >= 0 else len(self) + index + 1
    if index == 0:
        node.nex = self.head
        self.head = node
    else:
        pre = self.get(index - 1)
        if pre:
            nex = pre.nex
            pre.nex = node
            node.nex = nex
        else:
            return False
    return node
"""删除某个元素"""

def delete(self, index):
    f = index if index > 0 else abs(index + 1)
    if len(self) <= f:
        return False
    pre = self.head
    index = index if index >= 0 else len(self) + index
    prep = None
    while index:
        prep = pre
        pre = pre.nex
        index -= 1
    if not prep:
        self.head = pre.nex
    else:
        prep.nex = pre.nex
    return pre.data
"""反转链表"""

def __reversed__(self):
    """
    1.pre-->next 转变为 next-->pre
    2.pre 若是head 则把 pre.nex --> None
    3.tail-->self.head
    :return:
    """

    def reverse(pre_node, node):
        if pre_node is self.head:
            pre_node.nex = None
        if node:
            next_node = node.nex
            node.nex = pre_node
            return reverse(node, next_node)
        else:
            self.head = pre_node

    return reverse(self.head, self.head.nex)
"""清空链表"""

def clear(self):
    self.head = None

参考

4.二叉树节点

1
2
3
4
5
6
7
8

class Node(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))

5.前中后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#coding:utf-8
#二叉树的遍历
#简单的二叉树节点类
class Node(object):
    def __init__(self,value,left,right):
        self.value = value
        self.left = left
        self.right = right

#中序遍历:遍历左子树,访问当前节点,遍历右子树

def mid_travelsal(root):
    if root.left is None:
        mid_travelsal(root.left)
    #访问当前节点
    print(root.value)
    if root.right is not None:
        mid_travelsal(root.right)

#前序遍历:访问当前节点,遍历左子树,遍历右子树

def pre_travelsal(root):
    print (root.value)
    if root.left is not None:
        pre_travelsal(root.left)
    if root.right is not None:
        pre_travelsal(root.right)

#后续遍历:遍历左子树,遍历右子树,访问当前节点

def post_trvelsal(root):
    if root.left is not None:
        post_trvelsal(root.left)
    if root.right is not None:
        post_trvelsal(root.right)
    print (root.value)

6.前序中序求后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def rebuild(pre, center):
    if not pre:
        return
    cur = Node(pre[0])
    index = center.index(pre[0])
    cur.left = rebuild(pre[1:index + 1], center[:index])
    cur.right = rebuild(pre[index + 1:], center[index + 1:])
    return cur

def deep(root):
    if not root:
        return
    deep(root.left)
    deep(root.right)
    print root.data

推荐: http://blog.csdn.net/hinyunsin/article/details/6315502

坚持原创技术分享，您的支持将鼓励我继续创作！