立 志 于 打 造 最 贴 近 考 生 实 际 的 辅 导 书 计 算 机 考 研 之 数 据 结 构 高 分 笔 记 率 辉 编 著 周 伟 张 浩 审 核 讨 论 群 :

Transcription

1

2 立 志 于 打 造 最 贴 近 考 生 实 际 的 辅 导 书 计 算 机 考 研 之 数 据 结 构 高 分 笔 记 率 辉 编 著 周 伟 张 浩 审 核 讨 论 群 :

3 前 言 在 计 算 机 统 考 的 四 门 专 业 课 中, 最 难 拿 高 分 的 就 是 数 据 结 构 但 是 这 门 课 本 身 的 难 度 并 不 是 考 生 最 大 的 障 碍, 真 正 的 障 碍 在 于 考 生 不 能 独 自 把 握 复 习 的 方 向 和 考 试 范 围 也 许 有 同 学 要 问 了, 我 们 不 是 有 大 纲 吗? 照 着 大 纲 去 复 习 不 就 可 以 了 吗? 表 面 上 看 是 这 样, 但 是 当 你 真 正 开 始 复 习 的 时 候 你 就 会 发 现, 其 实 大 纲 只 给 了 考 生 一 个 大 致 范 围, 有 很 多 地 方 是 模 糊 的, 这 些 模 糊 的 地 方 就 可 能 是 你 要 纠 结 的 地 方 比 如 大 纲 里 对 于 栈 和 队 列 的 考 查 中 有 这 么 一 条 : 栈 和 队 列 的 应 用 这 个 知 识 点 就 说 的 很 模 糊, 因 为 只 要 涉 及 到 栈 和 队 列 的 地 方, 都 是 其 应 用 的 范 畴, 这 时 考 生 该 怎 么 办 呢? 于 是 把 所 有 的 希 望 寄 托 于 参 考 书, 希 望 参 考 书 能 帮 助 我 们 理 解 大 纲 的 意 图 下 边 我 们 就 来 说 说 参 考 书 吧 参 考 书 分 两 种, 一 是 课 本, 二 是 与 课 本 配 套 的 辅 导 书 对 于 课 本, 考 生 用 的 最 多 的 就 是 严 版 的 数 据 结 构, 这 里 我 也 推 荐 大 家 把 这 本 书 选 作 考 研 辅 导 教 材 因 为 这 本 书 的 内 容 非 常 丰 富, 如 果 能 把 这 本 书 中 考 纲 要 求 的 章 节 理 解 透 彻 了, 参 加 考 研 没 有 任 何 问 题 但 是 这 个 过 程 是 漫 长 的, 除 非 本 科 阶 段 就 学 的 非 常 好 计 算 机 统 考 后, 专 业 课 四 门 加 上 公 共 课 三 门, 一 共 是 七 门 绝 大 数 考 生 复 习 的 时 间 一 般 也 就 六 个 月, 而 数 据 结 构 的 复 习 需 要 占 用 多 少 时 间, 我 不 算 大 家 也 清 楚 要 在 这 么 短 的 时 间 内 掌 握 严 版 数 据 结 构 上 考 纲 要 求 的 知 识 点, 基 本 上 是 不 可 能 的, 这 就 需 要 一 本 辅 导 书 来 依 照 大 纲 从 课 本 中 总 结 出 考 纲 要 求 的 知 识 点, 才 能 使 得 考 生 在 短 时 间 内 达 到 研 究 生 考 试 的 要 求 市 面 上 的 参 考 书 有 两 种, 一 种 是 四 合 一 的 辅 导 书, 比 如 大 家 熟 悉 的 复 旦 版 的, 山 东 人 民 出 版 社 出 版 的 等 等 另 一 种 是 分 册 的, 比 如 网 上 流 行 的 1800 题 以 及 其 第 二 版, 此 书 题 目 巨 多, 并 且 有 很 多 老 式 的 考 研 题, 有 些 算 法 设 计 题 的 答 案 是 Pascal 语 言 写 的 这 本 书 中 的 题 目 一 般 考 生 全 做 基 本 上 是 不 可 能 的, 挑 着 做 又 会 把 时 间 浪 费 在 选 题 上 不 可 否 认, 这 本 书 确 实 是 一 本 非 常 好 的 题 库, 但 是 考 生 直 接 拿 来 用 做 考 研 辅 导 书 却 不 太 合 适 还 有 一 本 书 叫 数 据 结 构 习 题 与 解 析, 作 者 是 李 春 葆, 上 边 总 结 了 一 些 考 研 所 需 知 识 点, 但 是 这 本 书 同 样 出 自 统 考 以 前, 也 不 完 全 适 应 新 大 纲 的 要 求 直 到 复 试 后, 第 一 次 见 到 周 伟 写 的 计 算 机 网 络 高 分 笔 记 样 稿, 经 过 半 天 的 研 读, 发 现 这 个 就 是 我 想 要 的, 如 果 这 种 写 作 风 格 用 在 数 据 结 构 我 相 信 一 定 是 最 畅 销 的 书 籍 辅 导 书 就 应 该 站 在 学 生 的 角 度 去 写, 特 别 像 数 据 结 构 这 门 比 较 难 深 入 的 课 所 以 我 决 定 加 入 周 伟 的 队 伍 一 起 来 完 成 一 本 真 正 意 义 站 在 学 生 角 度 去 写 的 数 据 结 构 辅 导 书 去 更 好 的 帮 助 考 生 在 最 短 的 时 间 内 去 掌 握 这 一 门 课 这 也 是 我 写 这 本 辅 导 书 最 主 要 的 动 机 接 下 来 我 详 细 讲 解 一 下 这 本 辅 导 书 书 的 写 作 过 程, 请 看 下 图 :

4 图 中 所 涉 及 的 书 都 是 大 家 很 熟 悉 的 吧 当 年 这 些 书 我 都 买 了, 花 了 很 大 心 思 才 从 中 找 出 在 考 研 战 场 上 真 正 有 用 的 东 西 比 如 1800 题, 里 边 有 好 题, 有 废 题, 我 当 时 多 么 渴 望 有 人 能 在 我 复 习 之 前 就 帮 我 从 中 去 掉 重 复 的 题 目, 选 出 大 纲 要 求 的 题 目, 并 能 把 解 答 写 的 更 通 俗 易 懂 点, 可 是 当 时 没 有 人 这 么 做, 而 我 们 所 做 的 工 作 就 是 从 这 1800 题 中 选 出 了 大 纲 要 求 的 题 目, 并 且 修 正 了 部 分 解 答, 使 其 更 容 易 理 解, 我 想 这 也 是 你 们 很 想 要 的 吧 其 次 是 严 版 的 数 据 结 构 写 的 过 于 严 谨, 语 言 表 述 过 于 专 业, 对 于 基 础 稍 差 的 同 学 来 说 读 起 来 十 分 费 力, 要 很 长 时 间 才 能 适 应 这 本 书 的 写 作 风 格 我 当 时 就 是 在 这 本 书 中 痛 苦 的 挣 扎 了 很 久, 看 第 三 遍 的 时 候 才 真 正 的 可 以 说 适 应 了, 何 苦 这 样 呢? 如 果 当 时 有 一 本 辅 导 书 帮 我 把 那 些 复 杂 程 序 的 执 行 过 程, 拗 口 的 专 业 术 语, 令 人 头 大 的 符 号, 翻 译 成 容 易 理 解 的 语 言, 我 就 可 以 节 省 很 多 时 间, 可 惜 当 时 也 没 有 而 我 们 所 做 的 就 是 根 据 自 己 复 习 的 经 验, 以 及 对 这 本 书 的 理 解, 把 其 中 考 试 不 需 要 的 内 容 删 掉, 把 需 要 的 内 容 经 过 改 造 变 成 一 般 学 生 容 易 接 受 的 形 式 对 于 李 版 的 习 题 与 解 析 我 也 做 了 类 似 的 处 理 并 且, 我 在 本 书 中 穿 插 讲 解 了 一 些 考 纲 中 没 有 明 文 规 定 但 是 很 多 算 法 题 目 中 大 量 用 到 得 算 法 设 计 课 程 中 的 思 想, 来 帮 助 大 家 提 高 解 算 法 设 计 题 的 能 力, 比 如 搜 索 ( 打 印 图 中 两 节 点 之 间 的 所 有 路 径 ), 分 治 法 ( 二 分 法 排 序 求 树 的 深 度 等 等 ) 等 算 法 思 想 因 此 我 相 信 这 本 书 会 给 你 的 考 研 复 习 带 来 很 大 的 帮 助

5 本 书 特 点 : (1) 精 心 挑 选 出 适 合 考 研 的 习 题, 并 配 上 通 俗 易 懂 的 答 案 供 你 自 测 和 练 习 (2) 总 结 出 考 研 必 备 知 识 点, 并 且 帮 你 把 其 中 过 于 专 业 过 于 严 谨 的 表 述 翻 译 成 通 俗 易 懂 的 语 言 (3) 针 对 于 近 年 数 据 结 构 大 题 的 出 题 风 格 ( 比 如 算 法 设 计 题 目 中 的 三 段 式 题 目 :1. 表 述 算 法 思 想 2. 写 出 算 法 描 述 3. 计 算 算 法 的 时 间 和 空 间 复 杂 度 ), 设 计 了 独 特 的 真 题 仿 造 部 分, 让 你 在 复 习 的 过 程 中 逐 渐 养 成 适 合 解 决 考 研 类 型 题 目 的 习 惯 听 我 说 了 这 么 多 之 后, 很 多 学 生 现 在 想 问, 我 只 看 你 这 本 书 够 不 够? 还 需 要 自 己 准 备 其 他 书 吗? 对 于 这 个 问 题, 我 用 下 图 来 回 答

6 从 图 中 可 以 看 到, 如 果 你 只 看 本 书, 你 能 达 到 考 研 要 求 水 平 的 95% 左 右, 为 什 么 是 这 样, 因 为 今 年 大 纲 还 没 有 公 布, 所 以 我 不 敢 保 证 我 的 书 涵 盖 大 纲 所 有 内 容 但 是 数 据 结 构 中 的 经 典 内 容 本 书 已 经 全 部 包 括, 再 加 上 对 统 考 这 两 年 大 纲 范 围 的 解 读, 估 计 今 年 大 纲 变 化 不 会 太 大, 毕 竟 数 据 结 构 是 一 门 经 典 科 目, 因 此 考 研 对 这 一 门 科 的 考 察 范 围 较 为 稳 定 从 图 中 同 样 可 以 看 出, 掌 握 了 严 版 数 据 结 构 你 可 以 至 少 掌 握 比 考 试 范 围 多 出 30% 的 内 容, 但 是 这 需 要 花 很 多 时 间, 并 不 可 行 因 此 在 这 里 我 建 议 大 家 先 看 本 书, 把 重 要 知 识 点 先 拿 到 手, 然 后 把 严 版 数 据 结 构 当 做 字 典 来 用, 等 正 式 大 纲 出 来 之 后 进 行 查 缺 补 漏, 这 是 一 种 较 为 高 效 的 复 习 方 法 这 本 书 不 仅 涵 盖 了 考 纲 绝 大 部 分 内 容, 更 重 要 的 是 它 会 帮 助 你 理 解 大 纲, 理 解 出 题 人 的 思 路, 这 样 你 就 会 白 哪 一 类 的 题 目 有 可 能 考, 哪 一 类 的 题 目 不 会 考, 慢 慢 的, 你 复 习 的 方 向 感 会 越 来 越 明 确, 效 率 会 越 来 越 高 本 书 作 者

7 第 一 章 绪 论 针 对 考 研 数 据 结 构 的 代 码 书 写 规 范 以 及 C&C++ 语 言 基 础 考 研 综 合 应 用 题 中 算 法 设 计 部 分 的 代 码 书 写 规 范 考 研 中 的 C&C++ 语 言 基 础 杂 谈 算 法 的 时 间 复 杂 度 与 空 间 复 杂 度 分 析 基 础 考 研 中 的 算 法 时 间 复 杂 度 杂 谈 例 题 选 讲 考 研 中 的 算 法 空 间 复 杂 度 分 析 数 据 结 构 和 算 法 的 基 本 概 念 数 据 结 构 的 基 本 概 念 算 法 的 基 本 概 念 习 题 心 选 习 题 心 讲 第 二 章 线 性 表 线 性 表 的 基 本 概 念 与 实 现 线 性 表 的 基 本 操 作 线 性 表 的 定 义 顺 序 表 的 算 法 操 作 单 链 表 的 算 法 操 作 双 链 表 的 算 法 操 作 循 环 链 表 的 算 法 操 作 真 题 仿 造 真 题 仿 造 答 案 与 讲 解 习 题 心 选 习 题 心 讲 第 三 章 栈 队 列 和 数 组 栈 和 队 列 的 基 本 概 念 栈 的 基 本 概 念 队 列 的 基 本 概 念 栈 和 队 列 的 存 储 结 构 算 法 与 应 用 本 章 所 涉 及 的 数 据 结 构 定 义 顺 序 栈 的 基 本 算 法 操 作 链 栈 的 基 本 算 法 操 作 栈 的 应 用 顺 序 队 的 算 法 操 作 链 队 的 算 法 操 作 特 殊 矩 阵 的 压 缩 存 储 真 题 仿 造 真 题 仿 造 答 案 与 讲 解 : 习 题 心 选 习 题 心 讲 第 四 章 树 和 二 叉 树 树 的 基 本 概 念

