CodeTailor

无序表#

无序表（Unordered List） 是元素之间没有特定顺序关系的线性表。 无序表特点：

1. 元素顺序任意，没有排序要求
2. 可以包含重复元素
3. 元素类型可以不同（在动态类型语言中）
4. 操作关注元素本身，而非位置关系

示例：购物清单、待办事项、标签集合

无序表的实现与应用#

1. 基于数组的无序表

   1
   class UnorderedArrayList:
   2
       """基于数组的无序表实现"""
   3
       def __init__(self):
   4
           self.items = []
   5
   
   6
       def __str__(self):
   7
           return f"UnorderedList: {self.items}"
   8
   
   9
       def is_empty(self):
   10
           """判断是否为空"""
   11
           return len(self.items) == 0
   12
   
   13
       def add(self, item):
   14
           """添加元素 - O(1)"""
   15
           self.items.append(item)
   16
   
   17
       def remove(self, item):
   18
           """删除指定元素 - O(n)"""
   19
           if item in self.items:
   20
               self.items.remove(item)
   21
               return True
   22
           return False
   23
   
   24
       def search(self, item):
   25
           """查找元素 - O(n)"""
   26
           return item in self.items
   27
   
   28
       def size(self):
   29
           """获取大小"""
   30
           return len(self.items)
   31
   
   32
       def append(self, item):
   33
           """尾部追加"""
   34
           self.items.append(item)
   35
   
   36
       def index(self, item):
   37
           """获取元素索引 - O(n)"""
   38
           try:
   39
               return self.items.index(item)
   40
           except ValueError:
   41
               return -1
   42
   
   43
       def pop(self, pos=None):
   44
           """弹出元素"""
   45
           if pos is None:
   46
               return self.items.pop()
   47
           return self.items.pop(pos)
   48
   
   49
       def clear(self):
   50
           """清空列表"""
   51
           self.items.clear()

   测试无序数组表

   1
   ul_array = UnorderedArrayList()
   2
   ul_array.add(5)
   3
   ul_array.add(2)
   4
   ul_array.add(8)
   5
   ul_array.add(5)  # 允许重复
   6
   print(ul_array)  # UnorderedList: [5, 2, 8, 5]
   7
   print("查找8:", ul_array.search(8))  # True
   8
   print("删除5:", ul_array.remove(5))  # True（删除第一个5）
   9
   print(ul_array)  # UnorderedList: [2, 8, 5]

2. 基于链表的无序表

   1
   class Node:
   2
       """链表节点"""
   3
       def __init__(self, data):
   4
           self.data = data
   5
           self.next = None
   6
   
   7
   class UnorderedLinkedList:
   8
       """基于链表的无序表实现"""
   9
       def __init__(self):
   10
           self.head = None
   11
           self._size = 0
   12
   
   13
       def __str__(self):
   14
           values = []
   15
           current = self.head
   16
           while current:
   17
               values.append(str(current.data))
   18
               current = current.next
   19
           return " -> ".join(values) + " -> None" if values else "Empty"
   20
   
   21
       def is_empty(self):
   22
           return self.head is None
   23
   
   24
       def add(self, item):
   25
           """头部添加元素 - O(1)"""
   26
           new_node = Node(item)
   27
           new_node.next = self.head
   28
           self.head = new_node
   29
           self._size += 1
   30
   
   31
       def append(self, item):
   32
           """尾部添加元素 - O(n)"""
   33
           new_node = Node(item)
   34
   
   35
           if self.is_empty():
   36
               self.head = new_node
   37
           else:
   38
               current = self.head
   39
               while current.next:
   40
                   current = current.next
   41
               current.next = new_node
   42
   
   43
           self._size += 1
   44
   
   45
       def remove(self, item):
   46
           """删除指定元素 - O(n)"""
   47
           current = self.head
   48
           previous = None
   49
   
   50
           while current:
   51
               if current.data == item:
   52
                   if previous:
   53
                       previous.next = current.next
   54
                   else:
   55
                       self.head = current.next
   56
                   self._size -= 1
   57
                   return True
   58
               previous = current
   59
               current = current.next
   60
   
   61
           return False
   62
   
   63
       def search(self, item):
   64
           """查找元素 - O(n)"""
   65
           current = self.head
   66
           while current:
   67
               if current.data == item:
   68
                   return True
   69
               current = current.next
   70
           return False
   71
   
   72
       def size(self):
   73
           return self._size
   74
   
   75
       def index(self, item):
   76
           """获取元素位置 - O(n)"""
   77
           current = self.head
   78
           pos = 0
   79
   
   80
           while current:
   81
               if current.data == item:
   82
                   return pos
   83
               current = current.next
   84
               pos += 1
   85
   
   86
           return -1
   87
   
   88
       def pop(self, pos=None):
   89
           """弹出元素"""
   90
           if self.is_empty():
   91
               raise IndexError("Pop from empty list")
   92
   
   93
           if pos == 0 or pos is None and self.head:
   94
               # 弹出头部
   95
               value = self.head.data
   96
               self.head = self.head.next
   97
               self._size -= 1
   98
               return value
   99
   
   100
           # 找到指定位置
   101
           current = self.head
   102
           previous = None
   103
           current_pos = 0
   104
   
   105
           if pos is None:
   106
               # 弹出尾部
   107
               while current.next:
   108
                   previous = current
   109
                   current = current.next
   110
           else:
   111
               while current and current_pos < pos:
   112
                   previous = current
   113
                   current = current.next
   114
                   current_pos += 1
   115
   
   116
           if current is None:
   117
               raise IndexError("Index out of range")
   118
   
   119
           value = current.data
   120
           previous.next = current.next
   121
           self._size -= 1
   122
           return value

   测试无序链表

   1
   ul_linked = UnorderedLinkedList()
   2
   ul_linked.add(3)
   3
   ul_linked.add(1)
   4
   ul_linked.add(4)
   5
   ul_linked.append(2)
   6
   print(ul_linked)  # 4 -> 1 -> 3 -> 2 -> None
   7
   print("查找3:", ul_linked.search(3))  # True
   8
   print("删除1:", ul_linked.remove(1))  # True
   9
   print(ul_linked)  # 4 -> 3 -> 2 -> None

