软件设计师考试结合了当前软件设计开发中的主流技术和工程应用背景，强调了主流设计技术的应用问题，读者除应掌握基本的概念和理论基础知识外，还需要正确地针对实践应用中的问题提出合理的解决方案，将一系列的设计方法与原则应用在实际系统的分析、设计和开发环节中。编者委员会总结近几年的软件设计师考试所涉及的应用性内容，将其主要技术领域归纳为以下几点。

  1. 结构化分析与设计。
  2. 数据库分析与设计。
  3. 面向对象分析与设计。
  4. 算法设计与 C 程序实现。
  5. 面向对象的程序设计与实现。

12.1 结构化分析与设计

结构化分析将数据和处理（加工）作为分析对象，数据的分析结果表示了现实世界中实体的属性及其之间的相互关系，而处理的分析结果则展现了系统对数据的加工和转换。面向数据流建模是目前仍然被广泛使用的方法之一，而 DFD 则是面向数据流建模中的重要工具，DFD 将系统建模成输入—处理—输出的模型，即流入软件的数据对象，经由处理的转换，最后以结果数据对象的形式流出软件。DFD 使用分层的方式表示，第一个数据流模型有时被称为第 0 层 DFD 或者环境数据流图。从整体上表现系统，随后的数据流图将改进第 0 层图，并增加细节信息。

除 DFD 外，在进行建模时，还可结合数据字典和加工处理说明对 DFD 进行补充。数据字典以一种准确且无二义的方式定义所有被加工引用的数据流和数据存储，通常包括数据流条目、数据存储条目和数据项条目。数据流条目描述 DFD 中数据流的组成，数据存储条目描述 DFD 中数据存储文件的组成，而数据项条目则描述数据流或数据存储中所使用的数据项。加工处理的说明则可采用结构化自然语言、判定表和判定树等多种形式进行详细描述，其目的在于说明加工做什么。

掌握上述的工具后，即可对问题进行结构化的分析，其实施步骤如下。

  1. 确定系统边界，画出系统环境图。
  2. 自顶向下画出各层数据流图。
  3. 定义数据字典。
  4. 定义加工说明。
  5. 将图、字典以及加工组成分析模型。

在实际使用 DFD 进行数据流建模时，需要注意以下原则。

（1）加工和数据流的正确使用。 如一个加工必须既有输入又有输出；数据流只能和加工相关，即从加工流向加工、数据源流向加工或加工流向数据源。

（2） 每个数据流和数据存储都要在数据字典中有定义，数据字典包括各层数据流图中数据元素的定义。

（3） 数据流图中最底层的加工必须有加工说明。

（4）父图和子图必须平衡。 即父图中某加工的输入/输出（数据流）和分解这个加工的子图的输入/输出数据流必须完全一致。这种一致性不一定要求数据流的名称和个数一一对应，但它们在数据字典中的定义必须一致，数据流或数据项既不能多也不能少。

（5） 加工处理说明和数据流图中加工涉及的元素保持一致。例如，在加工处理说明中，输入数据流必须说明其如何使用，输出数据流说明如何产生或选取，数据存储说明如何选取、使用或修改。

（6） 一幅图中的图元个数控制在 $7\pm2$ 以内。

DFD、数据字典和加工说明可以充分地描述系统的分析模型，其后需要对分析模型进行变换从而得到系统的总体设计模型。系统总体设计模型可以采用层次图、HIPO 图和结构图来表达，但不论是哪一种图形工具，都反映了模块间的调用关系。

在分析模型的基础上进行设计时，主要是针对 DFD 进行变换从而得到模块的调用关系图，因此，需要掌握数据流的变换设计与事务设计。面向数据流的设计方法把数据流图映射成软件结构，数据流图的类型决定了映射的方法，数据流图可分为变换型数据流图和事务型数据流图。变换型数据流图具有明显的输入、变换（或称主加工）和输出；而事务型数据流图则是数据沿输入通路到达一个处理时，这个处理根据输入数据的类型在若干动作序列中选择一个来执行。变换设计的核心在于确定输入流和输出流的边界，从而孤立出变换中心；事务设计的核心在于将事务类型判断处理变换成调度模块以选择后续的输出分支模块。

经过总体设计阶段的工作，已经确定了软件的模块结构和接口描述，但每个模块仍被看作黑盒子。后续的详细设计目标是确定怎样具体地实现所要求的系统，经过详细设计，可以得出对目标系统的精确描述，从而在编码阶段可以将这个描述直接翻译成用某种程序设计语言书写的程序。因此，详细设计的结果基本上决定了最终的程序代码的质量。详细设计可以采用程序流程图、N-S 图、PAD 图和 PDL 语言等工具来表达。下面通过一个案例来说明如何应用结构化分析、总体设计与详细设计技术。

12.1.1 需求说明

图书管理系统的主要功能包括图书购入、借阅、归还以及注销。管理人员可以查询读者、图书的借阅情况，还可对当前图书借阅情况进行统计，给出统计数据。简单的图书管理系统针对图书进行 4 个方面的管理：购入新书、读者借书、读者还书以及图书注销。

购入新书需要为该书编制图书卡片，包括分类目录号、流水号（保证每本书都有唯一的流水号，同类图书也是如此）、书名、作者、内容摘要、价格和购书日期等信息，并将这些信息写入图书目录文件中。

读者借书时需填写借书单，包括读者号、欲借图书分类目录号，系统首先检查该读者号是否有效，若无效，则拒绝借书；否则进一步检查该读者所借图书是否超过最大限制数。若已达到最大限制数，则拒绝借书；若未达到最大限制数，读者可以借出该书，登记图书分类目录号、读者号和借阅日期等，写回到借书文件中。

读者还书时，根据图书分类目录号，从借书文件中读出和该图书相关的借阅记录，标明还书日期，再写回借书文件中。如果图书逾期未还，则处以相应罚款。

在某些情况下，需要对图书馆的图书进行清理工作，对一些过时或无继续保留价值的图书要注销，这时从图书文件里删除相关记录。

查询要求分为查询读者信息、图书信息和借阅统计信息 3 种。

12.1.2 结构化分析

结构化分析的最终结果需要得到系统的数据流图、数据字典和加工说明。根据需求说明，首先界定系统的边界。因为购入新书、读者借书、读者还书和图书注销将来都是由图书管理员来操作系统，因此图书管理员将是系统的外部实体之一。当读者借书超期时，系统会给读者一个罚款单信息，所以，这里可以将系统时钟和读者也作为系统的外部实体之一。当然，如果认为罚款单是由系统管理员转交给读者，则可以认为图书管理系统只和管理员与系统时钟进行交互，这里采用第二种观点。查询要求同样都是由系统管理员来操作，由此可以得出系统不完整的第 0 层 DFD 数据流图。

在 0 层 DFD 图上分析外部实体与系统间的数据流，因为管理员的两大工作任务是分析管理任务和查询任务，因此管理员会向系统输入管理请求信息与查询请求信息，根据输入的管理请求，系统将会对一些存储文件进行修改；对查询请求，系统则会给出读者、图书与借阅的统计信息。系统时钟主要为图书管理系统提供系统时间。

随后对 0 层 DFD 数据流图中的图书管理系统进行进一步细化，根据需求得知，系统主要分为管理任务和查询任务，因此可以将其细化为两个大的处理：查询和管理。

同样，对管理处理进行进一步细化，管理处理分为购书、借书、还书和清理 4 项任务，因此可以将管理处理分解为 4 个处理，另外需要一个单独的处理根据管理请求的类型进行请求分派。

同样的方法，可以对查询处理也进行细化。细化完成后，对得到的数据流图进行转化，从而形成系统的总体设计。但在转换之前，应该对数据流图中的数据流采用数据字典进行详细的说明，例如：

  1. 管理请求 = 清理请求 | 购书请求 | 借书请求 | 还书请求
  2. 清理请求 = 图书分类目录号

对于底层处理，以处理 2.3 为例进行说明。

  • 加工编号：2.3
  • 加工名称：借书
  • 输入流：借书请求，读者信息，借书信息
  • 输出流：更新库存信息，借书信息
  • 处理逻辑：根据读者信息和借书信息，首先判断读者是否合法，判断读者是否已经超出借阅图书数目的最大限制，若都合法，将借书信息重新写入借书文件中，同时更新图书目录文件。

12.1.3 总体设计

由于数据流呈现了事务型的特性，因此可采用事务型的变换方式对数据流图进行变换，得到系统的总体结构。

总体设计给出了数据流图中的各个处理转换为模块后模块与模块之间的调用关系，后续需要根据总体设计给出模块的详细设计。系统总体结构分为查询和管理两大模块，其中管理模块下又分为购书、借书、还书、清理等子模块。

12.1.4 详细设计

以借书为例，采用程序流程图的形式描述借书模块的详细设计。分析借书的输入是读者信息和借书信息，需要读者信息的读者借书证号，借书信息给出了读者已经借阅了多少本书，如果读者借阅的书籍数目尚未超出系统的限制，则允许继续借书，并把新的借书信息写入借书文件；否则，拒绝借书。

完成对每一个模块的详细设计，即可将详细设计转换为程序代码，从而实现整个管理系统。

12.2 数据库分析与设计

数据库设计属于系统设计的范畴。通常把使用数据库的系统统称为数据库应用系统，把对数据库应用系统的设计简称为数据库设计。数据库设计的任务是针对一个给定的应用环境，在给定的（或选择的）硬件环境和操作系统及数据库管理系统等软件环境下，创建一个性能良好的数据库模式，建立数据库及其应用系统，使之能有效地存储和管理数据，满足各类用户的需求。合理的数据库结构是数据库应用系统性能良好的基础和保证，但数据库的设计和开发却是一项庞大而复杂的工程。从事数据库设计的人员，不仅要具备数据库知识和数据库设计技术，还要有程序开发的实际经验，掌握软件工程的原理和方法。数据库设计人员必须深入应用环境，了解用户具体的专业业务。在数据库设计的前期和后期，与应用单位人员密切联系，共同开发，可大大提高数据库设计的成功率。

12.2.1 数据库设计的策略与步骤

1. 数据库设计的策略

数据库设计的一般策略有两种：自顶向下（Top Down）和自底向上（Bottom Up）。自顶向下是从一般到特殊的开发策略。它是从一个企业的高层管理着手，分析企业的目标、对象和策略，构造抽象的高层数据模型。然后逐步构造越来越详细的描述和模型（子系统的模型）。模型不断地扩展细化，直到能识别特定的数据库及其应用为止。

自底向上的开发采用与抽象相反的顺序进行。它从各种基本业务和数据处理着手，即从一个企业的各个基层业务子系统的业务处理开始，进行分析和设计。然后将各子系统进行综合和集中，进行上一层系统的分析和设计，将不同的数据进行综合。最后得到整个信息系统的分析和设计。这两种方法各有优缺点。在实际的数据库设计开发过程中，常常把这两种方法综合起来使用。

2. 数据库设计的步骤

多年来，人们提出了多种数据库设计方法、多种设计准则和规范。1978 年 10 月召开的新奥尔良（New Orleans）会议提出的关于数据库设计的步骤（简称新奥尔良法）是目前得到公认的，较完整、较权威的数据库设计方法，它把数据库设计分为以下 4 个主要阶段。

（1）用户需求分析。 数据库设计人员采用一定的辅助工具对应用对象的功能、性能和限制等要求所进行的科学分析。

（2）概念设计。 概念结构设计是对信息分析和定义，如视图模型化、视图分析和汇总。该阶段对应用对象精确地进行抽象和概括，以形成独立于计算机系统的企业信息模型。描述概念模型较理想的是采用 E-R 方法。

（3）逻辑设计。 将抽象的概念模型转化为与选用的 DBMS 产品所支持的数据模型相符合的逻辑模型，它是物理设计的基础，包括模式初始设计、子模式设计、应用程序设计、模式评价以及模式求精。

（4）物理设计。 逻辑模型在计算机中的具体实现方案。

当各阶段发现不能满足用户需求时，均需返回到前面适当的阶段，进行必要的修正。如此经过不断地迭代和求精，直到各种性能均能满足用户的需求为止。

12.2.2 需求分析

需求分析是在项目确定之后，用户和设计人员对数据库应用系统所要涉及的内容（数据）和功能（行为）的整理和描述，是以用户的角度来认识系统。这一过程是后续开发的基础，以后的逻辑设计和物理设计以及应用程序的设计都会以此为依据。

1. 需求分析的任务、目标及方法

需求分析阶段的任务：综合各个用户的应用需求，对现实世界要处理的对象（组织、部门和企业等）进行详细调查，在了解现行系统的情况，确定新系统功能的过程中，收集支持系统目标的基础数据及处理方法。

参与需求分析的主要人员是分析人员和用户。这是由于数据库应用系统是面向企业和部门的具体业务，分析人员一般并不了解，而同样用户也不会具有系统分析的能力，这就需要双方进行有效的沟通，使得设计人员对用户的各项业务了解和熟悉，进行分析和加工，将用户眼中的业务转换成为设计人员所需要的信息组织。

分析和表达用户需求的方法主要包括自顶向下和自底向上两类方法。自顶向下的结构化分析（Structured Analysis, SA）方法从最上层的系统组织机构入手，采用逐层分解的方式分析系统，并把每一层用数据流图和数据字典描述。需求分析的重点是调查组织机构情况、调查各部门的业务活动情况、协助用户明确对新系统的各种要求、确定新系统的边界，以此获得用户对系统的如下要求。

（1）信息要求。 用户需要在系统中保存哪些信息，由这些保存的信息要得到什么样的信息，这些信息以及信息间应当满足的完整性要求。

（2）处理要求。 用户在系统中要实现什么样的操作功能，对保存信息的处理过程和方式，各种操作处理的频度、响应时间要求、处理方式等以及处理过程中的安全性要求和完整性要求。

（3）系统要求。 系统要求包括安全性要求、使用方式要求和可扩充性要求。其中，安全性要求是指系统有几种用户使用，每一种用户的使用权限如何；使用方式要求是指用户的使用环境是什么，平均有多少用户同时使用，最高峰时有多少用户同时使用，有无查询相应的时间要求等；可扩充性要求是指对未来功能、性能和应用访问的可扩充性的要求。

2. 需求分析阶段的文档

需求调查所得到的数据可能是零碎的、局部的，分析师和设计人员必须进一步分析和表达用户的需求，建立需求说明文档、数据字典和数据流程图。将需求调查文档化，文档既要被用户所理解，又要方便数据库的概念结构设计。

