数据: 所有能输入到计算机中且能被计算机处理的符号的总称。

数据元素: 是数据的基本单位，表示数据集合中的一一个个体。

数据项: 数据元素中有独立含义的最小单位。

2021-12-07-15-48-54.png

数据结构

数据结构：相互之间存在一定关系的数据元素的集合。(数据、数据之间的关系)

  1. 逻辑结构
  2. 存储结构
  3. 运算

逻辑结构是存储结构的抽象表示，而存储结构是逻辑结构在计算机内的表示形式。

逻辑结构

数据的逻辑结构: 指数据元素之间的逻辑关系，是从实际问题抽象出的数学模型。

根据数据元素之间逻辑关系的不同，数据结构分为三种:

  1. 线性结构（一对一）
  2. 树结构（一对多）
  3. 图（多对多）
    2021-12-07-15-51-09.png

    存储结构

数据的存储结构: 指数据元素及其关系在计算机中的存储表示或实现，也称为物理结构。

其基本形式有两种:

  1. 顺序存储结构
  2. 链式存储结构

顺序存储结构

使用一组连续的内存单元依次存放数据元素，数据元素在内存中的物理存储次序与它们的逻辑次序相同。

序列A=（12，23，44，33，65），对应的顺序存储结构如下图所示：
2021-12-07-16-06-24.png

链式存储结构

使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素之间的逻辑关系用指针来表示。

序列A=（12，23，44，33，65），对应的链式存储结构如下图所示：
2021-12-07-16-07-39.png

在链式存储结构中，我们除了存储元素的数值以外，还要再存储元素之间的关系，用指针来存储，需要为指针再额外开辟空间。

运算

对数据的操作：每种数据结构都需要一组对其数据元素实现特定功能的操作（运算、处理、算法）。通常会包含一些基本操作，此外根据自身特点，还有一些特定操作。

基本操作如初始化、判断是否为空、存取、统计元素个数、遍历、插入、查找、排序等等。

数据类型与抽象数据类型

数据类型：一个值的集合和定义在这个值集上的一组操作的总称。
值的集合（整型、浮点型），操作（加、减、乘、除）

数据类型，定义了数据的取值，此外，对集合上的运算也实现了，它是一个比较具体的概念。

而在定义数据结构时，并不关注数据具体的类型和操作的实现过程，可以看成是一个比较抽象的概念。
2021-12-07-16-35-08.png

抽象数据类型（abstract data type, ADT）：一个数学模型以及定义在该模型上的一组操作。
抽象数据类型 = 逻辑结构 + 抽象运算

使用ADT描述数据结构，可以将数据及其操作的定义与实现相分离。
2021-12-07-16-49-09.png

声明抽象数据类型包括ADT名称定义、数据及其关系定义和操作集合：
ADT Complex

  1. {
  2.  D={real, imag | real,imag均为实数}  //复数由两个实数构成
  3.  R={<real, imag> | real是复数的实部，imag是复数的虚部}
  4.  Complex(real, imag)                 //构造一个复数
  5.  Complex add(Complex c)             //加法，返回相加后的复数
  6.  Complex sub(Complex c)             //减法，返回相减后的复数
  7. }

每种抽象数据类型描述一种数据结构的逻辑特性和操作集合，与其储存结构与实现无关。
image.png