Java 编 程 与 算 法 实 用 入 门 A Concise and Practical Introduction to Programming Algorithms in Java Chapter 8: Data-structures and object methods 第 8 章 : 数 据 结 构 和 对 象 的 方 法 1
Agenda 大 纲 FIFO data-structures 先 进 先 出 ( FIFO) 数 据 结 构 (= First In First Out) Heap data-structures 堆 结 构 Non-static methods 非 静 态 方 法 (= object methods) ( = 对 象 的 方 法 ) Revisiting lists (OO-style) 重 访 问 链 表 ( 面 向 对 象 的 类 型 ) 2
FIFOs: Mastering queues 先 进 先 出 : 控 制 队 列 Objects are considered in turn, one by one 对 象 轮 流 一 个 一 个 处 理 Process each object according to their arrival time 根 据 对 象 的 到 达 时 间 来 进 行 处 理 While objects are processed, others are queued 当 有 对 象 被 处 理 时, 其 它 对 象 排 队 等 待 First object should be first served! 第 一 个 到 达 的 对 象 被 第 一 个 处 理 Basic examples: 简 单 的 几 个 例 子 : Waiting in a queue at the post office. 在 邮 局 排 队 Printing?jobs> on a printer. 有 多 个 文 件 同 时 需 要 打 印 机 打 印 FIFO = First In First Out! FIFO = 先 进 先 出! 3
A basic solution 基 本 思 路 Stack objects in an array as soon as they arrive 一 收 到 对 象 就 把 它 存 在 栈 中 To stack an incoming object, should know the index of the last location 要 把 对 象 存 在 栈 中, 就 需 要 知 道 存 储 的 位 置 ( 索 引 ) Should also know the index of the last processed object (so that we can process the next one) While processing an object, others can come in the array (= queued) 同 时 还 需 要 知 道 上 一 个 处 理 的 对 象 的 索 引 ( 这 样 才 能 知 道 下 一 个 对 象 是 哪 个 ) 当 我 们 在 处 理 一 个 对 象 时, 其 它 对 象 可 以 在 数 组 中 排 队 4
A basic solution 基 本 思 路 An array: container array for storing objects 一 个 array( 数 组 ) : 存 储 数 组, 用 以 存 储 对 象 Two indices: lastprocessed and freeplace 两 个 索 引 : lastprocessed ( 用 以 记 录 最 后 处 理 的 对 象 位 置 ) 和 freeplace ( 用 以 记 录 可 用 空 间 的 位 置 ) To add an object x, we do array[freeplace]=x and we then increment: freeplace++ 增 加 一 个 对 象 x : array[freeplace] = x To process an object, we increment lastprocessed and we process array[lastprocessed] 当 我 们 需 要 处 理 一 个 对 象 时, 把 lastprocessed 加 1, 然 后 我 们 取 出 array[lastprocessed] 进 行 处 理 5
Visual depiction of a FIFO 借 助 图 来 理 解 先 进 先 出 算 法 ( FIFO ) 6
FIFO: Queuing objects 先 进 先 出 ( FIFO ): 对 象 排 队 7
Queuing another object 如 何 对 新 对 象 列 入 队 伍 8
Processing and queuing 处 理 对 象 和 把 新 对 象 列 入 队 列 Processing and queuing can be done in parallel using threads 处 理 对 象 和 把 新 对 象 列 入 队 列 可 以 用 多 线 程 并 行 处 理 9
Programming queues 队 列 的 代 码 10
FIFO: First In First Out FIFO : 先 进 先 出 11
Exercise: FIFO in action! 练 习 : FIFO Let A be a set of integers such that: 设 A 为 一 个 整 数 的 集 合, 满 足 以 下 条 件 : 1 belongs to A, and 1 属 于 A If a belongs to A, then 2*a+1 and 3*a belongs to A 如 果 a 属 于 A, 那 么 2*a+1 和 3*a 都 属 于 A Question: 问 题 : For a given n, display all integers less or equal to n that belong to A. 任 意 给 定 一 个 n, 显 示 出 所 有 小 于 等 于 n 并 且 属 于 A 的 数 字 12
Programming queues 给 队 列 编 程 Start with a FIFO initialized with element 1 首 先 用 1 给 FIFO 初 始 化 Use a boolean array to store whether a belong to A 构 造 一 个 布 尔 (Boolean) 数 组, 用 以 记 录 每 一 个 数 是 否 属 于 A (= marks, tag elements) ( 相 当 于 标 签 ) For each element a of the FIFO do: 对 于 FIFO 的 每 一 个 元 素 : Compute 2*a+1 and 3*a 计 算 2*a+1 和 3*a Add them to the FIFO if they are less than n...and not yet encountered (=marked) 如 果 他 们 小 于 n 并 且 是 一 个 新 数 字 ( 没 有 被 标 记 过 ) 的 话, 把 他 们 放 入 FIFO 队 列 中 Terminate when the FIFO is empty 直 到 当 FIFO 队 列 为 空 时 停 止 Display all marked elements (=result) 显 示 所 有 被 标 记 过 的 数 字 ( 结 果 ) 13
14
A few remarks on FIFOs 关 于 FIFO 的 几 点 值 得 注 意 的 地 方 Set beforehand the size of the array? 是 否 要 事 先 确 定 数 组 的 大 小? Can wrap the array using mod MAX_SIZE 可 以 用 mod MAX_SIZE 来 构 造 数 组 的 功 能 (=circular ring, extend arrays, etc.) ( 比 如 用 循 环 的 环, 扩 展 数 组 等 数 据 结 构 )...But how to check whether the queue is empty 但 问 题 是 如 何 检 验 队 列 是 否 为 空?... or full with circular arrrays? 以 及 如 何 检 验 循 环 结 构 的 数 组 是 否 已 满? 15
Priority queues: Heaps (=tas) 优 先 队 列 ( 堆 ) Objects are considered in turn 对 象 被 轮 流 考 虑 ( 等 待 处 理 ) Need to process them according to their priorities 根 据 他 们 的 优 先 级 来 处 理 While processing an objects, other may arrive 当 处 理 一 个 对 象 时, 其 它 新 对 象 可 能 会 到 达 ( 进 入 队 列 ) (= are being queued) Serve the object with the highest priority first 象 Examples: 例 子 : Ressource request 资 源 请 求 Operating system tasks 操 作 系 统 的 任 务 优 先 处 理 优 先 级 最 高 的 对 16
Defining mathematically heaps 用 数 学 语 言 来 定 义 堆 A heap is a sequence of integers: 堆 是 一 个 被 紧 密 存 储 在 数 组 中 的 整 数 序 列 stored compactly in an array such that: For example: 比 如 : 37, 22, 31, 16, 17, 2, 23, 12, 6, 9 ( heap of 10 elements) ( 10 个 元 素 的 堆 ) 17
Drawing a heap 画 出 堆 Draw a heap as a tree (=special graph Vertex/Edge) 用 树 状 结 构 ( 相 当 于 特 殊 的 图 ) 来 画 堆 Each node i contains a value t[i] and has 每 一 个 节 点 i 拥 有 一 个 值 t[i] 并 且 拥 有 0, 1, 或 2 个 对 应 值 小 于 他 们 父 亲 的 兄 弟 0, 1 or 2 siblings that contain nodes of values less than its parent Node i has children 2i and 2i+1 节 点 i 有 2 个 儿 子 : 2i 和 2i+1 37, 22, 31, 16, 17, 2, 23, 12, 6, 9: Read layer by layer, 从 树 根 到 叶 子, 一 层 一 层 地 读 from the root til the leaves 18
Storing and manipulating heaps 对 堆 进 行 存 储 和 操 作 Easy to code with a linear array 用 线 性 数 组 很 容 易 19
Fundamental property of heaps 堆 的 基 本 性 质 Largest value is stored at the root of the tree, namely 最 大 值 被 存 储 在 树 根, 即 数 组 的 第 一 个 位 置 at the first element of the array. 20
Adding an element in a heap 在 堆 中 增 加 一 个 元 素 Add the new element in position n (=n+1th element)... 把 新 元 素 放 在 位 置 n ( 第 n+1 个 元 素 ) But the condition that the array is a heap is violated... 但 这 样 的 话 数 组 就 不 是 以 堆 顺 序 存 储 So that we swap the element until.......it satisfies the heap constraint 所 以 我 们 需 要 改 变 元 素 的 顺 序 ( 交 换 元 素 ), 直 到 满 足 堆 的 条 件 为 止 21
Example: Add element 25 例 子 : 增 加 元 素 25 Not a heap anymore!!! 25>17 因 为 25 17, 这 不 再 是 一 个 堆 结 构 了!!! Swap with your parent! 交 换 父 节 点 22
Add element 25... and swap!!! 增 加 元 素 25, 然 后 交 换!!! It is a heap now! 现 在 它 是 一 个 堆 了! 23
Adding an element in the heap 在 堆 结 构 中 增 加 元 素 24
Removing the largest element of a heap 如 何 去 除 堆 中 最 大 的 元 素 We move the element at position (n-1) and put it at the root (position 0) 我 们 把 在 n-1 位 置 上 的 元 素 放 到 根 节 点 ( 位 置 0 ) 上 But it is not anymore a heap... 但 这 是 就 不 满 足 堆 的 性 质 了 So we swap to the bottom until......the heap condition is satisfied 因 此 我 们 把 元 素 交 换 到 堆 的 底 部, 直 到 满 足 堆 的 条 件 25
Removing the largest element of a heap 如 何 去 除 堆 中 最 大 的 元 素 26
27
Then Swap parent-child... 然 后 交 换 父 子 元 素 28
Removing the largest element of a heap 如 何 去 除 堆 中 最 大 的 元 素 29
Non-static methods and objects 非 静 态 方 法 和 对 象 Do not write static in front of the method 不 要 在 方 法 前 使 用 static 关 键 词 Method is thus attached to the object for which it applies for 这 样 的 话 该 方 法 就 和 他 所 应 用 的 方 法 相 关 联 For example, we prefer: 比 如, 我 们 偏 爱 u.display() rather than display(u) u.display() 而 不 是 display(u) u.addelement(a) instead of addelement(a,u) u.addelement(a) 而 不 是 addelement(a.u) To reference the object on which the method is called upon use this 如 果 要 表 示 引 用 该 方 法 的 对 象, 用 this 关 键 词 Object-oriented programming paradigm (OO) 面 向 对 象 ( OO ) 编 程 范 例 30
Object-oriented programming paradigm (OO) 面 向 对 象 ( OO ) 编 程 范 例 Design a software as a set of objects and methods applying on these objects 设 计 一 个 软 件 时, 把 软 件 视 为 一 组 对 象 以 及 一 系 列 应 用 在 这 些 对 象 上 的 方 法 Ask yourself first: 首 先 问 自 己 : - What are the objects? 什 么 是 对 象? - What are the methods? 什 么 是 方 法? Usually, a method often modifies the object (=fields) on which it applies for. 通 常 来 说, 一 个 方 法 能 够 修 改 它 所 应 用 的 对 象 (But not always, for example: Obj.Display()) ( 但 也 并 非 绝 对, 比 如 说 Obj.Display() 不 能 修 改 它 所 应 用 的 对 象 ) Picture : Public procedures 公 共 (public) 方 法 Private data 私 有 (private) 数 据 Private procedures 私 有 (private) 方 法 Interaction-Interface 交 互 - 接 口 ( Interface ) 31
OO style: 面 向 对 象 ( OO ) 风 格 : object methods 对 象 方 法? versus 还 是 static functions 静 态 函 数? 32
Static methods are useful for defining: 静 态 方 法 用 于 在 函 数 库 ( library ) 中 定 义 : - Constants 常 数 - Basic functions 基 本 函 数...in a library. 等 等 33
Heaps revisited in Object-Oriented style 用 面 向 对 象 ( OO ) 风 格 编 写 的 重 访 问 堆 Observe that the keyword static has disappeared 我 们 不 再 使 用 关 键 字 static 了 34
List in object-oriented style 面 向 对 象 风 格 的 链 表 ( list ) A cell stores information (say, an integer) and point/refer to the next one. 每 一 个 单 位 存 储 信 息 ( 比 如 一 个 整 数 ) 和 指 向 下 一 个 单 位 的 指 针 Pointing to another cell means storing a reference to the corresponding cell. 指 向 下 一 个 单 位 意 味 着 存 储 对 应 单 位 的 引 用 35
Pay special attention to null!!! 要 特 别 注 意 null!!! Remember that we cannot access fields of the null object 要 记 住, 我 们 无 法 进 入 空 对 象 的 域 Throw the exception nullpointerexception 会 抛 出 异 常 nullpointerexception Thus we need to check whether the current object is null or not, before calling the method 因 此 我 们 需 要 在 调 用 方 法 前 检 查 对 象 是 否 为 空 In the reminder, we consider that all lists (also the void list) contain a first cell that stores no information. 在 之 后 的 课 程 中, 我 们 假 设 所 有 的 链 表 ( 包 括 空 链 表 ) 的 第 一 个 不 存 储 任 何 信 息 的 元 素 36
Revisiting the linked list (OO style) 重 新 来 看 链 表 ( linked list ) ( 面 向 对 象 风 格 ) 37
Revisiting the linked list (OO style) 重 新 来 看 链 表 ( linked list ) ( 面 向 对 象 风 格 ) 38
Revisiting the linked list (OO style) 重 新 来 看 链 表 ( linked list ) ( 面 向 对 象 风 格 ) 39
Revisiting the linked list (OO style) 重 新 来 看 链 表 ( linked list ) ( 面 向 对 象 风 格 ) 40
Revisiting the linked list (OO style) 重 新 来 看 链 表 ( linked list ) ( 面 向 对 象 风 格 ) 41
Stacks (LIFO): Last In First Out 栈 数 据 结 构 : 后 进 先 出 ( LIFO, Last In First Out ) Two basic operations for that data-structure: 2 个 基 本 操 作 : Push: Add an element on top of the stack 压 入 ( push ): 在 栈 顶 加 入 一 个 元 素 Pull: Remove the topmost element 弹 出 ( Pull ): 从 栈 顶 移 去 一 个 元 素 42
Stacks (LIFO) using arrays 用 数 组 来 实 现 栈 ( LIFO ) 43
44
Stacks (LIFO) using linked lists 用 链 表 来 实 现 栈 ( LIFO ) 45
46
Stacks: API 栈 的 应 用 程 序 接 口 ( API ) // Use a Java package here // 这 里 我 们 使 用 Java 包 47
Stacks (LIFO) using linked lists 用 链 表 来 实 现 栈 ( LIFO ) Notice: Same code as StackArray demo program. 注 意 : 与 StackArray 演 示 程 序 代 码 相 同 48
Static functions versus methods 静 态 函 数 还 是 对 象 方 法 Static (class) functions: 静 态 函 数 : Access static/local variables only. 只 能 使 用 静 态 / 本 地 的 变 量 class methods» 类 方 法 Potentially many arguments in functions 静 态 函 数 中 容 易 产 生 许 多 参 数 Object methods: 对 象 方 法 : Access object fields (using this) 可 以 使 用 对 象 的 域 变 量 或 方 法 ( 用 this 关 键 字 ) Access (class) static variables too. 也 可 以 使 用 静 态 变 量 Objects are instances of classes 对 象 是 类 (class) 的 实 例 Data encapsulation 数 据 包 装 (=functions with limited number of arguments) (= 拥 有 少 量 参 数 的 函 数 ) Constructor (= field initialization) 构 造 函 数 (= 域 初 始 化 ) 49
50