数据流分析是对事务处理所需的原始数据的收集及经处理后所得数据及其流向，一般用数据流图（DFD）来表示。DFD 不仅指出了数据的流向，而且指出了需要进行的事务处理（但并不涉及如何处理，这是应用程序的设计范畴）。除了使用数据流图、数据字典以外，需求分析还可使用判定表、判定树等工具。

数据字典是各类数据描述的集合，它是关于数据库中数据的描述，即元数据，而不是数据本身。如用户将向数据库中输入什么信息，从数据库中要得到什么信息，各类信息的内容和结构，信息之间的联系等。数据字典包括数据项、数据结构、数据流、数据存储和加工 5 个部分（至少应该包含每个字段的数据类型和在每个表内的主键、外键）。

  1. 数据项描述 = {数据项名，数据项含义说明，别名，数据类型，长度，
  2.               取值范围，取值含义，与其他数据项的逻辑关系}
  4. 数据结构描述 = {数据结构名，含义说明，组成：{数据项或数据结构}}
  6. 数据流描述 = {数据流名，说明，数据流来源，数据流去向，
  7.              组成：{数据结构}，平均流量，高峰期流量}
  9. 数据存储描述 = {数据存储名，说明，编号，流入的数据流，流出的数据流，
  10.                组成：{数据结构}，数据量，存取方式}
  12. 加工描述 = {加工名，说明，输入：{数据流}，输出：{数据流}，
  13.            处理：{简要说明}}

需求分析阶段的成果是系统需求说明书，主要包括数据流图、数据字典、各种说明性表格、统计输出表和系统功能结构图等。系统需求说明书是以后设计、开发、测试和验收等过程的重要依据。

12.2.3 概念结构设计

数据库概念结构设计阶段是在需求分析的基础上，依照需求分析中的信息要求对用户信息加以分类、聚集和概括，建立信息模型，并依照选定的数据库管理系统软件转换成为数据的逻辑结构，再依照软/硬件环境，最终实现数据的合理存储，这一过程也称为数据建模。

数据库概念结构设计的目标是产生反映系统信息需求的数据库概念结构，即概念模式。概念结构是独立于支持数据库的 DBMS 和使用的硬件环境的。此时，设计人员从用户的角度看待数据以及数据处理的要求和约束，产生一个反映用户观点的概念模式，然后再把概念模式转换为逻辑模式。

1. 概念结构设计策略与方法

概念结构设计是设计人员以用户的观点对用户信息的抽象和描述，从认识论的角度来讲，它是从现实世界到信息世界的第一次抽象，并不考虑具体的数据库管理系统。

现实世界的事物纷繁复杂，即使是对某一具体的应用，由于存在大量不同的信息和对信息的各种处理，也必须加以分类整理，理清各类信息之间的关系，描述信息处理的流程，这一过程就是概念结构设计。

概念结构设计的策略通常有以下 4 种：自顶向下、自底向上、逐步扩张和混合策略。在实际应用中这些策略并没有严格的限定，可以根据具体业务的特点选择，如对于组织机构管理，因其固有的层次结构，可采用自顶向下的策略；对于已实现计算机管理的业务，通常可以以此为核心，采取逐步扩张的策略。

概念结构设计最著名、最常用的方法是 P.P.S Chen 于 1976 年提出的实体-联系（Entity-Relationship Approach, E-R）方法。它采用 E-R 模型将现实世界的信息结构统一由实体、属性以及实体之间的联系来描述。

使用 E-R 方法，无论是哪种策略，都要对现实事物加以抽象，以 E-R 图的形式描述出来。

2. 用 E-R 方法建立概念模型

E-R 图的设计要依照上述的抽象机制，对需求分析阶段所得到的数据进行分类、聚集和概括，确定实体、属性和联系。概念结构的具体工作步骤包括选择局部应用、逐一设计分 E-R 图和 E-R 图合并。

（1）选择局部应用。 需求分析阶段会得到大量的数据，这些数据分散杂乱，许多数据会应用于不同的处理，数据与数据之间关联关系也较为复杂，要最终确定实体、属性和联系，就必须根据数据流图这一线索理清数据。

数据流图是对业务处理过程从高层到底层的一级抽象，高层抽象流图一般反映系统的概貌，对数据的引用较为笼统，而底层又可能过于细致，不能体现数据的关联关系，因此要选择适当层次的数据流图，让这一层的每一部分对应一个局部应用，实现某一项功能。从这一层入手，就能很好地设计分 E-R 图。

（2）逐一设计分 E-R 图。 划分好各个局部应用之后，就要对每一个局部应用逐一设计分 E-R 图，又称为局部 E-R 图。对于每一局部应用，其所用到的数据都应该收集在数据字典中，依照该局部应用的数据流图，从数据字典中提取出数据，使用抽象机制确定局部应用中的实体、实体的属性、实体标识符及实体间的联系及其类型。

事实上，在形成数据字典的过程中，数据结构、数据流和数据存储都是根据现实事物来确定的，因此都已经基本上对应了实体及其属性，以此为基础，加以适当调整，增加联系及其类型，就可以设计分 E-R 图。

现实生活中，许多事物作为实体还是属性没有明确的界定，这需要根据具体情况而定，一般遵循以下两条准则。

  • ① 属性不可再分，即属性不再具有需要描述的性质，不能有属性的属性。
  • ② 属性不能与其他实体发生联系，联系是实体与实体间的联系。

（3）E-R 图合并。 根据局部应用设计好各局部 E-R 图之后，就可以对各分 E-R 图进行合并。合并的目的在于在合并过程中解决分 E-R 图中相互间存在的冲突，消除分 E-R 图之间存在的信息冗余，使之成为能够被全系统所有用户共同理解和接受的统一的、精炼的全局概念模型。合并的方法是将具有相同实体的两个或多个 E-R 图合而为一，在合成后的 E-R 图中把相同实体用一个实体表示，合成后的实体的属性是所有分 E-R 图中该实体的属性的并集，并以此实体为中心，并入其他所有分 E-R 图。再把合成后的 E-R 图以分 E-R 图看待，合并剩余的分 E-R 图，直到所有的 E-R 图全部合并，就构成一张全局 E-R 图。

分 E-R 图之间的冲突主要有以下三类。

  • ① 属性冲突。 同一属性可能会存在于不同的分 E-R 图，由于设计人员不同或是出发点不同，对属性的类型、取值范围和数据单位等可能会不一致，这些属性对应的数据将来只能以一种形式在计算机中存储，这就需要在设计阶段进行统一。
  • ② 命名冲突。 相同意义的属性在不同的分 E-R 图上有着不同的命名，或是名称相同的属性在不同的分 E-R 图中代表着不同的意义，这些也要进行统一。
  • ③ 结构冲突。 同一实体在不同的分 E-R 图中有不同的属性，同一对象在某一分 E-R 图中被抽象为实体，而在另一分 E-R 图中又被抽象为属性，需要统一。

分 E-R 图的合并过程中要对其进行优化，具体可以从以下三个方面实现。

  • ① 实体类型的合并。 两个具有 $1:1$ 联系或 $1:n$ 联系的实体可以予以合并，使实体个数减少，有利于减少将来数据库操作过程中的连接开销。
  • ② 冗余属性的消除。 一般在各分 E-R 图中的属性是不存在冗余的，但合并后就可能出现冗余。因为合并后的 E-R 图中的实体继承了合并前该实体在分 E-R 图中的全部属性，属性间就可能存在冗余，即某一属性可以由其他属性确定。
  • ③ 冗余联系的消除。 在分 E-R 图合并的过程中可能会出现实体联系的环状结构，即某一实体 A 与另一实体 B 间有直接联系，同时 A 又通过其他实体与实体 B 发生间接联系。通常，直接联系可以通过间接联系所表达，可消除直接联系。

12.2.4 逻辑结构设计

逻辑结构设计即是在概念结构设计的基础上进行数据模型设计，可以是层次模型、网状模型和关系模型，本节介绍如何在全局 E-R 图基础上进行关系模型的逻辑结构设计。逻辑结构设计阶段的主要工作步骤包括确定数据模型、将 E-R 图转换成为指定的数据模型、确定完整性约束和确定用户视图。

1. E-R 图关系模式的转换

E-R 方法所得到的全局概念模型是对信息世界的描述，并不适用于计算机处理，为适合关系数据库系统的处理，必须将 E-R 图转换成关系模式。E-R 图是由实体、属性和联系三要素构成，而关系模型中只有唯一的结构——关系模式，通常采用以下方法加以转换。

1）实体向关系模式的转换

将 E-R 图中的实体逐一转换成为一个关系模式，实体名对应关系模式的名称，实体的属性转换成关系模式的属性，实体标识符就是关系的码（键）。

2）联系向关系模式的转换

E-R 图中的联系有 3 种：一对一联系（$1:1$）、一对多联系（$1:n$）和多对多联系（$m:n$），针对这 3 种不同的联系，转换方法如下。

（1）一对一联系的转换。 一对一联系有两种方式向关系模式进行转换。一种方式是将联系转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性包括该联系所关联的两个实体的码及联系的属性，关系的码取自任一方实体的码；另一种方式是将联系归并到关联的两个实体的任一方，给待归并的一方实体属性集中增加另一方实体的码和该联系的属性即可，归并后的实体码保持不变。

（2）一对多联系的转换。 一对多联系有两种方式向关系模式进行转换。一种方式是将联系转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性取该联系所关联的两个实体的码及联系的属性，关系的码是多方实体的码；另一种方式是将联系归并到关联的两个实体的多方，给待归并的多方实体属性集中增加一方实体的码和该联系的属性即可，归并后的多方实体码保持不变。

（3）多对多联系的转换。 多对多联系只能转换成一个独立的关系模式，关系模式的名称取联系的名称，关系模式的属性取该联系所关联的两个多方实体的码及联系的属性，关系的码是多方实体的码构成的属性组。

2. 关系模式的规范化

由 E-R 图转换所得的初始关系模式并不一定能完全符合要求，还可能会有数据冗余、更新异常存在，这就需要经过进一步的规范化处理，具体步骤如下。

（1） 根据语义确定各关系模式的数据依赖。在设计的前一阶段，只是从关系及其属性来描述关系模式，并没有考虑到关系模式中的数据依赖。关系模式包含着语义，要根据关系模式所描述的自然语义写出关系数据依赖。

（2） 根据数据依赖确定关系模式的范式。由关系的码及数据依赖，根据规范化理论，就可以确定关系模式所属的范式，判定关系模式是否符合要求，即是否达到了 3NF 或 4NF。

（3） 如果关系模式不符合要求，要根据关系模式的分解算法对其进行分解，达到 3NF、BCNF 或 4NF。

（4） 关系模式的评价及修正。根据规范化理论对关系模式分解之后，就可以在理论上消除冗余和更新异常。但根据处理要求，可能还需要增加部分冗余以满足处理要求，这就需要做部分关系模式的处理，分解、合并或增加冗余属性，提高存储效率和处理效率。

3. 确定完整性约束

根据规范化理论确定了关系模式之后，还要对关系模式加以约束，包括数据项的约束、表级约束及表间约束，可以参照 SQL 标准来确定不同的约束，如检查约束、主码约束和参照完整性约束，以保证数据的正确性。

4. 用户视图的确定

确定了整个系统的关系模式之后，还要根据数据流图及用户信息建立视图模式，提高数据的安全性和独立性。

（1） 根据数据流图确定处理使用的视图。数据流图是某项业务的处理，使用了部分数据，这些数据可能要跨越不同的关系模式，建立该业务的视图，可以降低应用程序的复杂性，并提高数据的独立性。

（2） 根据用户类别确定不同用户使用的视图。不同的用户可以处理的数据可能只是整个系统的部分数据，而确定关系模式时并没有考虑这一因素，如学校的学生管理，不同的院系只能访问和处理自己的学生信息，这就需要建立针对不同院系的视图达到这一要求，这样可以在一定程度上提高数据的安全性。

12.2.5 数据库的物理设计

数据库系统实现是离不开具体的计算机的，在实现数据库逻辑结构设计之后，就要确定数据库在计算机中的具体存储。数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。为一个给定的逻辑数据模型设计一个最适合应用要求的物理结构的过程，就是数据库的物理设计。

在数据库的物理结构中，数据的基本单位是记录，记录是以文件的形式存储的，一条存储记录就对应着关系模式中的一条逻辑记录。在文件中还要存储记录的结构，如各字段长度、记录长度等，增加必要的指针及存储特征的描述。

数据库的物理设计是离不开具体的 DBMS 的，不同 DBMS 对物理文件存取方式的支持不同，设计人员必须充分了解所用 DBMS 的内部特征，根据系统的处理要求和数据的特点来确定物理结构。

一般来说，物理设计包括确定数据分布、存储结构和访问方式的工作。

1. 确定数据分布

从企业计算机应用环境出发，需要确定数据是集中管理还是分布式管理。目前，企业内部网及因特网的应用越来越广泛，大多采用分布式管理。对于数据如何分布需要从以下几个方面考虑。

（1）根据不同应用分布数据。 企业的不同部门一般会使用不同数据，将与部门应用相关的数据存储在相应的场地，使得不同的场地上处理不同的业务，对于应用多个场地的业务，可以通过网络进行数据处理。

（2）根据处理要求确定数据的分布。 对于不同的处理要求，也会有不同的使用频度和响应时间，对于使用频度高、响应时间短的数据，应存储在高速设备上。

（3） 对数据的分布存储必然会导致数据的逻辑结构的变化，要对关系模式做新的调整，回到数据库逻辑设计阶段做必要的修改。

2. 确定数据的存储结构

存储结构具体指数据文件中记录之间的物理结构。在文件中，数据是以记录为单位存储的，可以是顺序存储、哈希存储、堆存储和 B+ 树存储等，要根据数据的处理要求和变更频度选定合理的物理结构。

为提高数据的访问速度，通常会采用索引技术。在物理设计阶段，要根据数据处理和修改…

3. 确定数据的访问方式

数据的访问方式是由其存储结构所决定的，采用什么样的存储结构，就使用什么样的访问方式。数据库物理结构主要由存储记录格式、记录在物理设备上的安排及访问路径（存取方法）等构成。

1）存储记录结构设计

存储记录结构包括记录的组成、数据项的类型、长度和数据项间的联系，以及逻辑记录到存储记录的映射。在设计记录的存储结构时，并不改变数据库的逻辑结构，但可以在物理上对记录进行分割。数据库中数据项的被访问频率是很不均匀的，基本上符合公认的“80/20 规则”，即“从数据库中检索的 80% 的数据由其中的 20% 的数据项组成”。

