知识点总结（一）

数据结构的内容

• 数据结构分类：

1. 根据数据元素之间的逻辑关系
   （1）集合结构
   （2）线性结构
   （3）树形结构
   （4）图状结构
2. 根据数据元素之间关系的不同特性
   （1）线性结构：线性表，栈，队列，字符串，广义表和数组
   （2）非线性结构：树和图

• 存储结构：
  数据元素之间的关系在计算机中有两种表示方法：顺序映像和非顺序映象。由此可以得出两种不同的存储结构：
  （1）顺序存储：借助元素在存储器中的相对应位置来表示数据元素之间的逻辑关系。
  （2）链式存储：借助指针表示数据元素之间的逻辑关系。
  归纳总结为：逻辑结构，存储结构，运算集合。

• 算法
  数据结构 + 算法 = 程序

• 算法的特性
  （1）有穷性
  （2）确定性
  （3）可行性
  （4）有输入
  （5）有输出

• 算法评价的标准
  （1）正确性
  （2）可读性
  （3）健壮性（鲁棒性）
  （4）高效率与低存储量需求

• 算法性能分析

• 时间复杂度
  T（n）= O（f(n)）
  算法的执行时间与所有原操作的执行次数之和成正比。
  算法时间复杂度取决于最深循环内包含基本操作的语句的重复执行次数，被称语句重复执行的次数为语句的“频度”。

• 空间复杂度
  S（n）= O（f(n)）
  算法执行期间所需要的存储空间包括3个部分
  （1）算法程序所占的空间
  （2）输入的初始数据所占有的存储空间
  （3）算法执行过程中所需要的额外空间