什么是数据结构？

描述非数值计算问题的数学模型往往不只是常规的数学方程，而是诸如表、树、图之类的数据结构。换句话说，数据结构研究 非数值计算的程序设计问题，主要围绕数据对象、数据对象之间的关系和数据对象之间的操作展开。

术语

数据相关

数据

用以描述或量化实体或概念的符号，是个广泛的定义。

数据项

数据元素的实例，代表某个具体数据类型的其中一个组成部分。

1. 可以类比于组成数据库中记录的列(field)
2. 是数据的不可分割的最小单元

数据元素

数据的基本单位，是待解决问题的整体抽象，包括数据、数据间的关系、数据间的操作等。

1. 可以类比于数据库中的记录(record)

数据对象

性质相同的数据元素的集合，是数据的一个子集。

1. 可以类比于数据库中的表 (table)。

结构相关

数据结构

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

结构类型

数据元素之间的关系。通常分为下列4类基本结构：

1. 集合:数据元素之间除了同属一个集合外，无其他关系。
2. 线性结构：数据元素中存在一对一的关系
3. 树形结构：数据元素之间存在一对多的关系
4. 图形结构（网状结构）：数据元素之间存在多对多的关系。

存储结构

数据结构在计算机中的表示称为数据的物理结构或存储结构。

1. 数据元素之间的存储结构关系表示
   1. 顺序映像——对应顺序存储结构,借助元素在存储中的相对位置来寻址。
   2. 非顺序映像——对应链式、哈希等存储结构，借助算法或元素存储地址的指针来寻址。
2. 数据类型:由一个值域和定义在该值域上的一组操作构成。按照值的不同特性分类：
   1. 原子类型：原子类型的值不可分割，是基本类型。
   2. 结构类型：
      1. 固定聚合类型：值由可列举数目的成分按照某种结构组成。
      2. 可变聚合类型：与固定聚合集合类型相比，成分的数量不确定，如可变长数组。

算法相关

算法基本特征

对特定问题求解步骤的描述，满足5个基本特性：；

1. 有穷性：又穷的步骤，单个步骤的执行时间也是有穷的。
2. 确定性：每一条指令执行的输出唯一，无二义性
3. 输入：有零个或多个输入
4. 输出：有零个或多个输出
5. 可行性：在有穷性和确定性的前提下，确定的输入可以得到确定的输出。

算法需要满足的标准

1. 正确性：针对具体的问题和需求，可以无歧义性的描述输入、输出和加工处理的过程，并总是能够得到期望的结果。
2. 可读性：算法主要是为了人的阅读与理解，其次才是机器的执行。
3. 健壮性：当输入非法时，算法也能进行适当的处理，而不会产生无法预期的结果。
4. 高效率与低存储要求：
   1. 效率是指算法执行的时间，时间短的效率高；
   2. 存储量只算法过程中所申请的最大存储空间的要求。存储量又可以分为：
      1. 内存：堆栈上的内存分配属于此类
      2. 外存：如将数据写入磁盘

算法的时间度量

1. 算法是由控制结构（顺序、条件、循环）和原操作构成，
2. 算法时间快慢取决于两者的综合效果，将算法的原操作重复执行的次数作为算法快慢的量。
3. 其次和该算法中涉及到的数据量规模也紧密相关。

时间复杂度&渐近时间复杂度&平均时间复杂度

1. 表示随着问题规模n的增大，算法执行时间的增长率和n的增长速率的比率关系。
2. 渐近时间复杂度就是在时间复杂度的基础上，只关心对比率影响最大的部分，而忽略次要影响的部分。
3. 时间复杂度在无特殊说明的情况下，均指在最坏情况下的时间复杂度，而不是平均时间复杂度。
4. 平均时间复杂度也很重要，在输入具有一定的要求或规律时，平均算法时间复杂度更可以更准确的反映算法的性能。

空间复杂度

程序执行时，需要存储数据本身的空间大小，可能还需要一些辅助信息所占的空间大小。

1. 额外空间相对于输入来说是常数，与问题规模n无关，则称算法为原地工作
2. 如果额外空间依赖于特定的输入，则均按照最坏情况来分析

复杂度性能排序

从快到慢依次排序

1. 常数阶O(1)
2. 对数阶O(logN)
3. 线性阶O(n)
4. 线性对数阶O(nlogN)
5. 平方阶O(n²)
6. 立方阶O(n³)
7. K次方阶O(n^k)
8. 指数阶(2^n)

其他同类文章

• 数据结构 · 算法-2.4
• 数据结构 · 算法-2.3
• 数据结构 · 05-双向链表实现
• 数据结构 · 04-静态链表实现
• 数据结构 · 算法-2.2