当多个用户同时访问常用数据项时，会因访盘冲突而等待。如果将这些数据分布在不同的磁盘组上，当用户同时访问时，系统就可并行地执行 I/O，减少访盘冲突，提高数据库的性能。所以对于常用关系，最好将其水平分割成多个裂片，分布到多个磁盘组上，以均衡各个磁盘组的负荷，发挥多磁盘组并行操作的优势。

2）存储记录布局

存储记录的布局，就是确定数据的存放位置。存储记录作为一个整体，如何分布在物理区域上，是数据库物理结构设计的重要一环。聚簇功能可以大大提高按聚簇码进行查询的效率。聚簇功能不仅可用于单个关系，也适用于多个关系。设有职工表和部门表，其中部门号是这两个表的公共属性。如果查询涉及这两个表的连接操作，可以把部门号相同的职工元组和部门元组在物理上聚簇在一起，既可显著提高连接操作的速度，又可节省存储空间。建立聚簇索引的原则如下：

（1）聚簇码的值相对稳定，没有或很少需要进行修改。

（2）表主要用于查询，并且通过聚簇码进行访问或连接是该表的主要应用。

（3）对应每个聚簇码值的平均元组数既不太多，也不太少。

任何事物都有两面性，聚簇对于某些特定的应用可以明显地提高性能，但对于与聚簇码无关的查询却毫无益处。相反地，当表中数据有插入、删除、修改时，关系中的有些元组就要被搬动后重新存储，建立聚簇的维护代价很大。

3）存取方法的设计

存取方法是为存储在物理设备（通常是外存储器）上的数据提供存储和检索的能力。存取方法包括存储结构和检索机制两部分。存储结构限定了可能访问的路径和存储记录；检索机制定义每个应用的访问路径。

存取方法是快速存取数据库中数据的技术。数据库系统是多用户共享系统，对同一个关系建立多条存取路径才能满足多用户的多种应用要求。为关系建立多种存取路径是数据库物理设计的另一个任务，在数据库中建立存取路径最普遍的方法是建立索引。确定索引的一般顺序如下：

（1）首先可确定关系的存储结构，即记录的存放是无序的，还是按某属性（或属性组）聚簇存放。由于在前面已讨论过，这里不再重复。

（2）确定不宜建立索引的属性或表。对于太小的表、经常更新的属性或表、属性值很少的表、过长的属性、一些特殊数据类型的属性（大文本、多媒体数据）和不出现或很少出现在查询条件中的属性不宜建立索引。

（3）确定宜建立索引的属性。例如关系的主码或外部码、以查询为主或只读的表、范围查询、聚集函数（Min、Max、Avg、Sum、Count）或需要排序输出的属性可以考虑建立索引。

索引一般还需在数据库运行测试后，再加以调整。在 RDBMS 中，索引是改善存取路径的重要手段。使用索引的最大优点是可以减少检索的 CPU 服务时间和 I/O 服务时间，改善检索效率。但是，不能对进行频繁存储操作的关系建立过多的索引，因为过多的索引也会影响存储操作的性能。

12.2.6 数据库的实施与维护

在数据库正式投入运行之前，还需要完成很多工作。例如，在模式和子模式中加入数据库安全性、完整性的描述，完成应用程序和加载程序的设计，数据库系统的试运行，并在试运行中对系统进行评价。如果评价结果不能满足要求，还需要对数据库进行修正设计，直到满意为止。数据库正式投入使用，也并不意味着数据库设计生命周期的结束，而是数据库维护阶段的开始。

1. 数据库的实施

根据逻辑和物理设计的结果在计算机上建立起实际的数据库结构并装入数据进行试运行和评价的过程叫作数据库的实施（或实现）。

1）建立实际的数据库结构

用 DBMS 提供的数据定义语言（DDL）编写描述逻辑设计和物理设计结果的程序（一般称为数据库脚本程序），经计算机编译处理和执行后，就生成了实际的数据库结构。所用 DBMS 的产品不同，描述数据库结构的方式也不同。有的 DBMS 提供数据定义语言，有的提供数据库结构的图形化定义方式，有的两种方法都提供。在定义数据库结构时，应包含以下内容：

（1）数据库模式与子模式，以及数据库空间等的描述。例如，在 Oracle 系统中，数据库逻辑结果的描述包括表空间（Tablespace）、段（Segment）、范围（Extent）和数据块（Data block）。DBA 或设计人员通过对数据库空间的管理和分配，可控制数据库中数据的磁盘分配，将确定的空间份额分配给数据库用户，控制数据的可用性，将数据存储在多个设备上，以提高数据库性能等。

（2）数据库完整性描述。所谓数据的完整性，是指数据的有效性、正确性和一致性。在数据库设计时，如果没有一定的措施确保数据库中数据的完整性，就无法从数据库中获得可信的数据。数据的完整性设计，应该贯穿在数据库设计的全过程中。例如，在数据需求分析阶段，收集数据信息时，应该向有关用户调查该数据的有效值范围。在模式与子模式中，可以用 DBMS 提供的 DDL 语句描述数据的完整性。

（3）数据库安全性描述。数据安全性设计同数据完整性设计一样，也应在数据库设计的各个阶段加以考虑。在进行需求分析时，分析人员除了收集数据及数据间联系的信息之外，还必须收集关于数据的安全性说明。在设计数据库逻辑结构时，对于保密级别高的数据，可以单独进行设计。子模式是实现安全性要求的一个重要手段，可以为不同的应用设计不同的子模式。在数据操纵上，系统可以对用户的数据操纵进行两方面的控制：一是给合法用户授权，目前主要有身份验证和口令识别；二是给合法用户不同的存取权限。

（4）数据库物理存储参数描述。物理存储参数因 DBMS 的不同而不同。一般可设置的参数包括块大小、页面大小（字节数或块数）、数据库的页面数、缓冲区个数、缓冲区大小和用户数等。详细内容请参考 DBMS 的用户手册。

2）数据的加载

数据库应用程序的设计应该与数据库设计同时进行。一般地，应用程序的设计应该包括数据库加载程序的设计。在数据加载前，必须对数据进行整理。由于用户缺乏计算机应用背景的知识，常常不了解数据的准确性对数据库系统正常运行的重要性，因而未对提供的数据作严格的检查。所以，在数据加载前要建立严格的数据登录、输入和校验规范，设计完善的数据校验与校正程序，排除不合格数据。

数据加载分为手工输入和使用数据转换工具两种。现有的 DBMS 都提供了 DBMS 之间数据转换的工具。如果用户原来就使用数据库系统，可以利用新系统的数据转换工具。先将原系统中的表转换成新系统中相同结构的临时表，然后对临时表中的数据进行处理后插入到相应表中。另外，由于还需要对数据库系统进行联合调试，所以大部分的数据加载工作应在数据库的试运行和评价工作中分批进行。

3）数据库的试运行和评价

当加载了部分必须的数据和应用程序后，就可以开始对数据库系统进行联合调试，称为数据库的试运行。一般将数据库的试运行和评价结合起来，目的是测试应用程序的功能；测试数据库的运行效率是否达到设计目标，是否为用户所容忍。测试的目的是为了发现问题，而不是为了说明能达到哪些功能。因此，测试中一定要有非设计人员的参与。

2. 数据库的维护

只有数据库顺利地进行了实施，才可将系统交付使用。数据库一旦投入运行，就标志着数据库维护工作的开始。数据库维护工作的内容主要包括对数据库的监测和性能改善、故障恢复、数据库的重组和重构。在数据库运行阶段，对数据库的维护主要由 DBA 完成。

（1）对数据库性能的监测和改善。性能可以用处理一个事务的 I/O 量、CPU 时间和系统响应时间来度量。由于数据库应用环境、物理存储的变化，特别是用户数和数据量的不断增加，数据库系统的运行性能会发生变化。某些数据库结构（如数据页和索引）经过一段时间的使用以后，可能会被破坏。所以，DBA 必须利用系统提供的性能监控和分析工具，经常对数据库的运行、存储空间及响应时间进行分析，结合用户的反映确定改进措施。目前的 DBMS 都提供一些系统监控或分析工具。例如，在 SQL Server 中使用 SQL Server Profiler 组件、Transaction-SQL 工具和 Query Analyzer 组件等都可进行系统监测和分析。

（2）数据库的备份及故障恢复。数据库是企业的一种资源，所以在数据库设计阶段，DBA 应根据应用要求制定不同的备份方案，保证一旦发生故障能很快将数据库恢复到某种一致性状态，尽量减少损失。数据库的备份及故障恢复方案，一般基于 DBMS 提供的恢复手段。

（3）数据库重组和重构。数据库运行一段时间后，由于记录的增、删、改，数据库中物理存储碎片记录链过多，影响了数据库的存取效率。这时，需要对数据库进行重组和部分重组。数据库的重组是指在不改变数据库逻辑和物理结构的情况下去除数据库存储文件中的废弃空间以及碎片空间中的指针链，使数据库记录在物理上紧连。数据库的重构是指当数据库的逻辑结构不能满足当前数据处理的要求时对数据库的模式和内模式修改。

注意：由于数据库重构的困难和复杂性，数据库的重构一般都在迫不得已的情况下才进行。例如，应用需求发生了变化，需要增加新的应用或实体，取消某些应用或实体。又如，表的增删、表中数据项的增/删、数据项类型的变化等。重构数据库后，还需要修改相应的应用程序，并且重构也只能对部分数据库结构进行。一旦应用需求变化太大，需要对全部数据库结构进行重组，说明该数据库系统的生命周期已经结束，需要设计新的数据库应用系统。

12.2.7 案例分析

某单位图书馆需要建立一个图书管理系统，在图书管理过程中，由于要处理多种不同的业务流程，各个部门之间有相互联系。

1. 图书管理需求分析

通过对图书管理日常工作的详细调查，该图书馆对某书目的信息如表 12-1 所示，与该书目对应的图书信息如表 12-2 所示。

表 12-1 书目信息

书名 作者 出版商 ISBN 号 出版年月 册数 经办人
数据结构 严蔚敏 吴伟民 清华大学出版社 ISBN7-302-02368-9 1997.4 4 01

表 12-2 图书信息

图书 ID ISBN 号 存放位置 状态 经办人
C832.1 ISBN7-302-02368-9 图书流通室 已借出 01
C832.2 ISBN7-302-02368-9 图书阅览室 不外借 01
C832.3 ISBN7-302-02368-9 图书流通室 未借出 01
C832.4 ISBN7-302-02368-9 图书流通室 已预约 01
1）初步的需求分析结果

（1）资料室有图书管理员若干名，他们负责已购入图书的编目和借还工作，每名图书管理员的信息包括工号和姓名。

（2）读者可在阅览室读书，也可通过图书流通室借还图书，读者信息包括姓名、年龄、工作单位、借书证号、电话和 E-mail，系统为不同读者生成不同的借书证号。

（3）每本书在系统中对应唯一的一条图书在版编目数据（CIP，以下简称书目），书目的基本信息包括 ISBN 号、书名、作者、出版商、出版年月以及本资料室拥有该书的册数（以下简称册数），不同书目的 ISBN 号不相同。

（4）资料室对于同一书目的图书可拥有多册（本），图书信息包括图书 ID、ISBN 号、存放位置和当前状态，每一本书在系统中被赋予唯一的图书 ID。

（5）一名读者最多只能借阅 10 本图书，且每本图书最多只能借两个月，读者借书时需由图书管理员登记读者 ID、所借图书 ID、借阅时间和应还时间，读者还书时图书管理员在对应的借书信息中记录归还时间。

（6）当某书目的可借出图书的数量为 0 时，读者可以对其进行预约登记，即记录读者 ID、需要借阅的图书的 ISBN 号和预约时间。

2）业务流程

系统的主要业务处理如下：

（1）入库管理。图书购进入库时，管理员查询本资料室的书目信息，若该书的书目尚未建立，则由管理员编写该书的书目信息并输入系统，然后编写并输入图书信息；否则，修改该书目的册数，然后编写并输入图书信息。对于进入流通室的书，其初始状态为“未借出”，而送入阅览室的书的状态始终为“不外借”。

（2）图书证注册和注销。登记所有办理的新图书证和注销图书证，需要注明办理及注销日期及管理员号。

（3）挂失管理。挂失管理包括挂失登记和解除挂失，挂失登记指登记挂失的借书证，使得该图书证不能借书，注明挂失日期及管理员号；解除挂失指解除已经挂失的借书证，使得该借书证可以开始借书，注明解除挂失日期及管理员号。

（4）借书管理。读者借书时，若有，则由管理员为该读者办理借书手续，并记录该读者的借书信息，同时将借出图书的状态修改为“已借出”。

（5）预约管理。若图书流通室没有读者要借的书，则可为该读者建立预约登记，需要记录读者 ID、书的 ISBN 号、预约时间和预约期限（最长为 10 天）。一旦其他读者归还这种书，就自动通知该预约读者。系统将自动清除超出预约期限的预约记录并修改相关信息。

（6）还书管理。读者还书时，则记录相应借还信息中的“归还时间”，对于超期归还者，系统自动计算罚金（具体的计算过程此处省略）。系统同时自动查询预约登记表，若存在其他读者预约该书的记录，则将该图书的状态修改为“已预约”，并将该图书 ID 写入相应的预约记录中（系统在清除超出预约期限的记录时解除该图书的“已预约”状态）；否则，将该图书的状态修改为“未借出”。

（7）通知处理。对于已到期且未归还的图书，系统通过 E-mail 自动通知读者。若读者预约的书已到，系统则自动通过 E-mail 通知该读者来办理借书手续。

2. 图书管理概念结构设计

根据需求分析的结果设计的实体-联系图（不完整）如图 12-13 所示，请指出读者与图书、书目与读者、书目与图书之间的联系类型，并补充图 12-13 中实体间缺少的联系。

1）联系类型

读者与图书、书目与图书、书目与读者之间的联系类型分析如下：

（1）读者与图书之间的联系类型。读者与图书之间形成了借还关系，需求分析的结果已经说明“一名读者最多只能借阅 10 本图书”，显然一本图书可被多名读者借阅，而每名读者应该能够借阅多本图书，因此读者与图书之间的借还联系为多对多（$n:m$），即空（1）和空（2）应分别填写 $n$ 和 $m$。

（2）书目与图书之间的联系类型。图书馆对于同一书目的图书可拥有多册（本），每一本书在系统中被赋予唯一的图书 ID，所以书目与图书之间的联系类型为一对多（$1:n$），即空（3）和空（4）应分别填写 $1$ 和 $n$。

（3）书目与读者之间的联系类型。当某书目的可借出图书的数量为 0 时，读者可以对其进行预约登记，由于一名读者可借阅多种图书，因此书目与读者之间的预约联系类型为多对多（$n:m$），即空（5）和空（6）应分别填写 $n$ 和 $m$。

