文章目录

1. 知识总览
2. 一、基础概念
3. 二、数据结构的三要素
   • 2.1 逻辑结构
   • 2.2 物理结构（存储结构）
     • 2.2.1 顺序存储
     • 2.2.2 链式存储
     • 2.2.3 索引存储
     • 2.2.4 散列存储（哈希存储）
     • 2.2.5 小结
   • 2.3 数据的运算

知识总览

图来源b站王道。

一、基础概念

数据

数据是指可以输入计算机并被计算机识别和处理的符号集合。

信息的载体

数据元素是数据的基本单位，一个数据元素可由多个数据项组成。

数据元素

数据项构成数据元素的最小单位。

例如：一个人可以看作是一个数据元素，人有眼睛、鼻子、嘴巴和耳朵等部分，这些部分组成了人的这个数据元素。

数据项

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

数据结构

数据类型是指具有相同性质的数据元素的集合，它是数据的一个子集。

数据对象

抽象数据类型（ADT）是一种值的集合和定义在此集合上的一组操作的总称。它分为原子类型和结构类型两种：

• 原子类型：值不可再分的数据类型，例如 bool 类型可以取 true 或 false。
• 结构类型：值可以分解成若干成分的数据类型。

数据类型

抽象数据类型（ADT）是指抽象数据组织及与之相关的操作。它包括数据和操作两部分，但不关心具体实现。

二、数据结构的三要素

2.1 逻辑结构

各个元素同属于一个集合，别无其他关系。

数据元素之间是一对一的关系。除第一个元素外，所有元素都有唯一的前驱；除了最后一个元素，所有元素都有唯一后继。

数据元素之间的关系是一对多的结构。

网状结构中，数据元素之间存在多对多的关系。

2.2 物理结构（存储结构）

如何用存储结构表示数据元素的逻辑关系？接下来先探讨线性结构的数据元素的逻辑关系如何用存储结构表示。

2.2.1 顺序存储

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

2.2.2 链式存储

逻辑上相邻的元素在物理位置上可以不相邻，通过指针表示元素之间的逻辑关系。

2.2.3 索引存储

除了存储信息外，还建立附加的索引表。索引表中的每项称为索引项，一般形式为（关键字，地址）。

2.2.4 散列存储（哈希存储）

根据元素的关键字直接计算该元素的存储地址。

2.2.5 小结

1. 如果采用顺序存储，则各个元素在物理上必须是连续的；如果采用非顺序存储，则各个元素在物理上可以是离散的。
2. 数据的存储结构会影响存储空间的分配方便程度。
3. 数据的存储结构也会影响对数据运算的速度。

2.3 数据的运算

运算的定义针对逻辑结构，指出运算的功能；而算法则指出了运算的具体操作步骤。

抽象数据类型

集合

线性结构

树形结构

图状结构

顺序存储

连续的

存储结构

运算的实现是针对存储结构