【大总结1】数据结构与传统算法总结

曾经终败给现在 2022-05-08 11:06 276阅读 0赞

# **由于时间和水平有限，肯定有错误或者写得不好的地方** #

# **欢迎在文章下评论指出。** #

涉及语言：

**py3：注重算法本身的知识**

**c/c++：实现基础数据结构和算法**

**java：实现较复杂数据结构**

--------------------

# 一、概述 #

--------------------

[c语言知识体系][c]

[算法体系参考][Link 1]

--------------------

[课上笔记1（复习c、课程概述）][1_c]

[课上笔记2（基本概念、时空复杂度）][2]

[时空复杂度][Link 2]

[浅析P/NP/NPC][P_NP_NPC]

[引入：算法优化][Link 3]

--------------------

提高篇

[基础动态规划][Link 4]

[摔手机：借一道水题打开思路][Link 5]

--------------------

# 二、线性表 #

### 笔记： ###

[课上笔记3（线性表及顺序表示）][3]

[课上笔记5（链表概述）][5]

[课上笔记6（链表选讲、静态链表）][6]

[作业1讲解（最大子数组二维多维）][1]

### 基础代码实现： ###

[顺序存储实现（静/动）][Link 6]

[单链表不带头（标准实现）][Link 7]

[单链表不带头（压缩代码）][Link 8]

[双链表带头][Link 9]

### 应用： ###

[约瑟夫环（顺序、链式、数学）][Link 10]

[线性表表示集合][Link 11]

[线性表表示一元多项式][Link 12]

[链表环相关问题][Link 13]

[链表coding能力练习：归并排序][coding]

[LRU介绍和实现][LRU]

--------------------

提高篇

[链表coding能力练习：相交问题][coding 1]

--------------------

# 三、栈和队列 #

### 笔记： ###

[课上笔记7（栈、队列基础）][7]

### 基础代码实现： ###

[数组实现栈][Link 14]

[链表实现栈][Link 15]

[数组实现队列][Link 16]（易懂实现循环）

[链表实现队列][Link 17]

[双栈][Link 18]

[栈和队列的互相模拟][Link 19]

### 应用： ###

[栈排序][Link 20]

[括号匹配][Link 21]

[表达式求值][Link 22]

[简单迷宫问题][Link 23]

[借汉诺塔理解栈与递归][Link 24]

[手动维护栈实现二叉树三种遍历][Link 25]

[深搜、广搜与栈、队列][Link 26]

### 相关算法： ###

[单调栈][Link 27]

[单调双端队列][Link 28]

--------------------

提高篇

[双端队列优化的背包问题][Link 29]

--------------------

# 四、串 #

### 笔记： ###

[课上笔记8（串基础）][8]

### 基础代码实现： ###

[串的定长表示][Link 30]

[串的堆分配][Link 31]

[为何py整数不会溢出][py]

[c语言文件操作][c 1]

### 相关算法： ###

[一文读懂KMP][KMP]

[一文读懂Manacher][Manacher]

[KMP题集1][KMP_1]

[KMP题集2][KMP_2]

[KMP+DP入门][KMP_DP]

[字符串上的动态规划][Link 32]

[前缀树][Link 33]

[后缀树/后缀数组概述][Link 34]

[AC自动机][AC]

--------------------

# 五、数组和广义表 #

注：题目慢慢添加

### 笔记： ###

[课上笔记9（数组、广义表）][9]

### 部分题目实现： ###

[二维数组基操四连][Link 35]

[数组基本操作三连（1）][1 1]

[数组基本操作三连（2）][Link 35]

[数组基本操作三连（3）][3 1]

[数组基本操作三连（4）][4]

[数组精选操作（5）][5 1]

[数组精选操作（6）][6 1]

### 应用： ###

[2048小游戏实现][2048]

[吃豆人][Link 36]

[贪吃蛇][Link 37]

--------------------

# 六、树 #

### 笔记： ###

[课上笔记10（树和二叉树概述）][10]

[二叉树概述][Link 38]

[课上笔记11（满二叉树、完全二叉树）][11]

[课上笔记12（二叉树存储与遍历）][12]

[课上笔记13（树的存储）][13]

### 基础代码实现： ###

[理解二叉树遍历][Link 25]

[二叉树序列化/反序列化][Link 39]

[先序中序后序两两结合重建二叉树][Link 40]

[先序中序数组推后序数组][Link 41]

[直观打印二叉树][Link 42]

[根据数组建立平衡二叉搜索树][Link 43]

[平衡二叉树的判断][Link 44]

[完全二叉树的判断][Link 45]

[搜索二叉树的判断][Link 46]

[二叉树最长路径][Link 47]

[时间低于O(N)求完全二叉树结点个数][O_N]

### 应用： ###

[二叉搜索树][Link 48]

[堆][Link 49]

[堆应用例题三连][Link 50]

[并查集][Link 51]

[并查集入门题集][Link 52]

[线段树][Link 53]

