http://jwc..edu.cn/jxgl/ HomePage/Default.asp 2 说 明 总 学 时 : 72( 学 时 )= 56( 课 时 )+ 16( 实 验 ) 行 课 时 间 : 第 1 ~14 周 周 学 时 : 平 均 每 周 4 学 时 上 机 安 排 待 定 考 试 时 间 : 课 程 束 第 8 11 12 章 的 内 容 为 自 学 内 容 ; 目 录 中 标 有 ** 的 内 容 ( 除 递 归 外 ) 不 作 要 求 1
上 机 安 排 10 级 计 算 机 媒 专 业 1 2 班 指 导 老 师 : 时 间 :4-11 周 地 点 : 计 算 机 学 院 机 房 3 4 教 材 与 参 考 书 严 蔚 敏,, 清 华 大 学 出 版 社 Clifford A. Shaffer, 与 算 法 分 析, 电 子 工 业 出 版 社 Sartaj Sahni, 算 法 与 应 用, 机 械 工 业 出 版 社 严 蔚 敏, 题 集, 清 华 大 学 出 版 社 2
课 程 简 介 5 1. 的 研 究 对 象 2. 课 程 的 性 质 与 定 位 3. 课 程 的 内 容 与 组 织 是 现 实 世 界 的 字 化 研 究 在 计 算 机 中 的 表 示 关 联 存 储 与 处 理 方 法 组 织 与 是 计 算 机 科 学 最 基 本 内 容, 是 人 才 信 息 素 质 的 脊 梁 培 养 抽 象 能 力, 算 法 设 计 能 力 以 及 造 算 法 思 维 方 法 基 本 概 念 基 本 基 本 技 术 三 层 次 用 C 语 言 描 述 算 法, 突 出 算 法 实 质 例 题 习 题 典 型 题 例 实 习 范 例 课 程 设 计 全 方 位 训 练 6 1. 的 研 究 对 象 我 们 生 活 在 一 个 物 质 的 世 界, 计 算 机 工 作 者 又 面 对 着 字 的 世 界, 如 果 将 物 质 世 界 中 的 事 与 物 字 化, 那 么 它 们 在 计 算 机 中 的 表 现 均 为 这 些 来 源 于 现 实, 表 征 着 具 体 的 意 义, 而 且 在 计 算 机 中 有 着 统 一 的 表 示 方 法, 因 而 成 为 被 计 算 机 程 序 处 理 的 符 号 集 合 研 究 在 计 算 机 中 的 表 示 方 法 关 联 方 法 存 储 方 法 以 及 在 其 上 的 典 型 处 理 方 法, 就 成 了 课 程 的 主 要 内 容 3
2. 课 程 的 性 质 与 地 位 由 于 是 计 算 机 处 理 的 对 象, 使 用 计 算 机 的 过 程 就 是 对 进 行 加 工 处 理 的 过 程, 因 而 的 组 织 与 被 确 立 为 计 算 机 科 学 中 最 为 基 本 内 容 80 年 代 初, 课 程 就 已 成 为 国 内 计 算 机 专 业 教 学 计 划 中 的 核 心 课 程 人 类 解 决 问 题 的 思 维 方 式 可 分 为 推 理 方 式 和 算 法 方 式 两 大 类 推 理 方 式 凭 借 公 理 系 统 思 维 方 法 通 过 学 训 练 得 到 算 法 方 式 则 是 凭 借 造 性 思 维, 从 具 体 操 作 规 范 入 手, 通 过 操 作 过 程 的 造 实 施 来 解 决 特 定 问 题 7 的 学 习 过 程, 是 算 法 造 性 思 维 方 法 的 训 练 过 程, 技 能 培 养 的 重 要 程 度 不 亚 于 知 识 传 授 本 门 课 程 教 学 难 点 在 于 让 学 生 理 解 习 惯 算 法 造 思 维 方 法 培 养 学 生 的 抽 象 能 力, 算 法 设 计 能 力 以 及 创 造 性 思 维 方 法, 才 能 够 举 一 反 三 触 类 旁 通, 从 而 达 到 应 用 知 识 解 决 复 杂 问 题 的 目 的 8 2. 课 程 的 性 质 与 地 位 是 重 要 的 专 业 基 础 课, 是 计 算 机 科 学 的 核 心 课 程, 是 计 算 机 理 与 技 术 的 重 要 基 石 该 课 程 在 大 学 二 年 级 下 学 期 开 设, 具 有 承 上 启 下 的 重 要 作 用, 既 要 对 前 一 年 学 习 的 软 件 技 术 进 行 总 提 高, 又 要 为 后 续 专 业 课 程 提 供 基 础 它 贯 通 始 终, 是 计 算 机 科 学 与 技 术 人 才 素 质 培 养 框 架 中 的 中 坚 课 程, 对 学 生 的 软 件 开 发 能 力 培 养 有 至 关 重 要 的 作 用, 将 为 学 生 今 后 的 专 业 生 涯 打 下 牢 固 基 础 4
9 3. 课 程 的 内 容 与 组 织 以 抽 象 类 型 为 中 心, 采 用 面 向 对 象 的 新 观 点, 将 教 学 内 容 分 为 基 本 概 念 基 本 基 本 算 法 三 个 层 次, 并 贯 穿 了 计 算 机 科 学 中 的 一 些 重 要 的 问 题 求 解 技 术, 符 合 认 知 规 律 使 用 熟 悉 的 标 准 C 作 为 算 法 描 述 的 语 言, 使 与 大 多 院 校 讲 授 的 第 一 语 言 衔 接, 便 于 将 读 者 的 注 意 力 集 中 在 算 法 的 理 解 上 这 就 使 的 表 示 得 以 简 化, 突 出 了 算 法 表 示 的 实 质 例 题 习 题 典 型 题 例 实 习 范 例 课 程 设 计 全 方 位 训 练 4. 成 绩 计 算 平 时 成 绩 :30% 考 勤 + 课 堂 表 现 + 作 业 + 课 堂 测 验 + 上 机 考 察 考 试 成 绩 :70% 10 5
11 学 生 的 考 核 资 格 按 下 述 原 则 审 查 : 学 生 有 以 下 情 况 一 者, 不 能 参 加 课 程 成 绩 考 核, 该 课 程 的 考 核 成 绩 以 零 分 处 理 在 确 定 学 籍 处 理 授 予 学 士 学 位 时, 该 门 课 程 以 考 核 不 及 格 门 次 参 加 统 计 全 期 旷 课 累 计 达 该 课 程 教 学 时 五 分 一 ( 含 五 分 一 ) 以 上 者 ; 全 期 缺 交 该 课 程 任 课 教 师 布 置 作 业 三 分 一 ( 含 三 分 一 ) 以 上 者 ; 或 全 期 所 交 该 课 程 作 业, 虽 达 到 任 课 教 师 布 置 作 业 三 分 二 以 上, 但 所 交 作 业 的 准 确 度 整 洁 度 有 二 分 一 不 合 格 者 ; 全 期 缺 做 该 课 程 实 习 实 验 或 缺 交 实 习 实 验 报 告 达 三 分 一 ( 含 三 分 一 ) 以 上 者 ; 或 全 期 参 加 该 课 程 实 习 实 验, 所 交 实 习 实 验 报 告 都 在 三 分 二 以 上, 但 有 二 分 一 不 合 格 者 ; 未 经 批 准 或 未 办 理 选 课 手 续, 擅 自 修 读 该 门 课 程 者 12 目 录 第 一 章 : 第 二 章 : 线 性 表 第 三 章 : 栈 和 队 列 第 四 章 : 串 第 五 章 : 组 和 广 义 表 第 六 章 : 树 和 二 叉 树 第 七 章 : 图 第 九 章 : 查 找 第 十 章 : 内 部 排 序 6
第 一 章 的 有 关 概 念 算 法 和 算 法 分 析 14 1. 1 什 么 是 的 引 例 1 图 书 馆 的 书 目 检 索 系 统 自 动 化 问 题 在 书 目 自 动 检 索 系 统 中 可 以 建 立 一 张 按 等 录 顺 序 号 排 列 的 书 目 文 件 和 三 张 分 别 按 书 名 作 者 名 和 分 类 号 顺 序 排 列 的 索 引 表, 如 下 所 示 : 001 002 003 004 高 等 学 理 力 学 高 等 学. 线 形 代 樊 映 川 罗 远 祥 华 罗 庚 栾 汝 书. S01... L01... S01... S02..... 7
15 高 等 学 理 力 学. 线 形 代 L S. 按 书 名 排 列 001,003, 002, 004,... 按 索 引 号 排 列 002, 001, 003....... 樊 映 川 华 罗 庚. 栾 汝 书 按 作 者 排 列 001, 003, 004, 特 点 : 计 算 机 按 某 个 特 定 的 要 求 进 行 查 询. 处 理 对 象 间 存 在 一 种 简 单 的 线 形 关 系, 这 类 模 型 可 以 称 为 简 单 的 线 形........... 例 2: 计 算 机 和 人 的 对 弈 问 题 对 奕 的 过 程 是 在 一 定 的 规 则 下 随 机 进 行 的, 因 此, 计 算 机 必 须 对 对 弈 过 程 中 可 能 发 生 的 情 况 以 及 相 应 的 对 策 都 考 虑 周 全. 这 个 关 系 不 是 线 形 的, 从 一 个 棋 盘 可 以 派 生 出 几 个 格 局, 如 下 图 : * * 16 * * (a) 棋 盘 格 式 示 例 * * * * * * * * * * * * * * (b) 井 字 棋 对 弈 树 的 局 部 树 根 是 对 奕 开 始 前 的 棋 盘 格 局, 而 所 有 的 叶 子 是 可 能 出 现 的 局, 对 奕 的 过 程 就 是 从 树 根 沿 树 叉 到 达 某 个 叶 子 的 过 程. 8
例 3: 多 叉 路 口 交 通 灯 的 管 理 问 题 可 以 把 这 类 交 通, 道 路 的 问 题 当 作 一 种 图 的 : 一 个 顶 点 表 示 一 条 通 道, 而 通 道 间 的 矛 盾 的 关 系 以 两 个 顶 点 间 的 连 线 表 示. 如 下 图 所 示 : B C D 17 A (a) 五 叉 路 口 E 18 : 综 合 上 面 三 个 例 子, 描 述 这 类 非 值 计 算 性 问 题 的 学 模 型 不 再 是 学 方 程, 而 是 诸 如 表 树 和 图 类 的. 定 义 : 是 一 门 非 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的 操 作 对 象 以 及 它 们 间 的 关 系 和 操 作 等 的 学 科. 9
的 地 位 是 计 算 机 科 学 中 一 门 综 合 性 的 专 业 基 础 课 可 以 认 为 是 介 于 学 计 算 机 硬 件 计 算 机 软 件 三 者 间 的 一 门 核 心 课 程 19 20 (Data) 1. 2 基 本 概 念 客 观 事 物 的 符 号 表 示, 能 输 入 到 计 算 机 中 并 被 计 算 机 中 程 序 处 理 的 符 号 的 总 称 元 素 (Data element) 的 基 本 单 位, 可 由 项 组 成 类 型 (Data Type) 是 和 密 切 相 关 的 一 个 概 念, 在 高 级 语 言 中, 用 以 刻 画 ( 程 序 ) 操 作 对 象 的 特 性 是 一 个 值 的 集 合 和 定 义 在 这 个 值 集 上 的 一 组 操 作 的 总 称 10
对 象 (Data Object) 性 质 相 同 的 元 素 的 集 合, 是 的 子 集 (Data Structure) 21 相 互 间 存 在 一 种 或 多 种 特 定 关 系 的 元 素 的 集 合 元 素 间 的 相 互 关 系 称 为 有 下 列 四 种 基 本 : (1) 集 合 (2) 线 形 (3) 树 形 (4) 图 状 ( 网 状 ) 集 合 线 性 22 图 树 11
类 型 的 逻 辑 的 形 式 定 义 : Data_Structure=[D,S,P] 其 中 : D 是 元 素 的 有 限 集 S 是 上 下 关 系 的 有 限 集 P 是 对 对 象 的 基 本 操 作 的 物 理 ( 存 储 ), 基 本 操 作 的 实 现 ; 的 存 储 : 位 元 素 和 域 23 的 存 储 形 式 有 : 顺 序 存 储 链 式 存 储 类 型 综 述 类 型 可 以 分 为 原 子 类 型 值 不 可 以 分 解 类 型 值 由 若 干 成 分 按 某 种 组 成 抽 象 类 型 (ADT) ADT 是 一 个 值 的 集 合 和 定 义 在 这 个 值 集 上 的 一 组 操 作 的 总 称 包 括 : 原 子 类 型 固 定 聚 合 类 型 和 可 变 聚 合 类 型 24 12
25 操 作 描 述 的 基 本 操 作 : 插 入 : 在 的 指 定 位 置 添 加 新 的 元 素 删 除 : 去 掉 中 某 个 指 定 的 元 素 更 新 : 改 变 中 某 个 元 素 的 值 查 找 : 在 中 寻 找 某 个 满 足 特 定 要 求 的 元 素 排 序 : 重 新 安 排 元 素 的 逻 辑 顺 序 关 系, 使 值 按 从 小 到 大 或 从 大 到 小 的 顺 序 排 列 26 操 作 的 分 类 加 工 型 操 作 操 作 改 变 了 ( 操 作 前 的 ) 的 值 引 用 型 操 作 不 改 变 值, 只 是 查 询 或 求 得 的 值 操 作 的 描 述 13
27 1. 3 抽 象 类 型 的 表 示 与 实 现 语 言 的 描 述 预 定 义 常 量 和 类 型 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERROR 0 Status 是 函 的 类 型, 其 值 是 函 果 状 态 代 码 typedef int Status; 的 表 示 用 类 型 定 义 (typedef) 描 述, 元 素 类 型 约 定 为 ElemType, 可 以 是 C 语 言 中 任 何 类 型 28 基 本 操 作 的 算 法 用 以 下 形 式 函 来 描 述 函 类 型 函 名 ( 函 参 表 ) { // 算 法 说 明 语 句 序 列 } // 函 名 C 语 言 中 操 作 的 描 述 赋 值 语 句 循 环 语 句 选 择 语 句 注 释 束 语 句 输 入 和 输 出 语 句 逻 辑 运 算 约 定 14
29 1. 4 算 法 与 算 法 分 析 算 法 : 是 对 特 定 问 题 求 解 步 骤 的 一 种 描 述, 是 指 令 的 有 限 序 列 一 个 算 法 就 是 一 个 有 穷 规 则 的 集 合, 规 则 规 定 了 解 决 某 特 定 问 题 的 运 算 序 列 算 法 的 特 性 : 有 穷 性 确 定 性 可 行 性 输 入 输 出 30 算 法 设 计 的 两 个 目 标 易 读 易 编 码 和 调 试 ( 软 件 工 程 ) 充 分 利 用 计 算 机 资 源 ( 算 法 和 ) 算 法 的 设 计 要 求 正 确 性 : 程 序 不 含 语 法 错 误 ; 程 序 对 于 几 组 输 入 能 够 得 出 满 足 要 求 的 果 ; 程 序 对 于 精 心 选 择 的 典 型 苛 刻 的 输 入 能 够 得 出 满 足 要 求 的 果 ; 程 序 对 于 一 切 合 法 的 输 入 都 能 够 得 出 满 足 要 求 的 果 可 读 性 健 壮 性 效 率 与 低 存 储 量 要 求 15
最 佳 最 差 平 均 情 况 分 析 对 于 不 同 的 输 入 情 况, 算 法 的 时 间 代 价 不 同 例 如 : 在 一 个 组 中 查 找 元 素 K 分 为 最 佳 最 差 平 均 情 况 分 析 31 32 算 法 效 率 的 度 量 算 法 效 率 需 通 过 该 算 法 编 制 的 程 序 在 计 算 机 上 运 行 所 消 耗 的 时 间 多 少 以 及 所 需 辅 助 空 间 的 大 小 来 度 量 频 度 : 某 语 句 重 复 执 行 的 次 时 间 复 杂 度 : 从 算 法 中 选 取 一 个 对 于 所 研 究 的 问 题 来 说 是 基 本 操 作 的 源 操 作, 以 该 基 本 操 作 重 复 执 行 的 次 作 为 算 法 的 时 间 量 度 T(n)= O(f(n)) 它 表 示 随 着 n 的 增 大, 算 法 执 行 时 间 的 增 长 率 和 f ( n ) 的 增 长 率 相 同 16
空 间 复 杂 度 : 一 个 上 机 执 行 的 程 序 除 了 需 要 存 储 空 间 来 积 存 本 身 所 用 指 令, 常, 变 量 和 输 入 外, 也 需 要 一 些 对 进 行 操 作 的 工 作 单 元 和 存 储 一 些 实 现 计 算 所 需 信 息 的 辅 助 空 间 辅 助 空 间 的 大 小 反 映 了 该 算 法 的 空 间 复 杂 性 S(n)= O(f(n)) 33 34 大 O 表 示 法 的 运 算 规 则 单 位 时 间 简 单 布 尔 或 算 术 运 算 赋 值 简 单 I/O 函 返 回 加 法 规 则 : f1(n)+f2(n)=(max(f1(n), f2(n))) If, switch 乘 法 规 则 : f1 (n) f2(n) = (f1(n) f2(n)) for, while, do-while 17
例 1: 求 下 面 程 序 的 时 间 复 杂 度 35 程 序 段 一 : { ++x; s=0; } 程 序 段 二 : for(i=1;i<=n;++i) { ++x; s+=x; } 程 序 段 三 : for(j=1;j<=n;++j) for(k=1;k<=n;++k) { ++x; s+=x; } 该 程 序 中 ++x 是 基 本 操 作 语 句, 其 频 度 为 1, 其 时 间 复 杂 度 为 O(1), 为 常 量 阶 该 程 序 中 ++x 是 基 本 操 作 语 句, 其 频 度 为 n, 其 时 间 复 杂 度 为 O(n), 为 线 性 阶 该 程 序 中 ++x 是 基 本 操 作 语 句, 其 频 度 为 n 2, 其 时 间 复 杂 度 为 O(n 2 ), 为 平 方 阶 36 Ex( ) { int i, j, t ; (1) for( i=1 ; i<10 ; i++) (2) printf( \n %d, i ); (3) for(i=1; i<=2; i++) (4) printf( \n ); (5) for(i=1; i<=9; i++){ (6) for(j=1; j <= i ; j++) (7) { t = i * j ; printf( %5d,t); } (8) for(j=1; j<3 ; j++) (9) printf( \n ); } } 分 析 程 序 中 各 语 句 的 频 度 课 堂 作 业 18
37 Ex( ) { int i, j, t ; (1) for( i=1 ; i<10 ; i++) //n =10 (2) printf( \n %d, i ); //n =9 (3) for(i=1; i<=2; i++) //n =3 (4) printf( \n ); //n =2 (5) for(i=1; i<=9; i++){ //n =10 (6) for(j=1; j <= i ; j++) //n =54 (7) { t = i * j ; printf( %5d,t); } //n =45 (8) for(j=1; j<3 ; j++) //n =27 (9) printf( \n ); } //n =18 } 38 x = 91 ; y = 100 ; while (y > 0) { if (x > 100) { x -= 10 ; y -- ; } else x ++ ; } 问 if 语 句 执 行 了 多 少 次?(1100) y-- 执 行 了 多 少 次?(100) x ++ 执 行 了 多 少 次?(1000) 19
运 行 时 间 估 计 例 : 假 设 CPU 每 秒 处 理 10 6 个 指 令, 对 于 输 入 规 模 为 n= 10 8 的 问 题, 时 间 代 价 为 T(n)=2n 2 的 算 法 要 运 行 多 长 时 间? 操 作 次 为 T(n)=T(10 8 )=2 (10 8 ) 2 =2 10 16 运 行 时 间 为 2 10 16 10 6 2 10 10 秒 每 天 有 86,400 秒, 因 此 需 要 231,480 天 (634 年 ) 39 例 : 假 设 CPU 每 秒 处 理 10 6 个 指 令, 对 于 输 入 规 模 为 n = 10 8 的 问 题, 时 间 代 价 为 T(n)=nlogn 的 算 法 要 运 行 多 长 时 间? 操 作 次 为 T(n)=T(10 8 )= 10 8 log10 8 =2.66 10 9 运 行 时 间 为 2.66 10 9 106 2.66 10 3 秒, 即 44.33 分 钟 40 20
41 42 规 定 时 间 内 能 解 决 的 问 题 规 模 假 设 CPU 每 秒 处 理 10 6 个 指 令, 则 每 小 时 能 够 解 决 的 最 大 问 题 规 模 T(n)/10 6 3600 对 T(n) = 2n 2 和 nlogn 即 2n 2 3600 10 6 n 42, 426 T(n) = nlogn 即 nlogn 3600 10 6 n 133, 000, 000 21
本 章 重 点 的 有 关 基 本 概 念 ; 的 类 型 : 逻 辑 和 物 理 ; 算 法 及 算 法 分 析 ( 算 法 评 价 ) 43 22