8 4.1.1 树 的 定 义 树 的 基 本 术 语 树 的 存 储 结 构 二 叉 树 二 叉 树 的 定 义 二 叉 树 的 主 要 性 质 二 叉 树 的 存 储 结 构 二 叉 树 的 遍 历 算 法 线 索 二 叉 树 的 基 本 概 念 和 构 造 树 和 森 林 孩 子 兄 弟 存 储 结 构 森 林 与 二 叉 树 的 转 换 树 和 森 林 的 遍 历 树 与 二 叉 树 的 应 用 二 叉 排 序 树 与 平 衡 二 叉 树 哈 夫 曼 树 和 哈 夫 曼 编 码 真 题 仿 造 真 题 仿 造 答 案 与 解 析 : 习 题 心 选 习 题 心 讲 第 五 章 图 图 的 基 本 概 念 图 的 存 储 结 构 邻 接 矩 阵 邻 接 表 图 的 遍 历 算 法 操 作 深 度 优 先 搜 索 遍 历 (DFS) 广 度 优 先 搜 索 遍 历 (BFS) 例 题 选 讲 最 小 ( 代 价 ) 生 成 树 普 里 姆 算 法 和 克 鲁 斯 卡 尔 算 法 例 题 选 讲 最 短 路 径 迪 杰 斯 特 拉 算 法 弗 洛 伊 德 算 法 拓 扑 排 序 AOV 网 拓 扑 排 序 例 题 选 讲 关 键 路 径 AOE 网 关 键 路 径 真 题 仿 造 真 题 仿 造 答 案 解 析 :

9 习 题 心 选 习 题 心 讲 第 六 章 内 部 排 序 排 序 的 基 本 概 念 排 序 稳 定 性 排 序 算 法 的 分 类 插 入 类 排 序 直 接 插 入 排 序 折 半 插 入 排 序 交 换 类 排 序 起 泡 排 序 快 速 排 序 选 择 类 排 序 简 单 选 择 排 序 堆 排 序 二 路 归 并 排 序 基 数 排 序 排 序 知 识 点 小 结 : 真 题 仿 造 真 题 仿 造 答 案 与 解 析 : 习 题 心 选 习 题 心 讲 第 七 章 查 找 查 找 的 基 本 概 念 顺 序 查 找 法 折 半 查 找 法 查 找 的 基 本 概 念 顺 序 查 找 法 折 半 查 找 法 二 叉 排 序 树 平 衡 二 叉 树 二 叉 排 序 树 平 衡 二 叉 树 B- 树 及 其 基 本 操 作 B+ 树 的 基 本 概 念 B- 树 的 基 本 概 念 B- 树 的 基 本 操 作 散 列 (Hash) 表 散 列 (Hash) 表 的 概 念 散 列 (Hash) 表 的 建 立 方 法 以 及 冲 突 解 决 方 法 散 列 (Hash) 表 的 性 能 分 析 真 题 仿 造 真 题 仿 造 答 案 与 解 析 : 习 题 心 选 习 题 心 讲 年 计 算 机 考 研 试 题 年 计 算 机 考 研 试 题

10 第 一 章 绪 论 作 者 的 话 : 大 部 分 同 学 在 学 习 数 据 结 构 时, 想 必 对 数 据 结 构 课 本 里 的 伪 代 码 多 多 少 少 有 点 不 是 很 清 楚, 特 别 是 自 己 在 动 手 编 写 算 法 的 时 候, 明 明 知 道 算 法 的 思 路, 但 是 编 写 出 来 的 程 序 就 是 不 标 准, 可 能 在 考 试 的 时 候 就 会 吃 大 亏 所 以 在 开 始 数 据 结 构 的 旅 程 之 前, 我 觉 得 有 必 要 将 一 些 基 本 功 提 前 告 知 你 们, 掌 握 了 这 些 东 西, 在 本 章 以 后 的 章 节 中, 才 能 以 此 为 基 础 来 修 炼 更 高 深 的 武 功 本 章 概 略 针 对 考 研 数 据 结 构 的 C&C++ 语 言 基 础 以 及 代 码 书 写 规 范 对 于 考 研 数 据 结 构, 需 要 C 与 C++ 语 言 作 为 基 础, 但 是 又 不 需 要 太 多, 因 此 此 处 讲 解 有 针 对 性 现 在 我 们 面 临 的 是 研 究 生 考 试, 要 在 答 题 纸 上 写 代 码, 代 码 的 评 判 者 是 阅 卷 老 师, 而 不 是 TC,VC6.0 等 编 译 器 如 果 之 前 你 只 熟 悉 在 这 些 编 译 器 下 写 代 码, 那 你 要 看 看 这 一 部 分, 这 里 教 你 怎 么 快 速 的 写 出 能 让 阅 卷 老 师 满 意 的 代 码 算 法 的 时 间 复 杂 度 分 析 基 础 为 什 么 要 特 别 注 重 这 一 块 的 讲 解? 在 09 年 批 阅 数 据 结 构 算 法 那 道 题 的 时 候, 由 于 当 时 阅 卷 的 标 准 答 案 是 教 育 部 给 出 的, 并 且 明 确 说 明 以 此 为 标 准 答 案, 但 是 教 育 部 给 出 的 算 法 时 间 复 杂 度 太 大, 对 于 算 法 有 研 究 的 同 学, 可 以 很 轻 松 的 写 出 一 个 算 法, 并 且 时 间 复 杂 度 远 远 小 于 标 准 答 案 教 育 部 就 是 权 威, 没 有 办 法, 只 能 按 照 教 育 部 的 答 案 改, 这 样 就 导 致 了 算 法 牛 人 写 出 更 完 美 的 算 法, 却 得 了 最 低 的 分 也 许 是 为 了 避 免 这 种 不 公 平 的 再 次 出 现,10 年 的 考 试 要 求 终 于 改 了, 考 生 必 须 对 自 己 写 的 算 法 给 出 时 间 复 杂 度 和 空 间 复 杂 度, 并 以 此 来 作 为 评 分 的 依 据 所 以 这 已 经 成 为 数 据 结 构 45 分 里 面 的 必 考 内 容, 这 一 点 的 考 察 在 图 排 序 查 找 这 三 章 内 体 现 的 尤 为 明 显, 因 此 我 会 在 本 章 先 总 体 讲 一 下 算 法 时 间 复 杂 度 分 析 的 基 本 方 法, 并 在 以 后 章 节 中 以 题 目 的 形 式 讲 一 些 具 体 分 析 思 路, 这 样 考 生 逐 渐 的 就 会 掌 握 考 研 要 求 的 算 法 复 杂 度 分 析 方 法 数 据 结 构 和 算 法 的 基 本 概 念 这 一 部 分 介 绍 一 些 贯 穿 于 整 本 书 的 基 本 概 念 1.1 针 对 考 研 数 据 结 构 的 代 码 书 写 规 范 以 及 C&C++ 语 言 基 础 考 研 综 合 应 用 题 中 算 法 设 计 部 分 的 代 码 书 写 规 范 要 在 答 题 纸 上 快 速 的 写 出 能 让 阅 卷 老 师 满 意 的 代 码, 是 有 些 技 巧 的, 这 与 写 出 能 在 编 译 器 上 编 译 通 过 的 代 码 有 所 不 同 为 了 说 明 这 一 点 我 们 首 先 看 一 个 例 题 : 设 将 n(n>1) 个 整 数 存 放 到 一 维 数 组 R 中 设 计 一 个 算 法, 将 R 中 的 序 列 循 环 左 移 P ( 0<P<n ) 个 位 置, 即 将 R 中 的 数 据 由 X 0,X 1...X n-1 变 换 为

11 X p,x p-1,...,x n-1,x 0,X 1...X p-1 要 求 : 写 出 本 题 的 算 法 描 述 分 析 : 本 题 不 难, 要 实 现 R 中 序 列 循 环 左 移 P 个 位 置, 只 需 先 将 R 中 前 P 个 元 素 逆 置, 再 将 剩 下 的 元 素 逆 置, 最 后 将 R 中 所 有 的 元 素 再 整 体 做 一 次 逆 置 操 作 即 可 本 题 算 法 描 述 如 下 : #include<iostream> //1 #define N 50 //2 using namespace std; //3 void Reverse(int R[],int l,int r) //4 //5 int i,j; //6 int temp; //7 for(i=l,j=r;i<j;i++,j--) //8 //9 temp=r[i]; //10 R[i]=R[j]; //11 R[j]=temp; //12 //13 //14 void RCR(int R[],int n,int p) //15 //16 if(p<=0 p>=n) //17 cout<<"error"<<endl; //18 else //19 //20 Reverse(R,0,p-1); //21 Reverse(R,p,n-1); //22 Reverse(R,0,n-1); //23 //24 //25 int main() //26 //27 int L,i; //28 int R[N],n; //29 cin>>l; //30 cin>>n; //31 for(i=0;i<=n-1;i++) //32 cin>>r[i]; //33 RCR(R,n,L); //34 for(i=0;i<=n-1;i++) //35 cout<<r[i]<<" "; //36 cout<<endl; //37 return 0; //38 //39 以 上 程 序 段, 是 一 段 完 整 的 可 以 在 编 译 器 下 编 译 运 行 的 程 序, 程 序 比 较 长, 对 于 考 试 答 卷, 完 全 没 有 必 要 这 么 写 第 1 和 3 句, 在 我 们 大 学 里 写 的 程 序 中, 几 乎 都 要 用 到, 是 耳 熟 能 详 的, 研 究 生 考 试 这 种 选 拔 考 试 不 会 用 这 种 东 西 来 区 分 学 生 的 优 劣, 因 此 答 题 过 程 中 没 必 要 写, 去 掉 第 2 句, 定 义 了 一 个 常 量, 如 果 你 的 题 目 中 要 用 一 个 常 量, 在 你 用 到 的 地 方 加 上 一 句 注 释, 说 明 某 某 常 量 之 前 已 经 定 义 即 可 而 没 必 要 再 跑 到 前 边 去 补 上 一 句 #define XX XX, 因 为 试 卷 的 答 题 纸, 不 是 编 译 器, 插 入 语 句 不 是 那 么 方 便, 为 了 考 试 的 时 候 节 省 时 间 且 使 得 试 卷 整 洁, 这 是 最 好 的 解 决 办 法, 因 此 第 2 句 去 掉 第 26 到 第 39 是 主 函 数 部 分, 你 之 前 声 明 的 函 数 ( 第 4 到 第 25 句 ) 在 这 里 调 用 在 答 题 中, 我 们 只 需 要 写 出 自 己 的 函 数 说 明 (4 到 25 句 ), 写 清 楚 函 数 的 接 口 ( 何 为 接 口, 下

12 边 会 细 致 讲 解 ) 即 可, 答 卷 老 师 就 知 道 你 已 经 做 好 了 可 以 解 决 这 个 题 目 的 工 具 ( 即 函 数 ) 并 且 说 明 了 工 具 的 使 用 方 法 ( 即 函 数 接 口 ), 这 样 别 人 就 会 用 这 个 工 具 来 解 决 问 题, 而 没 必 要 你 把 它 用 给 别 人 看 ( 主 函 数 中 的 调 用, 就 是 用 这 个 函 数 解 决 问 题 的 过 程 ), 因 此 第 26 到 第 39 句 可 以 去 掉 经 过 以 上 删 减, 就 是 以 下 程 序 段 了, 看 着 是 不 是 简 洁 了 很 多? void Reverse(int R[],int l,int r) //1 //2 int i,j; //3 int temp; //4 for(i=l,j=r;i<j;i++,j--) //5 //6 temp=r[i]; //7 R[i]=R[j]; //8 R[j]=temp; //9 //10 //11 void RCR(int R[],int n,int p) //12 //13 if(p<=0 p>=n) //14 cout<<"error"<<endl; //15 else //16 //17 Reverse(R,0,p-1); //18 Reverse(R,p,n-1); //19 Reverse(R,0,n-1); //20 //21 //22 这 里 来 说 一 下 函 数 的 接 口 假 如 上 述 函 数 是 一 台 机 器, 可 以 用 原 材 料 来 加 工 成 成 品 那 么 接 口 就 可 以 理 解 成 原 材 料 的 入 口, 或 成 品 的 出 口 比 如 上 述 成 序 语 段 的 第 12 句 :RCR(int R[],int n,int p) 就 包 含 一 个 接 口, 它 是 原 材 料 的 一 个 入 口 括 号 里 所 描 述 的 就 是 原 材 料 类 型 以 及 名 称, 是 将 来 函 数 被 调 用 的 时 候 所 要 放 进 去 的 东 西 ; 是 在 告 诉 别 人, 我 要 三 个 原 材 料, 第 一 个 是 个 int 型 的 数 组 ; 第 二 个 是 一 个 int 型 的 变 量 ; 第 三 个 也 是 一 个 int 型 的 变 量 第 15 句,cout<<"ERROR"<<endl; 也 是 一 个 接 口, 它 会 在 输 出 设 备 上 打 印 出 一 个 ERROR, 用 来 提 示 用 户 这 里 出 错 了, 这 算 是 成 品 的 出 口, 这 里 的 成 品 就 是 一 个 提 示 同 时, 第 1 句 中 传 入 int 型 数 组 的 地 方 也 可 以 理 解 为 一 个 产 品 的 出 口, 因 为 从 这 里 传 入 的 数 组 的 内 容, 将 在 函 数 执 行 完 后 被 加 工 成 我 们 想 要 的 内 容 通 过 以 上 说 明 我 们 可 以 把 接 口 理 解 为 用 户 和 函 数 打 交 道 的 地 方, 通 过 接 口, 用 户 输 入 了 自 己 的 数 据, 得 到 了 自 己 想 要 的 结 果 到 这 里 我 们 可 以 知 道 考 研 综 合 应 用 中 算 法 设 计 题 中 的 代 码 部 分 重 点 需 要 写 哪 些 内 容 了, 即 只 需 写 出 一 个 或 多 个 可 以 解 决 问 题 的 有 着 清 楚 接 口 描 述 的 函 数 即 可 考 研 中 的 C&C++ 语 言 基 础 杂 谈 之 所 以 这 个 标 题 是 C&C++ 语 言, 而 不 是 单 一 的 一 种, 是 因 为 本 书 有 些 程 序 的 书 写 包 含 了 两 者 的 语 法 对 于 考 试 答 题 来 说,C++ 不 因 为 它 是 C 语 言 的 升 级 版 就 能 取 代 C C 和 C++ 是 各 有 所 长 的, 我 们 从 两 者 中 挑 选 出 来 对 考 研 答 卷 有 利 的 部 分, 组 合 起 来 应 用 下 边 就 来 具 体 介 绍 针 对 考 研 数 据 结 构 的 C 和 C++ 语 言 基 础 1. 数 据 类 型 对 于 基 本 的 数 据 类 型, 例 如 : 整 型 int,long, ( 考 研 中 涉 及 到 处 理 整 数 的 题 目 如 果 没 有 特 别 要 求 用 int 足 够 了 ), 字 符 型 char, 浮 点 型 float,double ( 对 于 处 理 小 数 的 问 题, 题 目 没 有 特 殊 要 求 的 请 况 下 用 float 就 足 够 了 ) 这 些 大 家 大 都 了 解, 就 不 再