2）图书馆管理 E-R 模型

根据需求分析的结果，图书馆管理应该包括图书证注册、注销和挂失管理，因此在图 12-13 中，管理员和读者实体间缺少的联系有注册、注销和挂失借书证管理联系。补充缺少的联系的 E-R 模型如图 12-14 所示。

3. 图书管理逻辑结构设计

根据概念设计得到的 E-R 图转换成图书管理系统的主要关系模式如下，请补充“借还记录”和“预约登记”关系中的空缺。注：时间格式为“年.月.日 时:分:秒”，请指出读者、书目关系模式的主键，以及图书、借还记录和预约登记关系模式的主键和外键。

  • 管理员（工号，姓名，权限）
  • 读者（姓名，年龄，工作单位，借书证号，电话，E-mail）
  • 书目（ISBN 号，书名，作者，出版商，出版年月，册数，工号）
  • 图书（图书 ID，ISBN 号，存放位置，状态，工号）
  • 借还记录（ $\underline{\quad(a)\quad}$ ，借出时间，应还时间，归还时间）
  • 预约登记（ $\underline{\quad(b)\quad}$ ，预约时间，预约期限，图书 ID）
  • 借书证管理（借书证号，使用状态，开始时间，结束时间，工号）
1）问题分析

由于读者借书时需由图书管理员登记借书证号、所借图书 ID、借出时间和应还时间，还书时图书管理员在对应的借书信息中记录归还时间，因此借还记录关系中的空（a）处应填入“借书证号，图书 ID”。

读者对某书目进行预约登记时，需记录借书证号、需要借阅的图书的 ISBN 号和预约时间等，目前的预约登记关系中已经有预约时间、预约期限、图书 ID 信息，显然还需要记录是哪位读者预约了书，以及书的 ISBN 号，因此，预约登记关系模式中的空（b）处应填入“借书证号，ISBN 号”。

2）主键与外键分析

主键也称为主码，是关系中的一个或一组属性，其值能唯一标识一个元组。根据图书管理的需求分析如下：

（1）管理员关系。主键显然是“工号”。

（2）读者关系。“系统为不同读者生成不同的借书证号”，因此读者关系的主键显然是“借书证号”。

（3）书目关系。不同书目的 ISBN 号不相同，书目关系的主键为书的“ISBN 号”，外键是管理员关系的“工号”。

（4）图书关系。同一书目的多册（本）图书具有相同的 ISBN 号，因此所有的图书依据“图书 ID”相互区分，图书关系的主键是“图书 ID”，外键是书目关系的“ISBN 号”和管理员关系的“工号”。

（5）借还记录关系。用于记录读者的借书和还书信息，为了区分读者在同一日期对同一本书多次借还，借还记录的主键为“借书证号，图书 ID，借出时间”。借还记录是由联系借还对应的关系，它记录与图书和读者的联系。因此，借还记录具有外键借书证号和图书 ID，分别与读者和图书相关联。

（6）预约登记关系。主键为“借书证号，ISBN 号，预约时间”，外键为读者关系的“借书证号”、书目关系的“ISBN 号”和图书关系的“图书 ID”。

（7）借书证管理关系。主键为“借书证号，开始时间”，外键是管理员关系的“工号”。

在实现数据库逻辑结构设计之后，就要确定数据库在计算机中的具体存储。由于数据库在物理设备上的存储结构与存取方法依赖于给定的计算机系统和应用环境，故案例中不再介绍。

12.3 面向对象分析与设计

面向对象开发方法将问题和问题的解决方案组织为离散对象的集合，数据结构和行为都包含在对象的表示中。面向对象的特性包括表示、抽象、分类、封装、继承、多态和持久性。面向对象开发方法包括面向对象分析、面向对象设计和面向对象实现。面向对象分析强调在问题领域内发现和描述对象或概念。例如，在图书馆信息系统里包含了书、图书馆和顾客这样一些概念。面向对象设计是采用协作的对象、对象的属性和方法说明软件解决方案的一种方式，强调的是定义软件对象和这些软件对象如何协作来满足需求，是面向对象分析的延续。例如，图书馆系统中，软件对象“书”可以有“标题”属性和“获取书”方法。在面向对象编程过程中会实现设计对象，如 Java 中的 Book 类。

面向对象方法中分析和设计有时会存在一部分重叠，不是完全独立的活动。在迭代开发中，不严格区分分析、设计和实现，而是每次迭代不同程度地进行精化。

面向对象分析和设计目前采用最多的是使用 UML。它是面向对象的标准建模语言，通过统一的语义和符号表示，使各种方法的建模过程和表示统一起来，已成为面向对象建模的工业标准。UML 通过事务、关系和图对现实世界进行建模。

12.3.1 面向对象分析与设计的步骤

面向对象分析包括 3 个活动：建模系统功能，发现并组织业务对象，组织对象并记录其关系。面向对象设计的目的是说明系统的对象和消息，包括精化用例模型以反映实现环境，建模支持用例情景的对象交互、行为和状态，修改对象模型以反映实现环境。

面向对象分析包含以下关键步骤：

（1）建模系统功能。需求分析可以包括对相关领域过程的描述，首先对系统需求进行建模，产生用例图。用例建模促进并鼓励了用户参与，为后期测试、跟踪和维护等方面提供支持，是项目成功的一个关键因素。建模需求用例模型的目的是提取和分析足够的需求信息，准备一个模型，该模型表示用户需要什么。产生用例的步骤如下：

  1. 确定参与者。
  2. 确定需求用例。
  3. 构造用例模型。

  4. 记录需求用例描述。

    然后建模用例活动，即建模系统的过程和步骤，描述业务过程或用例的活动的顺序流程和并行活动。UML 活动图用于构建系统的活动。建模用例执行过程中对象如何通过消息相互交互，将系统作为一个整体或者几个子系统进行考虑。

（2）定义领域模型。面向对象分析是从按对象分类的角度来创建对象领域的描述。领域的分解包括定义概念、属性和重要的关联。其结果可以被表示成领域模型，用一组显示领域概念或对象的图形来表示领域模型。

  1. 在用例建模中发现和确定业务对象。
  2. 组织对象并记录对象之间的主要概念关系。类图以图形化的用例描述对象及其关联关系。在该图中还包括多重性、关联关系、泛化/特化关系以及聚合关系。

（3）定义交互、行为和状态。面向对象设计定义软件对象及其协作。首先确定并分类用例设计类，然后确定类属性、行为和责任。交互概览图描述业务过程中的控制流概览，软件过程中的详细逻辑概览，以及将多个图进行连接。序列图和通信图可描述场景中涉及的所有对象类之间的交互。序列图通过描述按照时间顺序对象之间的消息交互建模了用例（或用例的一部分）的逻辑。这些消息按照时间顺序自顶向下排列，展示出软件对象之间的消息流动以及因此而引起的方法调用，描述对象之间的协作。通信图强调收发消息的对象的结构组织。还需基于对象的状态变化确定和建模具有复杂行为的对象，建模状态图。

（4）定义设计类图。除了在交互图中表示对象协作的动态视图外，还可以使用设计类图来创建类定义的静态视图，并说明类的属性和方法。

下面通过一个案例来说明如何应用面向对象分析和设计技术。

12.3.2 需求说明

某在线会议审稿系统（Online Reviewing System, ORS）主要处理会议前期的投稿和审稿事务。会议有名称、涵盖的主题（包括名称和描述）、提交期限、审稿期限、通知日期、状态和会议召开日期等信息。创建一个新的会议后审稿系统启动，在审稿结束时关闭审稿过程。

用户在初始使用系统时，必须在系统中注册成为作者或审稿人，需要提供名称、单位、电子邮件、登录名、密码、登录的状态。

作者登录后提交稿件和浏览稿件审阅结果。提交稿件必须在规定提交时间范围内，其过程为先输入标题和摘要、选择稿件所属主题类型、选择稿件所在位置（存储位置）。上述几步若未完成，则重复；若完成，则上传稿件至数据存储中，系统发送接收到稿件的通知。稿件的信息包括稿件 ID、标题、摘要、URL、状态和录用标准。状态随着整个审稿过程的进行而进行更新。

审稿人登录后可设置兴趣领域、审阅稿件给出评价意见以及罗列录用和（或）拒绝的稿件。审阅意见从原创性、技术质量、相关性和总体评价多个方面进行输入。稿件要限制不能被作者本人审阅。

会议委员会主席是一个特殊审稿人，可以浏览提交的稿件、到了稿件提交的最终日期后给审稿人分配稿件、罗列录用和（或）拒绝的稿件以及关闭审稿过程。如果审稿完成，浏览提交的稿件时可以列出录用和（或）拒绝的稿件。分配稿件时需要满足一篇稿件陆续被分配给 3 个审稿人审阅，当审阅完成时，如果 3 位审稿人的总评价满足设定的录用标准（审稿人评价值大于等于某个阈值），则稿件被录用，否则退稿，并发送电子邮件通知作者被录用或退稿。如果稿件被录用，则准备可打印版并打印。关闭审稿过程包括罗列录用和（或）拒绝的稿件。

12.3.3 建模用例

用例图描述系统与外部系统和用户的交互。换句话说，它们以图形化的方式描述了谁将使用系统，以及用户期望以什么方式与系统交互。用例描述也用于以文本化的方式描述每个交互步骤的顺序。用例是一个行为上相关的步骤序列（一个场景），既可以是自动的也可以是手工的，其目的是完成一个业务任务。用例从外部用户的观点并以他们可以理解的方式和词汇描述系统功能。参与者代表了需要同系统交互以交换信息的任何事物。发起或者触发用例的外部用户称为参与者，如人、组织、其他信息系统、外部设备甚至是时间。用例之间还可能存在扩展关系、包含关系、依赖关系和继承关系，需要进行识别和建模。

初步的需求分析得出表 12-3 所示的参与者和表 12-4 所示用例。

表 12-3 参与者列表

名称 说明 名称 说明
User 用户 Author 作者
Reviewer 审稿人 PCChair 委员会主席

表 12-4 用例名称列表

名称 说明 名称 说明
login 登录系统 register 注册
submit paper 提交稿件 browse review results 浏览稿件审阅结果
close reviewing process 关闭审稿过程 assign paper to reviewer 分配稿件给审稿人
set preferences 设定兴趣领域 enter review 审阅稿件给出意见
list accepted/rejected papers 罗列录用和（或）拒绝的稿件 browse submitted papers 浏览提交的稿件

从需求说明中可知：

（1）用户需注册成为合法的作者和审稿人，因此，如果一个用户要登录时，可先注册，再登录。

（2）作者必须登录之后才能提交稿件。

（3）审稿完成后，浏览提交的稿件时可以列出录用和（或）拒绝的稿件。

（4）关闭审稿过程包括罗列录用和（或）拒绝的稿件，可识别出扩展关系和包含关系。

根据上述分析，建模出用例图如图 12-15 所示的审稿系统用例图。

用例建模技术用于描述系统使用的模型，其建模过程是以用户为中心的建模过程，先识别问题中的参与者，再根据参与者确定每个参与者的用例、定义用例之间的关系、确定模型的过程。用例模型作为后续面向对象分析和设计的基础。

注意：要小心选用用例之间的关系，一般来说，这些关系都会增加用例和关系的个数，从而增加用例模型的复杂度。

12.3.4 建模活动

在用例建模完成后，对每个用例进行细化，建模活动图。活动图描述一个业务过程或者一个用例的活动的顺序，也可以用于系统的建模逻辑。在此以用例提交稿件（Submit Paper）为例，建模其活动。

根据需求描述，提交稿件过程识别出表 12-5 所示的活动。

表 12-5 提交稿件活动名称列表

名称 说明 名称 说明
select paper location 选择稿件位置 upload paper 上传稿件
select subject group 选择主题类型 send notification 发送通知
enter title and abstract 输入标题和摘要

从建模用例图时可知，参与者、作者和用户之间存在继承关系，提交稿件和登录之间存在扩展关系，提交稿件必须是在登录之后进行，所以，在提交稿件的过程中首先判断用户是否登录，如果登录则继续；如果没有登录，则执行登录活动。根据活动说明，建模出图 12-16 所示的活动图，其中 <<datastore>> 用于说明稿件存储对象。

活动图并不同于流程图，它提供了描述并行活动的机制，特别适用于建模操作正在执行时的活动以及那些活动的结果。建模活动图时应该遵循以下指导原则：

（1）根据分析决定是否采用泳道。

（2）从一个作为起点的初始结点开始。

（3）为用例的每个主要步骤（或者一个角色发起的每个主要步骤）添加一个动作。

（4）从一个动作到另一个动作、决策点或者终点添加一条流。除分支、合并、分岔和汇合外，每个动作应该只有一个输入流和一个输出流。

（5）在流分解成不同的路线的地方添加分支，确保用一个合并将各个流重新合并。

（6）在并行执行活动的地方添加分叉和汇合。

（7）用一个活动终止符号结束。

12.3.5 设计类图

类图用于描述系统的对象结构，显示了构成系统的对象类及其之间的关系。根据需求描述识别出对象类型有会议、用户、会议主题、稿件和审阅意见。

（1）会议。会议有名称、涵盖的主题（包括名称和描述）、提交期限、审稿期限、通知日期、状态和会议召开日期等信息。创建一个新的会议后审稿系统启动，在审稿结束时关闭审稿过程。所得到会议的属性有名称、提交期限、审稿期限、通知日期、状态和会议召开日期；行为有创建会议和关闭审稿过程。

（2）用户。需要提供名称、单位、电子邮件、登录名、密码、登录的状态。因此，得到用户的属性有名称、单位、电子邮件、登录名、密码、登录的状态；行为有登录和注册。

（3）会议主题。会议涵盖的主题包括名称和描述，所以属性为名称和描述。

（4）稿件。上传稿件的过程中需要输入标题和摘要、类型、URL、状态以及审阅结果，并在系统内有唯一标识，所以稿件的属性有稿件 ID、标题、摘要、URL 和审阅结果；行为有上传、分配和更新状态。

（5）审阅意见。审稿人对稿件进行审阅时，从原创性、技术质量、相关性和总体评价多个方面输入审阅意见。所以，审阅意见的属性有原创性、技术质量、相关性和总体评价；行为有输入审阅意见。

类及其属性名称如表 12-6 所示。

表 12-6 类及其属性和行为名称表

