萤火

有一份热，发一分光

0%

算法基础 1 - 序列 Sequence Interface

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

定义

序列用于维护数据元素的外部顺序，每个元素按照等级顺序存储在序列中。这里的外部顺序，是指在接口以外定义的，例如排序顺序、优先级顺序等。序列接口是栈和队列的一般化表示。

接口

实现

数组（Array Sequence）

  • 在RAM模型下，机器可以直接访问已知地址，因此get_at和set_at操作需要常数时间O(1)
  • 当时数组长度发生变化时，存储空间需要重新分配，因此需要线性时间O(n)
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
class Array_Seq():
    def __init__(self):                     # O(1)
        self.A = []
        self.size = 0

    def __len__(self): return self.size     # O(1)
    def __iter__(self): yield from self.A   # O(n)

		def build(self, X):                     # O(n)
        self.A = [None] * len(X)            # pretend this builds a static array
        i = 0
        for a in X:
            self.A[i] = a
            i += 1
        self.size = len(self.A)

    def get_at(self, i): return self.A[i]   # O(1)
    def set_at(self, i, x): self.A[i] = x   # O(1)

    def insert_at(self, i, x):              # O(n)
        n = len(self)
        new_A = [None] * (n + 1)
        for k in range(i-1):
            new_A[k] = self.A[k]
        for k in range(i-1, n):
            new_A[k+1] = self.A[k]
        new_A[i-1] = x
        self.build(new_A)

    def delete_at(self, i):                 # O(n)
        n = len(self)
        x = self.A[i-1]
        new_A = [None] * (n - 1)
        for k in range(i-1):
            new_A[k] = self.A[k]
        for k in range(i, n):
            new_A[k-1] = self.A[k]
        self.build(new_A)
        return x

    def insert_first(self, x):  self.insert_at(1, x)
    def insert_last(self,  x):  self.insert_at(len(self)+1, x)
    def delete_first(self): return self.delete_at(1)
    def delete_last(self): return self.delete_at(len(self))
		
# 备注：程序中的序号是以1为开始的

链表（Linked ）

  • 有离散的节点组成，每个节点包括一个数据和一个指向下个节点的地址（指针）
  • 只能通过一个节点一个节点的跳转实现指定的索引，时间复杂度为O(n)
  • 适合于序列的增减操作，尤其是在首尾的增减
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
class Linked_List_Node:
    def __init__(self, x):
        self.item = x
        self.next = None

    def later_node(self, i):
        if i == 0:
            return self
        assert self.next
        return self.next.later_node(i-1)

class Linked_list_Seq:
    def __init__(self):
        self.head = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        node = self.head
        while node:
            yield node.item
            node = node.next

    def build(self, X):                     # O(n)
        for a in reversed(X):
            self.insert_first(a)

    def get_at(self, i):                    # O(i)
        node = self.head.later_node(i-1)
        return node.item

    def set_at(self, i, x):                 # O(i)
        node = self.head.later_node(i-1)
        node.item = x

    def insert_first(self, x):              # O(1)
        new_node = Linked_List_Node(x)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def delete_first(self):                 # O(1)
        x = self.head.item
        self.head = self.head.next
        self.size -= 1
        return x

    def insert_at(self, i, x):              # O(i)
        if i == 1:
            self.insert_first(x)
        else:
            new_node = Linked_List_Node(x)
            pre_node = self.head.later_node(i-1-1)
            new_node.next = pre_node.next
            pre_node.next = new_node
            self.size += 1

    def delete_at(self, i):                 # O(i)
        if i == 1:
            return self.delete_first()
        else:
            pre_node = self.head.later_node(i-2)
            x = pre_node.next.item
            pre_node.next = pre_node.next.next
            self.size -= 1
            return x

                                            # O(n)
    def insert_last(self, x): self.insert_at(len(self)+1, x)
    def delete_last(self): return self.delete_at(len(self))

动态数组

  • 通过额外分配一定存储空间（如2倍于所需长度），来实现更快速的元素插入；当数组长度超过最大空间时，依然需要重新分配空间，但插入操作的平摊时间是常数的O(1)
  • 当数组长度远小于分配空间时，占用大量存储空间较为浪费，需要重新分配较小的空间（如小于存储空间1/4时，重新分配1/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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# 继承001的静态数组
class Dynamic_Array_Seq(Array_Seq):
    def __init__(self, r=2):                # O(1)
        super().__init__()
        self.r = r
        self._compute_bnouds()
        self._resize(0)

    def __len__(self): return self.size     # O(1)

    def __iter__(self):                     # O(n)
        for i in range(len(self)):
            yield self.A[i]

    def build(self, X):                     # O(n)
        for a in X:
            self.insert_last(a)

    def _compute_bnouds(self):              # O(1)
        self.upper = len(self.A)
        self.lower = len(self.A) // (self.r * self.r)

    def _resize(self, n):                   # O(1) / O(n)
        if(self.lower < n < self.upper):
            return
        m = max(n, 1) * self.r
        A = [None] * m
        for i in range(self.size):
            A[i] = self.A[i]
        self.A = A
        self._compute_bnouds()

    def insert_last(self, x):               # O(1)a
        self._resize(self.size + 1)
        self.size += 1
        self.A[self.size-1] = x

    def delete_last(self):                  # O(1)a
        self.A[self.size - 1] = None
        self.size -= 1
        self._resize(self.size)

    def insert_at(self, i, x):              # O(n)
        self.insert_last(None)
        for k in range(self.size, i-1, -1):
            self.A[k] = self.A[k-1]
        self.A[i-1] = x

    def delete_at(self, i):                 # O(n)
        x = self.A[i-1]
        for k in range(i, self.size):
            self.A[k-1] = self.A[k]
        self.delete_last()
        return x

                                            # O(n)
    def insert_first(self, x): self.insert_at(1, x)
    def delete_first(self): return self.delete_at(1)

