本文详细介绍了大厂数据结构与算法入门的相关知识，包括数据结构和算法的基本概念、常见类型及其应用场景，并提供了丰富的代码示例。文章还涵盖了数组、链表、树和图等核心数据结构，以及排序和查找算法的实际应用，帮助读者更好地理解和掌握这些基础知识。掌握这些内容不仅有助于提高编程效率，还能提升解决问题的能力，为面试做好充分准备。
数据结构基础什么是数据结构
数据结构是计算机科学中的一个重要概念，它指的是在计算机中组织和存储数据的方式，以便能够高效地访问和修改数据。数据结构不仅涉及数据的组织方式，还涉及相关的操作和算法。良好的数据结构设计可以提高程序的效率和性能，减少资源消耗。理解数据结构的基本概念和重要性，对于编写高效的程序至关重要。
常见的数据结构类型介绍
-
数组
数组是一种基本的数据结构，由一组相同类型的数据组成，每个元素都有一个唯一的索引。数组的主要优点是访问速度快，但由于大小固定，不适合频繁增删元素。# Python代码示例 array = [1, 2, 3, 4, 5] print(array[0]) # 输出第一个元素 -
链表
链表是一种动态数据结构，由多个节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点是插入和删除操作都相对简单，但查找操作相对较慢。# Python代码示例：单链表实现 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next # 创建链表 head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3) # 遍历链表 current = head while current: print(current.val) current = current.next -
栈
栈是一种只能在一端进行插入和删除操作的数据结构，遵循后进先出（LIFO）的原则。栈通常用于函数调用、表达式求值等场景。# Python代码示例 class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() def is_empty(self): return len(self.items) == 0 stack = Stack() stack.push(1) stack.push(2) print(stack.pop()) # 输出 2 -
队列
队列是一种只能在一端插入和另一端删除数据的数据结构，遵循先进先出（FIFO）的原则。队列通常用于任务调度、进程管理等场景。# Python代码示例 from collections import deque queue = deque() queue.append(1) queue.append(2) print(queue.popleft()) # 输出 1 -
树
树是一种非线性的数据结构，由节点构成，每个节点可以有零个或多个子节点。树结构广泛应用于文件系统、数据库索引等场景。# Python代码示例：二叉树实现 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right # 创建二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) # 遍历二叉树 def inorder_traversal(node): if node: inorder_traversal(node.left) print(node.val) inorder_traversal(node.right) inorder_traversal(root) # 输出 4 2 1 3 -
图
图是一种由节点和边组成的非线性数据结构，用于表示复杂的连接关系。图结构广泛应用于社交网络、路径规划等场景。# Python代码示例：无向图实现 from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def add_edge(self, u, v): self.graph[u].append(v) self.graph[v].append(u) def print_graph(self): for node in self.graph: print(node, '->', self.graph[node]) # 创建无向图 graph = Graph() graph.add_edge(1, 2) graph.add_edge(1, 3) graph.add_edge(2, 4) # 打印图 graph.print_graph()
数据结构的应用场景
- 数组：适用于需要快速访问元素的场景，如查找数组中的最大值或最小值。
- 链表：适用于需要频繁插入和删除操作的场景，如实现缓存淘汰算法。
- 栈：适用于需要后进先出处理的场景，如函数调用栈或括号匹配。
- 队列：适用于需要先进先出处理的场景，如任务队列或进程调度。
- 树：适用于层次结构的场景，如文件系统或数据库索引。
- 图：适用于复杂的连接关系，如社交网络或路径规划。
什么是算法
算法是一系列定义明确的步骤，用于解决特定问题或执行特定任务。算法的设计和实现是计算机科学的核心。一个有效的算法应具备以下特性：
- 输入：算法可以有零个或多个输入。
- 输出：算法至少有一个输出。
- 确定性：对于相同的输入，算法每次执行的结果相同。
- 有限性：算法在有限步骤后终止。
- 有效性：算法的每一步都是有效的。
常见算法类型介绍
-
排序算法
排序算法用于将元素按特定顺序排序。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序等。每种算法都有其特点和应用场景，如冒泡排序通过重复遍历数组，比较相邻元素并交换顺序；选择排序通过将列表分为已排序和未排序两部分，每次从未排序部分选择最小的元素，移动到已排序部分的末尾；插入排序通过遍历列表，将每个元素插入到已排序部分的正确位置；快速排序通过递归地将列表分为较小和较大两部分，分别对两部分进行排序。 -
查找算法
查找算法用于在数据结构中查找特定元素。常见的查找算法有线性查找、二分查找等。线性查找通过遍历整个列表查找指定的元素；二分查找通过将列表分成两部分，每次查找中间元素，缩小查找范围。 -
图算法
图算法用于处理图结构中的问题，如最短路径算法（Dijkstra算法、Floyd算法）、最小生成树算法（Prim算法、Kruskal算法）等。 -
动态规划
动态规划用于解决最优化问题，通过将问题分解为子问题并存储子问题的结果来提高效率。 - 贪心算法
贪心算法通过在每一步选择当前最优解来构建全局最优解。
算法的时间复杂度和空间复杂度
时间复杂度
时间复杂度指的是算法执行所需的时间与输入大小的关系。常见的时间复杂度有：
- O(1)：常数时间复杂度，算法执行时间与输入大小无关，如访问数组中的元素。
- O(log n)：对数时间复杂度，如二分查找。
- O(n)：线性时间复杂度，如遍历数组。
- O(n^2)：平方时间复杂度，如冒泡排序。
- O(n log n)：对数线性时间复杂度，如快速排序。
- O(2^n)：指数时间复杂度，如汉诺塔问题。
空间复杂度
空间复杂度指的是算法执行所需的空间与输入大小的关系。常见的空间复杂度有：
- O(1)：常数空间复杂度，算法执行所需的空间与输入大小无关，如交换两个变量的值。
- O(n)：线性空间复杂度，如创建一个与输入大小相同的数组。
- O(log n)：对数空间复杂度，如递归算法所需的空间。
数组的概念与操作
数组是一种基本的数据结构，由一组相同类型的数据组成，每个元素都有一个唯一的索引。数组的主要优点是访问速度快，但由于大小固定，不适合频繁增删元素。
数组的常见操作
- 访问：通过索引访问数组中的元素。
- 插入：在数组中插入一个新元素。
- 删除：从数组中删除一个元素。
- 查找：在数组中查找特定元素。
# Python代码示例：数组的基本操作
array = [1, 2, 3, 4, 5]
# 访问
print(array[2]) # 输出 3
# 插入
array.insert(2, 6)
print(array) # 输出 [1, 2, 6, 3, 4, 5]
# 删除
array.remove(6)
print(array) # 输出 [1, 2, 3, 4, 5]
# 查找
if 3 in array:
print("找到了3")链表的概念与操作
链表是一种动态数据结构，由多个节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点是插入和删除操作都相对简单，但查找操作相对较慢。
链表的常见操作
- 访问：通过遍历链表访问节点。
- 插入：在链表中插入一个新节点。
- 删除：从链表中删除一个节点。
- 查找：在链表中查找特定节点。
# Python代码示例：单链表的基本操作
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 创建链表：1 -> 2 -> 3
head = ListNode(1, ListNode(2, ListNode(3)))
# 访问
current = head
while current:
print(current.val)
current = current.next
# 插入
new_node = ListNode(4)
current = head
while current.next:
current = current.next
current.next = new_node
# 删除
current = head
while current and current.next.val != 4:
current = current.next
if current and current.next:
current.next = current.next.next
# 查找
current = head
while current:
if current.val == 4:
print("找到了4")
break
current = current.next数组与链表的比较与选择
| 特性 | 数组 | 链表 |
|---|---|---|
| 访问速度 | 快 | 慢 |
| 插入删除 | 慢 | 快 |
| 空间效率 | 高 | 低 |
| 适用场景 | 需要快速访问元素 | 需要频繁插入删除 |
- 访问速度：数组通过索引访问，速度很快；链表需要遍历节点，速度较慢。
- 插入删除：数组需要移动大量元素，速度较慢；链表只需要修改指针，速度很快。
- 空间效率：数组只需要存储元素本身；链表还需要存储指针。
- 适用场景：数组适合需要快速访问元素的场景；链表适合需要频繁插入删除的场景。
树的基本概念与特性
树是一种非线性的数据结构，由节点构成，每个节点可以有零个或多个子节点。树结构广泛应用于文件系统、数据库索引等场景。
树的特性
- 根节点：树的唯一一个没有父节点的节点。
- 叶子节点：没有子节点的节点。
- 父节点：一个节点的孩子节点的父节点。
- 子节点：一个节点的父节点下面的孩子节点。
- 高度：树中从根节点到最远叶子节点的最长路径长度。
- 深度：一个节点到根节点的路径长度。
树的常见类型
- 二叉树：每个节点最多有两个子节点。
- 满二叉树：每个节点都有两个子节点或没有子节点。
- 完全二叉树：除最后一层外，每一层都是满的。
- 平衡二叉树：任何节点的左右子树的高度差不超过1。
- 二叉查找树：任何节点的左子树的值都小于该节点的值，右子树的值都大于该节点的值。
# Python代码示例：二叉查找树实现
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert(val, self.root)
def _insert(self, val, node):
if val < node.val:
if node.left:
self._insert(val, node.left)
else:
node.left = TreeNode(val)
else:
if node.right:
self._insert(val, node.right)
else:
node.right = TreeNode(val)
def find(self, val):
return self._find(val, self.root)
def _find(self, val, node):
if not node:
return False
if val == node.val:
return True
elif val < node.val:
return self._find(val, node.left)
else:
return self._find(val, node.right)
# 创建二叉查找树
bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(8)
bst.insert(1)
bst.insert(4)
# 查找
print(bst.find(4)) # 输出 True
print(bst.find(6)) # 输出 False图的基本概念与特性
图是一种由节点和边组成的非线性数据结构，用于表示复杂的连接关系。图结构广泛应用于社交网络、路径规划等场景。
图的特性
- 节点：图中的基本单元，表示一个对象。
- 边：连接两个节点的连接关系。
- 有向图：边有方向，表示从一个节点到另一个节点的关系。
- 无向图：边没有方向，表示两个节点之间的关系。
- 权值：边可能具有权值，表示边的某种量度。
- 路径：图中从一个节点到另一个节点的一系列边。
- 环：一个节点通过一些边回到它自身。
- 连通图：图中任意两个节点之间都存在路径。
图的常见类型
- 无向图：边没有方向。
- 有向图：边有方向。
- 带权图：边具有权值。
- 有权无向图：边有方向且具有权值。
# Python代码示例：无向图实现
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def print_graph(self):
for node in self.graph:
print(node, '->', self.graph[node])
# 创建无向图
graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
# 打印图
graph.print_graph()树与图的应用实例
- 文件系统：文件系统通常使用树形结构表示文件和目录的关系。
- 数据库索引：数据库索引通常使用树形结构提高数据查找效率。
- 社交网络：社交网络通常使用图结构表示用户之间的好友关系。
- 路径规划：路径规划算法通常使用图结构表示路径和距离。
常见排序算法介绍
-
冒泡排序
冒泡排序是一种简单的排序算法，通过重复遍历要排序的列表，比较相邻元素并交换顺序。 -
选择排序
选择排序通过将列表分为已排序和未排序两部分，每次从未排序部分选择最小的元素，移动到已排序部分的末尾。 -
插入排序
插入排序通过遍历列表，将每个元素插入到已排序部分的正确位置。 - 快速排序
快速排序通过递归地将列表分为较小和较大两部分，分别对两部分进行排序。
常见查找算法介绍
-
线性查找
线性查找通过遍历整个列表查找指定的元素。 -
二分查找
二分查找通过将列表分成两部分，每次查找中间元素，缩小查找范围。 - 哈希查找
哈希查找通过哈希函数将元素映射到特定位置进行查找。
排序与查找算法的实现示例
# Python代码示例：冒泡排序实现
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 测试冒泡排序
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # 输出 [11, 12, 22, 25, 34, 64, 90]
# Python代码示例：选择排序实现
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
# 测试选择排序
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print(arr) # 输出 [11, 12, 22, 25, 34, 64, 90]
# Python代码示例：二分查找实现
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# 测试二分查找
arr = [1, 2, 3, 4, 5]
target = 3
index = binary_search(arr, target)
if index != -1:
print(f"找到了目标值，索引为 {index}")
else:
print("未找到目标值")数据结构与算法在面试中的重要性
数据结构与算法是面试中的重要环节，考察应聘者的基础知识和解决问题的能力。掌握数据结构与算法不仅可以提高编程效率，还能让面试官看到应聘者的技术水平。
实战演练：典型题目解析
-
题目1：给定一个整数数组，找到两个数，使它们的和等于目标数，返回这两个数的索引。
def two_sum(nums, target): num_dict = {} for i, num in enumerate(nums): complement = target - num if complement in num_dict: return [num_dict[complement], i] num_dict[num] = i # 测试 nums = [2, 7, 11, 15] target = 9 result = two_sum(nums, target) print(result) # 输出 [0, 1] -
题目2：给定一个排序数组，查找目标值，如果存在返回其索引，否则返回-1。
def search(nums, target): low, high = 0, len(nums) - 1 while low <= high: mid = (low + high) // 2 if nums[mid] == target: return mid elif nums[mid] < target: low = mid + 1 else: high = mid - 1 return -1 # 测试 nums = [-1, 0, 3, 5, 9, 12] target = 9 result = search(nums, target) print(result) # 输出 4
优化与调试技巧
- 优化：优化算法时间复杂度和空间复杂度，使用更高效的算法或数据结构。
- 调试：使用调试工具逐步执行代码，检查变量的值和程序的执行流程。
掌握数据结构与算法不仅可以提高编程效率，还能提升解决问题的能力。在面试中，通过深入理解算法原理和实践应用，可以更好地展示自己的技术实力。
共同學習，寫下你的評論
評論加載中...
作者其他優質文章