类 属性 行为
名称 说明 名称 说明 名称 说明
Conference 会议 name 会议名称 newConference 创建会议
submissionDate 提交期限 closeReviewing 关闭审稿过程
reviewDate 审稿期限
notificationDate 通知日期
status 状态
conferenceDate 召开日期
User 用户 name 名称 login 登录
organization 单位 register 注册
email 电子邮件
login 登录名
passwd 密码
loggedIn 登录的状态
Subject 会议主题 name 名称
description 描述
Review 审阅意见 originality 原创性 enterReview 输入审阅意见
technicalQuality 技术质量
relevance 相关性
overallRating 总体评价
Paper 稿件 paperID 稿件 ID upload 上传
title 标题 assign 分配
abstract 摘要 updateStatus 更新状态
url URL
status 状态
result 审阅结果

对于类型之间，确定其对象/类关系、多重度以及角色名称，例如会议和稿件之间的关系是聚合关系，一个会议有很多稿件，用户分为普通用户 user、author 和 reviewer 三种角色，并对其中的约束条件加以说明，某一稿件的审阅人不可以是本稿件的作者： reviewer.intersection(authors)→isEmpty\text{reviewer.intersection(authors)}\rightarrow\text{isEmpty} 得到图 12-17 所示的审稿系统的类图。

如果一个概念满足以下几点就应该抽象为一个类：

（1）几个有趣的事物，它们可以作为一个整体被描述为这个概念。

（2）具有不与任何其他的类共享的属性。

（3）这个概念的声明能将这个类及其所从属的某个较大的类相区别。

（4）这个概念的边界是不精确的。

（5）“兄弟”（如辅助类，这些辅助类的联合是该类的自然泛化）数目是少的。

12.3.6 建模对象状态

对象状态表示对象在其生命期中某一点所处的条件，通过修改对象属性的一个或多个值的事件触发对象状态变化。状态图用于建模在生命周期中事件如何改变对象可以经历的各种状态，以及引起对象从一个状态向另一个状态转换的事件。

基于需求描述中的信息，稿件上传成功之后，成为已上传状态。上传稿件的最后期限到了之后，就进入分配中，当分配给审稿人的数量达到规定的 3 个之后，进入审阅中，审阅结束后，评估结果如果大于等于设定的阈值，则变为录用状态，然后发送 E-mail 之后，变为已通知，当提交完准备好印制的电子版时，进入打印中，出版之后，状态结束；如果评估结果小于设定的阈值，变为拒绝状态，发送给作者 E-mail 通知状态结束。根据分析，确定表 12-7 所示状态名称以及行为或事件涉及术语对照表，建模得到图 12-18 所示的一份稿件的状态图。

表 12-7 状态以及行为或事件名称表

状态 行为或事件
名称 说明 术语 说明
submitted 已上传 date=deadline 日期到最后期限
under assignment 分配中 #reviewers 审阅人数
under review 审阅中 evaluated 审稿结果
accepted 录用 threshold 阈值
rejected 拒绝 camera-ready submitted 提交了印制的电子版
notified 已通知 published 已印制
inPrint 打印中 send E-mail 发送 E-mail

在建模状态图时应该注意遵循以下指导原则：

（1）状态名称要简单但具有描述性。

（2）避免“黑洞”状态，即只有变换进来而没有任何转换发出的状态，这种状态要么由于该状态是一个最终状态，要么就是已经错过了一个或多个转换。

（3）避免“奇迹”状态，即只有转换发出而没有任何转换进来的状态，这种状态要么是一个起点，要么就是已经错过了一个或多个转换。

（4）对复合状态，需要对子状态集进行建模。

（5）为复杂的实体创建分层的状态图。

12.3.7 建模交互

交互概览图是活动图的变体，描述业务过程中的控制流概览，软件过程中的详细逻辑概览，以及将多个图进行连接，抽象掉了消息和生命线。审稿系统中显示一篇已分配的稿件（Displaying as assigned paper），首先需获取（Retrieve list of assigned papers），然后再显示，然后再显示（Display selected paper），如图 12-19 所示。

序列图是以图形化的方式描述了在一个用例或操作的执行过程中对象如何通过消息互相交互，说明了消息在对象之间被发送和接收以及发送的顺序。根据分析设计的迭代演化需求，最初可以绘制系统序列图。系统序列图是一幅描述角色和系统在用例场景下交互的图形，有助于确定进入和退出系统的高层信息。

审稿人获取已分配给自己的稿件的执行序列，浏览会议主页，看到主页后，从导航条浏览已分配给自己的稿件，可循环进行选择，创建已分配稿件并显示给审稿人。涉及到的对象名称和执行操作如表 12-8 所示，得出图 12-20 所示的审稿人获取分配给自己的稿件列表序列图。

表 12-8 对象和执行操作名称列表

对象 操作
名称 说明 名称 说明
Reviewer 审阅人 navigate 导航
ConferenceHomepage 会议主页 show 显示
NavigationBar 导航栏 browse 浏览
AssignedPapers 分配的稿件 select 选择
Paper 稿件 create 创建
ListOfAssignedPapers 分配的稿件列表

建模序列图应该遵循以下指导原则：

（1）确定序列图的范围，描述这个用例场景或一个步骤。

（2）如果范围包括参与者和接口，则绘制参与者和接口类。

（3）沿左手边列出用例步骤。

（4）对控制器类及必须在序列中协作的每个实体类，基于它拥有的属性或已经分配给它的行为绘制框。

（5）为持久类和系统类绘制框。

（6）绘制所需消息，并把每条消息指到将实现响应消息的责任的类上。

（7）添加活动条指示每个对象实例的生命期。

（8）为清晰起见，添加所需的返回消息。

（9）如果需要，为循环、可选步骤和替代步骤等添加框架。

12.4 算法分析与设计

算法的概念在计算机科学领域几乎无处不在，在各种计算机软件系统的实现中，算法设计往往处于核心地位。例如，操作系统是现代计算机系统中不可缺少的系统软件，其中的各个任务都是一个单独的问题，每个问题由一个子程序根据特定的算法来实现。

尽管对有些应用来说，在应用这一层面上没有什么特别明显的算法方面的要求，例如，一些简单的 Web 应用。但是大多数问题对算法还是有一定要求的，例如，假设有一种基于 Web 的服务，用于确定如何从一个地方旅行到另一个地方，这可能涉及多个问题。解决这些问题依赖于快速的计算机硬件、图形用户界面（GUI）、广域网技术，甚至还可能要依赖于面向对象技术。除此之外，它还需要某些操作设计算法，例如寻找路由（最短路径算法）、显示地图和插入地址等。

此外，即使那些在应用层面上对算法性内容没有什么要求的应用，其实也是相当依赖于算法的，该应用是否要依赖于快速的计算机硬件？硬件的设计就要用到算法。该应用是否要用到图形用户界面？GUI 的设计也要依赖于算法。该应用是否要依赖于网络技术？网络路由对算法也有很大的依赖。该应用是否采用某种非机器代码的语言编写？那么，它就要由编译器、解释器或汇编器来处理，所有这些软件都要大量用到各种算法。因此，每个软件系统都会直接或者间接地涉及算法理论，算法是当代计算机中用到的大部分技术的核心。

随着计算机性能的不断增长，有人可能认为，算法的研究已经不是那么重要了。但是想一想，计算机可以做得很快，但还不能无限快。存储器可以做得很便宜，但不会是免费的。因此，计算时间是一种有限的资源，存储空间也是一种有限的资源，在开发软件系统时，这些有限的资源应该得到有效的利用。而且，正是由于计算机性能的不断增长，可以利用计算机来解决更复杂的问题或者规模更大的问题。因此，算法的研究是必要的，它是推动计算机技术发展的关键。

另外，算法只有经过某种程序设计语言实现，才能在计算机上运行，才能真正地解决问题，因此，本节的内容包括两个部分：C 程序设计语言与实现和算法设计与实现。

12.4.1 C 程序设计语言与实现

C 语言是面向过程程序设计中的典型语言，它提供了丰富的数据类型、运算符号和灵活的控制语句，熟悉 C 语言提供的数据类型、运算符号和语句是进行 C 程序设计的最基本要求。合理使用数据类型和控制结构对软件的可维护性、可扩展性有重要作用。由于篇幅限制，本节不介绍 C 语言的基本语法，只介绍 C 语言中的一个核心概念，即指针。

指针是 C 语言的精华部分，它极大地丰富了 C 语言的功能。通过利用指针，可以描述复杂的数据结构，在编程时能很好地利用内存资源，使其发挥最大的效率。运用指针编程是 C 语言最主要的风格之一。

1. 指针类型

1）变量和指针

在程序中定义或说明的变量，编译系统为其分配相应的内存单元，也就是说，每个变量都有具体的地址。简单而言，程序语言中的变量就是内存单元的抽象。变量具有类型、值、地址、作用域和生存期等属性。

变量的本质是程序中用来存放数据的一段存储空间。一般情况下，变量所对应的存储空间在内存区域，C 语言中程序员可以通过关键字 register 声明变量的存储单元是 CPU 中的寄存器。

变量的数据类型不同，它所占的内存单元数也不相同。在访问变量时，首先应找到其在内存的地址。如果在程序中将变量的地址保存在另一个变量中，则形成指针变量，通过指针对所指向变量的访问是一种对变量的“间接访问”。

例如，下面定义两个变量：整型变量 $a$ 和指针变量 ptr，在存取变量 $a$ 中的数据时，可通过变量 $a$ 或指向变量 $a$ 的指针来进行，分别称为直接访问和间接访问。

  1. int a;          /*a 是整型变量，其值为整数*/
  2. int *ptr;       /*ptr 是指针变量，其值为一个整型变量的地址*/

（1）直接访问变量 $a$ 中的数据。

  1. a = 5;          /*将字面量 5 赋值给变量 a*/
  2. a + 10;         /*读取变量 a 的值并与字面量 10 相加*/

（2）间接访问变量 $a$ 中的数据。

  1. ptr = &a;       /*将变量 a 的地址赋值给指针变量 ptr，称 ptr 指向变量 a*/
  2. *ptr = 5;       /*指针变量 ptr 指向的对象用 *ptr 表示*/
  3.                 /*等价于 a = 5;，通过指针变量 ptr 访问变量 a*/

经上述定义和处理后，变量 $a$ 和指针变量 ptr 之间的关系如图 12-21 所示。

若指针变量指向的对象仍然是一个指针变量，则称为多级指针。

例如，对于下面的变量定义，mulptr 是指向指针变量 ptr 的变量，这些变量间的关系如图 12-22 所示。

  1. int a, *ptr = &a, **mulptr = &ptr;

根据应用的需要，可以采用三级或多级指针。当然，采用多级指针在带来灵活性的同时降低了对数据的访问效率。

2）通过指针访问数组中的元素

C 程序中常利用指针对数组和字符串进行处理。一个数组由连续的一块内存单元组成，数组名就是这块连续内存单元的首地址（起始地址）。一个数组是由各个数组元素（通过下标区分）组成的，每个数组元素按其类型不同占有若干个连续的内存单元。

通过指针访问数组元素是指针变量的一种常见的应用方式。

（1）指针变量与一维数组。指针变量指向一维数组元素的情形较为简单。C 语言中定义一个指向数组元素的指针变量的方法如下。例如，定义一个整型数组 st 和指向数组元素的指针 ptr。

  1. int st[10];         /*定义 st 为包含 10 个整型数据的数组*/
  2. int *ptr = &st[0];  /*定义 ptr 为指向整型变量 st[0] 的指针，等价于 int *ptr = st*/

若 ptr 指向数组的第一个元素（即下标为 0 的元素），则 $*(p+i)$ 指向数组的第 $i+1$ 个元素（即下标为 $i$ 的元素）。

例如，设数组 $a$ 的空间足够大，函数 InsertElem(int a[], int n, int newElem) 的功能是将 newElem 中的数值插入到元素已经按照非递减方式排序的数组 $a$ 中，并保持数组 $a$ 中数据的排序特性。其中，对数组元素的访问采用指针方式。

  1. void InsertElem(int a[], int n, int newElem)
  2. {
  3.     int *p, *end;
  4.     end = a;
  5.     for(p = &a[n-1]; p >= end && *p > newElem; --p)
  6.         *(p+1) = *p;
  7.     *(p+1) = newElem;
  8. }

（2）指针变量与二维数组。指针变量指向二维数组元素的情形比较复杂，下面举例简单说明。

设有定义 int a[3][4]，其元素布局如图 12-23 所示。

数组 $a[3][4]$ 可看作是由 3 个一维数组（$a[0]$、$a[1]$、$a[2]$）构成的一维数组，每个一维数组的元素是 4 个。$a$ 是二维数组名，它代表整个二维数组的首地址。

$a[0]$ 是第 0 个一维数组的数组名和首地址。$(a+0)$、$a$ 和 $a[0]$ 是等效的，它们都表示一维数组 $a[0]$ 的 0 号元素的首地址。$\&a[0][0]$ 表示 $a$ 的第 0 行第 0 列元素的首地址。因此，$a$、$a[0]$、$(a+0)$、$a$ 和 $\&a[0][0]$ 所表示的内容相同。

同理，$a[1]$ 是第 1 个一维数组的数组名和首地址。将二维数组 $a[3][4]$ 看作元素是一维数组的一维数组时，$a$ 是数组首地址，$a+1$ 则是 1 号元素的地址，也就是 $a[1]$ 的地址，因此，$a+1$、$a[1]$、$*(a+1)$ 和 $\&a[1][0]$ 的含义相同，它们都表示数组 $a$ 第 1 行中第 0 个元素的地址。

所以，对于二维数组 $a[M][N]$，$a+i$、$a[i]$、$*(a+i)$ 和 $\&a[i][0]$ 是等同的。

把二维数组 $a[3][4]$ 分解为一维数组 $a[0]$、$a[1]$、$a[2]$ 之后，设 $p$ 为指向二维数组的指针变量。可定义为：

  1. int (*p)[4];    /*p 是一个指针变量，它指向包含 4 个元素的一维数组*/

因此，可令 $p=a$（等价于 $p=\&a[0]$）或 $p=\&a[1]$ 或 $p=\&a[2]$。若令 $p=\&a[0]$，则 $((p+1)+2)$ 就表示数组元素 $a[1][2]$，二维数组其他元素通过指针 $p$ 的表示方式依此类推。

3）指针与函数

C 程序中将指针与函数结合使用的常见方式有函数参数为指针、函数返回值为指针以及通过函数指针变量调用函数（函数指针变量）。

（1）函数参数为指针。函数的参数不仅可以是整型、实型、字符型等基本数据类型，还可以是指针类型。参数使用指针类型的作用是将一个变量的地址传送到另一个函数中。

C 语言中实参向形参传递值，反之则不行。

例如，定义函数 swap_1(a,b) 的功能是交换 $a$ 和 $b$ 的值，代码如下：

  1. void swap_1(int a, int b)   /*交换 a 和 b 的值*/
  2. {
  3.     int temp;
  4.     temp = a;  a = b;  b = temp;
  5. }

