Data Structure 数据结构

Question

Array

class Array:
  # 使用Python列表实现
  def __init__(self, x):
    self.data = list(x)
  # 数组元素的个数
  def size(self):
    return len(self.data)
  # 判断数组是否为空
  def is_empty(self):
    return True if not self.data else False
    # other ways: 1. self.data == [] ; 2. len(self.data) == 0
  # 获取数组对应索引的元素，若越界则报错
  def at(self,index):
    if index >= len(self.data):
      raise IndexError("Array index out of range.")
    return self.data[index]
  # 在数组末尾插入元素
  def push(self,item):
    self.data.append(item)
  # 在指定索引中插入元素，并把后面的元素依次后移
  def insert(self, index, item):
    self.data.insert(index, item)
  # 删除在数组末尾的元素并返回其值
  def pop(self):
    return self.data.pop()
  # 删除指定索引的元素，并把后面的元素依次前移
  def delete(self,index):
    self.data.pop(index)
  # 删除指定值的元素，并返回其索引（即使有多个元素）
  def remove(self, item):
    index_list = []
    item_count = self.data.count(item)
    for i in range(item_count):
      index_list.append(self.data.index(item))
      self.data.remove(item)
    return index_list
  # 寻找指定值的元素并返回其中第一个出现的元素其索引，若未找到则返回 -1
  def find(self, item):
    if item in self.data:
      return self.data.index(item)
    else:
      return -1
  # 翻转数组
  def reverse(self):
    temp = []
    size = len(self.data)
    for i in range(size):
      temp.append(self.data[size-1-i])
    self.data = temp
  # 升序排序数组
  def sort(self):
    return self.data.sort()  # self.data.sort(reverse = True) 为降序

普通测试用例

array1 = Array([1,2,3,3])
array1.push(4)
array1.push(3)
print("array1: ",array1.data)
print("size of array1: ", array1.size())
print("is array1 empty? ", array1.is_empty())
print("the 3rd element of array1: ", array1.at(2))
array1.sort()
print("sorted array1: ",array1.data)
array1.insert(3,9)
print("insert 9 to 3rd position: ", array1.data)
array1.pop()
print("pop: ",array1.data)
array1.delete(4)
print("delete index 4: ",array1.data)
array1.remove(3)
print("remove all 3: ", array1.data)
print("find the index of 9: ",array1.find(9))
array1.reverse()
print("reverse array: ",array1.data)

array1:  [1, 2, 3, 3, 4, 3]
size of array1:  6
is array1 empty?  False
the 3rd element of array1:  3
sorted array1:  [1, 2, 3, 3, 3, 4]
insert 9 to 3rd position:  [1, 2, 3, 9, 3, 3, 4]
pop:  [1, 2, 3, 9, 3, 3]
delete index 4:  [1, 2, 3, 9, 3]
remove all 3:  [1, 2, 9]
find the index of 9:  2
reverse array:  [9, 2, 1]

Linked List

class listNode:  # 链表中的结点类
  def __init__(self, x):
    self.val = x
    self.next = None

