Hello 演算法 Rust 語言版 作者：靳宇棟（@krahets） 程式碼審閱：伍志豪（@night‑cruise）、榮怡（@rongyi） Release 1.2.0 2024‑12‑06 序 兩年前，我在力扣上分享了“劍指 Offer”系列題解，受到了許多讀者的鼓勵與支持。在與讀者交流期間，我 最常被問到的一個問題是“如何入門演算法”。漸漸地，我對這個問題產生了濃厚的興趣。 付出的寶貴“注意力”，我會竭盡所能，投入最大的“注意力” 來完成本書的創作。 本人自知學疏才淺，書中內容雖然已經過一段時間的打磨，但一定仍有許多錯誤，懇請各位老師與同學批評 指正。 本書中的程式碼附有可一鍵執行的原始檔，託管於 github.com/krahets/hello‑algo 倉庫。 動畫在 PDF 內的展示效果有限，可訪問 www.hello‑algo.com 網頁版以獲得更佳的閱讀體驗。 ——李沐，亞馬遜資深首席科學家 電腦的出現為世界帶來了巨大的變革，它憑藉高速的運算能力與卓越的可程式化特性，成為執行演算法 與處理資料的理想媒介。無論是電玩遊戲的逼真畫面、自動駕駛的智慧決策，還是 AlphaGo 的精彩棋局、 ChatGPT 的自然互動，這些應用都是演算法在電腦上的精妙演繹。 事實上，在電腦問世之前，演算法和資料結構就已經存在於世界的各個角落。早期的演算法相對簡單，例如 古

. . . . . . . . . . . . . . . . . . . . 16 2.2 本訓練課程的程式碼範例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 使用 Cargo 在本機執行程式碼 . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 . . . . . . . . . . . . . . . . . . . . . 92 V 第 3 天：上午 94 18 歡迎參加第 3 天課程 95 19 記憶體管理 96 19.1 檢查程式記憶體 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 19.2 自動記憶體管理 . . . . . 4 use、super、self . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 26.5 練習：GUI 程式庫的模組 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 26.5.1 解決方案 . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . 17 2.2 本訓練課程的程式碼範例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 使用 Cargo 在本機執行程式碼 . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 . . . . . . . . . . . . . . . . . . . . . 94 V 第 3 天：上午 96 18 歡迎參加第 3 天課程 97 19 記憶體管理 98 19.1 檢查程式記憶體 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 19.2 自動記憶體管理 . . . . . 4 use、super、self . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 26.5 練習：GUI 程式庫的模組 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 26.5.1 解決方案 . . . . . . . . .

‧ C 语言是过程式编程语言，没有面向对象的概念，所以只有函数。但我们可以通过创建结构体（struct） 来模拟面向对象编程，与结构体相关联的函数就相当于其他编程语言中的方法。 ‧ Java 和 C# 是面向对象的编程语言，代码块（方法）通常作为某个类的一部分。静态方法的行为类似于 函数，因为它被绑定在类上，不能访问特定的实例变量。 ‧ C++ 和 Python 既支持过程式编程（函数），也支持面向对象编程（方法）。 部分名词在简体中文和繁体中文下的叫法不同。 表 16‑1 数据结构与算法的重要名词 English 简体中文 繁体中文 algorithm 算法 演算法 data structure 数据结构 資料結構 code 代码 程式碼 file 文件 檔案 function 函数 函式 method 方法 方法 variable 变量 變數 asymptotic complexity analysis 渐近复杂度分析 漸近複雜度分析 asymptotic upper bound 渐近上界 漸近上界 第 16 章 附录 hello‑algo.com 377 English 简体中文 繁体中文 sign‑magnitude 原码 原碼 1’s complement 反码 一補數 2’s complement 补码 二補數 array 数组 陣列 index 索引 索引 linked list 链表 鏈結串列 linked

