数据结构在学什么？

通过程序代码把现实世界的问题信息化

绪论

数据结构的基本概念

数据

• 信息的载体
• 描述客观事物属性的数、字符及所有可能被输入到计算机中并被程序识别和处理和符号集合

数据元素

• 数据的基本单位，作为一个整体进行考虑
• 一个数据元素可包含多个 数据项

数据对象

• 具有相同性质 的数据元素的集合

数据结构

• 相互之间存在 一种或多种 特定 关系 的元素的集合

数据结构的三要素

逻辑结构

数据元素之间的逻辑关系

• 线性结构
  • 数据元素之间是一对一关系
  • 除了第一个元素 所有元素都有 唯一前驱
  • 除了最后一个元素 所有元素 都有 唯一一个后继
• 非线性结构
  • 一对多的关系
  • 树形结构
  • 图结构

存储（物理）结构

如何用计算机表示出数据元素的逻辑关系

• 顺序存储
  • 逻辑相邻的元素 存储在物理位置上野相邻的存储单元中
• 非顺序存储
  • 链式存储
    • 逻辑相邻的物理位置可以不相邻
    • 借助指示元素存储地址的指针 指向下一个元素
  • 索引存储
    • 存储元素信息 还附加建立索引表
    • 索引表中的每一项是 索引项
    • 索引项 一般是 关键字 地址
  • 散列存储
    • 哈希存储
    • 元素关键字直接计算出存储地址

存储结构会影响 存储空间分配 的方便程度

数据的运算

• 运算的定义 针对 逻辑结构
• 运算的实现 针对 存储结构

数据类型、抽象数据类型

数据类型

一个值的集合和定义在此集合上的一组操作的总称

1. 原子类型
   • 其值不可再分
   • bool (与或非)、int（加减乘除）
2. 结构类型
   • 值可以分解为若干成分
   • c语言中 定义的 struct

抽象数据类型 ADT

abstract data type

• 抽象数据组织 及 相关的操作
• 关注数据要素中的 逻辑结构 和 运算

算法的基本概念

程序 = 数据结构 + 算法

算法

• 对特定问题求解步骤的一种描述

算法的5个重要特性

1. 有穷性
   • 执行 有限 步骤后结束，每一步都在有限时间内完成
2. 确定性
   • 每条指令 有 明确意义 无歧义
   • 相同的输入得到相同的输出
3. 可行性
   • 基本运算执行有限次来完成
4. 输入
   • 零个或多个输入
5. 输出
   • 一个或多个输出

好算法应该追求的目标

• 正确性
• 可读写
• 健壮性
  • 非法数据 做出对应的反应和处理
• 高效率与低存储量需求
  • 时间复杂度低
  • 空间复杂度低

算法的时间复杂度和空间复杂度

时间复杂度

事前估算 算法 的 时间开销 T(n) 与 问题规模 n 的关系

计算技巧

• 加法规则：顺序执行 → 复杂度相加，取大的、 系数为1
• 乘法规则：嵌套执行 → 复杂度相乘 、都保留
• 多层循环取 最内层循环 循环次数 和 问题规模的关系

时间复杂度排序必背

口诀： 常 对 幂 指 阶 $$ O(1) < O(log_2n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3) < O(2^n)< O(n!) < O(n^n) $$

复杂度分类

1. 最坏时间复杂度：输入数据 最坏 的情况
2. 平均时间复杂度：考虑所有输入数据都等概率出现的情况
3. 最好时间复杂度：输入数据 最好 的情况

空间复杂度

内存空间开销和问题规模 n 的关系 S(n)

• 无论问题规模怎么变，算法运行所需的内存空间都是固定的常量

  • 算法的空间复杂度为 S(n) = O(1)

• 算法 原地工作

  • 算法所需内存空间为常量

• 注意函数递归调用 带来 的内存开销

  • S(n) = O(n) 空间复杂度 = 递归调用的深度