《Hello 算法》数据结构篇小结精读：逻辑结构与物理结构、数值编码与字符编码核心结论全解析

本文是对《Hello 算法》「数据结构绪论（数据类型与编码）」章节小结（仓库中 俄文版 与 中文版 内容同源）的系统化整理与扩展：从"逻辑结构 vs 物理结构"的分类框架出发，梳理内存寻址、基本数据类型、原码/反码/补码、浮点编码与字符编码的 9 条核心结论，并结合仓库 C 语言源码逐条解答 5 个高频疑问。读完本文，你将掌握数据结构分类的底层依据、计算机数值编码为什么选补码，以及字符编码演进（ASCII → GBK → Unicode → UTF-8/16/32）的来龙去脉，并能用仓库源码印证"静态数据结构""哈希表混合结构"等抽象概念。

一、9 条重点回顾：本章必须带走的知识点

1.1 逻辑结构与物理结构：数据结构的两把"标尺"

数据结构可以从逻辑结构与物理结构两个角度分类：

• 逻辑结构描述数据元素之间的逻辑关系，常见的包括线性、树状、网状等。据此通常可将数据结构划分为线性结构（数组、链表、栈、队列）与非线性结构（树、图、堆）。
• 物理结构描述数据在计算机内存中的存储方式，主要分为连续空间存储（数组）与分散空间存储（链表）。

一个容易被忽略但极其重要的推论是：所有数据结构都是由数组、链表或两者的组合实现的。

仓库源码为这一结论提供了大量"双实现"证据——同一种线性结构，既有基于数组的版本，也有基于链表的版本：

• 栈：基于数组的 array_stack.c 与基于链表的 linkedlist_stack.c；
• 队列：基于数组的 array_queue.c 与基于链表的 linkedlist_queue.c；
• 双向队列：基于数组的 array_deque.c 与基于链表的 linkedlist_deque.c；
• 堆：作为完全二叉树，可以紧凑地"平铺"在数组中，对应 my_heap.c 的堆化实现思路。

而哈希表则是"数组 + 链表"组合的典型：底层是数组，桶内用链表承接冲突元素（详见下文 Q1 的源码佐证）。也就是说，一个看似高级的结构，其物理骨架往往脱胎于最基本的两种存储方式。

1.2 内存与地址：程序访问数据的方式

当程序运行时，数据被存储在计算机内存中。每个内存空间都拥有对应的内存地址，程序正是通过这些内存地址来访问数据的。这解释了为什么"随机访问数组元素"是常数时间操作——给定起始地址与下标，即可通过地址运算直接定位；也解释了物理结构"连续 vs 分散"对访问性能的决定性影响。相关话题在「数组与链表」章节的 ram_and_cache.md 中有更深入的展开（缓存局部性等）。

1.3 基本数据类型：取值范围取决于"占多少空间、怎么表示"

计算机中的基本数据类型包括：

• 整数：byte、short、int、long；
• 浮点数：float、double；
• 字符：char；
• 布尔：bool。

它们的取值范围取决于两件事：占用空间大小与表示方式（即下面要讲的编码规则）。详细讲解见 basic_data_types.md。

1.4 数字的三种编码：原码、反码、补码

原码、反码、补码是计算机中编码数字的三种方法，三者可以相互转换：

• 原码：整数的最高位是符号位（0 为正、1 为负），其余位是数值本身。
• 补码：整数在计算机中实际以补码形式存储。采用补码的根本动机有两条：其一，计算机可以对正数和负数的加法一视同仁，无需为减法操作单独设计特殊的硬件电路；其二，消除了"正零"与"负零"的歧义问题。

1.5 浮点数的编码：用精度换范围

浮点数的编码由 1 位符号位、8 位指数位和 23 位分数位构成（这是 32 位单精度浮点数的位布局）。正因为有指数位，浮点数的取值范围远超整数，但代价是牺牲了精度——尾数位有限，很多小数无法被精确表示。这也是编码原理中"表示方式决定取值范围与精度"的又一体现，详见 number_encoding.md。

1.6 字符编码：从 ASCII 到 Unicode 的统一之路