二叉树（AVL树）

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
def height(A):
    if A:
        return A.height
    else:
        return -1

class Binary_Node:
    def __init__(A, x):
        A.item = x
        A.left = None
        A.right = None
        A.parent = None
        A.subtree_update()

    def subtree_update(A):
        A.height = 1 + max(height(A.left), height(A.right))

    def skew(A):
        return height(A.right) - height(A.left)

    def subtree_iter(A):
        if A.left:
            yield from A.left.subtree_iter()
        yield A
        if A.right:
            yield from A.right.subtree_iter()

    def subtree_first(A):
        if A.left:
            return A.left.subtree_first()
        else:
            return A

    def subtree_last(A):
        if A.right:
            return A.right.subtree_last()
        else:
            return A

    def successor(A):
        if A.right:
            return A.right.subtree_first()
        while A.parent and (A is A.parent.right):
            A = A.parent
        return A.parent

    def predecessor(A):
        if A.left:
            return A.left.subtree_last()
        while A.parent and (A is A.parent.left):
            A = A.parent
        return A.parent

    def subtree_rotate_right(D):
        if D.left:
            B, E = D.left, D.right
            A, C = B.left, B.right
            D, B = B, D
            D.item, B.item = B.item, D.item
            B.left, B.right = A, D
            D.left, D.right = C, E
            if A:
                A.parent = B
            if E:
                E.parent = D

    def subtree_rotate_left(B):
        if B.right:
            A, D = B.left, B.right
            C, E = D.left, D.right
            B, D = D, B
            B.item, D.item = D.item, B.item
            D.left, D.right = B, E
            B.left, B.right = A, C
            if A:
                A.parent = B
            if E:
                E.parent = D

    def rebalance(A):
        if A.skew == 2:
            if A.right.skew() < 0:
                A.right.subtree_rotate_right()
            A.subtree_rotate_left()
        elif A.skew() == -2:
            if A.left.skew() > 0:
                A.left.subtree_rotate_left()
            A.subtree_rotate_right()

    def maintain(A):
        A.rebalance()
        A.subtree_update()
        if A.parent:
            A.parent.maintain()

    def subtree_insert_before(A, B):
        if A.left:
            A = A.left.subtree_last()
            A.right, B.parent = B, A
        else:
            A.left, B.parent = B, A
        A.maintain()

    def subtree_insert_after(A, B):
        if A.right:
            A = A.right.subtree_first()
            A.left, B.parent = B, A
        else:
            A.right, B.parent = B, A
        A.maintain()

    def subtree_delete(A):
        if A.left or A.right:
            if A.left:
                B = A.predecessor()
            else:
                B = A.successor()
            A.item, B.item = B.item, A.item
            return B.subtree_delete()
        if A.parent:
            if A is A.parent.left:
                A.parent.left = None
            else:
                A.parent.right = None
            A.maintain()
        return A

class Binary_Tree:
    def __init__(T, Node_Type=Binary_Node):
        T.root = None
        T.size = 0
        T.Node_Type = Node_Type

    def __len__(T): return T.size

    def __iter__(T):
        if T.root:
            for A in T.root.subtree_iter():
                yield A.item

class Size_Node(Binary_Node):
    def subtree_update(A):
        super().subtree_update()
        A.size = 1
        if A.left:
            A.size += A.left.size
        if A.right:
            A.size += A.right.size

    def subtree_at(A, i):
        if 0 <= i:
            if A.left:
                L_size = A.left.size
            else:
                L_size = 0
            if i < L_size:
                return A.left.subtree_at(i)
            elif i > L_size:
                return A.right.subtree_at(i - L_size - 1)
            else:
                return A

class Seq_Binary_Tree(Binary_Tree):
    def __init__(self):
        super().__init__(Size_Node)

    def build(self, X):
        def build_subtree(X, i, j):
            c = (i + j) // 2
            root = self.Node_Type(X[c])
            if i < c:
                root.left = build_subtree(X, i, c - 1)
                root.left.parent = root
            if c < j:
                root.right = build_subtree(X, c + 1, j)
                root.right.parent = root
            root.subtree_update()
            return root
        self.root = build_subtree(X, 0, len(X) - 1)
        self.size = self.root.size

    def get_at(self, i):
        if self.root:
            return self.root.subtree_at(i).item

    def set_at(self, i, x):
        if self.root:
            self.root.subtree_at(i).item = x

    def insert_at(self, i, x):
        new_node = self.Node_Type(x)
        if i == 0:
            if self.root:
                node = self.root.subtree_first()
                node.subtree_insert_before(new_node)
            else:
                self.root = new_node
        else:
            node = self.root.subtree_at(i - 1)
            node.subtree_insert_after(new_node)
        self.size += 1

    def delete_at(self, i):
        if self.root:
            node = self.root.subtree_at(i)
            ext = node.subtree_delete()
            if ext.parent is None:
                self.root = None
            self.size -= 1
            return ext.item

    def insert_first(self, x): self.insert_at(0, x)
    def delete_first(self, x): return self.delete_at(0)
    def insert_last(self, x): self.insert_at(len(self), x)
    def delete_last(self): return self.delete_at(len(self)-1)