查找数据结构及算法有哪些？

# 最基础的遍历无序列表的查找算法
# 时间复杂度O(n)

def sequential_search(lis, key):
 length = len(lis)
 for i in range(length):
  if lis[i] == key:
   return i
  else:
   return False


if __name__ == '__main__':
 LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
 result = sequential_search(LIST, 123)
 print(result)

# 针对有序查找表的二分查找算法
# 时间复杂度O(log(n))

def binary_search(lis, key):
 low = 0
 high = len(lis) - 1
 time = 0
 while low < high:
  time += 1
  mid = int((low + high) / 2)
  if key < lis[mid]:
   high = mid - 1
  elif key > lis[mid]:
   low = mid + 1
  else:
   # 打印折半的次数
   print("times: %s" % time)
   return mid
 print("times: %s" % time)
 return False

if __name__ == '__main__':
 LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
 result = binary_search(LIST, 99)
 print(result)

# 插值查找算法
# 时间复杂度O(log(n))

def binary_search(lis, key):
 low = 0
 high = len(lis) - 1
 time = 0
 while low < high:
  time += 1
  # 计算mid值是插值算法的核心代码
  mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
  print("mid=%s, low=%s, high=%s" % (mid, low, high))
  if key < lis[mid]:
   high = mid - 1
  elif key > lis[mid]:
   low = mid + 1
  else:
   # 打印查找的次数
   print("times: %s" % time)
   return mid
 print("times: %s" % time)
 return False

if __name__ == '__main__':
 LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
 result = binary_search(LIST, 444)
 print(result)

# 斐波那契查找算法
# 时间复杂度O(log(n))

def fibonacci_search(lis, key):
 # 需要一个现成的斐波那契列表。其最大元素的值必须超过查找表中元素个数的数值。
 F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
   233, 377, 610, 987, 1597, 2584, 4181, 6765,
   10946, 17711, 28657, 46368]
 low = 0
 high = len(lis) - 1
 
 # 为了使得查找表满足斐波那契特性，在表的最后添加几个同样的值
 # 这个值是原查找表的最后那个元素的值
 # 添加的个数由F[k]-1-high决定
 k = 0
 while high > F[k]-1:
  k += 1
 print(k)
 i = high
 while F[k]-1 > i:
  lis.append(lis[high])
  i += 1
 print(lis)
 
 # 算法主逻辑。time用于展示循环的次数。
 time = 0
 while low <= high:
  time += 1
  # 为了防止F列表下标溢出，设置if和else
  if k < 2:
   mid = low
  else:
   mid = low + F[k-1]-1
  
  print("low=%s, mid=%s, high=%s" % (low, mid, high))
  if key < lis[mid]:
   high = mid - 1
   k -= 1
  elif key > lis[mid]:
   low = mid + 1
   k -= 2
  else:
   if mid <= high:
    # 打印查找的次数
    print("times: %s" % time)
    return mid
   else:
    print("times: %s" % time)
    return high
 print("times: %s" % time)
 return False

if __name__ == '__main__':
 LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
 result = fibonacci_search(LIST, 444)
 print(result)

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5


class BSTNode:
 """
 定义一个二叉树节点类。
 以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。
 """
 def __init__(self, data, left=None, right=None):
  """
  初始化
  :param data: 节点储存的数据
  :param left: 节点左子树
  :param right: 节点右子树
  """
  self.data = data
  self.left = left
  self.right = right


class BinarySortTree:
 """
 基于BSTNode类的二叉排序树。维护一个根节点的指针。
 """
 def __init__(self):
  self._root = None

 def is_empty(self):
  return self._root is None

 def search(self, key):
  """
  关键码检索
  :param key: 关键码
  :return: 查询节点或None
  """
  bt = self._root
  while bt:
   entry = bt.data
   if key < entry:
    bt = bt.left
   elif key > entry:
    bt = bt.right
   else:
    return entry
  return None

 def insert(self, key):
  """
  插入操作
  :param key:关键码 
  :return: 布尔值
  """
  bt = self._root
  if not bt:
   self._root = BSTNode(key)
   return
  while True:
   entry = bt.data
   if key < entry:
    if bt.left is None:
     bt.left = BSTNode(key)
     return
    bt = bt.left
   elif key > entry:
    if bt.right is None:
     bt.right = BSTNode(key)
     return
    bt = bt.right
   else:
    bt.data = key
    return

 def delete(self, key):
  """
  二叉排序树最复杂的方法
  :param key: 关键码
  :return: 布尔值
  """
  p, q = None, self._root  # 维持p为q的父节点，用于后面的链接操作
  if not q:
   print("空树！")
   return
  while q and q.data != key:
   p = q
   if key < q.data:
    q = q.left
   else:
    q = q.right
   if not q:    # 当树中没有关键码key时，结束退出。
    return
  # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。
  if not q.left:
   if p is None:
    self._root = q.right
   elif q is p.left:
    p.left = q.right
   else:
    p.right = q.right
   return
  # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树
  # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。
  r = q.left
  while r.right:
   r = r.right
  r.right = q.right
  if p is None:
   self._root = q.left
  elif p.left is q:
   p.left = q.left
  else:
   p.right = q.left

 def __iter__(self):
  """
  实现二叉树的中序遍历算法,
  展示我们创建的二叉排序树.
  直接使用python内置的列表作为一个栈。
  :return: data
  """
  stack = []
  node = self._root
  while node or stack:
   while node:
    stack.append(node)
    node = node.left
   node = stack.pop()
   yield node.data
   node = node.right


if __name__ == '__main__':
 lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
 bs_tree = BinarySortTree()
 for i in range(len(lis)):
  bs_tree.insert(lis[i])
 # bs_tree.insert(100)
 bs_tree.delete(58)
 for i in bs_tree:
  print(i, end=" ")
 # print("\n", bs_tree.search(4))

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 忽略了对数据类型，元素溢出等问题的判断。


class HashTable:
 def __init__(self, size):
  self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法
  self.count = size # 最大表长

 def hash(self, key):
  return key % self.count # 散列函数采用除留余数法

 def insert_hash(self, key):
  """插入关键字到哈希表内"""
  address = self.hash(key) # 求散列地址
  while self.elem[address]: # 当前位置已经有数据了，发生冲突。
   address = (address+1) % self.count # 线性探测下一地址是否可用
  self.elem[address] = key # 没有冲突则直接保存。

 def search_hash(self, key):
  """查找关键字，返回布尔值"""
  star = address = self.hash(key)
  while self.elem[address] != key:
   address = (address + 1) % self.count
   if not self.elem[address] or address == star: # 说明没找到或者循环到了开始的位置
    return False
  return True


if __name__ == '__main__':
 list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
 hash_table = HashTable(12)
 for i in list_a:
  hash_table.insert_hash(i)

 for i in hash_table.elem:
  if i:
   print((i, hash_table.elem.index(i)), end=" ")
 print("\n")

 print(hash_table.search_hash(15))
 print(hash_table.search_hash(33))