数据结构与编码基础知识
数据结构与编码基础知识
本文将介绍数据结构、基本数据类型、数字编码以及字符编码等基础知识，帮助读者建立对计算机数据处理的基本认知。
数据结构分类
数据结构可以从两个维度进行划分：逻辑结构和物理结构。
逻辑结构：线性与非线性
逻辑结构揭示了数据元素之间的逻辑关系。数据可以线性排列，也可以呈现更复杂的层次或网络关系。
- 线性结构：数据呈一对一顺序关系。常见结构包括数组、链表、栈、队列、哈希表。
- 非线性结构：数据呈一对多或多对多关系，分为树形结构（如树、堆、哈希表）和网状结构（如图）。
物理结构：连续与分散
物理结构描述了数据在计算机内存中的存储方式。内存由单元格（内存空间）组成，每个单元格通过内存地址访问。
- 连续空间存储：数据存储在连续内存块中，常见于数组。
- 分散空间存储：数据存储在非连续内存块中，通过指针连接，常见于链表。
数据结构的实现方式
数据结构可以通过基于数组或链表的方式实现。
- 基于数组的实现：栈、队列、哈希表、树、堆、图、矩阵、张量。初始化后长度固定，但可通过重新分配内存实现一定动态性。
- 基于链表的实现：栈、队列、哈希表、树、堆、图。支持动态长度调整，适合在运行时需要频繁修改长度的场景。
数据结构选择依据
选择数据结构时需要权衡性能与内存效率。
- 连续存储（如数组）：适合需要快速访问的数据结构，但对内存连续性要求高。
- 分散存储（如链表）：适合需要频繁插入和删除操作的数据结构，内存利用率更高。
数据结构往往基于数组和链表的组合实现。如哈希表结合数组（存储槽位）和链表（处理冲突）。
基本数据类型
基本数据类型是CPU直接运算的数据类型，表示数据的基本形式。包括整数、浮点数、字符和布尔类型。
- 整数类型：byte、short、int、long，表示整数。
- 浮点数类型：float、double，表示小数。
- 字符类型：char，表示字母、标点符号及其他字符。
- 布尔类型：bool，表示“是/否”判断。
所有基本数据类型以二进制形式存储，一个二进制位（bit）是计算的最小单位。一个字节（byte）由8个比特（bit）组成（绝大多数现代操作系统遵循此规则）。基本数据类型取值范围取决于其占用的空间大小。
数字编码
原码、反码与补码
- 原码：二进制表示中，最高位为符号位（0表示正数，1表示负数），其余位表示数值。
- 反码：正数的反码与原码相同，负数的反码为原码符号位不变，其余位按位取反。
- 补码：正数的补码与原码相同，负数的补码为其反码加1。
补码解决了原码和反码中“正零”和“负零”带来的歧义问题，通过将负数运算转化为加法运算，简化硬件设计，支持的负数范围比正数多一个。
浮点数编码
根据IEEE 754标准，32位浮点数float由以下三部分组成：
- 符号位（1位）：正数或负数。
- 指数位（8位）：数值的指数部分。
- 分数位（23位）：有效数字部分。
整数与浮点数区别
- 存储空间：int和float都占用4字节，但表示范围和精度不同。int使用所有比特表示均匀分布整数，float使用部分比特表示指数位，扩展范围但降低精度。
- 适用场景：整数类型适用于精确计算，如计数或索引操作；浮点数类型适用于需要表示小数或范围极大数值。
字符编码
字符编码通过“字符集”将字符与二进制数一一对应，实现二进制数到字符的转换。
ASCII字符集
ASCII是最早的字符集，使用7位二进制表示，共支持128个字符。包含英文大小写字母、数字、标点符号及控制字符。EASCII扩展到8位，可表示256个字符。不同地区的EASCII字符集后128个字符定义不同，以适应本地语言需求。
GBK字符集
GB2312（1980年发布）解决了汉字表示问题，支持6763个汉字，但无法覆盖罕见字和繁体字。GBK在GB2312基础上扩展，支持21886个汉字。ASCII字符使用1字节，汉字使用2字节。
Unicode字符集
Unicode统一字符集，支持全球语言和符号，可容纳100多万个字符。通过统一的“码点”为每个字符分配编号。解决了多语言环境乱码问题，消除了不同字符集之间的兼容性障碍。
UTF-8编码
UTF-8是Unicode的一种编码方式，使用1至4字节表示一个字符。根据字符复杂性调整字节数，具备高效性和兼容性。
- 规则：1字节：ASCII字符（最高位为0）。多字节：起始字节高位以1标识字节长度，其余位用于编码字符码点。后续字节以10开头用于填充字符码点。
- 优点：向下兼容ASCII，适合处理历史遗留文本。多字节的起始位和校验位设计便于错误检测。
其他编码方式还包括UTF-16（2或4字节表示字符）和UTF-32（固定使用4字节）。