打牢算法基础，从动手出发！
- 2019 年 11 月 15 日
- 筆記
0.导语
大家好，我是光城。算法在计算机领域的重要性，就不用我多说了，每个人都想要学算法，打牢算法基础，可是不知道如何做，今天我来推荐一波学习思路。
最近我也在打牢算法，于是买了波波老师的慕课网课程《玩转儿数据结构》，由于官方为JAVA版本，但是本人用的C++，因此我将本课程的算法用C++实现了一遍，里面采用了操作符重载，接口使用，继承，组合等面向对象的思想，把我这个仓库学完，C++基础部分也就会了。
笔记仓库地址：
https://github.com/Light-City/algPratice
后面将更新波波老师的其他课程学习笔记。欢迎大家star与fork!
当前仓库共有2万多行代码，59个文件，全部自己写的代码，学习算法没有途径，只待你动手实践！
1.玩转数据结构 从入门到进阶C++版
- 动态数组 学习要点：动态数组的增删改查、时间复杂度、防止复杂度震荡策略。
- 动态数组实现
- 动态数组测试
- 栈和队列
- 队列的公共接口
- 基于底层为动态数组的队列实现
- 基于底层为动态数组的循环队实现
- 基于底层为链表的队列实现
- 队列的测试
- 栈的公共接口
- 基于底层为动态数组的栈实现
- 基于底层为链表的栈实现
- 栈的测试
- LeetCode20题
- 栈 学习要点：使用组合方案来完成栈的底层数据结构为数组，定义栈的入栈与出队策略。
- 队列 学习要点：多种底层实现的效率对比，接口的定义，定义队列的入队与出队策略。
- 链表 学习要点：链表内部节点结构定义、dummyHead使用、时间复杂度分析、链表栈与链表队列实现。z掌握递归的宏观与微观、如何对递归进行测试。
- 链表的实现
- 链表栈实现
- 链表队列实现
- 链表、链表栈、链表队列实现
- LeetCode203题不带与带dummyHead两种实现
- LeetCode203题递归实现
- 求和递归实现
- 二分搜索树 学习要点：掌握二分搜索树的结构、四种遍历方式的递归与非递归，bst树中最大与最小节点，删除节点原则，拓展二分查找法与基于floo、ceil的实现，当bst树退化为链表的时候对应的顺序查找表实现，顺序查找表与二分搜索树的效率对比。
- 补充
- 顺序查找表实现
- 二分查找法实现
- 基于floor与ceil的二分查找法实现
- 二分搜索树实现
- 二分搜索树测试
- 集合与映射
- 映射接口
- 基于底层为二分搜索树的映射
- 基于底层为链表的映射
- LeetCode804问题
- 拓展
- 基于底层为顺序查找表的映射
- 集合接口
- 基于底层为二分搜索树的集合
- 基于底层为链表的集合
- LeetCode804问题
- 拓展
- 基于底层为顺序查找表的集合
- 集合 学习要点：集合接口定义、二分搜索树与链表集合的效率对比。
- 映射 学习要点：映射接口定义、二分搜索树与链表映射的效率对比。学会什么时候用映射，什么时候用集合。
- 优先队列和堆 学习要点：堆的sift up与sift down、heapify、堆与优先队列的关系、如何使用STL的大顶堆与小顶堆、如何使用自己的优先队列解题。
- 基于动态数组的大顶堆实现
- 基于底层为大顶堆的优先队列实现
- 大顶堆与优先队列测试
- 使用C++ STL的优先队列解LeetCode347题
- 使用我们自己的优先队列解LeetCode347题
- 线段树 学习要点：掌握线段树的概念与应用，经典应用区间更新查询等，学会使用动态数组作为线段树的底层数据结构，掌握开辟多大空间存储。掌握其不是完全二叉树也不是满二叉树，但是平衡二叉树,依然可以用数组表示,看做满二叉树,后面不存在的节点在数组中用空来表示即可。
- 基于动态数组的线段树实现
- 线段树测试
- LeetCode303题
- LeetCode307题
- 字典树 学习要点：掌握字典树节点定义，学会使用自己的字典树解题。
- 字典树的实现
- LeetCode211题
- LeetCode677题
- 并查集 学习要点：quickfind、基于树高度优化的并查集、基于树的大小(只是当前父亲节点+孩子节点总数)优化、基于rank(树的深度)的优化、路径压缩1、路径压缩2。
- 基于动态数组的并查集六种实现
- 并查集测试
- 平衡树AVL 学习要点：左旋转、右旋转、平衡因子维护等。
- AVL实现
- AVL测试
- 红黑树 学习要点：红黑树节点颜色标记、左旋转、右旋转、颜色翻转、插入节点颜色调整。
- 红黑树实现
- 红黑树测试
- 哈希表 学习要点：哈希表动态扩容、哈希函数定义等。
- 简单的哈希表
- 简单的哈希表测试
- 素数哈希函数的哈希表
- 素数哈希函数的哈希表测试
