数据结构与算法分析(C++)序言.doc

《数据结构与算法分析(C++)序言.doc》由会员分享，可在线阅读，更多相关《数据结构与算法分析(C++)序言.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件开发 章节内容 问题分析和需求规格说明 设计 编码 测试、运行和调试 维护 章节学习目标n 介绍一些流行的软件开发方法并研究软件工程的基本阶段。n 对比入门性编程课程中的软件开发和实际的软件开发。n 学习软件设计的两种基本方法：自顶向下设计和面向对象设计。n 介绍设计的两个基本方面：选择或创建组织数据的数据类型以及为数据上的操作开发算法。n 考察开发好的源代码的一些基本方针，并学习一个优秀代码的例子。n 调查软件中的基本错误类型以及定位这些错误源头的方法。n 通过一些糟糕软件造成严重后果的例子来强调软件测试的重要性。n 关注软件维护所需要的大量时间和努力。使用计算机解决一个问题需要同时使用

2、硬件和软件。一个计算系统的硬件由实际的物理组件构成，比如中央处理器（CPU）、存储器以及组成系统的输入/输出设备等。软件指为了解决问题而用来控制硬件操作的程序。软件开发是一个复杂的过程，它既是一门艺术，也是一门科学。说它是艺术，是因为它需要丰富的想象力、创造力和灵活性。但它同时也是一门科学，因为它要使用某些标准化的技术和方法学。术语软件工程将被应用来表示对这些技术的学习和使用。尽管问题本身以及解决这些问题的技术常常是变化的，但是软件开发总是至少包括以下几个阶段：n 问题分析和需求规格说明：对问题进行分析，然后制定一个问题的需求规格说明。n 设计：设计出一个解决问题的计划。n 编码：使用某些编程

3、语言来实现上一步的计划，产生一个程序，同时，对某些问题来说，还可能产生一个或多个库。n 测试、运行和调试：测试程序，去除错误（缺陷）。n 维护：如果必要，程序将被升级和修改，以跟上时代发展和/或满足用户的要求。不过，从一个软件开发过程模型到下一个软件开发过程模型，这些阶段的名字和数量以及如何执行它们有可能会发生变化。一种最早的软件开发策略是瀑布模型，如图1.1所示。这个模型是通过顺序执行前面的每个阶段来构成的；当每一步骤完成后，开发过程就转移到下一个步骤。图1.1尽管这个软件开发模型已经被广泛地使用，但还是有它的缺点，其中最严重的一条在于，如果想回到前面的阶段并进行某些修改，将是非常困难的。实

4、际应用中，可能需要从任何一个阶段都能够回到前面某个阶段，如图1.2所示。图1.2这样，很多不同的新方法被开发出来，包括如下的这些：n 原型模型：创建了一个原型（最终系统的一个早期近似）。接着根据需要不断重复地评估并修改这个模型，直到得到一个可以接受的版本，从这个版本可以开发出完整的系统或产品。这是发生在开发人员和用户之间的一个试用并检验错误的重复过程，特别适合于实现不能详细了解所有需求的情况。n 螺旋模型：这些方法综合了原型模型和瀑布模型的特点，主要用于大型的复杂系统。首先开发出系统的一个初步设计，并根据这个设计创建第一个原型。这个结果通常是一个按比例缩小的系统，只是近似刻画了最终系统的特性。

5、这个过程被重复下去，更好地接近最终系统的原型被不断开发出来，直到用户满意为止。这样就开发出了最终的系统。n 敏捷模型：如它的名字所揭示的，这些方法根据需要进行适应和修改。它的基本原则包括以下这些： 鼓励需求中的变化，即使延迟到开发阶段。 运转软件是开发过程的主要评估手段。不断地将运行的软件传递给客户。 开发人员和用户应该每天都工作在一起。 通过提供所需的环境和支持来激励开发人员，并相信他们能完成工作。 面对面交流是在开发人员之间传递信息最高效也最有效的方法。一种得到极大关注的敏捷方法是极限编程（extreme programming，XP）。开发人员结成对子进行代码的编写和测试，随着项目的开发