13 具 体 讲 解, 这 里 主 要 讲 解 的 是 结 构 型 和 指 针 型 (1) 结 构 型 : 所 谓 结 构 型, 说 的 通 俗 点 就 是 用 户 自 己 制 作 的 数 据 类 型 其 实 我 们 常 用 的 数 组 也 是 用 户 自 己 制 作 的 数 据 类 型, 数 组 是 多 个 相 同 数 据 类 型 的 变 量 组 合 起 来 的, 比 如 下 边 这 句 int a[max];//max 是 已 经 定 义 的 常 量 就 定 义 了 一 个 数 组, 名 字 为 a 其 实 就 是 连 续 申 请 了 MAX 个 整 型 变 量 摆 在 一 起, 其 中 各 整 型 变 量 之 间 的 位 置 关 系 通 过 数 组 下 标 来 反 映, 这 不 难 理 解 如 果 我 想 制 作 一 个 这 样 的 数 组, 第 一 个 变 量 是 整 形 变 量, 第 二 个 变 量 是 字 符 型 变 量, 第 三 个 变 量 是 浮 点 型 变 量, 怎 么 办 呢? 这 里 就 用 到 结 构 体 了, 结 构 体 就 是 系 统 提 供 给 程 序 员 制 作 新 的 数 据 类 型 的 一 种 机 制, 即 可 以 用 系 统 已 经 有 的 不 同 的 基 本 数 据 类 型 或 用 户 定 义 的 结 构 型, 组 合 成 用 户 需 要 的 复 杂 数 据 类 型 比 如 上 边 提 到 的 要 制 作 一 个 由 不 同 类 型 的 变 量 组 成 的 数 组 可 以 这 么 构 造 : typedef struct int a; char b; float c; TypeA; 上 边 的 语 句 制 造 了 一 个 新 的 数 据 类 型,TypeA 型 int b[3]; 申 请 了 一 个 数 组, 名 字 为 b, 由 3 个 整 形 的 分 量 组 成 而 TypeA a; 同 样 可 以 认 为 申 请 了 一 个 数 组, 名 为 a, 只 不 过 组 成 a 数 组 的 3 个 分 量 是 不 同 类 型 的 对 于 数 组 b,b[0],b[1],b[2] 分 别 代 表 数 组 中 第 一, 第 二, 第 三 个 元 素 的 值 而 对 于 结 构 体 a,a.a,a.b,a.c 分 别 对 应 于 结 构 体 变 量 a 中 第 一, 第 二, 第 三 个 元 素 的 值, 两 者 十 分 相 似 再 看 这 样 一 个 定 义 TypeA a[3]; 这 句 定 义 了 一 个 数 组, 由 三 个 TypeA 型 的 元 素 组 成 前 边 我 们 知 道 TypeA 是 结 构 型, 它 含 有 3 个 分 量 ( 其 实 应 该 叫 做 结 构 体 的 成 员, 这 里 为 了 类 比, 将 它 叫 做 分 量 ), 因 此 a 数 组 中 的 每 个 元 素 都 是 结 构 型 且 每 个 元 素 都 有 3 个 分 量, 它 可 以 类 比 为 哪 一 种 数 组 呢? 显 然 我 们 可 以 把 它 类 比 成 一 个 二 维 数 组, 比 如 int b[3][3]; 定 义 了 一 个 名 字 为 b 的 二 维 数 组 二 维 数 组 可 以 看 成 其 数 组 元 素 是 一 维 数 组 的 一 维 数 组, 如 果 把 b 看 成 一 个 一 维 数 组 的 话, 其 中 的 每 个 数 组 元 素 都 有 3 个 分 量, 与 a 数 组 不 同 的 地 方 在 于,b 中 每 个 元 素 的 3 个 分 量 是 相 同 类 型 的, 而 a 数 组 中 每 个 元 素 的 三 个 分 量 是 不 同 数 据 类 型 的 b 数 组 取 第 一 个 元 素 的 第 一 个 分 量 的 值 的 写 法 为 b[0][0], 对 应 到 a 数 组 则 为 a[0].a 上 边 的 类 比 关 系 可 以 通 过 图 1.1 来 形 象 的 说 明

14 图 1.1 结 构 体 与 数 组 的 类 比 (2) 指 针 型 指 针 型 和 结 构 型 一 样, 是 比 较 难 理 解 的 部 分 对 于 其 他 类 型 的 变 量, 变 量 里 所 装 的 东 西 是 数 据 元 素 的 内 容, 而 指 针 型 变 量 内 部 装 的 是 变 量 的 地 址, 通 过 它 可 以 找 出 这 个 变 量 在 内 存 中 的 位 置, 就 像 一 个 指 示 方 向 的 指 针, 指 出 了 某 个 变 量 的 位 置, 因 此 叫 做 指 针 型 指 针 型 的 定 义 方 法 对 每 种 数 据 类 型 有 特 定 的 写 法 有 专 门 指 向 int 型 变 量 的 指 针, 有 专 门 指 向 char 型 变 量 的 指 针, 等 等 对 于 每 种 变 量, 指 针 的 定 义 方 法 有 相 似 的 规 则, 如 以 下 语 句 : int *a; // 对 比 一 下 定 义 int 型 变 量 的 语 句 : int a; char *b; // 对 比 一 下 定 义 char 型 变 量 的 语 句 : char b; float *c; // 对 比 一 下 定 义 float 型 变 量 的 语 句 :float c; TypeA *d; // 对 比 一 下 定 义 TypeA 型 变 量 的 语 句 :TypeA d; 上 边 四 句 分 别 定 义 了 指 向 整 型 变 量 的 指 针 a, 指 向 字 符 型 变 量 的 指 针 b, 指 向 浮 点 型 变 量 的 指 针 c, 和 指 向 TypeA 型 变 量 的 指 针 d 我 们 看 到 比 起 之 前 所 讲 其 他 变 量 的 定 义, 指 针 型 变 量 的 定 义 只 是 在 变 量 名 之 前 多 出 一 个 * 而 已 如 果 a 是 个 指 针 型 变 量, 且 它 已 经 指 向 一 个 变 量 b, 则 a 中 存 放 了 变 量 b 所 在 的 地 址 *a 就 是 取 变 量 b 的 内 容 (x=*a; 等 价 于 x=b;),&b 就 是 取 变 量 b 的 地 址, 语 句 a=&b; 就 是 将 变 量 b 的 地 址 存 于 a 中, 即 大 家 常 说 的 指 针 a 指 向 b 指 针 型 在 考 研 中 用 的 最 多 的 就 是 和 结 构 型 结 合 起 来 构 造 结 点 ( 如 链 表 的 结 点, 二 叉 树 的 结 点 ) 下 边 我 们 就 来 具 体 讲 讲 常 用 结 点 的 构 造, 这 里 的 构 造 我 们 就 把 它 理 解 成 先 定 义 一 个 结 点 的 结 构 类 型, 然 后 用 这 个 定 义 好 的 结 构 型 制 作 一 个 结 点 这 样 说 可 能 不 太 严 谨, 但 是 不 影 响 理 解 (3) 结 点 的 构 造 要 构 造 一 种 结 点, 必 须 先 定 义 结 点 的 结 构 类 型 下 边 描 述 了 链 表 结 点 和 二 叉 树 结 点 结 构 型 的 定 义 方 法 1) 链 表 结 点 的 定 义 链 表 的 结 点 有 两 个 域, 一 个 是 数 据 域, 用 来 存 放 数 据, 一 个 是 指 针 域, 用 来 存 放 下 一 个 结 点 的 位 置, 如 图 1.2 所 示 因 此, 链 表 的 结 构 型 定 义 如 下 : 图 1.2 链 表 节 点 typedef struct Node int data; // 这 里 默 认 的 是 int 型, 如 需 其 他 类 型 可 直 接 修 改 struct Node *next;// 指 向 Node 型 变 量 的 指 针 Node; 上 边 这 个 结 构 型 的 名 字 为 Node, 因 为 组 成 此 结 构 体 的 成 员 中 有 一 个 是 指 向 和 自 己 类 型 相 同 的 变 量 的 指 针, 所 以 内 部 要 用 自 己 来 定 义 这 个 指 针, 所 以 写 成 struct Node *next; 这 里 指 出, 凡 是 结 构 型 ( 假 设 名 为 a) 内 部 有 这 样 的 指 针 型 ( 假 设 名 为 b), 即 b 是 用 来 存

15 放 和 a 类 型 相 同 的 结 构 体 变 量 地 址 的 指 针 型 ( 如 图 1.2 中, 结 点 A 的 指 针 next,next 所 指 的 结 点 B 与 结 点 A 是 属 于 同 一 结 构 型 的 ), 则 在 定 义 a 的 typedef struct 语 句 之 后 都 要 加 上 a 这 个 结 构 型 的 名 字, 如 上 述 结 构 体 定 义 中 粗 体 的 Node 与 之 前 定 义 的 结 构 型 TypeA 进 行 比 较 一 下, 会 发 现 这 里 的 结 构 型 Node 在 定 义 方 法 上 的 不 同 有 的 书 上 在 把 上 述 链 表 结 点 结 构 定 义 写 成 如 下 形 式 : typedef struct node Node; 我 们 可 以 发 现, 有 一 个 node 和 一 个 Node, 即 结 构 体 定 义 中 的 上 下 两 个 名 称 不 同 其 实 对 于 考 研 来 说 这 样 写 除 了 增 加 记 忆 负 担 之 外, 就 没 别 的, 所 以 我 希 望 考 生 在 造 结 点 结 构 型 的 时 候, 上 下 写 成 一 致 的 名 称 2) 二 叉 树 节 点 的 定 义 在 链 表 结 点 结 构 型 的 基 础 上, 再 加 上 一 个 指 向 自 己 同 一 类 型 变 量 的 指 针 域 即 为 二 叉 树 结 点 结 构 型, 如 下 : typedef struct BTNode int data; struct BTNode *lchild; struct BTNode *rchild; BTNode; 在 考 研 数 据 结 构 中, 只 需 要 熟 练 掌 握 以 上 两 种 结 点 的 定 义 方 法, 其 他 的 结 点 都 是 由 这 两 种 衍 生 而 来 的 ( 其 实 二 叉 树 结 点 的 定 义 也 是 由 链 表 结 点 的 定 义 衍 生 而 来, 二 叉 树 结 点 只 不 过 比 链 表 结 点 多 了 一 个 指 针 而 已 ), 无 需 特 意 的 去 记 忆 说 明 : 对 于 结 构 型, 用 来 实 现 构 造 结 点 的 语 法 有 很 多 不 同 的 表 述, 我 们 完 全 没 必 要 全 部 掌 握 刚 刚 上 边 讲 到 的 那 些 语 法 用 来 构 造 结 点 已 经 足 够 用 了, 所 以 我 这 里 建 议 大 家, 熟 练 掌 握 以 上 两 种 构 造 结 点 的 结 构 体 定 义 的 写 法, 其 他 的 写 法 不 予 理 睬 有 些 语 法 对 我 们 考 试 来 说 复 杂 又 没 有 意 义, 比 如 上 边 二 叉 树 节 点 的 定 义 有 些 书 上 这 样 写 : typedef struct BTNode int data; struct BTNode *lchild; struct BTNode *rchild; BTNode,*btnode; 可 以 看 到 在 最 后 又 多 了 个 *btnode, 其 实 在 定 义 一 个 结 点 指 针 p 的 时 候,BTNode *p; 等 价 于 btnode p; 对 于 定 义 结 点 指 针,BTNode *p; 这 种 写 法 是 何 等 的 顺 理 成 章, 因 为 它 继 承 了 之 前 int *a;char *b;char *c;typea *d; 这 些 指 针 定 义 的 一 般 规 律, 使 得 我 们 记 忆 起 来 非 常 方 便, 何 苦 再 弄 个 btnode p; 这 种 写 法 来 增 加 不 必 要 的 记 忆 负 担 呢? 因 此 在 考 研 中 我 们 不 采 取 这 种 方 法, 对 于 上 边 的 结 构 体 定 义, 删 去 *btnode, 统 一 一 个 BTNode, 就 可 以 解 决 所 有 问 题 除 了 上 边 我 提 到 的 那 种 出 力 不 讨 好 的 写 法, 还 有 更 恶 心 且 没 用 的 写 法, 这 里 就 不 说 了,

