一、数据结构到底是什么

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

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

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

1.逻辑结构

1）定义

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

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

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

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

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

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

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

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

1）定义

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

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

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

2）顺序存储和链式存储

①顺序存储结构

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

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

②链式存储结构

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

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

3）其他存储方式

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

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

抽象数据类型

1.定义

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

例如：C语言中数据类型分为基本类型和构造类型

基本类型：整型、浮点型、字符型等

构造类型：数组、结构、联合、指针、枚举型、自定义类型等

②抽象数据类型（abstract data type，ADT）：是指一个数学模型及定义在该模型上的一组操作。

延伸阅读：

二、散列（哈希）存储结构

就是根据数据元素的关键字通过哈希函数计算出一个数值用做数据元素的存储地址，优点在于查找速度快，只需要给出关键字可立即计算出该数据元素的地址 特点是指存储数据元素不存储数据之间的逻辑关系，只适合进行快速查找和插入的场合。

上一篇

什么是哈希值?

下一篇

算法时间复杂度为O（n!）的是什么算法?