第二讲数据结构（数据结构的基本概念）

本节目录

一、数据结构基本概念之间的关系思维导图

基本概念和术语？

1. 数据

2. 数据元素

3. 数据项（属性、字段）

4. 数据对象

5. 数据结构

二、 逻辑结构和物理结构（存储结构）

1. 逻辑结构

1) 定义

2) 分类（线性结构和非线性结构）

2. .物理结构（存储结构）

1) 定义

2) 顺序存储和链式存储

3) 其他存储方式

3.数据结构操作

三、数据类型和抽象数据类型

1) 数据类型

2) 抽象数据类型

四、数据类型和抽象数据类型

1) 定义

2) 数据结构和数据类型关系

一、数据结构基本概念之间的思维导图

1、数据：描述客观事物属性的数、字符及所有能被输入到计算机中并被计算机程序识别和处理的符号的集合。

解释：数据不仅包括整形、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。 数据必须具备两个前提：（1）可以输入到计算机中；（2）能被计算机程序处理。对于整型、实型等数值类型，可以进行数值计算；而对于字符数据类型，就需要非数值的处理；而声音、图像、视频等可以通过编码的手段变成字符数据来处理。

2、数据元素：数据元素是组成数据的基本单位，通常称为记录。

解释：比如 畜类 牛、马、羊、鸡、猪、狗等动物当然就是畜类的数据元素。

3、数据项：不可分割的最小单位，具有独立含义。

解释：一个数据元素由若干个数据项组成。

4、数据对象：性质相同的数据元素的集合，是数据的一个子集。

解释：什么叫性质相同呢？是指数据元素具有相同数量和类型的数据项，比如人 这个例子，都有姓名、生日、性别等相同的数据项。 既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性质，在不产生混淆的情况下，我们将数据对象简称为数据。

图（2）数据、数据对象、数据元素、数据项关系图解

5.数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。

解释：数据元素都不是孤立存在的，它们之间存在某种关系，这些数据元素之间的关系称为结构(structure)。在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，这些关系称为结构。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

一、逻辑结构和物理结构（存储结构）

1. 逻辑结构

1) 定义

逻辑结构是指数据对象中数据元素之间相互关系（逻辑关系），即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机存储器的。

2）分类（线性结构和非线性结构）

根据数据元素之间关系的不同特征，通常有下列4类基本结构，复杂程度依次递进。

①集合：结构中的数据元素之间除了同属于一个集合外，没有其他的关系。

②线性结构：线性结构中的数据元素之间是一对一的关系。

③树形结构：树形结构中的数据元素之间是一对多的关系。

④图状结构或网状结构：结构中的元素之间是多对多的关系

2.物理结构（存储结构）

1）定义

数据的物理结构是指数据的逻辑结构在计算机中的存储方式。又称存储结构。

它研究的是数据结构在计算机中的实现方法，包括数据元素的表示和元素之间的关系。

数据元素的存储结构形式主要有两种：顺序存储和链式存储

2）顺序存储和链式存储

①顺序存储结构

是利用数据元素在存储器中的相对位置来表示数据元素之间的逻辑顺序。

顺序存储结构是把数据元素放在地址连续的存储单元中，程序设计中使用数组类型来实现。（逻辑相邻物理相邻）

图（3）顺序结构示意图

②链式存储结构

利用节点中指针来表示数据元素之间的关系。

把数据元素存储在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，程序设计中使用指针类型来实现。（逻辑相邻物理不一定相邻）

图（4）链式结构示意图

3）其他存储方式

索引存储：类似于目录，以后可以联系操作系统的文件系统章节来理解。

图（5）索引存储结构示意图

散列存储：通过关键字直接计算出元素的物理地址

1. 数据结构的操作

即在数据的逻辑结构上已定义的操作,在数据的存储结构上实现。最常用的数据运算：插入、删除、修改、查找、排序

三、数据类型和抽象数据类型

图（6）数据类型分类图

1. 数据类型

数据类型：是一个值的集合以及定义在这个值集上的一组操作。数据类型的分类为：原子类型和结构类型。

解释：为什么要有数据类型：计算机中内存也是有限的，为了提高内存使用效率，不浪费空间，自然是需要设计出数据类型来划定多大数据占多大内存空间，就有了数据类型。

2. 抽象数据类型

抽象数据类型（Abstract Data Type,ADT）是指一个数学模型以及定义在这个模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与它在计算机中的表示和实现无关。

解释：抽象数据类型，泛指除基本数据类型以外的数据类型。

基本数据类型被认做是最基本、不可再划分的数据，一般就是整形、浮点型、以及字符型。抽象数据类型是由若干基本数据类型归并之后形成的一种新的数据类型，这种类型由用户定义，功能操作比基本数据类型更多，一般包括结构体和类。其实说白了，抽象数据类型就是把一些有一定关联的基本数据类型打包，然后当做新的数据类型使用。下图（7）是抽象数据模型标准格式：

图（7）抽象数据类型的标准格式

1. 数据结构和数据类型之间的关系

数据结构是一种值（值=数据元素）的集合（根据数据结构的定义，只是给“值的集合”加了个约束：数据元素相互之间存在一种或多种特定关系，所以可以把数据结构看作一种值的集合），这种值集 定义在值集上的一组操作就是结构类型，而结构类型是数据类型的一种，所以数据结构是一种数据类型。

图（6）数据类型、原子类型、结构类型、数据结构之间的关系

参考文献：

(1) 《数据结构》（刘大有，杨博等编著）

(2) 《算法导论》（托马斯·科尔曼等编著）

本人由作者整理而成，同时参照多本教程以及网络论文，如果有错误的地方，希望读者指出。

,