第5章程序设计基础课件.ppt

1、5.1 程序设计概述程序设计概述5.2 算法概述算法概述5.3 软件工程概述软件工程概述第第5 5章章 程序设计基础程序设计基础5.1.1 程序设计的基本过程程序设计的基本过程5.1.2 程序设计的方法程序设计的方法5.1.3 程序设计语言程序设计语言5.1 程序设计概述程序设计概述5.1.1 程序设计的基本过程程序设计的基本过程w 程序设计：编写程序的过程w 程序设计过程包括分析、设计、编码、测试、编写文档等不同阶段5.1.2 程序设计的方法程序设计的方法w 结构化程序设计方法w 面向对象程序设计方法结构化程序设计结构化程序设计w 结构化程序设计的原则n自顶向下n逐步细化n模块化n限制使用g

2、oto语句结构化程序设计结构化程序设计w 结构化程序设计的基本结构n顺序结构n选择结构n循环结构结构化程序设计结构化程序设计w顺序结构n按照程序语句的书写顺序一条一条的执行n最基本、最常用的结构结构化程序设计结构化程序设计w选择结构（分支结构）n根据设定的条件，判断应该执行哪一条语句n包括单分支结构、双分支结构和多分支结构结构化程序设计结构化程序设计w循环结构（重复结构）n根据给定的条件，判断是否需要重复执行相同的程序段n分为当型循环结构和直到型循环结构 面向对象程序设计面向对象程序设计w 结构化程序设计又称为面向过程的程序设计w 面向对象程序设计方法模拟人们理解和处理客观世界的方式来分析问题

3、，把系统视为一系列对象的集合，分析者、设计者和编程者都可以使用相同的概念，从而使面向对象的程序设计方法能比较自然地模拟客观世界的活动，使问题描述空间与解空间在结构上尽可能一致。面向对象的基本概念面向对象的基本概念w 对象：客观世界中的任何实体，既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界和意义的东西。w 对象的特点：n标识唯一性n分类型n多态性n封装性n模块独立性面向对象程序设计面向对象程序设计w 类：n类是对象的抽象，它描述了该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例w 消息n面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互

4、合作需要一个机制来协助完成，这种机制称为“消息”面向对象程序设计面向对象程序设计w 继承n使用已有的类定义作为基础建立新类的定义技术n已有的类可当做基类来引用，新类可当做派生类来引用n继承具有传递性面向对象程序设计面向对象程序设计w 封装性n所谓封装，指的就是类中定义的数据只能被类中定义的方法所访问，除此之外别无它法n封装的结果实际上隐蔽了复杂性，并提供了代码重用性，从而降低了软件开发的难度。w 多态性n对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时，可导致完全不同的行动，该现象称为多态性面向对象程序设计面向对象程序设计w 面向对象方法的优点：n与人类习惯的思维方法一致n稳定性好

5、n可重用性好n易于开发大型软件产品n可维护性好5.1.3 程序设计语言程序设计语言w 程序设计语言就是用于书写计算机程序的一组记号和一组规则。w 分类：n机器语言n汇编语言n高级语言 由由0 0、1 1代码组成，代码组成，能被计算机硬件系统能被计算机硬件系统直接识别和执行的计算机语言，不需要翻译。直接识别和执行的计算机语言，不需要翻译。 占用空间小、执行速度快占用空间小、执行速度快 不易学习和修改不易学习和修改 不同类型不同类型的机器语言不同，的机器语言不同，通用性差通用性差机器语言程序机器语言程序注释注释10110000 00001000把8存放到累加器A中00101100 00001010

6、将10与累加器中的8相加，结果存在A中11110100程序结束机器语言实例机器语言实例 用助记符代替机器语言中的指令和数据用助记符代替机器语言中的指令和数据易修改，保持速度快，占用空间小易修改，保持速度快，占用空间小不同类型不同类型机器机器的的汇编语言不同，汇编语言不同，通用性差通用性差8+10加法题加法题MOV AX, 8HMOV AX, 8HMOV BX, 0AHMOV BX, 0AHADD BX, AXADD BX, AX 由贴近自然语言的由贴近自然语言的“词词”和和“数学公数学公式式”组成组成 易学、易读，易修改易学、易读，易修改 通用性好，不依赖于机器通用性好，不依赖于机器 具有很强

7、的具有很强的通用性通用性和和可移植性可移植性c=8+10常用的程序设计语言常用的程序设计语言w 面向过程语言nFortran、Pascal、C等w 面向对象语言nC+、java语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行的程序汇编语言汇编语言汇编程序汇编程序高级语言高级语言 高级语言高级语言 编译程序编译程序连接程序连接程序数据数据解释程序解释程序数据数据编译程序：编译程序：执行速度快，但占用内存多，可执行速度快，但占用内存多，可脱离编译程序和源程序独立存在并反复使用脱离编译程序和源程序独立存在并反复使用. .如：如： C/C+C/C+、PascalPascal、FORTRAN

