data-structure-overview | CouriourC Blog

数据结构的基本概念

graph LR

Center(数据结构)
Data(数据)
DataElm(数据元素)
DataElmItem(数据项)
DataObj(数据对象)
DataStruct(数据结构)
DataType(数据类型)
ADT(抽象数据类型)

LogicStruct(逻辑结构)
PhysicStruct(物理结构)
Opeartor(数据运算)

Center --- 基本概念
基本概念 --- Data
基本概念 --- DataElm --- DataElmItem
基本概念 --- DataObj --- DataStruct
基本概念 --- DataType --- ADT

Center --- 三要素
三要素 --- LogicStruct
三要素 --- PhysicStruct
三要素 --- Opeartor

基本概念

数据元素 是数据的 基本单位
数据项 是 数据元素 不可分割的 最小单位
数据结构 是 相互之间 存在一种或多种特定关系的数据元素集合
数据对象 是具有相同性质的数据元素的集合，是数据的一个子集。

三要素

逻辑结构
1. 集合：各个元素属于同一个集合，没有其他关系。
2. 线性结构：元素之间是 一对一 的关系，除了第一个元素之外都有唯一的前驱。
3. 树形结构：元素之间是 一对多 的关系
4. 图状结构（网状结构）
物理结构（存储结构）
1. 顺序结构：各个数据元素在物理上必须是连续的。
2. 链式存储：不要求逻辑上相邻的元素也相邻
3. 索引存储
4. 散列存储
数据的存储结构会影响数据的方便程度
数据运算
逻辑结构
- 线性结构
  1. 一般线性表
  2. 受限线性表
  1. 栈
  2. 队列
  3. 线性表推广
- 非线性结构
  1. 集合
  2. 树形结构
  1. 一般树
  2. 二叉树
  3. 图状结构
  1. 有向图
  2. 无向图
物理结构
- 顺序结构
  - 优点
    1. 可以实现随机存取
    2. 每个元素占有最少的存储空间
  - 缺点
    1. 只能使用相邻的一整块存储单元，可能产生较多的存储碎片
- 链式存储
  - 优点
    1. 不会出现碎片现象，能充分利用所有的存储单元
  - 缺点
    1. 每个元素因存储指针而占有额外的存储空间
    2. 只能实现顺序读取
- 索引存储
  - 优点
    1. 检索速度很快
  - 缺点
    1. 附加的索引表额外占用存储空间
- 散列存储
  - 优点
    1. 检索，增加和删除节点都很快
    2. 缺点
    1. 若是散列函数不好，则可能出现哈希冲突，存储单元冲突会增加时间开销和空间开销

算法的基本概念

算法时间复杂度

加法规则

T(n) = T_{1}(n) + T_{2}(n) \\ = O(f(n) +g(n)) \\ = O(max(fn(n),g(n)))

乘法规则
$T(n) = T_{1}(n) * T_{2}(n) \\ = O(f(n) * g(n))$
🍨 也就是数量级叠加，常对幂指阶

时间复杂度分类

最坏时间复杂度：最坏的情况下，一般考察这个
平均时间复杂度：所有输入示例的等概率出现的情况下，算法的期望运行时间。
~~最好时间复杂度~~：没啥用

一些结论

顺序执行代码只会影响常数项，可以忽略
只需要挑循环中的一个 基本操作 分析他的执行次数与 $n$ 的关系

如果有多层循环只需要关注 最深层 循环了几次

void find (int flag[],int n) {
    for (int i = 0l i < n; i++){
        if (flag[i] == n) {
            break; // 找到后跳出循环
        }
    }   
}

空间复杂度

略