数据与数据结构

一、数据

• 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
• 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录
• 数据项：一个数据元素可以由若干个数据项组成
• 数据对象：是性质相同的数据元素的集合，是数据的子集
• 数据结构：数据元素之间存在的特定关系

数据结构

对于本文档所要讨论的数据结构来说，所有的数据结构都是一种集合类型，类似于 C/C++ 的数组。也就是说每一种数据结构都是某种类型数据元素的集合。而数据对象就是这样一种集合类型的对象，数据元素就是一个数据对象所管理的元素对象，而一个数据元素可能并非一个单一类型，而是一种由多个数据类型组成的结构类型，用于组成这样一个数据元素类型的每个单一小类型就是各个数据项的类型，而每一个数据元素中所包含的单一小对象就是数据项。

具体而言，一个数据结构可以按照人与人之间的关系进行理解，这样的一个关系图就是一个该类型的对象，而这个关系图中的数据元素就是一个个独立的人，而一个人又是由更小的部分组成的，如眼睛、鼻子、耳朵等，这些更小的部分就是组成一个数据元素的数据项。

二、数据结构

数据结构从抽象意义上来说，可以分为各种逻辑结构，从实现角度上来说，可以分为各种物理结构。

一个数据结构以逻辑结构为基准，需要满足其要求实现的接口。而具体的实现方法则各有不同，可以按照任何可能的物理结构进行实现。

1. 逻辑结构

• 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系
• 线性结构：线性结构中的数据元素之间是一对一的关系
• 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系
• 图形结构：图形结构的数据元素是多对多的关系

2. 物理结构

物理结构即数据的逻辑结构在计算机中的存储形式。

数据元素的物理结构形式有两种：顺序结构和链式结构。

• 顺序结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。在 C/C++ 中该物理结构就是数组，无论是内置分配的数组还是动态分配的数组。
• 链式结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。在 C/C++ 中该物理结构通常通过在数据元素中添加“链”这一个数据项来实现。通常链式结构的数据都是动态分配的。

三、数据类型

数据类型是数据结构的延伸概念，是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称。

例如，int是一种数据类型，这种数据类型不仅包括其数据结构，也包括在该类型上的操作。例如int类型可以做算术运算，可以赋值，取地址等等。

对于任意一种数据类型，如果我们对其进行抽象，忽略其具体实现，就可以得到抽象数据类型（ADT），它是一个数学模型以及定义在该模型上的一组操作，与具体实现无关。

后续的抽象数据类型将按照如下格式给出：

ADT 抽象数据类型名

• Data

  数据元素之间逻辑关系的定义

• Operation

  • 操作1

  • 操作2

    ...

  • 操作n