如果发生函数调用 swap_1(x,y)，则系统将 x 的值传给 a、y 的值传给 b，在函数 swap_1 中实现了 a 和 b 的值交换，但是 x 和 y 的值并不发生交换。为实现将函数中对形参的修改结果返回给调用函数之处，可使用指针参数。

对于上例，定义函数 swap_2 如下：

  1. void swap_2(int *a, int *b) /*交换 a 和 b 所指向的变量的值*/
  2. {
  3.     int temp;
  4.     temp = *a;  *a = *b;  *b = temp;
  5. }

当形式参数为指针类型时，传递给形参的应该是地址信息，因此调用 swap_2 的形式为 swap_2(&x, &y)。这样通过“间接访问”，实现了在被调用函数中修改实参所对应的变量。

通过指针参数也可以实现将被调用函数中的多个处理结果传回给调用函数的地方。

当函数的参数为数组时，实参和形参既可以用指针形式，也可以用数组形式，实参向形参传递的是数组空间的首地址。

（2）函数返回值为指针。函数类型是指函数返回值的类型。在 C 语言中允许一个函数的返回值是一个指针（即地址），这种返回指针值的函数称为指针型函数。

需要注意的是，不能返回局部数据的指针。

例如，下面的函数 get_str 虽然返回了局部数组 str 的首地址，但调用 get_str 的其他函数并不能通过此地址访问字符串 "testing local pointer"。

  1. char* get_str(void) {
  2.     char str[] = {"testing local pointer"};
  3.     return str;
  4. }
  6. int main(){
  7.     char *p;
  8.     int i;
  10.     p = get_str();
  11.     for(i=0; *(p+i); i++)
  12.         putchar(*(p+i));
  13.     return 0;
  14. }

将上述函数 get_str 中的 char str[] = {"testing local pointer"}; 改为 char *str = {"testing local pointer"} 即可，或者从内存的堆区申请字符串的空间，然后返回首地址。

  1. char* get_str(void) {
  2.     char *str;
  3.     str = (char *)malloc(100);      /*数值 100 可根据需要改为其他值*/
  4.     if (!str)
  5.         return NULL;
  6.     strcpy(str, "testing local pointer");
  7.     return str;
  8. }

函数返回值为指针时，也可以实现将被调用函数中的多个处理结果传回给调用函数的地方。

（3）指针变量（函数指针）。程序中的一个函数总是占用一段连续的内存区，而函数名就是该函数所占内存区的首地址。可以把函数的首地址（或称入口地址）赋给一个指针变量，使指针变量指向该函数，然后通过指针变量就可以找到并调用这个函数。指向函数的指针变量称为“函数指针变量”。

函数指针变量定义的一般形式为：

  1. 类型说明符  (*指针变量名)();

其中，“类型说明符”表示被指函数的返回值的类型；“(指针变量名)”表示“”后面的变量是指针变量；最后的一对空括号表示指针变量所指向的对象是一个函数。

例如，下面定义了一个函数指针变量 funptr。

  1. int (*funptr)();    /*指针变量 funptr 指向的对象是一个返回值为整数的函数*/

下面的程序中先定义了一个函数 max(a,b)，其功能是比较用 $a$ 和 $b$ 表示的两个整数并返回它们中的较大者，然后通过函数指针变量调用 max。

  1. #include <stdio.h>
  2. int max(int a,int b){
  3.     if (a>b) return a;
  4.     else return b;
  5. }
  7. int main(){
  8.     int max(int a,int b);   /*声明 max 是具有两个整型参数、返回值为整数的函数*/
  9.     int(*funptr)();
  10.     int x,y,z;
  12.     funptr = max;           /*令 funptr 指向函数 max*/
  13.     printf("input two numbers:\n");
  14.     scanf("%d%d",&x,&y);
  15.     z = (*funptr)(x,y);     /*等价于 z = max(x,y)*/
  16.     printf("maxmum=%d",z);
  17.     return 0;
  18. }

既然函数指针变量是一个变量，当然也可以作为某个函数的参数来使用。例如，下面的程序中设计了一个 testFunCall 函数，该函数根据其函数指针参数值的不同分别调用函数 fun1 和函数 fun2（注：fun1 和 fun2 的定义形式应相同）。

  1. int fun1(int x);
  2. int fun2(int x);
  3. typedef int (*FunType)(int);    /*定义一个函数指针类型 FunType*/
  4. void testFunCall(FunType fp,int x);
  6. int main(){
  7.     testFunCall(fun1,10);       /*通过 testFunCall 调用函数 fun1*/
  8.     testFunCall(fun2,20);       /*通过 testFunCall 调用函数 fun2*/
  9.     return 0;
  10. }
  12. void testFunCall (FunType fp,int x){
  13.     int t;
  14.     t = fp(x);                  /*通过函数指针 fp 调用 fp 指向的函数*/
  15.     printf("result: %d\n", t);
  16. }
  1. int fun1(int x) {
  2.     int t;
  3.     t = x*x;
  4.     printf("函数 fun1 的参数为：%d\t返回值为：%d\n",x,t);
  5.     return t;
  6. }
  8. int fun2(int x) {
  9.     int t;
  10.     t = (int)sqrt(x);
  11.     printf("函数 fun2 的参数为：%d\t返回值为：%d\n",x,t);
  12.     return t;
  13. }

2. 指针与数据结构

“程序=数据结构+算法”常用来说明程序、数据结构（数据的存储结构）与算法之间的关系，指针在数据结构的设计和实现中有重要的作用。随着软件开发环境的不断完善和程序语言的抽象程度不断提高，数据结构的内部设计细节被封装和屏蔽起来，在很多应用软件的开发中没有必要也不再涉及底层细节，但是在系统级程序设计或嵌入式应用的软件设计中，指针及相关机制的应用仍然是十分必要的。

1）单链表的实现和应用

在数据结构的设计中，指针是常用的工具。对于无法预先确定数据规模的应用，可采用动态存储的方法解决数据的存储问题，也就是链表结构。链表中的每个结点之间可以是地址不连续的（结点内是连续的），结点之间的联系用指针实现，实际上是在结点结构中定义一个成员项来存放下一个结点的首地址，称为指针域。

C 语言标准库中提供的用于申请动态存储空间的函数是 malloc()、calloc() 和 realloc()，函数 free() 用于释放由上述函数申请的内存空间。

栈是一种常用的数据结构，下面设计并实现一个链表结构的栈，如图 12-24 所示（为了简化，栈中的元素类型设为 int 型）。

  1. typedef struct Node {
  2.     int data;           /*栈中的数据元素*/
  3.     struct Node* next;  /*上次入栈的数据元素结点的地址*/
  4. }Node;
  5. typedef struct Stack {
  6.     Node * pTop;        /*栈顶指针*/
  7. }Stack;
  9. Stack* NewStack(){
  10.     return (Stack*)calloc(1,sizeof(Stack));
  11. }
  13. int IsEmpty(Stack* S)   /*判断栈是否为空栈，为空时返回 1，否则返回 0*/
  14. {
  15.     if(S == NULL || S->pTop == NULL) return 1;
  16.     return 0;
  17. }
  19. int Top(Stack* S)       /*获取栈顶数据*/
  20. {
  21.     if( IsEmpty(S) )
  22.         return INT_MIN; /*若栈为空，则返回机器可表示的最小整数*/
  23.     return S->pTop->data;
  24. }
  26. void Push(Stack* S, int theData)    /*将数据元素 theData 压栈*/
  27. {
  28.     Node* newNodePtr;
  29.     newNodePtr = (Node *)malloc(sizeof(Node));
  30.     newNodePtr->data = theData;
  31.     newNodePtr->next = S->pTop;
  32.     S->pTop = newNodePtr;
  33. }
  35. void Pop(Stack* S)      /*非空栈的栈顶元素出栈*/
  36. {
  37.     Node* lastTop;
  38.     if( IsEmpty(S) ) return;
  39.     lastTop = S->pTop;
  40.     S->pTop = S->pTop->next;
  41.     free(lastTop);
  42. }
  44. #define MD(a)  a<<2
  1. int main(){
  2.     int i;
  3.     Stack* myStack;
  4.     myStack = NewStack();
  5.     Push(myStack, MD(1));
  6.     Push(myStack, MD(2));
  7.     Pop(myStack);
  8.     Push(myStack, MD(3)+1);
  9.     while( !IsEmpty(myStack) ) {
  10.         printf("%d ", Top(myStack));
  11.         Pop(myStack);
  12.     }
  13.     return 0;
  14. }
2）二叉链表和多叉链表的设计和应用

（1）二叉树的存储结构设计。二叉树是一种重要的数据结构，采用二叉链表存储时，其结点的类型常定义为：

  1. typedef struct Tnode{
  2.     ElemType data;              /*结点的数据，ElemType 是其类型的抽象表示*/
  3.     struct Tnode *Lchild,*Rchild;   /*指向结点左、右孩子的指针*/
  4. }*Bitree;

对于某些特殊的二叉树，如哈夫曼树（或称为最优二叉树），由于该类型二叉树中的内部结点是由初始的 $m$ 个叶子结点根据一定的规则构成的，因此其结点总数总是 $2m-1$，所以采用静态的三叉链表来表示，其类型定义如下：

  1. #define LEAFNUM  20     /*叶子结点数目，在应用中可预先确定*/
  2. struct node{
  3.     char ch;            /*当前结点表示的字符，对于非叶子结点，此域不用*/
  4.     int weight;         /*当前结点的权值*/
  5.     int parent;         /*当前结点的父结点的下标，为 0 时表示无父结点*/
  6.     int lchild, rchild; /*当前结点的左、右孩子结点的下标，为 0 时表示无对应的孩子结点*/
  7. }Ht[2* LEAFNUM];

以具有 4 个叶子结点（分别用 a、b、c、d 表示，权值为 2、7、4、5）为例，采用哈夫曼算法构造的最优二叉树及其存储结构如图 12-25 所示。

  1. int n, e;                   /*图中顶点数和边数*/
  2. struct AdjList *head;       /*指向图中第一个顶点邻接表的头结点的指针*/
  3. }LinkedWDigraph;

例如，某有向图（网）如图 12-28（a）所示，其邻接表存储结构如图 12-28（b）所示。

在散列技术中，可用拉链法将冲突的元素存储起来，实际上就是链表结构的一个应用。例如，可以设计散列桶结构的类型如下：

  1. #define NULLKEY  -1     /*散列桶的空闲单元标识*/
  2. #define Pnum     7      /*散列文件中基桶的数目*/
  3. #define ITEMS    3      /*基桶和溢出桶的容量*/
  4. typedef struct BucketNode{  /*基桶和溢出桶的类型定义*/
  5.     int KeyData[ITEMS];
  6.     struct BucketNode *Link;
  7. }BUCKET;
  8. BUCKET Bucket[Pnum];        /*基桶空间定义*/

设散列函数为 $\text{Hash(Key)}=\text{Key mod }7$，关键字序列“15, 14, 21, 87, 96, 293, 35, 24, 149, 19, 63, 16, 103, 77, 5, 153, 145, 356, 51, 68, 705, 453”的存储结构如图 12-29 所示。

从上述内容可知，利用指针实现的链表结构有灵活多变的形式，可根据应用的需要为数据存储设计不同的结构。显然，数据的存储方式不同，体现相同算法思路的处理过程可能会有较大的差异。因此，算法的实现过程与数据结构的设计是密切相关的，在有些情况下，算法的实际效率会因为数据存储结构的不同而不同。

12.4.2 算法设计与实现

正如第 8 章提到的，算法理论的研究主要包括算法设计技术和算法分析技术，这两者是不可分割的一个整体。算法设计要提出针对问题的高质量的算法，算法分析的对象是被提出的算法，并研究算法所耗费的计算资源与问题规模之间的函数关系，而每一个被设计出的算法只有经过算法分析才能评价其质量的优劣。

因此，用什么方法来设计算法，如何判定一个算法的优劣，所设计的算法需要占用多少时间资源和空间资源，在实现一个软件系统时都是必须予以解决的重要问题。

1. 算法设计过程

在设计算法时，有几个问题是要考虑到的：如何设计算法？如何表示算法？如何证明问题解决的正确性？如何评估算法的效率？如何进行算法的最优化？根据这些问题，可以归纳出算法设计的主要步骤：理解问题；确定相关因素，包括问题的输入与输出、用何种数据结构、用什么样的算法设计策略等；设计算法；证明所设计的算法的正确性；分析所设计的算法的效率；实现所设计的算法。

1）理解问题

在面对一个算法任务时，算法设计者往往不能准确地理解要求他做的是什么。对算法希望实现什么只有一个大致的想法就匆忙地落笔写算法，其后果往往是写出的算法漏洞百出。在设计算法时需要做的第一件事就是完全理解要解决的问题，仔细阅读问题的描述，手工处理一些小例子。

对于设计算法来说，这是一项重要的技能。准确地理解算法的输入是什么？要求算法做的是什么？即明确算法的入口和出口，这是设计算法的切入点。

2）确定相关因素

（1）预测所有可能的输入。

算法的输入确定了该算法所解问题的一个实例。一般而言，对于问题 $P$，总有其相应的实例集 $I$，因此算法 $A$ 若是问题 $P$ 的算法，则意味着把 $P$ 的任一实例 $\text{input}\in I$ 作为算法 $A$ 的输入，都能得到问题 $P$ 的正确输出。

预测算法所有可能的输入，包括合法的输入和非法的输入。事实上，无法保证一个算法（或程序）永远不会遇到一个错误的输入，一个对大部分输入都运行正确而只有一个输入不行的算法，就像一颗等待爆炸的炸弹。这绝不是危言耸听，有大量这种引起灾难性后果的案例。例如，许多年以前，整个 AT&T 的长途电话网崩溃，造成了几十亿美元的直接经济损失。原因只是一段程序的设计者认为他的代码能一直传送正确的参数值，可是有一天，一个不应该有的值作为参数传递了，导致了整个北美电话系统的崩溃。

如果养成习惯——首先考虑问题和它的数据，然后列举出算法必须处理的所有特殊情况，那么可以更快速地成功构造算法。

（2）在精确解和近似解间做选择。

计算机科学的研究目标是用计算机来求解人类所面临的各种问题。但是，有些问题无法求得精确解，例如求平方根、解非线性方程和求定积分等。有些问题由于其固有的复杂性，求精确解需要花费太长的时间，其中最著名的要算旅行商问题（TSP 问题），此时，只能求出近似解。

