数据结构基础

1. 基本概念和术语

1)数据

数据（Data）是信息的载体，是可以被计算机识别，存储并加工处理的描述客观事物的信息符号的总称。数据不仅仅包括了整形，浮点数等数值类型，还包括了字符甚至声音，视频，图像等非数值的类型。

2)数据元素

数据元素（Data Element）是描述数据的基本单位，也被称为记录。一个数据元素有若干个数据项组成。

如禽类，鸡鸭都属于禽类的数据元素。

3)数据项

数据项（Data Item）是描述数据的最小单位，其可以分为组合项和原子项：

a)组合项

如果数据元素可以再度分割，则每一个独立处理单元就是数据项，数据元素就是数据项的集合。

b)原子项

如果数据元素不能再度分割，则每一个独立处理的单元就是原子项。

如日期2019年4月25日就是一个组合项，其表示日期，但如果单独拿25日这个数据出来观测，这就是一个原子项，因为其不可以再分割。

4)数据对象

数据对象（Data Object）是性质相同的一类数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。

5)数据结构

数据结构（Data Structures）主要是指数据和关系的集合，数据指的是计算机中需要处理的数据，而关系指的是这些数据相关的前后逻辑，这些逻辑与计算机储存的位置无关，其主要包含以下四大逻辑结构。

2. 四大逻辑结构（Logic Structure）

1) 集合结构

集合结构（Set Structure）中所有数据元素除了同属于一个集合外，并无其他关系。

如图：

2) 线性结构

线性结构（Linear Structure）指的是数据元素之间存在“一对一的关系”

如图:

3) 树形结构

树形结构（Tree Structure）指的是数据元素之间存在“一对多”的层次关系。

如图：

4) 图形结构

图形结构（Graphic Structure，也称：网状结构）指的是数据元素之间存在“多对多的关系”（注：此时的“多对多”中的多表示，至少有一个）

图示：

3.数据类型

1) 数据类型

数据类型（Data Type）是高级程序设计语言中的概念，是数据的取值范围和对数进行操作的总和。数据类型规定了程序中对象的特性。程序中的每一个变量，常量或者表达式都属于一种数据类型。

2) 抽象数据类型

抽象数据类型（Abstract Data Type，ADT）只是一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象，定义了数据的取值范围以及对数据操作的集合。

抽象数据类型的特征是实现与操作分离，从而实现封装。

我们拿《魂斗罗》做比方：我们给予主角打，跳，移动的基本操作，这些操作就可以看作是抽象数据类型，这一组操作就属于一个模型，这组抽象的数据类型可以在《魂斗罗》这个环境中使用。