基本資料型別以二進位制的形式儲存在計算機中。一個二進位制位即為 1 位元。在絕大多數現代作業系統中， 1 位元組（byte）由 8 位元（bit）組成。 基本資料型別的取值範圍取決於其佔用的空間大小。下面以 Java 為例。 ‧ 整數型別 byte 佔用 1 位元組 = 8 位元，可以表示 28 個數字。 ‧ 整數型別 int 佔用 4 位元組 = 32 位元，可以表示 232 個數字。 表 3‑1 列舉了 整數 byte 1 位元組 −27 (−128) 27 − 1 (127) 0 short 2 位元組 −215 215 − 1 0 int 4 位元組 −231 231 − 1 0 第 3 章 資料結構 www.hello‑algo.com 55 型別 符號 佔用空間 最小值 最大值 預設值 long 8 位元組 −263 263 − 1 0 浮點數 float 4 位元組 1.175 × × 10−38 3.403 × 1038 0.0f double 8 位元組 2.225 × 10−308 1.798 × 10308 0.0 字元 char 2 位元組 0 216 − 1 0 布林 bool 1 位元組 false true false 請注意，表 3‑1 針對的是 Java 的基本資料型別的情況。每種程式語言都有各自的資料型別定義，它們的佔用 空間、取值範圍和預設值可能會有所不同。

会了解我的意思。我 期盼写出一本读起来很顺又绝对不会让你误解意思的中文计算机书。还有些名词在某些场 合使用中文而在某些场合使用原文，例如Class（类别）和Object（对象）和Menu（菜 单），为的也是使上下文阅读起来舒服一些。这些文字的使用都肇基于我个人对文字的 认知以及习惯，如果与您的风格不符，深感抱歉。我已尽力在一个处处需要英文名词的 领域中写一本尽可能阅读顺畅的中文技术书籍。 CMyWinApp CWinApp CWinApp CWinThread CWinThread CCmdTarget CCmdTarget 但是，MFC 之中用来处理消息的C++ 类别，并不呈单鞭发展。作为application framework 的重要架构之一的document/view，也具有处理消息的能力（你现在可能还不清楚什么是 document/view，没有关系）。因此，消息藉以攀爬的路线应该有横流的机会： 消息如果是从子类别流向父类别（纵向流动），那么事情再简单不过，整个Message Map 消息映射表已规划出十分明确的路线。但是正如上一节一开始我说的，MFC 之中用来处 理消息的C++ 类别并不呈单鞭发展，作为application framework 的重要架构之一的 document/view，也具有处理消息的能力（你现在可能还不清楚什么是document/view，没 有关系）；因此，消息应该有横向流动的机会。MFC

1/msvc2017/lib/cmake/Qt5/Qt5Config.cmake ，那 么请你设置变量 Qt5_DIR 为 D:/Qt5.12.1/msvc2017/lib/cmake/Qt5 。有三种设置方法： • (1) 单次有效。在 configure 阶段，可以从命令行设置（注意要加引号）： • cmake -B build -DQt5_DIR=”D:/Qt5.12.1/msvc2017/lib/cmake/Qt5” 1/lib/cmake/Qt5/Qt5Config.cmake ，那么请你设 置变量 Qt5_DIR 为 /opt/Qt5.12.1/lib/cmake/Qt5 。有三种设置方法： • (1) 单次有效。在 configure 阶段，可以从命令行设置： • cmake -B build -DQt5_DIR=”/opt/Qt5.12.1/lib/cmake/Qt5” • (2) 全局启用。修改你的 单项目有效。直接在你自己项目的 CMakeLists.txt 最开头写一行： • set(Qt5_DIR ”/opt/Qt5.12.1/lib/cmake/Qt5”) # 一定要加在最前面！ 三种方案利弊分析 • 单次有效（通过命令行）最安全，小彭老师高度推荐。 • 全局有效（添加环境变量）可能影响以后其他项目。比如你 A 项目依赖 Qt5.12.1 ，你设置了环 境变量 Qt5_DIR=/opt/Qt5.12

