基础概念与简单数据结构
目标: 掌握数据结构的基本概念和简单的数据结构。
学习内容:
- 什么是数据结构：定义和分类（线性、非线性）。
- 算法复杂度分析：时间复杂度和空间复杂度的基础知识（O(n)、O(1)、O(log n)等）。
- 数组（Array）：
- 数组的定义和特性。
- 常见操作（插入、删除、查找）的时间复杂度分析。
- 链表（Linked List）：
- 单向链表、双向链表、循环链表的结构和特点。
- 链表与数组的对比及应用场景。
实践:
- 实现简单的数组和链表操作，如插入、删除、查找等。
- 用语言的标准库进行链表相关操作，理解其背后实现。
学习笔记
1. 数据结构的定义与分类
1.1 数据结构的定义:
- 数据结构是一种组织、管理和存储数据的方式，使得数据能够高效地被访问和修改。
- 数据结构不仅仅涉及数据的存储方式，还包括如何处理这些数据的算法。
1.2 数据结构的分类:
线性结构: 数据按顺序排列，每个元素有且仅有一个前驱和一个后继。如：
- 数组（Array）: 固定大小的连续内存块，用索引直接访问。
- 链表（Linked List）: 元素通过指针连接，内存不连续。
- 栈（Stack）: 后进先出（LIFO），只允许在一端进行插入和删除。
- 队列（Queue）: 先进先出（FIFO），在一端插入，在另一端删除。
非线性结构: 数据之间的关系复杂，元素之间可能存在多个前驱和后继。如：
- 树（Tree）: 层次结构，每个节点可以有多个子节点。
- 图（Graph）: 顶点和边的集合，表示任意复杂关系。
学习要点:
- 线性结构适合顺序访问，非线性结构适合表示复杂的多对多关系。
2. 算法复杂度分析
2.1 时间复杂度:
- O(1): 操作时间不随输入规模变化，如数组访问元素。
- O(n): 操作时间随输入规模线性增加，如数组遍历。
- O(log n): 操作时间随输入规模对数增长，如二分查找。
- O(n^2): 操作时间随输入规模平方增长，如冒泡排序。
2.2 空间复杂度:
- O(1): 所需额外空间不随输入规模变化，如变量存储。
- O(n): 所需空间随输入规模线性增长，如存储n个元素的数组。
示例:
- 数组查找: 访问任意位置的元素，时间复杂度为O(1)。
- 链表查找: 需遍历链表，时间复杂度为O(n)。
学习要点:
- 理解常见算法的时间复杂度和空间复杂度，有助于评估算法性能和选择合适的数据结构。
3. 数组（Array）
3.1 数组的定义:
- 数组是存储在连续内存块中的相同类型元素的集合，每个元素通过一个整数索引进行访问。
3.2 数组的特性:
- 大小固定: 数组的大小在创建时确定，不能动态调整。
- 高效访问: 通过索引可以在O(1)时间内访问元素。
3.3 数组的常见操作:
- 插入:
- 在末尾插入: 直接在数组末尾添加元素，时间复杂度为O(1)。
- 在中间插入: 需要移动后续元素，时间复杂度为O(n)。
- 删除:
- 删除末尾元素: 直接移除最后一个元素，时间复杂度为O(1)。
- 删除中间元素: 需要移动后续元素，时间复杂度为O(n)。
- 查找:
- 根据索引查找: 直接访问元素，时间复杂度为O(1)。
- 根据值查找: 遍历数组查找匹配值，时间复杂度为O(n)。
学习要点:
- 数组适合用于需要频繁访问和遍历数据的场景。
- 插入和删除中间元素的操作代价较高，可能需要考虑其他数据结构如链表。
4. 链表（Linked List）
4.1 单向链表:
- 结构: 每个节点包含数据部分和指向下一个节点的指针。
- 操作:
- 插入: 在链表头部插入节点，时间复杂度为O(1)。
- 删除: 删除指定节点后，重新链接前后节点，时间复杂度为O(n)。
- 查找: 遍历链表查找指定值，时间复杂度为O(n)。
4.2 双向链表:
- 结构: 每个节点包含数据、前驱指针和后继指针，可以双向遍历。
- 操作:
- 插入和删除: 时间复杂度为O(1)，适合频繁插入/删除操作。
- 查找: 双向遍历，查找效率提高，但占用内存更多。
4.3 循环链表:
- 结构: 最后一个节点指向链表的第一个节点，形成闭环。
- 特点: 适用于循环数据处理，如操作系统的任务调度。
4.4 链表与数组对比:
- 数组: 大小固定，随机访问快，插入/删除慢。
- 链表: 大小动态，插入/删除快，随机访问慢。
学习要点:
- 链表适用于需要动态增长且频繁插入/删除数据的场景。
- 理解链表的指针操作对于掌握链表结构至关重要。
5. 实践部分
5.1 数组操作实践:
实现数组插入:
在数组末尾添加元素，代码示例（伪代码）：
def insert_to_array(array, element): array.append(element)在数组中间插入元素：
def insert_to_array_at_index(array, index, element): array.insert(index, element)
实现数组删除:
删除数组末尾元素：
def remove_from_array(array): array.pop()删除数组中间元素：
def remove_from_array_at_index(array, index): array.pop(index)
实现数组查找:
根据索引查找元素：
def get_element_at_index(array, index): return array[index]根据值查找元素：
def find_element_in_array(array, value): for i, element in enumerate(array): if element == value: return i return -1 # 未找到时返回-1
5.2 链表操作实践:
单向链表节点类的定义:
class Node: def __init__(self, data): self.data = data self.next = None链表的基本操作:
插入节点（头插法）：
def insert_at_head(head, data): new_node = Node(data) new_node.next = head return new_node # 新节点成为新的头节点删除节点（删除给定值的节点）：
def delete_node(head, value): if head.data == value: return head.next # 如果头节点就是要删除的节点 current = head while current.next: if current.next.data == value: current.next = current.next.next return head current = current.next return head # 未找到节点查找节点：
def find_node(head, value): current = head while current: if current.data == value: return current current = current.next return None # 未找到节点
5.3 标准库链表操作:
使用Python的
collections.deque:from collections import deque # 创建双端队列（可以作为双向链表使用） linked_list = deque() # 插入元素 linked_list.append('a') # 在尾部插入 linked_list.appendleft('b') # 在头部插入 # 删除元素 linked_list.pop() # 删除尾部元素 linked_list.popleft() # 删除头部元素 # 查找元素 # 由于deque不支持直接查找，可以通过遍历查找 if 'a' in linked_list: print('Found')