[树状数组][Link 54]

### 相关算法： ###

[最大搜索子树][Link 55]

[morris遍历 空间O(1)][morris_ _O_1]

--------------------

# 七、图 #

### 笔记： ###

[课上笔记14（图基础）][14]

[课上笔记15（存储、遍历）][15]

## 基础： ##

[最小生成树][Link 56]

[拓扑排序][Link 57]

[最短路][Link 58]

### 相关算法： ###

[迷宫][Link 23]

[棋盘简单深搜广搜][Link 26]

[皇后问题][Link 59]（位运算）

[旅行商问题][Link 60]（认识状态压缩）

--------------------

# 八、动态存储 #

--------------------

# 九、查找 #

### 基础代码实现： ###

[二分及拓展][Link 61]

[二叉搜索树实现][Link 48]

[数组建立二叉搜索树][Link 43]

[自平衡二叉搜索树][Link 62]

[AVL Tree][]

### 相关算法： ###

[HashMap记录的动态规划][HashMap]

[跳表介绍和实现][Link 63]

--------------------

# 十、排序 #

### 基础代码实现： ###

[八种排序][Link 64]

### 相关算法： ###

[快排-荷兰国旗][-]

[快排-前m大元素][-_m]

[归并-求逆序数][- 1]

[桶思想-相邻数最大差值][- 2]

[堆][Link 49]

[堆应用例题三连][Link 50]

[BFPRT][]