6、将代码集成到设计结构中，团队的成员之间经常进行面对面的交流。由于这不是一本软件工程方面的书籍，所以我们不会详细描述这些不同的软件开发方法，也不会特别关注其中某一种方法。当然，在本章中，我们将关注前面列出的软件开发的5个方面。我们将演示这些阶段，并描述软件开发者们要面对的一些问题和复杂因素以及他们用来解决这些问题和复杂因素的一些技术。1.1 问题分析和需求规格说明图1.3（a）中的作业表是程序设计入门课程中给出的最典型的编程问题。在这样的课程中，练习和问题往往都非常地简单并且能够清楚地陈述。这样常使得能够非常直接地描述解决这些问题的程序的行为：这个函数应该接收表示财政补助增长百分比的一个量，将被

7、修改的学生财政补助记录的编号，以及包含这些记录的一个数组。接着它应该通过按照给定的百分比增加每个记录中所有的财政补助奖金，从而更新这些记录。这样的一个描述也称为这个问题的一个需求规格说明（或约定）。不过，作为一个软件开发人员，我们能够以一种更形式化的方式编写这个需求规格说明，如下：目的：按照给定的百分比增加存储在一个学生财政补助记录数组中的每个记录的财政补助奖金。前置条件：财政补助记录存储在一个学生财政补助记录数组中，每个记录包含一个学生的身份标识号码、姓名、财政补助奖金数量，以及这些奖金的一个列表（每个奖金包含财政补助的来源，以及补助的数额）。后置条件：数组中的每个记录都被更新，按照给定的百

8、分比增加了财政补助奖金的 数额。前置条件描述了在一个程序单元一个程序或子程序（一个C+函数，一个Java方法，一个Fortran子例程，一个Pascal过程等）或一系列程序单元被执行之前的处理状态。通常，这都是为一个程序单元所做的假设，常常是对合法输入构成或接收值的一个或多个限制。以一种相似的方式，后置条件描述了在程序单元执行之后的处理状态。但是，对于现实世界中的绝大多数问题，如图1.3（b）中备忘录所演示的，制定一个需求规格说明并不是如此简单如此直接的。对这类问题的最初描述往往都是含糊和不准确的。提出问题的人往往并没有很好地理解问题本身，也不知道该如何去解决问题，或者不知道计算机到底具有什么

9、样的能力以及有哪些限制。形成一个解决问题所需要的行为的描述将会花费相当的时间和努力：提出问题、收集信息、澄清含糊的地方等。图1.3例如，形成需求规格说明的第一步的一项任务就是给出问题的输入的一个完整精确的描述，有哪些可用的信息可以用来解决问题。问题的陈述中往往包含不相关的信息条目，所以必须决定哪些条目对于解决问题是有用的。通常，还必须提出一些额外的问题。例如，对于每个学生来说，有哪些信息是当前可用的？如何访问这些信息？在程序执行的过程中，用户将输入哪些数据？对解决问题需要什么样的分析还要决定需要哪些输出，也就是说，为了解决问题必须产生哪些信息。要决定这个，可能必须要回答很多问题才行。例如，在向

10、FFAO提交的报表中必须包含哪些内容？这些报表必须要一个特定的格式吗？必须要生成相似的报表以提供给其他一些政府部门或者大学的院系部门吗？需要准备报表以邮寄给每个学生吗？计算机中的学生记录文件必须要更新吗？在问题的需求规格说明完备以前，可能还会需要额外的信息。有哪些硬件和软件资源可用？性能需求如何？例如，需要什么样的反应时间？软件运行于其中的应用的关键性程度如何？如果要求提供无故障性能要求，那么软件必须带有正确性证明吗？软件以什么样的频率被使用？用户会是有经验的老手还是没有经验的新手，如果是新手，软件必须界面特别友好并且特别健壮吗？对某些问题，必须根据计算机解决方案的可行性来做出决定。设计一个在

