【数据结构】第一章绪论

1.1 什么是数据结构

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

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

数据元素（Data Element）： 数据的基本单位，计算机程序中作为一个整体进行考量和处理。

可由若干数据项(Data Item)组成。数据项是不可分割的最小单位。

数据对象（Data Object）: 是性质相同的数据元素的集合，是数据的子集。

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

这种数据元素之间相互之间的关系称为结构（Structure）。通常有四类基本结构：

（1）集合；（2）线性结构；（3）树形结构；（4）图状结构或网状结构

数据结构形式定义：数据结构是一个二元组 Data Structure = (D,S) 其中： D是数据元素的有限集， S是D上关系的有限集。

逻辑结构：结构定义中的“关系” 描述数据元素之间的逻辑关系。

物理结构：数据结构在计算机中的表示，又称为存储结构。位（bit）。元素（Element）或结点（Node）。数据域（Data Field）

关系：顺序映像和非顺序映像。存储结构：顺序存储结构和链式存储结构

数据类型（Data Type）: 是一个值的集合和定义在这个值集上的一组操作的总称。例如：C 中int,值集位某个区间的整数。定义其上的操作为+/-/*// Mod

按值得不同特性，数据类型分为两类：一是原子类型。（值是不可分割的）。二是结构类型。是由原子类型组成的某种结构。

抽象数据类型（Abstract Data Tpe,简称ADT）: 是指一个数学模型以及定义在该模型上的一组操作。

ADT 表示：（D,S,P） D是数据对象， S是D上的关系集， P是对D的基本操作集。

本书采用的格式定义抽象数据类型：

ADT 抽象数据类型名{

数据对象： <数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

} ADT抽象数据类型名

其中，数据对象和数据关系定义用伪代码，基本操作定义格式为：

基本操作名（参数表）

初始条件：<初始条件描述>

操作结果：<操作结果描述>

书中描述了下类C语言的语法知识

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

时间复杂度：算法中基本操作重复执行的次数是问题规模n 的某个函数f（n）. 记做 T(n) = O(f(n)).

空间复杂度：算法所需的存储空间的量度。 S（n） = O(f(n))

总结：本章是很重要的一章，首先说明了最基本的概念，然后后面章节就是具体的数据结构，和算法分析。