• ASCII 码是最早出现的英文字符集，长度为 1 字节，共收录 128 个字符。
• GBK 字符集是常用的中文字符集，共收录两万多个汉字。
• Unicode 致力于提供完整的字符集标准，收录世界上各种语言的字符，从根源上解决因编码方式不一致导致的乱码问题。

那么如何用字节去存储 Unicode 码点？这引出具体的编码方法：

• UTF-8 是最受欢迎的 Unicode 编码方法，通用性非常好。它是变长编码，扩展性好，能有效提升存储空间利用效率。
• UTF-16 与 UTF-32 属于等长编码。一个容易被忽略的细节是：编码中文时，UTF-16 占用的空间比 UTF-8 更小；Java、C# 等编程语言默认使用 UTF-16 编码。

完整演进脉络见 character_encoding.md。

二、五问精讲：对重点结论的源码级深挖

Q1：为什么哈希表同时包含线性和非线性数据结构？

答案可以从"底层数组 + 桶内链表（必要时转树）"两层理解。

从逻辑分类上看，哈希表底层是数组；而为了解决哈希冲突，一种经典方案是"链式地址"（后续 hash_collision.md 会专门讲解）：数组中每个桶指向一个链表，当链表长度超过一定阈值时，又可能被转化为树（通常为红黑树，如 Java 等语言标准库中的做法）。

仓库的 C 语言实现 hash_map_chaining.c 就是这条思路最直白的注脚：

/* 链式地址哈希表 */
typedef struct {
    int size;         // 键值对数量
    int capacity;     // 哈希表容量
    double loadThres; // 触发扩容的负载因子阈值
    int extendRatio;  // 扩容倍数
    Node **buckets;   // 桶数组
} HashMapChaining;

结构体 hash_map_chaining.c 中的 Node **buckets 表明：哈希表的主体是一段连续的桶数组（线性、连续空间），而每个桶槽位实际指向一条链表（线性、分散空间）。插入新键值对时直接头插进对应桶的链表中（hash_map_chaining.c）。

因此，从存储角度看，哈希表的底层是数组，其中每个桶槽位可能包含一个值，也可能包含一条链表甚至一棵树——它确实可能同时包含线性数据结构（数组、链表）和非线性数据结构（树）。这个例子也再次印证 1.1 的结论：高级结构由基本结构的组合生长而来。

Q2：char 类型的长度是 1 字节吗？

不一定。char 类型的长度由编程语言采用的编码方法决定：

• 若语言面向 ASCII 风格的单字节字符模型（典型如 C 语言），char 长度为 1 字节；
• 而 Java、JavaScript、TypeScript、C# 等语言采用 UTF-16 编码（用于保存 Unicode 码点），因此它们中 char 类型的长度是 2 字节。

所以"char 是 1 字节"只是特定语言/编码语境下的结论，不能一概而论。这与 1.6 中"UTF-16 是等长编码、常用于语言内建字符类型"的事实互为印证。

Q3：数组实现的数据结构叫"静态数据结构"，是否有歧义？

栈明明支持出栈（pop）、入栈（push）等操作，这些操作显然是"动态"的，为什么还说它是"静态"的？

关键要区分**"数据操作是动态的"与"底层结构长度是否可变"这两个层面。栈确实可以实现动态的数据操作，但底层数据结构本身仍是"静态"的（长度不可变）：尽管基于数组的数据结构可以动态地添加或删除元素，但它的容量是固定的**。一旦数据量超出预分配大小，就必须创建一个新的更大的数组，并将旧数组内容复制到新数组中。

仓库源码 array.c 的 extend() 函数正是这一过程的"裸写"版本：先 malloc 一块更大的连续内存，再把旧数组元素逐一复制进新数组——数组一旦创建，其长度不可改变，所谓"扩容"实为"换一块更大的地皮搬家"。

Q4：构建栈（队列）时明明没指定大小，为何仍归为"静态数据结构"？

在高级编程语言中，我们无须人工指定栈（队列）的初始容量，这个工作由类内部自动完成；同样，扩容操作也是自动实现的。

以 Java 的 ArrayList 为例，其初始容量通常为 10。本仓库的 C 语言版动态列表 my_list.c 给出了同款设计：

