数据结构三要素

AI 摘要

|

数据的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为 线性结构 和 非线性结构 ，线性表是典型的线性结构；集合、树和图是典型的非线性结构。

集合结构

数据元素之间仅 "同属一个集合"

无序、独立

线性结构

数据元素之间只存在一对一的关系

一对一

树形结构

数据元素之间存在一对多的关系

一对多

图状结构

数据元素之间存在多对多的关系

多对多

数据的存储结构

存储结构是指数据结构在计算机中的表示（也称映像），也称 物理结构 。

存储结构 = 数据表示 + 关系表示

逻辑结构在计算机中的物理实现

它包括 数据元素的表示 和 关系的表示 。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。

数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

顺序存储

Sequential Storage

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

✓ 随机存取✓ 空间利用率高

✗ 插入删除困难✗ 可能产生碎片

链式存储

Linked Storage

不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

✓ 插入删除方便✓ 无碎片

✗ 额外指针空间✗ 顺序存取

索引存储

Indexed Storage

在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。

✓ 检索速度快

✗ 额外索引空间✗ 维护索引开销

散列存储

Hash Storage

根据元素的关键字直接计算出该元素的存储地址，
也称哈希（Hash）存储。

✓ 操作速度快

✗ 可能冲突✗ 解决冲突开销

数据的运算

施加在数据上的运算包括 运算的定义 和 实现 。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

运算定义

针对逻辑结构

指出运算的 功能

运算实现

针对存储结构

指出运算的 步骤

常见数据运算

插入

删除

查找

更新

遍历

排序

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