顺序查找无序存储的符号表 -- 链表
无序链表.png
#!/usr/bin/python3
class LinkTable:
'''无序链表
1. first 指向 链表的第一个元素
2. 最后一个节点的 next_node 的值为 None
'''
class Node:
'''定义节点Node的数据结构'''
def __init__(self, key, value, next_node):
self.key = key
self.value = value
self.next_node = next_node
def __init__(self):
self.first = None # 指向链表的一个节点的指针，
#该初始值None赋给第一个实际创建的节点，刚好时其 next_node 的值为 None
self.size = 0
def put(self, key, value):
'''先遍历一遍链表，如果 key 已存在，替换其 value'''
current_node = self.first
while True: # 遍历数组，判断 key 是否已经存在
if current_node != None: #（没有创建节点时，first 是 Node；有节点时，first是节点）（最后一个节点的 next_node 也是 None）
if current_node.key == key: # key 已存在，替换，并返回
current_node.value = value
return
else: # 进入下一个节点
current_node = current_node.next_node
else: # 遍历结束，需创建新节点
break
self.first = self.Node(key, value, self.first)
self.size += 1
def get(self, key):
'''遍历节点，查找 key，返回其 value '''
current_node = self.first
while True:
if current_node != None:
if current_node.key == key: # 找到，返回 value
return current_node.value
else:# 进入下一节点
current_node = current_node.next_node
else: # 遍历结束，无结果
return None
if __name__ == '__main__':
link_table = LinkTable()
# 读取输入
while True:
key = input('key: ').strip()
if key == '':
break
value = input('value: ').strip()
link_table.put(key, value)
print('-' * 30)
# 从链表中获取值
while True:
key = input('key: ').strip()
if key == '':
break
print('value: ', link_table.get(key))
有序符号表（基于数组）二分查找
符号表用两个数组实现：一个存放 key，一个存放 value （通过key的索引可以获取对应的 value）
该符表操作的核心是：rank(self, key) 通过二分查找实现；总的来说：会返回 key 在数组中应所属的位置（无关存在与否）；rank() 本意是要返回，key 前面有多少元素
比如， key 是第N的元素，那么它前面会有 N-1 个元素 --> 刚好 key 在数组中应位于索引 N-1 的位置；所以 put() 实现可以利用 rank() 返回值，判断 put 进来的 key 是否等于数组中的key：是，则替换；否，则将后面的元素向后移，并插入key
二分查找中的特殊情况
剩下两个值
low = 5
high = 6
-----
mid = low + (high - low) // 2 = 5 + 0 = 5
# key < mid: low = 5; high = 5 - 1 = 4 结束查找 （rank()返回low）
# key > mid: low = 5 + 1 = 6; high = 6 继续
key < mid, key要在5的位置；5及以后向又移
key > mid，继续二分
剩余一个值
low = 6
high = 6
------------
mid = 6 + (6 - 6) // 2 = 6
# key < mid: low = 6; high = 6 - 1 = 5 结束（返回low）
# key > mid: low = 6 + 1; high = 6 - 1 = 6 结束（返回low）
key < mid，返回 low
key > mid, 返回 low
- 返回 low 正确
#!/usr/bin/python3
class BinarySearchST:
def __init__(self):
self.keys = [None]
self.values = [None]
self.N = 0
def get_size(self):
return self.N #len(self.keys)
def is_empty(self):
return self.get_size() == 0
def resize(self, max):
# 在Python中数组的空间是不固定的
# 在其他语言中，自动调整空间可以是：当数组空间用完时，增加其空间扩大一倍
###
# 创建新数组，空间为原来的两倍
# 将就元素逐一复制到新数组
# 将新数组赋给原来的变量名，比如 self.keys
new_keys = []
new_values = []
for i in range(max):
new_keys.append(None)
new_values.append(None)
for i in range(self.N):
new_keys[i] = self.keys[i]
new_values[i] = self.values[i]
self.keys = new_keys
self.values = new_values
def rank(self, key):
'''如果key存在于符号表中，返回小于key的数量（该值刚好是key在数组中的索引值）
第N个元素，前面有N-1个元素；数组从0开始，刚好N-1是第N个元素的索引值
如果key不存在，也是返回key在数组中前面有多少个元素；
基于二分查找'''
low = 0
high = self.get_size() - 1
while True:
if low > high:
return low # 假如 key 比 keys[mid]小，return low (high=mid-1); key 比 keys[mid] 大，return low (low=mid+1)
mid = low + (high - low) // 2
elif key == self.keys[mid]:
return mid
elif key < self.keys[mid]:
high = mid - 1
elif key > self.keys[mid]:
low = mid + 1
def put(self, key, value):
if self.N == len(self.keys): self.resize(self.N * 2)
if self.is_empty():
self.keys[0] = key
self.values[0] = value
self.N += 1
return
i = self.rank(key)
if key == self.keys[i]: # key 已经在符号表中，替换key的值
self.values[i] == value
else:
for j in range(self.N, i, -1):
self.keys[j] = self.keys[j-1]
self.values[j] = self.values[j-1]
self.keys[i] = key
self.values[i] = value
self.N += 1
return
def get(self, key):
i = self.rank(key)
if self.keys[i] == key:
return self.values[i]
else:
return None
if __name__ == '__main__':
st = BinarySearchST()
# 读取输入
while True:
key = input('key: ').strip()
if key == '':
break
value = input('value: ').strip()
st.put(key, value)
print('-' * 30)
# 从链表中获取值
while True:
key = input('key: ').strip()
if key == '':
break
print('value: ', st.get(key))