有时需要根据问题以及问题所受的资源限制，在精确解和近似解间做选择。

（3）确定适当的数据结构。

在结构化程序设计时代，著名的计算机学者沃思（Wirth）提出了“算法+数据结构=程序”的观点，断言了算法和数据结构是构成计算机程序的重要基础。在面向对象的程序设计时代，数据结构对于算法设计和分析仍然是至关重要的。

确定数据结构通常包括对问题实例的数据进行组织和重构，以及为完成算法所设计的辅助数据结构。在很多情况下，数据结构的设计直接影响基于该结构之上设计的算法的时间性能。

（4）确定算法设计技术。

第 9 章介绍的算法设计技术（或称为算法设计策略）是设计算法的一般性方法，可用于解决不同计算领域的多种问题。这些算法设计技术包括分治法、动态规划法、贪心算法、回溯法、分支界限法、概率算法和近似算法等，已经被证明是对算法设计非常有用的通用技术，它们构成了一组强有力的工具，在为新问题设计算法时，可以运用这些技术设计出新的算法。算法设计技术作为问题求解的一般性策略，在解决计算机领域以外的问题时，也能发挥相当大的作用。

3）设计算法

根据 1）和 2）的结果，就可以设计算法。在构思和设计了一个算法之后，必须清楚、准确地将所设计的求解步骤记录下来，即描述算法。描述算法的常用方法有自然语言、流程图、程序设计语言和伪代码等，其中，伪代码是比较合适的描述算法的方法。

4）证明算法的正确性

可以用循环不变式来证明算法的正确性，以插入排序为例介绍循环不变式，以下是插入排序的 C 代码。

  1. #include<stdio.h>
  2. void Insertion_Sort(int A[],int length){
  3.     int index;
  4.     for(index = 1 ; index < length ; index++){
  5.         int temp = A[index];
  6.         if(A[index] < A[index - 1]){
  7.             /*因为 A[0..index-1] 有序，若 A[index]<A[index-1]，
  8.               则该元素应插入 index 之前的某个位置*/
  9.             int insert;
  10.             for(insert = index-1 ; insert >= 0 && A[insert] > temp ; insert--){
  11.                 /*从 index-1 向前遍历，遇到小于 temp 的元素时停止*/
  12.                 A[insert + 1] = A[insert];
  13.             }
  14.             A[insert + 1] = temp;
  15.         }
  16.     }
  17. }

对于要分析的算法，定义循环不变式，如对插入排序，定义其外层循环的循环不变式为：在每一轮迭代的开始，子数组 $A[1..j-1]$ 中包含了最初位于 $A[1..j-1]$，但目前已经排好序的各个元素，然后证明循环不变式的 3 个性质。

（1）初始化。

在循环的第一轮迭代开始之前它是正确的。对于插入排序，第一轮迭代之前，$j=2$，子数组为 $A[1..j-1]$，即 $A[1]$，也就是最初在 $A[1]$ 中的那个元素，显然这个子数组是已排好序的，因此循环不变式成立。

（2）保持。

如果在循环的每一次迭代之前它是正确的，那么在下一次迭代之前，它也应该保持正确。对于插入排序（上述伪代码包含两重循环，应该定义两个循环不变式，并证明它们的正确性。但为了简便，暂时不陷入过于形式化的细节，仅考虑外层循环），要将 $A[j-1]$、$A[j-2]$ 和 $A[j-3]$ 等元素向右移一个位置，直到找到 $A[j]$ 的适当位置为止，这时将 $A[j]$ 的值插入。很显然，循环不变式是成立的。

（3）终止。

当循环结束时，循环不变式给了我们一个有用的性质，它有助于表明算法是正确的。对于插入排序，当 $j$ 大于 $n$ 时，外层 for 循环结束。在循环不变式中，将 $j$ 替换为 $n+1$，就有子数组 $A[1..n]$ 包含了原先在 $A[1..n]$ 中的元素，但现在已经排好序了，这意味着算法是正确的。

除了循环不变式外，经验和研究表明，发现算法（或程序）中逻辑错误的重要方法就是系统地跟踪算法。跟踪必须要用“心和手”来进行，跟踪者要像计算机一样，用一组输入值来执行该算法，并且这组输入值要最大可能地暴露算法中的错误。即使有几十年经验的高级软件工程师，也经常利用此方法查找算法中的逻辑错误。

5）分析算法的效率

设计出的算法只有经过分析，才能评价其优劣，才能判断其是否能满足问题求解的需求或者在多个算法之间进行选择。算法分析主要分析两种效率：时间效率和空间效率。时间效率显示了算法运行得有多快，空间效率则显示了算法需要多少额外的存储空间，相比而言，一般更关注算法的时间效率。事实上，计算机的所有应用问题，包括计算机自身的发展，都是围绕着“时间—速度”这样一个中心进行的。一般来说，一个好的算法首先应该是比同类算法的时间效率高。

6）根据算法编写代码

现代计算机技术还不能将伪代码形式的算法直接“输入”进计算机中，而需要把算法转变为特定程序设计语言编写的程序，算法中的一条指令可能对应实际程序中的多条指令。在把算法转变为程序的过程中，虽然现代编译器提供了代码优化功能，但仍需要一些标准的技巧，例如，在循环体之外计算循环中的不变式、合并公共子表达式、用开销低的操作代替开销高的操作等。一般来说，这样的优化对算法速度的影响是一个常数因子，可能会使程序提高 10%～50% 的速度。

算法设计的一般过程如图 12-30 所示。需要强调的是，一个好算法是反复努力和重复修正的结果。那么，什么时候应该停止这种改进呢？设计算法是一种工程行为，需要在资源有限的情况下，在互斥的目标之间进行权衡。设计者的时间显然也是一种资源，在实际应用中，常常是项目进度表迫使我们停止改进算法。

2. 算法问题类型

就像生物学家把自然界的所有生物作为自己的研究对象，计算机科学把问题作为自己的研究对象，研究如何用计算机来解决人类所面临的各种问题。在计算领域的无数问题中，或者由于问题本身具有一些重要特征，或者由于问题具有实用上的重要性，有一些领域的问题是算法研究人员特别关注的。经验证明，无论对于学习算法还是应用算法，对这些问题的研究都是极其重要的。下面列出几类重要的问题。

1）查找问题

查找是在一个数据集合中查找满足给定条件的记录。对于查找问题来说，没有一种算法对于任何情况都是合适的。有的算法查找速度比其他算法快，但却需要较多的存储空间（例如 Hash 查找）；有的算法查找速度非常快，但仅适用于有序数组（例如折半查找），等等。此外，如果在查找的过程中数据集合可能频繁地发生变化，除了考虑查找操作外，还需要考虑在数据集合中执行插入和删除等操作。这种情况下，就必须仔细地设计数据结构和算法，以便在各种操作的需求之间达到一个平衡。而且，组织用于高效查找的特大型数据集合对于实际应用具有非常重要的意义。

2）排序问题

简单地说，排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序时，需要选定一个信息作为排序的依据，例如，可以按学生平均成绩对学生记录进行排序，这个特别选定的信息（平均成绩）称为关键码。

排序的一个主要目的是为了进行快速查找，这就是为什么字典、电话簿和班级名册都是排好序的。当然，在很多领域的重要算法中，排序也被作为一个辅助步骤，例如，搜索引擎将搜索到的结果按相关程度排序后显示给用户。

迄今为止，已经发现的排序算法不下几十种，没有一种排序算法在任何情况下都是最好的解决方案，有些排序算法比较简单，但速度相对较慢；有些排序算法速度较快，但却很复杂；有些排序算法适合随机排列的输入；有些排序算法更适合基本有序的初始排列；有些排序算法仅适合存储在内存中的序列；有些排序算法可以用来对存储在磁盘上的大型文件排序等。

3）图问题

算法中最古老也是最令人感兴趣的领域是图问题，很多纷乱复杂的现实问题抽象出的模型都是图结构，如社会网络、Web、工作流、XML 数据、电路、图像、化合物和生物网络等。作为一种通用的、复杂的数据结构，基于图的相关算法也具有十分重要的作用。

有些图问题在计算上是非常困难的，这意味着，在能够接受的时间内，即使用最快的计算机，也只能解决这种问题的一个很小规模的实例，例如 TSP 问题、最大团问题（即最大独立集问题）、图着色问题、哈密尔顿回路问题、顶点覆盖问题和最长路径问题等。图问题中还有一个奇怪的现象：许多形式上非常类似的问题，解决它们的难度却相差很大，例如，最短路径问题和欧拉回路问题存在多项式时间算法，而最长路径问题和哈密尔顿回路问题至今没有找到一个多项式时间算法。

4）组合问题

组合问题一般都是最优化问题，因此也称为组合优化问题，即寻找一个组合对象，例如一个排列、一个组合或一个子集，这个对象能够满足特定的约束条件并使得某个目标函数取得极值：价值最大或者成本最小。典型的组合优化问题包括 0-1 背包问题、TSP 问题和整数线性规划等。

无论从理论的观点还是实践的观点，组合问题都是计算领域中最难的问题，其原因如下：

（1）随着问题规模的增大，组合对象的数量增长极快，即使是中等规模的实例，其组合对象的数量也会达到不可思议的数量级，产生组合爆炸。

（2）还没有一种已知算法能在可接受的时间内精确地求解绝大多数问题。

5）几何问题

几何问题处理类似于点、线、面和体等几何对象。几何问题与其他问题的不同之处在于，哪怕是最简单、最初等的几何问题也难以用数字去处理。尽管人类对几何问题的研究从古代起便没有中断过，但是具体到借助计算机来解决几何问题的研究，还只是停留在一个初始阶段。随着计算机图形图像处理、机器人和断层 X 摄像技术等方面应用的深入，人们对几何算法产生了强烈的兴趣。经典的几何问题包括最近点对问题和凸包问题，前者指的是在给定平面上的 $n$ 个点中，求距离最近的两个点；后者指的是要找出一个能把给定集合中的所有点都包含在里面的最小凸多边形。

3. 典型实例

下面给出一些典型的问题，并用常用的算法设计技术来设计算法，求解问题。

1）循环赛日程安排问题

设有 $n(2^k)$ 位选手参加网球循环赛，循环赛共进行 $n-1$ 天，每位选手要与其他 $n-1$ 位选手赛一场，且每位选手每天赛一场，不轮空。试按此要求为比赛安排日程。

该问题可以用分治法来求解。设 $n$ 位选手被顺序编号为 $1, 2, \cdots, n$。比赛的日程表是一个 $n$ 行 $n-1$ 列的表，第 $i$ 行 $j$ 列的内容是第 $i$ 号选手第 $j$ 天的比赛对手。用分治法设计日程表，就是从其中一半选手（$2^{k-1}$ 位）的比赛日程导出全体（$2^k$ 位）选手的比赛日程。从众所周知的只有两位选手的比赛日程出发，反复这个过程，直到为 $n$ 位选手安排好比赛日程为止。

为了从 $2^{k-1}$ 位选手的比赛日程表中导出 $2^k$ 位选手的比赛日程表，假定只有 8 位选手（如图 12-31 所示），若 1～4 号选手之间的比赛日程填在日程表的左上角（4 行 4 列），5～8 号选手之间的比赛日程填在日程表的左下角（4 行 4 列），而左下角的内容可以由左上角对应项加上数 4 得到。至此，剩下的右上角（4 行 4 列）是为编号小的 1～4 号选手与编号大的 5～8 号选手之间的比赛安排日程。例如在第 4 天，让 1～4 号选手分别与 5～8 号选手比赛，以后各天，依次由前一天的日程安排，让 5～8 号选手循环轮转即可。最后，参照右上角得到右下角的比赛日程，如图 12-31 所示。由以上分析，不难得到为 $2^k$ 选手安排比赛的算法思路。

循环赛日程安排算法的关键在于寻找这四部分元素之间的对应关系，其 C 代码如下：

  1. int ** GameTable(int k){
  2.     /*为矩阵 A 分配空间，且不使用下标包含 0 的元素，即下标从 1 开始计算。
  3.       矩阵 A 的第一列为选手的编号*/
  4.     int** A = (int **) malloc( sizeof(int *)*((int)pow(2,k) + 1));
  5.     int i,j,t;
  6.     for (i = 1 ; i <= (int)pow(2,k) ; i++){
  7.         A[i] = (int *) malloc( sizeof(int)*((int)pow(2,k) + 1));
  8.     }
  9.     int n = 2;
  10.     A[1][1] = 1;
  11.     A[1][2] = 2;
  12.     A[2][1] = 2;
  13.     A[2][2] = 1;
  14.     for(t = 1 ; t < k ; t++){
  15.         /*以分治法填充日程表*/
  16.         int temp = n;
  17.         n *= 2;
  18.         /*扩展左下角*/
  19.         for(i = temp + 1 ; i <= n ; i++)
  20.             for(j = 1 ; j <= temp ; j++)
  21.                 A[i][j] = A[i - temp][j] + temp;
  22.         /*扩展右上角*/
  23.         for(i = 1 ; i <= temp ; i++)
  24.             for(j = temp + 1 ; j <= n ; j++)
  25.                 A[i][j] = A[i][j - temp] + temp;
  26.         /*扩展右下角*/
  27.         for(i = temp+1 ; i <=n ; i++)
  28.             for(j = temp + 1 ; j <= n ; j++)
  29.                 A[i][j] = A[i - temp][j - temp];
  30.     }
  31.     return A;
  32. }

其中，$A$ 为数组，$n=2^k$ 表示参加比赛的人数。

2）矩阵链乘问题

给定 $n$ 个矩阵 ${A1, A_2, \cdots, A_n}$，其中，$A_i$ 与 $A{i+1}$ 是可乘的，$i=1, 2, \cdots, n-1$，考虑这 $n$ 个矩阵的乘积。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵链乘的计算次序完全确定，这时就说该链乘已完全加括号。完全加括号的矩阵链乘可递归地定义为：

① 单个矩阵是完全加括号的。

② 矩阵链乘的乘积 $A$ 是完全加括号的，则 $A$ 可表示为两个完全加括号的矩阵链乘的乘积，$B$ 和 $C$ 的乘积并加括号，即 $A=(BC)$。

例如，矩阵链乘 $A_1A_2A_3A_4$ 可以有以下 5 种完全加括号的方式：$(A_1(A_2(A_3A_4)))$、$(A_1((A_2A_3)A_4))$、$((A_1A_2)(A_3A_4))$ 和 $(((A_1A_2)A_3)A_4)$。每一种加括号的方式确定了一个计算的次序。不同的计算次序与矩阵链乘的计算量有密切关系。

