【数据结构】数据结构概述
2022/03/13 23:32:30
摘要
- 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
- 数据的存储结构会影响存储空间分配的方便程度和数据运算速度。
- 栈是一种抽象数据类型，只表示逻辑结构。
- 数据中包含若干个数据元素，数据元素中包含若干个数据项。
- 数据结构就是定义如何把现实世界的问题信息化（逻辑结构），如何将信息存进计算机（存储结构），同时还要实现对数据结构的基本操作（运算）。
- 算法的性能问题只有在问题规模足够大时才会暴露出来。
数据结构的三要素
数据的逻辑结构
数据的逻辑结构是指数据元素之间逻辑上的关系。
- 集合
- 线性结构
- 树形结构
- 图状结构/网状结构
数据的存储结构
数据的存储结构是指数据在计算机中的存储方式。包括数据元素的表示和关系的表示。
- 顺序存储
- 链式存储
- 索引存储
- 离散存储
数据的运算
运算的定义是针对逻辑结构的，运算的实现是针对存储结构的。
队列的运算
- 队头元素出队
- 新元素入队
- 输出队列长度
算法
算法的特性
- 有穷性
- 确定性。同样的输入只能得出同样的输出。
- 可行性。算法的每一步都可实现。
- 输入
- 输出
好算法的特性
- 正确性
- 可读性。要无歧义地描述出解决问题的步骤。
- 健壮性。能处理非法数据。
- 高效率与低存储量需求。降低算法执行时间，减少执行过程中所需的最大存储空间。这两者都与问题规模有关。
算法效率的度量
算法中所有语句的频度之和记作 T(n)。
时间复杂度
时间复杂度分析时间开销与问题规模 n 之间的关系。
时间复杂度主要分析 T(n) 的数量级。因此在评判一个算法的时间复杂度时可以只用最大数量级的频度来表示。
例如：f(n) = an^3 + bn^2 + cn 的时间复杂度为 O(n^3)。
计算算法复杂度的方法：
- 忽略顺序执行代码。
- 只挑循环中的一个基本操作分析它的执行次数与n的关系即可。
- 多层循环时只需关注最深层循环的频度。
空间复杂度
空间复杂度分析的是问题规模 n 与所需额外存储空间之间的关系。
算法原地工作指算法所需要的辅助空间为常量（问题规模 n 与所需辅助存储空间无关），即 O(1)。
递归算法的最小空间复杂度等于递归调用的深度 S(n) = O(n)。