数据结构发展背景：为了分析待处理的对象以及各处理对象之间存在的关系。
计算机解决具体问题的粗略步骤：
- 从具体问题抽象出一个数学模型
- 设计一个解此数学模型的算法
- 编出程序，进行测试、调整直至得到最终解答
寻求数学模型的实质是分析问题，从中提取出操作的对象，并找出操作对象之间含有的关系，然后用数学的语言加以描述
数据结构的简单定义：
- 数据结构是一门研究【非数值计算的程序设计问题】中计算机的操作对象以及它们之间的关系和操作等的学科。
- 在计算机科学中“数据结构”不仅仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。
研究范畴：
基本概念和术语
data
对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
data element
数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时可由若干数据项组成。
data item
数据的不可分割的最小单位。
data object
性质相同的data element的集合，是数据的一个子集。
data structure
- 简单解释：相互之间存在一种或者多种特定关系的数据元素的集合。
- 在任何问题中，数据元素都不是孤立存在的，而是它们之间存在着某种关系，这种数据元素相互之间的关系称为 structure ，根据data element 相互之间关系的不同特性，通常有4类基本结构：
- 集合：结构中数据元素之间除了同属一个集合的关系外，无其他关系。
- 线性结构：data element存在一对一的关系。
- 树形结构：data element存在一对多的关系。
- 图状结构或网状结构：data element存在多对多的关系。
- 形式定义：一个二元组
- Data Structure=(D,S)
D是数据元素的有限集，S是D上关系的有限集。
关系描述的是data element之间的逻辑关系，又称为数据的逻辑结构。- 数据 在计算机中的表示（映像）称为数据的物理结构，又称存储结构。包括【数据元素的表示】和【关系的表示】。
- 计算机中表示信息最小单位的是bit，可以用一个由若干bit组合起来形成的一个位串表示一个data element，通常称这个位串为element或node。
- data field：当data element由若干数据项组成时，位串中对应于各个数据项的子位串称为data field。
- 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像、非顺序映像
对应两种不同的存储结构：顺序存储结构、链式存储结构
- 顺序映像的特点：借助element在存储器中的相对位置来表示数据元素之间的逻辑关系。
- 非顺序映像的特点：借助指示元素存储地址的pointer表示数据元素之间的逻辑关系。
任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储（物理）结构。
- 虚拟存储结构：data structure在某虚拟处理器中的表示。
data type
- 最早出现在高级程序语言中，用以刻画（程序）操作对象的特性的一个和data structure密切相关的一个概念。
某种意义上可以把data structure看成“一组结构具有相同结构的值”，则data type 可以看成由一种data structure和定义在其上的一组操作组成。
- 是一个值的集合和定义在这个值集上的一组操作的总称。
- 按照值的不同特性，高级程序语言中的data type可以分为两类：
- 原子类型（非结构）：值不可分解
- 结构类型：若干成分按照某种结构组成的，可分解，且成分可以是结构的也可以是非结构的。
- 引入data type的目的：从硬件角度看，是作为解释计算机内存中信息含义的一种手段；从使用data type的用户来看，是为了实现信息的隐蔽，将一切用户不需要了解的细节都封装在类型中。
Abstract Data Type
- 指一个数学模型和定义在该模型上的一组操作。
- 其定义仅取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。“抽象”的意义在于数据类型的数学抽象特性。
- 范畴更广：不局限于固有数据类型，还包括用户在设计软件系统时自己定义的数据类型。
近代程序设计方法学指出，为了提高软件的复用率，一个软件系统的框架应建立在数据之上，而不是建立在操作之上。
即构成软件系统的每一个相对独立的模块上定义一组数据和施于这些数据的一组操作，模块内部给出这些数据的表示及其操作细节，而外部使用的只是抽象的数据和抽象的操作。
所定义的数据类型的抽象层次越高，含有该数据类型的软件的复用程度就越高。
一个含有抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。- 按值的不同特性可将ADT分为3种类型：
- atomic data type：变量的值不可分解，不常见。
- fixed-aggregate data type：值由确定的数目的成分按某种结构组成。
- variable-aggregate date type：和前者比较，值的成分的数目不确定。
后两者简称 结构类型。- 形式定义：一个三元组
- Abstract Data Type=(D,S,P)
D是数据对象，S是D上的关系集，P是对D的基本操作集。
- ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
数据操作：<数据操作的定义>
}ADT 抽象数据类型名
- 其中数据对象和数据关系的定义用伪代码描述，基本操作的定义格式为：
基本操作名（参数表）
初始条件：<初始条件描述>
操作结果：<操作结果描述>- 基本操作有两种参数：
i. 赋值参数【提供输入值】
ii. 引用参数（&打头）【提供输入值并返回操作结果】- 初始条件描述了操作执行之前数据结构和参数应该满足的条件，如果不满足，则操作失败并返回相应出错信息。
- 操作结果说明了操作正常完成之后，data structure的变化状况和返回结果。若初始条件为空，则省略。
polymorphic data type
- 指其值成分不确定的数据类型。
- 不论元素有何种特性，element间关系相同，基本操作也相同。从ADT的角度看，具有相同的数学抽象特性，故称为多形数据类型。需要借助面向对象的程序设计语言实现。
