书: https://pan.baidu.com/s/1xhc2t938Uhd6HLI6pHjlVg?pwd=77ya
笔记如下：
一、数据结构与算法基础
- 指针与内存管理
C语言实现算法的核心是指针操作（如链表节点struct Node *next），需手动管理内存（malloc/free）。 - 递归与迭代转换
递归代码简洁但栈开销大（如斐波那契数列），尾递归可优化为迭代（如快速排序的尾递归消除）。 - 时间复杂度实战
实际编码中，常数因子影响显著（如循环展开优化），大O分析需结合硬件特性。
二、核心数据结构实现
- 动态数组（Vector）
通过realloc扩容（通常2倍策略），插入均摊O(1)，需处理扩容失败。 - 链表（Linked List）
哑节点（Dummy Node）简化边界操作（如头节点删除），双向链表支持O(1)尾部插入。 - 哈希表（Hash Table）
链地址法实现：hash(key)%size确定桶位置，负载因子>0.75时扩容。 - 二叉搜索树（BST）
递归插入/删除，最坏退化为链表（O(n)），需平衡策略（如AVL树）。
三、经典算法与优化
- 排序算法对比
- 插入排序对小数据量高效（局部有序场景）。
- 快速排序分区优化：三数取中法避免最坏O(n²)。
- 堆排序实现
数组模拟完全二叉树，sift_down操作建堆（O(n)），排序过程O(n log n)。 - 字符串匹配
暴力匹配（O(mn)） vs. KMP预处理部分匹配表（O(m+n)）。
四、高级算法设计
- 图算法C实现
- 邻接表存储（指针数组+链表），DFS/BFS用递归或队列/栈。
- Dijkstra算法优先队列优化（需自定义最小堆）。
- 动态规划示例
最长公共子序列（LCS）：二维数组填表，空间优化至O(n)。 - 回溯框架
八皇后问题的递归回溯：剪枝条件（列、对角线冲突检测）。
五、工程实践要点
- 防御性编程
检查输入指针非空（assert(p != NULL)），预分配内存避免中间失败。 - 内存池优化
频繁分配小对象时（如链表节点），自定义内存池减少malloc开销。 - 多线程安全
全局数据结构（如哈希表）需加锁（pthread_mutex_t），或采用无锁设计（CAS）。
六、性能调优技巧
- 缓存友好代码
顺序访问数组（空间局部性），避免链表随机跳转。 - 内联函数
static inline减少函数调用开销（如交换元素swap）。 - 位运算优化
用x & (x-1)判断2的幂，移位替代乘除（需处理符号位）。
七、扩展与兼容性
- C99/C11特性
- 变长数组（VLA）谨慎使用（栈溢出风险）。
stdint.h明确类型（int32_t替代int）提升可移植性。