数据结构形成和发展的背景
目前计算机的应用已不再局限于科学计算，而更多的用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这给程序设计带来了一些新的问题。为了编出一个“好”的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。
数据结构的定义
一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：
- 首先要从具体问题中抽象出一个适当的数学模型
- 然后设计一个解此数学模型的算法
- 最后编写出程序、进行测试、调整直至得到最终解答
寻求数学模型的实质是分析问题，从中提取操作的对象,并找出这些操作对象之间的关系，然后用数学语言加以描述。有些问题的数据模型可以用具体的数学方程等来表示,但更多的实际问题是无法用数学方程来表示的,这就需要从数据人手来分析并得到解决问题的方法。
基本概念和术语
数据(data)
数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。
数据元素(data element)
- 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。例如“树”中的一个棋盘格局，“图”中的一个圆圈都是一个数据元素。
- 数据元素又被称为元素、结点(node)或记录(record)。
数据项(data item )
- 一个数据元素可以由若干个数据项组成，例如一本书的书目信息为一个数据元素，而书目信息中的每一项（书名、作者等）为一个数据项。
- 数据项是数据不可分割的最小单位。
数据结构(data structure)
数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合，我们可以把数据结构看成是带结构的数据元素的集合。
数据结构通常包括以下几个方面：
(1)数据的逻辑结构( logical structure): 由数据元素之间的逻辑关系构成。
(2)数据的存储结构(storage structure):数据元素及其关系在计算机存储器中的存储表示，也称为数据的物理结构( physical structure)。
(3)数据的运算(operation): 施加在该数据上的操作。
逻辑结构
数据的逻辑结构可以采用多种方式表示，常见的有图表和二元组等。
图表表示
逻辑结构的图表表示就是采用表格或者图形直接描述数据的逻辑关系。
二元组表示
二元组是一种通用的逻辑结构表示方法。一个二元组表示为：
B=(D，R)
其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R所组成。其中：
D={ di | 1≤i≤n，n≥0}：数据元素的集合
R={ rj | 1≤j≤m，m≥0}：关系的集合
每个关系的用若干个序偶来表示：
- 序偶<x，y>（x，y∈D）Þ x为第一元素，y为第二元素。
- x为y的前驱元素。
- y为x的后继元素。
- 若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。
序偶<x，y>表示x、y是有向的，序偶(x，y)表示x、y是无向的。
逻辑结构的类型
(1)集合
(2)线性结构
(3)树形结构
(4)图(网)状结构
集合
元素之间关系：无。
特点：数据元素之间除了“属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。
线性结构
元素之间关系：一对一。
特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。
树形结构
元素之间关系：一对多。
特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后续元素；除开始元素外，每个元素有且仅有一个前驱元素。
图形结构
元素之间关系：多对多。
特点：所有元素都可能有多个前驱元素和多个后继元素。
存储结构
数据逻辑结构在计算存储器中的存储表示称为数据的存储结构(也称为映像)，也就是逻辑结构在计算机中的存储实现。当把数据对象存储到计算机中时,通常要求既要存储逻辑结构中的每一个数据元素,又要存储数据元素之间的逻辑关系。
常见的存储结构
顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑关系；
链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑关系。
结论
- 可以用所有高级语言中都有的“数组”类型来描述顺序存储结构
- 以C语言提供的“指针”来描述链式存储结构
写在最后