16 总 之 本 书 的 目 的 就 是 要 帮 你 从 垃 圾 堆 里 挑 出 适 合 考 研 的 宝 贝 通 过 以 上 的 讲 解, 我 们 知 道 了 链 表 结 点 和 二 叉 树 结 点 的 定 义 方 法 结 构 型 定 义 好 之 后, 就 要 用 它 来 制 作 新 结 点 了 以 二 叉 树 结 点 的 制 作 为 例, 有 以 下 两 种 写 法 : 1 BTNode BT; 2 BTNode *BT; BT=(BTNode*)malloc(sizeof(BTNode));// 此 句 要 熟 练 掌 握 1 中 只 有 一 句 就 制 作 了 一 个 结 点, 而 2 中 需 要 两 句, 比 1 要 繁 琐, 但 是 考 研 中 用 的 最 多 的 是 2 2 的 执 行 过 程 是 这 样 : 先 定 义 一 个 结 点 的 指 针 BT, 然 后 用 malloc 函 数 来 申 请 一 个 结 点 的 内 存 空 间, 最 后 让 指 针 BT 指 向 这 片 内 存 空 间, 就 完 成 了 一 个 结 点 的 制 作 2 中 的 第 二 句 就 是 用 系 统 已 有 的 malloc() 函 数 申 请 新 结 点 所 需 内 存 空 间 的 方 法, 考 研 数 据 结 构 中 所 有 类 型 结 点 的 内 存 分 配 都 可 用 malloc() 来 完 成, 模 式 固 定, 容 易 记 忆 图 1.3 结 点 空 间 申 请 函 数 图 1.3 就 是 申 请 一 个 结 点 空 间, 并 用 一 个 指 针 ( 图 中 为 p) 指 向 这 个 空 间 的 标 准 模 板 考 生 需 要 将 这 个 模 板 背 下 来, 以 后 制 作 一 个 新 结 点 的 时 候, 只 要 把 结 点 结 构 型 的 名 称 填 入 上 图 括 号 的 空 白 处 即 可 这 个 语 法 是 C 语 言 就 有 的,C++ 语 言 还 有 其 他 方 法, 不 需 要 掌 握 那 么 多, 对 于 考 研 来 说 有 这 一 个 足 够 了 2 句 中 的 BT 是 个 指 针 型 变 量, 用 它 来 存 储 刚 制 作 好 的 结 点 的 地 址 因 BT 是 变 量, 虽 然 现 在 BT 指 向 了 刚 生 成 的 结 点, 但 是 在 以 后 必 要 的 时 候 BT 可 以 离 开 这 个 结 点 转 而 指 向 其 他 结 点 而 1 句 则 不 行,1 中 的 BT 就 是 某 个 结 点 的 名 字, 一 旦 定 义 好, 它 就 不 能 脱 离 这 个 结 点 从 这 里 就 看 到 2 比 1 更 灵 活, 因 此 2 用 的 多, 并 且 2 完 全 可 以 取 代 1(2 中 BT 的 值 不 改 变 的 话 就 相 当 于 1) 对 于 1 和 2 中 的 BT 取 分 量 的 操 作 也 是 不 同 的 对 于 1 如 果 我 想 取 其 data 域 的 值 付 给 x, 则 应 该 写 成 x=bt.data; 而 对 于 2 则 应 该 写 成 x=bt->data; 一 般 来 说, 用 结 构 体 变 量 直 接 取 分 量, 其 操 作 用., 用 指 向 结 构 体 变 量 的 指 针 来 取 分 量, 其 操 作 用 -> 这 里 再 扩 展 一 点, 前 边 我 们 提 到, 如 果 p 是 指 针 ( 假 设 已 经 指 向 x),*p 就 是 取 这 个 变 量 的 值,a=*p; 等 价 于 a=x; 那 么 对 于 2 中 的 BT 指 针, 怎 么 用. 来 取 其 data 值 呢? 类 比 p,*bt 就 是 BT 指 向 的 变 量, 因 此 可 以 写 成 (*BT).data;((*BT).data; 与 BT->data 是 等 价 的 ) 注 意 *BT 外 边 要 用 括 号 括 起 来, 不 要 写 成 *BT.data 在 C 或 C++ 语 言 中 这 是 一 种 好 的 习 惯, 在 你 不 知 道 系 统 默 认 的 运 算 符 优 先 级 的 情 况 下, 你 最 好 依 照 自 己 所 期 望 的 运 算 顺 序 加 上 括 号 有 可 能 这 个 括 号 加 上 是 多 余 的, 但 是 为 了 减 少 错 误, 这 种 做 法 是 必 要 的 对 于 与 刚 才 那 句, 我 所 期 望 的 运 算 顺 序 是 先 算 *BT, 即 用 * 先 将 BT 变 成 它 所 指 的 变 量, 然 后 再 用. 取 分 量 值 因 此 写 成 (*BT).data 比 如 这 样 一 个 式 子 a*b/c, 假 设 你 不 知 道 系 统 会 默 认 先 算 乘 再 算 除, 而 你 所 期 望 的 运 算 优 先 顺 序 是 先 算 乘 再 算 除, 为 了 减 少 错 误,

17 你 最 好 是 把 它 写 成 (a*b)/c, 即 便 这 里 的 括 号 是 多 余 的 (4) 关 于 typedef 和 #define 1)typedef 有 的 书 上 在 定 义 变 量 的 时 候 会 出 现 一 些 你 在 程 序 设 计 教 材 中 从 来 没 见 过 的 诡 异 的 数 据 类 型, 比 如 严 奶 奶 书 上 就 有 类 似 于 Elemtype A; 的 变 量 定 义 语 句, 这 里 的 Elemtype 是 什 么 类 型, 新 来 的 同 学 常 常 会 一 头 雾 水 要 说 明 这 个 问 题, 我 们 先 来 说 明 一 下 typedef 的 用 法 一 句 话,typedef 就 是 用 来 给 现 有 的 数 据 类 型 起 一 个 新 名 字 的, 我 们 在 结 构 类 型 定 义 时 用 到 过, 如 typedef struct TypeA; 即 为 给 struct 起 了 一 个 名 字 TypeA, 就 好 比 你 制 作 了 计 算 机 中 的 整 型, 给 他 起 了 个 名 字 为 int 并 且 如 果 我 想 给 int 型 起 个 新 名 字 A, 就 可 以 这 样 写 typedef int A; 这 样 的 话 定 义 一 个 整 形 变 量 x 的 时 候 A x; 就 等 价 于 int x; 在 考 研 中 typedef 用 的 最 多 的 地 方 就 在 结 构 型 的 定 义 过 程 中, 其 他 的 地 方 几 乎 不 用 你 可 以 这 样 理 解 typedef 是 用 来 起 名 字 的, 新 定 义 的 结 构 型 没 有 名 字, 因 此 用 typedef 给 它 起 个 名 字 是 有 必 要 的, 但 是 对 于 已 有 的 数 据 类 型, 如 int,float 等 已 经 有 了 简 洁 的 名 字, 还 有 必 要 给 它 起 个 新 名 字 吗? 有 必 要, 但 不 是 在 考 研 数 据 结 构 中 为 什 么 有 必 要, 有 兴 趣 的 同 学 可 以 去 查 下 资 料, 查 完 你 会 发 现,typedef 对 程 序 设 计 的 贡 献 很 大, 但 是 对 于 考 研 答 卷, 用 处 不 大, 所 以 大 家 对 其 用 法 不 必 深 究 说 到 这 里 大 家 就 明 白 了, 严 奶 奶 的 书 上 之 所 以 有 那 么 多 大 家 不 认 识 的 数 据 类 型, 只 不 过 是 严 奶 奶 悄 悄 的 给 我 们 认 识 的 数 据 类 型 起 了 新 名 字 而 已 2)#define 在 严 奶 奶 的 书 上 除 了 我 们 没 见 过 的 数 据 类 型 以 外, 还 有 一 些 东 西 我 们 也 没 见 过, 比 如 在 一 个 函 数 中 她 会 写 到 return ERROR; return OK; 之 类 的 语 句, 对 于 经 常 在 编 译 器 上 写 代 码 的 同 学, 乍 一 看 到 这 种 语 句 会 十 分 的 不 爽, 立 马 就 会 想,ERROR 和 OK 这 样 的 东 西 能 编 译 通 过? 或 者 就 是 怀 疑 自 己 语 言 水 平 太 差, 严 奶 奶 写 的 程 序 里 边 有 太 多 自 己 看 不 懂 的 地 方 了, 信 心 大 减 其 实 不 然, 和 typedef 一 样, 严 奶 奶 悄 悄 的 用 #define 语 句 处 理 过 ERROR 或 者 OK 之 类 的 词 了 其 实 ERROR 和 OK 就 是 两 个 常 量, 作 为 函 数 的 返 回 值, 来 提 示 用 户 函 数 操 作 结 果 的 严 奶 奶 初 衷 是 想 把 0,1 这 种 常 作 为 函 数 返 回 标 记 的 数 字 定 义 成 ERROR 和 OK( 一 般 出 错 返 回 0, 成 功 返 回 1), 这 样 比 起 数 字 来 更 人 性 化, 更 容 易 理 解, 但 结 果 却 适 得 其 反, 让 新 手 们 更 困 惑 了 #define 对 于 考 研 数 据 结 构 可 以 说 没 有 什 么 贡 献, 我 们 只 要 认 得 它 就 行, 写 程 序 时 一 般 用 不 到 比 如 #define MAX 50 这 句, 即 定 义 了 常 量 MAX( 此 时 x=50; 等 价 于 x=max;) 在 写 程 序 大 题 的 时 候 如 果 你 要 定 义 一 个 数 组, 如 int A[MAX]; 加 上 一 句 注 释 : /*MAX 为 已 经 定 义 的 常 量, 其 值 为 50*/ 即 可 没 必 要 跑 到 你 的 程 序 最 前 边 去 加 上 #define MAX 50 这 一 句, 原 因 前 边 已 经 讲 过 严 奶 奶 的 书 中 有 很 多 用 自 己 加 工 过 的 代 码 书 写 的 程 序, 和 编 译 器 上 我 们 习 惯 的 写 法 有 很 大 出 入, 所 以 对 于 新 手 较 难 理 解 本 书 的 作 用 在 很 大 程 度 上 就 是 做 了 一 个 翻 译 的 角 色, 不 过 是 站 在 学 生 的 角 度 把 课 本 上 用 过 于 严 谨 以 及 专 业 化 的 词 语 描 述 的 思 想 用 通 俗 易 懂 的 语 言 表 达 给 你 而 已 2. 函 数 说 明 : 只 要 是 算 法 设 计 题, 必 用 到 函 数, 所 以 其 中 的 一 些 注 意 事 项 这 里 有 必 要 说 一 下 (1) 用 函 数 来 缩 短 代 码 如 果 有 一 段 较 长 的 操 作 需 要 在 一 个 函 数 中 反 复 多 次 使 用, 那 么 你 最 好 把 这 个 操 作 做 成 一 个 函 数, 在 你 要 用 的 地 方 调 用 它, 会 节 省 很 多 答 题 空 间 比 如 : void f() //1

18 //2 //3 //4 //5 //6 //7 //8 这 个 函 数 中 的 8 句 组 成 了 一 个 操 作 这 个 操 作 在 另 一 个 函 数 ( 函 数 名 为 F) 中 要 多 次 用 到 此 时 我 们 就 可 以 把 这 8 句 做 成 一 个 函 数, 当 用 到 的 时 候 调 用 即 可, 比 如 : void F() f(); f(); f(); 从 上 边 可 以 看 出, 如 果 不 用 f() 函 数, 就 得 把 f() 中 的 8 行 写 3 遍, 使 得 F() 函 数 很 长 (2) 被 传 入 函 数 的 参 数 是 否 会 改 变 int a; void f(int x) x++; 上 边 声 明 的 函 数, 它 需 要 一 个 整 型 变 量 作 为 参 数, 且 在 自 己 的 函 数 体 中 将 参 数 做 自 增 1 的 运 算 执 行 完 以 下 程 序 段 之 后 a 的 值 是 多 少 呢? a=0; //1 f(a); //2 有 些 同 学 可 能 以 为 a 等 于 1 这 个 答 案 是 错 误 的, 可 以 这 样 理 解, 对 于 函 数 f(), 在 调 用 他 的 时 候, 括 号 里 的 变 量 a 和 句 1 中 的 变 量 a 并 不 是 同 一 个 变 量 在 执 行 句 2 的 时 候, 变 量 a 只 是 把 自 己 的 值 赋 给 了 一 个 在 f() 的 声 明 过 程 中 已 经 定 义 好 的 整 形 变 量, 可 以 把 这 个 变 量 想 象 为 上 述 声 明 过 程 中 的 x, 即 句 2 的 执 行 过 程 拆 开 看 来 是 这 样 两 句 :x=a;x++; 因 此 a 的 值 在 执 行 完 1,2 两 句 之 后 不 变 如 果 我 想 让 a 依 照 f() 函 数 体 中 的 操 作 来 改 变 应 该 怎 么 写 呢, 这 里 就 要 用 到 函 数 的 引 用 型 ( 这 种 语 法 是 C++ 中 的,C 中 没 有,C 中 是 靠 传 入 变 量 的 地 址 的 方 法 来 实 现 的, 写 起 来 比 较 麻 烦 且 容 易 出 错, 因 此 这 里 采 用 C++ 的 语 法 ), 其 函 数 声 明 方 法 如 下 : void f(int &x) x++;

