数据结构与算法

学习笔记

数学基础层

必备知识：微积分、线性代数、离散数学（集合论、图论、数理逻辑）、概率论与数理统计
作用：支撑算法推导、逻辑证明及建模能力，如算法复杂度分析依赖离散数学，机器学习依赖概率论（CS 自学指南）

计算机系统层

核心课程：计算机组成原理（CPU/存储体系）、操作系统（进程管理/内存调度）、计算机网络（TCP/IP 协议栈）
学习重点：理解软硬件交互机制，例如虚拟内存技术如何关联 OS 与硬件（深入理解计算机系统）

数据与算法层

核心内容：数据结构（数组/链表/树）、算法设计（排序/搜索/动态规划）、数据库系统（SQL/事务原理）
实践要求：通过 LeetCode 刷题（推荐按专题分类）、实现数据库索引（B+树结构）（数据结构与算法基础）

开发工具与工程化层

关键技能：版本控制（Git）、系统编程（Linux C）、软件工程（敏捷开发/测试方法）
工具链：GCC 编译器、Docker 容器化、CI/CD 自动化流程（Linux 程序设计）

应用技术层

主流方向：人工智能（机器学习/深度学习）、Web 开发（前后端框架）、移动开发（iOS/Android）
技术栈示例：Python+PyTorch（AI）、React+Node.js（Web）、Kotlin（Android）（AI 基础知识学习库）

c 语言

学习路线：

  1. 基础学习（语法入门、数据类型、运算符和表达式、控制流语句）
  2. 进阶学习（Linux 系统编程、网络编程）
  3. 应用学习（嵌入式开发、Linux 开发、底层驱动、逆向安全）

基础语法

  • 数据类型
  • 运算符和表达式
  • 控制流语句

数组

字符串

函数

结构体

访问结构成员

成员访问运算符

  • 点运算符（结构体变量）：struct_name.member_name
  • 箭头运算符（结构体指针变量）：struct_ptr->member_name

共用体

指针

指针变量存储的是地址。

多级指针相当于指针数组

内存管理

  • malloc
  • calloc
  • realloc
  • free
  • memcpy

申请地址空间

1
2
int *p = malloc(sizeof(int));
int *arr = calloc(10, sizeof(int));

释放地址空间

1
free(p);

释放空间要从最小单位开始释放

1
2
3
4
5
6
7
8
9
10
buckets 变量（双指针）
│
↓
┌────────┬────────┬────────┬────────┐
│ 指针 0 │ 指针 1 │ 指针 2 │ 指针 3 │ ← 这就是指针数组！
│ (Node*)| (Node*)| (Node*)| (Node*)│
└────────┴────────┴────────┴────────┘
│ │ │ │
↓ ↓ ↓ ↓
链表头 链表头 链表头 链表头

文件操作

预处理命令

C 语言标准库

assert.h

assert 是 c 语言中的一个宏，用于在程序运行时检查一个条件是否为真。如果条件为假，assert 会触发一个断言失败的错误，并且程序会终止运行。

assert 宏的定义如下：

1
2
3
#include <assert.h>

void assert(int expression);

其中，expression 是一个返回值为整数的表达式。如果 expression 的值为 0，assert 会触发断言失败的错误。

数据结构与算法

复杂度分析

时间复杂度

空间复杂度

数据结构

线性数据结构：

  • 数组
  • 链表
  • 栈
  • 队列

非线性数据结构：

  • 树
  • 图

字符编码

  • ASCII 码
  • Unicode 码
  • UTF-8 编码

数字编码

  • 原码
    • 最高位为符号位，0 表示正数，1 表示负数
  • 反码
    • 正数的反码与原码相同
    • 负数的反码为其原码除符号位外各位取反
  • 补码
    • 正数的补码与原码相同
    • 负数的补码为其反码加 1

原码 -> 补码

  • 正数的补码与原码相同
  • 负数的补码为其反码加 1

补码 -> 原码

  • 正数的原码与补码相同
  • 负数的原码为其补码除符号位外各位取反加 1

数组

