# Python 数据结构和算法实用指南（三）（1）

• 哈希
• 哈希表
• 不同的元素功能

## 哈希

>>> sum(map(ord, 'hello world'))
1116

>>> sum(map(ord, 'world hello'))
1116

>>> sum(map(ord, 'gello xorld'))
1116

## 完美哈希函数

def myhash(s):
mult = 1
hv = 0
for ch in s:
hv += mult * ord(ch)
mult += 1
return hv 

for item in ('hello world', 'world hello', 'gello xorld'):
print("{}: {}".format(item, myhash(item))) 

% python hashtest.py
hello world: 6736
world hello: 6616
gello xorld: 6742

% python hashtest.py
ga: 297

## 哈希表

class HashItem:
def __init__(self, key, value):
self.key = key
self.value = value 

class HashTable:
def __init__(self):
self.size = 256
self.slots = [None for i in range(self.size)]
self.count = 0 

def _hash(self, key):
mult = 1
hv = 0
for ch in key:
hv += mult * ord(ch)
mult += 1
return hv % self.size 

## 在哈希表中存储元素

def put(self, key, value):
item = HashItem(key, value)
h = self._hash(key) 

while self.slots[h] is not None:
if self.slots[h].key is key:
break
h = (h + 1) % self.size 

if self.slots[h] is None:
self.count += 1
self.slots[h] = item  

## 从哈希表中检索元素

1. 我们计算给定密钥字符串"egg"的哈希值，结果为 51。然后，我们将此密钥与位置 51 处存储的密钥值进行比较，但不匹配。
2. 由于密钥不匹配，我们计算一个新的哈希值。
3. 我们查找新创建的哈希值位置 52 处的密钥；我们将密钥字符串与存储的密钥值进行比较，这里匹配，如下图所示。
4. 在哈希表中返回与此密钥值对应的存储值。请参见以下图表：

def get(self, key):
h = self._hash(key)    # computer hash for the given key
while self.slots[h] is not None:
if self.slots[h].key is key:
return self.slots[h].value
h = (h+ 1) % self.size
return None     

## 测试哈希表

ht = HashTable()
ht.put("good", "eggs")
ht.put("better", "ham")
ht.put("best", "spam")
ht.put("ga", "collide")
for key in ("good", "better", "best", "worst", "ad", "ga"):
v = ht.get(key)
print(v) 

% python hashtable.py
eggs
ham
spam
None
do not
collide 

## 使用[]与哈希表

def __setitem__(self, key, value):
self.put(key, value)
def __getitem__(self, key):
return self.get(key) 

ht = HashTable()
ht["good"] = "eggs"
ht["better"] = "ham"
ht["best"] = "spam"
ht["ga"] = "collide"
for key in ("good", "better", "best", "worst", "ad", "ga"):
v = ht[key]
print(v)
print("The number of elements is: {}".format(ht.count)) 

## 符号表

name = "Joe"
age = 27 

## 第八章：图和其他算法

• 了解图是什么
• 了解图的类型和它们的组成部分
• 了解如何表示图并遍历它
• 获得优先队列的基本概念
• 能够实现优先队列
• 能够确定列表中第 i 个最小的元素

## 图

• 节点或顶点：图中的一个点或节点称为一个顶点，通常在图中用一个点表示。在前面的图中，顶点或节点是ABCDE
• ：这是两个顶点之间的连接。连接AB的线是前面图中边的一个例子。
• 循环：当一个节点的边与自身相连时，该边形成一个循环。
• 顶点的度：一个给定顶点上的边的总数被称为该顶点的度。例如，前面图中B顶点的度为4
• 邻接：这指的是任意两个节点之间的连接；因此，如果两个顶点或节点之间有连接，则它们被称为相邻。例如，C节点与A节点相邻，因为它们之间有一条边。
• 路径：任意两个节点之间的顶点和边的序列表示从A节点到B节点的路径。例如，CABE表示从C节点到E节点的路径。
• 叶节点（也称为挂节点）：如果一个顶点或节点的度为 1，则称为叶节点或挂节点。

## 有向和无向图

• 入度：进入图中一个顶点的边的总数称为该顶点的入度。例如，在前面的图中，E节点由于边CE进入，所以入度为1
• 出度：从图中一个顶点出去的边的总数称为该顶点的出度。例如，在前面的图中，E节点的出度为2，因为它有两条边EFED出去。
• 孤立顶点：当一个节点或顶点的度为零时，称为孤立顶点。
• 源顶点：如果一个顶点的入度为零，则称为源顶点。例如，在前面的图中，A节点是源顶点。
• 汇点：如果一个顶点的出度为零，则称为汇点。例如，在前面的图中，F节点是汇点。

## 邻接表

graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['E','C', 'A']
graph['C'] = ['A', 'B', 'E','F']
graph['E'] = ['B', 'C']
graph['F'] = ['C'] 