19 这 样 就 相 当 于 a 取 代 了 x 的 位 置, 函 数 f() 就 是 在 对 a 本 身 进 行 操 作, 执 行 完 12 两 句 后,a 的 值 由 0 变 为 1 上 边 讲 到 的 是 对 针 对 普 通 变 量 的 引 用 型, 如 果 传 入 的 变 量 是 指 针 型 变 量, 且 在 函 数 体 内 要 对 传 入 的 指 针 进 行 改 变, 则 需 写 成 如 下 形 式 : void f(int *&x) // 指 针 型 变 量 在 函 数 体 中 需 要 改 变 的 写 法 x++; 执 行 完 上 述 函 数 后, 指 针 x 的 值 自 增 1 说 明 : 这 种 写 法 很 多 同 学 不 太 熟 悉, 但 是 它 在 树 与 图 的 算 法 中 应 用 广 泛, 在 之 后 的 章 节 中 考 生 要 注 意 观 察 其 与 一 般 引 用 型 变 量 的 书 写 差 别 上 边 是 单 个 变 量 作 为 函 数 参 数 的 情 况 如 果 一 个 数 组 作 为 函 数 的 参 数, 该 怎 么 写 呢? 传 入 的 数 组 是 不 是 也 有 引 用 型 一 说 呢? 对 于 数 组 作 为 函 数 的 参 数, 这 里 讲 两 种 情 况, 一 维 和 二 维 数 组 一 维 数 组 作 为 参 数 的 函 数 声 明 方 法 : void f(int x[],int n) ; 对 于 第 一 个 参 数 位 置 上 的 数 组 的 定 义 只 需 写 出 两 个 中 括 号 即 可, 不 需 要 限 定 数 组 长 度 ( 即 不 需 要 写 成 f(int x[5],int n), 即 便 是 你 传 入 的 数 组 真 的 是 长 度 为 5), 对 于 第 二 个 参 数 n, 是 写 数 组 作 参 数 的 函 数 的 习 惯, 用 来 说 明 将 来 要 传 进 函 数 加 工 的 数 组 元 素 的 个 数, 并 不 是 指 数 组 的 总 长 度 二 维 数 组 作 为 参 数 的 函 数 声 明 方 法 : void f(int x[][max],int n) ; 如 果 函 数 的 参 数 是 二 维 数 组, 数 组 的 第 一 个 中 括 号 内 不 需 要 写 上 数 组 长 度, 而 第 二 个 中 括 号 内 必 须 写 上 数 组 长 度 ( 假 设 MAX 是 已 经 定 义 的 常 量 ) 这 里 需 要 注 意, 你 所 传 入 的 数 组 第 二 维 长 度 也 得 是 MAX, 否 则 出 错, 比 如 : void f(int x[][5]) ; int a[10][5]; int b[10][3]; f(a); // 参 数 正 确 f(b); // 参 数 错 误 要 注 意 的 是, 将 数 组 作 为 参 数 传 入 函 数, 函 数 就 是 对 传 入 的 数 组 本 身 进 行 操 作, 即 如 果 函 数 体 内 涉 及 到 改 变 数 组 数 据 的 操 作, 传 入 的 数 组 中 的 数 据 就 会 依 照 函 数 的 操 作 来 改 变 因 此, 对 于 数 组 来 说, 没 有 引 用 型 和 非 引 用 型 之 分, 可 以 理 解 为 只 要 数 组 作 为 参 数,

20 都 是 引 用 型 的 (3) 有 返 回 值 的 函 数 声 明 一 个 函 数 : int f(int a) return a; 在 这 个 声 明 中 我 们 可 以 看 到, 有 一 个 int 在 函 数 名 的 前 边, 这 个 int 是 指 函 数 返 回 值 是 int 型 如 果 没 有 返 回 值, 声 明 函 数 的 时 候 用 void, 前 边 讲 过 的 函 数 中 已 经 有 所 体 现 返 回 值 常 常 用 来 作 为 判 断 函 数 执 行 状 态 ( 完 成 还 是 出 错 ) 的 标 记, 或 者 一 个 计 算 的 结 果 严 奶 奶 的 书 中 出 现 过 类 似 于 下 边 这 样 的 函 数 STATUS f(elemtype a) if(a>=0) return ERROR; else return OK; 对 于 一 些 基 础 稍 差 的 同 学 来 说, 这 个 函 数 麻 烦 了,STATUS,ELEMTYPE,ERROR,OK 这 都 什 么 东 西, 其 实 严 奶 奶 在 离 这 个 函 数 很 远 的 地 方 写 过 这 些 语 句 : #define ERROR 1 #define OK 0 typedef STATUS bool // 这 句 中 的 bool 是 布 尔 型, 只 取 两 个 值 //0 和 1, 其 实 用 bool 用 int 型 代 替 就 可 以, // 所 以 对 于 考 研 bool 用 处 不 大 typedef ELEMTYPE int 在 那 个 函 数 前 边 加 上 这 四 句 是 否 看 懂 了 呢? 看 懂 后 可 以 把 它 翻 译 一 下 就 能 写 出 以 下 代 码 : bool f(int a) // 本 行 可 换 成 int f(int a) if(a>=0) return 1; else return 0; 上 边 这 种 写 法 是 不 是 清 楚 明 白 了 严 奶 奶 之 所 以 要 将 程 序 写 的 如 此 个 性, 原 因 有 两 个, 一 是 上 边 那 个 自 己 另 起 的 类 型 名 或 者 常 量 名, 都 有 着 实 际 的 意 义,STATUS 代 表 状 态,OK 代 表 程 序 执 行 成 功,ERROR 代 表 出 错, 这 样 代 码 写 的 就 更 人 性 化 二 是, 如 果 我 们 在 写 一 个 大 工 程, 对 于 其 中 的 一 个 变 量, 在 整 个 工 程 中 都 已 经 用 int 型 定 义 过 了, 但 是 工 程 现 在 要 求 修 改, 将 所 有 int 型 换 成 char 型, 这 下 麻 烦 就 大 了 如 果 你 写 成 上 边 那 种 形 式, 将 int 型 起 个 新 名 字 ELEMTYPE, 在 整 个 程 序 中 凡 是 类 似 于 int x; 的 语 句 都 写 成 ELEMTYPE x; 此 时 如 果 要 统 一 更 换 数 据 类 型, 只 需 将 typedef ELEMTYPE int 这 一 句 中 的 int 换 成 char 即 可, 这 无 疑 是 十 分 方 便 的 事 情, 这 就 是 typedef 对 于 程 序 设 计 的 意 义 所 在 (#define 也 能 达 到 类 似 的 目 的 ) 但 显 然 的 是, 这 对 考 研 答 卷 意 义 不 大

21 1.2 算 法 的 时 间 复 杂 度 与 空 间 复 杂 度 分 析 基 础 考 研 中 的 算 法 时 间 复 杂 度 杂 谈 对 于 这 部 分, 要 牢 记 住 一 句 话 : 将 算 法 中 基 本 操 作 的 执 行 次 数 作 为 算 法 的 时 间 复 杂 度 这 里 我 们 所 讨 论 的 时 间 复 杂 度, 不 是 执 行 完 一 段 程 序 的 总 时 间, 而 是 其 中 基 本 操 作 的 总 次 数 因 此 对 于 一 个 算 法 进 行 时 间 复 杂 度 分 析 的 要 点, 无 非 是 明 确 算 法 中 哪 些 操 作 是 基 本 操 作, 然 后 计 算 出 基 本 操 作 所 重 复 执 行 的 次 数 在 考 试 中 算 法 题 目 里 你 总 能 找 到 一 个 n, 可 以 称 为 问 题 的 规 模, 比 如 要 处 理 的 数 组 元 素 的 个 数 为 n, 而 基 本 操 作 所 执 行 的 次 数 是 n 的 一 个 函 数 f(n)( 这 里 的 函 数 是 数 学 中 的 函 数 的 概 念, 不 是 C 或 C++ 语 言 中 的 函 数 的 概 念 ) 对 于 求 其 基 本 操 作 执 行 的 次 数, 就 是 求 函 数 f(n) 求 出 以 后 我 们 就 可 以 取 出 f(n) 中 随 n 增 大 增 长 最 快 的 项, 然 后 将 其 系 数 变 为 1 做 为 时 间 复 杂 度 的 度 量, 记 为 T(n)=O(f(n) 中 增 长 最 快 的 项 / 此 项 的 系 数 ), 比 如 f(n)=2n 3 +4n , 则 其 时 间 复 杂 度 为 为 T(n)=O(2n 3 /2)=O(n 3 ) 其 实 计 算 算 法 的 时 间 复 杂 度, 就 是 给 出 相 应 的 数 量 级, 当 f(n) 与 n 无 关 时, 时 间 复 杂 度 T(n)=O(1); 当 f(n) 与 n 是 线 性 关 系 时,T(n)=O(n); 是 平 方 关 系 时,T(n)=O(n 2 ); 以 此 类 推 说 明 : 考 研 中 常 常 要 比 较 各 种 时 间 复 杂 度 的 大 小, 常 用 的 比 较 关 系 如 下 : O 1 O log 2 n O n nlog 2 n O n 2 O n 3 O n k O 2 n 通 过 以 上 分 析 我 们 总 结 出 计 算 一 个 算 法 时 间 复 杂 度 的 步 骤 如 下 : (1) 确 定 算 法 中 的 基 本 操 作, 以 及 问 题 的 规 模 (2) 根 据 基 本 操 作 执 行 情 况 计 算 出 规 模 n 的 函 数 f(n), 并 确 定 时 间 复 杂 度 为 T(n)=O(f(n) 中 增 长 最 快 的 项 / 此 项 的 系 数 ) 注 意 : 有 的 算 法 中 基 本 操 作 执 行 次 数 跟 初 始 输 入 的 数 据 有 关 如 果 题 目 不 做 特 殊 要 求, 一 般 我 们 依 照 使 得 基 本 操 作 执 行 次 数 最 多 的 输 入 来 计 算 时 间 复 杂 度, 即 将 最 坏 的 情 况 作 为 算 法 时 间 复 杂 度 的 度 量 例 题 选 讲 例 题 1: 求 出 以 下 算 法 的 时 间 复 杂 度 void fun(int n) int i=1,j=100; while(i<n) j++; i+=2; 分 析 : 第 一 步 : 找 出 基 本 操 作, 确 定 规 模 n 1 找 基 本 操 作 ( 所 谓 基 本 操 作, 即 其 重 复 执 行 次 数 和 算 法 的 执 行 时 间 成 正 比 的 操 作, 通 俗 点 说, 这 种 操 作 组 成 了 算 法, 当 它 们 都 执 行 完 的 时 候 算 法 也 结 束 了, 多 数 情 况 下 我 们 取 最 深 层 循 环 内 的 语 句 所 描 述 的 操 作 作 为 基 本 操 作 ), 显 然 题 目 中 j++; 与 i+=2; 这 两 行 都 可 以

22 作 为 基 本 操 作 2 确 定 规 模, 由 循 环 条 件 i<n 可 以 知 道, 循 环 执 行 的 次 数, 即 基 本 操 作 执 行 的 次 数 和 参 数 n 有 关, 因 此 参 数 n 就 是 我 们 所 说 的 规 模 n 第 二 步 : 计 算 出 n 的 函 数 f(n) 显 然,n 确 定 以 后, 循 环 的 结 束 与 否 与 i 有 关,i 的 初 值 为 1, 每 次 自 增 2, 假 设 i 自 增 m 次 后 循 环 结 束, 则 i 最 后 的 值 为 1+2 m, 因 此 有 1+2 m+k=n( 其 中 K 为 一 个 常 数, 因 为 在 循 环 结 束 时 i 的 值 稍 大 于 n, 为 了 方 便 表 述 和 进 一 步 计 算, 用 K 将 1+2 m 修 正 成 n 因 为 K 为 常 数, 所 以 这 样 做 不 会 影 响 最 终 时 间 复 杂 度 的 计 算 ), 解 得 m=(n-1-k)/2, 即 f(n)=(n-1-k)/2, 可 以 发 现 其 中 增 长 最 快 的 项 为 n/2, 因 此 时 间 复 杂 度 T(n)=O(n) 例 题 2: 分 析 以 下 算 法 的 时 间 复 杂 度 void fun(int n) int i,j,x=0; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) x++; 分 析 : x++; 处 于 最 内 层 循 环, 因 此 取 x++; 做 为 基 本 操 作 显 然 n 为 规 模 可 以 算 出 x++; 的 执 行 次 数 为 f(n)=n(n-1)/2, 变 化 最 快 的 项 为 n 2, 因 此 时 间 复 杂 度 为 T(n)=O(n 2 ) 例 题 3: 分 析 以 下 算 法 的 时 间 复 杂 度 void fun(int n) int i=0;s=0; while(s<n) i++; s=s+i; 分 析 : 显 然 n 为 规 模, 基 本 操 作 为 i++;s=s+i;i 与 s 都 从 0 开 始, 假 设 循 环 执 行 m 次 结 束, 则 有 s 1 =1,s 2 =1+2=3,s 3 =1+2+3=6,,s m =m(m+1)/2( 其 中 s m 为 执 行 到 第 m 次 的 时 候 s 的 值 ), 则 有 m(m+1)/2+k=n,(k 为 起 修 正 作 用 的 常 数 ) 由 求 根 公 式 得 : 即 : 由 此 可 知 时 间 复 杂 度 为 : 1 8n n 1 8 n 2 T(n)=O( n)

