计算机软件开发第9讲.ppt

16:45,1,第4章 计算机软件系统(回顾),4.1 软件概述 4.2 操作系统概述 4.3 操作系统的功能 4.4 常见操作系统 4.5 应用软件,16:45,2,第 5 章 计算机软件开发 (第8、9讲),讲授：黄瑞兴,16:45,3,第 5 章 计算机软件开发,5.1 算法与数据结构 5.2 程序设计的基本概念 5.3 结构化程序设计 5.4 面向对象程序设计 5.5 软件工程 5.6 数据库系统概述,16:45,4,5.1 算法与数据结构,算法与数据结构是计算机程序的两个最基本的概念。瑞士著名计算机科学家尼可莱沃思在1976年曾提出算法与数据结构二者的关系： 算法+数据结构=程序 准确地说，一个程序规定了某个数据结构上的一个算法。,失算,起床,穿衣,冲凉,吃饭,上课,16:45,5,5.1.1 算法的基本概念,“算法(algorithms)”是什么？ 韦氏新世界词典将“算法”定义为：解决某种问题的任何专门的方法。 如公元前300年欧几里得在其著作几何原本中关于求两个数的最大公约数的辗转相除法就是著名的欧几里德算法。,16:45,6,欧几里德算法,给定两个正整数m和n求它们的最大公因子(即能同时整除m 和n 的最大正整数)步骤： 以n除m并令所得余数为r，r必小于n； 若r=0算法结束，输出结果n ，否则继续步骤3； 将n置换为m，r置换为n并返回步骤1。 欧几里德算法既表述了一个数的求解过程，同时又表述了一个判定过程。,16:45,7,汉诺塔问题,每次只能移动一个盘子 只能在三根柱子上移动，不能放在其他地方 移动时必须始终保持大盘在下，小盘在上 当这64个盘子全部移到第三根柱子上，世界末日就要到了。 汉诺塔问题只能用递归方法而不能用其他方法来求解。所谓递归就是将一个较大的问题归结为一个或多个比原问题简单，且在结构上与原问题相同的子问题的求解方法。,16:45,8,5.1.1 算法的基本概念,著名计算机科学家克努特把算法的性质归纳为 有穷性：算法必须在执行有限步之后结束。即必须在有限时间内完成。 确定性：算法中的每个步骤都必须有明确的定义，不允许存在多义性和模棱两可。 能行性：算法中描述的每步操作都应是可执行的。例如，当B0时A/B 就无法执行，不符合能行性的要求。 输入：一个算法必须有0个(自动生成初始数据)或多个输入。 输出：一个算法必须产生一个或多个输出,16:45,9,自然语言是人们日常所用的语言，如英语、汉语等 优点：自然语言所描述的算法通俗易懂、灵活自由。 缺点：歧义性，容易导致算法执行的不确定性；串行性，一个算法中循环和分支较多时就很难清晰地表示出来；不便转换成用计算机程序设计语言表示。,5.1.2 算法的表示-自然语言,16:45,10,流程图是采用一些的图框符号来描述算法的逻辑结构，每个图框符号表示不同性质的操作。ANSI在上世纪60年代颁布流程图的标准，规定用来表示程序中各种操作的流程图符号。,5.1.2 算法的表示-流程图,起止框,输入/ 输出框,判断框,处理框,16:45,11,5.1.2 算法的表示,例3.2 求5! 步骤1: 令p1 步骤2: 令i2 步骤3: 使pXi，成绩依然存入p中，可表示为ppxi 步骤4: 使i的值加1，可表示为ii1 步骤5: 如果i5，则返回步骤3的位置，从步骤3开始再次执行本算法。 如果i5，则算法结束。,流程图,开始,i5,p 1,i2,p p x i,i i1,结束,F,T,16:45,12,伪代码是一种非正式的语言，它是用介于自然语言和计算机语言之间的文字和符号来描述算法 比真正的程序代码更简明，更贴近自然语言 书写方便、格式紧凑、易于理解，便于转化为计算机语言算法（即程序）,5.1.2 算法的表示伪代码,16:45,13,5.1.2 算法的表示,用伪代码表示例3.2 求5!的算法 Begin 置 p的初值为1 置 i 的初值为2 while i 5 p p x i i i + 1 endwhile 打印p的值 End,16:45,14,5.1.3 数据结构的基本概念,数据：是描述客观事物的数字、字符及所有能输入到计算机中并被计算机程序处理的符号的集合。 数据元素：组成数据的基本单位称为数据元素。通常将数据元素作为一个整体进行处理。数据元素由若干个数据项组成，称数据元素为记录。 数据项是数据的不可分割的最小单位。最简单的数据元素仅含有一个数据项。,16:45,15,5.1.3 数据结构的基本概念,数据结构：是指数据之间的相互关系，即数据的组织形式。 数据结构的研究内容： 程序设计中计算机所操作的对象及相互间的关系和运算，即数据的逻辑结构、存储结构以及数据结构的运算。 数据的逻辑结构是指数据元素之间的逻辑关系。逻辑结构有：线性结构、树形结构和图状结构（或称网状结构）。,16:45,16,5.1.3 数据结构的基本概念,数据的存储结构是指数据在存储器中的存储方式。 顺序存储结构借助元素在存储器中的相对位置来表示数据元素的逻辑关系 链式存储结构借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。,16:45,17,数据结构的基本运算（操作）, 建立数据结构 撤消数据结构 插入数据元素。在一个给定的数据结构中，在指定位置上增添一个新的元素。 删除数据元素。对一个给定的数据结构，删除某个指定节点。 更新数据元素。在一个给定的数据结构中，改变某个元素的值，它等于插入和删除两个操作的组合。,16:45,18,数据结构的基本运算（操作）, 查找数据元素。在一个给定的数据结构中，找出满足指定条件的元素。 排序。对给定的数据结构中的所有的元素按照一定的条件将它们重新排列顺序 遍历。在一个给定的数据结构中，从第一个结点开始，依次访问各个结点。每个结点只能被访问一次。 判定某个数据结构是否为空或是否已达到最大允许的容量。 统计数据元素的个数。,16:45,19,5.1.3 数据结构的基本概念,学习数据结构的目的,可简化算法,节省空间,提高效率,程序设计中选择适当的数据结构,16:45,20,5.1.4 线性表,定义：线性表的逻辑结构是n个数据元素的有限序列：（a 1 , a 2 , a 3 , , a n ） 逻辑结构特征：数据元素之间呈线性关系 第1个：无前驱，有1个后继； 最后一个：有1个前驱，无后继； 其它：有1个前驱，有1个后继。 存储结构，一类是顺序 (静态存储结构)，另一类是链式 (动态存储结构),除书上所列举的26个英文字母、0-9数字字符组成线性表。 还能举出其他的线性表吗？,16:45,21,5.1.4 线性表,顺序存储结构线性表的插入、删除过程,15,18,22,25,26,29,11,12,16:45,22,5.1.4 线性表,顺序存储结构线性表的插入、删除过程,15,18,22,25,26,29,11,12,20,16:45,23,5.1.4 线性表,顺序存储结构线性表的插入、删除过程,11,16:45,24,5.1.4 线性表,链式存储线性表的插入、删除,插入c,删除d,16:45,25,5.1.5 栈与队列,栈是限定仅在表尾进行插入和删除操作的线性表。因此，对栈来说，表尾端有其特殊的含义，称为栈顶，相应的表头端称为栈底。不含元素的空表称为空栈 栈又称后进先出(Last In First Out)的线性表，简称LIFO。,16:45,26,5.1.5 栈与队列,栈的示意图,栈底,栈顶,进栈,出栈,a1,a2,an-1,an,16:45,27,5.1.5 栈与队列,栈顶指针和数据元素间的关系,A,B,C,D,E,16:45,28,5.1.5 栈与队列,栈的链式存储结构链栈示意图,栈顶指针,栈顶,栈底,16:45,29,5.1.5 栈与队列,队列是一种先进先出(First In First Out)的线性表，简称为FIFO。 队列只允许在表的一端进行插入操作，而在表的另一端进行删除操作。 允许插入元素的表端称为队尾，允许删除元素的表端称为队头。 类似于日常生活中的排队，删除元素从队头进行、插入元素从队尾进行，最早进入队列的元素最早离开。,16:45,30,5.1.5 栈与队列,队列示意图,a1,a2,an,队头,队尾,入队列,出队列,16:45,31,5.1.6 树与图,树：非线性结构（有树和二叉树）。非空树有且仅有一个根结点。结点拥有子结点的个数称结点的度。,A,B,F,L,K,E,D,G,H,I,J,M,C,层次,1,2,3,4,ABC的度是多少？,16:45,32,5.1.6 树与图,图：数据元素之间的关系可以是任意的,1,3,2,1,4,5,2,6,有向图,无向图,4,16:45,33,5.1.7 算法的设计,算法的设计目标 正确性：能无误地处理合法输入数据，得到满足要求的结果。 可读性：便于人们阅读和交流。 健壮性：对非法输入的数据能作出适当的反应和处理。 效率与存储量：衡量算法的执行时间及所需的最大存储空间。,16:45,34,5.1.7 算法的设计,算法设计的基本策略思想 分割求解法：把一个大问题划分为原问题的较小子问题，先求出各子问题的解答，然后把各子问题的解答合并成整个问题的解。 动态规划法：对所有的子问题都进行解答，每个子问题的解决依赖于一系列子问题的结果。如何找出后面的子问题，要依赖于前面一系列子问题的递推关系式，这就是动态规划策略的核心。,16:45,35,5.1.7 算法的设计,算法设计的基本策略思想 子目标法(倒推法)：从某个已知的特定解出发，反过来求这个解与已知条件之间存在的关系，以得到一般解的方法 图的搜索法：把问题的求解过程用图或树这种结构来描述。 回溯法：先试一试某一操作，如果以后发现这个操作不适合，则允许退回去，另选一个操作来进行。本质是一种搜索算法。,16:45,36,习题,(p69) 1. 什么是算法，算法应具备哪些特性，为什么？ (p70) 3. 几种常用的算法表示方法是什么，各有什么特点？ 10. 试比较线性表、栈和队列三种数据结构。 14. 好的算法应满足哪些主要的设计目标？,16:45,37,5.2 程序设计的基本概念,什么是程序设计Programming？ 程序设计是给出解决特定问题程序的过程，是指设计、编制、调试程序的方法和过程。是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。 程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。专业的程序设计人员常被称为程序员。,16:45,38,5.2 程序设计的基本概念,5.2.1 程序设计语言的分类 机器语言(1GL) 优点：可以被计算机直接理解和执行，执行速度快，且占用内存少。 缺点：通用性差、程序可读性很差、不易于调试和维护。,16:45,39,5.2.1 程序设计语言的分类,汇编语言(2GL) 用助记符表示机器指令操作码和地址码。助记符是一些有意义的英文单词的缩写和符号。如用ADD表示加法addition、用MOV表示数据的传送move等 优点：可用汇编语言写出语句少、质量高、执行速度快的程序 缺点：汇编语言仍是一种面向机器的语言，通用性差。,16:45,40,5.2.1 程序设计语言的分类,高级语言(3GL) 按照一定的“语法规则”构建程序。用英语单词表示的关键字和数学符号组成。简化开发应用程序的过程。高级语言是面向算法过程的语言。即不但要告诉计算机“做什么”，还要告诉计算机“怎么做” 优点：程序表达直观，可读性好，与具体机器无关，便于移植，通用性好,16:45,41,高级语言与翻译系统,通常把用高级语言编写的程序称为源程序，把用二进制代码表示的程序称为机器代码程序或者目标程序. 计算机只能识别和执行由二进制代码组成的机器语言，因此源程序必须经过语言处理程序 翻译成目标程序才能被计算机执行. 具有翻译功能的语言处理程序：编译程序(又称编译器)和解释程序(又称解释器),16:45,42,第四代语言4GL,是一种非过程化的语言。只需说明所要完成的加工和条件，给出输入数据并指明输出形式，就能得到所需结果。 优点：简单易学，编程省时省力，无需很多程序设计知识就能开发应用程序 应用：目前流行的关系型数据库管理系统结构化查询语言SQL，具有数据的查询、定义、操纵和控制功能。如Oracle、Sybase、MS SQL Server、Access等,5.2.1 程序设计语言的分类,16:45,43,非过程化语言,高级语言(过程化语言)解决问题时，必须详细描述解决问题的每一步，既要解决“做什么”，又要解决“怎么做”。 非过程化语言不必描述繁琐的解决问题过程，只需告诉计算机“做什么“而不必指明“怎么做“ 特点：只指定哪些数据被操纵，至于对这些数据要执行哪些操作，以及这些操作是如何执行的，则未被指定。,5.2.1 程序设计语言的分类,16:45,44,5.2.1 程序设计语言的分类,第五代语言5GL 也是非过程化的语言，它们提供了可视化的图形界面来生成源代码。通常第五代语言使用第三代语言或第四代语言的编译程序来转换得到相应的机器语言程序。有些面向对象的开发工具和网页开发工具，如Visual Basic、Visual C+、Java等就属于第五代语言。,16:45,45,程序设计分类,按照结构性质分，有结构化程序设计与非结构化程序设计。前者是指具有结构性的程序设计方法与过程。它具有由基本结构构成复杂结构的层次性，后者反之。 按照用户要求分，有过程式程序设计与非过程式程序设计。前者是指使用过程式程序设计语言的程序设计，后者指非过程式程序设计语言的程序设计。 按照设计的成分性质分，有顺序程序设计、并发程序设计、并行程序设计、分布式程序设计。 按照程序设计风格分，有逻辑式程序设计、函数式程序设计、对象式程序设计。,16:45,46,Java,Delphi,Visual BASIC、C#、C+,C、C+,PASCAL,5.2.2 几种常见的高级语言,COBOL,FORTRAN,BASIC,16:45,47,5.3 结构化程序设计,结构化程序设计的思想：任何程序都只依靠三种基本结构的组合实现：顺序结构、选择结构和循环结构。选择结构又称分支结构。由这三种基本结构组成的程序称为结构化程序 强调程序的结构和可读性，为缓解软件危机作出了重要的贡献,16:45,48,5.3 结构化程序设计,控制结构,表达式,语句1,If语句：单分支结构,表达式,语句1,If-else语句：双分支结构,语句2,F,T,F,T,一位老学者曾经说过：顺续执行的程序都是简单的；程序的复杂性往往都体现在条件判断与循环控制上。,16:45,49,5.3 结构化程序设计,控制结构,表达式,语句,while语句的执行流程,表达式2,计算表达式3,for语句的执行流程,语句,F,T,F,T,计算表达式1,For语句的下一条语句,比较while、for与 do-while,16:45,50,5.3 结构化程序设计,函数是C语言程序的基本组成单位。它不仅可以实现程序的模块化，使程序设计变得简单和直观，提高易读性和可维护性，而且还可以把程序中普通用到的一些计算或操作编成通用的函数，以供随时调用，这样可以大大地减轻程序员的代码工作量。 C语言主函数main() 若干个函数组成 函数可被任意调用；函数调用自己则产生递归,16:45,51,5.3 结构化程序设计,指针point 学习C语言, 如不能用指针编写有效、正确和灵活的程序, 可以认为没有学好C语言 指针、地址、数组及其相互关系是C语言中最有特色的部分。 规范地使用指针, 可使程序达到简单明了 不但要学会如何正确地使用指针, 而且要学会在各种情况下正确地使用指针变量,16:45,52,5.3 结构化程序设计,数组 数组是有序数据的集合。数组中的元素具有相同的数据类型和名字，以不同的下标相区分，称为数组元素。使用数组时，先要进行定义，然后才能使用。,a0,a1,a2,a3,a4,数组a的示意图,16:45,53,5.4 面向对象程序设计,面向对象具有如下优势： 抽象性，能很好地表达任何复杂的数据类型，亦允许用户灵活地定义自己所需的数据类型。 封装性，对象作为编程中的单元，满足模块独立性高的要求，再加上继承性和多态性，更有助于简化大型软件重复定义的模块。 可重用性，大大提高了大型软件的可靠性和开发效率。,16:45,54,什么是面向对象？,Coad和Yourdon给出了一个定义：“面向对象=对象+类+继承+消息” 如果一个软件系统是使用这样4个概念设计和实现的，则认为这个软件系统是面向对象的。 一个面向对象的程序的每一成份应是对象，计算是通过新的对象的建立和对象之间的消息传送来执行的。,16:45,55,对象object,对象是面向对象开发模式的基本成份 每个对象可用它本身的一组属性和它可以执行的一组操作来定义。 属性一般只能通过执行对象的操作来改变。 操作又称为方法或服务，它描述了对象执行的功能，若通过消息传递，还可以为其它对象使用。,16:45,56,类class,类是一组具有相同数据结构和相同操作的对象的集合。 类的定义包括一组数据属性和在数据上的一组合法操作。 类定义可以视为一个具有类似特性与共同行为的对象的模板，可用来产生对象 在一个类中，每个对象都是类的实例 Instance，它们都可使用类中的函数,16:45,57,对象实现了数据与操作的结合,行为Behavior说明这个对象能做什么，就是对象能进行什么操作，由方法或函数描述。 状态State当对象施加方法时对象的反映，通常用数据描述。 标识Identity区别于其它对象标志，每一个对象有唯一的ID。,16:45,58,对象实现了数据与操作的结合(续),改变传统方法中将数据与操作（亦称函数或过程）相分离的做法，实现了将数据与操作封装在对象的统一体中。 对象具有独立性和自治性，其内部状态不受或很少受外界的影响。,16:45,59,每架飞机都是一个具体的对象，如飞豹。,对象与类de示例,16:45,60,抽取飞机共同的特性，形成类： 凡是飞机都能在空中飞行，具有改变飞行方向、控制飞行高度和速度的操作特性； 凡是飞机都有机名、机型、飞行高度、飞行速度等数据，用以描述飞机的结构性能 飞机还有严格的飞 行安全约束规则， 如飞行条件、起 飞与降落条件等。,16:45,61,封装,面向对象编程中模块的基本单元是类。类将数据和处理数据的过程封装为一个有机的整体。 相比之下，面向过程编程中模块的基本单元是过程，数据处理在过程中进行，通过给函数传递参数然后获得一个函数返回值。,16:45,62,概念封装和信息隐蔽,概念封装和信息隐蔽，使得类具有更大的独立性。在任一时刻都可以在类的界面上增加新的操作，并能够修改实现，以改进性能，或引入原来设计中没有的新服务 为便于类的调整，应尽量做到定义与实现分离。对一个类的共有界面的实现所做的多次修改不应影响利用它的那些类。,16:45,63,5.4 面向对象程序设计,继承Inheritance 一个类可以有父类superclass，也可以有子类subclass。每个“子类”都可以继承“类”的属性和方法。这种低层类继承高层类的属性和方法就叫做继承 继承是指在类中，基于层次的关系共享属性和操作。一个类可以被细化为子类，每个子类继承父类的所有属性，也可以增加它独有的属性。,16:45,64,类层次的结构继承,16:45,65,5.4 面向对象程序设计,继承,16:45,66,5.5 软件工程software engineering,弗里兹.鲍尔定义：“软件工程是为了经济地获得能够在实际机器上有效运行的可靠软件而建立和使用的一系列完善的工程化原则” 1983年IEEE定义：“软件工程是开发、运行、维护和修复软件的系统方法” “软件”定义：计算机程序、方法、规则、相关的文档资料以及在计算机上运行时所必需的数据。强调工程化重要性,16:45,67,软件工程三要素：方法、工具和过程,方法强调“如何做” 。包括诸如项目计划与估算、需求分析、数据结构、系统总体结构的设计、算法过程的设计、编码、测试以及维护等。 工具为方法提供自动的或半自动的软件支撑环境。计算机辅助软件工程CASE 将各种软件工具、开发机器和一个存放开发过程信息的工程数据库组合成一个软件开发支撑系统，即软件工程环境。,16:45,68,软件工程三要素：方法、工具和过程,过程则是将软件工程的方法和工具综合起来以达到合理、及时地进行计算机软件开发的目的。过程定义了方法使用的顺序、要求交付的文档资料、为保证质量和协调变化所需要的管理、及软件开发各个阶段完成的里程碑。,16:45,69,5.5 软件工程,软件的生命周期的瀑布模型,计划,需求分析,设计,编码,测试,运行维护,16:45,70,演化模型,由于在项目开发的初始阶段人们对软件的需求认识常常不够清晰，因而使得开发项目难于做到一次开发成功，出现返工再开发在所难免，做两次。 第一次只是试验开发，其目标只是在于探索可行性，弄清软件需求； 第二次则在此基础上获得较为满意的软件产品。,16:45,71,螺旋模型,螺旋模型沿着螺线旋转，在四个象限上分别表达四个方面的活动： 制定计划：确定软件目标，选定实施方案，弄清项目开发的限制 风险分析：分析所选方案，考虑如何识别和消除风险