# 最基础的遍历无序列表的查找算法
# 时间复杂度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))
机械节能产品生产企业官网模板...
大气智能家居家具装修装饰类企业通用网站模板...
礼品公司网站模板
宽屏简约大气婚纱摄影影楼模板...
蓝白WAP手机综合医院类整站源码（独立后台）...苏ICP备2024110244号-2 苏公网安备32050702011978号 增值电信业务经营许可证编号：苏B2-20251499 | Copyright 2018 - 2025 源码网商城 (www.ymwmall.com) 版权所有