数据结构的序章。

数据结构的两种组织方式

名称逻辑结构存储结构
定义数据元素之间的逻辑关系数据结构在计算机中的表示
特征抽象的具体的

逻辑结构

  • 集合结构：元素同属于一个集合，元素之间无关系
  • 线性结构：元素之间存在一对一的关系
  • 树形结构：元素之间存在一种一对多的层次关系
  • 图形结构：元素之间存在多对多的关系

存储结构

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

主要学习前两种

顺序存储链式存储
优点可以实现随机存取、每个元素占用最少的空间充分利用所有存储单元，不会出现碎片现象
缺点只能使用整块的存储单元，会产出较多碎片需要额外的存储空间存放下一节点的指针、只能实现顺序存取

算法

算法是对特定问题求解步骤的描述。

算法的特点：有穷、确定、可行、具有输入输出

算法的时间复杂度

时间复杂度是所有语句的频度（运行次数）之和，即 T(n) = O(f(n))

n是问题规模，f(n) 是问题规模n的函数。

O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

算法的空间复杂度

S(n)指的是算法运行过程中使用的辅助空间的大小。