‧ C 语言是过程式编程语言，没有面向对象的概念，所以只有函数。但我们可以通过创建结构体（struct） 来模拟面向对象编程，与结构体相关联的函数就相当于其他编程语言中的方法。 ‧ Java 和 C# 是面向对象的编程语言，代码块（方法）通常作为某个类的一部分。静态方法的行为类似于 函数，因为它被绑定在类上，不能访问特定的实例变量。 ‧ C++ 和 Python 既支持过程式编程（函数），也支持面向对象编程（方法）。 部分名词在简体中文和繁体中文下的叫法不同。 表 16‑1 数据结构与算法的重要名词 English 简体中文 繁体中文 algorithm 算法 演算法 data structure 数据结构 資料結構 code 代码 程式碼 file 文件 檔案 function 函数 函式 method 方法 方法 variable 变量 變數 asymptotic complexity analysis 渐近复杂度分析 漸近複雜度分析 recursion tree 递归树 遞迴樹 big‑? notation 大 ? 记号 大 ? 記號 asymptotic upper bound 渐近上界 漸近上界 sign‑magnitude 原码 原碼 1’s complement 反码 一補數 2’s complement 补码 二補數 array 数组 陣列 index 索引 索引 linked list 链表 鏈結串列 linked

#[derive(HelloMacro)] struct Pancakes; fn main() { Pancakes::hello_macro(); } 示例 19-30: crate 用户所写的能够使用过程式宏的代码 运行该代码将会打印 Hello, Macro! My name is Pancakes! 第一步是像下面这样新建一个库 crate： $ cargo new hello_macro --lib hello_macro 函数提供一个能够打印实现了该 trait 的类型的名字的默认 实现：Rust 没有反射的能力，因此其无法在运行时获取类型名。我们需要一个在编译时生成 代码的宏。 下一步是定义过程式宏。在编写本部分时，过程式宏必须在其自己的 crate 内。该限制最终可 能被取消。构造 crate 和其中宏的惯例如下：对于一个 foo 的包来说，一个自定义的派生过 程宏的包被称为 foo_derive 。在 包的目录下创建过程式宏的 crate。如果改变 在 hello_macro 中定义的 trait，同时也必须改变在 hello_macro_derive 中实现的过程式宏。 这两个包需要分别发布，编程人员如果使用这些包，则需要同时添加这两个依赖并将其引入作 用域。我们也可以只用 hello_macro 包而将 hello_macro_derive 作为一个依赖，并重新导出 过程式宏的代码。但现在我们组织项目的方式使编程人员在无需

hello_macro crate，其包含名为 HelloMacro 的 trait 和关联函数 hello_macro。不同于让用户为其每一个类型实现 HelloMacro trait，我们将会提供一个过程式 宏以便用户可以使用 #[derive(HelloMacro)] 注解它们的类型来得到 hello_macro 函数的默认 实现。该默认实现会打印 Hello, Macro! My name is TypeName #[derive(HelloMacro)] struct Pancakes; fn main() { Pancakes::hello_macro(); } 示例 20-37: 我们 crate 的用户所写的能够使用过程式宏的代码 运行该代码将会打印 Hello, Macro! My name is Pancakes! 第一步是像下面这样新建一个库 crate： $ cargo new hello_macro --lib 的类型的名字的默认 实现：Rust 没有反射能力，因此其无法在运行时获取类型名。我们需要一个在编译时生成代 码的宏。 501/562Rust 程序设计语言 简体中文版 下一步是定义过程宏。在编写本部分时，过程式宏必须在其自己的 crate 内。该限制最终可能 被取消。crate 及其宏 crate 的结构惯例如下：对于一个名为 foo 的 crate，其自定义 derive 过程宏 crate 通常命名为

function」可以被独立执行，所有参数都以显式传递。「方法 method」与一个对象关联，被隐式传递 给调用它的对象，能够对类的实例中包含的数据进行操作。 下面以几种常见的编程语言为例来说明。 ‧ C 语言是过程式编程语言，没有面向对象的概念，所以只有函数。但我们可以通过创建结构体（struct） 来模拟面向对象编程，与结构体相关联的函数就相当于其他编程语言中的方法。 第 2 章 复杂度分析 hello‑algo ‧ Java 和 C# 是面向对象的编程语言，代码块（方法）通常作为某个类的一部分。静态方法的行为类似于 函数，因为它被绑定在类上，不能访问特定的实例变量。 ‧ C++ 和 Python 既支持过程式编程（函数），也支持面向对象编程（方法）。 Q：图解“常见的空间复杂度类型”反映的是否是占用空间的绝对大小？ 不是，该图展示的是空间复杂度，其反映的是增长趋势，而不是占用空间的绝对大小。 假设取