0x04 数据结构

0. 数据结构基础

• 算法的特性
  • 有穷性：算法不会产生死循环。
  • 可行性：算法是可以实施的。
  • 输入输出：可以没有输入，但是必须要有输出
  • 确定性：输入同样的数据，返回的结果是相同的
• 算法的度量
  • 事前估算：大O记法
  • 事后统计：成本大，不用
• 物理结构和逻辑结构
  • 物理结构（在内存中存储结构）
    • 顺序结构
    • 链式结构
  • 逻辑结构
    • 1. 集合(相互之间没有关联)
    • 2. 线性(一对一)
    • 1. 树形(一对多)
    • 1. 图(多对多)

         1. 线性表(一对一)

• 顺序表
  • 增删: O(n)，在第n个位置添加元素，需要移动size-n个元素的位置
  • 访问: O(1)，直接用下标
  • 当数据访问较多，增删较少的时候，使用顺序表
• 链表(手写链表)
  • 增删: O(1)，前提是已经找到了
    • 添加节点

  - 删除节点

• 访问:O(n)
• 当数据的访问较少，增删较多时，使用链表
  • 栈（线性表，插入和删除运算限定在某一端）
• 特性：先进后出
  • 队列
• 特性：先进先出

  2. 树和二叉树(一对多)

• 二叉排序树BST的性质
  • 左边的节点小于根节点，右边的节点大于根节点
  • 每个节点最多只有两个子节点
• 节点的计算
  • 满二叉树： 最底层的节点填满的树
    • 求节点的个数 2^n^-1
  • 完全二叉树：只有最底层的右边的缺省的
    • 求最少的节点个数 2^(n-1)^-1+1-> 2^(n-1)^
• 节点的添加
  • 左边的节点小于根节点，右边的节点大于根节点
  • 在某一棵树中添加一个节点，需要比较多少次
• 节点的删除
  • 在某一棵树中删除一个节点，需要寻找多少次
• 节点的遍历
  • 前序遍历：根 - 左 - 右 => 16 12 15 19 25 36

• 中序遍历：左 - 根 - 右 => 12 15 16 19 25 36，中序遍历的是有序树

• 后序遍历：左 - 右 - 根 => 15 12 36 25 19 16

• 层序遍历：16 12 25 15 19 36
  • 平衡二叉树的性质
• 左子树和右子树的高度小于2

3. A* 算法

• A* 算法是什么？
  • A* 算法是一个寻路算法