算法的框架思维

算法的框架思维

从十大排序算法解题思路中我们可以抽取一些共同的属性，有从整体到细节再到整体的分治，自顶向下的递归，自底向上从抽象到具体的迭代等框架思维是通用的，不只是学习数据结构和算法，学习其他任何知识都是高效的。

一、数据结构的种类

在我认为数据结构的存储方式只有两种：数组和链表，数组是顺序存储，查找快，增删较复杂，需要扩容，而链表是链式存储，查找慢，增删简单，不需要扩容。有可能好多人会问还有哈希表、栈队列堆树图等各种数据结构呢？我们看待一个问题得研究它的源头，这些都是在链表、数组或者链表+数组上的特殊 *** 作罢了。

比如队列栈数据结构可以用链表或者数组实现，哈希表的底层实现就是数组+链表，树用数组实现就是堆，比如前面我们介绍过的堆排序，就是在数组上进行 *** 作的，用链表实现的树也有红黑树、B树等。我们都知道图有两种表示，邻接表就是一种链表，而邻接矩阵是用二维数组表示。

综上所述，数据结构的种类有很多，甚至你也可以发明自己的数据结构，但底层实现一定是数组、链表或者两者的组合。

二、数据结构的基本 *** 作

对于任何数据结构，其基本 *** 作⽆⾮遍历 + 访问，再具体⼀点就是：增删查改。

如何遍历 + 访问？我们仍然从最⾼层来看，各种数据结构的遍历 + 访问⽆⾮两种形式：线性的和⾮线性的。

线性就是 for/while迭代为代表，⾮线性就是递归为代表。

⾸先要明确的是，数据结构是⼯具，算法是通过合适的⼯具解决特定问题的⽅法。也就是说，学习算法之前，最起码得了解那些常⽤的数据结构，了解它们的特性和缺陷。

三、数据结构的基本框架

二叉树的框架

```Java
class TreeNode {
            int val;
            TreeNode left, right;
        }
        void traverse(TreeNode root) {
            // 前序遍历代码位置
            traverse(root.left);
            // 中序遍历代码位置
            traverse(root.right);
            // 后序遍历代码位置
        }
```

单链表的框架节点减少一个就可以了，至于数组的框架简单的循环就可以解决。

刷题可以先刷二叉树，因为⼆叉树是最容易培养框架思维的，⽽且⼤部分算法技巧，本质上都是树的遍历问题。