2022/03/09 Wed 22:10    2022/11/16 Wed 23:36

数据结构再怎么变，主要是通过数组和链表
链表不用顺序实现，用指针实现，在内存中不连续，也即链表将一系列不连续的内存联系起来，将那种碎片化内存进行合理的利用，解决空间的问题。因此链表就允许插入、删除表上的任意位置上的节点，但是不允许随即随存。
数组与链表的区别：
区别：

  1. 链表是链式的存储结构；数组是顺序的存储结构。
  2. 链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
  3. 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难；
  4. 数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
    相同点：
    两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。
    把数据结构抽象化：
    最高层的抽象，数据结构只有两种：数组和链表（顺序存储结构和链式存储结构）。
    队列和栈这两种数据结构既可以使用链表也可以使用数组来实现
  • 用数组来实现：处理扩容和缩容的问题
  • 用链表来实现：需要更多的空间存储节点指针

散列表：通过散列函数把键映映射到一个大的数组中。
对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要空间；线性探查法就需要数组特性，以便连续寻址，省空间，但操作稍微复杂些。

树：
用数组实现就是堆，堆是一个完全二叉树，用数组存储不需要节点指针，操作简单
用链表实现就是常见的树，不一定是完全二叉树。在链表的结构上，又衍生出各种设计：二叉搜索树、平衡二叉树、红黑树、区间树、B树等等
对数据结构的操作,无非遍历 + 访问（增删查改）
如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式，线性的和非线性的。
线性就是 for/while 为代表，非线性就是递归为代表。再具体一步，无非以下两种框架：
数组遍历框架，典型的线性遍历结构：

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 访问 arr[i]
    }
}

二叉树遍历框架，典型的非线性递归遍历结构：

void traverse(TreeNode root) {
    traverse(root.left)
    traverse(root.right)
}

相关的变式：
链表遍历框架，兼具线性和非线性遍历结构：

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 访问 p.val
    }
}

void traverse(ListNode head) {
    // 访问 head.val
    traverse(head.next)
}

二叉树框架又可以具体扩展为 N 叉树的遍历框架：

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child)
}

N 叉树的遍历又可以扩展为图的遍历，因为，图就是好几 N 叉棵树的结合体。你说图是可能出现环的？这个很好办，用个布尔数组 visited 做标记就行了，就不写代码了。

所谓框架，就是说不管增删查改，这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码就行了。
为什么算法总是和数据结构同时出现
数据结构是工具，算法是通过合适的工具解决问题的方法。
拿原始人举例，我们学会了数据结构，就像原始人拥有了石刀，石斧等工具。而根据制造工具的工艺不同，石刀又分尖锐的石刀和锯齿状石刀，前者适合打猎，后者适合切割；就像图这种数据结构通过不同的实现方法（链表、数组），可以表示为邻接表和邻接矩阵，前者适合处理非稠密图，后者适合处理稠密图。原始人想要造一栋房子，就要进行规划，石斧砍树，石刀磨尖角等等；就像我们设计算法，发挥数据结构的特性，去解决实际问题。

算法利用数据结构，可以显式利用，比如说前文单调栈，就是巧妙地直接利用了栈结构先进后出的特性。稍微高级一点的算法设计思路，就是隐式利用数据结构，比如前文讲过的回溯算法、动态规划，以及传说中的的分治算法，都在利用树这种结构来解决问题。

但是，无论怎样利用数据结构，多么高大上的算法，其解法都逃不出第二点中相应的框架，是不是？
最后总结（重要）

对于一个初学算法的人来说，一定要学会从框架上看问题，而不要纠结于细节问题。
啥叫细节问题？比如说 i 到底应该加到 n 还是加到 n - 1 ？这个数组的大小到底应该开 n 还是 n + 1 ？
啥叫从框架上看问题？比如说前文动态规划中凑零钱的问题，如果你看了一眼代码就自动忽略细节问题，直接提取出 N 叉树遍历框架，你的框架思维就到位了。

int coinChange(vector<int>& coins, int amount) {
    if (amount == 0) return 0;
    int ans = INT_MAX;
    for (int coin : coins) {
        // 金额不可达
        if (amount - coin < 0) continue;
        int subProb = coinChange(coins, amount - coin);
        // 子问题无解
        if (subProb == -1) continue;
        ans = min(ans, subProb + 1);
    }
    return ans == INT_MAX ? -1 : ans;
}

/* N 叉树遍历框架 */
int coinChange(vector<int>& coins, int amount) {
    for (int coin : coins)
        coinChange(coins, amount - coin);
}

当然，如果细节出错，你得不到正确的答案，但是只要有框架，你再错也错不到哪去，因为你的方向是对的。
但是，你要是心中没有框架，那么你根本无法解题，给了你答案，你也不会发现这就是个树的遍历问题。
这就是框架的力量，能够保证你在快睡着的时候，依然能写出正确的程序；就算你啥都不会，都能比别人高一个级别。
初学阶段，根本没到纠结细节的地步。细节出错，可以有各种方法查出来，比如到处打 log，没有找不到的 bug。相比之下，别人还束手无策的时候，你已经做出了一个错误的答案；当别人没有框架的指导，被无限细节劝退数据结构的时候，你已经通过框架理解了数据结构的精髓。这不就是一种巨大的成功吗？真的得给你鼓掌。

栈是先进后出的线性表
s.top():获取栈底元素
s.empty():判断栈是否为空
s.push():往栈中添加一个元素
s.pop():栈顶元素的弹出
s.size()：获取栈的长度

队列是先进先出的线性表
q.front():获取队列的队头元素
q.push():在队尾添加一个新的元素进队列中
q.pop()：把我们的队头元素进行弹出
q.empty()：判断我们的队列是否为空
q.size():去求队列中的元素的个数

ToTOP
2018 bear