1.1 什么是数据结构

简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科

1.1.1 基本概念和术语

数据（data）：对客观事物的符号表示，在计算机学科中是指所有能输入到计算机中并被计算机程序处理的符号的总称

数据元素（data element）：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理

数据项（data item）：数据的不可分割的最小单位

数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集

数据结构（data structure）：相互之间存在一种或多种特定关系的数据元素的集合

数据结构的形式定义：

D 是数据元素的有限集，S 是 D 上关系的有限集

Data_Structure = (D, S)

逻辑结构：

存储结构/物理结构：数据结构在计算机中的表示（又称映像）

根据在计算机中的不同表示又分为 顺序映像 和 非顺序映像，由此得到两种不同的存储结构：顺序存储结构 和 链式存储结构

数据类型（data type）：一个值的集合和定义在这个值集上的一组操作的总称

抽象数据类型（abstract data type，简称 ADT）：一个数学模型以及定义在该模型上的一组操作

抽象数据类型格式

ADT 抽象数据类型名 {
  数据对象: <数据对象的定义>
  数据关系: <数据关系的定义>
  基本操作: <基本操作的定义>
} ADT 抽象数据类型名

多形数据类型（polymorphic data type）：其值的成分不确定的数据类型

对特定问题求解步骤的一种描述，是指令的有限序列

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

算法的特性：

好的算法应具备以下目标：

算法效率的度量是通过时间复杂度和空间复杂度来描述的

频度

一个语句的频度是指该语句在算法中被重复执行的次数

T(n) = O(f(n))

加法规则

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

乘法规则

T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))

S(n) = O(f(n))

只分析除输入和程序之外的额外空间

原地工作

指算法所需的辅助空间为常量，即 O(1)