一、架构梳理

• 线性（1:1)

  • 线性表

    • 顺序存储 –> arr

    • 链式存储 –> 指针 （有头，无头）

      有头是指有一个不存数据的头，始终作为这个链表的起点。

      会更加简单，无头的话，更改首部节点会麻烦。

      头节点不仅可以作为起点，还可以作为存储信息的仓库，因为头节点只有*next是必须的。

      • 单链表

        • 循环
        • 不循环

      • 双向链表

        lib四个版本，第一个最基础完善，第二个改成了变长结构体，第三个在第二个的基础上封装了函数指针，第四个在第二个的基础上隐藏了数据结构，只暴露接口。

        学到这里可以去读一下内核有关list的实现，主要都是宏和内联函数。

        • 循环
        • 不循环

  • 栈

  • 队列

    练习：

    1. 表达式计算

    2. 球钟算法
       三个栈，1h，5min，1min。27个球，过了多久队列里又是1到27的顺序。

• 树状（1:N）

  递归。递归转非递归。

  • 深度：层数

  • 度：子树的个数

  • 叶子：边缘节点

  • 孩子：与父节点对应

  • 兄弟：相同父节点

  • 堂兄弟：相同爷节点

  • 二叉树：

    • 满二叉树：深度为k且节点为2^k-1的二叉树
    • 完全二叉树：一颗二叉树，只有倒数两层可以存在不满两个孩子的节点，且单个孩子时只能是左孩子

  • 存储：

    • 顺序：直观，但是浪费空间
      满二叉树：父节点n，左孩子2n，右孩子2n+1
    • 链式：灵活，空间利用率高

  • 遍历

    先加中，或者，中加后，都可以逆推出树。先加后不行。

    • 按行
    • 先序（根，左，右）
    • 中序（左，根，右）
    • 后序（左，右，根）

  • 平衡：

    有很多种条件判定。

    这棵树的左右子树个数差值为1。

  • 广义表

    ( root ( left ) ( right) )，进行嵌套。

  • 搜索树

    空间换时间，查找是**o(1)**。

    课后作业：词频统计

• 图（N:M)