23 说 明 : 在 计 算 时 间 复 杂 度 的 时 候 有 可 能 会 出 现 这 种 情 况, 即 对 于 相 同 的 规 模, 因 输 入 序 列 不 同 会 出 现 不 同 的 时 间 复 杂 度, 这 时 我 们 一 般 取 最 坏 的 情 况 下 的 输 入 序 列 ( 即 使 得 基 本 操 作 执 行 次 数 最 多 的 序 列 ) 来 计 算 时 间 复 杂 度 考 研 中 的 算 法 空 间 复 杂 度 分 析 算 法 的 空 间 复 杂 度 指 算 法 在 运 行 时 所 需 存 储 空 间 的 度 量, 主 要 考 虑 在 算 法 运 行 过 程 中 临 时 占 用 的 存 储 空 间 的 大 小 ( 和 时 间 复 杂 度 一 样, 以 数 量 级 的 形 式 给 出 ) 说 明 : 这 一 部 分 在 理 解 了 各 种 数 据 的 存 储 结 构 及 其 操 作 之 后 更 容 易 理 解 因 此 对 于 这 一 部 分, 将 在 后 边 的 章 节 中 以 题 目 的 形 式 给 出 讲 解 1. 3 数 据 结 构 和 算 法 的 基 本 概 念 数 据 结 构 的 基 本 概 念 ( 不 需 要 刻 意 的 去 记 忆 这 些 内 容, 联 系 生 活 实 际 去 理 解 即 可 在 以 后 的 学 习 过 程 中, 如 果 碰 到 不 熟 悉 的 概 念, 来 这 里 查 一 查 就 可 以 了 ) 1. 数 据 数 据 是 对 客 观 事 物 的 符 号 表 示, 在 计 算 机 科 学 中 是 指 所 有 能 输 入 到 计 算 机 中 并 且 被 计 算 机 程 序 处 理 的 符 号 的 总 称 例 如 : 整 数 实 数 和 字 符 串 都 是 数 据 2. 数 据 元 素 数 据 元 素 是 数 据 的 基 本 单 位, 在 计 算 机 程 序 中 通 常 将 其 作 为 一 个 整 体 进 行 考 虑 和 处 理 有 时, 一 个 数 据 元 素 可 由 若 干 个 数 据 项 组 成 ; 例 如, 一 本 书 的 书 目 信 息 为 一 个 数 据 元 素, 而 书 目 信 息 的 每 一 项 ( 如 书 名, 作 者 名 等 ) 为 一 个 数 据 项 3. 数 据 项 数 据 项 是 数 据 结 构 中 讨 论 的 最 小 单 位, 是 数 据 记 录 中 最 基 本 的, 不 可 分 的 数 据 单 位 4. 数 据 对 象 数 据 对 象 是 性 质 相 同 的 数 据 元 素 的 集 合, 是 数 据 的 一 个 子 集 例 如, 大 写 字 母 就 是 一 个 数 据 对 象, 大 写 字 母 数 据 对 象 是 集 合 A, B Z 5. 数 据 结 构 数 据 结 构 是 指 相 互 之 间 存 在 一 种 或 多 种 特 定 关 系 的 数 据 元 素 的 集 合 数 据 结 构 包 括 3 方 面 的 内 容 : 逻 辑 结 构, 存 储 结 构 和 对 数 据 的 运 算 6. 数 据 的 逻 辑 结 构 数 据 的 逻 辑 结 构 是 对 数 据 之 间 关 系 的 描 述, 它 与 数 据 的 存 储 结 构 无 关, 同 一 种 逻 辑 结 构 可 以 有 多 种 存 储 结 构 归 纳 起 来 数 据 的 逻 辑 结 构 主 要 有 两 大 类 (1) 线 性 结 构 简 单 地 说, 线 性 结 构 是 一 个 数 据 元 素 的 有 序 ( 次 序 ) 集 合 它 有 四 个 基 本 特 征 : 1 ) 集 合 中 必 存 在 唯 一 的 一 个 第 一 个 元 素 2) 集 合 中 必 存 在 唯 一 的 一 个 最 后 的 元 素 3) 除 最 后 元 素 之 外, 其 它 数 据 元 素 均 有 唯 一 的 后 继 4) 除 第 一 元 素 之 外, 其 它 数 据 元 素 均 有 唯 一 的 前 驱 数 据 结 构 中 线 性 结 构 指 的 是 数 据 元 素 之 间 存 在 着 一 对 一 的 线 性 关 系 的 数 据 结 构 如 ( a1,a2,a3,...,an),a1 为 第 一 个 元 素, an 为 最 后 一 个 元 素, 此 集 合 即 为 一 个 线 性 结 构 的 集 合

24 (2) 非 线 性 结 构 与 线 性 结 构 不 同, 非 线 性 结 构 中 的 结 点 存 在 着 一 对 多 的 关 系, 它 又 可 以 细 分 为 树 形 结 构 和 图 形 结 构 7. 数 据 的 物 理 结 构 数 据 的 物 理 结 构 又 称 为 存 储 结 构, 是 数 据 的 逻 辑 结 构 在 计 算 机 中 的 表 示 ( 又 称 映 像 ) 它 包 括 数 据 元 素 的 表 示 和 关 系 的 表 示 当 数 据 元 素 是 由 若 干 数 据 项 构 成 的 时 候, 数 据 项 的 表 示 称 为 数 据 域 ; 比 如 一 个 链 表 结 点, 结 点 包 含 值 域 和 指 针 域, 这 里 结 点 可 以 看 做 一 个 数 据 元 素, 其 中 的 值 域 和 指 针 域 都 是 这 个 数 据 元 素 的 数 据 域 数 据 元 素 之 间 的 关 系 在 计 算 机 中 有 两 种 不 同 的 表 示 方 法 : 顺 序 映 像 和 非 顺 序 映 像 对 应 的 两 种 不 同 的 存 储 结 构 分 别 是 顺 序 存 储 结 构 和 链 式 存 储 结 构 顺 序 映 像 是 借 助 数 据 元 素 在 存 储 器 中 的 相 对 位 置 来 表 示 数 据 元 素 之 间 的 逻 辑 关 系 ; 非 顺 序 映 像 是 借 助 指 针 表 示 数 据 元 素 之 间 的 逻 辑 关 系 实 际 上, 在 数 据 结 构 中 有 以 下 4 种 常 用 的 存 储 方 法 (1) 顺 序 存 储 方 法 顺 序 存 储 结 构 是 存 储 结 构 类 型 中 的 一 种, 该 结 构 是 把 逻 辑 上 相 邻 的 结 点 存 储 在 物 理 位 置 上 相 邻 的 存 储 单 元 中, 结 点 之 间 的 逻 辑 关 系 由 存 储 单 元 的 邻 接 关 系 来 体 现 由 此 得 到 的 存 储 结 构 为 顺 序 存 储 结 构, 通 常 顺 序 存 储 结 构 式 借 助 于 计 算 机 程 序 设 计 语 言 ( 例 如 C/C++) 的 数 组 来 描 述 的 (2) 链 式 存 储 方 法 该 方 法 不 要 求 逻 辑 上 相 邻 的 结 点 在 物 理 位 置 上 亦 相 邻, 结 点 间 的 逻 辑 关 系 是 由 附 加 的 指 针 字 段 表 示 的 由 此 得 到 的 存 储 表 示 称 为 链 式 存 储 结 构, 通 常 借 助 于 计 算 机 程 序 设 计 语 言 ( 例 如 C/C++) 的 指 针 类 型 来 描 述 它 (3) 索 引 存 储 方 法 该 方 法 在 存 储 结 点 信 息 时 除 建 立 存 储 结 点 信 息 外, 还 建 立 附 加 的 索 引 表 来 标 识 结 点 的 地 址 索 引 项 的 一 般 形 式 一 般 是 < 关 键 字, 地 址 > 关 键 字 标 识 唯 一 一 个 结 点 : 地 址 作 为 指 向 结 点 的 指 针 (4) 散 列 ( 或 哈 希 ) 存 储 方 法 该 方 法 的 基 本 思 想 是 根 据 结 点 的 关 键 字 通 过 哈 希 函 数 直 接 计 算 出 该 结 点 的 存 储 地 址 这 种 存 储 方 法 本 质 上 是 顺 序 存 储 方 法 的 扩 展 8. 数 据 类 型 和 变 量 数 据 类 型 是 一 个 值 的 集 合 以 及 定 义 在 这 个 值 集 上 的 一 组 操 作 变 量 是 用 来 存 储 值 的 所 在 处, 它 们 有 名 字 和 数 据 类 型 变 量 的 数 据 类 型 决 定 了 如 何 将 代 表 这 些 值 的 位 存 储 到 计 算 机 的 内 存 中 在 声 明 变 量 时 也 可 指 定 它 的 数 据 类 型 所 有 变 量 都 具 有 数 据 类 型, 以 决 定 能 够 存 储 哪 种 数 据 算 法 的 基 本 概 念 1. 算 法 算 法 可 以 理 解 为 有 基 本 运 算 及 规 定 的 运 算 顺 序 所 构 成 的 完 整 的 解 题 步 骤 或 者 看 成 按 照 要 求 设 计 好 的 有 限 的 确 切 的 计 算 序 列 2. 算 法 的 特 性 一 个 算 法 应 该 具 有 以 下 五 个 重 要 的 特 征 : ( 1 ) 有 穷 性 一 个 算 法 必 须 保 证 执 行 有 限 步 之 后 结 束 (2) 确 定 性 算 法 的 每 一 步 骤 必 须 有 确 定 的 定 义

25 ( 3) 输 入 一 个 算 法 有 0 个 或 多 个 输 入, 以 刻 画 运 算 对 象 的 初 始 情 况, 所 谓 0 个 输 入 是 指 算 法 本 身 确 定 了 初 始 条 件 (4) 输 出 一 个 算 法 有 一 个 或 多 个 输 出, 以 反 映 对 输 入 数 据 加 工 后 的 结 果 没 有 输 出 的 算 法 是 毫 无 意 义 的 (5) 可 行 性 算 法 中 的 所 有 操 作 都 必 须 可 以 通 过 已 经 实 现 的 基 本 操 作 机 型 运 算, 并 在 有 限 次 内 实 现, 而 且 人 们 用 笔 和 纸 做 有 限 次 运 算 后 也 可 完 成 3. 算 法 的 设 计 目 标 算 法 设 计 目 标 为 正 确 性 可 读 性 健 壮 性 和 算 法 效 率 其 中 算 法 效 率 通 过 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 来 描 述 ( 1) 正 确 性 要 求 算 法 能 够 正 确 地 执 行 预 先 规 定 的 功 能 和 性 能 要 求 这 是 最 重 要 也 是 最 基 本 的 标 准 (2) 可 读 性 要 求 算 法 易 于 人 的 理 解 (3) 健 壮 性 要 求 算 法 有 很 好 的 容 错 性, 能 够 对 不 合 理 的 数 据 进 行 检 查 (4) 高 效 率 与 低 存 储 量 需 求 算 法 的 效 率 主 要 是 指 算 法 的 执 行 时 间 对 于 同 一 个 问 题 如 果 有 多 种 算 法 可 以 求 解, 执 行 时 间 短 的 算 法 效 率 高 算 法 的 存 储 量 指 的 是 算 法 执 行 过 程 中 所 需 要 的 最 大 存 储 空 间 高 效 率 和 低 存 储 量 这 两 者 都 与 问 题 的 规 模 有 关 习 题 心 选 一 选 择 题 1. 算 法 的 计 算 量 的 大 小 称 为 算 法 的 ( ) A. 效 率 B. 复 杂 性 C. 现 实 性 D. 难 度 2. 算 法 的 时 间 复 杂 度 取 决 于 ( ) A. 问 题 的 规 模 B. 待 处 理 数 据 的 初 态 C. A 和 B 3. 计 算 机 算 法 指 的 是 (1), 它 必 须 具 备 (2) 这 三 个 特 性 (1)A. 计 算 方 法 B. 排 序 方 法 C. 解 决 问 题 的 步 骤 序 列 D. 调 度 方 法 (2)A. 可 执 行 性 可 移 植 性 可 扩 充 性 C. 确 定 性 有 穷 性 稳 定 性 B. 可 执 行 性 确 定 性 有 穷 性 D. 易 读 性 稳 定 性 安 全 性 4. 一 个 算 法 应 该 是 ( ) A. 程 序 B. 问 题 求 解 步 骤 的 描 述 C. 要 满 足 五 个 基 本 特 性 D. A 和 C 5. 下 面 关 于 算 法 说 法 错 误 的 是 ( ) A. 算 法 最 终 必 须 由 计 算 机 程 序 实 现 B. 为 解 决 某 问 题 的 算 法 同 为 该 问 题 编 写 的 程 序 含 义 是 相 同 的 C. 算 法 的 可 行 性 是 指 指 令 不 能 有 二 义 性 D. 以 上 几 个 都 是 错 误 的 6. 下 面 说 法 错 误 的 是 ( ) (1) 算 法 原 地 工 作 的 含 义 是 指 不 需 要 任 何 额 外 的 辅 助 空 间

26 (2) 在 相 同 的 规 模 n 下, 复 杂 度 O(n) 的 算 法 在 时 间 上 总 是 优 于 复 杂 度 O(2 n ) 的 算 法 (3) 所 谓 时 间 复 杂 度 是 指 最 坏 情 况 下, 估 算 算 法 执 行 时 间 的 一 个 上 界 (4) 同 一 个 算 法, 实 现 语 言 的 级 别 越 高, 执 行 效 率 就 越 低 A.(1) B.(1),(2) C.(1),(4) D.(3) 7. 从 逻 辑 上 可 以 把 数 据 结 构 分 为 ( ) 两 大 类 A. 动 态 结 构 静 态 结 构 B. 顺 序 结 构 链 式 结 构 C. 线 性 结 构 非 线 性 结 构 D. 初 等 结 构 构 造 型 结 构 8. 以 下 哪 一 个 术 语 与 数 据 的 存 储 结 构 无 关?( ) A. 栈 B. 哈 希 表 C. 线 索 树 D. 双 向 链 表 E. 循 环 队 列 9. 在 下 面 的 程 序 段 中, 对 x 的 赋 值 语 句 的 频 度 为 ( ) for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; A. O(2n) B.O( n) C.O(n 2 ) D.O(log n 2 ) 10. 程 序 段 for(i=n-1;i>=1;i--) for(j=1;j<=i;j++) if(a[j]>a[j+1]) A[j] 与 A[j+1] 对 换 ; 其 中 n 为 正 整 数, 则 最 后 一 行 的 语 句 频 度 在 最 坏 情 况 下 是 ( ) A. O(n) B. O(nlogn) C. O(n 3 ) D. O(n 2 ) 11. 以 下 数 据 结 构 中,( ) 是 非 线 性 数 据 结 构 A. 树 B. 队 C. 栈 12. 连 续 存 储 设 计 时, 存 储 单 元 的 地 址 ( ) A. 一 定 连 续 B. 一 定 不 连 续 C. 不 一 定 连 续 D. 部 分 连 续, 部 分 不 连 续 13. 以 下 属 于 逻 辑 结 构 的 是 ( ) A. 顺 序 表 B. 哈 希 表 C. 有 序 表 D. 单 链 表 二. 综 合 应 用 题 1. 有 下 列 运 行 时 间 函 数 : ( 1) f 1 (n)=1000; (2)f 2 (n)=n n; (3)f 3 (n)=3n n 2 +n+1; 分 别 写 出 相 应 的 大 O 表 示 的 运 算 时 间 2. 下 面 函 数 mergesort 执 行 的 时 间 复 杂 度 为 多 少? 假 设 函 数 调 用 被 写 为 mergesort(1,n),merge 函 数 时 间 复 杂 度 为 O(n) void mergesort(int i,int j) int m; if(i!=j) mergesort(i,m); mergesort(m+1,j); merge(i,j,m);// 本 函 数 时 间 复 杂 度 为 O(n)

