01.什么是数据结构？(ADT)

数据结构？(ADT)"/>

01.什么是数据结构？(ADT)

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

程序设计=数据结构+算法

1.1数据

• 数据：描述客观事物的符号。包括：数值类型（整型等）、非数值类型（字符、声音、图像、视频等）。数据是数据元素的集合
  • 例如：人类、禽类
• 数据对象：性质相同的数据元素的集合，是数据的子集。将数据对象简称为数据
• 数据元素：是组成数据的、有一定意义的基本单位。数据元素是数据结构中建立数据模型的着眼点
  • 例如：组成人类的人、禽类的牛、羊等
• 数据项：一个数据元素由若干个数据项组成。数据的最小单位。
  • 例如：眼睛、鼻子等

1.2逻辑结构与物理结构

• 逻辑结构（面向问题）：数据对象中数据元素（结点）之间的相互关系（边）：

  • 集合结构、线性结构（一对一的关系）、树形结构（一对多的层次关系）、图形结构（多对多的关系。

• 物理结构（面向计算机）：指数据的逻辑结构在计算机中的存储形式（将数据及其逻辑关系存储到计算机内存中）

  • 数据的存储结构应正确反映数据元素之间的逻辑关系。
  • 如何存储数据元素之间的逻辑关系？
  • 顺序存储结构：将数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
  • 链式存储结构：将数据元素存放在任意的存储单元里，数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。数据存在哪里不重要，只要有一个指针存放了相应的地址就能找到它。

1.3抽象数据类型（ADT）

• 类型：就是用来说明变量或者表达式的取值范围和所能进行的操作。

• 数据类型：一组性质相同的值的集合及定义在此集合上的一些操作的总称。

• ADT：指一个数学模型及其定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

  • 一个ADT定义了：一个数据对象、数据对象中各元素之间的关系及对数据元素的操作
  • 例如：定义一个point的ADT，它有x、y、z三个整型变量，这样就能很方便的操作一个point数据变量就能知道这一点的坐标了。

• ADT体现了程序设计中问题的分解、抽象和信息隐藏的特性。

  抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立一个计算机能处理的数据模型，并把每个*功能模块**的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。

ADT 抽象数据类型名Data 数据元素之间逻辑关系的定义
Operation操作1初始条件操作结果描述操作2...操作n...
endADT