刚刚说过 CUDA 的优势在于对 C++ 的 完全支持。所以 __global__ 修饰的核函 数自然也是可以为模板函数的。 • 调用模板时一样可以用自动参数类型推导 ，如有手动指定的模板参数（单尖括号） 请放在三重尖括号的前面。 进一步：核函数可以接受函子（ functor ），实现函数式编程 • 不过要注意三点： 1. 这里的 Func 不可以是 Func const & ，那样会 （ Streaming Multiprocessors ）与板块（ block ） • GPU 是由多个流式多处理器（ SM ）组成的。每个 SM 可以处理一个或多个板块。 • SM 又由多个流式单处理器（ SP ）组成。每个 SP 可以处理一个或多个线程。 • 每个 SM 都有自己的一块共享内存（ shared memory ），他的性质类似于 CPU 中的缓 存——和主存相比很小，但是很 threadIdx=(0,1) 的线程 2 会访问 tmp[64] 也位于 bank 0…… 也就是说，同一个 warp 的所有线程都在访问 bank 0 ！这导致读取无法并 行，必须串行排队，从而（单看共享内存的效率）会变慢 32 倍。（不过据说最新架构中好像把 bank 数降低到 16 个，也就是 half-warp 了） 故意把二维数组的跨步从 32 调为 33 ：解决区块冲突 • 解决方法就是，把

并且即使多个线程同时调用了 func ，这个变量的 初始化依然保证是原子的（ C++11 起）。 • 这就是函数静态初始化 (func-static-init) 大法。 函数静态初始化可用于“懒汉单例模式” • 如右图。 • getMyClassInstance() 会在第一次调用时创 建 MyClass 对象，并返回指向他的引用。 • 根据 C++ 函数静态变量初始化的规则，之后 的调用不会再重复创建。 Helper ）执行得比全 局静态初始化（ before_main ）还早！ 用包装，避免因为链接的不确定性打乱了静态初始化的顺序 • 利用这个发现，我们意识到可以把 functab 用所谓的“懒汉单例模式”包装成一 个 getFunctab() 函数，里面的 inst 变量 会在第一次进入的时候初始化。因为第一 次调用是在 defCat 中，从而保证是在所 有 emplace 之前就初始化过，因此不会

函数，并在终端显示出 Hello, world 。 厂商 C C++ Fortran GNU gcc g++ gfortran LLVM clang clang++ flang 多文件编译与链接 • 单文件编译虽然方便，但也有如下缺点： 1. 所有的代码都堆在一起，不利于模块化和理解。 2. 工程变大时，编译时间变得很长，改动一个地方就得全部重新编译。 • 因此，我们提出多文件编译的概念，文件之间通过符号声明相互引用。 标准库的功能，难免会用到一些第三方库。 • 最友好的一类库莫过于纯头文件库了，这里是一些好用的 header-only 库： 1. nothings/stb - 大名鼎鼎的 stb_image 系列，涵盖图像，声音，字体等，只需单头文件！ 2. Neargye/magic_enum - 枚举类型的反射，如枚举转字符串等（实现方式很巧妙） 3. g-truc/glm - 模仿 GLSL 语法的数学矢量 / 矩阵库（附带一些常用函数，随机数生成等）

对于入队操作，将输入元素赋值给 rear 索引处，并将 queSize 自增 1 即可； ‧ 对于出队操作，仅需将 front 自增 1 ，并将 queSize 自减 1 即可； 观察发现，入队与出队操作都仅需单次操作即可完成，时间复杂度皆为 ?(1) 。 5. 栈与队列 hello‑algo.com 70 Figure 5‑6. 基于数组实现队列的入队出队操作 细心的同学可能会发现一个问题：在不断入队与出队的过程中，front 81 } return res; } }; 5.4. 小结 ‧ 栈是一种遵循先入后出的数据结构，可以使用数组或链表实现。 ‧ 在时间效率方面，栈的数组实现具有更好的平均效率，但扩容时会导致单次入栈操作的时间复杂度劣化 至 ?(?) 。相对地，栈的链表实现具有更加稳定的效率表现。 ‧ 在空间效率方面，栈的数组实现会造成一定空间浪费，然而链表结点比数组元素占用内存更大。 ‧ 队列是一种 回忆数组插入操作，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后再将 base 赋值给目标 索引。 11. 排序算法 hello‑algo.com 168 Figure 11‑4. 单次插入操作 11.3.1. 算法流程 1. 第 1 轮先选取数组的 第 2 个元素 为 base ，执行「插入操作」后，数组前 2 个元素已完成排序。 2. 第 2 轮选取 第 3 个元素 为 base

