基础数据结构

#算法/数据结构 #2023/07/30

一、数据结构的分类

数据结构可以从逻辑结构和物理结构两个维度进行分类

即：数据元素之间的逻辑关系是线性的或者非线性的，如

具体分类如下图：

非线性数据结构可以进一步被划分为 树形结构 和 网状结构。

总结：按逻辑结构分类：线性与非线性

线性结构：数组、链表、队列、栈、哈希表，元素存在**一对一**的顺序关系。

非线性结构：

树形结构：树、堆、哈希表，元素存在**一对多**的关系。

网状结构：图，元素存在**多对多**的关系。

在数据结构与算法的设计中，算法所占用的**内存峰值**不应超过 **系统剩余空闲内存**；所以如果运行的程序很多并且缺少大量连续的内存空间，那么所选用的数据结构必须能够存储在离散的内存空间内。相反，可以存储到**连续的内存空间**

「物理结构」 反映了数据在计算机内存中的存储方式 ，如下图：

注意上图中的 节点指针 与 节点值

所有数据结构都是基于数组、链表或二者的组合实现的

基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度的数组）等

基于链表可实现：栈、队列、哈希表、树、堆、图等。

按照数据结构在初始化后，是否可对其长度进行调整，又可以分为：

基本数据类型提供了数据的 内容类型，而 数据结构 提供了数据的 组织方式，如：

// JavaScript 的数组数据结构 可以自由存储各种 【基本数据类型】 和 对象
const array = [0, 0.0, 'a', false];

基本数据类型是 CPU 可以直接进行运算的类型，在算法中直接被使用，下表列举了**各种基本数据类型**** **的占用空间、取值范围和默认值

1、现代计算机 CPU 通常将 1 字节作为 最小寻址内存单元。因此，即使表示布尔量仅需 1 位（0 或 1 ），它在内存中通常被存储为 1 字节。

2、1 bytes = 8 bits , 可以表示 2^8 个不同的数字

1 byte 的取值范围是 [-128,127] 为什么不是 [-128,128]？它内在原因涉及到原码、反码、补码的相关知识

以上总结就是，如下图：

原码最直观，但数字以补码存到计算机中，为什么呢？这是因为原码的 2 个局限性

1、 负数的原码不能直接用于运算，如 1 + (-2) 不应该等于 -1 吗？但使用原码计算为 -3

2、数字零 的原码有 +0 和 -0 两种表示方式，即 正 0 和负 0 的原码不同，但补码相同

这里，再来回答 1 byte 的取值范围是 [-128,127] 为什么不是 [-127,127]？

因为， [-127,127] 区间内，所有整数的源码，反码、及补码都可以相互转化，但是 -128 的补码是 1000 0000 ，与 +0 的补码相同，所以计算机规定 补码1000 0000 没有原码，它代表 -128

总之，-128的补码比较特殊，和 +0 冲突了，计算机做特殊处理。

计算机内部的硬件电路主要是基于加法运算设计的。这是因为加法运算相对于其他运算（比如乘法、除法和减法）来说，硬件实现起来更简单，更容易进行并行化处理，从而提高运算速度；如：

我们可以总结出计算机使用补码的原因：基于补码表示，计算机可以用同样的电路和操作来处理正数和负数的加法，不需要设计特殊的硬件电路来处理减法，并且无需特别处理正负零的歧义问题。这大大简化了硬件设计，并提高了运算效率。

一个违反直觉的事情：int 和 float 长度相同，都是 4 bytes，但 为什么 float 的取值范围远大于 int ？ 这非常反直觉，因为按理说 float 需要表示小数，取值范围应该变小才对

简单来说就是，float 采用了不同的表示方式。如下

[!info] 1、尽管浮点数 float 扩展了取值范围，但其副作用是牺牲了精度 2、双精度 double 也采用类似 float 的表示方法，具体的需要再去查吧，这里点到即可

UTF-8 已成为国际上使用最广泛的 Unicode 编码方法。它是一种可变长的编码
除了 UTF-8 之外，常见的编码方式还包括 UTF-16 和 UTF-32
UTF-16 编码：使用 2 或 4 个字节来表示一个字符
UTF-32 编码：每个字符都使用 4 个字节
从存储空间的角度看
- 使用 UTF-8 表示英文字符非常高效，因为它仅需 1 个字节
- 使用 UTF-16 编码某些非英文字符（例如中文）会更加高效，因为它只需要 2 个字节，而 UTF-8 可能需要 3 个字节
从兼容性的角度看，UTF-8 的通用性最佳，所以许多工具和库都优先支持 UTF-8