第2章 计算机辅助系统开发基础知识2.1 数据结构 对于软件开发来说，数据结构具有重要的意义，所谓程序可以看作是数据结构+算法。借助数据结构可以采用相对规范的方法将编程对象加以表述。例如，当我们需要在程序中记录一组等高线数据，并要求表达它们之间的相邻关系（这往往是为了在相邻登高线之间建立三角形数字地面模型），可能就需要借助于树型数据结构了：这时我们利用等高线包围的区域相互包含与否的关系，建立树结构。在图2－1中，等高线A包围的区域直接包含了等高线B、D所包围的区域，B包围的区域包（a） （b） 图2－1 利用树来表示等高线之间的关系含了C所包围区域，D所包围区域包含了E所包围区域。为此建立如图2－1（b）所示的数据结构。这样，只要在父节点与子节点，以及同级子节点之间进一步判别等高线是否相邻，除此之外的情况是属于绝对不会相邻的。2.1.1栈 栈就像在一个只打开一端的乒乓球筒中放入乒乓球一样（参见图2－2），先放入的球需要后取出，具有元素的先进后出特性 ，我们往往利用这一特性 实 现 编程过 程中的某 些 目的。例如，在机场 场 道 设 计CAD系统的平 面布 局 设 计工 作中，由 于工 作带 有试 探 性 质 ，希望 必 要时能够 放弃 一些 刚 刚 完 成 的操 作，以退 回 原 来的某 种 状 态 重新 开始 。这时我们可以将所进行 的设 计工 作（例如增 加了一条 滑 行 道 ）按 照 完 成 的先后顺 序逐 步加入一个信 息 栈中，当需要退 回 原 来的某 一状 态 时，从 栈的顶 端逐 步取出修 改 变 化 情况的信 息 ，一步一步加以恢 复 。首 先恢 复 的是最 后进行 的工 作，直到 达到 希 望 退 回 的状 态 为止 。当然 这种 情况下 如果 栈中已 存 满 了元素，我们需要在栈的另 一端打开取出一些 元素加以放弃 ，以腾 出一些 栈空 间，这是一种 特殊 的取出操 作。 清 楚 了栈的基本 工 作原 理 ，还 需要定 义栈的基本 数据操 作，这样就便 于我们确 定 栈的基本 函 数。在栈上 定 义的基本 运 算一般 有： * 在内 存 空 间建立一个栈； * 检 查 栈中剩 余 的容 量 ； * 从 栈的顶 端推 入一个元素； * 从 栈的顶 端取出一个元素； * 删 除一个栈。 除了这些 基本 运 算之外，我们往往需要定 义一些 辅助运 算，以帮 助完 成 一些 复 杂 ...