有序表#

有序表（Ordered List） 是元素按照特定顺序排列的线性表。 有序表特点：

1. 元素按某种规则排序（升序/降序）
2. 通常不允许重复元素（集合）或允许重复（多重集）
3. 支持高效查找（二分查找）
4. 插入删除需要考虑位置

示例：电话簿、成绩排名、字典索引

有序表的实现与应用#

1. 基于数组的有序表（排序数组）

   1
   class OrderedArrayList:
   2
       """基于数组的有序表实现（升序）"""
   3
       def __init__(self):
   4
           self.items = []
   5
   
   6
       def __str__(self):
   7
           return f"OrderedList: {self.items}"
   8
   
   9
       def is_empty(self):
   10
           return len(self.items) == 0
   11
   
   12
       def add(self, item):
   13
           """添加元素并保持有序 - O(n)"""
   14
           if self.is_empty() or item >= self.items[-1]:
   15
               # 如果为空或大于等于最后一个元素，直接追加
   16
               self.items.append(item)
   17
           else:
   18
               # 找到插入位置
   19
               pos = 0
   20
               while pos < len(self.items) and self.items[pos] < item:
   21
                   pos += 1
   22
               self.items.insert(pos, item)
   23
   
   24
       def remove(self, item):
   25
           """删除元素 - O(n)"""
   26
           index = self._binary_search(item)
   27
           if index != -1:
   28
               self.items.pop(index)
   29
               return True
   30
           return False
   31
   
   32
       def search(self, item):
   33
           """二分查找 - O(log n)"""
   34
           return self._binary_search(item) != -1
   35
   
   36
       def _binary_search(self, item):
   37
           """二分查找实现"""
   38
           left, right = 0, len(self.items) - 1
   39
   
   40
           while left <= right:
   41
               mid = (left + right) // 2
   42
               if self.items[mid] == item:
   43
                   return mid
   44
               elif self.items[mid] < item:
   45
                   left = mid + 1
   46
               else:
   47
                   right = mid - 1
   48
   
   49
           return -1
   50
   
   51
       def size(self):
   52
           return len(self.items)
   53
   
   54
       def pop(self, pos=None):
   55
           """弹出元素"""
   56
           if pos is None:
   57
               return self.items.pop()
   58
           return self.items.pop(pos)
   59
   
   60
       def clear(self):
   61
           self.items.clear()
   62
   
   63
       def get_range(self, start, end):
   64
           """获取范围内的元素"""
   65
           import bisect
   66
           left = bisect.bisect_left(self.items, start)
   67
           right = bisect.bisect_right(self.items, end)
   68
           return self.items[left:right]

   测试有序数组表

   1
   ol_array = OrderedArrayList()
   2
   ol_array.add(5)
   3
   ol_array.add(2)
   4
   ol_array.add(8)
   5
   ol_array.add(3)
   6
   ol_array.add(5)  # 允许重复
   7
   print(ol_array)  # OrderedList: [2, 3, 5, 5, 8]
   8
   print("查找3:", ol_array.search(3))  # True
   9
   print("查找4:", ol_array.search(4))  # False
   10
   print("范围查询[3, 6]:", ol_array.get_range(3, 6))  # [3, 5, 5]

