1. 数据结构基本概念

![数据结构]
(/img/datastruct/1_extract/1.png)

1.1 数据

• 信息的载体，被计算机程序识别和处理的符号的集合

1.2 数据元素

• 数据的基本单位，常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。
• 例如一个人的信息

1.3 数据项

• 数据不可分割的最小单位。
• 例如姓名字段

1.4 数据对象

• 性质相同的数据元素的集合，是数据的一个子集。
• 例如所有人的信息

概念	定义	举例
数据	信息的载体，被计算机程序识别和处理的符号的集合	一个人的信息
数据元素	数据的基本单位，常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。	一个人的信息
数据项	数据不可分割的最小单位。	姓名字段
数据对象	性质相同的数据元素的集合，是数据的一个子集。	所有人的信息

1.5 数据结构

• 相互之间存在一种或多种特定关系的数据元素的集合。
• 例如所有人的信息按照年龄排序

1.6 逻辑结构

• 数据对象中数据元素之间的相互关系
• 例如所有人的信息按照年龄排序

1.7 物理结构

• 数据的逻辑结构在计算机中的存储形式
• 例如所有人的信息按照年龄排序，存储在数组中

1.8 数据类型

• 一组性质相同的值的集合及定义在此集合上的一些操作的总称
• 例如整数类型，浮点数类型

1.9 抽象数据类型

• 一个数学模型及定义在该模型上的一组操作
• 例如整数类型，浮点数类型

1.10 算法

• 为解决特定问题而规定的一个有限长的操作序列
• 例如排序算法

1.11 数据类型

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

原子类型	其值不可再分的数据类型
结构类型	其值可再分为若干成分的数据类型

1.12 抽象数据类型

• 一个数学模型及定义在该模型上的一组操作

---

2 数据结构三要素

2.1 逻辑结构

• 数据元素之间的逻辑关系
• 集合、线性、树形、图形

2.2 数据运算

• 增删查改

2.3 物理结构（存储结构）

• 用计算机表示数据元素的逻辑关系
  插入表格：

顺序存储	链式存储	索引存储	散列存储
数组	链表	索引表	散列表
逻辑相邻则物理相邻	逻辑相邻则物理不一定相邻	附加索引表	根据关键字得到存储地址

---

3 算法的基本概念

3.1 啥是算法

• 对特定问题求解步骤的一种描述
• 指令的有限序列
• 每条指令表示一个或多个操作

3.2 算法特性

• 有穷性

  ·执行有限步骤后结束

  ·每一步都可在有限时间内完成

• 确定性

  ·每一步都有确定的含义

  ·对于相同的输入只能得出相同的输出

• 可行性

  ·可以通过已经实现的基本运算执行有限次得出结果

• 输入

  ·有0个或多个输入

• 输出

  ·至少有1个或多个输出

3.3 算法设计的要求

• 正确性

  ·算法能够得出正确的结果

• 可读性

  ·算法要便于阅读、理解和交流

• 健壮性

  ·算法对不合理数据输入有适当的处理能力

• 时间效率高和存储量低

  ·算法执行时间短，占用存储空间少

3.4 算法效率的度量方法

3.4.1 事后统计方法

• 运行时间取决于计算机的硬件、软件环境

3.4.2 事前分析估算方法

• O(1)<O(log_n)<O(n)<O(nlog_n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)
• 时间复杂度
  
• 空间复杂度
  
• 例子：
  

赏

谢谢你请我吃糖果