数据结构基本概念

数据 对于客观事物的符号表示，所有能输入到计算机中并被计算机程序处理的符号总称

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

数据对象 性质相同的数据集合，是数据的一个子集

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

结构 数据元素之间的关系

常见的数据结构：

• 集合 所有元素同属于同一集合中
• 线性结构 结构中的数据元素之间存在一个对一个的关系
• 树形结构 结构中的数据元素之间存在一个对多个的关系
• 图状结构/网状结构 结构中的数据元素之间存在多个对多个的关系

数据结构的形式定义 一个二元组
$$
Data_Struct=(D,S)
$$
D : 数据元素的有限集 S ： D上关系的有限集

物理结构 数据结构在计算机中的表示 （存储结构）

位（bit） 信息的最小单位

元素（结点） 若干位组合起来形成的一个位串表示数据元素

数据域 数据元素由若干数据项组成，位串中对应于各个数据项的子位串

顺序映像 && 非顺序映像 数据元素之间的关系在计算机中有两种不同的表示方式

顺序存储结构 && 链式存储结构

1. 顺序结构的特点： 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
2. 非顺序结构的特点： 借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系

虚拟存储结构 数据结构在C虚拟处理器中的表示

数据类型 和数据结构密切相关的概念，用来刻画程序操作对象的特征

原子类型 原子类型的值是不可分解的 例如： 基本类型、指针类型和空类型

结构类型 数值是可以分解的，例如 结构体

抽象数据类型 Abstract Data Type 是指一个数学模型以及定义在该模型上的一组操作

• 原子类型 属于原子类型的变量的值是不可分割的
• 固定聚合类型 属于改类型的变量，数据
• 可变聚合类型 构成可变聚合类型的“值”的成分数目不确定