数据结构（一）：什么是数据结构

一、什么是数据结构

1、数据结构的定义

1. 数据：从计算机的角度来看，数据是所有能被输入到计算机中且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式（二进制码的抽象表示？）。
2. 数据元素：数据元素是数据中的一个个体，是数据的基本单位，在计算机中通常作为一个整体来进行考虑和处理。
3. 数据项：一个数据元素可以由多个数据项组成。数据项是具有独立含义的数据最小单位。

数据、数据元素、数据项这三个的关系类似表、元组、属性之间的关系，不过表、元组、属性之间具有确定的关系，而数据、数据元素、数据项之间只有层次关系而没有具体的关系。

1. 数据结构：数据结构是指数据以及数据相互之间的联系，可以看成是相互之间具有某种特定关系的数据元素的集合，因此，可以把数据结构看成是带结构的数据元素的集合。

数据结构包含以下几个方面：

• 数据元素之间的逻辑关系，即数据的逻辑结构。
• 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。
• 施加在该数据上的操作，即数据的运算。

所以数据结构由三个部分组成：逻辑结构、物理结构、运算。

数据的逻辑结构是从逻辑关系上描述数据（主要是相邻关系，比如栈、队列、链表等），它与数据的存储无关，是独立于计算机的。因此，数据结构可以看作从具体问题中抽象出来的数学模型。

数据的存储结构是逻辑结构用计算机语言的实现（逻辑结构在计算机存储中的映像），它是依赖于计算机语言的。

数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。最常用的运算有：检索（查找）、插入、删除、更新、排序等。

对于一种数据结构，其逻辑结构总是唯一的，但它可以对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

2、逻辑结构类型

在不产生混淆的情况下，通常将逻辑结构简称为数据结构。

数据的逻辑结构主要有以下几类：

1. 集合：集合中的元素相互独立，除了同属于一个集合之外，别无其他关系。（集合中的元素不能重复）
2. 线性结构：线性结构中的节点具有一对一的关系，其特点是开始节点和终端节点都是唯一的，除开始节点和终端节点之外，其余节点有且仅有一个前驱，有且仅有一个后继。
3. 树形结构：树形结构中的节点具有一对多的关系，其特点是每个节点最多只有一个前驱，但可以有多个后继，可以有多个终端节点。
4. 图形结构：图形结构中的节点具有多对多的关系，其特点是每个节点的前驱和后继的数量都可以是任意的。

图示

3、存储结构类型

1. 顺序存储方法：把逻辑上相邻的节点存储在物理上相邻的存储单元里，节点之间的逻辑关系由存储单元的邻接关系来体现。

优点：节省存储空间，可以实现节点的随机存取（每个节点对应一个序号，由该序号可直接确定节点的存储地址）

缺点：不便于修改（在对节点进行插入、删除的操作时，可能要移动一系列的节点）。

1. 链式存储方法：该方法不需要逻辑上相邻的节点在物理位置上也相邻，节点之间的逻辑关系由附加的指针字段表示。

优点：便于修改（在进行插入、删除操作时，只需要修改对应节点的指针域，不必移动节点）。

缺点：存储空间利用率较低（有一部分空间用来存储节点之间的逻辑关系了），不能进行随机存取（因为逻辑上相邻的节点在物理位置上不一定相邻）。

1. 索引存储方法：该方法通常在存储节点信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中关键字唯一标识一个节点，地址则是指向该节点的指针。

优点：支持随机访问（因为索引表是顺序存储的，类似于 C语言中的指针数组），具有较高的数据修改运算效率。

缺点：索引存储的方法增加了索引表，降低了存储空间的利用率。

1. 哈希（或散列）存储方法：该方法根据节点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作为该节点的存储地址。

优点：哈希存储方法的优点就是查找数据快，只要给出要查找节点的关键字，就可以立即计算出对应节点的存储地址。

缺点：哈希存储方法只存储节点的数据，不存储节点之间的逻辑关系。所以哈希存储方法一般只适合要求能够快速查找和插入的场合。

上面 4种基本的存储方法，既可以单独使用，也可以组合起来使用。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构，主要根据运算方便和算法的时空要求来决定。

转载自：

数据结构教程（第二版）

李春葆 等 编著

清华大学出版社

ISBN：978-7-302-14229-4