1.1 什么是数据结构
1.1.1 数据结构的定义
数据（data）是描述客观事物的数和字符的集合。从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。数据的基本单位是数据元素（data element）。
数据项（data item）是具有独立含义的数据最小单位，也称为字段或域。
注：一个数据元素可以由若干个数据项组成。
数据对象（data object）是指性质相同的数据元素的集合，它是数据的一个子集。
数据结构（data structure）是指所有数据元素以及数据元素之间的关系，可以看做是相互之间存在着某种特定关系的数据元素的集合。即 数据结构 = 数据 + 结构。
数据结构通常包括以下几个方面：
1. 逻辑结构：由数据元素之间的逻辑关系构成。
2. 存储结构：数据元素及其关系在计算机存储中的表示，也称为数据的物理结构。
3. 运算：施加在该数据上的操作。
1.1.2 逻辑结构
数据的逻辑结构是从数据元素的逻辑关系上描述数据的。数据的逻辑关系与数据的存储无关，是独立于计算机的。
数据结构中元素关系主要是指相邻关系或邻接关系。
1. 逻辑结构的表示
（1）图表。就是表格，没什么好说的。
（2）二元组。
二元组是一种通用的逻辑结构表示方法。
一个二元组表示为：B=(D, R)，其中B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R所组成。
每个关系的用若干个序偶来表示：
序偶
序偶<x,y>表示x,y是有向的，序偶(x,y)表示x,y是无向的。
2. 逻辑结构的类型
（1）集合
元素之间关系：无
特点：数据元素之间除了“属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。
（2）线性结构
元素之间关系：一对一
特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。
（3）树形结构
元素之间关系：一对多
特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后续元素；除开始元素外，每个元素有且仅有一个前驱元素。
（4）图形结构
元素之间关系：多对多
特点：所有元素都可能有多个前驱元素和多个后继元素。
京公网安备 11010502036488号