class LinkedList:  # 链表类
  def __init__(self):
    self.head = None
  # 打印链表
  def get_list(self):
    res = []
    head = self.head
    while head:
      res.append(head.val)
      head = head.next
    return res
  # 链表长度
  def size(self):
    size = 0
    head = self.head
    while head:
      size += 1
      head = head.next
    return size
  # 判断链表是否为空
  def empty(self):
    return False if self.head else True
  # 返回索引处的值
  def value_at(self, index):
    if not self.head:
      raise IndexError("Index out of range.")
    head = self.head
    while index > 0:
      if not head:
        raise IndexError("Index out of range.")
      head = head.next
      index -= 1
    return head.val
  # 添加元素到链表的首部
  def add(self, value):
    new_node = listNode(value)
    new_node.next = self.head
    self.head = new_node
  # 删除首部元素并返回其值
  def pop_front(self):
    if not self.head:
      raise IndexError("Pop from empty list")
    value = self.head.val
    self.head = self.head.next
    return value
  # 添加元素到链表的尾部
  def append(self, value):
    new_node = listNode(value)
    if not self.head:
      self.head = new_node
      return
    head = self.head
    while head.next:
      head = head.next
    head.next = new_node
  # 删除尾部元素并返回其值
  def pop_back(self):
    if not self.head:
      raise IndexError("Pop from empty list")
    if not self.head.next:
      value = self.head.val
      self.head = None
      return value
    head = self.head
    while head.next.next:
        head = head.next
    value = head.next.val
    head.next = None
    return value
  # 返回首部元素的值
  def front(self):
    if not self.head:
      raise ValueError("Linked list is empty")
    return self.head.val
  # 返回尾部元素的值
  def back(self):
    if not self.head:
      raise ValueError("Linked list is empty")
    head = self.head
    while head.next:
      head = head.next
    return head.val
  # 插入值到指定的索引
  def insert(self, index, value):
    if not self.head:
      raise IndexError("Index out of range")
    head = self.head
    new_node = listNode(value)
    if index == 0:
      new_node.next = head
      self.head = new_node
      return
    while index - 1 > 0:
      head = head.next
      if not head:
        raise IndexError("Index out of range")
      index -= 1
    temp = head.next
    head.next = new_node
    new_node.next = temp
  # 删除指定索引的节点
  def erase(self, index):
    if not self.head:
      raise IndexError("Index out of range")
    head = self.head
    if index == 0:
      self.head = head.next
    while index - 1 > 0:
      index -= 1
      head = head.next
      if not head:
        raise IndexError("Index out of range")
    temp = head.next
    head.next = temp.next
  # 翻转链表
  def reverse(self):
    prev = None
    head = self.head
    while head:
      temp = head.next
      head.next = prev
      prev = head
      head = temp
    self.head = prev
  # 删除链表中指定值的第一个元素
  def remove(self,value):
    if not self.head:
      return
    head = self.head
    if head.val == value:
      self.head = head.next
      return
    while head.next:
      if head.next.val == value:
        temp = head.next.next
        head.next = temp
        return
      head = head.next

普通测试用例

l1 = LinkedList()
a = [1,2,3,4,4,5]
for i in a:
  l1.append(i)
print("Linked list l1: ", l1.get_list())
print("size of l1: ", l1.size())
print("is l1 empty? ", l1.empty())
print("value at index 3: ", l1.value_at(3))
l1.add(-1)
print("add node -1: ", l1.get_list())
l1.pop_front()
print("pop the front node: ", l1.get_list())
l1.pop_back()
print("pop the end node: ", l1.get_list())
print("get the front node value: ", l1.front())
print("get the end node value: ", l1.back())
l1.insert(4,9)
print("insert 9 at index 4: ",l1.get_list())
l1.erase(1)
print("erase index 1: ",l1.get_list())
l1.remove(4)
print("remove value 4: ",l1.get_list())
l1.reverse()
print("revers l1: ",l1.get_list())

Linked list l1:  [1, 2, 3, 4, 4, 5]
size of l1:  6
is l1 empty?  False
value at index 3:  4
add node -1:  [-1, 1, 2, 3, 4, 4, 5]
pop the front node:  [1, 2, 3, 4, 4, 5]
pop the end node:  [1, 2, 3, 4, 4]
get the front node value:  1
get the end node value:  4
insert 9 at index 4:  [1, 2, 3, 4, 9, 4]
erase index 1:  [1, 3, 4, 9, 4]
remove value 4:  [1, 3, 9, 4]
revers l1:  [4, 9, 3, 1]

Stack

class Stack:
  # 使用Python的列表实现
  def __init__(self):
    self.data = []
  # 压栈
  def push(self, item):
    self.data.append(item)
  # 出栈
  def pop(self):
    if self.data:
      return self.data.pop()
    else:
      raise PopError("Pop from empty stack.")
  # 取栈顶的元素
  def peek(self):
    if self.data:
      return self.data[-1]
    else:
      raise IndexError("Stack is empty.")
  # 返回栈的大小
  def size(self):
    return len(self.data)
  # 判断栈是否为空
  def is_empty(self):
    return self.data == []

普通测试用例

s1 = Stack()
a = [1,2,3,4,5]
for i in a:
  s1.push(i)