8、FORTRAN等等解释程序：解释程序：边解释边执行，便于查错，占用内边解释边执行，便于查错，占用内存少，执行效率低、速度慢。如：存少，执行效率低、速度慢。如：BASICBASIC语言语言编译程序与解释程序的区别编译程序与解释程序的区别5.2.1 算法的概念算法的概念5.2.2 算法的表示算法的表示5.2.3 常用算法介绍常用算法介绍5.2 算法概述算法概述算法算法算法算法( (AlgorithmAlgorithm) )：算法就是一个有穷规：算法就是一个有穷规则的集合，其中的规则确定了一个解决某则的集合，其中的规则确定了一个解决某一特定类型问题的运算序列。一特定类型问题的运算序列。5.2.1 算

9、法的概念算法的概念算法的特性算法的特性 有限性有限性 确定性确定性 可行性可行性 输入输入 输出输出算法的表示方法算法的表示方法算法的表示方法：算法的表示方法：l自然语言；自然语言；l程序流程图；程序流程图；lN-S流程图；流程图；l伪代码；伪代码；自然语言自然语言w 使用自然语言描述求解sum=1+2+3+4+5+（n-1）+n的方法。 确定一个n的值； 设等号右边的算式项中的初始值i为1； 设sum的初始值为0； 如果in时，执行，否则转出执行； 计算sum加上i的值后，重新赋值给sum； 计算i加1，然后将值重新赋值给i； 转去执行； 输出sum 的值，算法结束。自然语言自然语言w 自然

10、语言描述方法的缺点：n自言语言的歧异性容易导致算法执行的不确定性。n自然语言的语句一般太长，从而导致了用自然语言描述的算法太长。n由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来。n自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。程序流程图程序流程图程程序序流流程程图图符符号号程序流程图程序流程图w 以求解sum=1+2+3+4+5+（n-1）+n为例来介绍算法的流程图描述方法N-S流程图流程图w N-S流程图简称N-S图，也被称为盒图。N-S图是在1973年，由美国学者I.Nassi 和 B.Shneiderman提出来的，并分别取两人名字的首字母来

11、进行命名。N-S图是在程序流程图的基础上去掉流程线，将全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框的一种算法表示方法。即由一些基本的框组成的一个大框。N-S流程图流程图w N-S流程图的三大结构w 顺序结构w 选择结构w 循环结构N-S流程图流程图写出求sum=1+2+3+4+5+（n-1）+n的 N-S图的描述方法伪代码伪代码w 用流程图或N-S图来描述算法虽然形象直观，但在算法设计过程中使用起来并不十分方便，特别是当算法稍微复杂一点时，不易修改。w 在实际的算法设计中，常常使用自然语言或计算机语言或类计算机语言来描述。w 这里的类计算机语言是一种非计算机语言，借用了一些高

12、级语言的某些成分，没有加入严格的规则，而且不能够被计算机所接受，称其为“伪代码”。伪代码伪代码写出求sum=1+2+3+4+5+（n-1）+n的 伪代码的描述方法(1) 算法开始；(2) 输入 n 的值；(3) i 1； (4) sum 0；(5) do while i=n(6) sum sum + i；(7) i i + 1；(8) 输出 sum 的值；(9) 算法结束；5.2.3 常用算法介绍常用算法介绍1.枚举法2.递推法3.求最大值、最小值问题4.交换两个变量的值5.排序算法6.查找算法枚举法又称为穷举法w 基本思想：根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况

13、逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。w 特点：算法简单，容易理解，运算量大1.1.枚举法枚举法1.1.枚举法枚举法应用：百钱买百鸡问题假定公鸡每只5元，母鸡每只3元，小鸡3只1元。现有100元钱要求买100只鸡，问共有几种购鸡方案？w 问题分析：根据题目，设公鸡、母鸡、小鸡各为x，y，z只，列出方程为：x+y+z=1005x+3y+z/3=100w 巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是一种重要的算法设计策略：穷举法几乎可以通用于任何领域的问题求解，可能是唯一一种解决所有问题的一般

14、性方法即使效率低下，仍可用穷举法求解一些小规模的问题实例；如果解决的问题实例不多，而穷举法可用一种可接受的速度对问题求解，那么花时间去设计一个更高效地算法是得不偿失的。 1.1.枚举法枚举法 思考题思考题 举例说明生活中的穷举法应用。举例说明生活中的穷举法应用。递推法又称为迭代法w 基本思想：利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。2.2.递推法递推法2.2.递推法递推法w w 基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为最大值，称

15、为擂主，依次同第2，3，n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。求最小值问题则先假设第一个数为最小值。3.3.求最大值、最小值问题求最大值、最小值问题3.3.求最大值、最小值问题求最大值、最小值问题应用：对输入的若干个学生成绩，求出最高分和最低分。w max=min=a0；w 用max依次与后续的成绩进行对比，若比max大则将相应值赋值给max；w 用min依次与后续的成绩进行对比，若比min小则将相应值赋值给min；w 最后输出max和min的值。w 基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的值只能采取间接交换的方法。4.4.交换两个变量

