本文还有配套的精品资源，点击获取
简介：《数据结构》是计算机科学中的基础课程，主要关注计算机中数据的组织和存储方式以及高效操作。殷人昆教授的电子课件详尽地介绍了数组、链表、栈、队列、树、图、哈希表、堆等核心数据结构，以及排序和搜索算法。课件强调C++实现，并深入探讨了数据结构的时间和空间复杂度分析，为计算机专业学生和IT从业者提供了宝贵的学习资源。
1. 数组与链表的基本概念和特性
数组与链表是数据结构中的基础构件，它们各自拥有独特的特性和应用场景。了解它们的基本概念和特性对于理解更复杂的结构至关重要。
1.1 数组的概念与特性
数组是一组具有相同类型的数据元素的集合。在内存中，数组的元素连续存储，并且可以通过下标快速访问。数组的优点是访问速度快，随机访问的时间复杂度为O(1)。然而，数组的大小是固定的，且插入和删除操作需要移动大量的元素，时间复杂度较高。
1.2 链表的概念与特性
链表是一种通过指针将一系列节点连接起来的数据结构，每个节点包含数据域和指向下一个节点的指针。链表的主要优点是动态大小，插入和删除操作仅需要改变相邻节点的指针，时间复杂度为O(1)。链表的缺点是访问元素需要遍历整个链表，因此访问速度较慢，时间复杂度为O(n)。
1.3 数组与链表的选择
在选择数组或链表时，需要根据具体的应用场景进行权衡。如果需要频繁的随机访问，则数组可能更加合适。而如果应用场景中插入和删除操作较为频繁，且内存限制较为宽松，则链表可能是一个更好的选择。
示例代码：
# 数组示例
array = [1, 2, 3, 4, 5] # 声明一个整型数组
# 链表示例
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
node1 = ListNode(1)
node2 = ListNode(2)
node1.next = node2 # 创建链表 1 -> 2
在上面的示例代码中，我们分别用Python语言创建了一个数组和一个简单的链表结构。通过这些基础概念的学习和实践，我们可以更好地理解并运用这些数据结构来解决实际问题。
2. 栈和队列的原理及应用
2.1 栈和队列的基本概念
2.1.1 栈的LIFO特性
栈是一种后进先出（Last In, First Out，LIFO）的数据结构，它的操作主要涉及两个基本动作：push和pop。push操作用于将元素添加到栈顶，而pop操作则用于移除栈顶元素。这种特性使得栈特别适合处理具有层次关系或需要逆序处理的数据。
在实际应用中，栈的LIFO特性可以用于实现各种算法和功能，例如括号匹配、函数调用栈、浏览器的后退功能等。函数调用栈是一个特别典型的例子，它记录了程序执行到某一点时的所有函数调用历史。当函数返回时，它会从调用栈中弹出，返回到上一个函数调用的环境。
2.1.2 队列的FIFO特性
队列是一种先进先出（First In, First Out，FIFO）的数据结构，它有两个主要操作：enqueue和dequeue。enqueue操作用于将元素添加到队列末尾，而dequeue操作用于从队列前端移除元素。这种特性使得队列非常适合模拟现实世界中的排队行为。
队列在各种场景下都有广泛的应用，包括任务调度、缓冲处理、并发编程中的锁队列等。在操作系统中，进程调度通常使用队列来管理待执行的进程。此外，计算机网络中，数据包的传输也经常采用队列结构来确保按照发送的顺序进行处理。
2.2 栈和队列在计算机科学中的应用
2.2.1 栈的应用实例
在算法设计中，栈是一种非常重要的数据结构，经常被用于解决诸如深度优先搜索（DFS）和括号匹配等问题。例如，在DFS中，栈用于跟踪每个节点的访问顺序，保证能够返回到上一个节点继续搜索。
另一个典型的栈应用是算术表达式求值。通过使用栈，我们可以将中缀表达式转换为后缀表达式，并最终计算其值。这个过程中，运算符和操作数被压入栈中，并在特定条件下进行弹出和组合计算。
2.2.2 队列的应用实例
队列的一个典型应用是在缓冲区管理中。在数据通信、图形用户界面事件处理和任务调度等场景中，队列保证了数据或任务按照接收或到达的顺序得到处理。
具体到算法层面，广度优先搜索（BFS）是使用队列的一个经典例子。在BFS中，队列用于记录将要探索的节点，确保每个节点的所有相邻节点都被按顺序访问到。
下面提供了一个简单的队列实现，包括入队（enqueue）和出队（dequeue）操作的代码示例：
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
"""在队列末尾添加元素"""
self.queue.append(item)
def dequeue(self):
"""从队列前端移除元素"""
if not self.is_empty():
return self.queue.popleft()
return None
def is_empty(self):
"""检查队列是否为空"""
return len(self.queue) == 0
def size(self):
"""返回队列的大小"""
return len(self.queue)
# 使用队列
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue()) # 输出 1
print(queue.dequeue()) # 输出 2
print(queue.size()) # 输出 1
在这个例子中，队列使用Python的 collections.deque 来实现，该数据结构本质上是一个双端队列，但是它提供了队列操作的高效实现。我们定义了队列的基本操作，并且使用 enqueue 和 dequeue 方法来管理元素的添加和移除。通过这种方式，我们可以模拟现实世界中排队的情景。
以上就是栈和队列的基本概念及其在计算机科学中的应用，通过理解这两个数据结构的特性和实现方法，可以为后续章节中介绍的更复杂数据结构和算法奠定坚实的基础。
3. 树形结构及其应用
3.1 树形结构的基本概念
3.1.1 树的定义和特性
树是计算机科学中一种非线性的数据结构，用来模拟具有层次关系的数据集合。在树形结构中，每一个节点（通常称为顶点）都可能有子节点，除了根节点之外的每个子节点都只有一个父节点。树结构在逻辑上呈现倒置的层次关系，即根节点位于树的顶端，而叶节点（没有子节点的节点）位于底部。
树形结构具有如下特性：
层级性 ：树是一种层次性结构，其中每个节点都可以视为一层，根节点位于顶层，而叶节点则位于最底层。 分支性 ：除根节点外，每个节点最多有一个父节点，而可以有任意数量的子节点。 根节点 ：树结构的顶部节点，它没有父节点。 叶节点 ：没有子节点的节点。 路径 ：在树中，从一个节点到另一个节点的节点序列定义了一条路径。
3.1.2 常见的树形结构
树形结构有很多变体，包括但不限于以下几种：
二叉树 ：每个节点最多有两个子节点的树结构。 二叉搜索树（BST） ：是一种特殊的二叉树，其中每个节点都满足以下性质：左子树上的所有节点的值均小于它的根节点的值；右子树上的所有节点的值均大于它的根节点的值。 平衡树 ：确保任何两个叶子节点的高度差不超过1的二叉树。 堆 ：一种特殊的完全二叉树，它满足父节点的值总是大于或等于（在最小堆中）或小于或等于（在最大堆中）任何一个子节点的值。
3.2 树形结构的应用
3.2.1 文件系统中的树形结构
在文件系统中，树形结构被用来表示文件和文件夹的层次关系。这种结构让文件系统能够有效地组织数据，使得文件和文件夹能够以有序的方式存储。
例如，文件系统中的根目录 / 是所有文件和子目录的起点。在这个目录下，可以有多个子目录（如 /home , /usr , /var 等），这些子目录又可以包含更多的子目录和文件。这种分层的结构允许用户通过逐层导航来访问文件系统中的各个文件和目录。
3.2.2 数据库中的树形结构
在数据库管理中，树形结构被用来表示和组织数据。这可以通过多种方式实现，其中包括树型索引和层次模型。
树型索引 ：特别是在存储引擎级别，例如数据库文件中的B树或B+树。这些树型索引结构帮助数据库快速定位数据记录，它们通过保持记录按一定顺序排列来优化查找、插入和删除操作。
层次模型数据库 ：一种数据库模型，其中数据以树状结构组织，每个实体类型对应树中的一个节点，而实体间的一对多关系则表现为树节点的分支。层次模型适合表示具有明确层次关系的数据，如企业组织结构。
接下来我们将深入探讨树形结构在数据库系统中的具体应用案例，以及其在数据索引、存储和查询优化方面的效果。
4. 图的构成和图算法
4.1 图的基本概念
4.1.1 图的定义和分类
图（Graph）是由顶点（Vertex）的有穷非空集合和顶点之间边（Edge）的集合组成的数据结构。在计算机科学中，图用于模拟对象与对象之间的关系，广泛应用于网络路由、社交网络分析、机器学习、推荐系统等领域。图可以分类为无向图和有向图。
无向图（Undirected Graph） ：边没有方向，表示两个顶点是互相连接的。 有向图（Directed Graph） ：边是有方向的，每个方向表示顶点之间的连接方向。
图可以进一步分类为有权图和无权图。
有权图（Weighted Graph） ：每条边都有一个与之相关的权重或成本。 无权图（Unweighted Graph） ：边不带权重，通常用在表示连接关系的场景中。
4.1.2 图的表示方法
图的表示方法主要有邻接矩阵和邻接表两种方式。
邻接矩阵（Adjacency Matrix） ：是一个二维数组，通常用二维布尔数组表示无权图，用二维数组表示有权图。如果顶点 i 与顶点 j 之间有边，则矩阵中的 a[i][j] 为 1（或边的权重），否则为 0。
# Python 邻接矩阵示例
graph_matrix = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0]
]
邻接表（Adjacency List） ：使用列表或字典来存储图中的顶点和边。列表中的每个元素对应一个顶点，其值是一个列表，包含所有与该顶点相邻的顶点。
# Python 邻接表示例
graph_list = {
'A': ['B'],
'B': ['A', 'C', 'D'],
'C': ['B', 'D'],
'D': ['B', 'C']
}
4.2 图算法的介绍
4.2.1 图的遍历算法
图的遍历算法主要有深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索（DFS, Depth-First Search） ：在图中，从一个未访问过的顶点开始，深入访问每一个分支，直到达到一个没有未访问过的相邻顶点为止，然后回溯，继续未访问过的分支。
# Python DFS 示例
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next_node in graph[start] - visited:
dfs(graph, next_node, visited)
return visited
dfs(graph_list, 'A')
广度优先搜索（BFS, Breadth-First Search） ：从一个顶点开始，访问其所有相邻顶点，然后再对每个相邻顶点执行同样的操作。
# Python BFS 示例
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
bfs(graph_list, 'A')
4.2.2 最短路径算法
最短路径算法用于在图中找到两个顶点之间的最短路径。
迪杰斯特拉算法（Dijkstra’s Algorithm） ：适用于带权重的有向或无向图中，寻找单源最短路径。算法使用贪心策略，总是选择当前已知的最短路径的顶点进行扩展。
# Python Dijkstra 算法示例
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
dijkstra(graph_list, 'A')
贝尔曼-福特算法（Bellman-Ford Algorithm） ：与迪杰斯特拉算法不同，它可以处理带有负权重边的图，并且可以检测图中是否存在负权重循环。
# Python Bellman-Ford 算法示例（简化）
def bellman_ford(graph, start):
# 此处省略了算法的实现细节
pass
以上是图的基本概念、分类、表示方法以及基本的图算法的介绍。理解这些基础知识是掌握后续复杂图算法和图在实际问题中应用的基石。
5. 哈希表的设计与实现
哈希表是一种使用哈希函数组织数据，以支持快速插入、删除和查找的数据结构。由于其平均时间复杂度为O(1)的访问速度，哈希表被广泛应用于各种计算问题中。
5.1 哈希表的基本概念
5.1.1 哈希表的定义和特性
哈希表，也称为散列表，通过一个哈希函数将键（Key）映射到表中的位置（槽 Slot）来存储数据。理想情况下，这个哈希函数可以将不同的键映射到不同的位置，但在实际中，由于键的数量可能远大于表的大小，冲突（Collision）不可避免。
5.1.2 哈希函数的设计
哈希函数的设计是哈希表中最为关键的部分。一个好的哈希函数能够将键均匀地分布到哈希表中，以减少冲突。设计哈希函数时需要考虑以下原则：
确定性：相同的键必须产生相同的哈希值。 快速计算：哈希值应能快速计算出来。 高效分布：哈希值在表中的分布应该是均匀的。
一个简单的哈希函数设计是使用键的某些部分直接计算索引，例如通过求模操作对键的值取余数。
5.1.3 哈希表的冲突解决
解决哈希冲突的方法主要有开放寻址法和链地址法两种。
开放寻址法（Open Addressing）通过寻找下一个空的槽位来解决冲突，例如线性探测、二次探测等。 链地址法（Chaining）则是在每个槽位上存储一个链表，冲突的元素作为链表中的节点。
5.2 哈希表的应用
5.2.1 哈希表在数据存储中的应用
哈希表在数据存储中应用广泛，例如数据库索引、缓存系统等。在数据库中，索引通常使用哈希表来实现，可以快速定位到数据所在的记录。
-- 示例：在MySQL中创建一个具有哈希索引的表
CREATE TABLE example (
key INT,
value VARCHAR(255),
INDEX (key) USING HASH
);
5.2.2 哈希表在搜索引擎中的应用
搜索引擎中，哈希表用于存储页面索引。搜索引擎通过哈希表快速定位页面的索引信息，从而快速进行页面的检索和排名。
# 示例：使用Python实现一个简单的哈希表类，用于存储索引数据
class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)]
def hash_function(self, key):
return key % self.size
def insert(self, key, value):
index = self.hash_function(key)
self.table[index].append((key, value))
def search(self, key):
index = self.hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# 创建一个大小为10的哈希表
index_hash_table = HashTable(10)
index_hash_table.insert("page1", "content_page1")
# ...
哈希表的这种快速访问特性使其在需要快速数据访问和检索的场景中具有不可替代的作用。随着技术的进步，哈希表的实现和优化方法也在不断发展，以适应更大规模和更复杂数据的处理需求。
6. 堆结构及其应用
堆结构是计算机科学中一种特殊的树形数据结构，它能够快速定位到数据集合中的最大值或最小值。其应用非常广泛，尤其在优先队列和堆排序的实现上具有高效的特点。本章将从堆的定义和特性开始，深入探讨堆的内部操作和实现方法，并通过实例来说明堆结构在实际应用中的作用。
6.1 堆结构的基本概念
6.1.1 堆的定义和特性
堆是一种基于二叉树的完全二叉树结构，通常用于实现优先队列。在堆中，每个节点都满足堆的性质，即该节点的值总是不大于（或不小于）其子节点的值，这取决于我们构建的是最大堆还是最小堆。在最大堆中，父节点总是大于或等于其任何子节点的值；而在最小堆中，父节点总是小于或等于其任何子节点的值。
堆结构的几个关键特性包括：
完全二叉树 ：除了最后一层外，每一层都是完全填充的，且最后一层的所有节点都尽可能向左填充。 堆性质 ：每个节点的值都满足堆的性质，即父节点大于等于（最大堆）或小于等于（最小堆）其子节点。 数组表示 ：堆通常通过数组来实现，而不是传统的节点和边的方式。在数组表示中，对于任意位置为 i 的元素，其左子节点的位置是 2i+1，右子节点的位置是 2i+2，父节点的位置是 (i-1)/2。
6.1.2 堆的操作和实现
堆提供了多个基本操作，如插入、删除、查找最大值或最小值等。这些操作的实现基于几个核心算法，主要包括：
Sift up（上浮） ：在插入新元素后，如果新元素大于其父节点（最大堆），则与父节点交换位置，直到满足堆性质。 Sift down（下沉） ：在删除最大值或最小值后，将堆尾元素放到根节点位置，然后与其子节点比较，如果子节点更大（或更小，对于最小堆），则与较大（或较小）子节点交换，直到满足堆性质。 Build heap（构建堆） ：从一个无序的数组构建一个堆结构，可以通过从最后一个非叶子节点开始执行sift down操作实现。
下面是一个构建最大堆并插入元素的简单示例代码：
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
# 如果左子节点存在且大于当前最大值，则更新最大值
if left < n and arr[largest] < arr[left]:
largest = left
# 如果右子节点存在且大于当前最大值，则更新最大值
if right < n and arr[largest] < arr[right]:
largest = right
# 如果最大值不是根节点，则交换它们，并继续sift down
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def build_heap(arr):
n = len(arr)
# 从最后一个非叶子节点开始，向上构建堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 构建最大堆
arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
build_heap(arr)
print("堆数组:", arr)
# 向堆中插入新元素
heapify(arr, len(arr), 0)
print("插入元素后的堆数组:", arr)
在上述代码中， heapify 函数用于维护最大堆的性质， build_heap 函数则用来构建一个最大堆。当我们插入一个新元素时，我们调用 heapify 函数确保堆性质得到满足。
6.2 堆结构的应用
6.2.1 堆在优先队列中的应用
优先队列是一种允许插入元素并按照元素优先级进行删除操作的数据结构。在优先队列中，每个元素都有一个与之关联的优先级，具有最高优先级的元素总是最先被删除。堆结构因其高效的堆操作，成为实现优先队列的理想选择。
在优先队列的堆实现中，堆顶元素自然是具有最高优先级的元素。当需要删除元素时，直接移除堆顶元素，并将堆尾元素移动到堆顶，然后执行下沉操作。这种操作的时间复杂度为 O(log n)，其中 n 是堆中元素的数量。相应地，插入新元素时，新元素被添加到堆尾，然后执行上浮操作，时间复杂度也是 O(log n)。
6.2.2 堆在堆排序中的应用
堆排序是一种基于比较的排序算法，它利用了堆结构的特性来进行排序。具体来说，堆排序分为两个主要步骤：
构建堆 ：首先将无序的输入数据构建成一个最大堆。 排序 ：重复执行以下操作，直到堆的大小减为 1： - 将堆顶元素（当前最大值）与堆的最后一个元素交换。 - 缩小堆的范围，不包括最后一个元素（此时已为最大值，可视为已排序）。 - 对新的堆顶元素执行下沉操作，恢复最大堆的性质。
堆排序的特点是原地排序，不需要额外的空间，排序过程中堆的大小逐渐减小，直到完成排序。其平均和最坏情况下的时间复杂度均为 O(n log n)，其中 n 是待排序的元素数量。
以下是堆排序的Python实现代码：
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 一个个从堆顶取出元素，然后重新调整堆
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0)
# 测试代码
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后的数组:", arr)
在这个例子中，我们首先构建了一个最大堆，然后通过逐个从堆顶取出最大元素并重新调整堆来实现排序。最后，得到的数组是按升序排列的。
堆结构因其独特的性质和操作效率，在计算机科学领域有着广泛的应用，尤其在处理需要快速访问最大或最小元素的场景时，堆结构显得尤为重要。无论是优先队列还是堆排序，堆结构都是不可或缺的数据结构之一。
7. 排序和搜索算法
7.1 排序算法的原理和应用
排序算法是计算机科学中不可或缺的一部分，它们用于将数据按照特定顺序排列。理解不同的排序算法以及它们的优缺点对于选择合适的算法来解决特定问题至关重要。
7.1.1 常见的排序算法
在数据排序中，存在多种算法，每种算法都有其特定的用例和性能特征。下面列举了一些常见的排序算法，并简单介绍它们的特点：
冒泡排序（Bubble Sort） 原理 ：通过重复遍历待排序的数组，比较并交换相邻元素，如果它们的顺序错误，直到整个数组排序完成。 复杂度 ：平均和最坏情况时间复杂度为O(n^2)，最好情况为O(n)（已排序数组）。
选择排序（Selection Sort）
原理 ：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。 复杂度 ：时间复杂度始终为O(n^2)。
插入排序（Insertion Sort）
原理 ：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 复杂度 ：平均和最坏情况时间复杂度为O(n^2)，最好情况为O(n)（已排序数组）。
快速排序（Quick Sort）
原理 ：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 复杂度 ：平均时间复杂度为O(n log n)，最坏情况为O(n^2)（很少出现）。
归并排序（Merge Sort）
原理 ：采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列。 复杂度 ：时间复杂度始终为O(n log n)。
7.1.2 排序算法的选择和应用
选择哪种排序算法主要取决于数据的大小、数据是否已经部分排序、排序的稳定性需求和空间复杂度的要求。例如：
数据量较小 ：可以使用插入排序或冒泡排序，因为它们实现简单。 需要稳定排序 ：归并排序是稳定的，但快速排序在默认情况下是不稳定的。 对空间有严格要求 ：原地排序算法（如快速排序和堆排序）是首选。 数据已经部分排序 ：插入排序的性能会有很大提升。
7.2 搜索算法的类型和原理
搜索算法用于在数据集合中查找特定的元素。它们的效率直接影响到程序处理数据的速度和响应时间。
7.2.1 常见的搜索算法
搜索算法的种类也比较多，以下是几种常见的搜索算法：
线性搜索（Linear Search） 原理 ：也称顺序搜索，它逐个检查每个元素直到找到所需的特定项或遍历完所有元素。 复杂度 ：平均和最坏情况时间复杂度为O(n)。
二分搜索（Binary Search）
原理 ：前提是数据集合必须有序，通过比较数组中的中间元素与目标值，不断缩小搜索范围来实现。 复杂度 ：时间复杂度为O(log n)。
深度优先搜索（DFS）
原理 ：是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深地搜索树的分支。 复杂度 ：时间复杂度为O(n)，在最坏情况下会遍历整个图。
广度优先搜索（BFS）
原理 ：同样用于树和图的遍历，从根节点开始，逐层向外扩展直到找到目标节点。 复杂度 ：时间复杂度为O(n)，其中n是图中节点的数量。
7.2.2 搜索算法的实现和应用
各种搜索算法在实现上都有不同的特点，以下为几个示例：
线性搜索实现示例
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
二分搜索实现示例
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
广度优先搜索实现示例
from collections import deque
def bfs(graph, start):
visited, queue = set(), deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
return visited
使用上述搜索算法，我们可以根据应用场景的不同需求选择最合适的搜索方法。例如，二分搜索在数组中查找效率很高，而DFS和BFS在解决连通性问题和图的遍历时则非常有效。
这些排序和搜索算法是数据结构与算法中的基础，对它们的深入理解和灵活运用可以帮助我们在IT行业和相关领域解决实际问题。
本文还有配套的精品资源，点击获取
简介：《数据结构》是计算机科学中的基础课程，主要关注计算机中数据的组织和存储方式以及高效操作。殷人昆教授的电子课件详尽地介绍了数组、链表、栈、队列、树、图、哈希表、堆等核心数据结构，以及排序和搜索算法。课件强调C++实现，并深入探讨了数据结构的时间和空间复杂度分析，为计算机专业学生和IT从业者提供了宝贵的学习资源。
本文还有配套的精品资源，点击获取