Python的拓展数据结构

在Python内置数据结构之外,需要自定义的数据结构成为Python的扩展数据结构。按照元素之间的逻辑关系可以将常用的数据结构按照如下方式进行分类。

映射和集合是一类,它们的元素之间没有逻辑关系。
线性结构中除第一个元素和最后一个元素外,其他元素与元素之间是首尾相接的。
非线性结构的各个元素不再保持首尾相接的顺序,可以存在一对多的连接。

一、线性结构

1、链表(Linked List)

链表是采用链式存储的线性表(区别于顺序存储,如列表、元组)。

(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
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
# coding=utf-8

class Node:
'''链表的节点'''
def __init__(self, item):
# item存放数据元素
self.item = item
# 下一个节点
self.next = None

class SingleLinkList:
'''单链表'''
def __init__(self):
self._head = None

def is_empty(self):
'''判断链表是否为空'''
return self._head is None

def length(self):
'''获取链表长度'''
cur = self._head
count = 0
while cur is not None:
count += 1
# 将cur后移,指向下一个节点
cur = cur.next
return count

def travel(self):
'''遍历链表'''
cur = self._head
print("--------")
while cur is not None:
print(cur.item)
cur = cur.next
print("--------")

def add(self, item):
'''链表头部添加元素'''
node = Node(item)
node.next = self._head
self._head = node

def append(self, item):
'''链表尾部添加元素'''
node = Node(item)
if self.is_empty():
self._head = node
else:
cur = self._head
while cur.next is not None:
cur = cur.next
# 此时cur指向链表最后一个节点,即 next = None
cur.next = node

def insert(self, pos, item):
'''指定位置添加元素'''
# 若指定位置pos为第一个元素之前,则执行头部插入
if pos <= 0:
self.add(item)
# 若指定位置超过链表尾部,则执行尾部插入
elif pos > (self.length() - 1):
self.append(item)
# 找到指定位置
else:
node = Node(item)
cur = self._head
cur_pos = 0
while cur.next is not None:
# 获取需要插入位置的上一个节点
if pos - 1 == cur_pos:
node.next = cur.next
cur.next = node
cur = cur.next
cur_pos += 1

def remove(self, item):
'''删除节点'''
cur = self._head
while cur is not None:
if cur.next.item == item:
cur.next = cur.next.next
break
cur = cur.next

def search(self, item):
'''查找节点是否存在'''
cur = self._head
count = 0
while cur is not None:
if cur.item == item:
return count
cur = cur.next
count += 1
# 找不到元素
if count == self.length():
count = -1
return count

if __name__ == "__main__":
ll = SingleLinkList()
ll.add(1) # 1
ll.add(2) # 2 1
ll.append(3) # 2 1 3
ll.insert(2, 4) # 2 1 4 3
print("length:", ll.length()) # 4
ll.travel() # 2 1 4 3
print("search(3):", ll.search(3)) # 3
print("search(5):", ll.search(5)) # -1
ll.remove(1)
print("length:", ll.length()) # 3
ll.travel() # 2 4 3
(2)单向循环链表

单链表的一个变形是单向循环链表,链表中最后一个节点的链接域不再为None,而是指向链表的头结点。

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
# coding=utf-8

class Node:
'''链表的节点'''
def __init__(self, item):
# item存放数据元素
self.item = item
# 下一个节点
self.next = None

class SinCycLinkedList:
'''单向循环链表'''
def __init__(self):
self._head = None

def is_empty(self):
'''判断链表是否为空'''
return self._head is None

def length(self):
'''链表长度'''
if self.is_empty():
return 0
count = 1
cur = self._head
while cur.next != self._head:
# print("cur", cur.item)
count += 1
cur = cur.next
return count

def travel(self):
'''遍历'''
if self.is_empty():
return

cur = self._head
print(cur.item)
while cur.next != self._head:
cur = cur.next
print(cur.item)

def add(self, item):
'''在头部添加一个节点'''
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
node.next = self._head
cur = self._head
while cur.next != self._head:
cur = cur.next

cur.next = node
self._head = node

def append(self, item):
'''在尾部添加一个节点'''
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
cur = self._head
# print(type(cur), cur.item, cur.next)
while cur.next != self._head:
cur = cur.next

# print(cur.item)
cur.next = node
node.next = self._head

def insert(self, pos, item):
'''指定位置pos添加节点'''
if pos <= 0:
self.add(item)
elif pos > (self.length() - 1):
self.append(item)
else:
node = Node(item)
cur = self._head
cur_pos = 0
while cur.next != self._head:
if (pos - 1) == cur_pos:
node.next = cur.next
cur.next = node
break
cur_pos += 1
cur = cur.next

def remove(self, item):
'''删除一个节点'''
if self.is_empty():
return

pre = self._head
# 删除首节点
if pre.item == item:
cur = pre
while cur.next != self._head:
cur = cur.next

cur.next = pre.next # 删除首节点(跳过该节点)
self._head = pre.next # 重新指定首节点

# 删除其他的节点
else:
cur = pre
while cur.next != self._head:
if cur.next.item == item:
cur.next = cur.next.next
cur = cur.next

def search(self, item):
'''查找节点是否存在'''
if self.is_empty():
return -1

cur_pos = 0
cur = self._head
if cur.item == item:
return cur_pos

while cur.next != self._head:
if cur.item == item:
return cur_pos
cur_pos += 1
cur = cur.next

if cur_pos == self.length() - 1:
return -1

if __name__ == "__main__":
ll = SinCycLinkedList()
ll.add(1) # 1
ll.add(2) # 2 1
ll.travel()
ll.append(3) # 2 1 3
ll.insert(2, 4) # 2 1 4 3
ll.insert(4, 5) # 2 1 4 3 5
ll.insert(0, 6) # 6 2 1 4 3 5
print("length:", ll.length()) # 6
ll.travel() # 6 2 1 4 3 5
print("search(3)", ll.search(3)) # 4
print("search(7)", ll.search(7)) # -1
print("search(6)", ll.search(6)) # 0
print("remove(1)")
ll.remove(1)
print("length:", ll.length()) # 6 2 4 3 5
print("remove(6)")
ll.remove(6)
ll.travel()
(3)双向链表

一种更复杂的链表是 “双向链表” 或 “双面链表”。每个节点有两个链接:一个指向前一个节点,当次节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。

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
# coding=utf-8

class Node:
'''双向链表的节点'''
def __init__(self, item):
self.item = item
self.prev = None
self.next = None

class DLinkList:
'''双向链表'''
def __init__(self):
self._head = None

def is_empty(self):
'''判断链表是否为空'''
return self._head is None

def length(self):
'''获取链表长度'''
if self.is_empty():
return 0
else:
cur = self._head
count = 1
while cur.next is not None:
count += 1
cur = cur.next

return count

def travel(self):
'''遍历链表'''
print("↓↓" * 10)
if self.is_empty():
print("")

else:
cur = self._head
print(cur.item)
while cur.next is not None:
cur = cur.next
print(cur.item)
print("↑↑" * 10)

def add(self, item):
'''链表头部添加节点'''
node = Node(item)
if self.is_empty():
self._head = node
else:
cur = self._head

node.next = cur
cur.prev = node
self._head = node

def append(self, item):
'''链表尾部添加节点'''
node = Node(item)
if self.is_empty():
self._head = node
else:
cur = self._head
# 遍历找到最后一个节点
while cur.next is not None:
cur = cur.next

# 在尾节点添加新的节点
cur.next = node
node.prev = cur

def insert(self, pos, item):
'''指定位置添加'''
# 头部添加
if pos <= 0:
self.add(item)

# 尾部添加
elif pos > (self.length() - 1):
self.append(item)

# 其他位置添加
else:
node = Node(item)

cur = self._head
cur_pos = 0
while cur.next is not None:
if cur_pos == (pos - 1):
# 与下一个节点互相指向
node.next = cur.next
cur.next.prev = node
# 与上一个节点互相指向
cur.next = node
node.prev = cur
cur_pos += 1
cur = cur.next

def remove(self, item):
'''删除节点'''
if self.is_empty():
return
else:
cur = self._head
# 删除首节点
if cur.item == item:
self._head = cur.next
cur.next.prev = None

# 删除其他节点
else:
while cur.next is not None:
if cur.item == item:
# 删除之前:1 ←→ [2] ←→ 3
# 删除之后:1 ←→ 3
cur.prev.next = cur.next
cur.next.prev = cur.prev
cur = cur.next

# 删除尾节点
if cur.item == item:
cur.prev.next = None

def search(self, item):
'''查找节点是否存在'''
if self.is_empty():
return -1
else:
cur = self._head
cur_pos = 0
while cur.next is not None:
if cur.item == item:
return cur_pos

cur_pos += 1
cur = cur.next

if cur_pos == (self.length() - 1):
return -1

if __name__ == "__main__":
ll = DLinkList()
ll.add(1) # 1
ll.add(2) # 2 1
ll.append(3) # 2 1 3
ll.insert(2, 4) # 2 1 4 3
ll.insert(4, 5) # 2 1 4 3 5
ll.insert(0, 6) # 6 2 1 4 3 5
print("length:", ll.length()) # 6
ll.travel() # 6 2 1 4 3 5
print("search(3)", ll.search(3))
print("search(4)", ll.search(4))
print("search(10)", ll.search(10))
ll.remove(1)
print("length:", ll.length())
ll.travel()
print("删除首节点 remove(6):")
ll.remove(6)
ll.travel()
print("删除尾节点 remove(5):")
ll.remove(5)
ll.travel()

2、栈(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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# coding=utf-8

class Stack(object):
'''栈'''
def __init__(self):
self.items = []

def is_empty(self):
'''判断栈是否为空'''
return self.items == []

def size(self):
'''返回栈中元素个数'''
return len(self.items)

def peek(self):
'''返回栈顶元素'''
return self.items[len(self.items) - 1]

def travel(self):
'''打印栈中元素'''
return self.items

def push(self, item):
'''压栈'''
self.items.append(item)

def pop(self):
'''出栈'''
self.items.pop()

if __name__ == "__main__":
s = Stack()
s.push(1)
s.push(2)
print(s.peek())
s.push(3)
print(s.travel())

s.pop()
s.pop()
print(s.travel())

3、队列(Queue)

队列是操作受限制的线性表,特性是先进先出。

(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
# coding=utf-8

class Queue:
'''不定长单向队列'''
def __init__(self):
self.items = []

def is_empty(self):
'''判断队列是否为空'''
return self.items == []

def size(self):
'''返回队列中元素个数'''
return len(self.items)

def travel(self):
'''打印队列中元素'''
return self.items

def enqueue(self, item):
'''往队列添加元素'''
self.items.insert(0, item)

def dequeue(self):
'''从队列头部删除一个元素'''
return self.items.pop()

if __name__ == "__main__":
q = Queue()
q.enqueue("a")
print(q.travel())
q.enqueue("b")
print(q.travel())
q.enqueue("c")
q.dequeue()
print(q.travel())
(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
# coding=utf-8

class Queue:
'''定长单向队列'''
def __init__(self, size=3):
self.items = [None for _ in range(size)] # 创建固定长的列表作为队列
self.tail = 0 # 队尾指针

def is_empty(self):
'''判断队列是否为空'''
return self.items == []

def is_filled(self):
'''判断队列是否已满'''
return self.tail == len(self.items)

def travel(self):
'''打印队列中元素'''
return self.items

def enqueue(self, item):
'''往队列添加元素'''
if not self.is_filled():
self.items[self.tail] = item
self.tail = self.tail + 1 # 队尾指针前进一
else:
print("Queue is filled")

def dequeue(self):
'''从队列头部删除一个元素'''
self.items.pop(0)
self.items.append(None)
self.tail = self.tail - 1

if __name__ == "__main__":
q = Queue(3)
q.enqueue("a")
print(q.travel())
q.enqueue("b")
print(q.travel())
q.enqueue("c")
q.dequeue()
q.dequeue()
q.enqueue("d")
print(q.travel())
(3)双向队列
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
# coding=utf-8

class DQueue:
'''双向队列'''
def __init__(self):
self.items = []

def is_empty(self):
'''判断队列是否为空'''
return self.items == []

def travel(self):
'''打印队列中元素'''
return self.items

def insert_head(self, item):
'''往队列头部添加元素'''
self.items.append(item)

def insert_tail(self, item):
'''往队列尾部添加元素'''
self.items.append(0, item)

def delete_head(self):
'''从队列头部删除一个元素'''
return self.items.pop()

def delete_tail(self):
'''从队列尾部删除一个元素'''
return self.items.pop(0)

if __name__ == "__main__":
q = DQueue()
q.insert_head(1)
q.insert_head(2)
q.insert_head(3)
q.insert_head(4)
print(q.travel())
q.delete_head()
print(q.travel())
q.delete_tail()
print(q.travel())

二、非线性结构

1、树

树是一种非常重要的数据结构。一棵树由根和其他子树组成,这些子树也是树。
二叉树是一种树的特殊化形式,每个父节点最多只有两个孩子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# coding=utf-8

class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

if __name__ == "__main__":
BT = Bnode(2, Bnode(6, 1, Bnode(9, 0, 8)), 10)
print(BT.left.root)
print(BT.left.right.root)
print(BT.right)

树的遍历一般有广度优先遍历(层序遍历)和深度优先遍历(又可分为前序遍历,中序遍历,后序遍历)

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
# coding=utf-8

class Bnode:
'''二叉树的节点'''
def __init__(self, root, left=None, right=None):
self.root = root
self.left = left
self.right = right

class Btree():
'''
二叉树遍历
'''
def preorder(self, node):
'''前序遍历:根左右'''
if node is not None:
print(node.root)
self.preorder(node.left)
self.preorder(node.right)

def inorder(self, node):
'''中序遍历:左根右'''
if node is not None:
self.inorder(node.left)
print(node.root)
self.inorder(node.right)

def postorder(self, node):
'''后序遍历:左右根'''
if node is not None:
self.postorder(node.left)
self.postorder(node.right)
print(node.root)

def BFS(self, node):
'''广度优先遍历'''
if node is not None:
queue = []
queue.append(node)

while queue:
now_node = queue.pop(0)
print(now_node.root)
if now_node.left != None:
queue.append(now_node.left)
if now_node.right != None:
queue.append(now_node.right)

def reverse(self, node):
'''反转树'''
if node is not None:
node.left, node.right = node.right, node.left
self.reverse(node.left)
self.reverse(node.right)


if __name__ == "__main__":
BT = Bnode(2, Bnode(6, Bnode(1), Bnode(9, Bnode(11), Bnode(21))), Bnode(10))

tree = Btree()
print('----前序----')
tree.preorder(BT)
print('----中序----')
tree.inorder(BT)
print('----后序----')
tree.postorder(BT)
print('----广度----')
tree.BFS(BT)
print('----反转后前序----')
tree.reverse(BT)
tree.preorder(BT)

2、图

图结构(Graph)是算法学中最强大的框架之一(树结构只是图的一种特殊情况)。
对于图结构的实现来说,最直观的方式之一就是使用邻接列表。基本上就是针对每个节点设置一个邻接列表。

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
# coding=utf-8

def searchGraph(graph, start, end):
'''在图中搜索两点间路径'''
results = []
generatePath(graph, [start], end, results) # 生成路径
results.sort(key=lambda x:len(x)) # 按路径长短排序
return results

def generatePath(graph, path, end, results):
'''生成路径'''
state = path[-1]
if state == end:
results.append(path)
else:
for arc in graph[state]:
if arc not in path:
generatePath(graph, path + [arc], end, results)

if __name__ == '__main__':

# 用图表示节点的邻接关系
Graph = {'A': ['B', 'C', 'D'],
'B': ['E'],
'C': ['D', 'F'],
'D': ['B', 'E', 'G'],
'E': [],
'F': ['D', 'G'],
'G': ['E']}

r = searchGraph(Graph, 'A','D') # 搜索A到D的所有路径
print('************************')
print('path A to D')
print('************************')
for i in r:
print(i)

r = searchGraph(Graph, 'A','E') # 搜索A到E的所有路径
print('************************')
print('path A to E')
print('************************')
for i in r:
print(i)

r = searchGraph(Graph, 'C','E') # 搜索C到E的所有路径
print('************************')
print(' path C to E')
print('************************')
for i in r:
print(i)
0%