第六章软件开发技术

　　学习目标：
　　1．理解软件的功能与开发流程 。
　　2．了解计算机程序设计的基本概念，程序设计语言的发展；数据结构和算法在程序设
　　计中的作用；软件工程的定义、主要内容和过程；软件开发常用的方法和技术
　　计算机是可以帮助人们完成工作的工具。但是，它又和我们见到的普通刀、锯有所不同，
　　计算机是一种特殊的工具，当计算机要执行指定的任务时，是通过执行内部的程序完成的。
　　计算机程序最基本的功能是把原始的数据转变成有意义的信息。程序指导计算机获取原始数
　　据，然后将数据转换为对于最终用户有用的信息。但是，程序的编写并不是简单的事情，学
　　习编程需要一段时间，需要懂得如何把你想要叫计算机做的事情教给计算机去做。这就需要
　　掌握和计算机交流的语言，需要学习有关程序设计的知识和方法。本章我们针对软件开发涉
　　及的主要技术进行介绍。
　　第一节 程序设计语言与解题过程
　　前面我们已经知道，计算机包括硬件系统和软件系统，硬件系统好比人的躯体，软件系
　　统好比人的灵魂。为了让计算机做更多的事，不仅要为它配备一套性能良好的硬件，还要为
　　其设计出一套套解决各式各样问题的软件，即计算机程序。
　　要设计出一个好的程序，首先必须了解利用计算机解决实际问题的过程，其次必须掌握
　　程序设计的基本技术，最后要熟练掌握某种程序设计语言。
　　一、计算机如何解题
　　我们看到，计算机可以画图，可以放影碟，可以玩游戏，诸如此类，不一而足。这是因
　　为计算机内部使用了不同的程序，才可以处理不同的问题。
　　1．程序
　　＂程序＂一词，从广义上讲可以认为是任何行动的方案或步骤，例如一场大型演唱会的
　　程序，大学新生报到的程序，电脑组装的程序等等。
　　计算机程序同日常生活中的程序含义基本上是相同的，表示的也是处理事务的顺序和步
　　骤。由于组成计算机程序的基本单位是指令，因此，计算机程序就是按照工作步骤事先编排
　　好的、具有特殊功能的指令序列。
　　使用计算机解决问题与人解决问题类似，必须将解题过程分为若干步骤。为了让计算机
　　代替人脑的部分功能，要教会计算机按照人所规定的步骤和顺序对数据进行处理。但用计算
　　机解题有其自身的特点。
　　首先，人类凭借自然语言进行思维。所谓自然语言就是人所使用的语言。由于国家或民
　　族不同，他们所使用的语言也是不同的，例如绝大多数的中国人使用汉语，英美国家的人使
　　用英语，俄罗斯人使用俄语，如此等等。计算机进行＂思维＂也要通过语言，这就是计算机
　　语言。控制计算机解题过程的算法必须以计算机能够＂读懂＂的形式表示出来。这种以计算机语言描述的算法就是程序。
　　其次，人解决问题的过程是一个＂自适应＂和＂自动调节＂的过程。也就是说，人在解
　　决问题之初，只要在脑海中形成一个初步的、＂模糊＂的方案，就可以着手处理；在处理过
　　程中，若发现方案有不妥或错误，可随时调整，直至问题解决。而计算机解决问题是一个完
　　全＂机械＂的过程，也就是说，计算机在解题前，必须输入一个包含完整的、确定的方法和
　　步骤的程序，不允许有丝毫的含糊；解题过程开始之后，严格按确定的方法和步骤执行，不
　　可能作任何修改；如发现错误，执行过程只能被迫停止，需修改程序，从头再来。
　　因此，确切地说，所谓程序，是用计算机语言对所要解决的问题中的数据以及处理问题
　　的方法和步骤所做的完整而准确的描述，描述的过程就称为程序设计。对数据的描述就是指
　　明数据结构形式；对处理方法和步骤的描述也就是算法设计。因而，数据结构与算法是程序
　　设计过程中密切相关的两个方面。从这个意义上讲，程序是建立在数据结构基础上使用计算
　　机语言描述的算法。发明 Pascal 语言的著名计算机科学家 Wirth 教授关于程序就提出了一个
　　著名公式：程序 数据结构+算法。这个公式很形象地说明了程序设计的主要任务。
　　2．程序设计过程
　　程序员和建筑师、作曲家以及作家一样，是富有创造性的人。有如建筑师通过图形、文
　　字构筑起高楼大厦，作家运用文学手段描写人物的个性和特征，作曲家用跳动的音符谱写动
　　听的旋律，程序设计者通过调动各种程序设计手段，先形成程序框架，然后翻译成最初的程
　　序版本，再反复修改，最后形成一个完美的程序。
　　对于程序设计的初学者来说，首先要学会设计一个正确的程序。一个正确的程序，通常
　　包括两个含义：一是书写正确，二是结果正确。书写正确是指程序在语法上正确，符合程序
　　语言的规则；而结果正确通常是指对应于正确的输人，程序能产生所期望的输出，符合使用
　　者对程序功能的要求。程序设计的基本目标是编制出正确的程序，但这仅仅是程序设计的最
　　低要求。
　　一个优秀的程序员，除了程序的正确性以外，更要注重程序的高质量。所谓高质量是指
　　程序具有结构化程度高、可读性好、时空效率高、可靠性高、便于调试维护等一系列特点。
　　毫无疑问，无论是一个正确的程序，还是一个高质量的程序，都需要通过精心设计才能达到
　　预期的目标。
　　对复杂程度较高的问题，想直接编写程序一般是不现实的，必须首先从问题描述入手，
　　经过对具体问题的分析，抽象出合适的数学模型并设计合适的算法，然后编写程序、调试和
　　运行直至得到正确结果。这一完整的过程称为程序设计。
　　那么，如何进行程序设计呢?程序设计的基本过程一般包含以下几个步骤：
　　(1)确定要解决的问题。接到任务后，首先对要处理的对象进行调查，了解其要求。然
　　后确定哪些任务由计算机完成，哪些任务手工完成，并对计算机要完成的任务，详细地给出
　　原始数据、处理后的结果及处理功能。
　　(2)分析问题，建立数学模型。由于程序是以数据处理的方式解决客观世界中的问题，
　　因此在程序设计之初，首先应该将实际问题用数学语言描述出来，形成一个抽象的、具有一
　　般性的数学问题，从而给出问题的抽象数学模型，然后制定解决由该模型所代表的数学问题
　　的算法。数学模型精确地阐述了问题所涉及的各种概念、已知条件、要求结果，以及已知条
　　件与要求结果之间的联系等信息。数学模型是下一步确定算法的基础。
　　(3)选择计算方法。根据特定的数学模型，选择适合计算机解决问题的方法。当同一问
　　题有多个解决方案时，可根据计算的速度、求值的精度、计算要求与计算机硬件性能的关系
　　进行选择。数学模型和算法的结合给出了问题的解决方案。
　　(4)确定数据结构和算法。解决方案确定后，要考虑数据的组织形式，也就是数据结构，
　　并设计与之相适应的算法。然后对算法进行描述。算法的初步描述可以采用自然语言，然后逐步转化为流程图或其他直观方式。要求描述方式简单明确，能够明显地展示设计者的思想，
　　是进行程序调试的重要参考。
　　(5)绘制流程图。根据已确定的算法，画出流程图或结构化流程图。这能使程序员保持
　　思路清晰，减少编程的错误。
　　(6)编写程序。使用计算机系统提供的某种程序设计语言，将已设计好的算法表达出来，
　　这个过程称为程序编制(编码)。编写的程序一般需要经过反复调试、修改才能得到可以运行
　　且结果＂正确＂的程序。
　　这一步应注意的是，要选择一种合适的语言来适应实际算法和所处的计算机环境，并要
　　正确地使用语言，准确地描述算法。
　　(7)调试并测试程序。调试程序就是对送入计算机的程序进行排错、试运行的过程，调
　　试的结果是得到一个能正确运行的程序。程序编写完成后必须经过科学的、严格的测试，才
　　能最大限度地保证程序的正确性。同时，通过测试可以对程序的性能作出评估。
　　(8)整理资料，交付使用。程序调试通过后，应将有关资料进行整理，编写程序使用说
　　明书，交付用户使用。
　　图 6.1 程序设计的流程。
　　由此可见，程序设计涉及四个方面的问题：数据结构、算法、编程语言以及隐含在程序
　　设计过程中的设计方法。这四个方面的知识都是程序设计人员所必须具备的，其中算法是至
　　关重要的一个方面。图 6.1 描述了程序设计的流程。
　　3．程序设计技术与基本原则
　　综上所述，程序设计过程是算法、数据结构和程序设计语言三者相结合与统一的过程。
　　要设计出一个好的程序，必须掌握程序设计的基本技术，熟练掌握某种程序设计语言。
　　对问题和算法的最初描述，无论是形式上还是内容上，离最终以计算机语言描述的算法
　　(程序)都有相当大的距离。如何从问题描述入手构造出解决问题的算法，如何组织好计算机
　　处理的数据，如何设计出结构和风格良好的高效程序，这涉及多方面的理论和技术，它们形
　　成了计算机科学的一个重要分支——程序设计方法学。
　　对于规模不很大的问题，程序设计的核心是算法和数据结构，只要构造出解决问题的高
　　效算法和数据结构，则完成剩下的任务已经不存在太大困难。如果问题规模大、功能复杂，
　　则有必要将问题分解成功能相对单一的一些小模块分别实现。这时，程序的组织结构和层次
　　设计越来越显示出重要性，程序设计方法将起到重要作用。在这种情况下，程序设计过程实
　　际上成为算法、数据结构以及程序设计方法学三个方面相结合与统一的过程，这三个方面被
　　称为程序设计三要素。为了编写出高质量的程序，必须首先明确评价程序质量性能的如下一些准则：
　　(1)正确性：指程序具备且只具备程序设计规格说明书中所列举的全部功能。它是判断
　　程序质量的首要标准。
　　(2)可靠性：指程序在多次反复使用过程中，保持不失败的概率。
　　(3)简明性：要求程序简明易读。
　　(4)有效性：程序在计算机上运行需要使用一定数量的计算机资源，如 CPU 的时间、存
　　储器的存储空间。有效性就是在一定的软、硬件条件下，程序综合效率的反映。
　　(5)可维护性：程序的维护分为校正性维护、适应性维护和完善性维护。软件的可维护
　　性关系到程序的可用性，应特别予以关注。
　　(6)可移植性：程序与其所完成的任务有关，也与它的运行环境有关。程序的开发应尽
　　可能远离机器的特征，以提高它的可移植程度。
　　由于程序类别以及应用领域的不同，上述判别准则在评估程序整体性能质量时所占的比
　　重会有所不同，需要具体问题具体分析。
　　由此可知，程序设计涉及到多方面的内容。有些初学程序设计的人认为，进行程序设计
　　就是用计算机语言写出源程序，其实这仅仅是完成了程序的编码。事实上程序设计从问题分
　　析就开始了，它包括了从问题分析直到取得正确结果这样一个完整过程。忽视编码之前的阶
　　段，即不讲究问题的定义和分析及数据结构和算法的设计，其结果很可能是＂事倍功半＂，
　　很难对付日益复杂的程序设计问题，难于满足高质量程序的基本标准。
　　二、人和计算机交流的语言――计算机语言
　　语言是交流思想、传达信息的工具。要叫计算机做人交给的任务，就需要使计算机理解
　　人所设计的算法，这就需要用计算机能够理解的语言――计算机语言来描述算法。计算机语
　　言是人们设计的专用于人与计算机交流、进而计算机能够自动识别的语言。计算机语言描述
　　的算法就是计算机程序。
　　1．计算机语言的分类
　　程序设计语言是人与计算机之间进行信息交换的工具。人们利用程序设计语言编制程序，
　　然后送入计算机，计算机对程序进行解释或翻译，识别人的意图并按人的意图进行处理，达
　　到解决问题的目的。随着计算机技术的飞速发展，人们总是希望设计出来的语言方便使用，
　　于是不同风格的程序设计语言，从最低级的机器语言到汇编语言，再到高级语言，以及更高
　　级、智能化的语言不断涌现。
　　计算机语言作为在计算机上实现算法的工具，其语法应该满足能简洁明了地描述算法结
　　构、数据、控制操作流程等各方面的需要。从最初的机器语言发展到今天各种各样的高级语
　　言，主要原因是计算机硬件技术的飞速发展，使得计算机能够处理的问题规模和计算机的应
　　用领域不断扩大。此外也由于人们一直在追求更良好、优美的编程风格。这就使得计算机语
　　言的抽象程度越来越高，描述能力越来越强，越来越向专业化或通用化两个不同方向发展，
　　程序风格也越来越接近自然语言，使程序设计过程也越来越接近人类的思维过程。
　　几十年来，程序设计语言发展迅速，出现了各种各样的程序语言。
　　（1）按语言类型分类
　　按语言类型分类，程序设计语言有机器语言、汇编语言和高级语言。
　　机器语言 ：人们在设计计算机硬件时就为计算机设计了一些基本操作，每一种基本操作
　　叫一条指令，这种指令的功能用计算机的逻辑电路可以直接实现。计算机能直接执行的指令
　　叫机器指令。最初的程序设计直接使用机器指令，也称为机器语言。使用机器指令进行程序
　　设计要求设计者具有深入的计算机专业知识，对机器的硬件有充分的了解。这种程序的可读
　　性差，而且由于不同机器的机器指令不同，因此程序的可移植性差，所编写的程序只能在相同的硬件环境下使用，大大地限制了计算机的应用。
　　机器语言编写的程序是由二进制代码组成的序列。可以直接访问和使用计算机的硬件资
　　源。计算机能直接识别并执行这种程序，效率高，这是它的优点。
　　但机器语言处理问题的方式与人们的习惯有较大差距，例如使用机器语言实现两个整数
　　加法，首先要将一个加数放入一个被称为累加器的运算器中，然后将另一个加数与累加器的
　　内容相加(运算结果在累加器中)，最后再把累加器中的内容放入存放运算结果的存储单元中。
　　很显然，用机器语言写出这个过程与直接书写 x=a+b 是大相径庭的。
　　汇编语言 ：由于用机器语言编写程序非常不方便，难以记忆各种不同的二进制形式，因
　　此提出将每一条机器语言指令用一串有比较清晰含义的符号来代替，用符号进行程序设计，
　　这样的语言称为符号语言或汇编语言，其符号常常用英语的动词或动词的缩写表示。用汇编
　　语言编写的程序称为汇编语言源程序。
　　汇编语言源程序与机器语言源程序相比，阅读和理解都比较方便，但计算机却无法识别
　　和执行了。由于汇编语言的符号命令和机器指令有很好的一一对应关系，于是人们设计了汇
　　编程序，汇编程序的任务是自动地将用汇编语言编写的源程序翻译成计算机能够直接理解并
　　执行的机器语言程序，即目标程序。再通过连接程序将目标程序中所需要的一些系统程序片
　　段(如标准库函数等)连接到目标程序中，形成可执行文件执行，获得所希望的结果。
　　汇编语言除了可读性比机器语言好外，同样也存在机器语言的缺点，尤其是描述问
　　题方式与人类习惯相差太远，而且通常仍要求编程者对计算机硬件有深入的了解。
　　高级语言： 针对汇编语言的缺点，通过进一步抽象，产生了高级语言(也称为通用程序
　　设计语言)。与汇编语言等低级语言相比，高级语言的表达方式更接近人类自然语言，对各
　　种公式的表示也近似于数学公式，具有很高的可读性。而且高级语言不像汇编语言那样直接
　　针对计算机硬件编程，因此不依赖于计算机的具体型号，具有良好的可移植性。虽然高级语
　　言不如汇编语言效率高，但一般都有广泛的应用范围。而且，一条高级语言语句的功能往往
　　相当于很多条汇编语言的指令，程序编制相对比较简单。因此，在工程计算、定理证明和数
　　据处理等方面，人们常用高级语言来编制程序。
　　用高级语言编写的程序称为高级语言源程序，同汇编语言源程序一样，计算机也不能理
　　解和执行，于是，人们设计了各种编译程序和解释程序，用于将高级语言源程序翻译成计算
　　机能直接理解并执行的二进制代码的目标程序。
　　（
　　2）按用户要求分类
　　按用户要求，程序设计语言有过程式语言和非过程式语言之分。
　　过程式语言，也叫命令式语言或强制式语言，它是通过指明一系列可执行的运算及运算
　　的次序来描述计算过程的语言。过程式语言的主要特征是，用户可以描述一系列可顺序执行
　　的运算，以表示相应的计算过程。例如，FORTRAN，ALGOL60，COBOL，PASCAL，C
　　等都是过程式语言。
　　凡是不必指明计算过程的语言，都是非过程式语言。例如结构化查询语言 SQL，只要
　　用户给出查询范围、查询条件和查询对象，不必指明＂如何去查询＂的具体操作系列，便可
　　自动获得所需的查询结果。
　　对普通用户来说，在大多数情况下使用的是高级语言。微机中常用的高级语言主要有 3
　　类：面向过程的程序设计语言、面向问题的程序设计语言和面向对象的程序设计语言。
　　面向过程的程序设计语言 。传统的程序设计高级语言几乎都是面向过程的程序设计语
　　言，在程序中需要将任务的每个步骤逐一编写出来，对问题的描述接近于问题求解过程，易
　　于掌握和书写。经常用的这类高级语言有 BASIC、FORTRAN、PASCAL、C 等。
　　面向问题的程序设计语言 。是为了易于定义和解决某些问题而设计的一类与机器无关的程序设计语言，其主要有点是减少了程序员编写程序的工作量。例如，报表语言、判定语
　　言、机床控制专用语言、医学诊断专用语言、电路设计专用语言等，都是面向问题的程序设
　　计语言。
　　数据库语言属于面向问题的程序设计语言，编写程序时只要写清楚要调用数据库的什么
　　功能或对数据进行哪种操作即可，至于具体如何完成这种功能或操作，则由语言本身提供。
　　数据库语言提供数据（记录)的存储、管理和维护，以及诸如检索、插入等各种高效的常见
　　数据库操作，比较适用于管理信息系统。目前广泛使用的数据库语言有数据库查询语言 SQL
　　等。SQL 不仅具有丰富的数据查询功能，而且具有数据定义和数据控制功能，集查询、DDL、
　　DML 和 DCL 于一体，充分体现了数据库语言的特点和优点。
　　面向对象的程序设计语言 。传统的高级语言，用户不仅要告诉计算机＂做什么＂，而
　　且要告诉计算机＂怎么做＂，也就是把每一步的操作事先都设想好，用高级语言编成程序，
　　让计算机按指定好的步骤去执行。近年来出现了＂面向对象＂的程序设计语言。所谓对象是
　　数据及相关方法的软件实体，可以在程序中用软件中的对象来代表现实世界中的对象。
　　面向对象语言提供了一系列语法，使编程者能够方便地按照人类思维的最一般规 律，
　　以与对所研究对象认知程度相同步的方式开发软件，是一种全新风格的语言。
　　目前计算机上流行的这类程序设计语言有 JAVA、C++、VB、VC、Delphi 等。
　　（
　　3）按应用范围分类
　　按应用范围，程序设计语言有通用语言和专用语言之分。
　　目标非单一的语言称为通用语言。如 FORTRAN，ALGOL60，COBOL，PASCAL，C
　　等都是通用语言。目标单一的语言称为专用语言，如自动数控程序工具语言 APT，就是专
　　门用于数控机床加工的语言。
　　（
　　4）按使用方式分类
　　按使用方式，程序设计语言有交互式语言和非交互式语言之分。
　　具有人—机交互作用的语言称为交互式语言。利用这种语言编写的程序在执行过程中会
　　向用户随时发出提示，警告等信息，用户可椐此采取相应措施。没有这种功能的语言为非交
　　互式语言。例如，BASIC、APL 就是交互式语言，而 FORTRAN、ALGOL60、COBOL、PASCAL，
　　C 等都是非交互式语言。
　　2．语言处理程序
　　对于用某种程序设计语言编写的程序，通常要经过编辑处理、语言处理、装配连接处理
　　后，才能够在计算机上运行。
　　编辑处理是指计算机通过编辑程序将人们编写的源程序送入计算机。编辑程序可以使用
　　户方便地修改源程序，包括添加、删除、修改等，直到用户满意为止。
　　语言处理程序是把用一种程序设计语言表示的程序转换为与之等价的另一种程序设计
　　语言表示的程序的程序。
　　在计算机软件中经常用到的语言处理程序是把汇编语言或高级语言＂翻译＂成机器语言
　　的翻译程序。被翻译的程序称为源程序或源代码，经过翻译程序＂翻译＂出来的结果程序称
　　为目标程序。
　　翻译程序有两种典型的实现途径，分别称为解释方式与编译方式。
　　（1）解释方式
　　解释方式是按照源程序中语句的执行顺序，逐句翻译并立即予以执行。即由事先放入计
　　算机中的解释程序对高级语言源程序逐条语句翻译成机器指令，翻译一句执行一句，直到程
　　序全部翻译执行完。解释方法类似于不同语言的口译工作。翻译员（解释程序）拿着外文版
　　的说明书（源程序）在车间现场对操作员作现场指导。对说明书上的语句，翻译员逐条译给操作员听；操作员根据听到的话（他能懂的语言）进行操作。翻译员每翻译一句，操作员就
　　执行该句规定的操作。翻译员翻译完全部说明书，操作员也执行完所需全部操作。由于未保
　　留翻译的结果，若需再次操作，仍要由翻译员翻译，操作员操作。
　　（
　　2）编译方式
　　先由翻译程序把源程序静态地翻译成为目标程序，然后再由计算机执行目标程序。这种
　　实现途径可以划分为两个明显的阶段：前一阶段称为生成阶段；后一阶段称为运行阶段。采
　　用这种途径实现的翻译程序，如果源语言是一种高级语言，目标语言是某一计算机的机器语
　　言或汇编语言，则这种翻译程序特称为编译程序。如果源语言是计算机的汇编语言，目标语
　　言是相应计算机的机器语言，则这种翻译程序特称为汇编程序。
　　编译方式类似于不同语言的笔译工作。例如，某国发表了某个剧本（源程序），我们计
　　划在国内上演。首先须由懂得该国语言的翻译（编译程序）把该剧本笔译成中文本（目的程
　　序）。翻译工作结束，得到了中文本后，才能交给演出单位（计算机）去演（执行）这个中
　　文本（目的程序）。在后面的演出（执行）阶段，并不需要原来的外文剧本（源程序），也
　　不需要翻译（编译程序）。
　　正像只懂中文的人与只懂英语的人交谈需要英语翻译，要与只懂日语的人交谈就需要日
　　语翻译一样，对不同的高级语言也需要不同的翻译程序。如果使用 BASIC 语言，需要在计
　　算机系统中装有 BASIC 语言的解释程序或编译程序；如果使用 C 语言，就需要在机器内装
　　有 C 编译程序。如果机器内没有装上汇编语言或高级语言的翻译程序，计算机是决不能够
　　理解用相应语言编写的程序的。相比较，在同样一篇外文文章情况下，逐句翻译比整篇翻译
　　的效率低，但一种语言的翻译程序类型不是由使用者来决定，而是由系统软件的生产者决定
　　的。
　　3. 对程序设计语言的基本要求
　　对自然语言而言，它们是人们在长期生活中自然形成的，无所谓优劣，而对计算机语言
　　来说，它们是人为创造的，就有优劣高低之分了。
　　（1）软件的质量要求
　　由于计算机语言用于编程，形成软件，所以为了讨论计算机语言的优劣，我们先讨论一
　　下对软件的质量要求。对软件可以提出以下 10 条基本要求。
　　①可理解性。主要指软件的用途即软件的功能，软件各部分之间、各子系统之间的分工
　　与相互关系是十分清楚的，当用户按规定调用软件的某部分时，软件应能按用户的要求作出
　　明确的响应，解决用户的问题。
　　②完整性。完整性要求软件自成体系，即解题过程中所需的全部环节（如输入、编辑、
　　分析计算或绘图、输出等)软件应该全部具备。完整也意味着软件的＂健壮性＂，即软件应
　　具有容错能力——自动排除错误和恢复工作的能力。
　　③简明性。简明性要求软件在应用过程中一目了然，知道是否出了问题；问题出在什么
　　地方和怎么解决问题；简明性的另一层含义是指用软件书写的程序有最少的指令行数。
　　④可移植性。可移植性即兼容性。即软件在任一类型的计算机配置下都能方便而有效地
　　操作。广义地谈，应在任何硬件配置和操作系统下都能正常有效地运行。
　　⑤可维护性。一个易于维护的软件产品，为了满足新的要求，应该是很容易修改的。
　　⑥可测试性。可测试性好的软件，能够比较容易地确定测试的准则，对它的技术性能作
　　出评价。
　　⑦人机界面是否友好。提供的界面是否方便，是否有图形化的菜单等。
　　⑧可靠性。主要指在软件整个生命期内，能否按照设计的要求，满意地实现所需要的功
　　能，换句话说，原设计的功能是否能正确实现，运行中会有多少隐藏的错误出现，错误出现的后果是什么，等等。
　　⑨结构性。主要指软件的是模块化的程度，是否符合结构化原则。追求高可靠性、高运
　　行效率可能会使结构性能变差。
　　⑩效率。指完成给定功能需要的资源。资源主要指存储空间，CPU 时间。
　　（
　　2）对程序设计语言的一般要求
　　根据上述对软件质量的 10 项要求，对用以编写、开发软件的语言。可以提出以下基本
　　要求：
　　①用户界面好；
　　②对硬件、软件环境要求低；
　　③对硬件资源的利用程度高；
　　④代码质量高，代码质量依据结构化程度，可读性，易维护性，目标程序的运行速度，
　　可靠性等等；
　　⑤用途广泛(计算、管理、控制……)；
　　⑥容易调用其他软件；
　　⑦自身发展快。
　　如果一种程序设计语言，能在上述 7 个方面都有较好的得分，那就是一种比较理想的语
　　言。
　　第二节 数据结构与算法基础
　　计算机发展初期，主要用于数值计算，处理的是数值数据，数据量小，结构简单，形式
　　统一。随着计算机技术的发展，计算机应用领域的扩大，越来越多的非数值数据需要处理，
　　数据的概念也被大大推广，数字、字符、图像、声音都属于数据的范畴。与数值数据相比，
　　非数值数据的结构比较复杂，其计算机表示也比较麻烦。这时，为数据选择一种好的结构是
　　非常重要的。只有对数据内部的结构关系以及数据在计算机内如何存储和操作进行深入的研
　　究，才能设计出高效可靠的程序，实现对数据的有效处理。而对数据在计算机中的存储和表
　　示的研究产生了数据结构。此外，前面我们已经讲过，利用计算机解决问题时，就要编制计
　　算机程序，而编写程序要依据一定方法。也就是说，编写程序要先有解决问题的算法。算法
　　就是解决问题的办法，是对特定问题求解步骤的详细描述。
　　在这一节里，我们将介绍有关数据结构和算法的基本知识。
　　一、数据结构
　　一个水平很高的厨师，如果不给他好原料或原料乱七八糟，也很难做出色、香、味俱佳
　　的菜肴。对于程序来讲，数据就是原料。程序进行的工作总是以数据为处理对象的。只有将
　　复杂、松散、无组织的数据，按照问题的要求组织好，才有利于设计出简明、高效的程序来。
　　也就是说程序设计离不开数据结构。
　　1. 数学模型
　　前面讲到，用计算机解决实际问题，首先必须抽象出一个适当的数学模型，用这个数学
　　模型能得出该问题的精确或近似解。建立实际问题的数学模型是计算机应用必须首先进行的
　　工作，也是一项很重要的工作。寻求数学模型的实质是分析问题，从中提取决定事物性质或
　　变化规律的关键因素，并找出这些因素之间的关系，再用数学语言加以描述。一个问题是否
　　能用计算机得出解答或得出的解答是否正确，首先取决于数学模型的正确与否。
　　前人在数学模型的建立上已经做了很多工作。例如：求解桥梁结构中应力的数学模型为线性方程组；预报人口增长的数学模型为微分方程；图书馆书目检索的数学模型为带索引的
　　线性表；数据通讯的二进制编码的数学模型为扩充二叉树；城市之间的最优交通线路的数学
　　模型为边带权的图等等。对于那些新出现的或情况发生了变化的复杂问题，建立相应的数学
　　模型仍是一项艰巨的任务。
　　数学模型大致可分为数值计算和非数值计算两大类。许多实际问题抽象的结果是数学方
　　程，可以用解析法求出精确解，或者用模拟法求出近似解。但是，随着科学技术的飞速发展，
　　计算机的应用范围不断扩大，已不再局限于单纯的数值计算，更多地应用于控制、管理及数
　　据处理等非数值计算的处理工作。因此，对于不同的处理对象，要想设计出高质量的程序，
　　就必须研究如何组织数据和处理数据，根据问题的要求及数据元素之间的特性，确定相应的
　　组织存储和操作运算，这些都是数据结构研究的内容。那么到底什么是数据结构呢？
　　2. 数据结构
　　我们首先通过自动查询电话号码这样一个例子来认识数据结构。
　　为了实现电话号码查询，可以按照客户向电信局申请电话号码的先后次序建立一个电话
　　号码表，存储到计算机中。在这种情况下，由于电话号码表是没有任何规律的，查找时只能
　　从第一个号码开始逐一进行。我们也可以把电话号码表根据每个用户姓名的第一个拼音字母
　　的顺序进行排列，这样根据姓名的第一个字母就可以缩小查找范围，从而减少了查找所需的
　　时间。
　　在上述例子中，我们感兴趣的是如何提高查找效率。为了解决这个问题，我们是对待处
　　理的数据进行了一定的排序组织，从而提高了数据处理的效率。
　　再比如我们要设计一个人机对弈的程序。由于对弈的过程是随机的，为了使计算机能灵
　　活对弈，就必须将所有可能发生的情况以及相应的对策都考虑周全。在决定对策时，不仅要
　　看当时的棋局，还要考虑对方的应对以及自己取胜的可能性。因此，计算机操作的对象（数
　　据元素）是对弈过程中每一步的棋盘状态（格局）。数据元素之间的关系由比赛规则决定，
　　通常不是线性的，是一个树型结构。问题要求在一个庞大的树型搜索空间里寻找出比较好的
　　应对策略。这也是一个如何组织存储以及如何进行操作的问题。数据结构就是研究这类非数
　　值处理的问题。
　　下面我们介绍一些数据结构的基本概念。
　　所谓数据，是指客观事物的名称、数量、特征、性质的描述形式(即编码)，是计算机所
　　能处理的一切符号的总称。数据既是计算机加工的对象，又是计算机的产品(计算结果)。
　　例如，利用数值分析方法解代数方程的程序，其处理对象是整数和实数；编译程序或者
　　文字处理程序的处理对象是字符串。因此，对计算机科学来讲，数据的含义很广泛，图形、
　　图象、色彩和声音等都可以通过编码而归于数据的范畴。
　　一般来说，我们对那些单个的孤立的数据并不感兴趣，而着重研究由众多数据元素组成
　　的数据集合，研究集合中数据元素之间存在怎样的内在联系，需要对数据和数据集合进行哪
　　些运算(即对数据进行的处理)，如何提高运算效率等等，这就引出了数据结构。
　　数据结构里包括一批数据，是数据的一个集合。这个集合中的每一个数据个体称为数据
　　元素，它是数据的基本单位。一个数据元素又叫做一个数据结点，简称结点。数据类型是指
　　程序设计语言中所允许的变量的种类，也就是变量可以取的值和可以进行的运算的集合。可
　　以把数据类型看成是在程序设计语言中已经实现了的数据结构。
　　数据元素可以是简单的，只有一个数据项，例如一个数，一个字符，一个名字等；也
　　可以是复杂的，由若干数据项组成，一个数据结点由用来描述一个独立事物的名称、数量、
　　特征、性质的一组相关信息组成。
　　例如，在设计处理学生成绩问题的程序时，有关每个学生的所有数据项构成一个数据
　　结点，可能包括学生的姓名、学号、各科考试成绩等等。在处理库存商品问题时，一个数据结点对应一种商品的相关数据项，包括商品编号和名称、规格、数量、生产厂家、单价、入
　　库日期等。
　　结点集合以及该集合中各结点之间的关系，组成数据的逻辑结构。数据的逻辑结构反映
　　的是数据元素之间的逻辑关系，与数据的存储无关，它独立于计算机。如用户在电话号码表
　　中的先后次序关系。数据的逻辑结构可分为线性结构和非线性结构两大类。线性结构包括：
　　线性表、栈和队列等，其主要特征为各个结点之间＂先后＂有序。非线性结构包括树和图型
　　结构，树型结构的主要特征是结点之间存在着一种层次的关系，每一个结点对应着下一层的
　　多个结点，也就是说，数据元素之间的关系是＂一对多＂的关系。而在图型结构中，任何两
　　个结点之间都可能存在着联系，数据元素之间存在着多对多的关系。
　　数据的存储结构是指数据元素在计算机存储设备中的存储方式。它包括数据本身在计算
　　机中的存储方式，以及数据之间的逻辑关系在计算机中的表示。因此，数据的存储结构是依
　　赖于计算机的。用来存储一个数据结点的存储单元叫做一个存储结点。因为一个数据结点对
　　应一个存储结点，所以存储结点通常也简称为结点，准备用来存储但尚未存储数据的存储结
　　点叫空白结点，或叫空结点、自由结点。数据的存储方式主要有两种：一种是顺序存储方式，
　　逻辑上相邻的数据元素在存储器中也相邻存储；另一种是链接存储方式，逻辑上相邻的数据
　　元素在存储器中不一定相邻，但是存储每个数据元素时都附加了指针（地址）字段，通过设
　　置指针使不相邻的数据元素有了相邻的逻辑关系。
　　数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。数
　　据的各种逻辑结构有相应的各种运算，每种逻辑结构都有一个运算的集合。
　　以下是数据结构通常具有的一些基本运算操作。
　　（1）插入：在数据结构的指定位置上添加一个新结点。
　　（
　　2）删除：删去数据结构中指定位置的结点。
　　（
　　3）更新：修改数据结构中某个结点的值。
　　（
　　4）查找：在数据结构中寻找满足指定条件的结点及其位置。
　　（
　　5）排序：按照指定的顺序，使结点重新排列。
　　总之，数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据
　　的存储结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法
　　（见图 6.2）。
　　数据结构与数学、计算机硬件和计算机软件有着十分密切的关系，它是操作系统、数据
　　库、语言编译、人工智能等软件的重要技术基础，广泛应用于信息科学、系统工程、应用数
　　学以及各种工程技术领域。在一定意义上，程序所描述的就是在数据结构上实现的算法。算
　　法的设计依赖于数据的逻辑结构，算法的实现依赖于数据的存储结构，所以数据结构选择的
　　好坏，对程序质量的影响甚大，如同人类的＂团结起来才有力量＂一样，数据＂组织起来才
　　有效率＂。好的数据结构能节省存储空间，并能极大地提高程序的执行速度。掌握基本的数
　　据结构知识，是提高程序设计水平的必要条件。
　　线性结构
　　树型结构
　　数据的逻辑结构 图型结构
　　集合等
　　顺序存储
　　数据结构 数据的存储结构
　　链式存储
　　插入、删除
　　数 据 的 运 算
　　查找、排序
　　图 6.2 数据结构的组成
　　二、算法
　　为了有效地进行程序设计，不仅要掌握一门程序设计语言，还应该学会针对各类问题拟
　　定出有效的解题方法和步骤——即算法设计。有了正确的算法，才能够编制程序。算法的好
　　坏，决定了程序的优劣，因此，程序设计的核心任务之一就是设计算法。
　　1．算法的概念
　　所谓＂算法＂，粗略地讲，是为解决一个特定问题而采取的特定的有限的步骤。广义的
　　说，做任何事情都有其算法，例如，歌谱就是歌曲的算法，因为它规定了歌唱者应如何唱歌，
　　而菜谱可以说是厨房里的算法了。再例如：求解一个一元二次方程，我们要知道一元二次方
　　程的求根公式，对于求解的一元二次方程的实根或虚根的详细的描述，就是求解—元方程问
　　题的算法。在计算机的数据处理中，如何对大批量的数据进行排序，如何进行查找，人们也
　　设计了各种算法，以便适应不同情况的需要。
　　从计算机应用的角度来说，算法是用于求解某个特定问题的一些指令的集合。具体地说，
　　我们用计算机所能实现的操作或指令，来描述问题的求解过程，就是这一特定问题的计算机
　　算法。算法设计的任务就是找到尽快解决问题的办法。
　　算法的研究可以说是源远流长。在漫长的岁月中，人们发现了很多有效的算法。已知最
　　早的算法是写在考古学家发掘出来的黏土板上的，这些黏土板的年代大约是公元前 3000
　　年――公元前 1500 年，也就是大约 3500—5000 年以前。历史上有许多有趣的数学难题大都
　　和算法的研究有关，激励着一代代数学爱好者去攻克、解决。直到电子计算机的出现，开创
　　了算法研究的新时代。计算机使人们用机器自动解题的梦想成为现实，人们可以将算法编写
　　成程序交给计算机去执行，从而迅速获得结果。著名的计算机科学家克努特（Knuth)认为：
　　计算机科学就是算法的学习。
　　2．算法的性质
　　一个完整的计算机算法必须满足下述 5 个准则或标准。
　　（1）有穷性
　　有穷性指的是一个算法必须在执行了有穷(有限)的步骤之后结束。
　　例如，如果用下述公式计算圆周率π值：
　　PI=(1-1/3+1/5-1/7+…)／4
　　若要求计算精度为 16 位小数，这是一个有穷的算法。因为达到 16 位精度时，算法的执
　　行就停止了，但其运算时间却长得令人不能容忍。如果不规定＂精度为 16 位小数＂，则执
　　行过程永远不会停止，这就不是算法，只能是一个计算过程或计算方法。
　　若某算法尽管在理论上是会结束的，但实际运算要花费几天、几十天，甚至几年的时间，
　　人们也认为该算法不实用。
　　（
　　2）确定性
　　确定性是说对算法的每一步，必须确切地定义。
　　在任何情况下，有待执行的动作必须严格地和清楚地规定，不允许有二义性。人们在交谈及阅读中，可以根据当时的环境及上下文，对于有歧义的语句作出正确的判断。而程序如
　　果出现语义含糊的情况，计算机是不会根据上下文做出正确决策的。因此，算法的正确性要
　　求对于同样的输入，算法只能有唯一的一条执行路径，只能得到相同的输出。
　　（
　　3）可行性
　　指对于算法的每一步，指令必须是可执行的。也就是说，算法中所有有待实现的运算都
　　应该是基本的，它们原则上都能够由人们仅用笔和纸做有穷次运算即可完成。算法的可行性
　　要求算法在有限步骤之后能够达到预期的目的。
　　（
　　4）输入性
　　指一个算法必须有零个或多个的输入。它们是在算法开始前对算法提供的最初的量。这
　　些输入取自于特定的对象集合，例如必须为整数。一般而言，由外部提供的输入，刻划了算
　　法的初始状态。若算法没有输入，则由算法内部确定其初始条件。
　　（
　　5）输出性
　　指算法必须有一个或多个输出。它们是同输入有某种特定关系的量。没有输出的算法是
　　毫无意义的。算法的输出与算法的输入之间存在特定的关系，算法完成从输入量到输出量之
　　间的数据加工，也可能转变输入量与输出量之间的数据关系。
　　具有上述 5 个特性才能称为算法，其中最重要的是算法的有穷性，如果不具备有穷性，
　　仅具有另外 4 种性质，只能称为计算过程或计算方法，而不是算法。
　　算法的含义与程序十分相似，但也有些差别。一般来说，程序并不需要满足有穷性，例
　　如操作系统本身也是一个程序，只要整个系统不遭受破坏，操作系统就永不结束。另外程序
　　是用机器可执行的语言书写的，而对算法通常并没有这种限制。
　　3. 算法的描述
　　算法设计人员在设计了一个算法之后，不能只是自己心知肚明，而必须准确清楚地将他
　　所设计的解题步骤记录下来，或提供交流，或编写成程序供计算机执行。为此，首先要解决
　　的问题是如何把算法正确地表示出来，这就要依赖于算法的描述工具。
　　算法不像诗歌那样浪漫，不如小说和电影那样情节迷离，也不像散文那样富有诗情画意，
　　令人遐思。算法完全是一种＂实话实说＂，是＂有一说一＂，它要求把你构思好的解题步骤
　　严密地、直接地表达出来。
　　目前存在着多种形式的算法描述工具，但是都可以归结为文字描述和图形描述两类。在
　　文字描述工具中，常用的描述形式有自然语言和伪码两种；在图形描述工具中，常用的有流
　　程图、N-S 图等工具。
　　(1)用自然语言表达
　　所谓的＂自然语言＂指的是日常生活中使用的语言，如汉语、英语或数学语言。例如：
　　我们想计算 1 到 N 的累加和，为简单起见，设 N 的值不大于 1000。算法可以用如下的方式
　　描述。
　　S1：输入 n(要求 n<=1000)；
　　S2：累加和 sum 置初值 0；
　　S3：自然数 i 置初值 1；
　　S4：若 i<=n， 则重复执行：
　　S41：i+sum —> sum；
　　S42：i+1 —>i
　　S5：输出 sum，结束。
　　更通用地，要求从自然数 n1 累加到 n2，算法仅需对 S1、S3 和 S4 做必要的修改： S1：输入n1、n2(要求n1<=n2，n2<=1000)
　　S3：自然数i置初值n1
　　S4：若i<=n2，则重复执行:
　　其余部分不用改动。这是用自然语言配合数学语言描述算法。
　　用自然语言描述算法最大的特点是通俗易懂，而且容易掌握。使用者不必对工具本身再
　　花精力去学习，写出来的算法也容易理解，但这种算法的表达方式与计算机的具体高级语言
　　形式差距较大，通常用于介绍如何解决问题。
　　此外，用自然语言表示算法容易出现二义性；语句一般太长；语句成线性排列，不易清
　　晰地表达分支和循环，这些也是它的缺点。
　　(2) 用伪代码表示
　　伪代码是一种介于自然语言与计算机语言之间的中间语言。它结构性较强，比较容易
　　书写和理解，修改起来也相对方便。其特点是不拘泥于语言的语法结构，而着重以灵活的形
　　式描述对象。它利用自然语言的功能和若干基本控制结构来描述算法。伪代码没有统一的标
　　准，和程序设计语言很类似，但表示的方式更宽松，比较自然、直观、易理解。常见的有类
　　PASCAL、类 C 等伪代码语言。
　　比如，我们可以规定如下的一组伪代码来描述算法。
　　顺序结构
　　类似自然语言中的语句构成，通常表示赋值、输入输出等顺序执行的步骤。
　　选择结构
　　IF 〈条件〉 THEN
　　〈语句组 1〉
　　[ELSE
　　〈语句组 2〉 ]
　　ENDIF
　　当型循环结构
　　WHILE 〈条件〉 DO
　　〈循环体〉
　　ENDDO
　　直到型循环结构
　　REPEAT
　　〈循环体〉
　　UNTIL 〈条件〉
　　FOR 循环结构
　　FOR 〈变量名〉=〈初值〉 TO〈终值〉〈条件〉[〈STEP 正增量〉]
　　〈循环体〉
　　ENDFOR
　　FOR 〈变量名〉=〈初值〉 DOWNTO〈终值〉〈条件〉[〈STEP 负增量〉]
　　〈循环体〉
　　ENDFOR
　　(3) 用传统流程图描述算法
　　流程图是人们经常用来描述算法的工具。它是是用规定式样的几何图形、流程线及文
　　字说明组合起来表示算法的框图。用流程图描述算法的优点是直观、清晰、便于检查、修改
　　和交流，往往使得设计者的思路表达得清楚易懂。
　　不像其他语言，流程图语言是二维的。用流程图表示的算法既独立于任何特定的计算机，又独立于任何特定的计算机程序设计语言。流程图语言的缺陷是严密性不如程序设计语
　　言，描述的灵活性不及自然语言。
　　表 6.1 是用传统流程图描述算法时常用的符号。
　　表 6.1 流程图常用符号
　　流程图符号
　　含义
　　数据输入/输出框，用于表示数据的输入和输出
　　处理框，描述基本的操作功能，如＂赋值＂操作、数学运算
　　等
　　两分枝判断框，根据框中给定的条件是否满足，选择执行两
　　条路径中的一条
　　开始/结束框，用于表示算法的开始与结束
　　连接符，用于连接流程图中不同地方的流程线
　　流程线，表示流程的路径和方向
　　条件
　　1 2 . . . n
　　多分支判断框，根据框中的＂条件值＂，选择执行多条路径中
　　的一条
　　注释框，框中内容是对某部分流程图的解释说明
　　用流程图描述算法时，一般要注意以下几点
　　①应根据解决问题的步骤从上至下顺序地画出流程图，各图框中的文字要尽量简洁。
　　②为避免流程图的图形显得过长，图中的流程线要尽量短。
　　③用流程图描述算法可粗可细，关键是要将算法描述清楚。其原则是：根据实际问题的
　　复杂性，最终效果为，依据此图就能用某种程序设计语言实现相应的算法(即完成编程)。
　　前面介绍了算法的基本概念和描述方式，下面我们给出个设计实例，以便掌握算法的描
　　述方法。
　　例 6．1 输入一个公元年份，判断它是否为闰年。
　　问题分析：闰年的条件如下。
　　①能被 4 整除，但不能被 100 整除。
　　②能被 400 整除。
　　(1)用伪码描述算法：
　　BEGIN
　　INPUT year //year 表示公元年份
　　IF year 能被 4 整除但不能被 100 整除 THEN
　　PRINT year 是闰年 ELSE
　　IF year 能 400 整除
　　PRINT year 是闰年
　　ELSE
　　PRINT year 不是闰年
　　ENDIF
　　ENDIF
　　END
　　(2)用流程图描述算法：如图 6.3 所示
　　图 6.3 判断闰年的流程图
　　一般来说，由于自然语言是人们日常生活的用语，故用自然语言描述算法易于表达和理
　　解，但是往往存在着表达不够简洁、不够严格、易产生理解上的＂多义性＂等问题。用伪码
　　描述算法时，可根据实际问题的需要使用中文或英文书写，既可把算法写得非常概括也非常
　　具体，且基本解决了用自然语言描述算法时产生的欠简洁和多义性的问题，是一种灵活、易
　　掌握、被广泛应用的算法描述工具。用流程图描述的算法，具有直观、易理解等优点。但是，
　　因为流程图可以用于描述非结构化的算法，所以可能会造成使用者不受限制地设计出由非基
　　本结构组成的算法。此外，在表示较复杂问题的算法时，易出现图形过长的问题。需要强调
　　的是，在为具体问题设计算法时，选用何种算法描述工具并不重要，重要的是一定要把算法
　　描述的简洁、正确，不会产生理解上的＂多义性＂。
　　4. 算法的＂快＂与＂慢＂――对算法设计的要求与评价
　　做事要讲究方法。方法得当，可以事半功倍。对同一个问题，可以用不同的算法去解决，
　　虽然达到的目的是一样的，但采用相对较好的算法不仅可以使程序的书写变得简洁，而且能
　　使程序运行效率相对提高。
　　(1)算法的设计要求算法设计一般要求满足以下几点。
　　①正确性
　　算法应当满足具体问题的需求，设计或选择的算法应当能够正确地反映这种需求，这是
　　衡量算法正确与否的准则。
　　②可读性
　　算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解，
　　而晦涩难懂的算法易于隐藏较多的错误，最终难以调试和修改。
　　③健壮性
　　是指当输入数据不在允许的范围时，算法也能适当地作出反应或处理，而不会产生莫名
　　其妙的输出结果。
　　④效率高与低存储量需求
　　效率是指的执行时间，如果对于一个问题有多个算法可以解决，那么执行时间短的算法
　　效率就高。存储量需求是指算法执行过程中所需的最大存储空间。一个理想的算法应该是数
　　据所占用的存储空间较小而数据处理的速度较快。
　　(2) 对算法的评价
　　评价算法需要从几个不同的角度去考虑，最主要的是正确性和运行效率。
　　①算法的正确性
　　算法的正确性是最起码的，也是最重要的。对于简单的算法(或程序)，可以通过上机调
　　试验证其正确与否。调试用的数据要精心挑选具有＂代表性＂的，甚至有点＂刁钻性＂的，
　　以保证算法对＂所有的＂数据都是正确的。
　　但是，一般来说，调试并不能保证算法对所有数据都正确，只能保证算法对部分数据正
　　确，调试只能验证算法有错，不能证明算法无错。就是说只要找出一组数据使算法失败(即
　　计算结果不对)，就能否定整个算法的正确性。但调试往往不能穷尽所有可能的情况，所以，
　　即使算法有错，也不一定能通过调试在短时间内发现。不少大型软件在使用多年后，仍然发
　　现错误就是这个道理。保证算法的正确性，通常要用数学归纳法去证明。
　　②算法的运行效率
　　主要指算法所耗费的时间和占用的空间。如果一个算法所需要的时间或空间比求解同一
　　问题的另一个算法所需的时间或空间少，就说这个算法比另一个算法好。
　　通常我们用时间复杂度来度量算法的时间耗费级别，用算法的空间复杂度来衡量算法的
　　空间占用情况。
　　在设计算法时，有时为了节省时间而多使用一些辅助变量(主要是数组)。这种做法实际
　　上是＂牺牲空间，换取时间＂。
　　在进行算法分析时，一般只讨论算法的时间效率，偶尔涉及到算法的存储量需求时，主
　　要考虑的也只是算法运行时所需辅助空间的大小。
　　三、算法、数据结构与程序设计
　　1．算法与程序设计
　　我们利用计算机解决各种问题，算法是至关重要的。没有算法，我们对要解决的问题就
　　无从下手，程序就成了无本之木，无源之水。有了算法，你才有可能去程序设计，最终让计
　　算机执行你的程序，完成你所要求的任务。算法一经确定，无论是谁使用，无论是用何种计
　　算机语言编制程序，算法的操作步骤是一样的，它不会因人而异。算法是程序的核心。算法
　　在程序编制，也可以说软件开发，以及整个计算机科学中的地位都是极其重要的。在计算机
　　领域的最高奖――图灵奖获得者中，有许多都是研究算法的科学家。2.数据结构与程序设计
　　计算机解决问题不但依赖于算法，而且会涉及到大批数据。数据的组织和存储会直接影
　　响算法的实现方式和效率。例如：在杂乱无章的数据里查找指定的数据和在有序数据集合里
　　查找数据的方法是不同的，利用二分法可以迅速地在有序数集里找到你所要查找的数据，而
　　对于无序数集，二分法就毫无用处了。
　　人们在处理复杂问题时，总要利用抽象这个思维工具。抽象是抓住问题的实质，而忽略
　　问题的次要部分；注意事物的普遍规律，或共性的东西。算法和数据结构是人们用计算机解
　　题时所作的两种抽象：算法是从计算机的操作角度对解题过程的抽象，是程序的核心。数据
　　结构是从如何组织处理操作对象的角度进行的抽象。程序进行计算或处理总是以某些数据为
　　对象的，而要设计出一个好的程序就需要将这些松散的数据按某种要求组成一种数据结构。
　　这两种抽象互相依赖、互相补充，最大限度地减低问题的复杂性。在这两个方面的基础上，
　　人们开发出运行效率较高的各种应用程序。因此，在—定意义上，人们认为：
　　程序=算法+数据结构
　　除了算法和数据结构之外，程序设计方法对程序设计也是重要的，它影响到程序设计的
　　成败及程序设计质量。随着计算机解决的问题越来越复杂，计算机本身的运算速度越来越快，
　　内存容量也越来越大，程序设计已决不是程序员个人技巧的＂手工艺品＂。程序设计要遵循
　　一定的开发方法及思想，如结构化设计方法，模块化程序设计方法、自顶向下的逐步细化的
　　方法、面向对象的程序设计方法等，要按照工程管理的方法去进行软件开发，即用软件工程
　　的思想及方法去指导进行软件开发。
　　第三节 用＂工程化＂的思想组织开发软件——软件工程概述
　　60 年代中期以后，计算机硬件技术日益进步，计算机的存贮容量、运算速度和可靠性
　　明显提高，生产硬件的成本不断降低。计算机价格的下跌为它的广泛应用创造了极好的条件。
　　在这种形势下，迫切要求计算机软件也能与之相适应。因而，一些开发大型软件系统的要求
　　提了出来。然而软件技术的进步一直未能满足形势发展的需要，在大型软件的开发过程中出
　　现了三大难题：
　　①复杂程度高。例如，美国阿波罗登月计划的程序就长达 1000 万行，航天飞程序就长
　　达 4000 万行。
　　②研制周期长。例如，著名的 IBM 360 的操作系统的开发，整整长达四年，花费了 5000
　　人年。也就是说，如果是一个人单干的话，得用上 5000 年，而人类自己得文明史也不过 5000
　　年。
　　③正确性难以保证。研制软件本质上是一个＂思考＂过程，很难对它进行控制。例如，
　　1963 年，美国用于控制火星探测器的计算机软件中的一个＂，＂号被误写为＂·＂，而使
　　飞往火星的探测器发生爆炸，造成高达数亿美元的损失。再例如，在 1985 年至 1987 年间，
　　至少有两个病人死于由 Therac—25 医用线性加速器产生的严重过量辐射，原因是控制软件
　　中存在一个错误。
　　由于遇到的问题找不到解决办法，致使问题堆积起来，形成了人们难以控制的局面，出
　　现了所谓的＂软件危机＂。
　　为了克服这一危机，一方面需要对程序设计方法、程序的正确性和软件的可靠性等问题
　　进行系列的研究；另一方面，也需要对软件的编制、测试、维护和管理的方法进行研究，从
　　而产生了程序设计方法学。一、软件工程的由来
　　计算机硬件的性能按照摩尔定律在不断提高，价格在不断降低。同硬件投资相比，软件
　　的投资所占比例扶摇直上，例如，美国 1985 年软件投资所占比重已经高达计算机总投资的
　　85％。人们对软件的需求在不断增加，而软件需要大量的投资，质量又不理想，这就产生了
　　尖锐的矛盾。人们逐步认识到：正像不能用造独木船的手工方式来建造航空母舰，不能用盖
　　茅屋、平房的手工作业来建造摩天大楼一样，沿用过去编写小型程序的那种手工方式来研制
　　大型软件系统也是不行的，必须在开发软件的方法上进行创新，必须寻找新的技术来指导软
　　件的大规模生产。
　　软件工作者在研制软件系统与建造楼房或制造机器之间找到了相似性，因此，可以参考
　　建筑工程、机械工程中的一些技术来指导软件的研制。于是，要像对待＂工程＂一样来处理
　　软件研制的全过程的想法应运而生。
　　1968 年 10 月，北大西洋公约组织（NATO）科学委员会在德国的加尔密斯
　　（Garmisch,Germany）开会讨论软件可靠性与软件危机的问题，弗里茨 鲍尔（Fritz Bauer）
　　首次提出了＂软件工程＂的概念，他认为：软件工程是为了经济性地获得能够在实际机器上
　　高效运行的可靠软件而建立和使用的一系列好的工程化原则。
　　后来，人们曾经多次给出了有关软件工程的定义，这里是 IEEE 组织给出的一个更为全
　　面的定义。软件工程是：①将系统性的、规范化的、可定量的方法应用与软件的开发、运行
　　和维护，即将工程化应用到软件上；②对①中所述方法的研究。
　　从上述定义中可以看出，软件工程包括以下两方面的内容：
　　（1）软件工程是工程概念在软件领域的一个特定应用。
　　（
　　2）软件工程涉及软件产品的所有环节。
　　软件工程就是采用工程化的方法开发和维护软件的工程学科。它把经过时间考验而证明
　　正确的管理技术和当前能够得到的最好的技术和方法结合起来，以便经济地开发出高质量的
　　软件并有效地维护它。
　　软件工程以关注软件的质量为目标，它包括方法、工具和过程三个要素。
　　（1）软件工程的方法为软件提供了＂如何做＂的技术，通常包括某种语言和或图形的
　　模型表示方法、良好的设计实践以及质量保证标准等，其中使用最广泛的两种方法是传统的
　　软件开发方法和面向对象方法。
　　（
　　2）软件工程的过程是管理和控制产品质量的关键，它定义了技术方法的采用、工程
　　产品（包括模型、文档、数据、报告、表格等）的产生、里程碑的建立、质量的保证和变更
　　的管理，从而将人员、技术、组织与管理有机地结合在一起，实现在规定的时间和预算内开
　　发高质量软件的目标。
　　（
　　3）软件工具为软件工程方法提供了自动的或半自动的软件支撑环境，辅助软件开发
　　任务的完成。现有的软件工具覆盖了需求分析、系统建模、代码生成、程序调试和软件测试
　　等多个方面，形成了集成化的软件开发环境 CASE(Computer Aided Software Engineering)，
　　以便提高开发效率和软件质量，降低开发成本。
　　软件工程的目标是在给定成本、进度的前提下，利用工程化原则，开发出具有可修改性、
　　有效性、可靠性、可理解性、可维护性、可重用性、可适用性、可移植性、可追踪性和可互
　　操作性并满足用户需求的软件产品。
　　软件工程是一门交叉性的工程学科，它将计算机科学、数学、工程学和管理学等基本原
　　理应用于软件的工程实践中，并借鉴传统工程的原则和方法，以系统的、可控的、有效的方
　　式产生高质量的软件。需要强调的是，由于软件自身的特殊性，软件工程更强调抽象、建模、
　　信息组织与表示以及变更管理，另外还包括软件开发过程的质量控制活动，强调在软件开发
　　中的持续的维护。这些又与传统工程存在着明显区别。迄今为止，软件工程的研究与应用已取得很大成就，大大缓解了软件危机，但是软件的
　　开发还是一项艰巨的任务，大型软件的开发是一项涉及到人、技术、管理组织的开放复杂大
　　系统，人们还在不断地探索和研究之中。
　　二、软件工程框架
　　软件工程与其它工程(例如土木工程)一样，有其自己的目标、过程和原则。软件工程的
　　框架可概括为图 6．4 中所示的内容。
　　图 6．4 软件工程的框架
　　1．软件工程的目标
　　软件工程的目标可概括为＂生产具有正确性、可用性以及开销合宜的产品＂。
　　正确性指软件产品达到预期功能的程度。可用性指软件基本结构、实现及文档为用户可
　　用的程度。开销合宜意义自明。
　　2．软件工程的过程和活动
　　软件工程过程是＂生产一个最终满足需求且达到工程目标的软件产品所需要的步骤＂。
　　主要包括分析过程、开发过程、维护过程。它们覆盖了需求、设计、实现、确认以及维护等
　　活动。
　　需求活动包括问题分析和需求分析。问题分析获取需求定义，又称软件需求规约。需求
　　分析生成功能规约。
　　设计活动一般包括概要设计和详细设计。概要设计建立整个软件体系结构，包括子系统、
　　模块以及相关层次的说明、每一模块的接口定义。详细设计产生程序员可用的模块说明，
　　包括每一模块中数据结构说明及加工描述。
　　实现活动把设计结果转换为可执行的程序代码。
　　确认活动贯穿于整个开发过程，实现完成后的确认，保证最终产品满足用户的
　　要求。
　　维护活动包括使用过程中的扩充、修改和完善。
　　伴随以上活动，还有管理过程、支持过程、培训过程等。
　　3．软件工程的基本原则
　　围绕软件开发的工程设计、工程支持以及工程管理，提出了以下四条基本原则：
　　（1）选取适宜的开发模型。该原则与系统设计有关。在系统设计中，软件需求、硬件
　　需求以及其它因素之间是相互制约、相互影响的，经常需要权衡。因此，必须认识需求定义
　　的易变性，采用适宜的开发模型予以控制，以保证软件产品满足用户的要求。
　　（
　　2）采用合适的设计方法。在软件设计中，通常要考虑软件的模块化、抽象与信息隐
　　蔽、局部化、一致性以及适应性等特征。合适的设计方法有助于这些特征的实现，以达到软件工程的目标。
　　（
　　3）提供高质量的工程支持。＂工欲善其事，必先利其器＂。在软件工程中，软件工
　　具与环境对软件过程的支持颇为重要。软件工程项目的质量与开销直接取决于对软件工程所
　　提供的支撑质量和效用。
　　（
　　4）重视开发过程的管理。软件工程的管理，直接影响可用资源的有效利用，生产满
　　足目标的软件产品，提高软件组织的生产能力等问题。因此，仅当软件过程予以有效管理时，
　　才能实现有效的软件工程。
　　三、 软件工程的研究内容
　　根据软件工程这一框架，软件工程学科的研究内容主要包括：软件开发模型，软件开发
　　方法，软件过程，软件工具，软件开发环境、计算机辅助软件工程(CASE)以及软件经济学
　　等。
　　1．软件开发模型
　　软件开发模型着重研究软件开发全部过程、活动和任务的结构框架。例如瀑布模型、螺
　　旋模型及喷泉模型等。作为一个模型，对于不同的应用系统，应允许采用不同的开发手段和
　　方法，使用不同的程序设计语言以及各种不同技能的人员参与，还应允许采用各种不同的软
　　件工具或各种不同的软件工程环境。
　　2．软件开发方法
　　软件开发方法是指软件开发过程所遵循的办法和步骤。开发过程一般包括需求、设计、
　　实现、确认等活动。目前，主要针对需求和设计，提出了各种方法，其中典型的有：结构化
　　方法、面向数据结构方法和面向对象方法。
　　3．软件过程
　　软件过程指软件生存周期所涉及的一系列相关过程。软件过程主要针对软件生产和管理
　　进行研究。为了获得满足工程目标的软件，不仅涉及工程开发，而且还涉及工程支持和工程
　　管理。软件工程中的过程管理贯穿于软件开发和维护的各个阶段。管理者负责项目计划、人
　　员组织、成本估算和控制、质量保证、配置管理等，并对软件开发的质量、进度、成本进行
　　评估、管理和控制。
　　4．软件工具
　　软件工具是用来辅助软件开发、维护和管理的软件。使用软件工具能节省开发时间和费
　　用，提高软件生产率和质量。软件工具是人类在软件开发过程中智力和体力的延伸与扩充，
　　它自动或半自动地支持软件的开发和管理，支持各种软件文档的生成。软件工具最初是零散
　　的，不系统、不配套的，后来人们将支持不同开发阶段的软件工具和软件工程数据库集成在
　　一起，建立了集成化的计算机辅助软件工程(CASE)环境。软件工具种类繁多，从通常可分
　　为：项目管理工具、配置管理工具、分析和设计工具、程序设计工具、测试工具以及维护工
　　具等。
　　5．软件开发环境
　　软件开发环境是支持软件产品生产的软件系统。该环境由集成机制和工具集组成。集成
　　机制主要实现工具的集成，使之能够系统有效地支持软件开发。工具集包括支持软件开发模
　　型和方法的工具。四、软件的生存周期
　　如同人的一生要经历少年、青年、中年、壮年、老年等阶段。同样，软件系统也有生命
　　期，其生产也可以划分若干阶段。
　　软件产品从形成概念开始，经过开发、使用和维护，直至最后退役的全过程称为软件生
　　存周期。
　　一般说来，软件生存周期包括软件定义、软件开发、软件使用与维护三个部分，并可进
　　一步细分为可行性研究、需求分析、概要设计、详细设计、实现、组装测试、确认测试、使
　　用、维护和退役十个阶段。下面依次介绍各阶段的主要任务、技术途径及其阶段性产品。
　　1．分析用户想＂做什么＂――软件的分析定义时期
　　俗话说：＂隔行如隔山＂。用户熟悉自己本身的业务，但不熟悉计算机技术，软件人员
　　则熟悉计算机技术而不了解用户的业务。许多情况下，用户常常不能对自己所需要的功能进
　　行科学、合理的概括和总结，这就需要开发人员和用户之间很好地沟通和交流，认真分析用
　　户究竟想＂做什么＂或帮助用户明确自己到底想＂要什么＂样的软件系统。然后，将用户的
　　需求很好地表达出来，形成这一时期的文档――系统说明书（或规格说明书），它描述了＂产
　　品打算做什么＂。
　　在这一时期，＂需求分析＂和＂完整表达＂的精确性是至关重要的。所形成的文档将作
　　为开发部门和用户间的合同，也是软件人员进行设计和编写程序的基础，当然也是验收的依
　　据。因而它应该既精确、完整、无二义性，又简明易懂，易于维护。
　　软件定义时期的任务包括：①确定软件开发工程必须完成的总目标；②论证工程的可行
　　性；③确定对人力资源和设备资源的要求；④作出成本估算；⑤制定工程进度表；⑥明确验
　　收标准。
　　软件定义时期主要包括可行性研究和需求分析两个阶段。
　　（
　　1）可行性研究
　　可行性包括技术可行性、操作可行性和经济可行性三部分。技术可行性指，使用目前可
　　用的开发方法和工具能否支持需求的实现。操作可行性指，用户能否在某一特定的软件运行
　　环境中使用这个软件。经济可行性指，实现和使用软件系统的成本能否被用户接受。
　　（
　　2）需求分析与规格说明
　　需求分析的任务是：通过对应用问题及其环境的理解与分析，为问题涉及的信息、功能
　　及系统行为建立模型，将用户需求精确化、一致化、完全化，最终形成需求规格说明，其内
　　容包括软件系统的功能需求、性能需求、接口需求、设计需求、基本结构、开发标准及验收
　　原则，等等。需求规格说明是软件设计、实现、测试直至维护的主要基础。
　　2．找解决方案――软件开发时期
　　明确了＂做什么＂之后，就开始考虑软件＂怎么做＂，即寻求＂解答＂了。
　　软件开发通常由软件设计阶段（包含概要设计和详细设计）、实现阶段、测试阶段组成。
　　（1）软件设计阶段
　　首先是结构设计或概要设计，它将一个整体的产品分解成各个部分，每个部分称为模块；
　　然后再对每个模块进行设计，这个过程称为详细设计。在这里得出的两个设计文档描述了＂产
　　品是如何做的＂。
　　设计阶段的主要成果是设计本身，它包括两部分：结构设计，从模块的角度对产品进行
　　描述；以及详细设计，对每个模块的描述。详细设计交由程序员完成。
　　（
　　2）软件实现阶段
　　在实现阶段，对各种组成模块进行编码，同时对它们进行单元测试(或桌面测试)，用测试用例运行它们。这个非正式的测试是由程序员做的，在此之后由质量保证小组对模块进行
　　系统测试。与实现阶段相关的主要文档是每个模块的源代码，及适当的注释。还包括测试用
　　例、期望的结果和实际输出。
　　为了保证模块测试的质量，测试之前应制定测试方案并产生相应的测试数据，不仅要对
　　合法输入数据进行测试，而且还要对非法输入数据进行测试；既要对正常处理路径进行测试，
　　也要对异常或出错处理路径进行测试。
　　程序模块测试方案、用例、预期的测试结果是软件文档的重要组成部分，必须及时整理
　　并存档。
　　（
　　3）软件集成阶段
　　将产品的各个部分组合起来，并作为一个整体进行集成测试；当开发人员对产品的功能
　　感到满意时，由客户对产品进行验收测试。在具体的开发中有时集成阶段应当与实现阶段并
　　行进行。
　　集成测试的目的是检查模块是否正确地组合在一起，是否能够实现规格说明文档对产品
　　功能的要求。在集成测试阶段，对模块接口测试必须格外小心。不仅必须测试产品的正确性，
　　还需要测试产品的健壮性。即，故意将错误的输入数据提供给产品，确定产品是否会崩溃，
　　或者是否产品的错误处理能力足够应付这些有问题的数据。
　　集成测试接下来是验收测试。软件交付给客户，客户使用真实数据，在实际的硬件上对
　　产品进行测试。
　　软件集成阶段产生的文档包括：整个项目的源代码(包括注释)，整个项目的测试用例，
　　以及用户手册、操作手册、数据库手册和其他手册。
　　3．软件使用、维护和退役
　　软件使用和维护时期的主要任务是使软件持久地满足用户的需要，即：1)当软件在使用
　　过程中发现错误时应该加以改正；2)当环境改变时应该修改软件，以适应新的环境：3)当用
　　户有新要求时应该及时改进软件，以满足用户的新需要。
　　有时人们认为只有坏的软件才需要维护，实际上恰恰相反，人们通常将坏的软件扔掉，
　　而对好的软件在 10 年、15 年甚至 20 年的时间范围内进行改进和提高。维护的代价是惊人
　　的，可以发现整个软件耗费有大约 2／3 都用于了维护，此外，有许多组织投入 80％的时间
　　和努力用于维护。由此我们可以发现，维护是软件生命周期中时间和金钱花费最昂贵的一个
　　阶段。
　　由上可见，软件生命周期中，每个阶段都有确定的任务，并产生一定规格的文档，送交
　　下一个阶段；而下一阶段是在前一阶段评审通过的基础上，继续开展工作。
　　软件�...