2. 基于平衡二叉搜索树的有序表

   1
   class TreeNode:
   2
       """二叉搜索树节点"""
   3
       def __init__(self, key):
   4
           self.key = key
   5
           self.left = None
   6
           self.right = None
   7
           self.height = 1
   8
   
   9
   class AVLTree:
   10
       """AVL树实现的有序表（自平衡二叉搜索树）"""
   11
       def __init__(self):
   12
           self.root = None
   13
   
   14
       def __str__(self):
   15
           return "AVL Tree (inorder): " + str(self.inorder_traversal())
   16
   
   17
       def height(self, node):
   18
           """获取节点高度"""
   19
           if not node:
   20
               return 0
   21
           return node.height
   22
   
   23
       def balance_factor(self, node):
   24
           """计算平衡因子"""
   25
           if not node:
   26
               return 0
   27
           return self.height(node.left) - self.height(node.right)
   28
   
   29
       def rotate_right(self, y):
   30
           """右旋转"""
   31
           x = y.left
   32
           T2 = x.right
   33
   
   34
           # 执行旋转
   35
           x.right = y
   36
           y.left = T2
   37
   
   38
           # 更新高度
   39
           y.height = 1 + max(self.height(y.left), self.height(y.right))
   40
           x.height = 1 + max(self.height(x.left), self.height(x.right))
   41
   
   42
           return x
   43
   
   44
       def rotate_left(self, x):
   45
           """左旋转"""
   46
           y = x.right
   47
           T2 = y.left
   48
   
   49
           # 执行旋转
   50
           y.left = x
   51
           x.right = T2
   52
   
   53
           # 更新高度
   54
           x.height = 1 + max(self.height(x.left), self.height(x.right))
   55
           y.height = 1 + max(self.height(y.left), self.height(y.right))
   56
   
   57
           return y
   58
   
   59
       def insert(self, node, key):
   60
           """插入节点"""
   61
           # 1. 标准BST插入
   62
           if not node:
   63
               return TreeNode(key)
   64
   
   65
           if key < node.key:
   66
               node.left = self.insert(node.left, key)
   67
           elif key > node.key:
   68
               node.right = self.insert(node.right, key)
   69
           else:
   70
               return node  # 重复键不插入
   71
   
   72
           # 2. 更新高度
   73
           node.height = 1 + max(self.height(node.left), self.height(node.right))
   74
   
   75
           # 3. 获取平衡因子
   76
           balance = self.balance_factor(node)
   77
   
   78
           # 4. 如果不平衡，有4种情况
   79
           # 左左情况
   80
           if balance > 1 and key < node.left.key:
   81
               return self.rotate_right(node)
   82
   
   83
           # 右右情况
   84
           if balance < -1 and key > node.right.key:
   85
               return self.rotate_left(node)
   86
   
   87
           # 左右情况
   88
           if balance > 1 and key > node.left.key:
   89
               node.left = self.rotate_left(node.left)
   90
               return self.rotate_right(node)
   91
   
   92
           # 右左情况
   93
           if balance < -1 and key < node.right.key:
   94
               node.right = self.rotate_right(node.right)
   95
               return self.rotate_left(node)
   96
   
   97
           return node
   98
   
   99
       def add(self, key):
   100
           """添加元素 - O(log n)"""
   101
           self.root = self.insert(self.root, key)
   102
   
   103
       def search(self, key):
   104
           """查找元素 - O(log n)"""
   105
           return self._search(self.root, key)
   106
   
   107
       def _search(self, node, key):
   108
           if not node:
   109
               return False
   110
   
   111
           if key == node.key:
   112
               return True
   113
           elif key < node.key:
   114
               return self._search(node.left, key)
   115
           else:
   116
               return self._search(node.right, key)
   117
   
   118
       def inorder_traversal(self):
   119
           """中序遍历（得到有序序列）"""
   120
           result = []
   121
           self._inorder(self.root, result)
   122
           return result
   123
   
   124
       def _inorder(self, node, result):
   125
           if node:
   126
               self._inorder(node.left, result)
   127
               result.append(node.key)
   128
               self._inorder(node.right, result)

测试AVL树

1
avl = AVLTree()
2
for num in [9, 5, 10, 0, 6, 11, -1, 1, 2]:
3
    avl.add(num)
4

5
print("AVL树中序遍历:", avl.inorder_traversal())  # [-1, 0, 1, 2, 5, 6, 9, 10, 11]
6
print("查找6:", avl.search(6))  # True
7
print("查找7:", avl.search(7))  # False

对比#

1. 核心对比

2. 性能对比 空间复杂度对比

   数组实现：O(n)，内存连续，可能有空间浪费

   链表实现：O(n)，每个节点有额外指针开销

   树实现：O(n)，每个节点有左右指针和高度信息

无序表思维（就像杂货店——东西随便放，找起来麻烦）#

元素平等，顺序无关 适用场景：集合、容器、不需要顺序的存储

关键点：

1. 关注元素存在性，而非位置
2. 插入快，查找慢
3. 实现简单，使用灵活

有序表思维（就像图书馆——东西排好队，找起来方便）#

元素有序，位置重要 适用场景：排名、搜索、范围查询

关键点：

1. 元素有顺序关系
2. 查找快，插入慢
3. 支持高效的范围操作