11、给定输入上执行所要求的处理以获取期望的输出的软件是否可能？如果可能，那么这是经济可行的吗？如果以人工方式来解决问题是否更好？这个软件需要多长时间才可用？它的预期的生命周期是多长？如果计算机辅助解决方案被决定是可能的而且是划算的，那么问题的需求规格说明就变成了指导软件开发的蓝图，并且是用来检查最终的产品是否确实解决了问题的标准或者说基准。因此，这个需求规格说明必须是完整的、一致的，并且是正确的。当按照合同为一个公司或者机构开发软件时，有可能会有必要争论软件确实是（没有）按照需求规格说明中所描述的那样工作的，而且这种争论有可能是在法庭上进行的。在这种情况下，需求规格说明必须被陈述得非常准确，因此，

12、一系列的形式化方法，例如Z，VDM（维也纳开发方法，Vienna Development Method），以及Larch，被开发出来制定需求规格说明。这些方法通常会在更高级的软件工程课程中学习，而在本书中，问题的需求规格说明会在一定程度陈述得不那么形式化。1.2 设计当给定一个问题的需求规格说明以后，就必须制定一个计划来开发解决这个问题的一个程序或者一个由模块、库和程序构成的系统。这个设计阶段是整个软件开发过程中最具挑战性的一个阶段。因为计算机并没有天生的解决问题的能力，在计算机的帮助下制定一个解决问题的计划需要程序员的想象力和创造力。在过去一段时间里有不同的设计方法被开发出来，这里将阐述其中

13、的两种：自顶向下设计和面向对象设计（OOD）。每种方法中的主要思想都是模块化，也就是，分别考虑问题的不同方面，然后再将这些方面结合在一起解决原始的问题。它们的区别在于如何实现模块化。1.2.1 自顶向下设计在入门性质的程序设计课程中编写的程序很少超过数百行，而实际应用中开发的软件常包括成千上万行的代码，在某些情况下，还可能达到数百万行。在开发这样的系统时，通常不可能在一开始就看清楚或预见到整个问题的一个完全解决方案。一种流行的处理这种问题的方法是自顶向下，这种方法将原始问题划分成更简单的子问题，每个子问题可以被单独考虑。一些或全部这些子问题可能仍然相当复杂，这个模块化的过程可以重复地应用到这些

14、子问题上，直到所获得的子问题都能够被解决为止。这些问题的解决方案就组成了解决原始问题的系统。作为一个简单的说明，再次考虑图1.3（b）中的财政补助问题。回忆一下，由奖学金和财政补助办公室副主任提出的对问题的陈述相当的含糊，仅仅提到了必须维护所有当前接收财政补助的学生的精确记录，以及必须向FFAO（Federal Financial Aid Office，联邦财政补助办公室）提交正规报表。这个大问题的一些很明显的子问题如下：（1）获取学生记录。（2）处理这些记录。（3）准备报表。我们可以使用图1.4中的结构图刻画这个模块化过程。图1.4典型地，这些第一层子问题中的某个或某些仍然很复杂，所以必须被

15、再划分成更小的子问题。例如，在和奖学金以及财政补助部门的职员商量之后，我们可以发现有一些所需的信息来自于财政补助办公室维护的学生记录，而其他信息来自注册办公室的学生记录。所以第一个问题被划分成两个子问题。相似地，处理记录问题也可以被分成三个子问题：提取一个学生的财政补助记录，从用户那里读取对这个记录的更新，以及接着修改这个记录，如图1.5所示。图1.5当然，部分或所有这些第二层的子问题还可以被划分成更小的子问题。例如，修改一个记录可能牵涉到在一系列记录中查找这个记录，接着使用用户输入的更新信息来修改这个记录，如图1.6所示。图1.6可以为更多层的精化持续这个过程，直到每个子问题都足够简单，为它

16、设计一个解决方案是相当地容易和直接。这个解决方案由数据的存储结构和处理数据的算法构成。例如，对于查找问题，待查找的学生记录集合可以被存储在一个数组中，并且按照这些记录中的关键字段（例如，学生的身份标识号码）升序排列，而算法可以是每个程序员的工具箱中都有的标准折半查找算法（参见1.4节）。1.2.2 面向对象设计另一种随着面向对象编程的普及越来越普遍的设计方法是面向对象设计（OOD）。自顶向下设计主要关注解决问题必须执行的任务以及执行这些任务的算法，与之相比，OOD主要关注问题中的“实际对象”。这里模块化主要是通过确认一系列的对象来实现的，每个这种对象都是由数据和在数据上的操作构成的，可以建模实

