数据结构（1）

---

1. 前导

 1. 数据结构学什么：(1) 如何用程序代码把现实世界的问题信息化。 (2) 如何用计算机高效地处理这些信息从而创造价值。

 2. 计算机专业基础四门课之间的关系：

2. 基本概念

 1. 数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
 数据是计算机程序加工的原料，包括：数值数据：整数、实数等。非数值数据：图形、图象、声音、文字等。

 2. 数据元素：数据的基本单位，在程序中作为一个整体进行考虑和处理。
 数据项：构成数据元素的最小单位。

 数据对象：是具有相同性质的数据元素的集合，是数据的一个子集。
 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

3. 数据结构三要素

 1. 数据结构三要素：逻辑结构、物理结构、数据的运算。

3.1 数据的逻辑结构

 1. 集合：数据元素之间没有关系
 2. 线性结构：数据元素之间是一对一的线性关系
 3. 树结构：数据元素之间是一对多的层次关系
 4. 图结构：数据元素之间是多对多的任意关系

3.2 数据的存储结构

 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置表示。

 2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。

 3. 索引存储结构：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是关键字＋地址。

4. 算法

4.1 基本概念

 1. 程序 = 数据结构 + 算法。 算法必须是有穷的，而程序可以是无穷的。

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

 3. 算法的基本特性：(1) 有穷性: 有穷时间内能执行完。 (2) 确定性: 相同输入只会有相同输出。 (3) 可行性: 可以用已有的基本操作实现算法。 (4) 输入：一个算法有零个或多个输入，这些输入取决于某个特定的对象的集合。 (5) 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

 4. 好算法特性：①正确性；②可读性；③健壮性: 能处理一些异常；④高效率与低存储量需求（即时间复杂度和空间复杂度低）。

4.2 算法的时间复杂度

 1. 算法时间复杂度：事前预估算法时间开销 $T(n)$ 与问题规模 $n$ 的关系。如下面这幅图中的例子，为了方便讨论，这里我们把每一条语句的执行时间都看做是一样的，记为一个时间单元。

 2. 我们一般只关心随着问题规模 $n$ 趋于无穷时函数中对函数结果影响最大的项，也就是最高次项。

 3. (1) 加法规则：多项相加，只保留最高阶的项，且系数变为1。
 (2) 乘法规则：多项相乘，都保留。
 常见的时间复杂度如下所示，可以将顺序总结为：常对幂指阶。

4.3 算法的空间复杂度

 空间复杂度是指：空间开销（内存开销）与问题规模 $n$ 之间的关系。处理方法和知识与时间复杂度类似。