【王道 · 数据结构】 第一章

章节总览

1.0 开篇_数据结构在学什么

1.1_1 数据结构的基本概念

数据：

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料（二进制的0和1）。

世界上第一台通用计算机ENIAC

数据元素、数据项：
数据元素【元素、记录】是数据的基本单位，一个数据元素可由若干数据项组成。

数据项【字段、域】是构成数据元素的不可分割的最小单位。

如：xx班【数据对象】的每个学生记录【数据元素】由学号、姓名、班级、年龄等【数据项】构成。

数据对象：

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

数据结构：

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

数据结构三要素：

1. 逻辑结构
2. 存储结构
3. 运算

结构关系图：

1.1_2 数据结构的三要素

1. 逻辑关系

1.1 集合结构：

各个元素同属一个集合，无其他关系

1.2 线性结构：

数据元素之间是一对一的关系。

除了第一个元素，所有元素都有唯一前驱;除了最后一个元素，所有元素都有唯一后继

1.3 树形结构：

数据元素之间是—对多的关系

1.4 图状结构：

数据元素之间是多对多的关系

2. 数据的运算--针对于某种逻辑结构，定义基本运算（如对链表的增删改查操作）

3. 数据的物理结构（存储结构）--如何用计算机表示数据元素的逻辑关系?

1.2_1 算法的基本概念

程序=数据结构+算法

算法：

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

1.2_2 算法的时间复杂度

算法时间复杂度—事前预估算法时间开销T(n)与问题规模n的关系，只考虑阶数高的部分如O(n)

1.2_3 算法的空间复杂度

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为O（1）