# 编程思想-数据结构
数据结构按照其逻辑结构可分为线性结构、树结构、图结构
- 线性结构：数据结构中的元素存在一对一的相互关系
- 树结构：数据结构中的元素存在一对多的相互关系
- 图结构：数据结构中的元素存在多对多的相互关系
# 列表/数组
数组特点
- 数组元素类型相同
- 数组长度固定
# 栈
栈(Stack)是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表
- 栈的特点：后进先出 LIFO（last-in, first-out）
- 栈的概念：栈顶、栈底
- 栈的基本操作：进栈、出栈、取栈顶、是否为空
# 定义栈
class Stack(object):
def __init__(self):
self.stack = []
def push(self, value):
self.stack.append(value)
def pop(self):
return self.stack.pop()
def get_top(self):
if len(self.stack) > 0:
return self.stack[-1]
else:
return None
def is_empty(self):
return len(self.stack) == 0
- 栈的应用：括号匹配问题
def brace_match(row_string):
"""
括号匹配问题
"""
match = {'}': '{', ']': '[', ')': '('}
stack = Stack()
for ch in row_string:
# 左括号入栈
if ch in match.values(): # ch in ['{', '[', '(']
stack.push(ch)
# 右括号出栈
else: # ch in ['}', ']', ')']
if stack.is_empty():
# 1. 为空时异常，返回False
return False
elif stack.get_top() == match[ch]:
# 2. 正常出栈，匹配成功
stack.pop()
else:
# 3. 正常出栈，匹配失败
return False
if stack.is_empty():
return True
else:
return False
print(brace_match('[(){}[]]'))
# 队列
队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除
- 进行插入的一端称为队尾(rear)，插入动作称为进队或入队
- 进行删除的一端称为队头(front)，删除动作称为出队
- 队列的性质：先进先出(First-in, First-out)
队列的实现方式——环形队列
- 环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0
- 队尾指针前进1：rear = (rear + 1) % MaxSize
- 队首指针前进1：front = (front + 1) % MaxSize
- 队空条件：rear == front
- 队满条件：(rear + 1) % MaxS-ize == front
class Queue(object):
def __init__(self, size=100):
self.size = size
self.queue = [0 for _ in range(size)]
self.rear = 0 # 队尾指针，入队
self.front = 0 # 队首指针，出队
def push(self, element):
if not self.is_full():
# 想象一个列表，当新来元素时，self.rear 索引值不断增加，不断指向最后
# 如果只有一个索引 self.rear 只能操作一端 那就是栈了
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = element
else:
raise Exception('队满')
def pop(self):
if not self.is_empty():
# 实际存储和用户使用看起来是相反的
self.front = (self.front + 1) % self.size
return self.queue[self.front]
else:
raise Exception('队空')
def is_empty(self):
"""判断对空"""
return self.rear == self.front
def is_full(self):
"""判断队满"""
return (self.rear + 1) % self.size == self.front
# 链表
链表是由一系列节点组成的元素集合, 每个节点包含两部分, 数据域item和指向下一个节点的指针next, 通过节点之间的相互连接, 最终串联成一个链表
class Node(object):
def __init__(self, item):
self.item = item
self.next = None
def create_head_link_list(li):
"""
头插法 head = Node(li[0]) 指向头节点
"""
head = Node(li[0])
for element in li[1:]:
node = Node(element)
node.next = head
head = node
return head
def create_tail_link_list(li):
"""
尾插法 正序
"""
head = tail = Node(li[0])
for element in li[1:]:
node = Node(element)
tail.next = node
tail = node
return head
# 双链表
双链表的每个节点有两个指针：一个指向后一个节点, 另一个指向前一个节点
class Node(object):
def __init(self, item=None):
self.item = item
self.next = None
self.prior = None
# 链表与顺序表
- 链表在插入和删除的操作上明显快于顺序表
- 链表的内存可以更灵活的分配
- 链表这种链式存储的数据结构对树和图的结构有很大的启发性
# 哈希表
哈希表一个通过哈希函数来计算数据存 储位置的数据结构
- insert(key, value)：插入键值对(key,value)
- get(key)：如果存在键为key的键值对则返回其value，否则返回空值
- delete(key)：删除键为key的键值对
# 二叉树
二叉树的链式存储: 将二叉树的节点定义为一个对象, 节点之间通过类似链表的链接方式来连接
# 基本结构
class BiTreeNode(object):
def __init__(self, data):
self.data = data
self.left_child = None
self.right_child = None
# 手动建树
a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')
e.left_child = a
e.right_child = g
a.right_child = c
c.left_child = b
c.right_child = d
g.right_child = f
root_node = e
def pre_order(root):
"""
前序遍历：先父节点，再left_child, 最后right_child
"""
if root:
print(root.data, end=',')
pre_order(root.left_child)
pre_order(root.right_child)
def in_order(root):
"""中序遍历"""
if root:
in_order(root.left_child)
print(root.data, end=',')
in_order(root.right_child)
def post_order(root):
"""后序遍历"""
if root:
post_order(root.left_child)
post_order(root.right_child)
print(root.data, end=',')
def level_order(root):
"""层级遍历"""
queue = deque()
queue.append(root)
while len(queue) > 0: # 只要对列不空，一直访问
node = queue.popleft()
print(node.data, end=',')
if node.left_child:
queue.append(node.left_child)
if node.right_child:
queue.append(node.right_child)
# 二插搜索树
# coding: utf-8
class BiTreeNode(object):
def __init__(self, data):
self.data = data
self.left_child = None
self.right_child = None
self.parent = None
class BiSearchTree(object):
"""满足左节点小于父节点，右节点大于父节点"""
def __init__(self, li=None):
self.root = None
self.li = li or []
for value in self.li:
self.direct_insert(value)
def insert(self, node, value):
"""
向 node 节点插入 value
:param node:
:param value:
:return: node
"""
if not node:
node = BiTreeNode(value)
elif value < node.data:
node.left_child = self.insert(node.left_child, value)
node.left_child.parent = node
elif value > node.data:
node.right_child = self.insert(node.right_child, value)
node.right_child.parent = node
return node
def direct_insert(self, value):
p = self.root
if not p: # 空树
self.root = BiTreeNode(value)
return
while True:
if value < p.data:
if p.left_child:
p = p.left_child
else:
p.left_child = BiTreeNode(value)
p.left_child.parent = p
return
elif value > p.data:
if p.right_child:
p = p.right_child
else:
p.right_child = BiTreeNode(value)
p.right_child.parent = p
return
else:
return
def pre_order(self, root):
"""
前序遍历：先父节点，再left_child, 最后right_child
"""
if root:
print(root.data, end=',')
self.pre_order(root.left_child)
self.pre_order(root.right_child)
def in_order(self, root):
if root:
self.in_order(root.left_child)
print(root.data, end=',')
self.in_order(root.right_child)
def post_order(self, root):
if root:
self.post_order(root.left_child)
self.post_order(root.right_child)
print(root.data, end=',')
def query(self, node, value):
"""递归版本 需要一个node"""
if not node:
return None
if node.data < value:
return self.query(node.right_child, value)
elif node.data > value:
return self.query(node.left_child, value)
else:
return node
def direct_query(self, value):
p = self.root
while p:
if p.data < value:
p = p.right_child
elif p.data > value:
p = p.left_child
else:
return p
return None
def _remove_node_1(self, node):
"""情况一：node是叶子节点"""
if not node.parent: # 根节点
self.root = None
if node == node.parent.left_child: # node是父节点的左孩子
node.parent.left_child = None
else: # node是父节点的右孩子
node.parent.right_child = None
def _remove_node_21(self, node):
"""
情况二：只有一个左孩子 node.left_child
父节点分两种情况：
node.parent.left_child
node.parent.right_child
"""
if not node.parent: # 根节点
self.root = node.left_child
node.left_child.parent = None
elif node == node.parent.left_child: # node是父节点的左孩子
node.parent.left_child = node.left_child
node.left_child.parent = node.parent
else:
node.parent.right_child = node.left_child
node.left_child.parent = node.parent
def _remove_node_22(self, node):
"""
情况二：只有一个右孩子 node.right_child
父节点分两种情况：
node.parent.left_child
node.parent.right_child
"""
if not node.parent: # 根节点
self.root = node.right_child
node.right_child.parent = None
elif node == node.parent.left_child: # node是父节点的左孩子
node.parent.left_child = node.right_child
node.right_child.parent = node.parent
else:
node.parent.right_child = node.right_child
node.right_child.parent = node.parent
def delete(self, value):
if not self.root:
return False
node = self.direct_query(value)
if not node:
return False
if not node.left_child and not node.right_child:
self._remove_node_1(node)
elif not node.right_child:
self._remove_node_21(node)
elif not node.left_child:
self._remove_node_22(node)
else:
# 两个孩子都有
# 找右子树最小节点min_node，替换到node节点，最后删除min_node
min_node = node.right_child
while node.left_child:
min_node = node.left_child
node.data = min_node.data
if min_node.right_child:
self._remove_node_22(min_node)
else:
self._remove_node_1(min_node)
return True
if __name__ == '__main__':
tree = BiSearchTree([4, 6, 7, 9, 2, 1, 3, 5, 8])
tree.pre_order(tree.root)
print('')
tree.in_order(tree.root)
print('')
tree.post_order(tree.root)
# AVL树
AVL树：AVL树是一棵自平衡的二叉搜索树
- 根的左右子树的高度之差的绝对值不能超过1
- 根的左右子树都是平衡二叉树
B树(B-Tree)：B树是一棵自平衡的多路搜索树。常用于数据库的索引