我的书签
添加书签
移除书签第12章 软件系统分析与设计
软件设计师考试结合了当前软件设计开发中的主流技术和工程应用背景，强调了主流设计技术的应用问题，除要求掌握基本的概念和理论基础知识外，还需要正确地针对实践应用中的问题，提出合理的解决方案，将一系列的设计方法与原则应用在实际系统的分析、设计和开发环节中。编者委员会总结近几年的软件设计师考试所涉及的应用性内容，其主要技术领域可归纳为以下几点。
（1）结构化分析与设计。
（2）数据库分析与设计。
（3）面向对象分析与设计。
（4）算法分析与设计。
（5）面向过程的程序设计与实现。
（6）面向对象的程序设计与实现。
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±2以内。
DFD、数据字典和处理加工说明可以充分地描述系统的分析模型，其后需要对分析模型进行变换从而得到系统的总体设计模型。系统总体设计模型可以采用层次图、HIPO图和结构图来表达，但不论是哪一种图形工具，都反映了模块间的调用关系。
在分析模型的基础上进行设计时，主要是针对DFD进行变换从而得到模块的调用关系图，因此，需要掌握数据流的变换设计与事务设计。面向数据流的设计方法把数据流图映射成软件结构，数据流图的类型决定了映射的方法，数据流图可分为变换型数据流图和事务型数据流图。变换型数据流图具有明显的输入、变换（或称主加工）和输出；而事务型数据流图则是数据沿输入通路到达一个处理时，这个处理根据输入数据的类型在若干动作序列中选择一个来执行。变换设计的核心在于确定输入流和输出流的边界，从而孤立出变换中心；事务设计的核心在于将事务类型判断处理变换成调度模块以选择后续的输出分支模块。
经过总体设计阶段的工作，已经确定了软件的模块结构和接口描述，但每个模块仍被看作黑盒子。后续的详细设计目标是确定怎样具体地实现所要求的系统，经过详细设计，可以得出对目标系统的精确描述，从而在编码阶段可以将这个描述直接翻译成用某种程序设计语言书写的程序。因此，详细设计的结果基本上决定了最终的程序代码的质量。详细设计可以采用程序流程图、N-S图、PAD图和PDL语言等工具来表达。下面通过一个案例来说明如何应用结构化分析、总体设计与详细设计技术。
12.1.1 需求说明
图书管理系统的主要功能包括图书购入、借阅、归还以及注销。管理人员可以查询读者、图书的借阅情况，还可对当前图书借阅情况进行统计，给出统计数据。简单的图书管理系统针对图书进行4方面的管理：购入新书、读者借书、读者还书以及图书注销。
购入新书需要为该书编制图书卡片，包括分类目录号、流水号（保证每本书都有唯一的流水号，同类图书也是如此）、书名、作者、内容摘要、价格和购书日期等信息，并将这些信息写入图书目录文件中。
读者借书时需填写借书单，包括读者号、欲借图书分类目录号，系统首先检查该读者号是否有效，若无效，则拒绝借书；否则进一步检查该读者所借图书是否超过最大限制数。若已达到最大限制数，则拒绝借书；若未达到最大限制数，读者可以借出该书，登记图书分类目录号、读者号和借阅日期等，写回到借书文件中。
读者还书时，根据图书流水号，从借书文件中读出和该图书相关的借阅记录，标明还书日期，再写回借书文件中。如果图书逾期未还，则处以相应罚款。
在某些情况下，需要对图书馆的图书进行清理工作，对一些过时或无继续保留价值的图书要注销，这时从图书文件里删除相关记录。
咨询要求分为查询读者信息、图书信息和借阅统计信息三种。
12.1.2 结构化分析
结构化分析的最终结果需要得到系统的数据流图、数据字典和加工处理说明。根据需求说明，首先界定系统的边界。因为购入新书、读者借书、读者还书和图书注销将来都是由图书管理员来操作系统，因此图书管理员将是系统的外部实体之一。当读者借书超期时，系统会给读者一个罚款单信息，所以，这里可以将系统时钟和读者也作为系统的外部实体之一。当然，如果认为罚款单是由系统管理员转交给读者，则可以认为图书管理系统只和管理员与系统时钟进行交互，这里采用第二种观点。咨询要求同样都是由系统管理员来操作，由此可以得出系统不完整的第0层DFD数据流图如图12-1所示。
图12-1 不完整的第0层DFD图
在0层DFD图上分析外部实体与系统间的数据流，因为管理员的两大工作任务是分析管理任务和咨询任务，因此管理员会向系统输入管理请求信息与查询请求信息，根据输入的管理请求，系统将会对一些存储文件进行修改；对查询请求，系统则会给出读者、图书与借阅的统计信息。系统时钟主要为图书管理系统提供系统时间。为图12-1补充数据流所得完整的0层DFD数据流图如图12-2所示。
图12-2 第0层DFD图
随后对0层DFD数据流图中的图书管理系统进行进一步细化，根据需求可以得知，系统主要分为管理任务和查询任务，因此可以将其细化为两个大的处理，如图12-3所示。
图12-3 第1层DFD图
同样，对处理2进行进一步细化，管理处理分为购书、借书、还书和清理4项任务，因此可以将处理2分解为4个处理，另外需要一个单独的处理根据管理请求的类型进行请求分派。细化后的数据流图如图12-4所示。
图12-4 处理2的第2层DFD图
同样的方法，可以对处理1也进行细化。一旦对处理1的细化完成，即可对得到的数据流图进行转化，从而形成系统的总体设计。但在转换之前，应该对数据流图中的数据流采用数据字典进行详细的说明，例如：
管理请求＝清理请求｜购书请求｜借书请求｜还书请求
清理请求＝图书分类目录号
┆
对于底层处理，以处理2.3为例进行说明。
加工编号：2.3
加工名称：借书
输入流：读者信息，借书信息
输出流：借书信息
处理逻辑：根据读者信息和借书信息，首先判断读者是否合法，判断读者是否已经超出借阅图书数目的最大限制，若都合法，将借书信息重新写入借书文件中，同时更新图书目录文件。
12.1.3 总体设计
由于数据流呈现了事务型的特性，因此，可采用事务型的变换方式对数据流图进行变换，从而得到的系统的总体结构如图12-5所示。
总体设计给出了数据流图中的各个处理间转换为模块后，模块与模块之间的调用关系，后续就需要根据总体设计给出模块的详细设计。
图12-5 系统总体结构图
12.1.4 详细设计
以借书为例，采用程序流程图的形式描述借书模块的详细设计。分析借书的输入是读者信息和借书信息，需要读者信息的读者借书证号，借书信息给出了读者已经借阅了多少本书，如果读者借阅的书籍数目尚未超出系统的限制，则允许借书，并把新的借书信息写入借书文件；否则，拒绝借书。该模块的详细流程图如图12-6所示。
图12-6 借书模块流程图
完成对每一个模块的详细设计，即可将详细设计转换为程序代码，从而实现整个管理系统。
12.2 数据库分析与设计
数据库设计属于系统设计的范畴。通常把使用数据库的系统统称为数据库应用系统，把对数据库应用系统的设计简称为数据库设计。数据库设计的任务是针对一个给定的应用环境，在给定的（或选择的）硬件环境和操作系统及数据库管理系统等软件环境下，创建一个性能良好的数据库模式，建立数据库及其应用系统，使之能有效地存储和管理数据，满足各类用户的需求。
合理的数据库结构是数据库应用系统性能良好的基础和保证，但数据库的设计和开发却是一项庞大而复杂的工程。从事数据库设计的人员，不仅要具备数据库知识和数据库设计技术，还要有程序开发的实际经验，掌握软件工程的原理和方法。数据库设计人员必须深入应用环境，了解用户具体的专业业务。在数据库设计的前期和后期，与应用单位人员密切联系，共同开发，可大大提高数据库设计的成功率。
12.2.1 数据库设计的步骤
1．数据库应用系统的生命期
按照软件工程对系统生命周期的定义，软件生命周期分为6个阶段工作：制定计划、需求分析、设计、程序编制、测试以及运行维护。在数据库设计中也参照这种划分，把数据库应用系统的生命周期分为数据库规划、需求描述与分析、数据库设计与应用程序设计、实现、测试、运行维护6个阶段。
（1）数据库规划。数据库规划是创建数据库应用系统的起点，是数据库应用系统的任务陈述和任务目标。任务陈述定义了数据库应用系统的主要目标，而每个任务目标定义了系统必须支持的特定任务。数据库规划过程还必然包括对工作量的估计、使用的资源和需要的经费等。同时，还应当定义系统的范围和边界，以及它与公司信息系统的其他部分的接口。
（2）需求描述与分析。需求描述与分析是以用户的角度，从系统中的数据和业务规则入手，收集和整理用户的信息，以特定的方式加以描述，是下一步工作的基础。
（3）数据库与应用程序设计。数据库设计是对用户数据的组织和存储设计；应用程序设计是在数据库设计基础上对数据操作及业务实现的设计，包括事务设计和用户界面设计。
（4）数据库系统实现。数据库系统实现是依照设计，使用DBMS支持的数据定义语言（DDL）实现数据库的建立，用高级语言（Basic、Delphi、C、C++和Power builder等）编写应用程序。
（5）测试阶段。测试阶段是在数据系统投入使用之前，通过精心制定的测试计划和测试数据来测试系统的性能是否满足设计要求，发现问题。
（6）运行维护。数据库应用系统经过测试、试运行后即可正式投入运行。运行维护是系统投入使用后，必须不断地对其进行评价、调整与修改，直至系统消亡。
在任一设计阶段，一旦发现不能满足用户数据需求时，均需返回到前面的适当阶段，进行必要的修正。经过如此的迭代求精过程，直到能满足用户需求为止。在进行数据库结构设计时，应考虑满足数据库中数据处理的要求，将数据和功能两方面的需求分析、设计和实现在各个阶段同时进行，相互参照和补充。
在数据库设计中，对每一个阶段设计成果都应该通过评审。评审的目的是确认某一阶段的任务是否全部完成，从而避免出现重大的错误或疏漏，保证设计质量。评审后还需要根据评审意见修改所提交的设计成果，有时甚至要回溯到前面的某一阶段，进行部分重新设计乃至全部重新设计，然后再进行评审，直至达到系统的预期目标为止。
2．数据库设计的方法
在确定了数据库设计的策略以后，就需要相应设计方法和步骤。多年来，人们提出了多种数据库设计方法，多种设计准则和规范。
1978年10月召开的新奥尔良（New Orleans）会议提出的关于数据库设计的步骤（简称新奥尔良法）是目前得到公认的，较完整、较权威的数据库设计方法，它把数据库设计分为如下4个主要阶段。
（1）用户需求分析。数据库设计人员采用一定的辅助工具对应用对象的功能、性能和限制等要求所进行的科学分析。
（2）概念设计。概念结构设计是对信息分析和定义，如视图模型化、视图分析和汇总。该阶段对应用对象精确地进行抽象和概括，以形成独立于计算机系统的企业信息模型。描述概念模型的较理想工具是E-R图。
（3）逻辑设计。将抽象的概念模型转化为与选用的DBMS产品所支持的数据模型相符合的逻辑模型，它是物理设计的基础。包括模式初始设计、子模式设计、应用程序设计、模式评价以及模式求精。
（4）物理设计。逻辑模型在计算机中的具体实现方案。
当各阶段发现不能满足用户需求时，均需返回到前面适当的阶段，进行必要的修正。如此经过不断地迭代和求精，直到各种性能均能满足用户的需求为止。
12.2.2 需求分析
需求分析是在项目确定之后，用户和设计人员对数据库应用系统所要涉及的内容（数据）和功能（行为）的整理和描述，是以用户的角度来认识系统。这一过程是后续开发的基础，以后的逻辑设计和物理设计以及应用程序的设计都会以此为依据。
1．需求分析的任务、目标及方法
需求分析阶段的任务：综合各个用户的应用需求，对现实世界要处理的对象（组织、部门和企业等）进行详细调查，在了解现行系统的概况，确定新系统功能的过程中，收集支持系统目标的基础数据及处理方法。
参与需求分析的主要人员是分析人员和用户，由于数据库应用系统是面向企业和部门的具体业务，分析人员一般并不了解，而同样用户也不会具有系统分析的能力，这就需要双方进行有效的沟通，使得设计人员对用户的各项业务了解和熟悉，进行分析和加工，将用户眼中的业务转换成为设计人员所需要的信息组织。
分析和表达用户需求的方法主要包括自顶向下和自底向上两类方法。自顶向下的结构化分析（Structured Analysis, SA）方法从最上层的系统组织机构入手，采用逐层分解的方式分析系统，并把每一层用数据流图和数据字典描述。需求分析的重点是调查组织机构情况、调查各部门的业务活动情况、协助用户明确对新系统的各种要求、确定新系统的边界，以此获得用户对系统的如下要求。
（1）信息要求。用户需要在系统中保存哪些信息，由这些保存的信息要得到什么样的信息，这些信息以及信息间应当满足的完整性要求。
（2）处理要求。用户在系统中要实现什么样的操作功能，对保存信息的处理过程和方式，各种操作处理的频度、响应时间要求、处理方式等以及处理过程中的安全性要求和完整性要求。
（3）系统要求。包括安全性要求、使用方式要求和可扩充性要求。安全性要求：系统有几种用户使用，每一种用户的使用权限如何。使用方式要求：用户的使用环境是什么，平均有多少用户同时使用，最高峰时有多少用户同时使用，有无查询相应的时间要求等。可扩充性要求：对未来功能、性能和应用访问的可扩充性的要求。
需求分析阶段的工作以及形成的相关文档（作为概念结构设计阶段的依据）如图12-7所示。
图12-7 需求分析阶段的工作
2．需求分析阶段的文档
需求调查所得到的数据可能是零碎的、局部的，分析师和设计人员必须进一步分析和表达用户的需求，建立需求说明文档、数据字典和数据流程图。将需求调查文档化，文档既要被用户所理解，又要方便数据库的概念结构设计。
数据流分析是对事务处理所需的原始数据的收集及经处理后所得数据及其流向，一般用数据流程图（DFD）来表示。DFD不仅指出了数据的流向，而且还指出了需要进行的事务处理（但并不涉及如何处理，这是应用程序的设计范畴）。除了使用数据流程图、数据字典以外，需求分析还可使用判定表、判定树等工具。下面介绍数据流程图和数据字典，其他工具的使用可参见软件工程等方面的参考书。
数据字典（Data Dictionary, DD）是各类数据描述的集合，它是关于数据库中数据的描述，即元数据，而不是数据本身。如用户将向数据库中输入什么信息，从数据库中要得到什么信息，各类信息的内容和结构，信息之间的联系等。数据字典包括数据项、数据结构、数据流、数据存储和处理过程5个部分（至少应该包含每个字段的数据类型和在每个表内的主键、外键）。
数据项描述＝｛数据项名，数据项含义说明，别名，数据类型，长度，取值范围，取值含义，与其他数据项的逻辑关系｝
数据结构描述＝｛数据结构名，含义说明，组成：｛数据项或数据结构｝｝
数据流描述＝｛数据流名，说明，数据流来源，数据流去向，组成：｛数据结构｝，平均流量，高峰期流量｝
数据存储描述＝｛数据存储名，说明，编号，流入的数据流，流出的数据流，组成：｛数据结构｝，数据量，存取方式｝
处理过程描述＝｛处理过程名，说明，输入：｛数据流｝，输出：｛数据流｝，处理：｛简要说明｝｝
需求分析阶段的成果是系统需求说明书，主要包括数据流图、数据字典、各种说明性表格、统计输出表和系统功能结构图等。系统需求说明书是以后设计、开发、测试和验收等过程的重要依据。关于需求分析的详细过程请参见第4.2节。
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图合并，如图12-8所示。
图12-8 概念结构设计工作步骤
（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图之间的冲突主要有以下三类。
（1）属性冲突。同一属性可能会存在于不同的分E-R图，由于设计人员不同或是出发点不同，对属性的类型、取值范围和数据单位等可能会不一致，这些属性对旧的数据将来只能以一种形式在计算机中存储，这就需要在设计阶段进行统一。
（2）命名冲突。相同意义的属性，在不同的分E-R图上有着不同的命名，或是名称相同的属性在不同的分E-R图中代表着不同的意义，这些也要进行统一。
（3）结构冲突。同一实体在不同的分E-R图中有不同的属性，同一对象在某一分E-R图中被抽象为实体，而在另一分E-R图中又被抽象为属性，需要统一。
分E-R图的合并过程中要对其进行优化，具体可以从以下几个方面实现。
（1）实体类型的合并。两个具有1∶1联系或1∶n联系的实体可以予以合并，使实体个数减少，有利于减少将来数据库操作过程中的连接开销。
（2）冗余属性的消除。一般在各分E-R图中的属性是不存在冗余的，但合并后就可能出现冗余。因为合并后的E-R图中的实体继承了合并前该实体在分E-R图中的全部属性，属性间就可能存在冗余，即某一属性可以由其他属性确定。
（3）冗余联系的消除。在分E-R图合并过程中，可能会出现实体联系的环状结构，即某一实体A与另一实体B间有直接联系，同时A又通过其他实体与实体B发生间接联系。通常直接联系可以通过间接联系所表达，可消除直接联系。
12.2.4 逻辑结构设计
逻辑结构设计即是在概念结构设计的基础上进行数据模型设计，可以是层次模型、网状模型和关系模型，本节介绍如何在全局E-R图基础上进行关系模型的逻辑结构设计。逻辑结构设计阶段的主要工作步骤包括确定数据模型、将E-R图转换成为指定的数据模型、确定完整性约束和确定用户视图，如图12-9所示。
图12-9 逻辑结构设计阶段工作步骤
1．E-R图关系模式的转换
E-R方法所得到的全局概念模型是对信息世界的描述，并不适用于计算机处理，为适合关系数据库系统的处理，必须将E-R图转换成关系模式。E-R图是由实体、属性和联系三要素构成，而关系模型中只有唯一的结构——关系模式，通常采用以下方法加以转换。
1）实体向关系模式的转换
将E-R图中的实体逐一转换成为一个关系模式，实体名对应关系模式的名称，实体的属性转换成关系模式的属性，实体标识符就是关系的码。
2）联系向关系模式的转换
E-R图中的联系有三种：一对一联系（1∶1）、一对多联系（1∶n）和多对多联系（m∶n），针对这三种不同的联系，转换方法如下。
（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的内部特征，根据系统的处理要求和数据的特点来确定物理结构。数据库的物理设计工作过程如图12-10所示。
图12-10 数据库的物理设计工作过程
一般来说，物理设计包括确定数据分布、存储结构和访问方式的工作。
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 数据库实施与维护
在数据库正式投入运行之前，还需要完成很多工作。例如，在模式和子模式中加入数据库安全性、完整性的描述，完成应用程序和加载程序的设计，数据库系统的试运行，并在试运行中对系统进行评价。如果评价结果不能满足要求，还需要对数据库进行修正设计，直到满意为止。数据库正式投入使用，也并不意味着数据库设计生命周期的结束，而是数据库维护阶段的开始。数据库实施阶段的工作过程如图12-11所示。
图12-11 数据库实施阶段的工作过程
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 书目信息
表12-2 图书信息
1）初步的需求分析结果
（1）资料室有图书管理员若干名，他们负责已购入图书的编目和借还工作，每名图书管理员的信息包括工号和姓名。
（2）读者可在阅览室读书，也可通过图书流通室借还图书，读者信息包括姓名、年龄、工作单位、借书证号、电话和E-mail，系统为不同读者生成不同的借书证号。
（3）每部书在系统中对应唯一的一条图书在版编目数据（CIP，以下简称书目），书目的基本信息包括ISBN号、书名、作者、出版商、出版年月以及本资料室拥有该书的册数（以下简称册数），不同书目的ISBN号不相同。
（4）资料室对于同一书目的图书可拥有多册（本），图书信息包括图书ID、ISBN号、存放位置和当前状态，每一本书在系统中被赋予唯一的图书ID。
（5）一名读者最多只能借阅10本图书，且每本图书最多只能借两个月，读者借书时需由图书管理员登记读者ID、所借图书ID、借阅时间和应还时间，读者还书时图书管理员在对应的借书信息中记录归还时间。
（6）当某书目的可借出图书的数量为0时，读者可以对其进行预约登记，即记录读者ID、需要借阅的图书的ISBN号和预约时间。
2）业务流程
图书管理信息系统在应用中的业务流程图如图12-12所示。
图12-12 图书管理业务流程图
系统的主要业务处理如下。
（1）入库管理。图书购进入库时，管理员查询本资料室的书目信息，若该书的书目尚未建立，则由管理员编写该书的书目信息并录入系统，然后编写并录入图书信息；否则，修改该书目的册数，然后编写并录入图书信息。对于进入流通室的书，其初始状态为“未借出”，而送入阅览室的书的状态始终为“不外借”。
（2）图书证注册和注销。登记所有办理的新图书证和注销图书证，需要注明办理及注销日期及管理员号。
（3）挂失管理。包括挂失登记，登记挂失的图书证，使得该图书证不能借书，注明挂失日期及管理员号；解除挂失，解除已经挂失的图书证，使得该借书证可以开始借书，注明解除挂失日期及管理员号。
（4）借书管理。读者借书时，若有，则由管理员为该读者办理借书手续，并记录该读者的借书信息，同时将借出图书的状态修改为“已借出”。
（5）预约管理。若图书流通室没有读者要借的书，则可为该读者建立预约登记，需要记录读者ID、书的ISBN号、预约时间和预约期限（最长为10天）。一旦其他读者归还这种书，就自动通知该预约读者。系统将自动清除超出预约期限的预约记录并修改相关信息。
（6）还书管理。读者还书时，则记录相应借还信息中的“归还时间”，对于超期归还者，系统自动计算罚金（具体的计算过程此处省略）。系统同时自动查询预约登记表，若存在其他读者预约该书的记录，则将该图书的状态修改为“已预约”，并将该图书ID写入相应的预约记录中（系统在清除超出预约期限的记录时解除该图书的“已预约”状态）；否则，将该图书的状态修改为“未借出”。
（7）通知处理。对于已到期且未归还的图书，系统通过E-mail自动通知读者。若读者预约的书已到，系统则自动通过E-mail通知该读者来办理借书手续。
2．图书管理概念结构设计
根据需求分析的结果设计的实体联系图（不完整）如图12-13所示，请指出读者与图书、书目与读者、书目与图书之间的联系类型，并补充图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所示。
图12-14 补充缺少的联系的图书管理系统的实体联系图
3．图书管理逻辑结构设计
根据概念设计得到的E-R图转换成图书管理系统的主要关系模式如下，请补充“借还记录”和“预约登记”关系中的空缺。注：时间格式为“年．月．日 时∶分∶秒”，请指出读者、书目关系模式的主键，以及图书、借还记录和预约登记关系模式的主键和外键。
管理员（工号，姓名，权限）
读者（姓名，年龄，工作单位，借书证号，电话，E-mail）
书目（ISBN号，书名，作者，出版商，出版年月，册数，工号）
图书（图书ID，ISBN号，存放位置，状态，工号）
借还记录（ （a） ，借出时间，应还时间，归还时间）
预约登记（ （b） ，预约时间，预约期限，图书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 面向对象分析与设计的步骤
面向对象分析包括三个活动：建模系统功能，发现并组织业务对象，组织对象并记录其关系。面向对象设计的目的是说明系统的对象和消息，包括精化用例模型以反映实现环境，建模支持用例情景的对象交互、行为和状态，修改对象模型以反映实现环境。
面向对象分析包含如下关键步骤。
（1）建模系统功能。需求分析可以包括对相关领域过程的描述，首先对系统需求进行建模，产生用例图。用例建模促进并鼓励了用户参与，为后期测试、跟踪和维护等方面提供支持，是项目成功的一个关键因素。建模需求用例模型的目的是提取和分析足够的需求信息，准备一个模型，该模型表示用户需要什么。产生用例的步骤如下。
① 确定参与者。
② 确定需求用例。
③ 构造用例模型。
④ 记录需求用例描述。
然后建模用例活动，即建模系统的过程和步骤，描述业务过程或用例的活动的顺序流程和并行活动。UML活动图用于构建系统的活动。建模用例执行过程中对象如何通过消息相互交互，将系统作为一个整体或者几个子系统进行考虑。
（2）定义领域模型。面向对象分析是从按对象分类的角度来创建对象领域的描述。领域的分解包括定义概念、属性和重要的关联。其结果可以被表示成领域模型，用一组显示领域概念或对象的图形来表示领域模型。
① 在用例建模中发现和确定业务对象。
② 组织对象并记录对象之间的主要概念关系。类图以图形化的用例描述对象及其关联关系。在该图中还包括多重性、关联关系、泛化／特化关系以及聚合关系。
（3）定义交互、行为和状态。面向对象设计定义软件对象及其协作。首先确定并分类用例设计类，然后确定类属性、行为和责任。顺序图可描述场景中涉及的所有对象类之间的交互，通过描述按照时间顺序对象之间的消息交互建模了用例（或用例的一部分）的逻辑。这些消息按照时间顺序自顶向下排列，展示出软件对象之间的消息流动以及因而引起的方法调用，描述对象之间的协作。还需基于对象的状态变化确定和建模具有复杂行为的对象，建模状态图。
（4）定义设计类图。除了在交互图中表示对象协作的动态视图外，还可以使用设计类图来创建类定义的静态视图，并说明类的属性和方法。
下面通过一个案例来说明如何应用面向对象分析和设计技术。
12.3.2 需求说明
某在线会议审稿系统（Online Reviewing System, ORS）主要处理会议前期的投稿和审稿事务。会议有名称、涵盖的主题（包括名称和描述）、提交期限、审稿期限、通知日期、状态和会议召开日期等信息。创建一个新的会议后审稿系统启动，在审稿结束时关闭审稿过程。
用户在初始使用系统时，必须在系统中注册成为作者或审稿人。需要提供名称、单位、电子邮件、登录名、密码、登录的状态。
作者登录后提交稿件和浏览稿件审阅结果。提交稿件必须在规定提交时间范围内，其过程为先输入标题和摘要、选择稿件所属主题类型、选择稿件所在位置（存储位置）。上述几步若未完成，则重复；若完成，则上传稿件至数据存储中，系统发送接收到稿件的通知。稿件的信息包括稿件ID、标题、摘要、URL、状态和录用标准。状态随着整个审稿过程的进行而进行更新。
审稿人登录后可设置兴趣领域、审阅稿件给出评价意见以及罗列录用和（或）拒绝的稿件。审阅意见从原创性、技术质量、相关性和总体评价多个方面进行录入。稿件要限制不能被作者本人审阅。
会议委员会主席是一个特殊审稿人，可以浏览提交的稿件、到了稿件提交的最终日期后给审稿人分配稿件、罗列录用和（或）拒绝的稿件以及关闭审稿过程。如果审稿完成，浏览提交的稿件时可以列出录用和（或）拒绝的稿件。分配稿件时需要满足一篇稿件陆续被分配给3个审稿人审阅，当审阅完成时，如果3位审稿人的总评价满足设定的录用标准（审稿人评价值大于等于某个阈值），则稿件被录用，否则退稿，并发送电子邮件通知作者被录用或退稿。如果稿件被录用，则准备可打印版并打印。关闭审稿过程包括罗列录用和（或）拒绝的稿件。
12.3.3 建模用例
用例图描述系统与外部系统和用户的交互。换句话说，它们以图形化的方式描述了谁将使用系统，以及用户期望以什么方式与系统交互。用例描述也用于以文本化的方式描述每个交互步骤的顺序。用例是一个行为上相关的步骤序列（一个场景），既可以是自动的也可以是手工的，其目的是完成一个单一的业务任务。用例从外部用户的观点并以他们可以理解的方式和词汇描述系统功能。参与者代表了需要同系统交互以交换信息的任何事物。发起或者触发用例的外部用户称为参与者，如人、组织、其他信息系统、外部设备、甚至是时间。用例之间还可能存在扩展关系、包含关系、依赖关系和继承关系，需要进行识别和建模。
初步的需求分析得出表12-3所示的参与者和表12-4所示用例。
表12-3 参与者列表
表12-4 用例名称列表
从需求说明中可知：
（1）用户需注册成为合法的作者和审稿人，因此，如果一个用户要登录时，可先注册，再登录。
（2）作者必须登录之后才能提交稿件。
（3）审稿完成后，浏览提交的稿件时可以列出录用和（或）拒绝的稿件。
（4）关闭审稿过程包括罗列录用和（或）拒绝的稿件，可识别出扩展关系和包含关系。
根据上述分析，建模出用例图如图12-15所示的审稿系统用例图。
图12-15 审稿系统用例图
用例建模技术用于描述系统使用的模型，其建模过程是以用户为中心的建模过程，先识别问题中的参与者、再根据参与者确定每个参与者的用例、定义用例之间的关系、确定模型的过程。用例模型作为后续面向对象分析和设计的基础。
注意：要小心选用用例之间的关系，一般来说这些关系都会增加用例和关系的个数，从而增加用例模型的复杂度。
12.3.4 建模活动
用例建模完成后，对每个用例进行细化，建模活动图。活动图描述一个业务过程或者一个用例的活动的顺序，也可以用于系统的建模逻辑。以用例提交稿件（submit paper）为例，建模其活动。
根据需求描述，提交稿件过程识别出表12-5所示的活动。
表12-5 提交稿件活动名称列表
因为从建模用例图时可知，参与者、作者和用户之间存在继承关系，提交稿件和登录之间存在扩展关系，提交稿件必须是在登录之后进行，所以，提交稿件的过程中首先判断用户是否登录，如果登录则继续；如果没有登录，则执行登录活动。根据活动说明，建模出图12-16所示的活动图。
图12-16 提交稿件过程
活动图并不同于流程图，它提供了描述并行活动的机制，特别适合用于建模当操作正在执行时的活动，以及那些活动的结果。建模活动图时应该遵循如下指导原则。
（1）从一个作为起点的初始节点开始。
（2）如果它们与你的分析有关就增加分割。
（3）为用例的每个主要步骤（或者一个角色发起的每个主要步骤）添加一个动作。
（4）从一个活动到另一个活动、决策点或者终点添加一条流。为了含义的最大精确度，每个动作应该只有一个输入流和一个输出流，所有的分支、联合、决策和合并例外。
（5）在流分解成不同的路线的地方添加决策。确保用一个合并将各个流重新合并。
（6）在并行执行活动的地方添加分支和联合。
（7）用一个单一的活动终止符号结束。
12.3.5 设计类图
类图用于描述系统的对象结构，它们显示了构成系统的对象类，以及那些对象类之间的关系。根据需求描述识别出对象类型有会议、用户、会议主题、稿件和审阅意见。
（1）会议。“会议有名称、涵盖的主题（包括名称和描述）、提交期限、审稿期限、通知日期、状态和会议召开日期等信息。创建一个新的会议后审稿系统启动，在审稿结束时关闭审稿过程。”所得到会议的属性有名称、提交期限、审稿期限、通知日期、状态和会议召开日期；行为有创建会议和关闭审稿过程。
（2）用户。“需要提供名称、单位、电子邮件、登录名、密码、登录的状态。”因此，得到用户的属性有名称、单位、电子邮件、登录名、密码、登录的状态；行为有登录和注册。
（3）会议主题。会议涵盖的主题包括名称和描述，所以属性为名称和描述。
（4）稿件。上传稿件的过程中需要输入标题和摘要、类型、URL、状态已经审阅后的结果，并在系统内有唯一标识，所以稿件的属性有稿件ID、标题、摘要、URL和录用标准；行为有上传、分配和更新状态。
（5）审阅意见。审稿人对稿件进行审阅时，从原创性、技术质量、相关性和总体评价多个方面录入审阅意见。所以，审阅意见的属性有原创性、技术质量、相关性和总体评价；行为有输入审阅意见。
对于每个类型之间，确定其对象／类关系和度数，例如会议和稿件之间的关系是聚合关系，一个会议有很多稿件，得到图12-17所示审稿系统的类图。
Lenat和Guha建议，如果一个概念满足以下几点就应该抽象为一个类。
（1）几个有趣的事务，它们可以作为一个整体被描述为这个概念。
（2）它具有不与任何其他的类共享的属性。
（3）这个概念的声明能将这个类及其所从属的某个较大的类相区别。
（4）这个概念的边界是不精确的。
（5）“兄弟”（如辅助类，这些辅助类的联合是该类的自然泛化）数目是少的。
图12-17 审稿系统的类图
12.3.6 建模对象状态
对象状态表示对象在其生命期中某一点所处的条件，通过修改对象属性的一个或多个值的事件触发对象状态变化。状态图用于建模在生命周期中事件如何改变对象可以经历的各种状态，以及引起对象从一个状态向另一个状态转换的事件。
基于需求描述中的信息，稿件上传成功之后，成为已上传状态。上传稿件的最后期限到了之后，就进入分配中，当分配给审稿人的数量达到规定的三个之后，进入审阅中，审阅结束后，评估结果如果大于等于设定的阈值，则变为录用状态，然后发送E-mail之后，变为已通知，当提交完准备好印制的电子版时，进入打印中，出版之后，状态结束；如果评估结果小于设定的阈值，变为解决状态，发送给作者E-mail通知状态结束。根据分析，得到图12-18所示的一份稿件的状态图。
建模状态图时应该注意遵循如下指导原则。
（1）状态名称要简单但具有描述性。
（2）避免“黑洞”状态，即只有变换进来而没有任何转换发出的状态，这种状态要么由于该状态是一个最终状态，要么就是已经错过了一个或多个转换。
（3）避免“奇迹”状态，即只有转换发出而没有任何转换进来的状态，这种状态要么是一个起点，要么就是已经错过了一个或多个转换。
（4）对符合状态，需要对子状态集进行建模。
（5）为复杂的实体创建分层的状态图。
图12-18 一份稿件的状态图
12.3.7 建模序列图
序列图是以图形化的方式描述了在一个用例或操作的执行过程中对象如何通过消息互相交互，说明了消息在对象之间被发送和接收以及发送的顺序。根据分析设计的迭代演化需求，最初可以绘制系统序列图。系统序列图是一副描述角色和系统在用例场景下交互的图形，有助于确定进入和退出系统的高层信息。
以审稿人获取已分配给自己的稿件的执行序列，浏览会议主页，看到主页后，从导航条浏览已分配给自己的稿件，可循环进行选择，创建已分配稿件并显示给审阅人。得出图12-19所示的审稿人获取分配给自己的稿件列表。
建模序列图应该遵循如下指导原则。
（1）确定顺序图的范围，描述这个用例场景或一个步骤。
（2）绘制参与者和接口类，如果范围包括这些内容的话。
（3）沿左手边列出用例步骤。
（4）对控制器类及必须在顺序中协作的每个实体类，基于它拥有的属性或已经分配给它的行为绘制框。
（5）为持续类和系统类绘制框。
（6）绘制所需消息，并把每条消息指到将实现响应消息的责任的类上。
（7）添加活动条指示每个对象实例的生命期。
（8）为清晰起见，添加所需的返回消息。
（9）如果需要，为循环、可选步骤和替代步骤等添加框架。
图12-19 审稿人获取分配的稿件列表
12.4 算法分析与设计
12.4.1 算法与软件系统
算法的概念在计算机科学领域几乎无处不在，在各种计算机软件系统的实现中，算法设计往往处于核心地位。例如，操作系统是现代计算机系统中不可缺少的系统软件，其中的各个任务都是一个单独的问题，每个问题由一个子程序根据特定的算法来实现。
尽管对有些应用来说，在应用这一层面上没有什么特别明显的算法方面的要求（例如，一些简单的Web应用），但是大多数问题对算法还是有一定要求的。例如，假设有一种基于Web的服务，用于确定如何从一个地方旅行到另一个地方。其实现依赖于快速的计算机硬件、图形用户界面（GUI）、广域网技术，甚至还可能要依赖于面向对象技术。除此之外，它还需要某些操作设计算法，如寻找路由（最短路径算法）、显示地图和插入地址等。
此外，即使那些在应用层面上对算法性内容没有什么要求的应用，其实也是相当依赖于算法的，该应用是否要依赖于快速的计算机硬件？硬件的设计就要用到算法。该应用是否要用到图形用户界面？任何GUI的设计也要依赖于算法。该应用是否要依赖于网络技术？网络路由对算法也有很大的依赖。该应用是否采用某种非机器代码的语言编写？那么，它就要由编译器、解释器或汇编器来处理，所有这些软件都要大量用到各种算法。因此，每个软件系统都会直接或者间接地涉及到算法理论，算法是当代计算机中用到的大部分技术的核心。
随着计算机性能的不断增长，有人可能认为，算法的研究已经不是那么重要了。但是想一想，计算机可以做得很快，但还不能是无限快。存储器可以做得很便宜，但不会是免费的。因此，计算时间是一种有限的资源，存储空间也是一种有限的资源，在开发软件系统时，这些有限的资源应该得到有效的利用。而且，正是由于计算机性能的不断增长，可以利用计算机来解决更复杂的问题，或者规模更大的问题。因此，算法的研究是必要的，它是推动计算机技术发展的关键。
正如第9章提到的，算法理论的研究主要包括算法设计技术和算法分析技术，这两者是不可分割的一个整体。算法设计要设计出针对问题的高质量的算法，算法分析的对象是被设计出的算法，并研究算法所耗费的计算资源与问题规模之间的函数关系，而每一个被设计出的算法只有经过算法分析，才能评价其质量的优劣。
因此，用什么方法来设计算法，如何判定一个算法的优劣，所设计的算法需要占用多少时间资源和空间资源，在实现一个软件系统时，都是必须予以解决的重要问题。
12.4.2 算法设计过程
算法是问题的解决方案，这个解决方案本身并不是问题的答案，而是能获得答案的指令序列。不言而喻，由于实际问题千奇百怪，问题求解的方法千变万化，所以，算法的设计过程是一个灵活的充满智慧的过程，它要求设计人员根据实际情况具体问题具体分析。可以肯定的是，设计算法是一个非常有创造性和值得付出精力的过程。
在设计算法时，有几个问题是要考虑到的：如何设计算法？如何表示算法？如何证明问题解决的正确性？如何评估算法的效率？如何进行算法的最优化？根据这些问题，可以归纳出算法设计的主要步骤：理解问题；确定相关因素，包括问题的输入与输出、用何种数据结构、用什么样的算法设计策略等；设计算法；证明所设计的算法的正确性；分析所设计的算法的效率；实现所设计的算法。
1）理解问题
在面对一个算法任务时，算法设计者往往不能准确地理解要求他做的是什么。对算法希望实现什么只有一个大致的想法就匆忙地落笔写算法，其后果往往是写出的算法漏洞百出。在设计算法时需要做的第一件事就是完全理解要解决的问题，仔细阅读问题的描述，手工处理一些小例子。
对设计算法来说，这是一项重要的技能。准确地理解算法的输入是什么？要求算法做的是什么？即明确算法的入口和出口，这是设计算法的切入点。
2）确定相关因素
（1）预测所有可能的输入。算法的输入确定了该算法所解问题的一个实例。一般而言，对于问题P，总有其相应的实例集I，因此算法A若是问题P的算法，则意味着把P的任一实例input∈I作为算法A的输入，都能得到问题P的正确输出。
预测算法所有可能的输入，包括合法的输入和非法的输入。事实上，无法保证一个算法（或程序）永远不会遇到一个错误的输入，一个对大部分输入都运行正确而只有一个输入不行的算法，就像一颗等待爆炸的炸弹。这绝不是危言耸听，有大量这种引起灾难性后果的案例。例如，许多年以前，整个AT&T的长途电话网崩溃，造成了几十亿美元的直接经济损失。原因只是一段程序的设计者认为他的代码能一直传送正确的参数值，可是有一天，一个不应该有的值作为参数传递了，导致了整个北美电话系统的崩溃。
如果养成习惯——首先考虑问题和它的数据，然后列举出算法必须处理的所有特殊情况，那么可以更快速地成功构造算法。
（2）在精确解和近似解间做选择。计算机科学的研究目标是用计算机来求解人类所面临的各种问题。但是，有些问题无法求得精确解，例如求平方根、解非线性方程和求定积分等。有些问题由于其固有的复杂性，求精确解需要花费太长的时间，其中最著名的要算旅行商问题（TSP问题），此时，只能求出近似解。
有时需要根据问题以及问题所受的资源限制，在精确解和近似解间做选择。
（3）确定适当的数据结构。在结构化程序设计时代，著名的计算机学者沃思（Wirth）提出了“算法＋数据结构＝程序”的观点，断言了算法和数据结构是构成计算机程序的重要基础。在面向对象的程序设计时代，数据结构对于算法设计和分析仍然是至关重要的。
确定数据结构通常包括对问题实例的数据进行组织和重构，以及为完成算法所设计的辅助数据结构。在很多情况下，数据结构的设计直接影响基于该结构之上设计的算法的时间性能。
（4）确定算法设计技术。第9章介绍的算法设计技术（或称为算法设计策略）是设计算法的一般性方法，可用于解决不同计算领域的多种问题。这些算法设计技术包括分治法、动态规划法、贪心算法、回溯法、分支限界法、概率算法和近似算法等，已经被证明是对算法设计非常有用的通用技术，它们构成了一组强有力的工具，在为新问题设计算法时，可以运用这些技术设计出新的算法。算法设计技术作为问题求解的一般性策略，在解决计算机领域以外的问题时，也能发挥相当大的作用。
3）设计算法
根据1）和2）的结果，就可以设计算法。在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。描述算法的常用方法有自然语言、流程图、程序设计语言和伪代码等，其中伪代码是比较合适的描述算法的方法。
4）证明算法的正确性
可以用循环不变式来证明算法的正确性，以插入排序为例介绍循环不变式，以下是插入排序的伪代码（伪代码的约定参考第9章）。
对要分析的算法，定义循环不变式，如对插入排序，定义其外层循环的循环不变式为：在每一轮迭代的开始，子数组A［1..j-1］中包含了最初位于A［1..j-1］，但目前已经排好序的各个元素。然后证明循环不变式的三个性质。
（1）初始化。在循环的第一轮迭代开始之前它是正确的。对于插入排序，第一轮迭代之前，j＝2，子数组为A［1..j-1］，即A［1］，也就是最初在A［1］中的那个元素，显然这个子数组是已排好序的，因此循环不变式成立。
（2）保持。如果在循环的每一次迭代之前它是正确的，那么在下一次迭代之前，它也应该保持正确。对于插入排序（上述伪代码包含两重循环，应该定义两个循环不变式，并证明它们的正确性。但为了简便，暂时不陷入过于形式化的细节，仅考虑外层循环），要将A［j-1］、A［j-2］和A［j-3］等元素向右移一个位置，直到找到A［j］的适当位置为止（第4～7行），这时将A［j］的值插入（第8行）。很显然，循环不变式是成立的。
（3）终止。当循环结束时，循环不变式给了我们一个有用的性质，它有助于表明算法是正确的。对于插入排序，当j大于n时，外层for循环结束。在循环不变式中，将j替换为n+1，就有子数组A［1..n］包含了原先在A［1..n］中的元素，但现在已经排好序了，这意味着算法是正确的。
除了循环不变式外，经验和研究表明，发现算法（或程序）中逻辑错误的重要方法就是系统地跟踪算法。跟踪必须要用“心和手”来进行，跟踪者要像计算机一样，用一组输入值来执行该算法，并且这组输入值要最大可能地暴露算法中的错误。即使有几十年经验的高级软件工程师，也经常利用此方法查找算法中的逻辑错误。
5）分析算法的效率
设计出的算法只有经过分析，才能评价其优劣，才能判断其是否能满足问题求解的需求或者在多个算法之间进行选择。算法分析主要分析两种效率：时间效率和空间效率，时间效率显示了算法运行得有多快，空间效率则显示了算法需要多少额外的存储空间，相比而言，一般更关注算法的时间效率。事实上，计算机的所有应用问题，包括计算机自身的发展，都是围绕着“时间—速度”这样一个中心进行的。一般来说，一个好的算法首先应该是比同类算法的时间效率高。
6）根据算法编写代码
现代计算机技术还不能将伪代码形式的算法直接“输入”进计算机中，而需要把算法转变为特定程序设计语言编写的程序，算法中的一条指令可能对应实际程序中的多条指令。在把算法转变为程序的过程中，虽然现代编译器提供了代码优化功能，但仍需要一些标准的技巧，例如，在循环体之外计算循环中的不变式、合并公共子表达式、用开销低的操作代替开销高的操作等。一般来说，这样的优化对算法速度的影响是一个常数因子，可能会使程序提高10％～50％的速度。
算法设计的一般过程如图12-20所示。需要强调的是，一个好算法是反复努力和重复修正的结果。那么，什么时候应该停止这种改进呢？设计算法是一种工程行为，需要在资源有限的情况下，在互斥的目标之间进行权衡。设计者的时间显然也是一种资源，在实际应用中，常常是项目进度表迫使我们停止改进算法。
图12-20 算法设计过程
12.4.3 算法问题类型
就像生物学家把自然界的所有生物作为自己的研究对象，计算机科学把问题作为自己的研究对象，研究如何用计算机来解决人类所面临的各种问题。在计算领域的无数问题中，或者由于问题本身具有一些重要特征，或者由于问题具有实用上的重要性，有一些领域的问题是算法研究人员特别关注的。经验证明，无论对于学习算法还是应用算法，对这些问题的研究都是极其重要的。下面列出几类重要的问题。
1．查找问题
查找是在一个数据集合中查找满足给定条件的记录。对于查找问题来说，没有一种算法对于任何情况都是合适的。有的算法查找速度比其他算法快，但却需要较多的存储空间（例如Hash查找）；有的算法查找速度非常快，但仅适用于有序数组（例如折半查找），等等。此外，如果在查找的过程中数据集合可能频繁地发生变化，除了考虑查找操作外，还需要考虑在数据集合中执行插入和删除等操作。这种情况下，就必须仔细地设计数据结构和算法，以便在各种操作的需求之间达到一个平衡。而且，组织用于高效查找的特大型数据集合对于实际应用具有非常重要的意义。
2．排序问题
简单地说，排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对记录进行排序时，需要选定一个信息作为排序的依据，例如，可以按学生平均成绩对学生记录进行排序，这个特别选定的信息（平均成绩）称为关键码。
排序的一个主要目的是为了进行快速查找，这就是为什么字典、电话簿和班级名册都是排好序的。当然，在很多领域的重要算法中，排序也被作为一个辅助步骤，例如，搜索引擎将搜索到的结果按相关程度排序后显示给用户。
迄今为止，已经发现的排序算法不下于几十种，没有一种排序算法在任何情况下都是最好的解决方案，有些排序算法比较简单，但速度相对较慢；有些排序算法速度较快，但却很复杂；有些排序算法适合随机排列的输入；有些排序算法更适合基本有序的初始排列；有些排序算法仅适合存储在内存中的序列；有些排序算法可以用来对存储在磁盘上的大型文件排序等。
3．图问题
算法中最古老也是最令人感兴趣的领域是图问题，很多纷乱复杂的现实问题抽象出的模型都是图结构，如社会网络、Web、工作流、XML数据、电路、图像、化合物和生物网络等。作为一种通用的、复杂的数据结构，基于图的相关算法也具有十分重要的作用。
有些图问题在计算上是非常困难的，这意味着，在能够接受的时间内，即使用最快的计算机，也只能解决这种问题的一个很小规模的实例，例如TSP问题、最大团问题（即最大独立集问题）、图着色问题、哈密尔顿回路问题、顶点覆盖问题和最长路径问题等。图问题中还有一个奇怪的现象：许多形式上非常类似的问题，解决它们的难度却相差很大，例如，最短路径问题和欧拉回路问题存在多项式时间算法，而最长路径问题和哈密尔顿回路问题至今没有找到一个多项式时间算法。
4．组合问题
组合问题一般都是最优化问题，因此也称为组合优化问题，即寻找一个组合对象，例如一个排列、一个组合或一个子集，这个对象能够满足特定的约束条件并使得某个目标函数取得极值：价值最大或者成本最小。典型的组合优化问题包括0-1背包问题、TSP问题和整数线性规划等。
无论从理论的观点还是实践的观点，组合问题都是计算领域中最难的问题，其原因如下。
（1）随着问题规模的增大，组合对象的数量增长极快，即使是中等规模的实例，其组合对象的数量也会达到不可思议的数量级，产生组合爆炸。
（2）还没有一种已知算法能在可接受的时间内，精确地求解绝大多数问题。
5．几何问题
几何问题处理类似于点、线、面和体等几何对象。几何问题与其他问题的不同之处在于，哪怕是最简单、最初等的几何问题也难以用数字去处理。尽管人类对几何问题的研究从古代起便没有中断过，但是具体到借助计算机来解决几何问题的研究，还只是停留在一个初始阶段。随着计算机图像图形处理、机器人和断层X摄像技术等方面应用的深入，人们对几何算法产生了强烈的兴趣。经典的几何问题包括最近点对问题和凸包问题，前者指的是在给定平面上的n个点中，求距离最近的两个点；后者指的是要找出一个能把给定集合中的所有点都包含在里面的最小凸多边形。
12.4.4 现代优化计算方法
上述提到的组合优化问题很多都是NP-难问题，因此目前还不存在有效的算法——多项式时间算法来求解，而这些问题又是现实中人们常常遇到的、需要解决的问题。因此，计算机科学和算法研究者们致力于研究求解这些难解问题的一些可行的方法。自20世纪80年代以来得到快速发展和广泛应用的现代优化计算方法，借助现代计算机作为工具，对复杂的组合优化问题的求解具有普遍适用性。这些方法包括禁忌搜索算法（tabu search）、模拟退火算法（simulated annealing）、遗传算法（genetic algorithms）、蚁群优化算法（ant colony optimization）和人工神经网络（artificial neural networks）等。它们中的每一个算法都以人类、生物的行为方式或物质的运动形态为背景，经过数学抽象建立算法模型，通过计算机的计算来求解组合优化问题，因此这些算法也被称之为元启发式算法（meta-heuristics）。
1．禁忌搜索算法
禁忌搜索的思想最早由Glover于1986年提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。简单的局部邻域搜索从任何一个初始解出发，达到一个局部最优解停止。因此，算法停止时得到的解依赖于算法初始解的选取、邻域的结构和邻域选解的规则。这个方法往往容易导致局部最优解，而难以得到全局最优解。而禁忌搜索算法引入禁忌策略尽量避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。禁忌搜索的思想基于这样的日常生活现象：当要寻找某个东西或寻找某个地方时，对刚刚已经搜索的地方不会立即去搜索，而更大的概率是到近一段时间内没有去过的地方进行搜索，若没有找到，再搜索已经去过的地方。
禁忌搜索涉及到邻域函数、禁忌表、禁忌对象、禁忌长度、候选解和藐视准则等概念。通常邻域函数沿用局部邻域搜索的思想，以实现邻域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；禁忌长度决定禁忌对象的任期；候选解从当前解的邻域函数产生的邻域解中确定；藐视准则是对优良状态的奖励，是对禁忌策略的一种松弛，从而实现全局优化。
禁忌算法的基本思想：给定一个初始解（当前解）和一种邻域函数，在当前解的邻域函数确定的邻域解中确定若干候选解。若最佳候选解对应的目标值优于best so far状态，则忽视其禁忌特性，用其代替当前解和best so far状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期。若不存在上述候选解，则在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期。如此重复上述迭代搜索过程，直至满足停止准则。
禁忌搜索算法的新解不是在当前解的邻域中随机产生，而是优于best so far的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。由于禁忌搜索算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增强获得更好的全局最优解的概率，所以禁忌搜索算法是一种局部搜索能力很强的全局迭代寻优算法。但是，禁忌搜索算法对于初始解具有较强的依赖性，一个较好的初始解可使禁忌搜索在解空间中搜索到更好的解，而一个较差的初始解则会降低禁忌搜索的收敛速度，搜索到的解也相对较差。迭代搜索过程是串行的，仅是单一状态的移动，而非并行搜索，这就使得算法的优化时间往往较长。
禁忌搜索算法在组合优化、生产调度、机器学习、路由选择和电路设计等领域取得了很大的成功。并且，为了进一步改善禁忌搜索算法的性能，可以对算法本身的操作和参数选择进行改进，也可以把禁忌搜索与其他启发式方法结合起来，如与模拟退火、遗传算法和人工神经网络等相结合。
2．模拟退火算法
模拟退火算法最早的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地应用在组合优化问题上。模拟退火算法是局部搜索算法的扩展，它不同于局部搜索之处是以一定的概率选择邻域中较差的解。从理论上说，它是一个全局最优算法。
模拟退火算法来源于物理退火过程，主要包括如下三个阶段。
（1）加温阶段。
（2）等温阶段。
（3）冷却阶段。
模拟退火算法的基本思想：首先将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状态，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为
其中E为温度T时的内能，∆E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子∆t、每个t值时的迭代次数L和停止条件S。
模拟退火的步骤如下。
（1）初始化。初始温度T（充分大），初始解状态S（是算法迭代的起点），每个T值的迭代次数L。
（2）对k＝1,…，L进行（3）～（6）步操作。
（3）产生新解S′。
（4）计算增量∆t′＝C（S′）－C（S），其中C（S）为评价函数。
（5）若∆t′＜0，则接受S′作为新的当前解；否则以概率exp（-∆t′/T）接受S′作为新的当前解。
（6）如果满足终止条件则输出当前解作为最优解，结束程序（终止条件通常取为连续若干个新解都没有被接受时终止算法）。
（7）T逐渐减少，且T趋于0，然后转步骤（2）。
模拟退火算法实质上是局部搜索算法的推广，因此它克服了局部搜索算法局部最优的缺点，但它同样也面临解的表示和邻域函数的设计问题，好的设计方法能使算法在可行解域内进行搜索，否则会扩大搜索空间，增加搜索时间。同时，模拟退火算法是一种通用的、高效的、健壮的和灵活的随机近似算法，并且可以较容易地并行实现以进一步提高运行效率，适合求解大规模组合优化问题，特别是NP完全问题，因此具有很大的实用价值。此外，对模拟退火算法做一些局部或策略上的修改，还可以得到一些推广或变异形式。
3．遗传算法
遗传算法由J.Holland教授于1975年首先提出，并逐渐发展起来。“适者生存”揭示了大自然生物进化过程中的一个规律—最适合自然环境的群体往往产生了更大的后代群体。遗传算法就是基于生物界的进化规律演化而来的随机化搜索方法，其思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。其中，选择、交叉和变异构成了遗传算法的基本操作。
（1）选择（也称为再生）。从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。
（2）交叉。在选中用于繁殖下一代的个体中，对两个不同个体的相同位置的基因进行交换，从而产生新的个体。
（3）变异。在选中的个体中，对个体中的某些基因执行异向转化。
遗传算法的主要步骤如下。
（1）初始化。选择一个群体，这个初始的群体也就是问题假设解的集合。
（2）选择。根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
（3）交叉。对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P，在选中的位置实行交换。
（4）变异。根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。
（5）全局最优收敛。
当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到步骤（2）即选择操作处继续循环执行。
遗传算法是一种随机的优化与搜索方法，具有并行性、通用性、全局最优性、健壮性、可操作性和简单性等特点。遗传算法不论是在应用、算法设计上，还是基础理论上都得到了长足的发展，已经成为信息科学、计算机科学、运筹学和应用数学等诸多学科共同关注的热点研究领域。
4．蚁群优化算法
1991年，意大利学者M.Dorigo等基于自然界蚁群觅食原理，首先提出了第一个蚁群算法的最早形式——蚂蚁系统（AS），并应用到TSP问题中。AS算法被提出之后，其应用范围逐渐广泛，算法本身也不断被完善和改进，形成了一系列的蚁群优化算法。蚁群优化算法是一种受自然界生物行为启发而产生的“自然”算法，产生于对蚁群行为的研究，是一种分布式的智能模拟算法。蚁群中的蚂蚁以信息素为媒介，间接异步地相互联系。这是蚁群算法的最大特点。蚂蚁在行动（寻找食物或者寻找回巢的路径）中，会在它们经过的地方留下一些化学物质，称之为“信息素”。这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后者的行为，具体表现在后到的蚂蚁选择有这些物质的路径的可能性比选择没有这些物质的路径的可能性大得多。后到者留下的信息素会对原有的信息素进行加强，并循环下去。这样，经过蚂蚁越多的路径，后到蚂蚁选择这条路径的可能性就越大。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。
通俗地说，蚁群算法可以看作是三个过程的相互作用，即蚂蚁构建解、更新信息素和后台执行。
蚂蚁构建解通过使蚂蚁移动到相应构建图Gc上的邻近点，而使一群蚂蚁并行异步地访问所考虑问题的邻近状态。蚂蚁根据信息素和启发式信息，采用一个随机局部决策方法选择移动的下一步。这样，蚂蚁就可以逐步建立起优化问题的解。一旦蚂蚁建立了一个解，或者是在构建解的期间，蚂蚁将对部分解进行评估，以便在更新信息素过程使用该（部分）解来决定应释放信息素的多少。
更新信息素就是修改信息素浓度的大小。信息素的浓度可能会因蚂蚁在点或连接的边上释放信息素而增加，也可能会由于信息素的蒸发而减少。从实际的角度看，释放新的信息素增加了蚂蚁访问某个点或者某条连接边的概率，这些点（边）有可能已经有很多蚂蚁访问过，或者至少有一只蚂蚁访问过，并产生了好的解从而会吸引以后的蚂蚁重新访问。不同的是，信息素的蒸发所起到的遗忘作用是很有用的：它可以避免算法朝着一个并非最佳的解区域过早收敛，从而使算法有更多的机会探索搜索空间中的新区域。
后台执行的过程就是执行单一蚂蚁不能完成的集中行动。后台执行的例子有局部优化过程的执行和全局信息的收集，在非局部的情况下，这个全局信息可以用于决定释放某些额外的信息素来调整搜索过程。
作为一种新的启发式优化算法，蚁群算法引起了相关领域的关注。蚁群算法具有较强的健壮性、通用性、快速性、全局优化和并行搜索等优点，蚁群算法从本质上讲是一种模拟进化算法，它的产生与进化算法的发展息息相关。如果与群体搜索策略结合使用，并保证群体中个体之间的信息交换，则蚁群算法可体现进化计算的优越性。但蚁群算法还存在如下一些问题。
（1）从数学上对其正确性与可靠性进行证明比较困难。
（2）蚁群算法是一个专用算法，一般只能解决一个问题，各种算法之间的相似性很差。
（3）系统的高层次行为是通过低层次的昆虫（蚂蚁）之间的简单行为交互而产生的。将高层的复杂行为映射到低层次简单个体的简单行为是一件极其困难的事情。
（4）蚁群算法的搜索时间较长，在算法模型、收敛性以及理论依据上还有许多工作有待进一步深入研究。
5．人工神经网络
人类对人工神经网络的研究可以追溯到1943年，心理学家W.S.McCuloch和数理逻辑学家W.Pitts最早提出的人工神经网络模型—M-P模型，是第一个用数理语言描述人脑的信息处理过程的模型，从此开创了神经科学理论研究的新纪元。1969年，人工智能的创始人中M.Minsky和S.Papert出版了有较大影响的《感知器》一书，指出感知器功能上的局限性，该论点极大地影响了人工神经网络的研究，至此进入了人工神经网络发展史上长达10年的低潮期。进入20世纪80年代后，随着计算机科学、生物技术和光电技术等领域学科的迅速发展，人工神经网络的研究进入到了一个新的大发展阶段。1982年，美国生物学家、物理学家J.Hopfield提出了Hopfield网络模型；1985年，D.E.Rumelhart和J.LMcclelland提出了误差反向传播（BP）算法，成为迄今为止影响较大的一种网络学习方法。
人工神经网络模型主要考虑网络连接的拓扑结构、神经元的特征和学习规则等。目前，已有近40种神经网络模型，其中有反传网络、感知器、自组织映射、Hopfield网络、波耳兹曼机和适应谐振理论等。根据连接的拓扑结构，神经网络模型可以分为如下几种。
（1）前向网络。网络中各个神经元接受前一级的输入，并输出到下一级，网络中没有反馈，可以用一个有向无环图表示。这种网络实现信号从输入空间到输出空间的变换，它的信息处理能力来自于简单非线性函数的多次组合。网络结构简单，易于实现。反传网络是一种典型的前向网络。
（2）反馈网络。网络内神经元间有反馈，可以用一个无向的完备图表示。这种神经网络的信息处理是状态的变换，可以用动力学系统理论处理。系统的稳定性与联想记忆功能有密切关系。Hopfield网络、波耳兹曼机均属于这种类型。
学习是神经网络研究的一个重要内容，它的适应性是通过学习实现的。根据环境的变化，对权值进行调整，改善系统的行为。由Hebb提出的Hebb学习规则为神经网络的学习算法奠定了基础。Hebb规则认为学习过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。在此基础上，人们提出了各种学习规则和算法，以适应不同网络模型的需要。有效的学习算法，使得神经网络能够通过连接权值的调整，构造客观世界的内在表示，形成具有特色的信息处理方法，信息存储和处理体现在网络的连接中。
人工神经网络具有以分布方式存储知识、并行方式处理、较强的容错能力，并且它具有可以逼近任意的非线性函数以及有很强的自学习、自适应和联想记忆功能等特征，引起了众多研究人员的兴趣，并在相关领域取得了显著的进展。例如，自动化领域的系统识别和神经控制器以及智能检测，经济领域中的市场预测和信贷分析，工程领域中的汽车工程、军事工程、水利工程和化学工程，信息领域中的信号处理、模式识别、数据压缩，医学领域中的生物活动分析、医学专家系统等。
12.5 面向过程的程序设计与实现
C语言是面向过程程序设计中的典型语言，它提供了丰富的数据类型、运算符号和灵活的控制语句，熟悉C语言提供的数据类型、运算符号和语句是进行C程序设计的最基本要求。合理使用数据类型和控制结构对软件的可维护性、可扩展性起重要作用。
指针是C语言的精华部分，它极大地丰富了C语言的功能。通过利用指针，可以描述复杂的数据结构，编程时能很好地利用内存资源，使其发挥最大的效率。运用指针编程是C语言最主要的风格之一。
12.5.1 指针类型
1．变量和指针
在程序中定义或说明的变量，编译系统为其分配相应的内存单元，也就是说，每个变量都有具体的地址。简单而言，程序语言中的变量就是内存单元的抽象。变量具有类型、值、地址、作用域和生存期等属性。
变量的本质是程序中用来存放数据的一段存储空间，一般情况下，变量所对应的存储空间在内存区域，C语言中程序员可以通过关键字register声明变量的存储单元是CPU中的寄存器。
变量的数据类型不同，它所占的内存单元数也不相同。访问变量时，首先应找到其在内存的地址。如果在程序中将变量的地址保存在另一个变量中，则形成指针变量，通过指针对所指向变量的访问，是一种对变量的“间接访问”。
例如，下面定义两个变量：整型变量a和指针变量ptr，在存取变量a中的数据时，可通过变量a或指向变量a的指针来进行，分别称为直接访问和间接访问。
（1）直接访问变量a中的数据。
（2）间接访问变量a中的数据。
经上述定义和处理后，变量a和指针变量ptr之间的关系如图12-21所示。
图12-21 指针变量ptr与指针变量指向的对象*ptr（a）
若指针变量指向的对象仍然是一个指针变量，则称为多级指针。
例如，对于下面的变量定义，mulptr是指向指针变量ptr的变量，这些变量间的关系如图12-22所示。
图12-22 二级指针变量mulptr
根据应用的需要，可以采用三级或多级指针。当然，采用多级指针在带来灵活性的同时降低了对数据的访问效率。
2．通过指针访问数组中的元素
C程序中常利用指针对数组和字符串进行处理。一个数组由连续的一块内存单元组成，数组名就是这块连续内存单元的首地址（起始地址）。一个数组是由各个数组元素（通过下标区分）组成的，每个数组元素按其类型不同占有若干个连续的内存单元。
通过指针访问数组元素是指针变量的一种常见应用方式。
1）指针变量与一维数组
指针变量指向一维数组元素的情形较为简单。C语言中定义一个指向数组元素的指针变量的方法如下所示。例如，定义一个整型数组st和指向数组元素的指针ptr。
若ptr指向数组的第一个元素（即下标为0的元素），则*（p+i）指向数组的第i＋1个元素（即下标为i的元素）。
例如，设数组a的空间足够大，函数InsertElem（int a[], int n, int newElem）的功能是将newElem中的数值插入到元素已经按照非递减方式排序的数组a中，并保持数组a中数据的排序特性。其中对数组元素的访问采用指针方式。
2）指针变量与二维数组
指针变量指向二维数组元素的情形比较复杂，下面举例简单说明。
设有定义int a[3][4]，其元素布局如图12-23所示。
图12-23 二维数组a[3][4]元素布局
数组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为指向二维数组的指针变量。可定义为：
因此，可令p＝a（等价于p＝a[0]）或p＝a[1]或p＝a[2]。若令p＝a[1]，则*（p+2）就表示数组元素a[1][2]，二维数组其他元素通过指针p的表示方式依此类推。
3．指针与函数
C程序中将指针与函数结合使用的常见方式有函数参数为指针、函数返回值为指针以及通过函数指针变量调用函数（函数指针变量）。
1）函数参数为指针
函数的参数不仅可以是整型、实型、字符型等基本数据类型，还可以是指针类型。参数使用指针类型的作用是将一个变量的地址传送到另一个函数中。
C语言中实参向形参传递值，反之则不行。
例如，定义函数swap_1（a,b）的功能是交换a和b的值，代码如下：
如果发生函数调用swap_1（x,y），则系统将x的值传给a、y的值传给b，在函数swap_1中实现了a和b的值交换，但是x和y的值并不发生交换。为实现将函数中对形参的修改结果返回给调用函数之处，可使用指针参数。
对于上例，定义函数swap_2如下：
当形式参数为指针类型时，传递给形参的应该是地址信息，因此调用swap_2的形式为swap_2（&x，&y）。这样通过“间接访问”，实现了在被调用函数中修改实参所对应的变量的内容。
通过指针参数也可以实现将被调用函数中的多个处理结果传回给调用函数的地方。
当函数的参数为数组时，实参和形参即可以用指针形式，也可以用数组形式，实参向形参传递的是数组空间的首地址。
2）函数返回值为指针
函数类型是指函数返回值的类型。在C语言中允许一个函数的返回值是一个指针（即地址），这种返回指针值的函数称为指针型函数。
需要注意的是，不能返回局部数据的指针。
例如，下面的函数get_str虽然返回了局部数组str的首地址，但调用get_str的其他函数并不能通过此地址访问字符串″testing local pointer″。
将上述函数get_str中的char str[]={″testing local pointer″}；改为char *str={″testing local pointer″}即可，或者从内存的堆区申请字符串的空间，然后返回首地址。
函数返回值为指针时，也可以实现将被调用函数中的多个处理结果传回给调用函数的地方。
3）指针变量
程序中的一个函数总是占用一段连续的内存区，而函数名就是该函数所占内存区的首地址。可以把函数的首地址（或称入口地址）赋给一个指针变量，使指针变量指向该函数，然后通过指针变量就可以找到并调用这个函数。指向函数的指针变量称为“函数指针变量”。
函数指针变量定义的一般形式为：
类型说明符 （*指针变量名）（）；
其中，“类型说明符”表示被指函数的返回值的类型；“（指针变量名）”表示“”后面的变量是指针变量；最后的一对空括号表示指针变量所指向的对象是一个函数。
例如，下面定义了一个函数指针变量funptr。
下面的程序中先定义了一个函数max（a,b），其功能是比较用a和b表示的两个整数并返回它们中的较大者，然后通过函数指针变量调用max。
既然函数指针变量是一个变量，当然也可以作为某个函数的参数来使用。例如，下面的程序中设计了一个testFunCall函数，该函数根据其函数指针参数值的不同分别调用函数fun1和函数fun2（注：fun1和fun2的定义格式应相同）。
12.5.2 指针与数据结构
“程序＝数据结构＋算法”常用来说明程序、数据结构（数据的存储结构）与算法之间的关系，指针在数据结构的设计和实现中有重要的作用。随着软件开发环境不断完善和程序语言的抽象程度不断提高，数据结构的内部设计细节被封装和屏蔽起来，在很多应用软件的开发中没有必要也不再涉及底层细节，但是在系统级程序设计或嵌入式应用的软件设计中，指针及相关机制的应用仍然是十分必要的。
1．单链表的实现和应用
在数据结构的设计中，指针是常用的工具。对于无法预先确定数据规模的应用，可采用动态存储的方法解决数据的存储问题，也就是链表结构。链表中的每个节点之间可以是地址不连续的（节点内是连续的），节点之间的联系用指针实现，实际上是在节点结构中定义一个成员项来存放下一节点的首地址，称为指针域。
C语言标准库中提供的用于申请动态存储空间的函数是malloc（）、calloc（）和realloc（），函数free（）用于释放由上述函数申请的内存空间。
栈是一种常用的数据结构，下面设计并实现一个用链表结构的栈，如图12-24所示（为了简化，栈中的元素类型设为int型）。
图12-24 栈的链式存储结构示意图
2．二叉链表和多叉链表的设计和应用
1）二叉树的存储结构设计
二叉树是一种重要的数据结构，采用二叉链表存储时，其节点的类型常定义为：
对于某些特殊的二叉树，如哈夫曼树（或称为最优二叉树），由于该类型二叉树中的内部节点是由初始的m个叶子节点根据一定的规则构成的，因此其节点总数总是2m－1，所以采用静态的二叉链表来表示，其类型定义如下：
以具有4个叶子节点（分别用a，b，c，d表示，权值为2，7，4，5）为例，采用哈夫曼算法构造的最优二叉树及其存储结构如图12-25所示。
图12-25 树及其孩子—兄弟表示示意图
2）其他树结构的存储结构设计
一般的树结构常采用孩子—兄弟表示法表示，即采用二叉链表作为树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。节点类型定义如下：
例如，图12-26（a）所示树的孩子一兄弟表示如图12-26（b）所示。
图12-26 树及其孩子—兄弟表示示意图
显然，在物理上，表示一般二叉树的二叉链表与树的孩子一兄弟表示法的结构是相同的，其差别在于对指针所指对象的解释，也就是在逻辑上进行区分。
B树是适用于外部查找的平衡查找树，一个4阶的B树如图12-27所示。
图12-27 4阶B树示例
其存储结构的类型定义如下。
B树的阶M、bool类型、关键字类型及B树节点的定义如下：
3．其他链表的设计和应用
图也可以采用链接表存储结构，称为邻接表，其数据类型定义如下：
例如，某有向图（网）如图12-28（a）所示，其邻接表存储结构如图12-28（b）所示。
图12-28 图的邻接表存储结构设计
在散列技术中，可用拉链法将冲突的元素存储起来，实际上就是链表结构的一个应用。例如，可以设计散列桶结构的类型如下：
设散列函数为Hash（Key）=Key mod7，对于关键字序列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-29 散列桶结构示例
从上述内容可知，利用指针实现的链表结构有灵活多变的形式，可根据应用的需要为数据存储设计不同的结构。显然，数据的存储方式不同，体现相同算法思路的处理过程可能会有较大的差异。因此，算法的实现过程与数据结构的设计是密切相关的，在有些情况下，算法的实际效率会因为数据存储结构的不同而不同。
12.5.3 C语言实现面向对象设计思路
C语言是典型的过程式和结构化程序设计语言，由于支持位运算及内存地址操作，因此该语言适用于系统级和嵌入式软件设计。面向对象程序语言C++是在保持C语言效率的基础上扩充面向对象特性得到的。另一个面向对象程序语言Java虽然具备许多独立的特性，但它是在摒弃了多种语言的不足之处，从根本上解决了C++的固有缺陷后而开发的面向对象语言。Java对象其实是从C++中的对象和指针共同继承而来的。因此，在操作系统软件的底层部分常用C语言实现，而高层部分则采用面向对象程序设计语言实现。
用程式语言也可以在部分程度上实现面向对象的程序设计思想。例如，在一个简化的绘图程序中，支持点（point）和圆（circle）两种图形，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形（shape），并定义类型shape_t、point_t和circle_t分别表示基本图形、点和圆，点和圆自然具有基本图形的所有特征，它们的关系如图12-30所示。
图12-30 point_t、circle_t和shape_t的关系
下面的程序代码利用指针、可变数目参数机制实现以上设计，point_t和circle_t两种结构通过其成员shape_t common表示了图12-30中的继承关系；circle_t与point_t之间的引用关系用circle_t的数据成员point_t *center来表示。
C语言是一种基础性很强的通用程序设计语言，而程序设计方法是跨语言的，指针类型为实现C语言的强大功能和灵活性提供了保障，软件设计师应该熟悉C语言提供的各种机制，掌握用该语言实现的常用数据结构、算法并灵活应用。
12.6 面向对象的程序设计与实现
12.6.1 设计与实现方法
面向对象程序设计主要是根据问题的详细描述，设计出能够被迅速转换为面向对象程序实现的代码，相比本章的第12.3节，其设计与实现更为底层，更接近代码。但是，对面向对象设计结果的衡量没有统一的标准，因此很难衡量针对一个问题所设计的解决方案是否最优，这也正是软件工程领域内分析与设计的难点，更多的情况下，分析与设计的结果是一种经验的总结。
尽管不存在一致的对分析与设计结果的衡量标准，但许多面向对象和软件工程领域内的“大师”都根据自己长期的实践经验，总结出了面向对象分析与设计的原则，而这些原则可成为我们在对实际问题进行分析与设计时的指导准则。
一般而言，当面临一个具体的问题时，可分为两大阶段：首先根据问题进行设计，其次根据设计进行实现。由于面向对象的实现和面向对象设计之间不存在较大的差异，所不同的是设计更多采用的是UML的标准表示，而实现则是采用面向对象语言表达，因此解决问题的重点应放在面向对象的设计上。
目前，被公认的好的面向对象设计是由前人所总结的设计模式，因此，熟练并正确地掌握面向对象设计技术，必须很好地体会并理解常用的23种设计模式。当对23种设计模型运用时，必须做到以下几点。
（1）能够根据设计模式的名称画出其对应的类图。
（2）理解类图中每一个类的作用与功能。
（3）能够将现实问题中所描述的各种职责映射到类图中具体的类。
（4）能够使用一种面向对象语言实现设计。
下面通过具体的应用来说明这个过程。
12.6.2 设计模式的应用
1．问题说明
已知某类库开发商提供了一套类库，类库中定义了Application类和Document类，它们之间的关系如图12-31所示，其中，Application类表示应用程序自身，而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个Document对象表示。
图12-31 Application与Document关系图
当开发一个具体的应用程序时，开发者需要分别创建自己的Application和Document子类，例如图12-31中的类MyApplication和类MyDocument，并分别实现Application和Document类中的某些方法。
已知Application类中的openDocument方法采用了模板方法（Template Method）设计模式，该方法定义了打开文档的每一个主要步骤，如下所示。
（1）首先检查文档是否能够被打开，若不能打开，则给出出错信息并返回。
（2）创建文档对象。
（3）通过文档对象打开文档。
（4）通过文档对象读取文档信息。
（5）将文档对象加入到Application的文档对象集合中。
2．根据设计模式的名称画出其对应的类图
问题描述中已经给出了该设计采用的设计模式为模板方法，因此，首先给出模板方法的类图，如图12-32所示。
3．理解类图中每一个类的作用与功能
模板方法类图中，AbstractClass类定义了基本的操作PrimitiveOperation1（）和PrimitiveOperation2（），并在TemplateMethod（）方法中调用了这两个操作，但这两个操作都并未实现，而是留待子类去实现，从而达到模板方法的目的：定义一个操作中的算法的骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。
图12-32 模板方法类图
4．能够将现实问题中所描述的各种职责映射到类图中具体的类
在提出的具体问题中，已经告知了Application类中的openDocument方法采用了模板方法，而openDocument方法的步骤都已经给出，因此，很容易将Application类对应为模板方法类图中的AbstractClass类，openDocument方法映射为模板方法类图中的TemplateMethod方法，而主要步骤则对应为PrimitiveOperation1（）等基本操作。由此可推出，各种主要的步骤中，应该存在某些步骤是由Application的子类实现的。
5．能够使用一种面向对象语言实现设计
一旦分析清楚实际问题的设计结果和原始的设计模式类图中类的对应关系，便可采用一种面向对象语言实现。下面分别采用C++和Java语言实现给出的设计。
【C++代码】
【Java代码】
