数据结构

数据结构基础

数据结构是指相互之间存在一种或多种特定关系的数据元素集合。

与数据结构有关的基本概念术语：

• 数据

• 数据元素

• 数据对象

• 数据类型

• 抽象数据类型

• 数据结构

数据结构的逻辑结构分为集合、线性、层次和 网状四种。

数据结构的存储结构分为顺序 和非顺序 两种。

在线性结构、树形结构和图型结构中，数据元素之间分别存在着一对一、一对多和多对多联系。

抽象数据类型（Abstract Data Type）

• 数据类型

  • 数据对象集

  • 数据集合相关联的操作集

• 抽象：描述数据类型的方法不依赖于具体实现

  • 与存放数据的机器无关

  • 与数据存储的物理结构无关

  • 与实现操作的算法和编程语言均无关

复杂度

• 空间复杂度S(n)——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

  • 时间复杂度T(n)——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度。 if-else结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大。