## 邻接矩阵

matrix_elements = sorted(graph.keys())
cols = rows = len(matrix_elements) 

adjacency_matrix = [[0 for x in range(rows)] for y in range(cols)]
edges_list = []

for key in matrix_elements:
for neighbor in graph[key]:
edges_list.append((key, neighbor)) 

>>> [('A', 'B'), ('A', 'C'), ('B', 'E'), ('B', 'C'), ('B', 'A'), ('C', 'A'),
('C', 'B'), ('C', 'E'), ('C', 'F'), ('E', 'B'), ('E', 'C'),
('F', 'C')]

for edge in edges_list:
index_of_first_vertex = matrix_elements.index(edge[0])
index_of_second_vertex = matrix_elements.index(edge[1])
adjacency_matrix[index_of_first_vertex][index_of_second_vertex] = 1 

matrix_elements数组有它的rowscols，从A到所有其他顶点，索引从05for循环遍历我们的元组列表，并使用index方法获取要存储边的相应索引。

>>>
[0, 1, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 1, 0, 1, 1]
[0, 1, 1, 0, 0]
[0, 0, 1, 0, 0]

Python 数据结构和算法实用指南（三）（2）https://developer.aliyun.com/article/1507581

|
2天前
|

【眼疾病识别】图像识别+深度学习技术+人工智能+卷积神经网络算法+计算机课设+Python+TensorFlow

21 9
|
2天前
|

【8月更文挑战第2天】决策树算法以其直观性和解释性在机器学习领域中独具魅力，尤其擅长处理非线性关系。相较于复杂模型，决策树通过简单的分支逻辑实现数据分类，易于理解和应用。本示例通过Python的scikit-learn库演示了使用决策树对鸢尾花数据集进行分类的过程，并计算了预测准确性。虽然决策树优势明显，但也存在过拟合等问题。即便如此，无论是初学者还是专家都能借助决策树的力量提升数据分析能力。
11 4
|
1天前
|

【8月更文挑战第3天】站在数据的海洋边，线性回归算法犹如智慧的预言家，揭示着房价的秘密。作为房地产投资者，面对复杂的市场，我们可通过收集房屋面积、位置等数据并利用Python的pandas及scikit-learn库，建立线性回归模型预测房价。通过评估模型的均方根误差(RMSE)，我们可以更精准地判断投资时机，让数据引领我们走向成功的彼岸。
7 1
|
3天前
|

Python数据分析高手修炼手册：线性回归算法，让你的数据说话更有力
【8月更文挑战第1天】在数据驱动时代,掌握数据分析技能至关重要。线性回归是最基础且强大的工具之一,能从复杂数据中提炼简单有效的模型。本文探索Python中线性回归的应用并通过实战示例加深理解。线性回归建立变量间线性关系模型:Y = β0 + β1*X + ε。使用scikit-learn库进行实战:首先安装必要库,然后加载数据、训练模型并评估性能。示例展示了如何使用LinearRegression模型进行房价预测,包括数据可视化。掌握线性回归,让数据“说话”更有力。
12 2
|
7天前
|

23 8
|
10天前
|

7月更文挑战第14天
|
11天前
|

【7月更文挑战第24天】在编程世界里, Python以简洁强大备受欢迎, 但算法设计与复杂度分析对程序性能至关重要。算法是程序的灵魂, 其效率直接影响数据处理能力。时间复杂度衡量算法执行速度, 如冒泡排序O(n²)与快速排序O(n log n)的显著差异; 空间复杂度关注内存占用, 递归算法需警惕栈溢出风险。优秀算法需平衡时间和空间效率, 深入理解问题本质, 迭代优化实现高效可靠。
20 2
|
11天前
|

【7月更文挑战第24天】在编程中，算法效率由时间复杂度（执行速度）与空间复杂度（内存消耗）决定。时间复杂度如O(n), O(n^2), O(log n)，反映算法随输入增长的耗时变化；空间复杂度则衡量算法所需额外内存。案例对比线性搜索(O(n))与二分搜索(O(log n))，后者利用有序列表显著提高效率。斐波那契数列计算示例中，递归(O(n))虽简洁，但迭代(O(1))更节省空间。掌握这些，让代码性能飞跃，从小白到高手不再是梦想。
14 1
|
17天前
|

MCKP-MMF算法是一种启发式流量估计方法，用于寻找无线传感器网络的局部最优解。它从最小配置开始，逐步优化部分解，调整访问点的状态。算法处理访问点的动态影响半径，根据带宽需求调整，以避免拥塞。在MATLAB 2022a中进行了仿真，显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段：慢启动阶段识别瓶颈并重设半径，随后进入周期性调整阶段，追求最大最小公平性。
26 1
|
1天前
|

12 4