第5章-程序设计基础课件

5.1程序设计概述程序设计概述5.2算法概述算法概述5.3软件工程概述软件工程概述第第第第5 5 5 5章章章章 程序设计基础程序设计基础程序设计基础程序设计基础5.1程序设计概述第程序设计概述第5章章程序设计基础程序设计基础5.1.1 程序设计的基本过程程序设计的基本过程5.1.2 程序设计的方法程序设计的方法5.1.3 程序设计语言程序设计语言5.1程序程序设计概述概述5.1.1程序设计的基本过程程序设计的基本过程5.1程序设计概述程序设计概述5.1.1程序程序设计的基本的基本过程程w程序设计：编写程序的过程w程序设计过程包括分析、设计、编码、测试、编写文档等不同阶段5.1.1程序设计的基本过程程序设计：编写程序的过程程序设计的基本过程程序设计：编写程序的过程5.1.2程序程序设计的方法的方法w结构化程序设计方法w面向对象程序设计方法5.1.2程序设计的方法结构化程序设计方法程序设计的方法结构化程序设计方法结构化程序设计结构化程序设计w结构化程序设计的原则n自顶向下n逐步细化n模块化n限制使用goto语句结构化程序设计结构化程序设计的原则结构化程序设计结构化程序设计的原则结构化程序设计结构化程序设计w结构化程序设计的基本结构n顺序结构n选择结构n循环结构结构化程序设计结构化程序设计的基本结构结构化程序设计结构化程序设计的基本结构结构化程序设计结构化程序设计w顺序结构n按照程序语句的书写顺序一条一条的执行n最基本、最常用的结构结构化程序设计顺序结构结构化程序设计顺序结构结构化程序设计结构化程序设计w选择结构（分支结构）n根据设定的条件，判断应该执行哪一条语句n包括单分支结构、双分支结构和多分支结构结构化程序设计选择结构（分支结构）结构化程序设计选择结构（分支结构）结构化程序设计结构化程序设计w循环结构（重复结构）n根据给定的条件，判断是否需要重复执行相同的程序段n分为当型循环结构和直到型循环结构 结构化程序设计循环结构（重复结构）结构化程序设计循环结构（重复结构）面向对象程序设计面向对象程序设计w结构化程序设计又称为面向过程的程序设计w面向对象程序设计方法模拟人们理解和处理客观世界的方式来分析问题，把系统视为一系列对象的集合，分析者、设计者和编程者都可以使用相同的概念，从而使面向对象的程序设计方法能比较自然地模拟客观世界的活动，使问题描述空间与解空间在结构上尽可能一致。面向对象程序设计结构化程序设计又称为面向过程的程序设计面向对象程序设计结构化程序设计又称为面向过程的程序设计面向对象的基本概念面向对象的基本概念w对象：客观世界中的任何实体，既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界和意义的东西。w对象的特点：n标识唯一性n分类型n多态性n封装性n模块独立性面向对象的基本概念对象：客观世界中的任何实体，既可以是具体的面向对象的基本概念对象：客观世界中的任何实体，既可以是具体的面向对象程序设计面向对象程序设计w类：n类是对象的抽象，它描述了该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例w消息n面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制来协助完成，这种机制称为“消息”面向对象程序设计类：面向对象程序设计类：面向对象程序设计面向对象程序设计w继承n使用已有的类定义作为基础建立新类的定义技术n已有的类可当做基类来引用，新类可当做派生类来引用n继承具有传递性面向对象程序设计继承面向对象程序设计继承面向对象程序设计面向对象程序设计w封装性n所谓封装，指的就是类中定义的数据只能被类中定义的方法所访问，除此之外别无它法n封装的结果实际上隐蔽了复杂性，并提供了代码重用性，从而降低了软件开发的难度。w多态性n对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时，可导致完全不同的行动，该现象称为多态性面向对象程序设计封装性面向对象程序设计封装性面向对象程序设计面向对象程序设计w面向对象方法的优点：n与人类习惯的思维方法一致n稳定性好n可重用性好n易于开发大型软件产品n可维护性好面向对象程序设计面向对象方法的优点：面向对象程序设计面向对象方法的优点：5.1.3程序设计语言程序设计语言w程序设计语言就是用于书写计算机程序的一组记号和一组规则。w分类：n机器语言n汇编语言n高级语言5.1.3程序设计语言程序设计语言就是用于书写计算机程序的程序设计语言程序设计语言就是用于书写计算机程序的(1)(1)机器语言机器语言 由由0 0、1 1代码组成，代码组成，能被计算机硬件系统能被计算机硬件系统直接识别和执行的计算机语言，不需要翻译。直接识别和执行的计算机语言，不需要翻译。特点特点：占用空间小、执行速度快占用空间小、执行速度快不易学习和修改不易学习和修改不同类型不同类型机器机器的机器语言不同，的机器语言不同，通用性差通用性差程序设计语言程序设计语言(1)机器语言机器语言由由0、1代码组成，能被计算机硬件系统直代码组成，能被计算机硬件系统直机器语言程序机器语言程序注释注释1011000000001000把8存放到累加器A中0010110000001010将10与累加器中的8相加，结果存在A中11110100程序结束机器语言实例机器语言实例机器语言程序注释机器语言程序注释1011000000001000把把8存放到存放到(2)(2)汇编语言（符号语言）汇编语言（符号语言）程序设计语言程序设计语言 用助记符代替机器语言中的指令和数据用助记符代替机器语言中的指令和数据特点：特点：易修改，保持速度快，占用空间小易修改，保持速度快，占用空间小不同类型不同类型机器机器的的汇编语言不同，汇编语言不同，通用性差通用性差实例：实例：8+10加法题加法题MOV AX,8HMOV AX,8HMOV BX,0AHMOV BX,0AHADD BX,AXADD BX,AX(2)汇编语言（符号语言）程序设计语言汇编语言（符号语言）程序设计语言用助记符代替机器语用助记符代替机器语(3)(3)高级语言高级语言程序设计语言程序设计语言 由贴近自然语言的由贴近自然语言的“词词”和和“数学公数学公式式”组成组成特点：特点：易学、易读，易修改易学、易读，易修改通用性好，不依赖于机器通用性好，不依赖于机器具有很强的具有很强的通用性通用性和和可移植性可移植性实例：实例：c=8+10(3)高级语言程序设计语言高级语言程序设计语言由贴近自然语言的由贴近自然语言的“词词”和和“常用的程序设计语言常用的程序设计语言w面向过程语言nFortran、Pascal、C等w面向对象语言nC+、java常用的程序设计语言面向过程语言常用的程序设计语言面向过程语言语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行的程序分类汇编程序编译程序解释程序程序设计语言处理系统程序设计语言处理系统语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行汇编语言汇编语言源程序源程序 机器语言程序机器语言程序汇编程序汇编程序 汇编程序汇编程序程序设计语言处理系统程序设计语言处理系统汇编程序汇编程序汇编程序程序设计语言处理系统汇编程序程序设计语言处理系统高级语言高级语言 源程序源程序源程序源程序 高级语言高级语言 目标目标目标目标源程序源程序源程序源程序 程序程序程序程序编译程序编译程序连接程序连接程序可执行可执行可执行可执行程序程序程序程序计算计算计算计算结果结果结果结果数据数据解释程序解释程序计算计算计算计算结果结果结果结果数据数据编译程序：编译程序：执行速度快，但占用内存多，可执行速度快，但占用内存多，可脱离编译程序和源程序独立存在并反复使用脱离编译程序和源程序独立存在并反复使用.如：如：C/C+C/C+、PascalPascal、FORTRANFORTRAN等等解释程序：解释程序：边解释边执行，便于查错，占用内边解释边执行，便于查错，占用内存少，执行效率低、速度慢。如：存少，执行效率低、速度慢。如：BASICBASIC语言语言程序设计语言处理系统程序设计语言处理系统编译程序连接程序可执行计算数据解释程序计算数据编译程序：执行编译程序连接程序可执行计算数据解释程序计算数据编译程序：执行编译程序与解释程序的区别编译程序与解释程序的区别编译程序与解释程序的区别编译程序与解释程序的区别5.2.1 算法的概念算法的概念5.2.2 算法的表示算法的表示5.2.3 常用算法介绍常用算法介绍5.2算法概述算法概述5.2.1算法的概念算法的概念5.2算法概述算法概述算法算法算法算法(AlgorithmAlgorithm)：算法就是一个有穷规：算法就是一个有穷规则的集合，其中的规则确定了一个解决某则的集合，其中的规则确定了一个解决某一特定类型问题的运算序列。一特定类型问题的运算序列。5.2.1算法的概念算法的概念算法算法5.2.1算法的概念算法的概念算法的特性算法的特性 有限性有限性 确定性确定性 可行性可行性 输入输入 输出输出算法的特性算法的特性有限性有限性算法的表示方法算法的表示方法算法的表示方法：算法的表示方法：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的值，算法结束。自然语言使用自然语言描述求解自然语言使用自然语言描述求解sum=1+2+3+4+5+自然语言自然语言w自然语言描述方法的缺点：n自言语言的歧异性容易导致算法执行的不确定性。n自然语言的语句一般太长，从而导致了用自然语言描述的算法太长。n由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来。n自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。自然语言自然语言描述方法的缺点：自然语言自然语言描述方法的缺点：程序流程图程序流程图程程序序流流程程图图符符号号程序流程图程序流程图符号程序流程图程序流程图符号程序流程图程序流程图w以求解sum=1+2+3+4+5+（n-1）+n为例来介绍算法的流程图描述方法程序流程图以求解程序流程图以求解sum=1+2+3+4+5+（n-1）+N-S流程图流程图wN-S流程图简称N-S图，也被称为盒图。N-S图是在1973年，由美国学者I.Nassi和B.Shneiderman提出来的，并分别取两人名字的首字母来进行命名。N-S图是在程序流程图的基础上去掉流程线，将全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框的一种算法表示方法。即由一些基本的框组成的一个大框。N-S流程图流程图N-S流程图简称流程图简称N-S图，也被称为盒图。图，也被称为盒图。N-S图图N-S流程图流程图wN-S流程图的三大结构w顺序结构w选择结构w循环结构N-S流程图流程图N-S流程图的三大结构流程图的三大结构N-S流程图流程图写出求sum=1+2+3+4+5+（n-1）+n的N-S图的描述方法N-S流程图写出求流程图写出求sum=1+2+3+4+5+（n-1）伪代码伪代码w用流程图或N-S图来描述算法虽然形象直观，但在算法设计过程中使用起来并不十分方便，特别是当算法稍微复杂一点时，不易修改。w在实际的算法设计中，常常使用自然语言或计算机语言或类计算机语言来描述。w这里的类计算机语言是一种非计算机语言，借用了一些高级语言的某些成分，没有加入严格的规则，而且不能够被计算机所接受，称其为“伪代码”。伪代码用流程图或伪代码用流程图或N-S图来描述算法虽然形象直观，但在算法设计图来描述算法虽然形象直观，但在算法设计伪代码伪代码写出求sum=1+2+3+4+5+（n-1）+n的伪代码的描述方法(1)算法开始；(2)输入n的值；(3)i1；(4)sum0；(5)dowhilei=n(6)sumsum+i；(7)ii+1；(8)输出sum的值；(9)算法结束；伪代码写出求伪代码写出求sum=1+2+3+4+5+（n-1）+n的的5.2.3常用算法介绍常用算法介绍1.枚举法2.递推法3.求最大值、最小值问题4.交换两个变量的值5.排序算法6.查找算法5.2.3常用算法介绍常用算法介绍1.枚举法枚举法枚举法又称为穷举法基本思想：根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。特点：算法简单，容易理解，运算量大1.1.枚举法枚举法枚举法又称为穷举法枚举法又称为穷举法1.枚举法枚举法1.1.枚举法枚举法应用：百钱买百鸡问题假定公鸡每只5元，母鸡每只3元，小鸡3只1元。现有100元钱要求买100只鸡，问共有几种购鸡方案？w问题分析：根据题目，设公鸡、母鸡、小鸡各为x，y，z只，列出方程为：x+y+z=1005x+3y+z/3=1001.枚举法应用：百钱买百鸡问题枚举法应用：百钱买百鸡问题w巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是一种重要的算法设计策略：穷举法几乎可以通用于任何领域的问题求解，可能是唯一一种解决所有问题的一般性方法即使效率低下，仍可用穷举法求解一些小规模的问题实例；如果解决的问题实例不多，而穷举法可用一种可接受的速度对问题求解，那么花时间去设计一个更高效地算法是得不偿失的。1.1.枚举法枚举法 思考题思考题 举例说明生活中的穷举法应用。举例说明生活中的穷举法应用。巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是递推法又称为迭代法基本思想：利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。2.2.递推法递推法递推法又称为迭代法递推法又称为迭代法2.递推法递推法2.2.递推法递推法w2.递推法递推法w基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为最大值，称为擂主，依次同第2，3，n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。求最小值问题则先假设第一个数为最小值。3.3.求最大值、最小值问题求最大值、最小值问题基本思想：采用如同打擂台的方法。在基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为个数中，先假设第一个数为3.3.求最大值、最小值问题求最大值、最小值问题应用：对输入的若干个学生成绩，求出最高分和最低分。wmax=min=a0；w用max依次与后续的成绩进行对比，若比max大则将相应值赋值给max；w用min依次与后续的成绩进行对比，若比min小则将相应值赋值给min；w最后输出max和min的值。3.求最大值、最小值问题应用：对输入的若干个学生成绩，求出最求最大值、最小值问题应用：对输入的若干个学生成绩，求出最w基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的值只能采取间接交换的方法。4.4.交换两个变量的值交换两个变量的值基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的4.4.交换两个变量的值交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝墨水的瓶子里，而把蓝墨水错装在了黑墨水瓶子里，要求将其互换。4.交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝4.4.交换两个变量的值交换两个变量的值应用：a=5,b=10，交换a，b的值并输出w引入一个新的变量c；w将a的值赋值给c；w将b的值赋值给a；w将c的值赋值给b；4.交换两个变量的值应用：交换两个变量的值应用：a=5,b=10，交换，交换a，b的值的值w选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记录与第i个位置的记录进行交换，也即第一轮从n个记录中选取关键码最小的记录与第1个位置的记录交换，第二轮从剩下的n-1个记录中选取关键码最小的记录与第2个位置的记录进行交换，直到整个序列的记录选完5.5.排序算法排序算法选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记5.5.排序算法排序算法【例5.6】给出一组关键字(28，6，72，85，39，41，13，20)，排序后得到(6，13，20，28，39，41，72，85)，其选择排序过程如下5.排序算法【例排序算法【例5.6】给出一组关键字】给出一组关键字(28，6，72，85w查找是指从给定的数据结构中查找某个给定的值。w常用的查找算法有顺序查找、二分查找等等。w顺序查找是直接从头到尾搜索集合中满足条件的值。w二分查找是必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合中满足条件的值。6.6.查找算法查找算法查找是指从给定的数据结构中查找某个给定的值。查找是指从给定的数据结构中查找某个给定的值。6.查找算法查找算法6.6.查找算法查找算法二分查找的方法如下：w将x与线性表的中间项进行比较；w若中间项的值等于x，则说明查找到，查找结束；w若x小于中间项的值，则在线性表的前半部分以相同的方法进行查找。w若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找。w这个过程一直进行到查找成功或子表长度为0为止。6.查找算法二分查找的方法如下：查找算法二分查找的方法如下：【例5.7】有序表中关键字序列为3，10，13，17，40，43，50，70，要查找关键字值为43的数据元素6.6.查找算法查找算法【例【例5.7】有序表中关键字序列为】有序表中关键字序列为3，10，13，17，40，5.3.1 软件危机软件危机5.3.2 软件工程软件工程5.3.3 软件生存周期软件生存周期5.3软件工程概述件工程概述5.3.1软件危机软件危机5.3软件工程概述软件工程概述5.3.1软件危机软件危机w软件危机是指在计算机软件的开发和维护过程中所遇到的一系列严重问题，主要有以下一些表现形式。软件开发费用和进度失控。软件的可靠性差。生产出来的软件难以维护。用户对“已完成”的系统不满意现象经常发生。5.3.1软件危机软件危机是指在计算机软件的开发和维护过程软件危机软件危机是指在计算机软件的开发和维护过程5.3.2软件工程软件工程wIEEE给出的软件工程的定义是：软件工程是将系统化的、规范的、可度量的方法应用于软件的开发、运行、维护过程，即将工程化应用于软件中的方法的研究。w人们给出的一般定义是：软件工程是一门旨在生产无故障的、积极交付的、在预算之内的和满足用户需求的软件的学科。实质上，软件工程就是采用工程的概念、原理、技术和方法来开发与维护软件，把经过实践考验而证明正确的管理方法和最先进的软件开发技术结合起来，应用到软件开发和维护过程中，来解决软件危机问题。5.3.2软件工程软件工程IEEE给出的软件工程的定义是：软件工程给出的软件工程的定义是：软件工程5.3.2软件工程软件工程w软件工程包括三要素：方法、工具和过程。w软件工程的目标是：在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性并且满足用户需求的软件产品。追求这些目标有助于提高软件产品的质量和开发效率，减少维护的困难w软件工程的原则：抽象、信息隐藏、模块化、局部化、一致性、确定性、完备性和可验证性5.3.2软件工程软件工程包括三要素：方法、工具和过程。软件工程软件工程包括三要素：方法、工具和过程。5.3.3软件生存周期软件生存周期w软件定义期软件定义期“做什么做什么”，确定工程的，确定工程的总目标和可行性，导出实现工程目标应使总目标和可行性，导出实现工程目标应使用的策略及系统必须完成的功能，估计完用的策略及系统必须完成的功能，估计完成工程需要的资源和成本，制定进度表。成工程需要的资源和成本，制定进度表。w软件开发期软件开发期“如何做如何做”，具体设计和，具体设计和实现在前一个使其定义的软件实现在前一个使其定义的软件w软件维护期软件维护期“如何长久的做如何长久的做”，使软，使软件持久地满足用户的需求。件持久地满足用户的需求。5.3.3软件生存周期软件定义期软件生存周期软件定义期“做什么做什么”，确定工程的，确定工程的软件过程模型软件过程模型w定义：从软件项目需求定义直至软件运行定义：从软件项目需求定义直至软件运行维护为止，跨越整个生存期的系统开发、维护为止，跨越整个生存期的系统开发、运作和维护所实施的全部过程、活动和任运作和维护所实施的全部过程、活动和任务的结构框架。务的结构框架。w常见的软件过程模型：常见的软件过程模型：n瀑布模型瀑布模型n原型模型原型模型n增量模型增量模型n螺旋模型螺旋模型软件过程模型定义：从软件项目需求定义直至软件运行维护为止，跨软件过程模型定义：从软件项目需求定义直至软件运行维护为止，跨瀑布模型（瀑布模型（WaterfallModel）w19701970年提出，又称年提出，又称线性模型线性模型，是历史上第一个，是历史上第一个正式使用并得到业界广泛认可的软件开发模型正式使用并得到业界广泛认可的软件开发模型w具体划分：具体划分：n制定计划、需求分析、软件设计、程序编写、制定计划、需求分析、软件设计、程序编写、软件测试、运行维护软件测试、运行维护n规定了自上而下、相互衔接的固定次序规定了自上而下、相互衔接的固定次序瀑布模型（瀑布模型（WaterfallModel）1970年提出，又年提出，又原型模型原型模型w原型模型的基本思想是：原型模型从需求采集开始，如图所示，然后是“快速设计”，集中于软件中那些对用户可见的部分的表示，并最终导致原型的创建。原型模型原型模型的基本思想是：原型模型从需求采集开始，如图所原型模型原型模型的基本思想是：原型模型从需求采集开始，如图所螺旋模型螺旋模型w1988年由TRW公司的B.Boehm提出，将瀑布模型和演化模型结合，并强调了其他模型都忽略了的风险分析。螺旋模型螺旋模型1988年由年由TRW公司的公司的B.Boehm提出，将瀑布模提出，将瀑布模并发模型并发模型w并发模型也称并发工程，它表达了在软件项目任一阶段的活动之间存在的并发性。并发模型并发模型也称并发工程，它表达了在软件项目任一阶段的活并发模型并发模型也称并发工程，它表达了在软件项目任一阶段的活基于构件的开发模型基于构件的开发模型w基于构件的开发（CBD）模型（如图5.18所示）融合了螺旋模型的许多特征，本质上是演化型的，要求软件创建迭代过程，但是基于构件的开发模型是利用预先封装好的软件构件来构造应用的。基于构件的开发模型基于构件的开发（基于构件的开发模型基于构件的开发（CBD）模型（如图）模型（如图5.18小 结程序设计的基本方法程序设计的基本方法程序设计语言程序设计语言算法的表示方法算法的表示方法常用的算法常用的算法软件工程软件工程软件生存周期软件生存周期小小结程序设计的基本方法结程序设计的基本方法