数组是一种线性数据结构，每个元素在内存中都是连续存储的。

优点：

  • 访问操作效率高，时间复杂度为 O(1)

缺点：

  • 插入和删除操作效率低，时间复杂度为 O(n)

操作：

  • 初始化
  • 访问
  • 插入
  • 删除
  • 扩容

链表

链表是一种线性数据结构，每个节点元素包括数据域和指针域。

优点：

  • 动态分配内存，不需要提前分配内存空间
  • 插入和删除操作效率高，时间复杂度为 O(1)

缺点：

  • 访问操作效率低，时间复杂度为 O(n)

分类：

  • 单链表
  • 双链表
  • 循环链表

操作：

  • 初始化
  • 插入
  • 删除
  • 访问
  • 遍历
  • 查找

列表

列表是抽象的数据结构，它是一种有序的集合，每个元素都有一个唯一的索引。

  • 基于数组实现
  • 基于链表实现

操作：

  • 初始化
  • 访问
  • 修改
  • 插入
  • 删除
  • 遍历
  • 查找
  • 排序

栈

栈是一种线性数据结构，遵循后进先出（LIFO）的原则。

实现：

  • 基于数组实现
  • 基于链表实现

操作：

  • 初始化
  • 入栈
  • 出栈
  • 访问栈顶元素
  • 检查栈是否为空
  • 遍历栈元素

队列

队列是一种线性数据结构，遵循先进先出（FIFO）的原则。

操作：

  • 初始化
  • 入队
  • 出队
  • 访问队头元素
  • 检查队列是否为空
  • 遍历队列元素

双向队列

双向队列是一种线性数据结构，允许在队列的两端进行入队和出队操作。
表现栈和队列的逻辑特征。

实现：

  • 基于数组实现
  • 基于链表实现

操作：

  • 初始化
  • 入队（队头入队、队尾入队）
  • 出队（队头出队、队尾出队）
  • 访问队头元素
  • 访问队尾元素
  • 检查队列是否为空
  • 遍历队列元素

哈希表

哈希表（Hash Table），又称散列表，是一种基于哈希函数实现的键值对存储结构。
它通过将键映射到一个唯一的索引位置来存储和检索值。

操作：

  • 查找
  • 添加键值对
  • 删除键值对
  • 遍历哈希表

哈希冲突

哈希冲突是指不同的键映射到了相同的索引位置。
解决哈希冲突的方法有多种，包括：

  • 链地址法（拉链法）
  • 开放地址法
    • 线性探测法
    • 平方探测法
    • 双哈希法

哈希算法

1

树

二叉树

完美二叉树

完美二叉树所有层的节点都被完全填满。

完美二叉树的节点总数为 $2^h - 1$，其中 $h$ 是树的高度。

完全二叉树

完全二叉树所有层的节点都被完全填满， 除了最后一层，且最后一层的节点都靠左填充。

完满二叉树

完满二叉树要求每个节点要么是叶子节点，要么有两个子节点。

平衡二叉树

平衡二叉树中每个节点的左右子树高度差不超过 1。

二叉树遍历

遍历方式：

  • 层序遍历（根节点->左节点->右节点）
  • 前序遍历（根节点->左子树->右子树）
  • 中序遍历（左子树->根节点->右子树）
  • 后序遍历（左子树->右子树->根节点）
层序遍历

层序遍历是一种按层级顺序遍历二叉树的方法。本质上属于广度优先遍历（Breadth-First Traversal），也称广度优先搜索（Breadth-First Search，BFS）。

前序、中序、后序遍历

前序、中序、后序遍历都属于深度优先遍历（Depth-First Traversal），也称深度优先搜索（Depth-First Search，DFS）。

二叉树数组表示

若节点的索引为 i，则它的左节点为$2i + 1$，它的右节点为$2i + 2$, 它的父节点为$(i-1)/2$

二叉搜索树

对于根节点，所有左子树的节点值都小于根节点的值，所有右子树的节点值都大于根节点的值。

操作：

  • 搜索
  • 插入
  • 删除