MyList *newMyList() {
    MyList *nums = malloc(sizeof(MyList));
    nums->capacity = 10;        // 初始容量 10
    nums->arr = malloc(sizeof(int) * nums->capacity);
    nums->size = 0;
    nums->extendRatio = 2;      // 每次扩容翻倍
    return nums;
}

当 size == capacity 时，add/insert 会触发 extendCapacity：按 extendRatio = 2 分配新容量、复制旧数据、释放旧内存并更新指针（my_list.c）。

可见："自动扩容"只是封装了"创建新数组并复制旧内容"的静态操作，并没有改变"底层是固定容量数组"这一物理事实。因此从物理结构看，它们仍属于"基于数组的（静态）结构"。上述列表的完整逻辑见 my_list.c，延伸阅读可看 list.md 中关于列表（动态数组）的讲解。

Q5：补码转原码为什么也能用"先取反后加 1"？

原码转补码的规则是"先取反后加 1"。若按直觉，补码转原码应是逆运算"先减 1 后取反"，可实际两者都能用"先取反后加 1"完成，这是为什么？

根本原因在于：原码与补码的相互转换，本质是计算"补数"的过程。先给出补数定义：若 $a + b = c$，则称 $a$ 是 $b$ 到 $c$ 的补数，反之也称 $b$ 是 $a$ 到 $c$ 的补数。

以 $n = 4$ 位长度的二进制数 $0010$ 为例。若将其看作原码（暂不考虑符号位），其补码按"先取反后加 1"得到：

$$0010 \rightarrow 1101 \rightarrow 1110$$

观察可知，原码与补码的和为 $0010 + 1110 = 10000$——也就是说，补码 $1110$ 是原码 $0010$ 到 $10000$ 的补数。这意味着"先取反后加 1"本质上是在计算"到 $10000$ 的补数"。

那么补码 $1110$ 到 $10000$ 的补数（即它的原码）是多少？依然可用"先取反后加 1"求得：

$$1110 \rightarrow 0001 \rightarrow 0010$$

换句话说，原码与补码互为对方到 $10000$ 的补数，因此"原码转补码"与"补码转原码"可以共用同一操作（先取反后加 1）。

当然，也可以用逆运算求补码 $1110$ 的原码，即"先减 1 后取反"：

$$1110 \rightarrow 1101 \rightarrow 0010$$

总结来看，"先取反后加 1"与"先减 1 后取反"都是在计算到 $10000$ 的补数，二者等价。再往本质推一层："取反"操作本身求的是到 $1111$ 的补数（因为恒有 原码 + 反码 = 1111）；而在反码基础上再加 1，得到的补码就是到 $10000$ 的补数。

以上推导以 $n = 4$ 为例，但可推广至任意位数的二进制数——这正是"溢出丢弃最高进位"后补码体系能够自洽的原因。

三、小结与延伸阅读

梳理全篇，可以用一条主线串联所有知识点：

1. 分类：逻辑结构（线性/非线性）＋物理结构（连续/分散），且一切结构皆由数组、链表组合而来（Q1 哈希表是绝佳例证）；
2. 硬件：数据存于内存、靠地址访问（连续 vs 分散决定访问方式）；
3. 数值：基本类型的取值范围由占用空间与编码共同决定；整数用补码存储以统一加减、消除 ±0；浮点用指数位换范围、失精度；
4. 文本：字符编码从 ASCII、GBK 走向统一的 Unicode，再以 UTF-8/UTF-16/UTF-32 落地存储（Q2 解释了语言内建 char 的长度差异）；
5. 辨析："静态数据结构"针对物理容量而非操作灵活性（Q3、Q4 用源码印证了"扩容=换数组"的本质）。

若想沿本章继续深入，仓库提供了完整的配套章节：classification_of_data_structure.md（分类总览）、number_encoding.md（整数与浮点编码全推导）、character_encoding.md（字符集与编码对照），以及用于检验掌握程度的 exercises.md。相关源码可对照 C 语言目录 codes/c/ 下 chapter_array_and_linkedlist、chapter_stack_and_queue、chapter_heap、chapter_hashing 等文件夹中的同名实现，逐行验证本文引用的结论。