DSA 目录

• 链表

  • 单向链表

    • 基本操作

      复制已有链表

      归并排序（自身版，和另一链表版）

      查找（有序、无序版）

      去重

      头插法、尾插法建表

      反转

      单节点插入、删除

  • 双向链表

    • 基本操作

      复制已有链表

      排序（归并、插入、选择）

      查找（有序、无序版）

      去重（有序、无序版）

      单节点插入、删除

• 栈

  • 基本操作

    扩容、缩容

    压栈、出栈、取栈顶

    求规模、判断是否为空

    找特定元素

  • 应用

    1. 进制转换

    2. 括号匹配

    3. 栈混洗

    4. 中缀表达式求值

    5. RPN转换

    6. 搜索回溯：n皇后问题

• 队列

  • 版本

    • 利用双向链表

    • 利用数组

    • 环状数组

  • 基本操作

    扩容、缩容

    出队、入队、取队首、取队尾

    求规模、判断是否为空

• 树

  • 二叉树

    • 基本操作

      先序中序后序递归版和迭代版

      层序遍历

      中序遍历时的直接后继

      插入左右孩子节点

      插入左右树

      删除节点及其子树

      分离子树

      树的重构

        前序+中序
        
        中序+后序
        
        （前序+后序）*真二叉树
      

  • 二叉搜索树 BST

    • 基本操作

      插入、删除节点

      查找（特定节点、最大最小节点）

  • 平衡二叉树之AVL树

    • 基本操作

      插入节点

      旋转（LL,RR,LR,RL）

      删除节点

  • 堆

    • 基本操作

      根据已有序列建堆

      插入、删除特定元素

      删除堆顶

  • 哈夫曼树

    • 基本操作

      建树

  • 并查集

    • 基本操作

      查找所属集合（普通版、优化版）

      集合求并（普通版、优化版）

• 图

  • 版本

    • 邻接矩阵版

    • 邻接表版

  • 基本操作

    建图

    遍历（BFS,DFS）