10 程序设计方法学.ppt

第第10章章 程序设计方法学程序设计方法学主要内容主要内容软件开发过程简介软件开发过程简介程序设计方法的发展历程程序设计方法的发展历程面向过程的程序设计方法面向过程的程序设计方法JosephusJosephus问题结构化方法的实现问题结构化方法的实现面向对象的方法面向对象的方法面向对象的软件开发面向对象的软件开发JosephusJosephus问题面向对象方法的实现问题面向对象方法的实现2课件制作10.1 10.1 软件开发过程简介软件开发过程简介基本术语基本术语源程序：用源语言写的，有待翻译的程序源程序：用源语言写的，有待翻译的程序目标程序：也称为目标程序：也称为“结果程序结果程序”，是源程序通过翻译程序加工以后，是源程序通过翻译程序加工以后所生成的程序所生成的程序翻译程序：是指一个把源程序翻译成等价的目标程序的程序翻译程序：是指一个把源程序翻译成等价的目标程序的程序汇编程序：其任务是把用汇编语言写成的源程序，翻译成机器语言形式汇编程序：其任务是把用汇编语言写成的源程序，翻译成机器语言形式的目标程序的目标程序编译程序：若源程序是用高级程序设计语言所写，经翻译程序加工生成编译程序：若源程序是用高级程序设计语言所写，经翻译程序加工生成目标程序，那么，该翻译程序就称为目标程序，那么，该翻译程序就称为“编译程序编译程序”解释程序：也是一种翻译程序，同样是将高级语言源程序翻译成机器指解释程序：也是一种翻译程序，同样是将高级语言源程序翻译成机器指令。它与编译程序不同点就在于：它是边翻译边执行的，即输入一句、令。它与编译程序不同点就在于：它是边翻译边执行的，即输入一句、翻译一句、翻译一句、执行一句，直至将整个源程序翻译并执行完毕。执行一句，直至将整个源程序翻译并执行完毕。3课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件设计开发过程软件设计开发过程有无正确开始1.编辑2.编译3.连接4.运行结束有错？结果正确？不正确源程序*.h/*.cpp目标程序*.obj/*.dll可执行程序*.EXE库函数和其它目标程序开始1.问题描述2.问题分析3.系统总体设计4.系统详细设计需求分析报告系统总体设计报告系统详细设计报告结束4课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件过程建模软件过程建模基本术语基本术语软件过程软件过程:是一组软件工程活动的总称是一组软件工程活动的总称,它把用户需求转化为可执行的它把用户需求转化为可执行的系统。它是生产软件产品的工具、方法和实践的集体系统。它是生产软件产品的工具、方法和实践的集体元过程元过程:描述、维护和演化软件过程的过程描述、维护和演化软件过程的过程软件过程模型软件过程模型:对软件过程中的开发活动、产品、资源、人员等信息的对软件过程中的开发活动、产品、资源、人员等信息的抽象描述。它和软件过程之间的关系类似于程序和程序执行之间的关系抽象描述。它和软件过程之间的关系类似于程序和程序执行之间的关系过程程序过程程序:一种使用过程描述语言一种使用过程描述语言(PML)(PML)所描述的可执行的过程模型所描述的可执行的过程模型软件产品软件产品:软件生命周期中生产的所有产品软件生命周期中生产的所有产品(包括中间件产品和最终产包括中间件产品和最终产品品,也包括所有版本的程序和各种文档也包括所有版本的程序和各种文档)工具工具:是一组可执行程序的集合，通常由活动调用。开发工具一般用于是一组可执行程序的集合，通常由活动调用。开发工具一般用于需求规约、重用、建模、程序生成、编译、维护和文档生成等活动。需求规约、重用、建模、程序生成、编译、维护和文档生成等活动。5课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件过程建模软件过程建模基本术语基本术语用户用户:在过程支持下使用工具进行开发工作的人，包括程序员、设计人在过程支持下使用工具进行开发工作的人，包括程序员、设计人员、质量工程师、项目管理员等员、质量工程师、项目管理员等 视图视图:软件过程某一个侧面的信息软件过程某一个侧面的信息,是软件过程的一个投影是软件过程的一个投影 个体视图个体视图:软件过程中每一个用户的任务和任务状态视图软件过程中每一个用户的任务和任务状态视图,过程工程师过程工程师可借此跟踪了解个体工作进度可借此跟踪了解个体工作进度 过程模型演化过程模型演化:以一种可控的方法对现有的模型进行修改以一种可控的方法对现有的模型进行修改,使之适应新使之适应新的需求和新的环境的需求和新的环境软件过程建模：软件过程模型是对软件过程的抽象描述，这种描述软件过程建模：软件过程模型是对软件过程的抽象描述，这种描述可以是形式化的可以是形式化的,也可以是非形式化的。进行这种抽象描述的工程也可以是非形式化的。进行这种抽象描述的工程活动活动,就称为软件过程建模就称为软件过程建模 6课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件过程建模软件过程建模软件过程建模语言：软件过程建模语言：UML(Unified Modeling Language,统一建模语言统一建模语言)，由，由OMG(Object Management Group,对象管理组织对象管理组织)110107年确认年确认Person -ID:int+stepOntoFloor(Floor&):void +enterElevator(Elevator&,Floor&):void+exitElevator(Floor&,Elevator&):voidFloor-floorNumber：int-elevatorRef:elevator-occupantPtr:Person+elevatorArrived():void+isOccupied():bool+personArrives():void Building-floor:Floor-elevator:Elevator -clock:Clock -scheduler:Scheduler+runSimulation(int):voidElevator-currentFloor:int=1-direction:enum=up-capacity:int=1-arrivalTime:int-moving:bool=false-scheduler:Scheduler+summonElevator():void+prepareToLeave():void+processTime():void+personEnters():void+personExits():voidrunSimulation(int):voidClock-time:int=0-scheduler:Scheduler+getTime():int+tick():voidScheduler-floorArrivalTime:int-currentClockTime:int+processTime(time:int):int0.1 乘坐 11 0.1 等待 1 1 11电梯模拟系统类关系图电梯模拟系统类关系图7课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件过程建模软件过程建模软件过程建模工具软件过程建模工具非形式化：非形式化：MS Word,MS Visio形式化：形式化：IBM Rational Software Architect V8.0 8课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件开发与管理工具软件开发与管理工具软件开发工具：本节以软件开发工具：本节以Microsoft Visual Studio 6.0中中 VC+6.0为例，为例，简单介绍简单介绍VC+6.0集成开发环境的若干概念：集成开发环境的若干概念：IDE（Integrated Development Environment，集成开发环境）：是指集源，集成开发环境）：是指集源程序编辑、编译、链接、调试于一体的计算机程序设计语言开发平台程序编辑、编译、链接、调试于一体的计算机程序设计语言开发平台Workspace（工作区）：为便于大型软件开发工作管理而设置的项目管理（工作区）：为便于大型软件开发工作管理而设置的项目管理环境（文件名后缀为环境（文件名后缀为.dsw），通常由若干相关项目组成；），通常由若干相关项目组成；Projects（项目）：通常是指具有功能相对完整、可独立执行的软件模块，（项目）：通常是指具有功能相对完整、可独立执行的软件模块，由若干文件组成，管理这些文件的文件为项目文件（文件名后缀为由若干文件组成，管理这些文件的文件为项目文件（文件名后缀为.dsp）；）；Files（文件）：主要指项目源程序文件（文件）：主要指项目源程序文件（*.c,*.cpp,*.h）和资源文件）和资源文件（如程序中用到的位图文件、光标文件等）；（如程序中用到的位图文件、光标文件等）；9课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件开发与管理工具软件开发与管理工具软件开发工具软件开发工具10课件制作10.1 10.1 软件开发过程简介软件开发过程简介软件开发与管理工具软件开发与管理工具软件开发管理工具软件开发管理工具(SourceSafe)11课件制作10.2 10.2 程序设计方法的发展历程程序设计方法的发展历程面向面向过程过程的程序设计方法的程序设计方法程序的目的：用于数学计算程序的目的：用于数学计算主要工作：设计求解问题的过程主要工作：设计求解问题的过程缺点：对于庞大、复杂的程序难以开发和维护缺点：对于庞大、复杂的程序难以开发和维护面向面向过程的结构化过程的结构化程序设计方法程序设计方法设计思路：自顶向下、逐步求精。采用模块分解与功能抽象，自顶设计思路：自顶向下、逐步求精。采用模块分解与功能抽象，自顶向下、分而治之向下、分而治之程序结构：程序结构：按功能划分为若干个基本模块，形成一个树状结构按功能划分为若干个基本模块，形成一个树状结构各模块间的关系尽可能简单，功能上相对独立；每一模块内部均是由顺各模块间的关系尽可能简单，功能上相对独立；每一模块内部均是由顺序、选择和循环三种基本结构组成序、选择和循环三种基本结构组成其模块化实现的具体方法是使用函数其模块化实现的具体方法是使用函数(子程序子程序)12课件制作10.2 10.2 程序设计方法的发展历程程序设计方法的发展历程面向面向过程的结构化过程的结构化程序设计方法程序设计方法优点：有效地将一个较复杂的程序系统设计任务分解成许多易于控优点：有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子任务，便于开发和维护制和处理的子任务，便于开发和维护缺点：缺点：可重用性差、数据安全性差、难以开发大型软件和图形界面的应用软件可重用性差、数据安全性差、难以开发大型软件和图形界面的应用软件把数据和处理数据的过程分离为相互独立的实体把数据和处理数据的过程分离为相互独立的实体当数据结构改变时，所有相关的处理过程都要进行相应的修改当数据结构改变时，所有相关的处理过程都要进行相应的修改每一种相对于老问题的新方法都要带来额外的开销每一种相对于老问题的新方法都要带来额外的开销图形用户界面的应用程序，很难用过程来描述和实现，开发和维护也都图形用户界面的应用程序，很难用过程来描述和实现，开发和维护也都很困难。很困难。13课件制作10.2 10.2 程序设计方法的发展历程程序设计方法的发展历程面向面向对象对象的方法的方法将数据及对数据的操作方法封装在一起，作为一个相互依存、不可将数据及对数据的操作方法封装在一起，作为一个相互依存、不可分离的整体分离的整体对象对象对同类型对象抽象出其共性，形成类对同类型对象抽象出其共性，形成类类通过一个简单的外部接口，与外界发生关系类通过一个简单的外部接口，与外界发生关系对象与对象之间通过消息进行通讯对象与对象之间通过消息进行通讯优点：优点：程序模块间的关系更为简单，程序模块的独立性、数据的安全性就有了程序模块间的关系更为简单，程序模块的独立性、数据的安全性就有了良好的保障良好的保障通过继承与多态性，可以大大提高程序的可重用性，使得软件的开发和通过继承与多态性，可以大大提高程序的可重用性，使得软件的开发和维护都更为方便维护都更为方便14课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法要想成为一名优秀的要想成为一名优秀的软件设计开发人员软件设计开发人员，必须：，必须：熟练掌握程序设计语言；熟练掌握程序设计语言；熟练掌握必要的程序设计方法；熟练掌握必要的程序设计方法；多了解、掌握和积累一些计算机常用算法；多了解、掌握和积累一些计算机常用算法；重视算法的设计；重视算法的设计；数据结构数据结构 +算法算法 =程序程序对于较小的简单问题，一般采用下列步骤进行程序设计对于较小的简单问题，一般采用下列步骤进行程序设计定义数学模型；定义数学模型；确定数据结构，如：变量、数组；确定数据结构，如：变量、数组；确定算法；确定算法；编写程序代码；编写程序代码；上机调试；上机调试；整理并写出文档资料；整理并写出文档资料；15课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法例例CH10_1：计算：计算n!1、定义数学模型：根据数学知识、定义数学模型：根据数学知识 n=0,n!=n*(n-1)*(n-2)2*12、确定数据结构：主要是程序中用的主要变量：阶数、确定数据结构：主要是程序中用的主要变量：阶数n，计算结果，计算结果 fac(factorial)，代表乘数的变量，代表乘数的变量 i；3、确定算法、确定算法step1:读入读入 n的值；的值；step2:如果如果 n=0，则，则 变量初始化变量初始化:fac 置初值置初值 1，i 置初值置初值 1；进行累乘运算进行累乘运算 fac=fac*i；乘数乘数 i 增增 1 得到下一个乘数的值，即得到下一个乘数的值，即 i=i+1;如果如果 i n，则执行步骤，则执行步骤；否则执行步骤；否则执行步骤 和和；输出输出 fac 的值；的值；step4:结束算法结束算法16课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法4、编写程序、编写程序#include using namespace std;int main()int n,i,fac;coutn;if(n 0)coutYour input is invalid!;return-1;fac=1;i=2;do fac=fac*i;i+;while(i=n);coutn!=facendl;return 1;5 5、上机调试；、上机调试；6 6、整理文档：问题描述，数学模型，算法描述及主要数据结构说明，源程序，、整理文档：问题描述，数学模型，算法描述及主要数据结构说明，源程序，可执行程序，测试案例；可执行程序，测试案例；17课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法定义：是为解决一个具体问题而采取的定义：是为解决一个具体问题而采取的确定的有限的确定的有限的操操作步骤，这里仅指计算机能执行的算法作步骤，这里仅指计算机能执行的算法算法的特性：正确的算法应该满足算法的特性：正确的算法应该满足5个特性个特性有穷性：算法包含的操作步骤应是有限的，每一步都能在合理的有穷性：算法包含的操作步骤应是有限的，每一步都能在合理的时间内完成；时间内完成；确定性：算法的每个步骤都应是确定的，不允许有歧义性；确定性：算法的每个步骤都应是确定的，不允许有歧义性；有效性：算法的每个步骤都应是有效执行的，且能得到确定的结有效性：算法的每个步骤都应是有效执行的，且能得到确定的结果；果；有零个或多个输入；有零个或多个输入；有一个或多个输出；有一个或多个输出；18课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法算法的分类算法的分类 数值运算算法：数值运算算法：解决的是求数值解的问题，例如用辗转相除法求解决的是求数值解的问题，例如用辗转相除法求两个数的最大公约数等，专门课程两个数的最大公约数等，专门课程计算方法或数值分析计算方法或数值分析；非数值运算算法：非数值运算算法：主要用于解决需要用分析推理、逻辑推理才能主要用于解决需要用分析推理、逻辑推理才能解决的问题，例如人工智能中的许多问题，查找、分类等问题；解决的问题，例如人工智能中的许多问题，查找、分类等问题；算法的表示方法算法的表示方法自然语言表示：参见例自然语言表示：参见例 计算计算 n!;n!;传统的流程图表示传统的流程图表示N-SN-S结构化流程图表示结构化流程图表示 伪代码表示伪代码表示19课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法流程图：用图框表示各种类型的操作，用箭头表示这些操作的顺序流程图：用图框表示各种类型的操作，用箭头表示这些操作的顺序数据输入框或输出框数据输入框或输出框数据处理框数据处理框开始框或结束框开始框或结束框判断框判断框条件？条件？A操作操作B操作操作成立成立不成立不成立流程线流程线连接符连接符20课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法流程图：用图框表示各种类型的操作，用箭头表示这些操作的顺序流程图：用图框表示各种类型的操作，用箭头表示这些操作的顺序开始开始定义标识符定义标识符x、y、sum为变量为变量sumx+y输出输出sum的值的值结束结束x4.6,y7.85开始开始定义标识符定义标识符a、b、max为变量为变量输入输入a、b的值的值ab?YNmaxbmaxa输出输出max结束结束21课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法流程图：用图框表示各种类型的操作，流程图：用图框表示各种类型的操作，用箭头表示这些操作的顺序用箭头表示这些操作的顺序YN开始开始定义标识符定义标识符 s、n 为变量为变量s0，n1n=100?ss+nnn+1输出输出 s 的值的值结束结束22课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法N-SN-S图：去掉流程图中的流线，把整个算法描述在一个矩形框中图：去掉流程图中的流线，把整个算法描述在一个矩形框中顺序结构顺序结构B操作操作A操作操作C操作操作分支结构分支结构是是 条件？条件？否否A操作操作 B操作操作循环结构循环结构循环条件循环条件 循环体循环体循环体循环体 循环条件循环条件23课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法N-SN-S图：去掉流程图中的流线，把整个算法描述在一个矩形框中图：去掉流程图中的流线，把整个算法描述在一个矩形框中例例 1定义标识符定义标识符x,y,sum为变量为变量x4.6,y7.85sumx+y输出输出sum的值的值例例 2定义标识符定义标识符a,b,max为变量为变量输入输入a,b的值的值 是是 a b?a b?否否 maxb maxa 输出输出 c 的的值值例例 3定义标识符定义标识符 s,n 为变量为变量s0,n1 nn+1输出输出 s 的值的值n=100s s+nn n+124课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法算法算法伪码描述：介于自然语言和计算机语言之间的一种代码，是帮助伪码描述：介于自然语言和计算机语言之间的一种代码，是帮助程序员指定算法的智能化语言，不能在计算机上运行，程序员指定算法的智能化语言，不能在计算机上运行，无固定格无固定格式和规范式和规范，使用灵活，但要，使用灵活，但要语义明确，易于理解语义明确，易于理解例例 求求n!input n if n 0 print “input error!”goto End else fac=1 i=2 Loop:fac=fac*i i=i+1 if i=n goto Loop print facEnd:25课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法程序设计的若干原则程序设计的若干原则结构化程序设计的核心思想结构化程序设计的核心思想采用顺序、选择和循环三种基本结构作为程序设计的基本单元采用顺序、选择和循环三种基本结构作为程序设计的基本单元 只有一个入口；只有一个入口；只有一个出口；只有一个出口；无死语句，即不存在永远都执行不到的语句；无死语句，即不存在永远都执行不到的语句；无死循环，即不存在永远都执行不完的循环。无死循环，即不存在永远都执行不完的循环。采用采用“自顶向下、逐步求精自顶向下、逐步求精”和模块化的方法进行结构化程序设计和模块化的方法进行结构化程序设计构成程序的三种基本结构构成程序的三种基本结构顺序结构顺序结构选择结构选择结构循环结构循环结构已经证明，任何程序均可只用这已经证明，任何程序均可只用这三种结构综合描述，只用这三种结三种结构综合描述，只用这三种结构编制的程序，叫结构化程序；程构编制的程序，叫结构化程序；程序必须符合结构化规则序必须符合结构化规则26课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法顺序结构顺序结构BA传统流程图N-S图BA27课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法分支结构（选择结构）分支结构（选择结构）NBAY如果如果如果如果 成绩成绩6060 那么那么那么那么 通知补考通知补考否则否则否则否则 告知你考试成绩告知你考试成绩28课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法循环结构循环结构A真真假假A假假真真当型循环当型循环直到型循环直到型循环直到型循环直到型循环29课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法函数设计的原则函数设计的原则函数的功能要单一，不要设计多用途的函数函数的功能要单一，不要设计多用途的函数 函数的规模要小，尽量控制在函数的规模要小，尽量控制在50行代码以内行代码以内1986年年 IBM 在在 OS/360 的研究结果：大多数有错误的函数都大于的研究结果：大多数有错误的函数都大于500 行行2001 年对年对 148,000 行代码的研究表明：小于行代码的研究表明：小于 143 行的函数比更长的函数行的函数比更长的函数更容易维护更容易维护每个函数只有一个入口和一个出口每个函数只有一个入口和一个出口 向函数传递信息时，向函数传递信息时，尽量不使用全局变量尽量不使用全局变量几个有关联的函数需要使用全局变量时，几个有关联的函数需要使用全局变量时，全局变量应和访问全局变全局变量应和访问全局变量的函数放在单独的一个文件中量的函数放在单独的一个文件中，与其它文件分别编译，并且将该，与其它文件分别编译，并且将该全局变量声明为全局变量声明为static（静态全局变量）（静态全局变量）30课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法函数设计的原则函数设计的原则函数参数的书写要完整，不要省略参数以及返回值的类型和名字，函数参数的书写要完整，不要省略参数以及返回值的类型和名字，如果没有，则用如果没有，则用voidvoid声明声明 定义好函数接口以后，应在文件的开头处进行函数说明定义好函数接口以后，应在文件的开头处进行函数说明尽量少用静态局部变量尽量少用静态局部变量，以避免使函数具有，以避免使函数具有“记忆记忆”功能功能模块和链接模块和链接 将一个程序分解成若干个模块，分别放在几个源文件中，形成一将一个程序分解成若干个模块，分别放在几个源文件中，形成一个项目（个项目（ProjectProject）对每一个源文件分别单独进行编译对每一个源文件分别单独进行编译将所有模块的目标代码连同标准函数库中的函数链接在一起，形将所有模块的目标代码连同标准函数库中的函数链接在一起，形成可执行文件成可执行文件主模块：主模块：main()所在的文件也是一个模块所在的文件也是一个模块31课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法模块和链接模块和链接 模块之间通过互相调用函数和共享全局变量联系起来模块之间通过互相调用函数和共享全局变量联系起来头文件是联系的纽带头文件是联系的纽带 头文件里对全局变量的声明要加上头文件里对全局变量的声明要加上extern关键字，用以说明该变量关键字，用以说明该变量为外部变量为外部变量 优点：优点：当一个文件中的代码被修改后，不必对所有程序重新编译，从而节省了当一个文件中的代码被修改后，不必对所有程序重新编译，从而节省了程序的编译时间程序的编译时间;使程序更宜于维护，给多个程序员共同编制一个大型项目的代码提供了使程序更宜于维护，给多个程序员共同编制一个大型项目的代码提供了方便手段方便手段;32课件制作10.3 10.3 面向过程的程序设计方法面向过程的程序设计方法C+程序源程序文件1源程序文件2源程序文件n编译预处理命令全局变量声明函数1函数n函数首部函数体局部变量声明执行语句C+程序结构程序结构33课件制作10.4 10.4 面向过程的程序设计方法实例面向过程的程序设计方法实例程序调试实例程序调试实例 CH10_2#include using namespace std;int Factorial(int x);/阶乘函数原型声明阶乘函数原型声明int main()int x,rs;while(1)/*无限循环无限循环*/coutx;if(x 0)break;/*循环出口循环出口*/else rs=Factorial(x);coutThe factorial of x is rsendl;/*函数功能函数功能：计算整数计算整数 x的阶乘的阶乘 函数入口参数：函数入口参数：整型整型x 函数返回值：函数返回值：整型的结果整型的结果*/int Factorial(int x)int i,result;for(i=1;i=2)开始位置 s校验(1=s=n)间隔数 m校验(1=m=n)37课件制作10.4 10.4 面向过程的程序设计方法实例面向过程的程序设计方法实例Josephus问题问题算法描述算法描述函数：创建环链表函数：创建环链表 链表头初始化；for(i=1;i=n;i+)申请 1 个小孩信息内存;赋给小孩编号 挂接到链表 endfor 将最后一个节点指向链表头；将链表头指针转到开始位置s(数s个小孩)函数：循环计数，排除函数：循环计数，排除 n-1个小孩个小孩 while(小孩数多于1个)数 m 个小孩 当前小孩从链表删除 endwhile函数：数函数：数 m 个小孩个小孩 for(m 间隔)保存当前位置 当前指针指向下一个小孩位置 endfor38课件制作10.4 10.4 面向过程的程序设计方法实例面向过程的程序设计方法实例Josephus问题问题算法实现算法实现/josephus problem procedural solving#includeusing namespace std;/-struct Jose/小孩结点小孩结点 int code;/小孩编号小孩编号 Jose*pNext;/指向下一个小孩结点指向下一个小孩结点;/-/-bool GetValue(int&n,int&s,int&m);Jose*CreateRing(Jose*pHead,int n,int s);/创建环链表创建环链表Jose*CountBoys(Jose*pHead,int m);/数数m个小孩个小孩Jose*Process(Jose*pHead,int m);/排除排除n-1个小孩个小孩/-39课件制作10.4 10.4 面向过程的程序设计方法实例面向过程的程序设计方法实例JosephusJosephus问题问题算法实现算法实现/-int main()int n,s,m;Jose*pHead=NULL;if(!GetValue(n,s,m)return 0;pHead=CreateRing(pHead,n,s);pHead=Process(pHead,m);coutnThe winner is coden;delete pHead;return 1;/-bool GetValue(int&n,int&s,int&m)cout nsm;if(n=2&s=1&s=1&m=n)return true;cerrfailed in bad boyNumber or startPosition or intervalNumber.n;return false;/-40课件制作10.4 10.4 面向过程的程序设计方法实例面向过程的程序设计方法实例Josephus问题问题算法实现算法实现Jose*CreateRing(Jose*pHead,int n,int s)Jose*pCur,*pPrev;for(int i=1;icode=i;pCur-pNext=NULL;/将新节点加入链表将新节点加入链表 if(pHead=NULL)pHead=pCur;pPrev=pCur;else pPrev-pNext=pCur;pPrev=pCur;/-pCur-pNext=pHead;/构成循环链表构成循环链表 coutThere are npNext-pNext;return pHead;/-新节点插入新节点插入链表何处：链表何处：首，尾？首，尾？41课件制作10.4 10.4 面向过程的程序设计方法实例面向过程的程序设计方法实例JosephusJosephus问题问题算法实现算法实现Jose*CountBoys(Jose*pHead,int m)Jose*pCur,*pPrev;if(pHead-pNext=pHead)return pHead;pCur =pHead;for(int i=1;ipNext;return pPrev;/-42课件制作10.4 10.4 面向过程的程序设计方法实例面向过程的程序设计方法实例Josephus问题问题算法实现算法实现Jose*Process(Jose*pHead,int m)Jose*pCur,*pPrev;coutpNext!=pHead)pPrev=CountBoys(pHead,m);pCur =pPrev-pNext;pHead=pCur-pNext;static int line=0;cout code;if(!(+line%10)coutpNext=pHead;/小孩脱链小孩脱链 delete pCur;return pHead;/=43课件制作10.5 10.5 面向对象方法学概述面向对象方法学概述 面向对象面向对象(Object-Oriented,缩写为缩写为OO)方法学的出发点和基本原则，是方法学的出发点和基本原则，是尽可能模拟人类习惯的思维方式，使开发软件的方法与过程尽可能接近人尽可能模拟人类习惯的思维方式，使开发软件的方法与过程尽可能接近人类认识世界解决问题的方法与过程，也就是使类认识世界解决问题的方法与过程，也就是使描述问题的问题空间描述问题的问题空间(也称为也称为问题域问题域)与与实现解法的解空间实现解法的解空间(也称为求解域也称为求解域)在结构上尽可能一致。在结构上尽可能一致。面向对象方法是一种新的思维方法，它不是把程序看作是工作在数据上面向对象方法是一种新的思维方法，它不是把程序看作是工作在数据上的一系列过程或函数的集合，而是把程序看作是的一系列过程或函数的集合，而是把程序看作是相互协作而又彼此独立的相互协作而又彼此独立的对象的集合对象的集合。每个对象就像一个微型程序，有自己的数据、操作、功能和。每个对象就像一个微型程序，有自己的数据、操作、功能和目的。目的。面向对象方法在概念和表示方法上的一致性，保证了软件工程各项开发面向对象方法在概念和表示方法上的一致性，保证了软件工程各项开发活动之间的平滑（活动之间的平滑（“无缝无缝”）过渡。）过渡。面向对象开发过程的核心是面向对象开发过程的核心是面向对象分析面向对象分析(Object-Oriented Analyze，OOA)和面向对象设计和面向对象设计(Object-Oriented Design,OOD)两个阶段，但二者两个阶段，但二者的界限比较模糊。的界限比较模糊。44课件制作10.5 10.5 面向对象方法学概述面向对象方法学概述 OOA 通过分析用例，提取用户的需求，从而建立问题域逻辑模型的过通过分析用例，提取用户的需求，从而建立问题域逻辑模型的过程；程；OOD 是建立面向对象的求解域模型的过程。是建立面向对象的求解域模型的过程。从从OOA到到OOD实际是一个多次反复、逐步迭代模型的过程。实际是一个多次反复、逐步迭代模型的过程。面向对象是面向对象是认识事物认识事物的一种方法，是一种以对象为中心的的一种方法，是一种以对象为中心的思维方式思维方式，涉，涉及的主要概念：对象、类、封装、继承、消息、结构与关联、多态性。及的主要概念：对象、类、封装、继承、消息、结构与关联、多态性。对象对象世界上所有的事物都可以称为对象世界上所有的事物都可以称为对象对象可以是有形的如：一台电视机等，也可以是无形的如：帐户、一项记对象可以是有形的如：一台电视机等，也可以是无形的如：帐户、一项记录等。录等。对象是封装了数据结构及可以施加在这些数据结构上的操作的对象是封装了数据结构及可以施加在这些数据结构上的操作的封装体封装体，这，这个封装体有可以唯一地标识它的名字，而且向外界提供一组服务个封装体有可以唯一地标识它的名字，而且向外界提供一组服务(即公有的即公有的操作操作)45课件制作10.5 10.5 面向对象方法学概述面向对象方法学概述对象对象属性和操作是对象的两大要素。属性和操作是对象的两大要素。属性属性是对象静态特征的描述，如电视的属性是对象静态特征的描述，如电视的属性有：品牌、尺寸、重量等。有：品牌、尺寸、重量等。操作操作是对象动态特征的描述，如电视的操作有：是对象动态特征的描述，如电视的操作有：收视、选台、音量调节等。收视、选台、音量调节等。对象名也称为对象标识对象名也称为对象标识对象具有静态特征和动态特征对象具有静态特征和动态特征类类类是对象的蓝图。根据抽象的原则对客观对象进行归纳和划分，把具有相同类是对象的蓝图。根据抽象的原则对客观对象进行归纳和划分，把具有相同特征的对象归为一个类。它是一个抽象的概念。特征的对象归为一个类。它是一个抽象的概念。类是对象模版，用于创建具有相同属性和相同操作（服务）的对象，它包括类是对象模版，用于创建具有相同属性和相同操作（服务）的对象，它包括属性和方法（注：类的服务、行为和操作只是叫法上的区别）属性和方法（注：类的服务、行为和操作只是叫法上的区别）46课件制作10.5 10.5 面向对象方法学概述面向对象方法学概述封装封装封装是指按照信息隐藏的原则，把对象的属性和操作结合在一起，封装是指按照信息隐藏的原则，把对象的属性和操作结合在一起，构成一个独立的封装体。封装性也就是信息隐藏，通过封装把对象构成一个独立的封装体。封装性也就是信息隐藏，通过封装把对象的实现细节对外界隐藏起来的实现细节对外界隐藏起来具有封装性的条件如下具有封装性的条件如下:l有一个清晰的边界。所有私有数据和实现操作的代码都被封装在这个边有一个清晰的边界。所有私有数据和实现操作的代码都被封装在这个边界内，从外面看不见更不能直接访问。界内，从外面看不见更不能直接访问。l有确定的接口有确定的接口(即协议即协议)。接口就是对象之间通信的桥梁，只能通过向对。接口就是对象之间通信的桥梁，只能通过向对象发送消息来使用它。象发送消息来使用它。l受保护的内部实现。实现对象功能的细节受保护的内部实现。实现对象功能的细节(私有数据和私有方法私有数据和私有方法)不能在不能在定义该对象的类的范围外进行访问。定义该对象的类的范围外进行访问。l外部对象不能直接操作对象的属性，只能使用对象提供的接口。外部对象不能直接操作对象的属性，只能使用对象提供的接口。47课件制作10.5 10.5 面向对象方法学概述面向对象方法学概述继承继承继承使得一个类可以继承另一个类的属性和方法。继承使得一个类可以继承另一个类的属性和方法。通过抽象出共同的属性和方法组建新的类，便于