17、际对象，并互相交互从而解决问题。例如，在图1.3的财政补助问题中，一个中心对象是财政补助奖金。它可以由下面的数据项构成：数额、来源（例如，奖学金、捐赠、贷款等）、接收这个奖的资格、颁发这个奖的时间长度，如此等等。而操作可以包括提取数额、来源、资格、时间区间；显示数额、来源、资格、时间区间；修改数额、来源、资格、时间区间。另一个中心对象是由财政补助办公室维护的学生记录。它可以存储一个学生的相关信息，例如，身份标识号码、姓名、地址、年级以及所获得的一个或多个财政补助奖金。在这个数据上的操作可以包括提取并显示身份标识号码和学生的名字，提取并显示财政补助奖金，修改这些奖金，添加新的财政补助奖金，删除某

18、些财政补助奖金，如此等等。还有一个对象是由注册办公室维护的学生记录；它也具有特定的数据成员和操作。同一类型的对象的集合被称为一个类，每个特定的对象被称为这个类的一个实例。例如，财政补助奖金集合构成了一个类，可以称之为FinancialAidAward，而每个特定的财政补助奖金都是这个类的一个实例。相似地，所有的学生财政补助记录构成了一个类，可以称之为StudentAidRecord；Mary Doe的财政补助记录是这个类的一个实例。而注册办公室的学生记录构成一个类，可以命名为StudentRegistratrionRecord。在面向对象设计和编程中，单词对象指类的一个实例；即，一个类型为某个

19、类的实体。每个对象都具有两个部分：存储数据的数据成员和在数据上操作的函数成员；我们称对象封装了它的数据和在这些数据上的操作。除了封装性，面向对象编程还具有其他两个特性：n 继承性：一个类（称为派生类或子类）可以重用另一个类（称为基类或父类）的所有属性和操作。n 多态性：一个对象可以在不同时间表现出不同形式的行为。我们将在后续章节中详细考察OOP的这些属性，在那里将了解它们如何能够将OOP扩展到大问题中，对于这些问题，可以封装基类对象的共同性质，并在从基类派生出的类中重用这些性质。我们将使用一个简化的FinancialAidAward类来说明封装性。每个FinancialAidAward对象将具

20、有两个数据成员，将它们命名如下：n 一个实型值amount。n 一个文本串source。它还具有执行前面列出的操作的函数成员：n getAmount()：访问amount数据成员，返回存储在那里的实型值。n getSource()：访问source数据成员，返回存储在那里的文本串。n display()：在屏幕上显示存储在source和amount数据成员中的值。n setSource()：修改source数据成员。n setAmount()：修改amount数据成员。（在函数成员的名字中使用圆括号以将它们和数据成员区分开来。）我们可以使用如下的一幅图刻画一个FinancialAidAward

21、对象。FinancialAidAwardamountsourcegetAmount()getSource()display()setAmount()setSource()上图是通用建模语言（Unified Modeling Language，UML）中使用的类图的一个简单形式，UML是一种在面向对象设计中使用的可视化建模语言，它正变得越来越流行。注意类的名字位于最顶层的部分，数据成员位于第二部分，而函数成员位于第三部分。在UML中，还可以在一个类图中提供关于这个类的数据成员的更多信息，例如n 它们是否是公有的（+）：在类的内部和外部都可以访问它们。私有的（）：只能在类的内部访问它们。n 它们的

22、类型（包括整数、浮点数、字符串以及布尔型）。n 一个默认值。关于每个函数成员的更多信息也可以被包含进来：n 对它的访问类型：公有的或私有的（如对数据成员的描述）。n 函数的形参以及形参的类型。n 函数的返回类型（如果它返回一个值）。例如，FinancialAidAward类的一个更完善的类图如图1.7所示。在图中还给出了StudentAidRecord的类图。箭头表示一个StudentAidRecord包含一个FinancialAidAward对象数组。在本书中，将使用类似于这些UML类图的图形来定义ADT（抽象数据类型）。图1.7除了类图以外，UML还提供其他的图形元素来描述面向对象设计，包

