1、第第1212章章 软件技术基础软件技术基础新编大学计算机基础教程1本章节目录本章节目录12.1程序设计概述12.2算法12.3数据结构12.4程序设计方法12.5软件工程212.1 12.1 程序设计概述程序设计概述12.1.1程序设计语言的分类12.1.2程序设计语言的选择12.1.3程序设计的基本过程12.1.4程序设计风格312.1.1 12.1.1 程序设计语言的分类程序设计语言的分类1机器语言2汇编语言3高级语言44GL语言4高级语言高级语言分类分类命令式语言。语义基础是模拟“数据存储/数据操作”的图灵机可计算模型，十分符合现代计算机体系结构的自然实现方式。函数式语言。语义基础是基于
2、数学函数概念的值映射的算子可计算模型，是一种非冯诺伊曼式的程序设计语言，它将计算机运算视为数学上的函数计算，并且避免使用程序状态以及易变对象，非常适合于进行人工智能等工作的计算。典型的函数式语言如Lisp、Haskell、ML、Scheme、F#等。5常用程序设计语言常用程序设计语言（2）常用程序设计语言C语言C+语言C#语言Java语言.Net简介612.1.2 12.1.2 程序设计语言的选择程序设计语言的选择应用领域算法和计算复杂性数据结构的复杂性软件开发方法及运行环境用户需求中关于性能方面的需要软件开发人员的知识水平和心理因素712.1.3 12.1.3 程序设计的基本过程程序设计的基
3、本过程分析要解决的问题，找出运算和变化规律，建立数学模型，明确要实现的功能。选择适合计算机解决问题的最佳方案。依据解决问题的方案确定数据结构和算法。选择合适的程序设计语言编写程序。调试运行程序，达到预期目标。对解决问题整个过程的有关资料进行整理，编写程序使用说明书。812.1.4 12.1.4 程序设计风格程序设计风格1源程序文档化标识符的命名。程序注释。视觉组织。2数据说明数据说明的次序规范化。说明语句中变量安排有序化。使用注释，说明复杂数据的结构。3语句的结构4输入和输出5.追求效率原则912.2 12.2 算法算法12.2.1算法的概念12.2.2算法的特征12.2.3算法的表示12.2
4、.4算法设计的基本方法12.2.5算法评价1012.2.1 12.2.1 算法的算法的概念概念在计算机科学中，算法是描述计算机解决给定问题的有明确意义操作步骤的有限集合。计算机算法一般可分为数值计算算法和非数值计算算法。数值计算算法就是对所给的问题求数值解，如求函数的极限、求方程的根等；非数值计算算法主要是指对数据的处理，如对数据的排序、分类、查找及文字处理、图形图像处理等。1112.2.2 12.2.2 算法的特征算法的特征可行性：算法中描述的操作必须是可执行的，通过有限次基本操作可以实现。确定性：算法的每一步操作，必须有确切的含义，不能有二义性和多义性。有穷性：一个算法必须保证执行有限步骤
5、之后结束。输入：一个算法有零个或多个输入，以描述运算对象的初始情况。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。1212.2.3 12.2.3 算法的算法的表示表示1自然语言【例12-2】用自然语言描述交换两个变量值的算法。设有变量m、n和中间变量t。解决问题的算法如下：输入两个值到变量m和变量n中。将变量m的值赋给中间变量t。将变量n的值赋给变量m。将中间变量t的值赋给变量n。13 2 2传统传统流程图流程图起止框：表示流程开始或结束。输入/输出框：表示输入或输出。处理框：表示对基本处理功能的描述。判断框：根据条件是否满足，在几个可以选择的路径中，选择某一路径。流向线、：表
6、示流程的路径和方向。连接点：用于将画在不同地方的流程线连接起来。14【例12-4】用传统流程图描述sum135+99的算法153 3N-SN-S图图【例12-5】用N-S图描述sum135+99的算法，如图12-3所示。16sum0n1当n100时sumsum+nnn+2输出sum的值4 4伪代码伪代码【例12-6】用伪代码描述sum135+99的算法。BEGINsum=0n=1FORn=1TO100STEP2sum=sum+nENDFORPRINTsumEND175 5计算机语言计算机语言 【例12-7】用C语言描述sum135+99的算法。#includevoidmain()intn,su
7、m;sum=0;n=1;dosum=sum+n;n+=2;while(n=100);printf(sum=%dn,sum);1812.2.4 12.2.4 算法设计的基本方法算法设计的基本方法1列举法2归纳法3递推法4递归法5回溯法1912.2.5 12.2.5 算法评价算法评价1正确性2健壮性3可读性4时间复杂度5空间复杂度2012.3 12.3 数据结构数据结构12.3.1数据结构的基本概念12.3.2线性结构与非线性结构12.3.3线性表12.3.4栈和队列12.3.5树与二叉树12.3.6查找与排序方法21数据结构主要研究和讨论以下3个方面的问题数据集合中各数据元素之间所固有的逻辑关系
8、，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。2212.3.1 12.3.1 数据结构的基本概念数据结构的基本概念1数据数据是描述客观事物的所有能输入到计算机中并被计算机程序处理的符号的总称。例如数值、字符、声音、图形、图像等。2数据元素数据元素是数据的基本单位，在计算机中通常作为一个整体加以考虑和处理。例如：电话号码簿中的一条记录为一个数据元素，包括了姓名、住址、电话号码等数据项。23Access2010后台视图24Access2010工作界面3数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：电话号码簿就是一个
9、数据对象。4数据类型在高级程序设计语言中，用数据类型来表示操作对象的特性。数据类型与数据结构密切相关，具有相同数据结构的一类数据的全体构成一种数据类型。例如：C语言中的整型、实型、字符型等都是数据类型。5 5数据结构数据结构（1）数据结构的概念数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。一个数据结构有两个要素：一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示：B=(D,R)，其中B表示数据结构，D是数据元素的有限集，R是D上关系的有
10、限集。25（2）数据结构的图形表示一个数据结构可以用二元组表示，也可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的圆表示，一般称之为数据结点，简称为结点。为了进一步表示各数据元素之间的逻辑关系，对于关系R中的每一个二元组，用一条有向线段从前驱结点指向后继结点。2612.3.2 12.3.2 线性结构与非线性结构线性结构与非线性结构如果一个数据结构满足条件：除了第一个和最后一个结点以外的每个结点只有唯一的一个前驱和唯一的一个后继，第一个结点没有前驱，最后一个结点没有后继，则称该数据结构为线性结构；否则，称之为非线性结构。27线性结构的线性结构的四四
11、个基本特征个基本特征：1集合中必存在唯一的一个第一个元素；2集合中必存在唯一的一个最后的元素；3除最后元素之外，其它数据元素均有唯一的后继；4除第一元素之外，其它数据元素均有唯一的前驱。2812.3.3 12.3.3 线性表线性表1线性表定义线性表是由n（n0）个数据元素a1，a2，an组成的一个有限序列，记为（a1，a2，ai，an）。其中，数据元素个数n称为线性表长度，n=0时称此线性表为空表。292 2非空线性表的结构特征非空线性表的结构特征均匀性：线性表的数据元素可以是各种类型的，但对于同一线性表的各数据元素必定具有相同的数据类型。有序性：各数据元素在线性表中的位置只取决于它的序号，数
12、据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”的数据元素，除了第一个和最后一个外，其他元素均只有一个直接前驱和直接后继。303 3线性表的顺序存储结构线性表的顺序存储结构在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序表。线性表在顺序存储结构中具有以下两个基本特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的；3112.3.4 12.3.4 栈和队列栈和队列1栈（1）栈的定义栈（stack）是一种特殊的线性表，这种线性表上的插入与删除运算限定在表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入与删除
13、元素操作；另一端是开口的，允许插入与删除元素操作。在顺序存储结构下，对这种类型线性表的插入与删除运算不需要移动表中其他数据元素。3233（2 2）栈的运算）栈的运算：入栈运算：是指在栈顶位置插入一个新元素。出栈运算：是指取出栈顶元素并赋给一个指定的变量。读栈顶元素：是指将栈顶元素赋给一个指定的变量。34【例12-10】栈在顺序存储结构下的运算35（a）有4个元素的栈（b）两个元素入栈后的栈（c）一个元素出栈后的栈2 2队列队列队列（queue）是只允许在一端进行插入元素，而在另一端进行删除元素的线性表。这与日常生活中的排队是同理的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾，
14、通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针（front）指向队首元素的位置。36【例【例12-1112-11】队列的入队与出队】队列的入队与出队运算运算37（a）一个队列（b）元素A出队后的队列（c）元素E入队后的队列12.3.5 12.3.5 树与树与二叉树二叉树1.树树（Tree）是一种简单的非线性结构。树中所有数据元素之间的关系具有明显的层次特性，即树是一种层次结构。在用图形表示树时，很像自然界中的树，只不过是一棵倒长的树，因此，这种数据结构就用“树”来命名。38有关树的一些基本特征及基本有关树的一些
15、基本特征及基本术语术语父结点和根结点子结点和叶子结点度层深度子树392.2.二叉树二叉树二叉树（binarytree）是一种特殊的树，它的特点是每个结点最多只有两个子结点，即二叉树中不存在度大于2的结点。40（1 1）二叉树的基本性质）二叉树的基本性质性质1：在二叉树的第k层上，最多有2k-1（k1）个结点。性质2：深度为m的二叉树最多有2m-1个结点。性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个（n0n21）。性质4：具有n个结点的完全二叉树的深度为log2n1，其中log2n表示取log2n的整数部分。41性质5：设完全二叉树共有n个结点。如果从根结点开始
16、，按层序（第一层从左到右）用自然数1，2，n对结点进行编号，则对于编号为k（k1，2，n）的结点有以下结论：若k1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为k/2。若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。若2k1n，则编号为k的结点的右子结点编号为2k1；否则该结点无右子结点。42（2 2）二叉树的）二叉树的遍历遍历前序遍历（DLR）：前序遍历的过程是首先访问根结点，然后遍历左子树、最后遍历右子树。中序遍历（LDR）：中序遍历的过程是首先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历（LRD）：后序遍历的过程是首先
17、遍历左子树，然后遍历右子树，最后访问根结点。4312.3.6 12.3.6 查找与排序查找与排序方法方法1查找顺序查找一般是指从线性表的第一个元素开始，依次将线性表中的元素与给定条件进行比较，若匹配成功，则表示找到（即查找成功）；若线性表中所有的元素都与所给定的条件不匹配，则表示线性表中没有满足条件的元素（即查找失败）。【例12-16】在线性表（36，17，79，86，44，30，34，49，67）中查找元素49和77。44（2 2）二分法）二分法查找查找二分法查找是将被查元素x与线性表查找范围的中间项进行循环比较的查找方法。二分法查找适用于顺序存储的有序线性表，有序表是指线性表中的元素是递增
18、或递减的序列。45【例12-17】在线性表（17，22，30，34，36，44，49，67，79，86，94）中查找元素49和77462 2排序排序（1）选择排序法最简单的选择排序是直接选择排序，以从小到大的顺序排列为例，基本过程如下：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表再从中选出最小的元素，将它交换到子表的第一个位置，如此下去采用同样的方法，直到子表长度为1时即可完成排序。47（2）冒泡排序法冒泡排序法是通过相邻数据元素的比较交换，逐步将线性表由无序变成有序的排序方法。以从小到大的顺序排列为例，冒泡排序法的基本过程如下：（3）插入排序法插入排序法是指将无
19、序序列中的各元素依次插入到已经有序的线性表中。4812.4 12.4 程序设计程序设计方法方法12.4.1结构化程序设计12.4.2面向对象程序设计12.4.3结构化程序设计与面向对象程序设计的比较4912.4.1 12.4.1 结构化程序结构化程序设计设计1结构结构化程序设计的设计思想结构化程序的概念首先是从以往编程过程中无限制地使用转移语句而提出的。如果一个程序中多处出现这种转移情况，会导致程序流程无序可寻，程序结构杂乱无章，这样的程序是令人难以理解和接受的，并且容易出错。在实际软件产品的开发中，更多的追求软件的可读性和可修改性。502 2结构化程序设计的基本结构化程序设计的基本结构结构结
20、构化程序设计具有3种基本结构：顺序结构、选择结构和循环结构。1966年，Boehm和Jacopini证明了任何单入口单出口且没有“死循环”的程序都能利用顺序、选择和循环3种最基本的控制结构构造出来。采用结构化程序设计方法编写程序，可使程序结构清晰、易读、易理解、易维护。51523 3结构化程序设计的结构化程序设计的基本原则基本原则（1）自顶向下（2）逐步求精（3）模块化（4）限制使用goto语句5312.4.2 12.4.2 面向对象程序设计面向对象程序设计1面向对象程序设计的基本概念（1）对象（object）客观世界中任何一个事物都可以看成一个对象。或者说，客观世界是由千千万万对象组成的。对
21、象可以是自然物体（如汽车、房屋），也可以是社会生活中的一种逻辑结构（如班级、连队），一篇文章、一个图形等都可视作对象，对象是构成系统的基本单位。54对象基本对象基本特点：特点：标识唯一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。分类性。指可以将具有相同属性和操作的对象抽象成类。多态性。指同一个操作可以是不同对象的行为。封装性。从外面看只能看到对象的外部特性。55（2 2）类（）类（classclass）将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。所以，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的
22、一个实例。由类的定义可知，类是关于对象性质的描述，它与对象一样，包括一组数据属性和在数据上的一组合法操作。56（3 3）消息（）消息（messagemessage）消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息。消息的使用类似于函数调用，消息中指定了某一个实例、一个操作名和一个参数表。57（4 4）继承（）继承（lnheritancelnheritance）继承是面向对象方法的一个主要特征。继承是使用已有的类（父类）定义作为基础建立新类（子类）的定义。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。58（5 5）多态性（）多态性（polymorp
23、hismpolymorphism）对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。例如：在Windows环境下，用鼠标双击一个文件对象（这就是向对象传送一个消息），如果对象是一个可执行文件，则会执行此程序；如果对象是一个文本文件，则启动文本编辑器并打开该文件。在面向对象的软件技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。592 2面向对象程序设计的思想面向对象程序设计的思想 面向对象程序设计从所处理的数据入手，以数据为中心而不是以服务（功能）为中心来描述系统。它把编程问题视为一个数据集合
24、，数据相对于功能而言，具有更强的稳定性。603 3面向对象程序设计的步骤面向对象程序设计的步骤（1）面向对象分析（ObjectOrientedAnalysis，OOA）（2）面向对象设计（ObjectOrientedDesign，OOD）（3）面向对象编程（ObjectOrientedProgramming，OOP）（4）面向对象测试（ObjectOrientedTest，OOT）（5）面向对象维护（ObjectOrientedSoftMaintenance，OOSM）6112.4.3 12.4.3 结构化程序设计与面向对象程序设结构化程序设计与面向对象程序设计的计的比较比较从概念方面看，结构
25、化软件是功能的集合，通过模块以及模块和模块之间的分层调用关系实现；面向对象软件是事物对象的集合，通过对象以及对象和对象之间的通讯联系实现；从构成方面看，结构化软件是过程和数据的集合，以过程为中心；面向对象软件是数据和相应操作的封装，以对象为中心；62从运行控制方面看，结构化软件采用顺序处理方式，由过程驱动控制；面向对象软件采用交互式、并行处理方式，由消息驱动控制；从开发方面看，结构化方法的工作重点是设计；面向对象方法的工作重点是分析；63从应用方面看，相对而言，结构化方法更加适合数据类型比较简单的数值计算和数据统计管理软件的开发；面向对象方法更加适合大型复杂的人机交互软件的开发。6412.5
26、12.5 软件工程软件工程12.5.1软件工程的基本概念12.5.2软件开发方法(SoftwareDevelopmentMethod)12.5.3软件测试12.5.4软件维护6512.5.1 12.5.1 软件工程的基本软件工程的基本概念概念1软件定义与软件特点软件是一种逻辑实体，具有抽象性。软件没有明显的制造过程。软件在使用过程中，没有磨损、老化的问题。但软件会被废弃。软件对硬件和环境有着不同程度的依赖性。软件的开发至今尚未完全摆脱手工作坊式的开发方式，生产效率低。软件涉及人类社会的各行各业、方方面面，软件开发常常涉及其它领域的专业知识，日益复杂。软件的成本昂贵。软件工作牵涉到很多社会因素。
27、662 2软件危机与软件危机与软件工程软件工程概括来说，软件危机包含两方面问题：如何开发软件，以满足不断增长，日趋复杂的需求；如何维护数量不断膨胀的软件产品。67软件工程就是用工程、科学和数学的原则与方法研制、维护计算机软件的有关技术及管理方法。软件工程学的主要内容是软件开发技术和软件工程管理学。其中，软件开发技术包含了软件开发方法、软件工具和软件工程环境，软件工程管理学包含了软件工程经济学和软件管理学。683 3软件生命周期与开发软件生命周期与开发模型模型（1）软件生命周期69（2 2）软件开发）软件开发模型模型瀑布模型（WaterfallModel）增量模型（IncrementalMode
28、l）螺旋模型（SpiralModel）喷泉模型（FountainModel）智能模型（四代技术4GL）组合模型（HybridModel）704.4.软件工程的目标与软件工程的目标与原则原则（1）软件工程的目标软件工程的目标是在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。追求这些目标有助于提高软件产品的质量和开发效益，降低维护难度。71（2）软件工程的原则抽象信息隐蔽模块化局部化确定性一致性。完备性可验证性725 5软件开发工具与软件开发工具与软件开发环境软件开发环境（1）软件开发工具早期的软件开发
29、除了一般的程序设计语言以外，缺少工具的支持。软件开发工具的发展是从单项工具逐步向集成工具发展的，软件开发工具为软件工程方法提供了自动的或半自动的软件支撑环境。同时，软件开发方法的有效应用也必须得到相应工具的支持，否则方法将难以有效地实施。73（2）软件开发环境按软件开发模型及开发方法分类，有支持瀑布模型、演化模型、螺旋模型、喷泉模型以及结构化方法、信息模型方法、面向对象方法等不同模型及方法的软件开发环境。按功能及结构特点分类，有单体型、协同型、分散型和并发型等多种类型的软件开发环境。按应用范围分类，有通用型和专用型软件开发环境。7412.5.2 12.5.2 软件开发方法软件开发方法(Soft
30、ware(Software Development Method)Development Method)1面向过程的方法面向过程的方法包括面向过程需求分析、面向过程设计、面向过程编程、面向过程测试、面向过程维护、面向过程管理。面向过程方法的特点是：程序的执行过程不由用户控制，完全由程序控制。752面向对象的方法面向对象的方法包括面向对象需求分析、面向对象设计、面向对象编程、面向对象测试、面向对象维护、面向对象管理。面向对象的方法在电子商务中被广泛采用，如网站前台界面的制作、信息的发布和处理、个人网页的制作、用户在网上浏览和录入信息等应用软件都是利用面向对象的方法设计与实现的。763面向数据的方
31、法数据位于企业信息系统的中心。只要企业的业务方向和内容不变，企业的元数据就是稳定的，由元数据构成的数据模型也是稳定的。对元数据的处理方法是可变的。企业信息系统的核心是数据模型。信息系统的实现（编码）方法主要是面向对象，其次才是面向数据和面向过程。自始至终参与信息系统的分析、设计、实现与维护。7712.5.3 12.5.3 软件测试软件测试1测试的目的软件测试是为了发现错误而执行程序的过程，测试要以查找错误为中心，而不是为了演示软件的正确功能。一个好的测试用例在于能发现至今尚未发现的错误，一个成功的测试是发现了至今尚未发现的错误的测试。782测试的方法（1）静态测试（2）动态测试白盒测试：黑盒测
32、试：灰盒测试793测试的策略（1）单元测试（2）集成测试（3）确认测试（4）系统测试804.常用测试工具开源测试管理工具：Bugfree、Bugzilla、TestLink、mantiszentaopms开源功能自动化测试工具：Watir、Selenium、MaxQ、WebInject开源性能自动化测试工具：Jmeter、OpenSTA、DBMonster、TPTEST、WebApplicationLoadSimulator国内免费软件测试工具有：AutoRunner和TestCenter。8112.5.4 12.5.4 软件维护软件维护1传统的软件维护纠错性维护适应性维护完善性维护预防性维护
33、822目前的软件维护目前软件企业一般将自己的软件产品维护活动分为面向缺陷维护（程序级维护）和面向功能维护（设计级维护）两类。面向缺陷维护是较小规模的维护，面向功能维护是较大规模的维护。833软件维护与软件产品版本升级软件维护与软件产品版本升级有一定的关系。软件的版本信息主要有四个值组成：主版本号、次版本号、内部版本号、内部修订号。例如：1.000版。84本章本章小结小结本章介绍了程序设计语言的分类及选择方法，算法的特征与表示方法，数据结构的基本概念，线性表、二叉树的基本操作及查找、排序的常用方法，结构化程序设计的思想，面向对象程序设计的基本概念，介绍了常用的程序设计语言，软件工程的基本概念和开发方法。85本章习题本章习题五、简答题1常用的程序设计语言有哪些？2简述程序设计方法与风格。3结构化程序设计的基本思想是什么？4什么是软件工程？5软件的特点是什么？6简述冒泡排序的基本过程。7结构化程序设计有哪几种基本结构，各自是怎样实现的？试画出相应的结构图。9软件测试的目的是什么？10软件生命周期的主要活动阶段有哪些？11软件工程的3种开发方法是什么？。86
陕公网安备 61072602000132号 违法和不良信息举报：0916-4228922