多元组：固定⻓度的不同类型数据的集合 定义： (<表达式>, <表达式>, ...) 类型： (<表达式类型>, <表达式类型>, ...) 例如： 身份信息： ("Bob", 2023, 10, 24): (String, Int, Int, Int) 成员访问： <多元组>.<索引> ： (2023, 10, 24).0 == 2023 列表：任意⻓度的相同类型数据的集合 例如： 字符的序列： Cons('H', Cons('i', Cons('!', Nil))) Cons ： construct 的缩写 3 笛卡尔积 ⼀个多元组类型的元素即是每个组成类型的元素构成的有序元素组 集合的笛卡尔积，⼜称积类型 例：扑克牌的所有花⾊：{ } 4 结构体 元组的问题在于，难以理解其所代表的数据 (String, Int) ：⼀个⼈的姓名和年龄？姓名和⼿机号？地址和邮编？ old_info, age: 2, } 2. let other_info = { .. old_info, name: "Hello", } 7 多元组与结构体的关系 结构体与相同类型集合构成的多元组同构 集合 A 与 B 之间存在⼀⼀映射的关系 存在⼀对映射 f: (A) -> B 与 g: (B) -> A 使得 g(f(a)) == a f(g(b)) == b 例： struct

现代编程思想 哈希表与闭包 Hongbo Zhang 1 回顾 表 键值对的集合，其中键不重复 简单实现：⼆元组列表 添加时向队⾸添加 查询时从队⾸遍历 树实现：⼆叉平衡树 基于第五节课介绍的⼆叉平衡树，每个节点的数据为键值对 对树操作时⽐较第⼀个参数 2 哈希表 哈希函数/散列函数 Hash function 将任意⻓度的数据映射到某⼀固定⻓度的数据 在⽉兔的 Hash Entry[K, V] { // 存储键值对 2. key : K 3. mut value : V // 允许原地修改值 4. } 5. 6. struct Bucket[V] { // 存储键值对的集合 7. mut val : Option[(V, Bucket[V])] // 允许原地进⾏增删操作 8. } 9. 10. struct HT_bucket[K, V] { 11. mut 数组⻓度，动态维护 13. mut size : Int // 哈希表键值对数量，动态维护 14. } 6 哈希表：直接寻址 添加/更新操作 添加时，根据键的哈希计算出应当存放的位置 遍历集合查找键 如果找到，修改值 否则，添加键值对 删除操作类同 0 3 1. 计算对应数组索引 4 9 2.遍历对应数据结构 7 哈希表：直接寻址 添加/更新操作 1. fn put[K

课程⼯具 MoonBit⽉兔 现代静态类型多范式编程语⾔ 语法轻量，易上⼿ 浏览器开发环境、云原⽣开发环境或本地集成开发环境 4 课程概览 课程 主题 课程 主题 课程介绍与程序设计 接⼜：集合与表 ⾯向值编程 结构体 命令 函数 列表与递归 可变状态 与可变数据结构 列表 元组 嵌套模式 抽象堆栈结构机器 数据类型与树 可变队列 树与⼆分查找 迭代与尾递归 ⼆叉搜索树的插⼊与删除

BoxedInt { value : Int } derive(Default, Eq, Compare, Debug) 需要数据结构内部的数据同样实现接⼝ 9 表：利⽤接⼝实现 ⼀个表是键值对的集合 对于每⼀个 键 存在⼀个对应 值 例： { 0 -> "a", 5 -> "Hello", 7 -> "a"} 1. type Map[Key, Value] 2. 3. // 创建表 4

⼆叉平衡树 2 ⽣活中的树状图 ⽣活中有很多的数据的结构与⼀颗树相似 谱系图（⼜称，家族树） ⽂件结构 数学表达式 …… 3 树的逻辑结构 数据结构中，树是由有限个节点构成的具有层次关系的集合 节点是存储数据的结构，节点之间存在亲⼦关系：⽗节点和⼦节点 如果树不为空，则它拥有⼀个根节点：根节点没有⽗节点 所有⾮根节点都有唯⼀的⽗节点 如果没有⼦节点的节点可称为叶节点 任何节点不能是⾃⼰的后代节点：树中不能有环路

当代码多次重复出现 当抽出的逻辑具有合适的语义 编程语⾔为我们提供了各种抽象的⼿段 函数、泛型、⾼阶函数、接⼝…… 2 泛型函数与泛型数据 3 堆栈 栈是⼀个由⼀系列对象组成的⼀个集合，这些对象的插⼊和删除遵循后进先出原则 （Last In First Out） 4 堆栈 我们定义以下操作，以存储整数的堆栈 IntStack 为例 1. empty: () -> IntStack

String "hello" "Moonbit" + "Hello, " + "MoonBit" Bool true false && || not() not(b1) || b2 每⼀个类型对应⼀个值的集合 每⼀个表达式由基于值的运算构成，并且可以简化为⼀个值（或已经是⼀个值） 可以使⽤括号来嵌套表达式 11 静态 vs 动态 �静态�指在程序运⾏之前的事物 �动态�指在程序运⾏之时的事物

现代编程思想 函数, 列表与递归 Hongbo Zhang 1 基本数据类型：函数 2 函数 在数学上，描述对应关系的⼀种特殊集合 对于特定的输⼊，总是有特定的输出 在计算机中，对相同运算的抽象，避免⼤量重复定义 计算半径为1的圆的⾯积： 3.1415 * 1 * 1 计算半径为2的圆的⾯积： 3.1415 * 2 * 2 计算半径为3的圆的⾯积： 3.1415 * 3 *