16、的值交换两个变量的值4.4.交换两个变量的值交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝墨水的瓶子里，而把蓝墨水错装在了黑墨水瓶子里，要求将其互换。4.4.交换两个变量的值交换两个变量的值应用：a=5, b=10，交换a，b的值并输出w 引入一个新的变量c；w 将a的值赋值给c；w 将b的值赋值给a；w 将c的值赋值给b；w 选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记录与第i个位置的记录进行交换，也即第一轮从n个记录中选取关键码最小的记录与第1个位置的记录交换，第二轮从剩下的n-1个记录中选取关键码最小的记录与第2个位置的记录进行交换，直到整个序列的记录选完5.5

17、.排序算法排序算法5.5.排序算法排序算法【例5.6】给出一组关键字(28，6，72，85，39，41，13，20)，排序后得到(6，13，20，28，39，41，72，85)，其选择排序过程如下w 查找是指从给定的数据结构中查找某个给定的值。w 常用的查找算法有顺序查找、二分查找等等。w 顺序查找是直接从头到尾搜索集合中满足条件的值。w 二分查找是必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合中满足条件的值。6.6.查找算法查找算法6.6.查找算法查找算法二分查找的方法如下：w 将x与线性表的中间项进行比较；w 若中间项的值等于x，则说明查找到，查找结束；w 若x小于中间项的值，

18、则在线性表的前半部分以相同的方法进行查找。w 若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找。w 这个过程一直进行到查找成功或子表长度为0为止。【例5.7】有序表中关键字序列为3，10，13，17，40，43，50，70，要查找关键字值为43的数据元素6.6.查找算法查找算法5.3.1 软件危机软件危机5.3.2 软件工程软件工程5.3.3 软件生存周期软件生存周期5.3 软件工程概述软件工程概述5.3.1 软件危机软件危机w 软件危机是指在计算机软件的开发和维护过程中所遇到的一系列严重问题，主要有以下一些表现形式。软件开发费用和进度失控。软件的可靠性差。生产出来的软件难以维护。

19、用户对“已完成”的系统不满意现象经常发生。5.3.2 软件工程软件工程w IEEE给出的软件工程的定义是：软件工程是将系统化的、规范的、可度量的方法应用于软件的开发、运行、维护过程，即将工程化应用于软件中的方法的研究。w 人们给出的一般定义是：软件工程是一门旨在生产无故障的、积极交付的、在预算之内的和满足用户需求的软件的学科。实质上，软件工程就是采用工程的概念、原理、技术和方法来开发与维护软件，把经过实践考验而证明正确的管理方法和最先进的软件开发技术结合起来，应用到软件开发和维护过程中，来解决软件危机问题。5.3.2 软件工程软件工程w 软件工程包括三要素：方法、工具和过程。w 软件工程的目标

20、是：在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性并且满足用户需求的软件产品。追求这些目标有助于提高软件产品的质量和开发效率，减少维护的困难w 软件工程的原则：抽象、信息隐藏、模块化、局部化、一致性、确定性、完备性和可验证性5.3.3 软件生存周期软件生存周期软件过程模型软件过程模型w 定义：从软件项目需求定义直至软件运行定义：从软件项目需求定义直至软件运行维护为止，跨越整个生存期的系统开发、维护为止，跨越整个生存期的系统开发、运作和维护所实施的全部过程、活动和任运作和维护所实施的全部过程、活动和任务的结构框

21、架。务的结构框架。w 常见的软件过程模型：常见的软件过程模型：n瀑布模型瀑布模型n原型模型原型模型n增量模型增量模型n螺旋模型螺旋模型瀑布模型（瀑布模型（Waterfall Model）w 19701970年提出，又称年提出，又称线性模型线性模型，是历史上第一个，是历史上第一个正式使用并得到业界广泛认可的软件开发模型正式使用并得到业界广泛认可的软件开发模型w 具体划分：具体划分：n制定计划、需求分析、软件设计、程序编写制定计划、需求分析、软件设计、程序编写、软件测试、运行维护、软件测试、运行维护n规定了自上而下、相互衔接的固定次序规定了自上而下、相互衔接的固定次序原型模型原型模型w 原型模型的基本思想是：原型模型从需求采集开始，如图所示，然后是“快速设计”，集中于软件中那些对用户可见的部分的表示，并最终导致原型的创建。 螺旋模型螺旋模型w 1988年由TRW公司的B.Boehm提出，将瀑布模型和演化模型结合，并强调了其他模型都忽略了的风险分析。并发模型并发模型w 并发模型也称并发工程，它表达了在软件项目任一阶段的活动之间存在的并发性。基于构件的开发模型基于构件的开发模型w 基于构件的开发（CBD）模型（如图5.18所示）融合了螺旋模型的许多特征，本质上是演化型的，要求软件创建迭代过程，但是基于构件的开发模型是利用预先封装好的软件构件来构造应用的。小 结