23、括n 对象图：表示类的实例。n 使用情况图：从用户角度描述系统的行为。n 状态图：说明系统可能处于的不同状态，以及从一个状态向另一个状态的转移。这些元素和其他图形元素组合起来提供被设计系统的图形集合。因为本书主要关注抽象数据类型以及使用数据结构实现它们，而不是设计大型系统，所以我们将把对UML特性的详细学习留给软件工程课程（参见本书的Web站点以获取更多关于UML信息的一些来源）。1.2.3 小规模设计对于通常在程序设计入门课程中布置的编程项目这样的小规模问题，可以使用类似于对大规模问题所描述的方法来设计解决方案。像自顶向下设计所产生的模块化包括确认执行特定任务的程序单元，例如C+的函数，以及

24、使用某些高层的程序单元控制它们的执行，并使得main函数位于最顶层。这里假设这些工作已经被完成了，希望设计一个子程序（一个C+函数，一个Java方法，一个Fortran子例程，一个Pascal过程等）来解决一个小问题。特别地，将考虑图1.3（a）中的编程作业，其中要设计一个C+函数来修改学生财政补助记录。我们的方法属于关注问题对象的一类，如面向对象设计所做的。数据类型问题中每个数据元素的最重要的属性就是它的类型，这决定了它可以具有什么样的值，可以对它进行什么样的操作，以及这些操作将产生什么样的结果等。在你的第一个程序设计课程里，将学习这个程序设计语言中所提供的用于单独实体的简单数据类型。例如，

25、在C+中，对于123这样单独的整数使用int（或者它的变形，例如unsigned、short int以及long int）；对于3.98这样单独的实数值使用double（或者float、long double）；对于A这样单个字符使用char；对于true或者false这样单独的逻辑值使用bool；对于单独的枚举值使用enum；以及对于单独的内存地址使用一个指针来存储（所有这些数据类型将在第2章中回顾）。不过，有些对象是一系列的值，而绝大多数编程语言提供结构化数据类型（也称为数据结构）来存储这些成系列的值。其中最普通的，也应该已经熟悉的一种是数组（将在3.2节中回顾数组）。几乎所有高级程序设计

26、语言都提供数组，并且还可能提供数组的更加现代化的扩展，例如，C+中的valarray和vector（参见第9章）。数组被用来组织类型相同的数据元素；例如，图1.3中财政补助编程作业中描述的数组被用来存储财政补助对象。然而，财政补助对象的类型必须是一个能够存储不同类型元素的结构：一个表示数额的实型值，一个表示财政补助来源的字符串。相似地，学生财政补助对象的结构必须存储一个整数身份标识号码，一个表示学生名字的字符串，以及一个财政补助对象。绝大多数编程语言确实都提供一种机制用于创建这种类型。例如，C+中的结构和类，Java中的类，Fortran中的结构，以及Pascal中的记录。本书从第4章开始的一

27、大部分，都用于详细学习如何设计和创建这些类型（被称为抽象数据类型（ADT）以及如何使用C+中提供的数据类型来实现它们。算法在设计过程中，除了对象的数据成员，还必须考虑在这些数据上的操作。例如，对于财政补助问题，我们确认出的操作包括提取财政补助来源和数额，设置来源和数额为某个特定值，以及显示财政补助。在1.3节中将看到如何使用预定义的C+操作将这些操作简单地实现为类的函数成员。其他操作将需要一些更多的工作。例如，图1.3（a）中编程作业的另一个操作是更新学生财政补助记录数组。因为这不是C+中的一个预定义的操作，所以不得不自己实现这个操作，也就是设计一个函数来执行它。在1.1节中我们为这个函数形成了一个需求规格说明，规定了这个函数的目的，在函数使用之前必须具有的前置条件，以及函数必须产生的结果的后置条件。下面必须开发一个操作序列，称为一个算法，来产生这个结果。例如，下面是更新学生财政补助记录算法的第一个版本：对于每个学生财政补助记录，做以下工作。