[c]: https://blog.csdn.net/hebtu666/article/details/82866168
[Link 1]: https://blog.csdn.net/hebtu666/article/details/81837497
[1_c]: https://blog.csdn.net/hebtu666/article/details/82624070
[2]: https://blog.csdn.net/hebtu666/article/details/82700455
[Link 2]: https://blog.csdn.net/hebtu666/article/details/82463970
[P_NP_NPC]: https://blog.csdn.net/hebtu666/article/details/82465495
[Link 3]: https://blog.csdn.net/hebtu666/article/details/79912328
[Link 4]: https://blog.csdn.net/hebtu666/article/details/81777273
[Link 5]: https://blog.csdn.net/hebtu666/article/details/84789853
[3]: https://blog.csdn.net/hebtu666/article/details/82753068
[5]: https://blog.csdn.net/hebtu666/article/details/82834818
[6]: https://blog.csdn.net/hebtu666/article/details/82893113
[1]: https://blog.csdn.net/hebtu666/article/details/82788866
[Link 6]: https://blog.csdn.net/hebtu666/article/details/82973911
[Link 7]: https://blog.csdn.net/hebtu666/article/details/82980561
[Link 8]: https://blog.csdn.net/hebtu666/article/details/81261043
[Link 9]: https://blog.csdn.net/hebtu666/article/details/82784343
[Link 10]: https://blog.csdn.net/hebtu666/article/details/82980735
[Link 11]: https://blog.csdn.net/hebtu666/article/details/82993158
[Link 12]: https://blog.csdn.net/hebtu666/article/details/82982642
[Link 13]: https://www.cnblogs.com/xudong-bupt/p/3667729.html
[coding]: https://blog.csdn.net/hebtu666/article/details/82984679
[LRU]: https://blog.csdn.net/hebtu666/article/details/89360428
[coding 1]: https://blog.csdn.net/hebtu666/article/details/82995430
[7]: https://blog.csdn.net/hebtu666/article/details/83106543
[Link 14]: https://blog.csdn.net/hebtu666/article/details/81286583
[Link 15]: https://blog.csdn.net/hebtu666/article/details/83025150
[Link 16]: https://blog.csdn.net/hebtu666/article/details/82736862
[Link 17]: https://blog.csdn.net/hebtu666/article/details/82863168
[Link 18]: https://blog.csdn.net/hebtu666/article/details/83011115
[Link 19]: https://blog.csdn.net/hebtu666/article/details/82740895
[Link 20]: https://blog.csdn.net/hebtu666/article/details/82759172
[Link 21]: https://blog.csdn.net/hebtu666/article/details/83035778
[Link 22]: https://blog.csdn.net/hebtu666/article/details/83035552
[Link 23]: https://blog.csdn.net/hebtu666/article/details/83064066
[Link 24]: https://blog.csdn.net/hebtu666/article/details/83047821
[Link 25]: https://blog.csdn.net/hebtu666/article/details/82853988
[Link 26]: https://blog.csdn.net/hebtu666/article/details/81483407
[Link 27]: https://blog.csdn.net/hebtu666/article/details/82717317
[Link 28]: https://blog.csdn.net/hebtu666/article/details/82720880
[Link 29]: https://blog.csdn.net/hebtu666/article/details/83018230
[8]: https://blog.csdn.net/hebtu666/article/details/83831884
[Link 30]: https://blog.csdn.net/hebtu666/article/details/83505987
[Link 31]: https://blog.csdn.net/hebtu666/article/details/83862545
[py]: https://blog.csdn.net/hebtu666/article/details/83538609
[c 1]: https://blog.csdn.net/hebtu666/article/details/85156791
[KMP]: https://blog.csdn.net/hebtu666/article/details/79822446
[Manacher]: https://blog.csdn.net/hebtu666/article/details/79822584
[KMP_1]: https://blog.csdn.net/hebtu666/article/details/82492660
[KMP_2]: https://blog.csdn.net/hebtu666/article/details/82492803
[KMP_DP]: https://blog.csdn.net/hebtu666/article/details/82790653
[Link 32]: https://blog.csdn.net/hebtu666/article/details/82687245
[Link 33]: https://blog.csdn.net/hebtu666/article/details/83141560
[Link 34]: https://blog.csdn.net/hebtu666/article/details/83512671
[AC]: https://blog.csdn.net/hebtu666/article/details/83443391
[9]: https://blog.csdn.net/hebtu666/article/details/83831940
[Link 35]: https://blog.csdn.net/hebtu666/article/details/83381130
[1 1]: https://blog.csdn.net/hebtu666/article/details/90270402
[3 1]: https://blog.csdn.net/hebtu666/article/details/90739305
[4]: https://blog.csdn.net/hebtu666/article/details/90741340
[5 1]: https://blog.csdn.net/hebtu666/article/details/90751832
[6 1]: https://blog.csdn.net/hebtu666/article/details/91524543
[2048]: https://blog.csdn.net/hebtu666/article/details/81663648
[Link 36]: https://blog.csdn.net/hebtu666/article/details/86526655
[Link 37]: https://blog.csdn.net/hebtu666/article/details/83586583
[10]: https://blog.csdn.net/hebtu666/article/details/83900565
[Link 38]: https://blog.csdn.net/hebtu666/article/details/82853617
[11]: https://blog.csdn.net/hebtu666/article/details/84389466
[12]: https://blog.csdn.net/hebtu666/article/details/84390001
[13]: https://blog.csdn.net/hebtu666/article/details/84395716
[Link 39]: https://blog.csdn.net/hebtu666/article/details/84553147
[Link 40]: https://blog.csdn.net/hebtu666/article/details/84322113
[Link 41]: https://blog.csdn.net/hebtu666/article/details/84338555
[Link 42]: https://blog.csdn.net/hebtu666/article/details/83105504
[Link 43]: https://blog.csdn.net/hebtu666/article/details/84556551
[Link 44]: https://blog.csdn.net/hebtu666/article/details/84260028
[Link 45]: https://blog.csdn.net/hebtu666/article/details/84257066
[Link 46]: https://blog.csdn.net/hebtu666/article/details/84259619
[Link 47]: https://blog.csdn.net/hebtu666/article/details/84254502
[O_N]: https://blog.csdn.net/hebtu666/article/details/84289179
[Link 48]: https://blog.csdn.net/hebtu666/article/details/81741034
[Link 49]: https://blog.csdn.net/hebtu666/article/details/81706288
[Link 50]: https://blog.csdn.net/hebtu666/article/details/83380199
[Link 51]: https://blog.csdn.net/hebtu666/article/details/82663647
[Link 52]: https://blog.csdn.net/hebtu666/article/details/82840116
[Link 53]: https://blog.csdn.net/hebtu666/article/details/82691008
[Link 54]: https://blog.csdn.net/hebtu666/article/details/82692564
[Link 55]: https://blog.csdn.net/hebtu666/article/details/84251431
[morris_ _O_1]: https://blog.csdn.net/hebtu666/article/details/83093983
[14]: https://blog.csdn.net/hebtu666/article/details/84502345
[15]: https://blog.csdn.net/hebtu666/article/details/84874125
[Link 56]: https://blog.csdn.net/hebtu666/article/details/87823689
[Link 57]: https://blog.csdn.net/hebtu666/article/details/87823806
[Link 58]: https://blog.csdn.net/hebtu666/article/details/87823902
[Link 59]: https://blog.csdn.net/hebtu666/article/details/84631083
[Link 60]: https://blog.csdn.net/hebtu666/article/details/84988118
[Link 61]: https://blog.csdn.net/hebtu666/article/details/81410301
[Link 62]: https://blog.csdn.net/hebtu666/article/details/84992363
[AVL Tree]: https://blog.csdn.net/hebtu666/article/details/85047648
[HashMap]: https://blog.csdn.net/hebtu666/article/details/83507376
[Link 63]: https://blog.csdn.net/hebtu666/article/details/89370679
[Link 64]: https://blog.csdn.net/hebtu666/article/details/81434236
[-]: https://blog.csdn.net/hebtu666/article/details/81772701
[-_m]: https://blog.csdn.net/hebtu666/article/details/81772978
[- 1]: https://blog.csdn.net/hebtu666/article/details/81773190
[- 2]: https://blog.csdn.net/hebtu666/article/details/91994726
[BFPRT]: https://blog.csdn.net/hebtu666/article/details/83070107