道题目，熟悉主流的算法问题。初次刷题 时，“知识遗忘”可能是一个挑战，但请放心，这是很正常的。我们可以按照“艾宾浩斯遗忘曲线”来 复习题目，通常在进行 3～5 轮的重复后，就能将其牢记在心。推荐的题单和刷题计划请见此 GitHub 仓库。 3. 阶段三：搭建知识体系。在学习方面，我们可以阅读算法专栏文章、解题框架和算法教材，以不断丰富 知识体系。在刷题方面，可以尝试采用进阶刷题策略，如按专题分类、一题多解、一解多题等，相关的 要事实：计算机内部的硬件电路主要是基 于加法运算设计的。这是因为加法运算相对于其他运算（比如乘法、除法和减法）来说，硬件实现起来更简 第 3 章 数据结构 hello‑algo.com 58 单，更容易进行并行化处理，运算速度更快。 请注意，这并不意味着计算机只能做加法。通过将加法与一些基本逻辑运算结合，计算机能够实现各种其他 的数学运算。例如，计算减法 ? − ? 可以转换为计算加法 灵活地实现一些额外逻辑。 5.4 小结 1. 重点回顾 ‧ 栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现。 ‧ 在时间效率方面，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度会 劣化至 ?(?) 。相比之下，栈的链表实现具有更为稳定的效率表现。 ‧ 在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内 存空间比数组元素更大。

要事实：计算机内部的硬件电路主要是基 于加法运算设计的。这是因为加法运算相对于其他运算（比如乘法、除法和减法）来说，硬件实现起来更简 第 3 章 数据结构 hello‑algo.com 56 单，更容易进行并行化处理，运算速度更快。 请注意，这并不意味着计算机只能做加法。通过将加法与一些基本逻辑运算结合，计算机能够实现各种其他 的数学运算。例如，计算减法 ? − ? 可以转换为计算加法 活地实现一些额外逻辑。 5.4 小结 1. 重点回顾 ‧ 栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现。 ‧ 从时间效率角度看，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度 会降低至 ?(?) 。相比之下，基于链表实现的栈具有更为稳定的效率表现。 ‧ 在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内 存空间比数组元素更大。 的输出都相同，因此我们可以很容易地从哈希值反推出可用的 key ，从而破解密码。 6.3.2 哈希算法的设计 哈希算法的设计是一个需要考虑许多因素的复杂问题。然而对于某些要求不高的场景，我们也能设计一些简 单的哈希算法。 ‧ 加法哈希：对输入的每个字符的 ASCII 码进行相加，将得到的总和作为哈希值。 ‧ 乘法哈希：利用了乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII 码累积到哈希值中。

对于入队操作，将输入元素赋值给 rear 索引处，并将 queSize 自增 1 即可； ‧ 对于出队操作，仅需将 front 自增 1 ，并将 queSize 自减 1 即可； 观察发现，入队与出队操作都仅需单次操作即可完成，时间复杂度皆为 ?(1) 。 Figure 5‑6. 基于数组实现队列的入队出队操作 5. 栈与队列 hello‑algo.com 70 细心的同学可能会发现一个问题：在不断入队与出队的过程中，front 意，“撤销”的核心逻辑仍然是栈的先入后出，只是双向队列可以更加灵活地实现。 5.4. 小结 ‧ 栈是一种遵循先入后出的数据结构，可以使用数组或链表实现。 ‧ 在时间效率方面，栈的数组实现具有更好的平均效率，但扩容时会导致单次入栈操作的时间复杂度劣化 至 ?(?) 。相对地，栈的链表实现具有更加稳定的效率表现。 ‧ 在空间效率方面，栈的数组实现会造成一定空间浪费，然而链表结点比数组元素占用内存更大。 ‧ 队列是一种 回忆数组插入操作，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后再将 base 赋值给目标 索引。 11. 排序算法 hello‑algo.com 167 Figure 11‑4. 单次插入操作 11.3.1. 算法流程 循环执行插入操作： 1. 先选取数组的 第 2 个元素 为 base ，执行插入操作后，数组前 2 个元素已完成排序。 2. 选取 第 3 个元素 为 base