前言

常用数据结构的python实现，一方面是复习，一方面是给自己做个备份吧。

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

特点：先进后出，新进的在栈顶，出栈的为栈顶元素

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
class Stack:
    def __init__(self):
        self.stack = []

    def __sizeof__(self):
        return len(self.stack)

    def isEmpty(self):
        return len(self.stack) == 0

    def pop(self):
        if self.isEmpty():
            print("空栈不能弹出")
        else:
            return self.stack.pop()

    def push(self,num):
        self.stack.append(num)

    def top(self):
        '''
         查看栈顶元素
        :return:栈顶元素
        '''
        if not self.isEmpty():
            return self.stack[-1]

单链表

相对于列表，链表在插入删除方面的时间复杂度极低，为O(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
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
class Node:
    '''
    节点
    '''

    def __init__(self, data):
        self.data = data
        self.next = None


class Link_List:

    def __init__(self):
        self.head = None

    def initList(self, data_list):
        self.head = Node(data_list[0])
        tmp = self.head
        for i in data_list[1:]:
            node = Node(i)
            tmp.next = node
            tmp = tmp.next

    def isEmpty(self):
        if self.head == None:
            return True
        else:
            return False

    def length(self):
        tmp = self.head
        longth = 0
        while tmp != None:
            longth += 1
            tmp = tmp.next
        return longth

    def insert(self, index, value):
        '''

        :param index: 位置索引
        :param value: 插入的值
        '''
        if index < 0 or index > self.length():
            print("索引错误！")
        else:
            tmp = self.head
            while index >= 0:
                pre = tmp
                tmp = tmp.next
                index -= 1
            node = Node(value)
            pre.next = node
            node.next = tmp

    def printList(self):
        print("打印链表：")
        tmp = self.head
        print_list = []
        while tmp != None:
            print_list.append(tmp.data)
            tmp = tmp.next
        print(print_list)

    def delete(self, index):
        if index < 0 or index > self.length():
            print("索引错误！")
        else:
            tmp = self.head
            while index >= 0:
                pre = tmp
                tmp = tmp.next
                index -= 1
            pre.next = tmp.next

    def reverse(self):
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

特点：先进后出，队列头出列，新进的在队尾

链表实现

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
class Node:
    def __init__(self, vlaue, next=None):
        self.value = vlaue
        self.next = next


class Queue:
    def __init__(self):
        # 头节点
        self.head = None
        # 尾节点
        self.rear = None

    def isEmpty(self):
        return self.head is None

    def enqueue(self, value):
        '''
        入列
        '''
        node = Node(value)
        if self.isEmpty():
            # 如果队列当前为空
            self.head = node
            self.rear = node
        else:
            # 当前不为空,入队尾
            self.rear.next = node
            self.rear = node

    def dequeue(self):
        # 出列
        if self.isEmpty():
            print("当前队列为空")
        else:
            de = self.rear.value
            self.head = self.head.next
            return de

    def peek(self):
        # 返回队列头部元素，但是不出队列
        if self.isEmpty():
            print("当前队列为空")
        else:
            return self.head.value

    def printQueue(self):
        print("队列：")
        tmp = self.head
        tmpList = []
        while tmp is not None:
            tmpList.append(tmp.value)
            tmp = tmp.next
        print(tmpList)

列表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Queue:
    def __init__(self):
        self.entries = []  # 表示队列内的参数
        self.length = 0  # 表示队列的长度
        self.front = 0  # 表示队列头部位置

    def enqueue(self, item):
        self.entries.append(item)  # 添加元素到队列里面
        self.length = self.length + 1  # 队列长度增加 1

    def dequeue(self):
        self.length = self.length - 1  # 队列的长度减少 1
        dequeued = self.entries[self.front]  # 队首元素为dequeued
        self.front -= 1  # 队首的位置减少1
        self.entries = self.entries[self.front:]  # 队列的元素更新为退队之后的队列
        return dequeued

    def peek(self):
        return self.entries[0]  # 直接返回队列的队首元素

二叉树

删除节点：

  • 被删除的结点是叶子结点：直接删除
  • 被删除的节点只有一个叶子节点：将其唯一叶子节点仍然与父节点相连，原来是父节点的左节点，那么其子节点仍连为父节点的左节点，右同。
  • 被删除的节点有两个叶子节点：判断删除的节点的右子节点有无左子节点，如无，将右子节点替换删除的节点即可；如有，找到最左子节点，去替换要删除的节点，还要注意最左子节点可能也有右子节点，这个节点也要接到最左子节点的父节点上去
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
class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.item)


class Tree:
    def __init__(self):
        self.root = None('root')  # 根节点不变

    def add(self, item):
        node = None(item)
        if self.root is None:
            self.root = Node
        else:  # 从根节点开始往下判断哪个子节点为空
            q = [self.root]  # 用列表来实现队列深度搜索
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                    return
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)

    def get_parent(self, item):
        if self.root.item == item:
            print("根节点没有父节点")
            return None
        else:
            tmp = [self.root]
            while tmp:
                pop_node = tmp.pop(0)
                if pop_node.left and pop_node.left.item == item:
                    return pop_node
                if pop_node.right and pop_node.right.item == item:
                    return pop_node
                if pop_node.left is not None:
                    tmp.append(pop_node.left)
                if pop_node.right is not None:
                    tmp.append(pop_node.right)
            return None

    def delete(self, item):
        if self.root is None:  # 如果根为空，就什么也不做
            return False
        parent = self.get_parent(item)
        if parent:
            del_node = parent.left if parent.left.item == item else parent.right  # 待删除节点
            if del_node.left is None:
                if parent.left.item == item:
                    parent.left = del_node.right
                else:
                    parent.right = del_node.right
                del del_node
                return True
            elif del_node.right is None:
                if parent.left.item == item:
                    parent.left = del_node.left
                else:
                    parent.right = del_node.left
                del del_node
                return True
            else:  # 左右子树都不为空
                tmp_pre = del_node
                tmp_next = del_node.right
                if tmp_next.left is None:
                    # 替代
                    tmp_pre.right = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right

                else:
                    while tmp_next.left:  # 让tmp指向右子树的最后一个叶子
                        tmp_pre = tmp_next
                        tmp_next = tmp_next.left
                    # 替代
                    tmp_pre.left = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                if parent.left.item == item:
                    parent.left = tmp_next
                else:
                    parent.right = tmp_next
                del del_node
                return True
        else:
            return False

堆

在之前的文章中实现了，详情可以看排序算法的堆排序部分。