项目说明

本项目旨在重新学习程序设计、数据结构、算法，通过造轮子巩固基础，来一起 AK 知识点吧！这个项目也是一份教学设计大纲，由于国内教材与授课模式的相对落后，本项目参考了大量留学生作业来对一些国内课程的内容进行了改进，内容将会持续更新。

Part1: 程序设计

• 安装vscode，配置 gcc/g++/make/cmak 环境

• 如何编写 Makefile 文件

• 如何使用命令行参数

• 结构体数组的运行

  • 实践项目：编写一个塔防游戏

• 深入学习动态内存分配技术

  • 如何使用数组实现一个哈希表
    • 拉链法
    • 寻址法
  • 动态内存管理技术
    • 实现一个简易的分配算法
    • 实现一个简易的回收算法
    • 实现一个简易的伙伴系统

• 深入学习如何去写递归代码

  • 基于递归实现求和、分治求最值、递归实现链表遍历 (前序与后序)
  • 基于二叉树学习三种顺序的递归 (前中后)、维护多叉树的树上信息 (树链剖分)

Part2: 数据结构

• Linked List

  • 掌握链接结构存储方法：线性链表、实现循环链表、实现双向链表
    • 实践项目：基于链表实现集合的交并差三种运算
    • 实践项目：基于链表实现多项式的加法与乘法运算
    • 实践项目：实现列车模拟小程序
    • 实践项目：实现 Python-List-like 多层嵌套广义表并以递归求解其深度
  • 使用数组模拟链表运行，实现静态链表，并基于此实现内存池机制

• Stack & Queue

  • 基于动态数组实现 Stack、基于链表实现 Stack
  • 基于动态数组实现 Queue、基于链表实现 Queue

• String

  • 如何存储不确定长度的多个串
  • 如何快速查找模式子串
    • 实践项目：实现一个简易终端文本编辑器
    • 实践项目：使用多种不同的算法统计 txt 电子书英文词频

• Tree

  • 掌握树结构存储方法：双亲表示法、孩子表示法、兄弟表示法
    • 多叉树的树上信息维护
    • 略微复杂的树形结构
      • 线段树
      • 平衡树

• Graph

  • 掌握图结构存储方法：邻接矩阵、邻接表法 (链式前向星方法)、十字链表法
  • 掌握两种图遍历模式 (DFS & BFS)，以及拓扑排序
  • 并查集
  • 最小生成树
  • 最短路径
    • 实践项目：实现一个具有导航功能的寻路系统
    • 实践项目：自行爬取小规模网络并做一个 PageRank 分析
  • DAG 图结构具备的性质 (铺垫动态规划部分的内容)

Part3: 算法设计

此处算法设计的学习目标并非 ACM，而是工作面试，因而更加注重代码实现，而非理论分析，不过讲授过程也会引入一些算法竞赛的问题作为课后练习：

• 基本排序算法
  • 归并排序 (二分查找、双指针合并)
  • 快速排序
• 动态规划算法

更新~