1. 数据元素与数据结构

1.1 逻辑结构与存储结构

用于描述数据元素之间的关系（一对一）（一对多）（多对多），一种逻辑结构可以用多种物理结构来实现。物理结构影响逻辑结构上的各种操作复杂度。
存储结构：描述实际存放数据元素的物理结构

1.2 算法与复杂度

• 算法的特性：有穷、确定、可行

• 算法的评价标准：正确、可读、健壮、高效

• 时间复杂度: 给定输入规模n，在最坏的情况下要多少时间一定做完.

• 空间复杂度：给定输入规模n，在最坏的情况下要多少额外的空间一定做完。

1.3 线性表的顺序存储和链式存储

• 顺序存储：
  • 结点中自身信息域，没有任何关联的信息域，存储密度大，存储空间利用率高
  • 支持随机存取
  • 插入和删除要移动大量的元素来维护存储结构
• 链式存储
  • 结点中不仅存放了自身信息域，还有关联的信息域，存储密度小、空间利用率低
  • 不支持随机存取、只能顺序存取
  • 插入和删除方便灵活，不必移动结点只需修改结点中的关联指针即可。

1.4 栈与队列

• 栈的特点：

  • 后进先出 （LIFO）
  • 受限制的线性表只允许从表的一端操作，这端称为栈顶，另一端称为栈底。
  • 压入元素（push）：往栈顶新增一个元素，新元素成为新栈顶。
  • 弹出元素 （pop）：移除栈顶元素，原栈顶元素下一元素成为新栈顶元素或成为空栈。

• 队列

  • 先进先出（FIFO）
  • 入队（enqueue）：往队尾新增一个元素，新元素成为新队尾。
  • 出队（dequeue）：移除队首元素，下一个元素成为新队首或者列变成空。

• 栈的应用：括号匹配

• 队列应用：循环队列