3.1-数据结构
数据结构
逻辑结构
数据结构揭示数据与元素之间的关系，主要可以分为两类
- 线性：数组、链表、栈、队列、哈希表（一对一），元素之间为一对一的顺序关系
- 非线性数据结构：树、堆、图、哈希表（一对多）
- 树形结构：树，堆，哈希表，元素之间为一对多
- 图，元素之间为多对多
物理结构
算法运行时，正在处理的数据主要存储在内存中，系统通过内存地址来访问目标位置的数据
实际内存的工作机制比较复杂，涉及地址空间、内存管理、缓存机制、虚拟内存和物理内存等概念。
内存是所有程序的共享资源，某个模块被程序占用，通常无法被其它程序同时使用。因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。比如算法所占用的内存不应超过系统剩余空闲内存。如果缺少连续的内存空间，所选数据结构必须能存储在分散的内存空间内。
比如数组和链表的存储方式不同
- 连续空间存储（数组）占用空间比链表小
- 分散空间存储（链表）占用空间比数组大
所有数据结构都是基于数组、链表，或者两者的组合实现的
基本数据类型
基本数据类型是 CPU 可以直接进行运算的类型，主要包括以下几种
- 整数类型：
byte、short、int、long - 浮点数类型：
float、double，表示小数 - 字符类型：
char表示各种语言的字母，标点甚至是表情 - 布尔类型：
bool，表示 是 或者 否
基本数据类型以二进制的形式存储在计算机中。
- 整数类型
byte占用 字节 = 比特 ，可以表示 个数字。 - 整数类型
int占用 字节 = 比特 ，可以表示 个数字。
数字编码
原码、反码和补码
例如 byte 的取值范围是 [-128,127]。
- 原码：我们将数字的二进制表示的最高位视为符号位，其中 0 表示正数，1 表示负数，其余位表示数字的值。
- 反码：正数的反码与其原码相同，负数的反码是对其原码除符号位外的所有位取反。
- 补码：正数的补码与其原码相同，负数的补码是在其反码的基础上加 1。
数字 0 5 -0 -28
原码 0000 0000 0000 0101 1000 0000 1001 1100
反码 0000 0000 0000 0101 1111 1111 1110 0011
补码 0000 0000 0000 0101 0000 0000 1110 0100
有符号位的数字运算时，需要先转换为反码，比如：
1 + (-2)
-> 0000 0001 (原码) + 1000 0010 (原码)
-> 0000 0001 (反码) + 1111 1101 (反码)
-> 1111 1110 (反码)
-> -1
数字零的原码有 +0 和 -0 两种表示方式。这意味着数字零对应两个不同的二进制编码，这可能会带来歧义。比如在条件判断中，如果没有区分正零和负零，则可能会导致判断结果出错。为了避免这类问题，引入补码
数字 -0 -1 ... -127 -128
原码 1000 0000 1000 0001 ... 1111 1111
反码 1111 1111 1111 1110 ... 1000 0000
补码 0000 0000 1111 1111 ... 1000 0001 1000 0000
- byte 类型的取值为
[-128,127]其中-128是一个例外，没有它的补码
浮点数编码
int 和 float 长度相同，都是 4 字节 ，但为什么 float 的取值范围远大于 int ？这非常反直觉，因为按理说 float 需要表示小数，取值范围应该变小才对。
根据 IEEE 754 标准，32-bit 长度的 float 由以下三个部分构成。
- 符号位 ：占 1 位 ，对应 第 31 位。
- 指数位 ：占 8 位 ，对应 第 23 - 30 位。
- 分数位 ：占 23 位 ，对应 0 - 22 位。
值的计算方法为
val = (-1)b31 * 2 (b30 - b23) * 2 x (1.b22...b0)
转换为十进制为
val = (-1)S * 2E-127 * (1+N)
并且指数位 E = 0，E =255 具有特殊含义，用于表示零、无穷大、NaN 等。
- E = 255，分数为 N=0 表示正负无穷
- E = 255，分数位 N !=0 表示 NaN
float 的表示方式包含指数为，因此取值范围远大于 int，表示的最大的正整数约为 3.4*1038，int 类型将所有的 32 bit 用于数字，且为均匀分布，由于指数位存在，值越大，两个数字之间的差值就越大。