为了说明该问题，回忆两个矩阵相乘的相关概念。矩阵 $A$ 和矩阵 $B$ 可乘的条件是矩阵 $A$ 的列数等于矩阵 $B$ 的行数，若 $A$ 是一个 $p \times q$ 矩阵，$B$ 是一个 $q \times r$ 矩阵，则其乘积 $C=AB$ 是一个 $p \times r$ 矩阵，且标准的两个矩阵相乘所需要的计算量为 $pqr$ 次乘法操作。

考虑 3 个矩阵 ${A_1, A_2, A_3}$ 链乘的例子。设这 3 个矩阵的维数分别为 $10 \times 100$、$100 \times 5$ 和 $5 \times 50$。若按第一种加括号方式 $((A_1A_2)A_3)$ 计算，则所需要的乘法次数为 $10 \times 100 \times 5 + 10 \times 5 \times 50 = 7500$。若按第二种加括号方式 $(A_1(A_2A_3))$ 计算，则所需要的乘法次数为 $10 \times 5 \times 50 + 10 \times 100 \times 50 = 75000$。第二种加括号方式乘法次数是第一种的 10 倍。由此可以看出，不同的加括号方式确定的不同的计算次序对矩阵链乘的运算量影响是巨大的。

矩阵链乘问题定义如下：给定 $n$ 个矩阵 ${A1, A_2, \cdots, A_n}$，矩阵 $A_i$ 的维数为 $p{i-1} \times p_i$，$i=1, 2, \cdots, n$，如何给矩阵链乘 $A_1 \times A_2 \times \cdots \times A_n$ 完全加上括号，使得矩阵链乘中乘法次数最少。

矩阵链乘是非常难的问题，若用穷尽搜索法，能够证明需要指数时间来求解。现在考虑用动态规划法来求解矩阵链乘问题，具体步骤如下。

（1）刻画矩阵链乘问题的结构。

为简便起见，用 $A{i..j}$ 表示矩阵乘积 $A_iA{i+1}\cdots Aj$ 的结果，其中 $i \leq j$。若问题是非平凡的，即 $i < j$，那么乘积 $A_iA{i+1}\cdots Aj$ 一定在 $A_k$ 与 $A{k+1}$ 之间被分裂，$i \leq k < j$。问题 $AiA{i+1}\cdots Aj$ 完全加括号的开销等于计算矩阵 $A{i..k}$ 与计算 $A_{k+1..j}$ 的开销，再加上它们的结果相乘的开销。

问题的最优子结构可刻画如下：假定问题 $AiA{i+1}\cdots Aj$ 被完全加括号的最优方式是在 $A_k$ 与 $A{k+1}$ 之间被分裂，那么分裂之后，最优解 $AiA{i+1}\cdots Aj$ 中的子链 $A_iA{i+1}\cdots Ak$ 一定是问题 $A_iA{i+1}\cdots Ak$ 的最优加括号方式。同样，最优解 $A{k+1}A{k+2}\cdots A_j$ 中的子链一定是问题 $A{k+1}A_{k+2}\cdots A_j$ 的最优加括号方式。

（2）递归定义最优解的值。

根据问题的最优解递归地定义问题最优解的开销。设 $m[i, j]$ 表示计算 $A{i..j}$ 所需的最小乘法次数，得到下列递归式。对于原问题，计算 $A{1..n}$ 的最小开销则为 $m[1, n]$。

$$ m[i, j] = \begin{cases} 0 & , i = j \ \min\limits{i \leq k < j}{m[i, k] + m[k+1, j] + p{i-1}p_kp_j} & , i < j \end{cases} $$

（3）计算最优解的值。

根据上述递归式，以自底向上的方式计算最优开销。假设输入为 $p=$，用表 $m[1..n, 1..n]$ 存储 $m[i, j]$，用辅助表 $s[1..n, 1..n]$ 存储哪一个 $k$ 使得计算 $m[i, j]$ 时达到最优。最终需要利用 $s$ 构造问题的一个最优解。算法的 C 代码如下：

  1. int** Matrix_Chain_Order(int* p,int Length){
  2.     int Multip_times=Length-1;
  3.     /*为 m、s 分配空间*/
  4.     int** m = (int **)malloc(sizeof(int *)*(Length));
  5.     int** s = (int **)malloc(sizeof(int *)*(Length));
  6.     int i;
  7.     for (i = 0; i < Length; i++){
  8.         m[i] = (int *)malloc(sizeof(int)*(Length));
  9.         s[i] = (int *)malloc(sizeof(int)*(Length));
  10.     }
  11.     /*初始化 m*/
  12.     for(i = 1;i <= Multip_times;i++)
  13.         m[i][i] = 0;
  14.     int l;
  15.     /*自底至上计算 m、s*/
  16.     for(l = 2;l <= Multip_times;l++){   /*l 为子问题长度，即有 l 个矩阵相乘*/
  17.         for(i = 1;i <= (Multip_times - l + 1);i++){
  18.             int j = i + l - 1;
  19.             m[i][j] = INT_MAX;
  20.             int k;
  21.             for(k = i;k < j;k++){   /*计算 m[i,j] 的最小代价*/
  22.                 int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
  23.                 if(q < m[i][j]){    /*当前代价小于之前的最小代价*/
  24.                     m[i][j] = q;
  25.                     s[i][j] = k;
  26.         }
  27.     }
  28. }
  29. return s;
  30. }

由上述伪代码很容易得到算法的时间复杂度为 $O(n^3)$。举个例子说明上述过程，假设 $n=6$，$p=\langle p_0, p_1, \cdots, p_6 \rangle = \langle 30,35,15,5,10,20,25 \rangle$。则根据上述伪代码，图 12-32 给出了 $m[i,j]$ 的计算次序以及 $m[i,j]$ 和 $s[i,j]$ 的值。

图 12-32 矩阵链乘的动态规划算法示例（包括：(a) $m[i,j]$ 的计算次序；(b) $m[i,j]$ 的值；(c) $s[i,j]$ 的值）

(4) 构造最优解

上一步给出了计算矩阵乘积的最少乘法次数（最优解的值），但没有给出具体的乘法次序（最优解）。可以由辅助表 $s$ 的信息构造最优解，C 代码如下。

  1. void Print_Optimal_Parens(int **s, int i, int j){ 
  2.     /*表项 s[i,j]记录了对乘积 A_iA_{i+1}...A_j 在 A_k 和 A_{k+1} 之间
  3.       进行分裂，以取得最优加全部括号时的 k 值*/
  4.     if(i == j)
  5.         printf("A%d", i);
  6.     else{
  7.         printf("(");
  8.         Print_Optimal_Parens(s, i, s[i][j]);       /*在当前分裂左侧继续分裂*/
  9.         Print_Optimal_Parens(s, s[i][j] + 1, j);   /*在当前分裂右侧继续分裂*/
  10.         printf(")");
  11.     }
  12. }

上述例子调用 OutputOptimalParens(s,1,6) 后得到输出结果 $((A_1(A_2A_3))((A_4A_5)A_6))$。

3）多机调度问题

假设有 $n$ 个独立的作业 ${1,2, \cdots, n}$，由 $m$ 台相同的机器 ${M_1, M_2, \cdots, M_m}$ 进行加工处理，作业 $i$ 所需的处理时间为 $t_i$，每个作业均可在任意一台机器上加工处理，但不可间断或拆分，即一旦一个作业在某台机器上加工处理，便不会再转移到其他的机器上。多机调度问题要求给出一种作业调度方案，使所给的 $n$ 个作业在尽可能短的时间内由 $m$ 台机器加工处理完成。

多机调度问题是 NP 难问题，到目前还没有有效的算法。对于这类问题，用贪心算法求解有时可以得到较好的近似解。贪心法求解多机调度问题时的贪心策略是最长处理时间优先。当 $m \ge n$ 时，只要将机器 $i$ 上的 $[0, t_i]$ 时间区间分配给作业 $i$ 即可；当 $m<n$ 时，首先将 $n$ 个作业按其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的机器。例如，假设有 7 个作业 ${1,2,3,4,5,6,7}$，由 3 台机器 ${M_1, M_2, M_3}$ 加工处理，各个作业所需要的时间分别为 ${2,14,4,16,6,5,3}$。首先将这 7 个作业按其处理时间从大到小排序，则作业 ${4,2,5,6,3,7,1}$ 的处理时间为 ${16,14,6,5,4,3,2}$。图 12-33 给出了按最长处理时间作业优先的原则时，这 7 个作业的调度情况及其所需要的总加工处理时间。

图 12-33 3 台机器的调度问题示例

假设对 $n$ 个作业按其加工处理时间从大到小进行了排序，排序的时间复杂度为 $O(n\lg n)$。

下面给出用贪心法解决多机调度问题的 C 代码。

  1. typedef struct{
  2.     int ID;
  3.     int time;
  4. } Task;
  6. int IndexOfMin(int *Array, int Number){
  7.     int i;
  8.     int index = 0;
  9.     int min = Array[0];
  10.     for(i = 1; i < Number; i++){
  11.         if(Array[i] < min){
  12.             index = i;
  13.             min = Array[i];
  14.         }
  15.     }
  16.     return index;
  17. }
  19. int* MultiMachineSchedule(Task *Tasks, int Task_number, int Machine_number){
  20.     /*Finish_times 数组为每台机器完成作业的累积时间*/
  21.     /*Task_lists 数组为每台机器完成作业的列表，如第一台机器依次完成作业 1、2、3，
  22.       则其数组元素为 123 */
  23.     int* Finish_times = (int *) malloc(sizeof(int) * (Machine_number));
  24.     int* Task_lists = (int *) malloc(sizeof(int) * (Machine_number));
  25.     int i;
  27.     for(i = 0; i < Machine_number; i++){
  28.         /*初始化数组*/
  29.         Finish_times[i] = 0;
  30.         Task_lists[i] = 0;
  31.     }
  33.     for(i = 0; i < Machine_number; i++){
  34.         /*先让 Machine_number 台机器处理排名前 Machine_number 的作业*/
  35.         Task_lists[i] = Task_lists[i] * 10 + Tasks[i].ID;
  36.         Finish_times[i] += Tasks[i].time;
  37.     }
  39.     for(; i < Task_number; i++){
  40.         /*选择最早完成作业的机器处理未完成作业中所需时间最长的作业*/
  41.         int index = IndexOfMin(Finish_times, Machine_number); //选出最先完成任务的机器
  42.         Task_lists[index] = Task_lists[index] * 10 + Tasks[i].ID;
  43.         Finish_times[index] += Tasks[i].time;
  44.     }
  46.     return Task_lists;
  47. }

12.5 面向对象的程序设计与实现

12.5.1 设计与实现方法

面向对象程序设计主要是根据问题的详细描述，设计出能够被迅速转换为面向对象程序实现的代码，相比本章的第 12.3 节，其设计与实现更为底层，更接近代码。但是，对面向对象设计结果的衡量没有统一的标准，因此很难衡量针对一个问题所设计的解决方案是否最优，这也正是软件工程领域内分析与设计的难点，在更多的情况下，分析与设计的结果是一种经验的总结。

尽管不存在一致的对分析与设计结果的衡量标准，但许多面向对象和软件工程领域内的“大师”都根据自己长期的实践经验总结出了面向对象分析与设计的原则，而这些原则可成为我们在对实际问题进行分析与设计时的指导准则。

一般而言，当面临一个具体的问题时，可分为两大阶段：首先根据问题进行设计，其次根据设计进行实现。由于面向对象的实现和面向对象设计之间不存在较大的差异，所不同的是设计更多采用的是 UML 的标准表示，而实现则是采用面向对象语言表达，因此解决问题的重点应放在面向对象的设计上。

目前，被公认的好的面向对象设计是由前人所总结的设计模式。因此，熟练并正确地掌握面向对象设计技术，必须很好地体会并理解常用的 23 种设计模式。在对 23 种设计模式加以运用时，必须做到以下几点。

  1. 能够根据设计模式的名称画出其对应的类图。
  2. 理解类图中每一个类的作用与功能。
  3. 能够将现实问题中所描述的各种职责映射到类图中具体的类。
  4. 能够使用一种面向对象语言实现设计。

下面通过具体的应用来说明这个过程。

12.5.2 设计模式的应用

1. 问题说明

已知某类库开发商提供了一套类库，类库中定义了 Application 类和 Document 类，它们之间的关系如图 12-34 所示。其中，Application 类表示应用程序自身，而 Document 类表示应用程序打开的文档。Application 类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个 Document 对象表示。

图 12-34 Application 与 Document 关系图

当开发一个具体的应用程序时，开发者需要分别创建自己的 Application 和 Document 子类，例如图 12-34 中的类 MyApplication 和类 MyDocument，并分别实现 Application 和 Document 类中的某些方法。

已知 Application 类中的 openDocument 方法采用了模板方法（Template Method）设计模式，该方法定义了打开文档的每一个主要步骤，如下所述。

  1. 首先检查文档是否能够被打开，若不能打开，则给出出错信息并返回。
  2. 创建文档对象。
  3. 通过文档对象打开文档。
  4. 通过文档对象读取文档信息。
  5. 将文档对象加入到 Application 的文档对象集合中。

2. 根据设计模式的名称画出其对应的类图

问题描述中已经给出了该设计采用的设计模式为模板方法，因此，首先给出模板方法的类图，如图 12-35 所示。

3. 理解类图中每一个类的作用与功能

在模板方法类图中，AbstractClass 类定义了基本的操作 PrimitiveOperation1() 和 PrimitiveOperation2()，并在 TemplateMethod() 方法中调用了这两个操作，但这两个操作都并未实现，而是留待子类去实现，从而达到模板方法的目的：定义一个操作中的算法的骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。

图 12-35 模板方法类图

4. 能够将现实问题中所描述的各种职责映射到类图中具体的类

在提出的具体问题中，已经告知了 Application 类中的 openDocument 方法采用了模板方法，而 openDocument 方法的步骤都已经给出，因此，很容易将 Application 类对应为模板方法类图中的 AbstractClass 类，openDocument 方法映射为模板方法类图中的 TemplateMethod 方法，而主要步骤对应 PrimitiveOperation1() 等基本操作。由此可推出，在各种主要的步骤中，应该存在某些步骤是由 Application 的子类实现的。

5. 能够使用一种面向对象语言实现设计

一旦分析清楚实际问题的设计结果和原始的设计模式类图中类的对应关系，便可采用一种面向对象语言实现。下面分别采用 C++ 和 Java 语言实现给出的设计。

【C++代码】

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. class Document{
  6. public:
  7.     void save(){ /*存储文档数据，此处代码省略*/ }
  8.     void open(string docName){ /*打开文档，此处代码省略*/ }
  9. };