27 习 题 心 讲 选 择 题 : 1.B 本 题 考 查 算 法 时 间 复 杂 度 的 定 义 算 法 中 基 本 操 作 的 重 复 执 行 次 数 就 是 算 法 的 计 算 量, 将 其 大 小 作 为 算 法 的 时 间 复 杂 度, 因 此 选 B 2.C 本 题 考 查 算 法 时 间 复 杂 度 的 定 义 算 法 时 间 复 杂 度 即 为 基 本 操 作 执 行 次 数, 显 然 问 题 规 模 越 大, 基 本 操 作 的 次 数 越 多, 因 此 时 间 复 杂 度 与 规 模 有 关 在 相 同 的 规 模 下, 与 数 据 初 态 也 有 关, 比 如 两 个 数 相 乘, 有 一 个 因 子 为 0 时 的 计 算 速 度 显 然 要 比 两 个 因 子 都 非 0 的 情 况 要 快 本 题 选 C 3. C B 本 章 算 法 基 本 概 念 中 已 讲 过 4.B 本 章 算 法 基 本 概 念 中 已 讲 过 5.D 本 题 考 查 算 法 的 概 念 选 项 A 计 算 机 程 序 只 是 实 现 算 法 的 一 种 手 段, 人 用 手 工 也 可 以 完 成 选 项 B 算 法 可 以 理 解 为 由 基 本 运 算 及 规 定 的 运 算 顺 序 所 构 成 的 完 整 的 解 题 步 骤 程 序 是 为 实 现 特 定 目 标 或 解 决 特 定 问 题 而 用 计 算 机 语 言 编 写 的 命 令 序 列 的 集 合 两 者 显 然 是 不 同 的 概 念 选 项 C 明 显 错 误, 课 本 概 念 中 已 经 讲 过 6.C 本 题 考 查 算 法 的 时 间 复 杂 度 和 空 间 复 杂 度 的 相 关 知 识 ( 1 ) 一 个 可 执 行 程 序 除 了 需 要 内 存 空 间 来 寄 存 本 身 的 指 令 常 数 变 量 和 输 入 数 据 外, 还 需 要 额 外 空 间, 如 果 这 个 额 外 空 间 相 对 于 问 题 的 规 模 ( 输 入 数 据 ) 来 说 是 个 常 数, 那 我 么 们 就 称 之 为 原 地 工 作 因 此 (1) 不 对 ( 2) 节 考 研 中 的 算 法 时 间 复 杂 度 杂 谈 中 已 经 讲 过 (3) 对 于 O(1),O(log 2 n),o(n) 等,O 的 形 式 定 义 为 : 若 f(n) 是 正 数 n 的 一 个 函 数, 则 O(f(n)) 表 示 存 在 一 个 正 常 数 M, 使 得 当 n n 0 时 满 足 O(f(n) ) 小 于 等 于 M f(n), 也 就 是 O(f(n)) 给 出 了 函 数 f(n) 的 一 个 上 界 (4) 这 句 话 是 严 版 数 据 结 构 上 的 原 句, 大 多 数 情 况 下 应 该 是 这 样, 但 是 不 能 说 的 这 么 绝 对, 得 看 编 译 链 接 后 的 最 终 的 机 器 指 令, 这 些 指 令 操 作 的 次 数 越 少, 说 明 该 语 言 在 某 种 编 译 链 接 环 境 下 效 率 较 高, 实 际 上 即 使 同 一 种 语 言 在 不 同 的 编 译 环 境 下, 也 有 可 能 不 同 综 上, 本 题 答 案 为 C 7.C 节 数 据 结 构 的 概 念 中 已 经 讲 过 8.A 本 题 考 查 基 本 数 据 结 构 A 项, 栈 是 逻 辑 结 构 从 节 第 7 个 讲 解 中 可 以 知 道 B 项, 线 索 树 是 在 链 式 存 储 结 构 的 基 础 上 对 树 进 行 线 索, 与 链 式 存 储 结 构 有 关 C 项, 双 向 链 表 也 是 说 明 线 性 表 是 以 链 式 结 构 存 储 D 项, 哈 希 是 算 法, 哈 希 存 储 方 法 本 质 上 是 顺 序 存 储 方 法 的 扩 展 哈 希 表 本 质 上 是 顺 序

28 表 的 扩 展 E 项, 循 环 队 列 是 建 立 在 顺 序 存 储 结 构 上 的 说 明 : 这 种 题 目 还 有 一 种 比 较 直 观 的 解 法, 要 判 断 是 否 与 数 据 的 存 储 结 构 无 关, 只 需 看 看 这 种 结 构 到 底 有 没 有 具 体 到 使 用 顺 序 存 储 还 是 链 式 存 储, 如 果 已 经 具 体 到 了 那 就 一 定 是 和 数 据 的 存 储 结 构 有 关, 比 如 A 选 项 中 的 栈 并 没 有 说 明 是 用 顺 序 栈 还 是 用 链 栈 来 实 现, 所 以 是 逻 辑 结 构 B 选 项 中 的 线 索 树 很 明 显 是 要 用 链 式 来 实 现 ( 现 在 不 清 楚 没 关 系, 等 学 完 树 那 一 章 就 理 解 了 ), 故 与 数 据 的 存 储 结 构 有 关, 以 此 类 推 9.C 本 题 考 查 算 法 时 间 复 杂 度 的 计 算 f(n)=n 2, 因 此 时 间 复 杂 度 是 O(n ) 10.D 本 题 考 查 算 法 时 间 复 杂 度 的 计 算 此 算 法 为 冒 泡 排 序 算 法 的 核 心 语 句, 最 坏 情 况 下 时 间 复 杂 度 为 O(n 2 ) 11.A 本 题 考 查 基 本 数 据 结 构 树 是 一 种 分 支 结 构, 显 然 不 属 于 线 性 结 构 12.A 本 题 考 查 数 据 的 物 理 结 构 顺 序 存 储 结 构 要 开 辟 一 片 连 续 的 存 储 空 间, 结 合 第 7 个 讲 解 可 知 本 题 选 A 13.C 本 题 考 查 数 据 的 物 理 结 构 有 序 表 指 出 了 表 中 数 据 是 有 一 定 逻 辑 顺 序 排 列 的, 是 一 种 逻 辑 结 构 2 综 合 应 用 题 : 1. 答 案 : 根 据 节 中 公 式 得 : (1)T 1 (n)= O(1000/1000)=O(1) (2)T 2 /1)=O(n 2 2 (n)=o(n ) ( 3)T 3 (n)=o(3n 3 /3)=O(n 3 ) 2. 分 析 : 显 然 规 模 为 n, 基 本 操 在 merge 函 数 中,merge 时 间 复 杂 度 为 O(n) 因 此 merge 内 基 本 操 作 次 数 可 设 为 cn,mergesort 函 数 基 本 操 作 次 数 设 为 f(n), 则 有 : f(n)=2f(n/2)+cn =2 2 f(n/4)+2cn =2 3 f(n/8)+3cn = =2 k f(n/(2 k ))+kcn 1 由 mergesort 函 数 可 知,f(1)=O(1) 2 由 12 可 知, 当 n=2 k 即 k=log 2 n 时 f(n)=n+kcnlog 2 n

29 因 此 时 间 复 杂 度 T(n)=O(nlog 2 n) 作 者 的 话 : 假 如 你 是 一 个 很 新 的 新 手 ( 至 少 要 稍 微 有 一 点 C 或 C++ 语 言 基 础, 如 果 连 这 个 都 没 有 的 话, 先 去 读 谭 浩 强 的 C), 到 这 里 为 止, 我 已 经 把 考 研 数 据 结 构 要 用 到 的 全 部 基 本 功 教 给 你 了, 对 于 考 研 数 据 结 构, 要 想 拿 高 分, 有 很 多 学 习 的 风 格, 本 书 则 走 了 一 种 让 广 大 考 生 都 容 易 接 受 的 风 格, 希 望 读 者 能 适 应 这 种 风 格, 这 样 你 的 学 习 会 变 的 轻 松 下 面 就 让 我 们 从 下 一 章 开 始, 把 考 纲 所 要 求 的 知 识 点 一 一 击 破

30 第 二 章 线 性 表 大 纲 要 求 线 性 表 的 定 义 和 基 本 操 作 线 性 表 的 实 现 1. 顺 序 存 储 结 构 2. 链 式 存 储 结 构 3. 线 性 表 的 应 用 ( 这 一 部 分 通 过 线 性 表 算 法 中 的 各 种 题 目 来 讲 解, 不 单 独 作 为 一 节 ) 说 明 : 本 章 大 纲 要 求 过 于 简 略, 有 些 知 识 点 大 纲 没 有 明 文 写 出, 但 是 掌 握 了 这 些 知 识 点 对 本 章 以 及 其 他 章 中 很 多 知 识 点 的 理 解 都 有 帮 助 因 此 本 章 会 添 加 一 些 必 须 的 知 识 点, 以 帮 助 你 更 好 的 理 解, 虽 然 大 纲 中 没 有 涉 及 这 些 知 识 点 2.1 线 性 表 的 基 本 概 念 与 实 现 1. 线 性 表 的 定 义 线 性 表 是 具 有 相 同 特 性 数 据 元 素 的 一 个 有 限 序 列 该 序 列 中 所 含 元 素 的 个 数 叫 做 线 性 表 的 长 度, 用 n 表 示 (n 0); 注 意 n 可 以 等 于 零, 表 示 线 性 表 是 一 个 空 表, 空 表 也 可 以 作 为 一 个 线 性 表 线 性 表 是 一 种 简 单 的 数 据 结 构, 我 们 可 以 把 它 想 象 成 一 队 学 生 学 生 人 数 对 应 了 线 性 表 的 长 度, 学 生 人 数 是 有 限 的, 这 里 体 现 了 线 性 表 是 一 个 有 限 序 列 ; 队 中 所 有 人 的 身 份 都 是 学 生, 这 里 体 现 了 线 性 表 中 的 数 据 元 素 具 有 相 同 的 特 性 ; 线 性 表 可 以 是 有 序 的 也 可 以 是 无 序 的, 如 果 学 生 是 按 照 身 高 来 排 队, 矮 在 前, 高 在 后, 这 就 体 现 了 线 性 表 的 有 序 性 2. 线 性 表 的 逻 辑 特 性 继 续 拿 定 义 中 的 例 子 来 说 明 在 一 队 学 生 中, 只 有 一 个 学 生 在 队 头, 同 样 只 有 一 个 学 生 在 队 尾 在 队 头 的 学 生 的 前 面 没 有 其 他 学 生, 在 队 尾 的 学 生 的 后 边 也 没 有 其 他 学 生 除 了 队 头 和 队 尾 的 学 生 以 外, 对 于 其 他 的 每 一 个 学 生, 紧 挨 着 站 在 其 前 后 的 学 生 都 只 有 一 个, 这 是 很 显 然 的 事 情 线 性 表 也 是 这 样, 只 有 一 个 表 头 元 素, 只 有 一 个 表 尾 元 素, 表 头 元 素 没 有 前 驱, 表 尾 元 素 没 有 后 继, 除 表 头 和 表 尾 元 素 之 外 其 他 元 素 只 有 一 个 直 接 前 驱, 也 只 有 一 个 直 接 后 继 以 上 就 是 线 性 表 的 逻 辑 特 性 3. 线 性 表 的 存 储 结 构 线 性 表 的 存 储 结 构 有 顺 序 存 储 结 构 和 链 式 存 储 结 构 两 种 前 者 称 为 顺 序 表, 后 者 称 为 链 表 下 边 就 通 过 对 比 来 介 绍 这 两 种 存 储 结 构 ( 1) 顺 序 表 顺 序 表 就 是 把 线 性 表 中 的 所 有 元 素 按 照 其 逻 辑 顺 序, 依 次 存 储 到 存 储 器 中 从 指 定 存 储 位 置 开 始 的 一 块 连 续 的 存 储 空 间 中 这 样 线 性 表 中 第 一 个 元 素 的 存 储 位 置 就 是 指 定 的 存 储 位 置, 第 i+1 个 元 素 的 存 储 位 置 紧 接 在 第 i 个 元 素 的 存 储 位 置 的 后 面

31 ( 2) 链 表 在 链 表 存 储 中, 每 个 结 点 不 仅 包 含 所 存 元 素 本 身 的 信 息, 还 包 含 元 素 之 间 逻 辑 关 系 的 信 息, 即 前 驱 结 点 包 含 后 继 结 点 的 地 址 信 息, 这 样 就 可 以 通 过 前 驱 结 点 中 的 地 址 信 息 方 便 的 找 到 后 继 结 点 的 位 置 两 种 存 储 结 构 的 比 较 : 顺 序 表 就 好 像 图 2.1(a) 所 示 的 一 排 房 间, 每 个 房 间 左 边 的 数 字 就 是 该 房 间 离 0 点 的 距 离 同 时 也 代 表 了 房 间 号, 房 间 的 长 度 为 1 因 此 我 们 只 要 知 道 0 点 的 位 置, 然 后 通 过 房 间 号 就 马 上 可 以 找 到 任 何 一 个 房 间 的 位 置, 这 就 是 顺 序 表 的 第 一 个 特 性, 随 机 访 问 特 性 由 下 图 我 们 还 可 以 看 出, 5 个 房 间 所 占 用 的 地 皮 是 紧 挨 着 的, 即 连 续 的 占 用 了 一 片 空 间, 并 且 地 皮 的 块 数 6 是 确 定 的, 当 我 们 在 地 皮 上 布 置 新 的 房 间 或 者 拆 掉 老 的 房 间 ( 即 对 顺 序 表 的 操 作 过 程 中 ) 地 皮 的 块 数 不 会 增 加 也 不 会 减 少 这 就 是 顺 序 表 的 第 二 个 特 性, 即 顺 序 表 要 求 占 用 连 续 的 存 储 空 间, 存 储 分 配 只 能 预 先 进 行, 即 静 态 分 配, 一 旦 分 配 好 了, 在 对 其 操 作 过 程 中 不 变 再 看 链 表, 如 图 所 示, 房 间 是 散 落 存 在 的, 每 个 房 间 的 右 边 有 走 向 下 一 个 房 间 的 方 向 指 示 箭 头 因 此 如 果 我 们 想 访 问 最 后 一 个 房 间, 就 必 须 从 第 一 个 房 间 开 始, 依 次 走 过 前 三 个 房 间 才 能 来 到 最 后 一 个 房 间, 而 不 能 直 接 得 出 最 后 一 个 房 间 的 位 置, 即 链 表 不 支 持 随 机 访 问 通 过 图 2.1(b) 我 们 还 可 以 知 道, 链 表 中 每 一 个 结 点 需 要 划 出 一 部 分 空 间 来 存 储 指 向 下 一 个 结 点 位 置 的 指 针, 因 此 链 表 中 结 点 的 存 储 空 间 利 用 率 较 之 顺 序 表 稍 低 一 些 链 表 中 结 点 是 散 落 的 分 布 在 存 储 器 中 的, 所 以 链 表 支 持 存 储 空 间 的 动 态 分 配, 即 在 需 要 新 的 结 点 时 再 进 行 空 间 划 分, 而 不 需 要 一 次 性 的 划 分 所 有 所 需 空 间 给 链 表 图 2.1(a) 顺 序 表 中 最 右 边 的 一 个 表 结 点 空 间 代 表 没 有 被 利 用 ( 即 顺 序 表 还 有 剩 余 空 间 来 注 入 新 数 据 ), 如 果 我 们 想 在 1 号 房 间 和 2 号 房 间 之 间 插 入 一 个 房 间, 则 必 须 将 2 号 以 后 的 房 间 都 往 后 移 动 一 个 位 置 ( 假 设 房 间 是 可 以 随 意 搬 动 的 ), 即 顺 序 表 做 插 入 操 作 的 时 候 要 移 动 多 个 元 素 而 链 表 就 无 需 这 样, 如 图 2.1(b) 的 链 表, 如 果 想 在 第 一 个 和 第 二 个 房 间 之 间 插 入 一 个 新 房 间, 则 只 需 改 动 房 间 后 边 的 方 向 指 示 箭 头 即 可, 将 第 一 个 房 间 的 箭 头 指 向 新 插 入 的 房 间, 然 后 将 新 插 入 的 房 间 的 箭 头 指 向 第 二 个 房 间 即 可, 即 在 链 表 中 进 行 插 入 操 作 无 需 移 动 元 素 图 2.1 顺 序 表 和 链 表 的 比 较 链 表 有 如 下 5 种 形 式 ( 在 程 序 题 目 中 用 到 的 链 表 结 点 的 c 语 言 描 述 将 在 以 后 的 章 节 中 介 绍 ): (1) 单 链 表 图 2.2 带 头 结 点 的 单 链 表

32 在 每 个 结 点 中 除 了 包 含 数 据 域 外, 还 包 含 一 个 指 针 域, 用 以 指 向 其 后 继 结 点 如 图 2.2 所 示, 即 为 带 头 结 点 的 单 链 表 这 里 要 区 分 一 下 带 头 结 点 的 单 链 表 和 不 带 头 结 点 的 单 链 表 1) 带 头 结 点 的 单 链 表 中 头 指 针 head 指 向 头 结 点, 头 结 点 的 值 域 不 含 任 何 信 息, 从 头 结 点 的 后 继 结 点 开 始 存 储 信 息 头 指 针 head 始 终 不 等 于 NULL,head->next 等 于 NULL 的 时 候 链 表 为 空 2) 不 带 头 结 点 的 单 链 表 其 中 的 头 指 针 head 直 接 指 向 开 始 结 点, 即 图 2.2 中 的 结 点 A1, 当 head 等 于 NULL 的 时 侯 链 表 为 空 总 之, 两 者 最 明 显 的 区 别 是, 带 头 结 点 的 单 链 表 有 一 个 结 点 不 存 储 信 息, 只 是 作 为 标 记, 而 不 带 头 结 点 的 单 链 表 所 有 结 点 都 存 储 信 息 注 意 : 在 题 目 中 要 区 分 头 结 点 和 头 指 针, 不 论 是 带 头 结 点 的 链 表 还 是 不 带 头 结 点 的 链 表, 头 指 针 都 指 向 链 表 中 第 一 个 结 点, 即 图 2.2 中 的 head 指 针 而 头 结 点 是 带 头 结 点 的 链 表 中 的 第 一 个 结 点, 只 作 为 链 表 存 在 的 标 志, 结 点 内 不 存 信 息 (2) 双 链 表 : 图 2.3 双 链 表 单 链 表 只 能 由 开 始 结 点 走 到 终 端 结 点, 而 不 能 由 终 端 结 点 反 向 走 到 开 始 结 点 如 果 要 求 输 出 从 终 端 结 点 到 开 始 结 点 的 数 据 序 列, 则 对 于 单 链 表 来 说 操 作 就 非 常 麻 烦 为 了 解 决 这 类 问 题 我 们 构 造 了 双 链 表 如 图 2.3 所 示, 即 为 带 头 结 点 的 双 链 表 双 链 表 就 是 在 单 链 表 结 点 上 增 添 了 一 个 指 针 域, 指 向 当 前 结 点 的 前 驱 这 样 就 可 以 方 便 的 由 其 后 继 来 找 到 其 前 驱, 而 实 现 输 出 终 端 结 点 到 开 始 结 点 的 数 据 序 列 同 样, 双 链 表 也 分 为 带 头 结 点 的 双 链 表 和 不 带 头 结 点 的 双 链 表, 情 况 类 似 于 单 链 表 带 头 结 点 的 双 链 表 head->next 为 NULL 的 时 候 链 表 为 空 不 带 头 结 点 的 双 链 表 head 为 NULL 的 时 候 链 表 为 空 (3) 循 环 单 链 表 图 2.4 循 环 链 表 知 道 了 单 链 表 的 结 构 之 后, 循 环 单 链 表 就 显 得 比 较 简 单 了, 只 要 将 单 链 表 的 最 后 一 个 指 针 域 ( 空 指 针 ) 指 向 链 表 中 第 一 个 结 点 即 可 ( 这 里 之 所 以 说 第 一 个 结 点 而 不 说 是 头 结 点 是 因 为, 如 果 循 环 单 链 表 是 带 头 结 点 的 则 最 后 一 个 结 点 的 指 针 域 要 指 向 头 结 点 ; 如 果 循 环 单 链 表 不 带 头 结 点, 则 最 后 一 个 指 针 域 要 指 向 开 始 结 点 ) 如 图 2.4 所 示, 即 为 带 头 结 点 的 循 环 单 链 表 循 环 单 链 表 可 以 实 现 从 任 一 个 结 点 出 发 访 问 链 表 中 任 何 结 点, 而 单 链 表 从 任 一 结 点 出 发 后 只 能 访 问 这 个 结 点 本 身 及 其 后 边 的 所 有 结 点 带 头 结 点 的 循 环 单 链 表 当 head 等 于 head->next; 时 链 表 为 空 ; 不 带 头 结 点 的 循 环 单 链 表 当 head 等 于 NULL 时 链 表 为 空

