数据结构三要素

逻辑结构

数据元素之间的逻辑关系，从逻辑关系上描述数据，叫做数据的逻辑结构。

与数据的存储（物理）结构无关，是独立于计算机的。

可以分为：

• 线性结构
• 非线性结构

线性表是典型的线性结构，衍生出的栈、队列、串、数组、广义表也都是线性结构；

非线性结构主要有：集合、树（一般树、二叉树）、图（有向图、无向图）

特别注意：

• 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
• 线性结构：结构中的数据元素之间只存在一对一的关系。
• 树形结构：结构中的数据元素之间存在一对多的关系。
• 图状结构和网状结构：结构中的数据元素之间存在多对多的关系。

存储（物理）结构

数据结构在计算机中的表示（映像）。包括数据元素的表示和关系的表示。

存储结构是逻辑结构用计算机语言实现的，依赖于计算机语言。

可以分为：

• 顺序存储
• 链式存储
• 索引存储
• 散列（Hash）存储

注意：存储和存取的概念不一样

顺序存储

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

优点：

• 可以实现随机存取
• 元素占用最少的存储空间

缺点：

• 只能使用相邻的一整块存储单元，依赖于物理结构相邻；
• 容易产生外部碎片

什么是内外部碎片？

参考资料：https://blog.csdn.net/qq_22238021/article/details/80209062

• 外部碎片：还没有分配出去（不属于任何进程），但是由于大小而无法分配给申请内存空间的新进程的内存空闲块。
• 内部碎片：已经被分配出去（能明确指出属于哪个进程）的内存空间大于请求所需的内存空间，不能被利用的内存空间就是内部碎片。

链式存储

与顺序存储不同，链式存储不要求逻辑上相邻的元素在物理位置上也相邻。

借助指示元素存储地址的指针表示元素之间的逻辑关系。

优点：

• 不会出现碎片现象
• 充分利用所有存储单元

缺点：

• 除了存储元素外，还需要额外存储指针，会占用额外的存储空间（结合数据库索引学习）。
• 链式存储，只能实现顺序存取，不能实现随机存取（指针的遍历）

索引存储

存放数据元素和元素间关系的存储方式，在存储元素信息的同时，还需要建立附加的索引表。

索引表的每一项称为索引项，索引项的一般形式是：<关键字，地址>

优点：

• 检索快（就好比字典有了目录，查询就很快了）

缺点：

• 增加了索引表，占用较多的存储空间（典型的空间换时间策略）
• 增加、删除数据时，需要对应修改索引表，花费更多时间。

散列（Hash）存储

根据元素的关键字直接通过散列（Hash）函数计算出元素的存储地址。

优点：

• 检索快，添加、删除元素结点操作快（获取元素地址直接，整体时间就少了）

缺点：

• 非常依赖于散列函数
• 会出现散列冲突（主要依赖与散列函数，散列函数不好就很容易出现散列冲突）
• 出现散列冲突时，解决冲突就会增加时间和空间上的开销

数据的运算

数据上的运算包括：运算的定义 、运算的实现

• 运算的定义：针对逻辑结构，指出运算的功能
• 原酸的实现：针对存储结构，指出运算的具体操作步骤

线性表既可以用顺序存储方式实现，也可以用链式存储方式实现。