print("s1: ", a)
print("s1 peek: ",s1.peek())
s1.pop()
print("s1 pop and peek: ",s1.peek())
print("s1 size: ", s1.size())
print("is s1 empty? ", s1.is_empty())

s1:  [1, 2, 3, 4, 5]
s1 peek:  5
s1 pop and peek:  4
s1 size:  4
is s1 empty?  False

Queue（单链队列）

class Queue:
  # 使用Python的列表实现
  def __init__(self):
    self.data = []
  # 元素入队（在队尾添加元素）
  def enqueue(self, item):
    self.data.append(item)
  # 出队
  def dequeue(self):
    if self.data:
      return self.data.pop(0)
    else:
      raise DequeueError("Queue is empty.")
  # 返回队列长度
  def size(self):
    return len(self.data)
  # 判空
  def is_empty(self):
    return self.data == []

普通测试用例

q1 = Queue()
a = [1,2,3,4,5]
for i in a:
  q1.enqueue(i)
print("queue q1: ", a)
print("dequeue: ", q1.dequeue())
print("size of q1: ", q1.size())
print("is q1 empty? ", q1.is_empty())

queue q1:  [1, 2, 3, 4, 5]
dequeue:  1
size of q1:  4
is q1 empty?  False

Queue（循环队列）

class CircularQueue:
  def __init__(self, max_size = 6):
    self.data = [None]*(max_size+1)
    self.front = 0
    self.rear = 0
  # 获得队列可容纳的最大长度
  def get_max_size(self):
    return len(self.data) - 1
  # 调整队列的最大长度（扩容或缩减）
  def resize(self, max_size):
    new_queue = [None]*(max_size+1)
    size = self.size()
    for i in range(size):
      new_queue[i] = self.data[(self.front+i)%self.get_max_size()]
    self.data = new_queue
    self.front = 0
    self.rear = size
  # 将新元素添加到队尾，若队列已满则报错
  def enqueue_strict(self, item):
    if (self.rear+1) % len(self.data) == self.front:
      raise SizeError("Queue is full. Unable to enqueue.")
    self.data[self.rear] = item
    self.rear = (self.rear+1) % len(self.data)
  # 将队首的元素出队，若队列为空则报错
  def dequeue_strict(self):
    if self.front == self.rear:
      raise SizeError("Queue is empty. Unable to dequeue.")
    item = self.data[self.front]
    self.data[self.front] = None
    self.front = (self.front + 1) % len(self.data)
    return item
  # 将新元素添加到队尾，若队列已满，则先扩容为原来可容纳大小的2倍，再入队
  def enqueue(self, item):
    if (self.rear+1) % len(self.data) == self.front:
      self.resize(self.get_max_size() * 2)
    self.data[self.rear] = item
    self.rear = (self.rear+1) % len(self.data)
  # 将队首的元素出队，若队列为空则报错。若队列当前长度为可容纳总长度的1/4，且列表总空间大于等于2时，将队列最大长度减小为原来的1/2以减小空间开销
  def dequeue(self):
    if self.front == self.rear:
      raise SizeError("Queue is empty. Unable to dequeue.")
    item = self.data[self.front]
    self.data[self.front] = None
    self.front = (self.front + 1) % len(self.data)
    if self.size() == self.get_max_size()//4 and len(self.data) >= 2:
      self.resize(self.get_max_size() // 2)
    return item
  # 获得队列的当前长度
  def size(self):
    return (self.rear - self.front + len(self.data)) % len(self.data)
  # 判断队列是否为空
  def is_empty(self):
    return self.front == self.rear

普通测试用例

q1 = CircularQueue()
a = [1,2,3,4,5,6]
for i in a:
  q1.enqueue(i)
print("queue q1: ", q1.data)
print("q1 max_size: ", q1.get_max_size())
q1.enqueue(7)
print("after enqueue, max size: ", q1.get_max_size())
print("q1: ", q1.data)
print("q1 size: ", q1.size())
print("is q1 empty? ", q1.is_empty())
print("dequeue until q1 size = 3")
for i in range(4):
  print("dequeue: ", q1.dequeue())
print("now q1 size = ", q1.size())
print("q1: ", q1.data)
print("q1 max size: ", q1.get_max_size())

queue q1:  [1, 2, 3, 4, 5, 6, None]
q1 max_size:  6
after enqueue, max size:  12
q1:  [1, 2, 3, 4, 5, 6, 7, None, None, None, None, None, None]
q1 size:  7
is q1 empty?  False
dequeue until q1 size = 3
dequeue:  1
dequeue:  2
dequeue:  3
dequeue:  4
now q1 size =  3
q1:  [5, 6, 7, None, None, None, None]
q1 max size:  6

Deque

class Deque:
  def __init__(self):
    self.data = []
  def is_empty(self):
    return self.data == []
  def add_front(self, item):
    self.data.append(item)
  def add_rear(self, item):
    self.data.insert(0, item)
  def remove_front(self):
    return self.data.pop()
  def remove_rear(self):
    return self.data.pop(0)
  def size(self):
    return len(self.data)

d1 = Deque()
print("is d1 empty? ", d1.is_empty())
d1.add_front(4)
d1.add_front('dog')
d1.add_rear('cat')
d1.add_rear('bird')
print('d1 size: ', d1.size())
print('is d1 empty? ', d1.is_empty())
print('d1: ', d1.data)
print('remove rear: ', d1.remove_rear())
print('remove front: ', d1.remove_front())
print('d1: ', d1.data)

is d1 empty?  True
d1 size:  4
is d1 empty?  False
d1:  ['bird', 'cat', 4, 'dog']
remove rear:  bird
remove front:  dog
d1:  ['cat', 4]

Binary Tree

• 二叉树的遍历（递归实现）
• 二叉树的遍历（非递归实现）

class treeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

二叉树的遍历（递归实现）

# 前序遍历
def preorder(root):
  if root is None:
    return []
  return [root.val] + preorder(root.left) + preorder(root.right)

# 中序遍历
def inorder(root):
  if root is None:
    return []
  return inorder(root.left) + [root.val] + inorder(root.right)

# 后序遍历
def postorder(root):
  if not root:
    return []
  return postorder(root.left) + postorder(root.right) + [root.val]

测试用例

a1 = treeNode(1)
a2 = treeNode(2)
a3 = treeNode(3)
a4 = treeNode(4)
a5 = treeNode(5)
a6 = treeNode(6)
'''
      1
      /   \
     /   \
    2     3
     / \     \
    4   5     6 
'''
a1.left = a2
a1.right = a3
a2.left = a4
a2.right = a5
a3.right = a6

# 验证前序遍历
print("PreOrder: ", preorder(a1))  # [1,2,4,5,3,6]
# 验证中序遍历
print("InOrder: ", inorder(a1))  # [4,2,5,1,3,6]
# 验证后序遍历
print("PostOrder: ", postorder(a1))  # [4,5,2,6,3,1]

PreOrder:  [1, 2, 4, 5, 3, 6]
InOrder:  [4, 2, 5, 1, 3, 6]
PostOrder:  [4, 5, 2, 6, 3, 1]

二叉树的遍历（非递归实现）

# 前序遍历
def preorder_wh(root):
  if root is None:
    return []
  res = []
  nodestack = []
  while nodestack or root:
    if root:
      res.append(root.val)
      nodestack.append(root)
      root = root.left
    else:
      root = nodestack.pop()
      root = root.right
  return res

# 中序遍历
def inorder_wh(root):
  if root is None:
    return []
  res = []
  nodestack = []
  while nodestack or root:
    if root:
      nodestack.append(root)
      root = root.left
    else:
      root = nodestack.pop()
      res.append(root.val)
      root = root.right
  return res

# 后序遍历1：修改前序遍历，倒序输出“根-右-左”
def postorder_wh1(root):
  if root is None:
    return []
  res = []
  nodestack = []
  while nodestack or root:
    if root:
      res.append(root.val)
      nodestack.append(root)
      root = root.right
    else:
      root = nodestack.pop()
      root = root.left
  # res1 用来存放 res 的倒序输出，或者直接用 res[::-1] 倒序输出
  res1 = []
  for i in range(len(res)):
    res1.append(res.pop())
  return res1

# 后序遍历2：使用两个栈实现
def postorder_wh2(root):
  if root is None:
    return []
  res = []
  nodestack = [root]
  while nodestack:
    root = nodestack.pop()
    res.append(root)
    if root.left:
      nodestack.append(root.left)
    if root.right:
      nodestack.append(root.right)
  # 此时res中存放了倒序的结点，使用res1将其倒序输出并取结点的值
  res1 = []
  for i in range(len(res)):
    res1.append(res.pop().val)
  return res1

# 层次遍历
def level_order(root):
  if not root:
    return []
  res = []
  nodequeue = [root]
  while nodequeue:
    root = nodequeue.pop(0)
    res.append(root.val)
    if root.left:
      nodequeue.append(root.left)
    if root.right:
      nodequeue.append(root.right)
  return res

测试用例

a1 = treeNode(1)
a2 = treeNode(2)
a3 = treeNode(3)
a4 = treeNode(4)
a5 = treeNode(5)
a6 = treeNode(6)
'''
      1
      /   \
     /   \
    2     3
     / \     \
    4   5     6 
'''
a1.left = a2
a1.right = a3
a2.left = a4
a2.right = a5
a3.right = a6

# 验证前序遍历
print("PreOrder: ", preorder_wh(a1))  # [1,2,4,5,3,6]
# 验证中序遍历
print("InOrder: ", inorder_wh(a1))  # [4,2,5,1,3,6]
# 验证后序遍历：方法1
print("PostOrder, method 1 : ", postorder_wh1(a1))  # [4,5,2,6,3,1]
# 验证后序遍历：方法2
print("PostOrder, method 2 : ", postorder_wh2(a1))
# 验证层次遍历
print("LevelOrder: ", level_order(a1))  # [1,2,3,4,5,6]

PreOrder:  [1, 2, 4, 5, 3, 6]
InOrder:  [4, 2, 5, 1, 3, 6]
PostOrder, method 1 :  [4, 5, 2, 6, 3, 1]
PostOrder, method 2 :  [4, 5, 2, 6, 3, 1]
LevelOrder:  [1, 2, 3, 4, 5, 6]

Binary Search Tree

class treeNode:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

# 查找某个元素
def find_item(item, root):
  if not root:
    return None
  while root:
    if root.val == item:
      return root
    elif root.val > item:
      root = root.left
    else:
      root = root.right
  return None
# 返回BST中的最小元素
def find_min(root):
  if not root:
    return None
  while root.left:
    root = root.left
  return root
# 返回BST中的最大元素
def find_max(root):
  if not root:
    return None
  while root.right:
    root = root.right
  return root
# 在二叉搜索树中插入一个新的元素，若元素已存在则忽略
def add_node(value, root):
  if not root:
    return treeNode(value)
  if value > root.val:
    root.right = add_node(value, root.right)  # 递归插入右子树
  elif value < root.val:
    root.left = add_node(value, root.left)  # 递归插入左子树
  else:
    pass  # 如果value已经存在，则什么也不做
  return root
# 从二叉搜索树中删除一个结点
def delete_node(value, root):
  if not root:
    return None  # 说明要删除的元素未找到
  if value < root.val:
    root.left = delete_node(value, root.left)  # 左子树递归删除
  elif value > root.val:
    root.right = delete_node(value, root.right)  # 右子树递归删除
  else:  # 说明已经找到要删除的结点了
    if not root.left:  # 只有右子树或者没有子结点
      return root.right
    elif not root.right:  # 只有左子树
      return root.left
    else:  # 有左右两个结点
      temp = find_min(root.right)  # 在右子树中找到最小的元素
      root.val = temp.val
      root.right = delete_node(temp.val, root.right)
  return root

测试用例

a1 = treeNode(4)
'''
      4
      /   \
     /   \
    2     6
     / \   / \
    1   3   5   7 
'''
for i 
  add_node(i, a1)
print("test add_node. After add, InOrder: ", inorder_wh(a1))
print("find value 6. Left: ", find_item(6, a1).left.val, "right: ", find_item(6, a1).right.val)
print("find min: ", find_min(a1).val)
print("find max: ", find_max(a1).val)
delete_node(6, a1)
print("delete value 6, InOrder: ",inorder_wh(a1))

test add_node. After add, InOrder:  [1, 2, 3, 4, 5, 6, 7]
find value 6. Left:  5 right:  7
find min:  1
find max:  7
delete value 6, InOrder:  [1, 2, 3, 4, 5, 7]

Balanced Search Tree

实现红黑树

BLACK = False
RED = True

class rb_node:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    self.color = BLACK
    
'''
这里实现的红黑树：
红色结点均为左结点
'''
class RedBlackBST:
  def __init__(self):
    self.root = None
  def rotate_left(self, node):
    if not node.right:
      return False
    temp = node.right
    node.right = temp.left
    temp.left = node
    return temp
  def rotate_right(self, node):
    if not node.left:
      return False
    temp = node.left
    node.left = temp.right
    temp.right = node
    return temp
  def re_color(self, node):
    # 重新着色. 着色前：结点是黑色，两个子结点都是红色；着色后：结点是红色，两个子结点都是黑色
    self.color = RED
    self.left.color = BLACK
    self.right.color = BLACK
  def is_red(self, node):
    if not node:
      return False
    return node.color == RED
  def insert(self, val):
    def _insert(node, val):
      new_node = rb_node(val)
      if not node:
        new_node.color = RED
        return new_node
      if val > node.val:
        node.right = _insert(node.right, val)
      elif val < node.val:
        node.left = _insert(node.left, val)
      else:
        pass
      # 分三种case修复结点（见笔记）；顺序：CASE2-CASE3-CASE1
      if is_red()
    _insert(self.root, val)
    self.root.color = BLACK

Heap

class MaxHeap:
  def __init__(self):
    self.data = [None]
  # 判断堆是否为空
  def is_empty(self):
    return len(self.data) == 1
  # 获得堆当前的大小
  def get_size(self):
    return len(self.data) - 1
  # 返回堆顶元素（最大值），但不删除
  def peek_max(self):
    if self.is_empty():
      return None
    else:
      return self.data[1]
  # 向堆中插入元素
  def insert(self, value):
    self.data.append(value)
    index = self.get_size()
    # 如果比父结点大并且不是根结点则向上调整
    while index > 1 and self.data[index] > self.data[index//2]:
      self.data[index], self.data[index//2] = self.data[index//2], self.data[index]
      index = index // 2
  # 用于删除和创建堆的函数。从当前结点开始向下调整，保证结点往下是一个堆
  def sift_down(self, index):
    while 2*index <= self.get_size():
      # 左子结点的索引
      child = 2 * index
      # 如果右子结点存在且比左子结点大，则应与右子结点交换
      if 2*index + 1 <= self.get_size() and self.data[2*index+1] > self.data[2*index]:
        child += 1  # 右子结点的索引
      # 如果当前结点的值小于子结点中的较大者，则应继续向下交换，否则结束
      if self.data[index] < self.data[child]:
        self.data[index], self.data[child] = self.data[child], self.data[index]
        index = child
      else:
        break
  # 删除堆顶元素（最大值）
  def remove(self):
    if self.is_empty():
      raise RemoveError("Unable to remove from an empty heap.")
    # 用堆的最后一个元素替代堆顶元素，然后删除最后一个元素
    self.data[1], self.data[self.get_size()] = self.data[self.get_size()], self.data[1]
    self.data.pop()
    # 从堆顶向下调整
    self.sift_down(1)
  # 从一个序列创建堆
  def build_heap(self, array):
    self.data = [None] + array
    index = self.get_size() // 2
    # 从倒数第二层开始，从右到左，逐层向上调整。每次调整只需sift_down
    while index > 0:
      self.sift_down(index)
      index -= 1

测试用例

a = [1,5,16,21,33,48,60]
h1 = MaxHeap()
h1.build_heap(a)
print("build heap through list: ", h1.data)
h1.insert(100)
print("insert value 100: ", h1.data)
print("value of top of h1: ", h1.peek_max())
h1.remove()
print("remove top of heap: ", h1.data)
print("size of h1: ",h1.get_size())
print("is h1 empty? ", h1.is_empty())

build heap through list:  [None, 60, 33, 48, 21, 5, 1, 16]
insert value 100:  [None, 100, 60, 48, 33, 5, 1, 16, 21]
value of top of h1:  100
remove top of heap:  [None, 60, 33, 48, 21, 5, 1, 16]
size of h1:  7
is h1 empty?  False

Union-Find

# 实现平衡树形结构的并查集
class UnionFind:
  # 初始化并查集中的元素，默认每个元素的值就是数组下标，每个元素的集合只有自身
  def __init__(self, N):
    self.data = list(range(N))  # 存储元素的值
    self.count = N  # 存储集合的个数
    self.parent = list(range(N))  # 存储该元素的父结点的数组下标
    self.size = [1] * N  # 存储以该元素为根的树的大小（树中的元素个数）
  def find(self, value):  # 返回根结点的下标
    index = self.data.index(value)
    while self.parent[index] != index:
      index = self.parent[index]
    return index
  def union(self, value1, value2):
    root1 = self.find(value1)
    root2 = self.find(value2)
    if root1 == root2:
      return
    if self.size[root1] > self.size[root2]:
      self.parent[root2] = root1
      self.size[root1] += self.size[root2]
    else:
      self.parent[root1] = root2
      self.size[root2] + self.size[root1]
    self.count -= 1
  def connected(self, value1, value2):
    return self.find(value1) == self.find(value2)

测试用例

uf1 = UnionFind(10)
print("find 5: ", uf1.find(5))
# {0} {1,5,8} {2,3,4,6} {7,9}
uf1.union(1, 5)
uf1.union(5, 8)
uf1.union(2, 6)
uf1.union(3, 6)
uf1.union(2, 4)
uf1.union(7, 9)
print("find 4: ", uf1.find(4))
print("find 2: ", uf1.find(2))
print("find 3: ", uf1.find(3))
print("connected: 1,8: ", uf1.connected(1,8))
print("connected: 3,7", uf1.connected(3,7))

find 5:  5
find 4:  4
find 2:  4
find 3:  4
connected: 1,8:  True
connected: 3,7 False

Hash Table

class listNode:
  def __init__(self, key, value):
    self.key = key
    self.value = value
    self.next = None

class HashTable:
  def __init__(self, N):
    self.size = N
    self.table = [None] * N
  def hash_code(self, key):
    # (((a*key + b) mod p) mod N)
    return ((13 * key  + 31) % 16908799) % self.size
  def insert(self, key, value):
    index = self.hash_code(key)
    head = self.table[index]
    if not head:  # 如果哈希表对应位置还是空的
      self.table[index] = listNode(key, value)
    else:
      while head.next:
        head = head.next
      head.next = listNode(key, value)
  def find(self, key):
    index = self.hash_code(key)
    head = self.table[index]
    if not head:
      return None
    else:
      while head:
        if head.key == key:
          return head.value
        head = head.next
      return None
  def remove(self, key):
    index = self.hash_code(key)
    head = self.table[index]
    if not head:
      return None
    else:
      prev = None
      while head:
        if head.key == key:
          next_node = head.next
          if prev:
            prev.next = next_node
            return head.value
          else:
            self.table[index] = head.next
            return head.value
        else:
          prev = head
          head = head.next
      return None

测试用例

h1 = HashTable(20)
a = [
  [322, 'jack'],
  [543, 'michael'],
  [167, 'jhon'],
  [132, 'henry'],
  [113, 'steve'],
  [256, 'ray'],
  [289, 'christopher']
]
for x in a:
  h1.insert(x[0], x[1])
print("find 322: ", h1.find(322))
print("find 543: ", h1.find(543))
print("find 167: ", h1.find(167))
print("find 132: ", h1.find(132))
print("find 113: ", h1.find(113))
print("================")
print("find 333: ", h1.find(333))
print("================")
print("remove 322")
h1.remove(322)
print("find 322: ", h1.find(322))

find 322:  jack
find 543:  michael
find 167:  jhon
find 132:  henry
find 113:  steve
================
find 333:  None
================
remove 322
find 322:  None