33 (4) 循 环 双 链 表 图 2.5 双 循 环 链 表 和 循 环 单 链 表 类 似, 循 环 双 链 表 的 构 造 源 自 双 链 表, 即 将 终 端 结 点 的 next 指 针 指 向 链 表 中 第 一 个 结 点, 将 链 表 中 第 一 个 结 点 的 prior 指 针 指 向 终 端 结 点, 如 图 2.5 所 示 循 环 双 链 表 同 样 有 带 头 结 点 和 不 带 头 结 点 之 分 带 头 结 点 的 循 环 双 链 表 当 head->next 和 head->prior 两 个 指 针 都 等 于 head 时 链 表 为 空, 不 带 头 结 点 的 循 环 双 链 表 当 head 等 于 NULL 的 时 候 为 空 上 述 前 4 种 链 表 可 以 用 4 种 道 路 来 形 象 的 比 喻 一 下, 如 以 下 图 组 : 单 链 表 : (a) 单 链 表 就 像 图 (a) 中 的 单 行 车 道, 只 允 许 车 辆 往 一 个 方 向 行 驶 双 链 表 : (b) 双 链 表 就 像 图 (b) 中 的 双 向 车 道, 车 辆 既 可 以 从 左 往 右 行 驶, 又 可 以 从 右 向 左 行 驶 循 环 单 链 表 : (c) 循 环 单 链 表 就 像 图 (c) 的 环 形 车 道, 车 辆 可 沿 着 一 个 方 向 行 驶 在 这 条 车 道 上

34 循 环 双 链 表 : (d) 循 环 双 链 表 就 像 图 (d) 的 双 向 环 形 车 道, 车 辆 可 以 沿 着 2 个 方 向 行 驶 在 这 条 车 道 上 (5) 静 态 链 表 这 种 链 表 借 助 一 维 数 组 来 表 示, 如 图 2.6 所 示 图 2.6 静 态 链 表 的 表 示 图 2.6 中 左 图 是 静 态 链 表, 右 图 是 其 对 应 的 一 般 链 表 一 般 链 表 结 点 空 间 是 来 自 于 整 个 内 存, 静 态 链 表 则 来 自 于 一 个 结 构 体 数 组, 数 组 中 每 一 个 结 点 含 有 两 个 分 量, 一 个 是 数 据 元 素 分 量 data, 另 一 个 是 指 针 分 量, 指 示 了 当 前 结 点 的 直 接 后 继 结 点 在 数 组 中 的 位 置 ( 这 和 一 般 链 表 中 next 指 针 的 地 位 是 同 等 的 ) 说 明 : 在 考 研 中 经 常 要 考 到 顺 序 表 和 链 表 的 比 较, 这 里 给 出 一 个 较 为 全 面 的 答 案 : (1) 基 于 空 间 的 比 较 : 存 储 分 配 的 方 式 : 顺 序 表 的 存 储 空 间 是 静 态 分 配 的 链 表 的 存 储 空 间 是 动 态 分 配 的 存 储 密 度 ( 存 储 密 度 = 结 点 数 据 域 所 占 的 存 储 量 / 结 点 结 构 所 占 的 存 储 总 量 ): 顺 序 表 的 存 储 密 度 =1 链 表 的 存 储 密 度 <1( 因 为 结 点 中 有 指 针 域 ) (2) 基 于 时 间 的 比 较 : 存 取 方 式 : 顺 序 表 可 以 随 机 存 取, 也 可 以 顺 序 存 取 ( 对 于 顺 序 表 一 般 只 答 随 机 存 取 即 可 )

35 链 表 是 顺 序 存 取 的 插 入 / 删 除 时 移 动 元 素 个 数 : 顺 序 表 平 均 需 要 移 动 近 一 半 元 素 链 表 不 需 要 移 动 元 素, 只 需 要 修 改 指 针 对 顺 序 表 进 行 插 入 和 删 除 算 法 时 间 复 杂 度 分 析 : 具 有 n 个 元 素 的 顺 序 表 ( 如 下 图 ), 插 入 一 个 元 素 所 进 行 的 平 均 移 动 个 数 为 多 少 ( 假 设 新 元 素 插 入 在 表 中 每 个 元 素 之 后 ) 因 为 题 目 要 计 算 平 均 移 动 个 数, 这 就 是 告 诉 我 们 要 计 算 移 动 个 数 的 期 望 对 于 本 题 要 计 算 期 望 的 话 就 要 知 道 在 所 有 可 能 的 位 置 插 入 元 素 时 所 对 应 的 元 素 移 动 个 数 以 及 在 每 个 位 置 发 生 插 入 操 作 的 概 率 1 求 概 率 : 因 为 插 入 位 置 的 选 择 是 随 机 的, 所 以 所 有 位 置 被 插 入 的 可 能 性 都 是 相 同 的, 有 n 个 可 插 入 位 置, 所 以 任 何 一 个 位 置 被 插 入 元 素 的 概 率 都 为 p=1/n 2 求 对 应 于 每 个 插 位 置 需 要 移 动 的 元 素 个 数 : 假 设 要 把 新 元 素 插 入 在 表 中 第 i 个 元 素 之 后, 则 需 要 将 i 元 素 之 后 的 所 有 元 素 往 后 移 动 一 个 位 置, 因 此 移 动 元 素 个 数 为 n-i 由 1 和 2 知, 移 动 元 素 个 数 的 期 望 为 : 即 要 移 动 近 一 半 元 素, 由 此 即 可 以 知 道, 插 入 和 删 除 算 法 的 平 均 时 间 复 杂 度 为 O(n) 2.2 线 性 表 的 基 本 操 作 线 性 表 的 定 义 #define MAX 100 // 这 里 定 义 一 个 整 型 常 量 MAX, 值 为 顺 序 表 的 结 构 定 义 typedef struct int data[max]; // 存 放 顺 序 表 元 素 的 数 组 ( 默 认 是 int 型, 可 根 据 题 目 要 // 求 将 int 换 成 其 他 类 型 ) int length; // 存 放 顺 序 表 的 长 度 Sqlist; // 顺 序 表 类 型 的 定 义