第7章 软件技术基础.pdf

第第 7 7 章章 软件技术基础软件技术基础主要内容主要内容：本章主要介绍计算机软件实现的相关基础知识，包括程序设计与程序设计的基本过程、程序设计语言、数据结构与算法、软件工程、 软件开发方法 、应用系统开发过程和方法等。学习目标学习目标：1.了解计算机程序设计的基本概念，程序设计语言的发展。2.了解数据结构和算法在程序设计中的作用。3 了解软件工程的定义、主要内容和过程。4.了解软件开发常用的方法和技术。5.掌握开发一个应用系统的主要步骤。7.17.1 程序设计基础程序设计基础在计算机科学领域，计算机软件扮演着十分重要的角色， 那么，计算机软件是由什么构成？它又是如何产生的呢？最通俗的说法就是计算机软件是由计算机程序构成的， 是由计算机程序员设计产生的。那么什么是计算机程序，它由什么组成？在这里,首先介绍计算机程序设计的相关基础知识。7.1.17.1.1 计算机程序设计计算机程序设计计算机作为一种电子设备， 一旦被制造出来，它的硬件结构也就确定了， 而计算机要能够充分发挥作用是离不开计算机软件的。 对于一台计算机， 需要它实现何种功能就要给它安装相应的软件，否则它的功能就无法发挥出来。 比如用户需要用计算机进行文档处理， 那么就需要安装 Office 或 WPS 等相应的文档处理软件；假如用户需要进行多媒体创作就需要在计算机上安装 Flash、Authorware 或 Director 等相应的多媒体处理软件。提到计算机软件自然要涉及到程序的概念， 所有的软件都是程序员通过编写程序代码实现的。计算机作为一种电子设备， 它所能实现的功能都是人类赋予它的， 要使计算机完成一项任务就必须要告诉计算机完成这项任务的工作步骤， 人类就是通过计算机程序来完成这一工作的。 可以说计算机程序是人和计算机之间的媒介， 它传递着人和计算机之间的交流信息。从直观上来看， 计算机程序就是使用一种计算机能够懂得的语言编写的一组指令序列。 创作计算机程序的过程就叫做计算机程序设计。7.1.27.1.2 程序设计语言程序设计语言计算机程序实现人和计算机之间的信息交流， 而实现这一交流的基础工具就是计算机程序设计语言。 计算机程序设计语言是人们为描述计算过程而设计的一种具有语法语义描述的记号。为了实现人与计算机之间的通信，人们设计出了各种词汇较少、语法简单、意义明确并适合于计算机的程序设计语言。 对于计算机工作人员而言， 程序设计语言是除计算机本身之外的所有工具中最重要的工具，是其他所有工具的基础。从计算机诞生至今，随着计算机应用范围和规模的发展，程序设计语言不断升级换代，大体上经历了五代：1 1第一代是机器语言第一代是机器语言机器语言是一种 CPU 指令系统，是该 CPU 可以识别的一组由 0 和 1 序列组成的指令码。用机器语言编写程序，就是从所使用的CPU 指令系统中挑选合适的指令,组成一个机器可以直接理解、执行的指令序列。例如某CPU 指令系统中的两条指令：10000000加10010000减通过示例可以看出，这种 0、1 码序列组成程序序列太长，不直观，而且难记、难认、难理解，不易查错，因而只有专业人员才能掌握，程序生产效率很低，质量也难以保证。这种繁重的手工方式与高速、自动工作的计算机不相称，大大限制了计算机的推广使用。2 2第二代是汇编语言第二代是汇编语言为了减轻人们在编程中的劳动强度，克服机器语言的缺点，50 年代中期人们开始使用一些“助记符号”来代替0、1 码编程。如上例所示的两条机器指令， 用汇编语言可以写成：A+BA或ADD A,BA-BA或SUB A,B这种用助记符号描述的指令系统称为第二代计算机程序设计语言， 也称汇编语言。 汇编语言也是一种面向机器的程序设计语言，它用助记符号来表示机器指令的操作符与操作数，汇编指令与机器指令之间的关系是一对一的关系， 但是， 汇编语言指令不能被计算机直接识别、理解和执行，需要经过一个特定的翻译程序（即汇编程序）将其中的各个指令逐个翻译成相应的机器指令后才能执行。用汇编语言编程，程序的生产效率及质量都有所提高。汇编语言与机器语言都是随CPU不同而异，都是一种面向机器语言。程序员用它们编程时，不仅要考虑解题思路， 还要熟悉机器内部结构，编程强度仍很大，影响计算机的普及与推广。3 3第三代是高级程序设计语言第三代是高级程序设计语言为了克服汇编语言和机器语言的缺点，在50 年代初期，人们开始研制另一种计算机程序设计语言-面向过程的语言， 人们可用日常熟悉的， 接近自然语言和数学语言的方式对操作过程进行描述， 这种语言称为第三代计算机程序设计语言， 即高级程序设计语言或面向过程语言。用高级语言编程时，人们不必熟悉计算机内部具体构造和熟记机器指令， 而把主要精力放在算法描述上面，所以又称算法语言。例如，求一个表达式的值， 可在高级语言程序中直接写出如下语句：X=(A+B)/(A-B)而不需要写出大量的助记符号。第三代程序设计语言主要应用于事务应用、 数字计算、通用应用和专用应用等领域。 最具代表性的有 ALGOL、FORTRAN、COBOL、BASIC、PASCAL 等。4 4第四代是非过程化程序设计语言第四代是非过程化程序设计语言第四代程序设计语言的出现是由于商业需要。第四代程序设计语言这个词最早是在 80年代初期出现在软件厂商的广告和产品介绍中。 因此， 这些厂商的第四代程序设计语言产品不论从形式上还是从功能上， 差别都很大。但是，人们很快发现这一类语言由于具有“面向问题”、 “非过程化程度高等特点， 可以成数量级地提高软件生产率， 缩短软件开发周期，因此赢得了很多用户。第四代程序设计语言以数据库管理系统所提供的功能为核心、 进一步构造了开发高层次软件系统的开发环境，如报表生成、 多窗口表格设计、菜单生成系统、 图形图像处理系统和决策支持系统，为用户提供了一个良好的应用环境。它提供了功能强大的非过程问题手段，用户只需要告知系统做什么，而无须说明怎么做， 因此可以大大提高软件生产率。例如，数据库中的结构化查询语言SQL 就是属于第四代程序设计语言。当用户需要检索一批数据时，只需要通过 SQL 语言指定查询的范围、 内容和查询的条件， 系统就会自动形成具体的查找过程，并一步一步地去执行查找，最后获取查询结果。比如：查询 StudentInfo 表中，成绩不及格的同学的学号、姓名和成绩：SELECT Num，Name，ScoreFROM StudentInfoWhere Score605 5第五代是智能性语言第五代是智能性语言第五代语言除具有第四代语言的基本特征外， 还具备许多新的功能， 特别是具有一定的智能。主要应用于商品化人工智能系统、 专家系统和面向对象数据库管理系统等领域。 最具代表性的有 LISP、PROLOG、GEMSTONE 等。目前， 计算机的应用已经深入到了各行各业， 与此同时也出现了各种各样的为数众多的计算机程序设计语言。据统计， 目前已有数千种程序设计语言。在这些程序设计语言中，只有很小部分得到比较广泛的应用。 下面是一些在教学、 科研和开发中常用程序设计语言的简介：（1）BASIC 语言BASIC(Beginner All-Purpose Symbolic lnstruction Code)是由美国 Dartmouth 大学JohnKemeny 和 Thomas Kurt 开发的高级语言。它允许有较多的人机对话，简单易学，便于修改和调试，具有简单的语法形式和有限的数据结构与控制结构， 现在仍被广泛使用。它的流行得益于它的简单性、 实现的方便性与高效率。 它不仅用于各种科学计算， 而且广泛应用于各种数据处理， 还可用作教学工具。 目前有各种不同的版本。 例如， GWBASIC、 TURBO BASIC、TRUE BASIC 和 VISUAL BASIC 等。（2）Pascal 语言Pascal 语言是 70 年代初由瑞士联邦大学的 NWirth 教授创建的程序设计语言，为了纪念法国数学家 Pascal 而命名。Pascal 语言不仅用作教学语言，而且也用作系统程序设计语言和某些应用。 所谓系统程序设计语言， 就是用这种语言可以编写系统软件。 如操作系统、编译程序等。Pascal 语言是一种安全可靠的语言，有强数据类型。语法满足自顶向下设计和结构程序设计。Pascal 语言吸收了 ALGOL 语言中许多有益成分，使得Pascal 语言的数据抽象进入一个新的层次。（3）C 语言C 语言是在 70 年代初期由美国 Bell 实验室 Rithie 和 Thompson 在原 BCPL 语言基础上发展起来，用于编写UNIX 操作系统，取BCPL 的第二字母 C 而命名。C 语言在很多方面继承和发扬了许多高级程序设计语言的特色， 具有结构性，是一种结构化语言， 层次清晰，易于调试和维护；但它又不是完全结构化的，因为在C 函数中允许使用 goto 语句，函数可以相互调用，无嵌套关系，在同一控制流或函数中允许多个出口，语句简练，书写灵活，处理能力强，移植性好。（4）C语言C语言是一种在 C 语言基础上发展起来的面向对象语言，是由美国 Bell 实验室BStroustrup 在 80 年代设计并实现的。C语言具有数据抽象和面向对象的能力，是对C 语言的扩充。 C语言从 Simula 中吸取了类， 从 ALGOL 语言中吸取了运算符的一名多用、引用和在分程序中任何位置均可说明变量，综合了Ada 语言的类属和 Clu 语言的模块特点，形成了抽象类，从 Ada、Clu 和 ML 等语言吸取了异常处理，从BCPL 语言中吸取了用/表示注释。C语言对数据抽象的支持主要在于类概念和机制。对面向对象的支持主要通过虚拟机制函数。C语言是当前面向对象程序设计的一种主流语言。（5）Java 语言Java 语言的名字取自于印度尼西亚一个盛产咖啡的岛屿“爪哇”，是由 SUNMircoSystem 公司于 1995 年 5 月正式对外发布的。Java 语言是一种面向对象的、简捷易学的、可在 Internet 上分布执行的、可以防止部分故障，具有一定的安全健壮性程序设计语言，受到各种应用领域的重视， 发展很快。但是Java 还不很成熟，尚有不少需要改进之处。7.1.37.1.3 数据结构与算法数据结构与算法早期的计算机多用于进行数值计算， 数值计算的特点是数据元素之间的的关系简单但是计算复杂。而今，计算机的迅猛发展早已使其摆脱了单纯的科学计算， 现在各行各业都有大量的计算机在从事着行政事务管理、 生产作业调度和实时控制以及通信、 教育等方面的工作。而计算机自身的普及和发展也使得人们要求计算机处理的问题越来越多， 越来越复杂， 规模越来越大。 计算机处理非数值计算的问题的特点就是数据元素之间的关系复杂， 但是计算简单。非数值计算处理诸如字符、图像、声音、信号等各种各样具有一定结构的数据，为了有效地对它们进行组织和管理， 设计出高质量的程序，高效率地使用计算机， 必须深入地研究这些数据的特性以及它们之间的相互联系，这就是数据结构这门学科研究的内容。1 1数据结构数据结构数据结构(Data Structure)是一门研究非数值计算的程序设计问题中操作数据对象及它们之间的关系和操作的学科。 人们对数据结构的研究主要是研究： 一个具体问题的数据之间的结构关系是什么？适宜选用什么样的存储结构？采用什么样的实现算法效率更高？在程序设计中， 数据结构将程序和数据组成有机的整体。 数据元素之间的结构关系一般有以下几种基本形式：集合、线性结构、树形结构和图形结构。（1）集合：集合中的数据元素之间除了存在一个“属于同一集合”的关系外，没有其他关系存在。这种结构的数据元素之间的关系极为松散，可以用其它结构来表示。（2）线性结构：线性结构中的数据元素之间存在一个一对一的关系。（3）树形结构：结构中的数据元素之间存在一个一对多的关系，表示着分岐和等级的关系。（4）图（网）状结构：结构中的数据元素之间存在多个多对多的关系，表示着复杂的客观世界事物间的关系。图 7.1 为上述几种数据结构的图示。(a)集合(b)线性(c)树(d)图图 7.1 数据元素之间的结构为了使计算机能够解决各类非数值计算问题， 需要首先要对具体问题进行分析， 从中提取出操作对象并找出这些操作对象之间含有的结构关系； 然后研究这种关系的数据在计算机中如何存储， 以及计算机处理这样的关系数据所要进行的操作和实现方法。 先来看如下一个示例。例 7.1 如表 7.1 所示，建立某班级的同学的基本情况表。班级同学的基本情况包括：学号、姓名、性别、出生日期、所在院系、政治面貌等。学号4030805340206112姓名贾亮李寒光性别男男出生日期83/03/0582/12/12所在院系语言学院法学院政治面貌团员团员表 7.1 学生基本情况表问题分析： 1 每一个同学的数据为一条记录，每一条记录包括学号、姓名、性别、出生日期、所在院系、政治面貌六个数据项， 每个同学的每个数据项之间存在着一对一的线性关系。 称所有同学的每个数据项之间存在的这种一对一的线性关系构成了一种数据结构线性表。 2 要求对于线性表上能够实现插入、 删除一条记录的操作， 则插入和删除操作就构成了该线性表的操作集合。 3 对于线性表的存储可以采用两种不同的存储结构：顺序存储和单链存储。顺序存储： 采用连续的一段存储器空间存储数据元素并体现其逻辑关系,如图 7.2 所示。a1a2aiai+1an图 7.2 线性表的顺序存储结构顺序存储线性表是用数据元素在机内的物理位置上的相邻关系来表示数据元素之间逻辑上的相邻关系，只要确定了起始位置， 线性表中的任意数据元素都可以随机存取。 顺序存储结构只需存放数据元素自身的信息， 所以存储密度大，空间利用率高，但是在线性表中实现插入和删除操作时不是十分方便。通常用程序设计语言中的数组来实现线性表的顺序存储。如上例所示,将所有的记录依次存放在一个数组中：数组下标01学号4030805340206112姓名贾亮李寒光性别男男出生日期83/03/0582/12/12所在院系语言学院法学院政治面貌团员团员单链存储：将数据元素所占存储单元分作两部分， 一部分存储其值，另一部分存放表示数据元素之间的关系的指针。如图7.3 所示。ABC图 7.3线性表的链式存储线性表的链式存储克服了线性表的顺序存储结构的一些不足， 可以采用任意的存储单元（可以是连续的也可以是不连续的） 存储各数据元素。 在链式存储中的数据元素逻辑上相邻的元素在实际存储时物理位置上不一定要相邻。如上例所示将每一个记录看作是一个结点，让所有的结点依次勾链：Head40308053贾亮男83/03/05语言团员Next40206112李寒男83/12/12语言团员Next图 7.4线性表的链式存储示例所有的记录可以存放在一个连续的存储空间上， 也可以存放在几个不连续的空间上。 系统可以根据上一个记录的地址找到下一个记录的地址，从而实现相关的操作。在线性表中，根据所选用的数据存储方式的不同，则实现相应操作的算法就不相同。2 2算法算法算法(Algorithm)和数据结构有着密切的联系。用计算机解题涉及两大类算法。第一类是数值计算，第二类是非数值计算。通过前面的介绍大家已经知道， 数据结构是一门研究非数值计算的程序设计问题中操作数据对象及它们之间的关系和操作的学科。 完成对数据对象之间的关系的存储和操作的实现都需要涉及到算法， 著名的计算机科学家沃思提出了一个著名的公式：数据结构算法程序设计由此可见，要设计出一个好的计算机程序，很大程度上取决于设计出一个好的算法。算法其实就是解决问题的办法，是一种计算逻辑，是对特定问题求解步骤的一种描述，它是指令的有限序列， 其中每一条指令表示一个或多个操作。 计算机程序就是用计算机语言表述的算法，流程图就是图形化的算法， 甚至一个公式也叫做算法。通常， 作为一个完整的算法应该具有下列性质：（1）有穷性：每条指令必须在有穷的次数和时间内完成。（2）确定性：每一条指令的含义必须明确，无二义性。（3）可行性：每一条指令必须可以执行并且有正确的结果。（4）输入：一个算法可以有零个或多个输入，这些输入取自于特定的对象集合。（5）输出：一个算法至少要有一个输出，这些输出与输入有某些特定的联系。算法设计可以避开具体的语言进行，但实现必须借助某种形式的语言进行描述。3 3算法的设计目标算法的设计目标当人们在应用计算机解决一个具体问题时， 需要对具体问题进行分析， 设计出实现的算法。设计的算法应该满足以下几个目标：（1）正确性：有四层含义，不含语法错误；对几组数据运行正确；对典型、苛刻数据运行正确；对所有数据运行正确。（2）可读性：易于人们的阅读和理解。（3）健壮性：当输入非法数据时，算法也能作出适当的反应，不会出现莫名其妙的输出结果。（4）高效率与低存储量需求：算法的执行时间要短，占用的存储空间要小。4 4算法的效率度量算法的效率度量当人们设计出一个算法后， 需要有一种标准来判断此算法的优劣。 其中，算法的时间复杂度是衡量一个算法实现效率的重要指标。算法的时间复杂度指的是在给定的问题规模n下，算法中语句重复执行次数的数量级， 记作 O(f(n)，其中 f(n)表示基本操作的重复执行次数。例 7.2求两个 nn 矩阵 A 和 B 相乘，结果存在 C 矩阵for(i=1;i=n;i+) for(j=1;j=n;j+) Cij=0; for(k=1;k=n;k+) Cij+=Aik*Bkj; 此算法的问题规模为 n，基本操作的执行次数f(n) n n n，因此，本算法的时间复3杂度是 O(n )。