《大学计算机基础》第5章-程序设计基础.ppt

《《大学计算机基础》第5章-程序设计基础.ppt》由会员分享，可在线阅读，更多相关《《大学计算机基础》第5章-程序设计基础.ppt（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大学计算机基础大学计算机基础北京航空航天大学北京航空航天大学教学课件教学课件1第第5 5章章 程序设计基础程序设计基础2本章重点本章重点n程序的概念程序的概念n程序设计语言的结构程序设计语言的结构n算法的概念与描述方法算法的概念与描述方法n程序设计步骤程序设计步骤n程序设计方法程序设计方法35.1 程序和程序设计语言程序和程序设计语言u5.1.1 程序的一般概念程序的一般概念 u5.1.2 程序设计语言的概述程序设计语言的概述 u5.1.3 程序设计语言的结构程序设计语言的结构 4程序的一般概念程序的一般概念 n生活中程序的概念生活中程序的概念例例1：年终总结会的程序：年终总结会的程序：会议主

2、持宣布会议开始会议主持宣布会议开始领导讲话领导讲话个人或团队代表发言个人或团队代表发言领导总结领导总结会议主持宣布会议结束会议主持宣布会议结束5程序的一般概念（续程序的一般概念（续1）n生活中程序的概念生活中程序的概念甲地甲地乙地乙地丙地丙地A线线8公里公里B线线5公里公里C线线4公里公里步行步行骑车骑车开车开车时间时间红绿灯红绿灯铁道铁道解决该计算问题的方法、步骤就包含了程序的概念。解决该计算问题的方法、步骤就包含了程序的概念。例例2：某人从甲地到丙地去。：某人从甲地到丙地去。6程序的一般概念（续程序的一般概念（续2）n计算机程序的概念：计算机程序的概念：为实现某一算法而编写的指令序列。为实

3、现某一算法而编写的指令序列。宏观地描述该指令序列，可用计算机的宏观地描述该指令序列，可用计算机的l机器语言机器语言l汇编语言汇编语言l高级语言高级语言用经典的公式可表示为：用经典的公式可表示为：程序程序=算法算法+数据结构数据结构7程序设计语言的概述程序设计语言的概述 n程序设计程序设计编写程序的全过程。编写程序的全过程。有学者认为：有学者认为：程序设计程序设计=算法算法+数据结构数据结构+程序设计语言程序设计语言 n程序设计语言程序设计语言人和计算机之间对话和交流的一种工人和计算机之间对话和交流的一种工具，用于描述计算机所执行的操作。具，用于描述计算机所执行的操作。n计算机程序设计语言有几百

4、种，但是最常用的不过计算机程序设计语言有几百种，但是最常用的不过10多种，了解一些程序设计语言的不同特性，有助于为多种，了解一些程序设计语言的不同特性，有助于为特定任务而选择适当的程序设计语言。特定任务而选择适当的程序设计语言。81.机器语言（机器语言（Machine Language）n指令指令指挥计算机完成某个基本操作的命令。指挥计算机完成某个基本操作的命令。机器语言程序机器语言程序注解注解10110000 0000100000101100 0000101011110100把把8存放到累加器存放到累加器A中。中。将将10与累加器与累加器A中的中的8相加，结果存在相加，结果存在A中。中。程序

5、结束。程序结束。n指令系统指令系统所有的指令集合。所有的指令集合。（第一代程序设计语言第一代程序设计语言）n机器语言机器语言用二进制代码表示指令系统的语言。用二进制代码表示指令系统的语言。n机器语言程序机器语言程序由二进制代码按一定规则组成的、能被由二进制代码按一定规则组成的、能被机器理解和运行的指令序列。（也称可执行程序机器理解和运行的指令序列。（也称可执行程序）例如：计算累加器例如：计算累加器A=8+10的机器语言程序如下：的机器语言程序如下：92.汇编语言汇编语言（Assembly Language）n汇编语言汇编语言实质就是以容易记忆的代码或英文单词来实质就是以容易记忆的代码或英文单词

6、来代替约定的机器指令。（代替约定的机器指令。（第二代程序设计语言第二代程序设计语言）汇编语言源程序汇编语言源程序注解注解MOV A,8MOV A,8ADD A,10ADD A,10HLTHLT把把8 8存放到累加器存放到累加器A A中。中。将将1010与累加器与累加器A A中的中的8 8相加，结果存在相加，结果存在A A中。中。程序结束。程序结束。例如：用例如：用ADD表示加、表示加、SUB表示减、表示减、JMP表示跳转、表示跳转、MOV表示数据的传送指令等表示数据的传送指令等。n汇编源程序汇编源程序使用汇编语言编写的程序。使用汇编语言编写的程序。例如：上述计算累加器例如：上述计算累加器A=8

7、+10的汇编语言程序如下：的汇编语言程序如下：103.高级语言高级语言（High Level Language）n高级语言高级语言类似数学语言或人的自然语言，同时又不依赖于类似数学语言或人的自然语言，同时又不依赖于某种计算机硬件，使得设计编制的程序能够在所有机器上通某种计算机硬件，使得设计编制的程序能够在所有机器上通用。用。（第三代程序设计语言第三代程序设计语言）n程序设计语言在不同的系统平台使用比较普遍的有：程序设计语言在不同的系统平台使用比较普遍的有：FORTRAN、ALGOL、COBOL、LISP、PL/I、BASIC、SIMULA 67、Pascal、C、Smalltalk 80、Ad

8、a、C+、VC、VB、Delphi、Java、JavaScript、C#、Visual BASIC.NET。n可视化语言可视化语言构成了命令式语言中的另一个子类。最流行的构成了命令式语言中的另一个子类。最流行的可视化语言可视化语言Visual BASIC（1999年），已被年），已被Visual BASIC.NET（2002年）取代。提供拖拉式生成代码段的功年）取代。提供拖拉式生成代码段的功能。一度被认作第四代语言，此说法已不再使用了。能。一度被认作第四代语言，此说法已不再使用了。11程序设计语言的特点程序设计语言的特点 n机器语言的特点：机器语言的特点：编程难编程难效率高效率高 需要指令系统

9、需要指令系统难读难读难维护难维护n高级语言的特点：高级语言的特点：编程容易编程容易效率低效率低 需要编译系统需要编译系统易读易读易维护易维护n汇编语言的特点：汇编语言的特点：编程不容易编程不容易效率较高效率较高 需要汇编程序需要汇编程序不易读不易读不易维护不易维护12程序设计语言的结构程序设计语言的结构 n程序结构的多样性：程序结构的多样性：结构化程序结构化程序 模块化程序模块化程序 面向对象的程序结构面向对象的程序结构n一个良好结构的程序具有以下等特点：一个良好结构的程序具有以下等特点：结构清晰结构清晰容易阅读容易阅读容易理解容易理解容易验证容易验证容易维护容易维护n1996年，计算机科学家

10、年，计算机科学家Boehm和和Jacopini提出并从数学上证明提出并从数学上证明 任何一个算法，都能以三种基本控制结构表示，即任何一个算法，都能以三种基本控制结构表示，即顺序结构顺序结构、选择结构选择结构和和循环结构循环结构。13结构化程序设计中结构化程序设计中顺序结构顺序结构 n按照程序语句行的自然顺序，一条语句一条语句按照程序语句行的自然顺序，一条语句一条语句地执行程序。地执行程序。语句语句A入口入口语句语句B出口出口14结构化程序设计中结构化程序设计中选择结构选择结构 n根据条件的判断确定应该执行哪一条分支的语句根据条件的判断确定应该执行哪一条分支的语句序列。（又称为序列。（又称为分支

11、结构分支结构）入口入口出口出口语句序列语句序列A语句序列语句序列B条件条件真真假假15入口入口假假真真语句序列语句序列出口出口直到型循环结构直到型循环结构 条件条件结构化程序设计中结构化程序设计中循环循环结构结构 n主要用于重复执行相同的语句序列（被称为主要用于重复执行相同的语句序列（被称为循环体循环体），），直到判定条件为假（或为真）时才可终止执行循环体。直到判定条件为假（或为真）时才可终止执行循环体。出口出口入口入口语句序列语句序列假假条件条件真真当型循环结构当型循环结构 16结构化程序设计的特点结构化程序设计的特点 n每种结构，只有一个入口和一个出口，这是结构化设计每种结构，只有一个入口

12、和一个出口，这是结构化设计的一个原则。的一个原则。n遵循结构化程序设计的原则，按照结构化程序设计方法遵循结构化程序设计的原则，按照结构化程序设计方法设计出的程序具有明显的优点：设计出的程序具有明显的优点：其一，程序易读、理解和维护。程序员用结构化编程其一，程序易读、理解和维护。程序员用结构化编程方法，将复杂程序分解成若干子结构，便于控制、降方法，将复杂程序分解成若干子结构，便于控制、降低程序的复杂性，因此容易编写程序，同时便于验证低程序的复杂性，因此容易编写程序，同时便于验证程序。程序。其二，提高编程工作效率，降低软件开发成本。由于其二，提高编程工作效率，降低软件开发成本。由于结构化编程方法能

13、够把错误控制到最低限度，因此能结构化编程方法能够把错误控制到最低限度，因此能够减少调试和查错的时间。够减少调试和查错的时间。175.2 算法算法u5.2.1 算法的概念与特征算法的概念与特征 u5.2.2 算法的描述方法算法的描述方法 u5.2.3 程序设计典型算法程序设计典型算法 18算法的概念与特征算法的概念与特征 1976年年Niklaus Wirth（也是（也是Pascal语言发明者，语言发明者，1984年获得图灵奖）的专著：年获得图灵奖）的专著：Algorithms Data Structures Programs （算法算法 十十 数据结构数据结构=程序）程序）在计算机软件开发行业

14、中产生了极为深远的影响，从在计算机软件开发行业中产生了极为深远的影响，从而推动了软件开发技术和方法步入正轨，使人们开始深入而推动了软件开发技术和方法步入正轨，使人们开始深入研究数据结构和算法设计与分析的技术和方法。研究数据结构和算法设计与分析的技术和方法。191.算法的概念算法的概念 n算法算法解决某个具体问题而采取的方法与步骤的完整和解决某个具体问题而采取的方法与步骤的完整和准确的描述。准确的描述。是指令的有限序列，其中每一条指令表示一个或多个操是指令的有限序列，其中每一条指令表示一个或多个操作。作。是问题的程序化解决方案，这些解决方案本身并不是答是问题的程序化解决方案，这些解决方案本身并不

15、是答案，而是获得答案的精确指令。案，而是获得答案的精确指令。n算法的分类算法的分类顺序算法：是由冯顺序算法：是由冯诺依曼型计算机体系结构所决定的，诺依曼型计算机体系结构所决定的，其主要思想是指令逐条运行，每次执行一步操作。其主要思想是指令逐条运行，每次执行一步操作。并行算法：要求在一些更新式的计算机中可以在同一时并行算法：要求在一些更新式的计算机中可以在同一时间执行多条指令。间执行多条指令。202.算法的特征算法的特征 n一个算法必须具备五项基本特征：有穷性、确定性、一个算法必须具备五项基本特征：有穷性、确定性、数据输入、数据输出和可行性。数据输入、数据输出和可行性。（1）有穷性）有穷性算法是

16、有序指令的集合，并在执行有穷步骤后能够算法是有序指令的集合，并在执行有穷步骤后能够终止。终止。（2）确定性）确定性每条指令必须有确切的含义，且无二义性。在任何每条指令必须有确切的含义，且无二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入数条件下，算法只有唯一的一条执行路径，即对于相同的输入数据只能得到相同的输出数据。据只能得到相同的输出数据。（3）输入数据）输入数据可有零个或多个输入数据。这些输入数据取自于可有零个或多个输入数据。这些输入数据取自于某个特定对象的集合。某个特定对象的集合。（4）输出数据）输出数据必须有一个或多个输出数据。必须有一个或多个输出数据。（5）可行性）

17、可行性描述的操作都可以通过已经实现的基本运算执行有描述的操作都可以通过已经实现的基本运算执行有限次来实现，也可以证明整个算法实施后可以得到预期的解。限次来实现，也可以证明整个算法实施后可以得到预期的解。21例例5.1 一个非算法的计数过程一个非算法的计数过程 令令n为为0；置置n为为n+1；返回返回。结论：不能称为算法。结论：不能称为算法。原因：违背了算法特征中（原因：违背了算法特征中（1）、（）、（4）、（）、（5）。）。22例例5.2 计数器算法计数器算法 用自然语言编写一个不超过用自然语言编写一个不超过1万次的计数器算法：万次的计数器算法：令令n为为0；置置n为为n+1 若若n小于小于1

18、0000，则返回，则返回；否则，输出；否则，输出n之值，之值，且算法到此结束。且算法到此结束。结论：是算法。结论：是算法。原因：符合算法特征。原因：符合算法特征。在算法设计过程中，其实还有有关正确性、可读性、在算法设计过程中，其实还有有关正确性、可读性、健壮性、效率与低存储量需求，以及算法效率的度量等健壮性、效率与低存储量需求，以及算法效率的度量等问题。问题。23算法的描述方法算法的描述方法 流程图（流程图（FlowChart）PAD图（图（Problem Analysis Diafram，问题分析图），问题分析图）N-S图图自然语言自然语言伪代码伪代码 UML图图（Unified Model

19、ing Language，统一建模语言），统一建模语言）241.流程图流程图 n流程图（框图）用不同形状的几何图形表示不同性质的操流程图（框图）用不同形状的几何图形表示不同性质的操作，用流程线指明算法的执行方向。作，用流程线指明算法的执行方向。ANSI(美国国家标准美国国家标准化协会化协会)、ISO（国际标准化组织）和我国国家标准中均（国际标准化组织）和我国国家标准中均有类似的规定。常见的流程图符号如下：有类似的规定。常见的流程图符号如下：n向下或向右的流程线可以不画出箭头。当流程线有交叉时，向下或向右的流程线可以不画出箭头。当流程线有交叉时，则画一半圆通过交叉点。则画一半圆通过交叉点。25用

20、流程图描述的计数器算法用流程图描述的计数器算法 263.N-S图图 n1973年美国两位学者提出无流程线的年美国两位学者提出无流程线的N-S图（盒图）。图（盒图）。n结构化程序设计由三种基本结构而组成，则算法也应采用结构化程序设计由三种基本结构而组成，则算法也应采用结构化描述方法，结构化描述方法，N-S图的基本单元是矩形框，框内可以图的基本单元是矩形框，框内可以有三种基本结构，形如堆积木，也只有一个入口和一个出有三种基本结构，形如堆积木，也只有一个入口和一个出口。三种基本结构的口。三种基本结构的N-S图如下：图如下：28用用N-S图描述的计数器算法图描述的计数器算法 294.自然语言自然语言

21、n自然语言是人们日常生活、工作和学习中使用的通用语言，自然语言是人们日常生活、工作和学习中使用的通用语言，使用自然语言的文字描述算法通俗易懂，但也有它的缺陷：使用自然语言的文字描述算法通俗易懂，但也有它的缺陷：（1）容易产生歧义性，因为自然语言经常要根据上下文才）容易产生歧义性，因为自然语言经常要根据上下文才能判别其含义，不太严格。能判别其含义，不太严格。（2）自然语言很难清楚地表达算法的逻辑流程，对于算法）自然语言很难清楚地表达算法的逻辑流程，对于算法中的条件判断、循环，尤其是在这些处理中还有多层嵌中的条件判断、循环，尤其是在这些处理中还有多层嵌套，就很难用清晰而直观的语言来表达算法的流程。

22、因套，就很难用清晰而直观的语言来表达算法的流程。因此仅适于描述简单问题。此仅适于描述简单问题。305.伪代码伪代码 n伪代码是介于自然语言和计算机语言之间的文字和符号，伪代码是介于自然语言和计算机语言之间的文字和符号，它不能被计算机所理解，但使用伪代码描述的算法很容易它不能被计算机所理解，但使用伪代码描述的算法很容易转变成某种编程语言。转变成某种编程语言。/用用伪代码描述的计数器算法如下：伪代码描述的计数器算法如下：n 0n 0 do do n n+1 n n+1 while n 10000 while n 10000 输出输出n n，且算法到此结束。，且算法到此结束。n常用的伪代码是用自然语

23、言与类常用的伪代码是用自然语言与类Pascal或类或类C语言相结合语言相结合的方法来描述算法。的方法来描述算法。31流程图形的绘制工具流程图形的绘制工具n当使用图形描述算法时，流程图形的绘制工具有很多当使用图形描述算法时，流程图形的绘制工具有很多。n一般比较简单的图形可用一般比较简单的图形可用Word或或PowerPoint中的绘图工具栏来制中的绘图工具栏来制作完成，若安装了功能强大的作完成，若安装了功能强大的Microsoft Office Visio 2003，则可，则可以更快地绘制具有专业水平的高质量图形。以更快地绘制具有专业水平的高质量图形。n在在Visio 2003中：中：含有丰富的

24、基本流程图形状。含有丰富的基本流程图形状。能够快速、简便地建立流程图、组织图、日历时间表和其它多种能够快速、简便地建立流程图、组织图、日历时间表和其它多种图表。图表。支持缩放矢量图形（支持缩放矢量图形（SVG），这是一种新的图形格式标准。），这是一种新的图形格式标准。集合集合Internet的运用，可使用不同的语言创建绘图、创建包含多的运用，可使用不同的语言创建绘图、创建包含多种语言的绘图以及跨多种语言共享绘图和展开协作。种语言的绘图以及跨多种语言共享绘图和展开协作。通过支持新的汉字编码标准通过支持新的汉字编码标准GB18030，可从这个新的字符编码，可从这个新的字符编码集中创建包含汉字的绘图

25、。集中创建包含汉字的绘图。32程序设计典型算法程序设计典型算法n算法算法数值算法数值算法或或非数值算法非数值算法：数值算法数值算法主要用于数值求解或分析，如：主要用于数值求解或分析，如：求和、求平方根、解方程、用组合梯形法则求和、求平方根、解方程、用组合梯形法则求定积分等。求定积分等。非数值算法非数值算法主要用于各领域管理类的信息主要用于各领域管理类的信息处理，如：各种排序、查找等。处理，如：各种排序、查找等。n本节介绍一些简单的常用算法，并假设各数据均本节介绍一些简单的常用算法，并假设各数据均能满足值域要求。能满足值域要求。331.求求3个整数的最大值算法个整数的最大值算法 n为了编写求为了

26、编写求3个整数个整数最大值最大值的通用实现过程，采用主函的通用实现过程，采用主函数调用子函数的形式描述算法。数调用子函数的形式描述算法。（1 1）主函数算法描述如下：）主函数算法描述如下：输入三个整数输入三个整数a,b,c;a,b,c;max=max3(a,b,c);max=max3(a,b,c);输出输出maxmax。（2 2）max3 max3 子函数算法描述如下：子函数算法描述如下：从从a a与与b b中取大数送中取大数送m m中中;从从m m与与c c中取大数送中取大数送m m中中;返回返回m m给主函数。给主函数。34求求3个整数的最大值的个整数的最大值的C程序程序/*/*使使C C

27、预编译包含预编译包含I/OI/O头文件，则可用头文件，则可用scanfscanf、printfprintf函数函数*/#include#include void main(void)void main(void)int a,b,c,max;int a,b,c,max;/*/*定义定义 4 4 个整型变量个整型变量 */int max3(int a,int b,int c);int max3(int a,int b,int c);/*max3/*max3 函数原形声明函数原形声明 */printf(printf(“Input 3 integer numbers:Input 3 integer n

28、umbers:”););/*/*输出双引号中的提示信息输出双引号中的提示信息 */scanf(scanf(“%d%d%d%d%d%d”,&a,&b,&c);,&a,&b,&c);/*/*输入输入 3 3 个整数个整数 */max=max3(a,b,c);max=max3(a,b,c);/*/*调用调用 max3 max3 函数求最大值函数求最大值 */printf(printf(“The max is:%d nThe max is:%d n”,max);,max);/*/*输出输出 max max 中的最大值中的最大值 */*End of main function*/*End of main

29、 function*/*/*求求 3 3 个整数的最大值的个整数的最大值的子函数子函数 max3 */*/int max3(int a,int b,int c)int max3(int a,int b,int c)/*max3/*max3 函数将返回整型值函数将返回整型值 */int m;int m;/*/*定义定义 m m 整型变量整型变量 */if(a b)m=a;if(a b)m=a;/*/*从从 a a 与与 b b 中取大数送中取大数送 m m 中中 */else m=b;else m=b;if(m c);if(m c);/*/*从从 m m 与与 c c 中取大数送中取大数送 m

30、m 中，中，“；”即即m=m m=m*/*/else else m=c;m=c;return(m);return(m);/*/*返回返回 m m 给主函数给主函数*/*End of max3 function*/*End of max3 function*/352.欧几里得算法欧几里得算法 n求解两个不全为求解两个不全为0的非负整数的非负整数m和和n的最大公约数，可以采的最大公约数，可以采用以下用以下欧几里得算法欧几里得算法。（1 1）欧欧几几里里得得算算法法主主函函数数描述如下：描述如下：输输入入两两个个不不全全为为0 0的的非负整数非负整数m,n;m,n;Ecd=Euclid(m,n);E

31、cd=Euclid(m,n);输输出出EcdEcd，且且算算法法到到此结束。此结束。（2 2）Euclid(m,n)Euclid(m,n)子子函函数算法描述如下：数算法描述如下：while n 0 dowhile n 0 do r m mod n r m mod n m n m n n r n r return m return m363.两个变量值的交换算法两个变量值的交换算法 n计算机实现的两个变量值的计算机实现的两个变量值的交换交换算法如下：算法如下：令令 a=5,b=10a=5,b=10 c c a,a a,a b,b b,b c c 输出输出 a a 和和 b b 的值。的值。/*/

32、*两个变量值交换算法的两个变量值交换算法的 C C 源程序源程序 */void main(void)void main(void)int a=5,b=10,c;int a=5,b=10,c;/*/*定义定义 a a、b b、c 3c 3个整型变量个整型变量*/printf(printf(“交换前交换前:a=%d,b=%dn:a=%d,b=%dn”,a,b);,a,b);/*/*交换前输出交换前输出a a和和b b的值的值 */c=a;c=a;/*/*将将 a a 中的值赋值给中的值赋值给 c */c */a=b;a=b;/*/*将将 b b 中的值赋值给中的值赋值给 a */a */b=c;b

33、=c;/*/*将将 c c 中的值赋值给中的值赋值给 b */b */printf(printf(“交换后交换后:a=%d,b=%dn:a=%d,b=%dn”,a,b);,a,b);/*/*交换后输出交换后输出a a和和b b的值的值*/*End of main function*/*End of main function*/374.排序算法排序算法 n给定一个有给定一个有n个元素可个元素可排序排序的序列，例如数字数据或字符的序列，例如数字数据或字符串数据等，要求按照升序或降序方式重新排列。串数据等，要求按照升序或降序方式重新排列。n排序算法：如排序算法：如冒泡排序法冒泡排序法、选择排序法选

34、择排序法、插入排序法插入排序法、合合并排序法并排序法、快速排序法快速排序法等等排序算法。等等排序算法。38蛮力法中的选择排序法蛮力法中的选择排序法 n按照降序方式排序的选择排序算法：按照降序方式排序的选择排序算法：SelectionSort（Array 0.n-1 ）/*/*本算法用选择排序法对给定数组按照降序方式排序本算法用选择排序法对给定数组按照降序方式排序*/*/*Array0.n-1 是有是有n个元素的可排序数组个元素的可排序数组 */*/*本算法的结果在本算法的结果在Array数组中数组中 */for i 0 to n-2 do max i for j i+1 to n-1 do i

35、f Array j Array max max j j swap swap Array i and Array max 39选择排序法的选择排序法的 C 程序程序/*SelectionSort(Array 0.n-1 )/*SelectionSort(Array 0.n-1 )选择排序算法的选择排序算法的 C C 源程序源程序 */void SelectionSort(int n,int Array )void SelectionSort(int n,int Array )int i,j,max,t;int i,j,max,t;/*/*定义定义4 4个整型变量个整型变量 */for(i=0;i

36、=n-2;i+)for(i=0;i=n-2;i+)/*/*做做 n-1 n-1 遍扫描寻找最大元素遍扫描寻找最大元素 */max=i;max=i;/*/*记录当前扫描最大元素的位置记录当前扫描最大元素的位置*/for(j=i+1;j=n-1;j+)for(j=i+1;j Arraymax)if(Arrayj Arraymax)max=j;max=j;/*/*记录大数元素的下标位置记录大数元素的下标位置*/*/*利用利用 t t 变量做三角对换变量做三角对换 */t=Arrayi,Arrayi=Arraymax,Arraymax=t;t=Arrayi,Arrayi=Arraymax,Arraym

37、ax=t;/*End of SelectionSort function*/*End of SelectionSort function*/40选择排序法降序方式排序操作过程选择排序法降序方式排序操作过程 n例如：对序列例如：对序列89，29，68，90，17，34，45操作。操作。|89 29 68 90 17 34 45 90|29 68 89 17 34 45 90 89|68 29 17 34 45 90 89 68|29 17 34 45 90 89 68 45|17 34 29 90 89 68 45 34|17 29 90 89 68 45 34 29|17 每行表示该算法的一次

38、迭代，即从尾部到竖线的一遍扫每行表示该算法的一次迭代，即从尾部到竖线的一遍扫描；找到的最大元素用黑体字表示，竖线左边元素已经描；找到的最大元素用黑体字表示，竖线左边元素已经位于它们的最终位置，所以在当前和以后的循环中，都位于它们的最终位置，所以在当前和以后的循环中，都不必再操作了。排序操作过程如下：不必再操作了。排序操作过程如下：415.查找算法查找算法 n查找是指从给定的集合（或者是多重集，它允许几个元素查找是指从给定的集合（或者是多重集，它允许几个元素具有相同的值）中查找一个给定的值（称为具有相同的值）中查找一个给定的值（称为查找键查找键 K）。）。n常用的查找算法有常用的查找算法有顺序查

39、找顺序查找和和折半查找折半查找，还有那些将原来，还有那些将原来的集合表示为另一种形式以方便查找的算法等等。的集合表示为另一种形式以方便查找的算法等等。顺序查找顺序查找直接从头到尾搜索集合的查找键。直接从头到尾搜索集合的查找键。折半查找折半查找必须首先将集合按照降序或升序排序，必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合的查找键，所以，当集合然后利用折半技术搜索集合的查找键，所以，当集合是有序的时候，使用折半查找效率高、速度快。是有序的时候，使用折半查找效率高、速度快。42判定哪一种算法是最佳方案判定哪一种算法是最佳方案 n针对排序和查找方面的算法更多，例如，采用针对排序和查找方面

40、的算法更多，例如，采用分治法分治法、减治法减治法、变治法变治法等等方法中的各种排序和查找算法。等等方法中的各种排序和查找算法。n运用经典的算法设计技术运用经典的算法设计技术时空权时空权衡衡、动态规划动态规划、贪婪技术贪婪技术等；算法能等；算法能力的极限中的力的极限中的决策树决策树技术、在技术、在多项式多项式的时间内求解的时间内求解、数值分析数值分析，超越算法超越算法能力的极限中的能力的极限中的回溯发回溯发、分支界限法分支界限法和和近似算法设计近似算法设计技术。技术。技术和思维技术和思维方式都是不方式都是不可或缺的可或缺的鞭策学习和鞭策学习和掌握程序设掌握程序设计中的算法计中的算法设计与分析设计

41、与分析技术技术n托马斯托马斯爱迪生（爱迪生（1847-1931）的名）的名言：言：“不断关注那些已被他人成功应不断关注那些已被他人成功应用的新思路。你的原创思想只应该应用的新思路。你的原创思想只应该应用在那些你正在研究的问题上用在那些你正在研究的问题上”。435.3 程序设计步骤与程序设计方法程序设计步骤与程序设计方法 u5.3.1 程序设计步骤程序设计步骤 u5.3.2 程序设计方法程序设计方法 44程序设计步骤程序设计步骤n 一般程序设计应该包含以下一般程序设计应该包含以下4个步骤：个步骤：（1）针对具体问题进行分析）针对具体问题进行分析了解问题性质，明确问题解决所达目标，了解问题性质，明

42、确问题解决所达目标，提供的输入是什么？最终实现的输出是什么？执行中要做什么？怎么提供的输入是什么？最终实现的输出是什么？执行中要做什么？怎么做？并建立相应的数学模型。做？并建立相应的数学模型。（2）确定数据结构并设计相应的算法）确定数据结构并设计相应的算法对具体问题进行概念抽象，构造对具体问题进行概念抽象，构造出解决问题的轮廓，设计程序的数据结构和算法。出解决问题的轮廓，设计程序的数据结构和算法。（3）编写实现算法的程序）编写实现算法的程序根据算法确定解决问题的详细步骤，通常是根据算法确定解决问题的详细步骤，通常是通过绘制程序流程图，来描述问题处理的过程；然后按照流程图的描通过绘制程序流程图，

43、来描述问题处理的过程；然后按照流程图的描述选用某种程序设计语言编写程序。述选用某种程序设计语言编写程序。（4）测试与调试程序）测试与调试程序在程序设计过程中，经常不是那么一帆风顺的，在程序设计过程中，经常不是那么一帆风顺的，尤其是初学者会遇到各种这样或那样的问题，还有一些问题可能是不尤其是初学者会遇到各种这样或那样的问题，还有一些问题可能是不可预测的，往往不得不返到上一步骤中更改或调整相应的内容，并将可预测的，往往不得不返到上一步骤中更改或调整相应的内容，并将相应文档也一并修改，通过举一反三的方法来解决给定问题。相应文档也一并修改，通过举一反三的方法来解决给定问题。45测试程序与调试程序测试程

44、序与调试程序 n测试程序测试程序 为了发现程序中的设计错误而运行程序为了发现程序中的设计错误而运行程序。所使用的测试用例尤其重要，因为不仅需要合法所使用的测试用例尤其重要，因为不仅需要合法值域用例，而且非法值域用例也是必须的。值域用例，而且非法值域用例也是必须的。程序测试的成功与否直接可以体现程序健壮性。程序测试的成功与否直接可以体现程序健壮性。当软件项目是由团队开发时，测试程序可分为：当软件项目是由团队开发时，测试程序可分为：单元测试、组装测试和确认测试。单元测试、组装测试和确认测试。n调试程序调试程序 错误定位和纠错的过程，这一过程的快慢与程序设计错误定位和纠错的过程，这一过程的快慢与程序

45、设计人员的编程经历和经验是密切相关的人员的编程经历和经验是密切相关的。46高级语言编写和运行过程高级语言编写和运行过程yesyes源文件源文件目标文件目标文件可执行文件可执行文件其它目标文件库函数开始编辑源程序检查确认 有错？编译程序 有错？有错？运行程序 有错？yesnonoyes连接程序no结束no数据47程序设计方法程序设计方法n早期的程序设计方法早期的程序设计方法n结构化程序设计方法结构化程序设计方法 n面向对象程序设计方法面向对象程序设计方法 481.早期的程序设计方法早期的程序设计方法 n早期的程序设计方法早期的程序设计方法追求程序的高效率，编程过份依赖追求程序的高效率，编程过份依

46、赖技巧，忽视程序清晰，而不注重所编写程序的结构，很技巧，忽视程序清晰，而不注重所编写程序的结构，很少考虑程序的规范化问题，也就是没有固定程序设计方少考虑程序的规范化问题，也就是没有固定程序设计方法的时期。法的时期。n程序的可读性、可重用性都很差。其中典型问题是：频程序的可读性、可重用性都很差。其中典型问题是：频繁使用繁使用goto语句，特意算计如何节省内存空间。语句，特意算计如何节省内存空间。n虽然这些方法存在很多问题，但当时受限于计算机运行虽然这些方法存在很多问题，但当时受限于计算机运行速度慢、内存容量小、硬件价格昂贵，程序的规模也比速度慢、内存容量小、硬件价格昂贵，程序的规模也比较小，对于

47、单人完成较为简单的任务，事实上这些方法较小，对于单人完成较为简单的任务，事实上这些方法还是经常被采用的。还是经常被采用的。492.结构化程序设计方法结构化程序设计方法 n结构化程序设计方法结构化程序设计方法出现在出现在70年代中期。年代中期。n随着计算机硬件成本急剧下降，软件需要处理的复杂问随着计算机硬件成本急剧下降，软件需要处理的复杂问题也就越来越多。题也就越来越多。n为了摆脱为了摆脱6070年代初的软件危机，因为当时编程无章年代初的软件危机，因为当时编程无章可循，程序常常带有强烈的个人色彩，程序的可读性差，可循，程序常常带有强烈的个人色彩，程序的可读性差，程序的调试和维护更困难，促使人们认

48、真反省和研究程程序的调试和维护更困难，促使人们认真反省和研究程序设计中一系列根本性问题：序设计中一系列根本性问题：程序的基本结构是什么？程序的基本结构是什么？程序设计应当采用什么方法？程序设计应当采用什么方法？算法设计先于程序编码？算法设计先于程序编码？清晰第一，效率第二？清晰第一，效率第二？程序设计技术与方法如何规范化和工程化？程序设计技术与方法如何规范化和工程化？解决手工解决手工作坊式软作坊式软件开发的件开发的弊端弊端50结构化程序设计方法的特点结构化程序设计方法的特点 n使得程序层次分明、逻辑清晰、功能独立，简化了开发使得程序层次分明、逻辑清晰、功能独立，简化了开发程序的复杂性，增加了程

49、序的可靠性，能够充分发扬团程序的复杂性，增加了程序的可靠性，能够充分发扬团队精神快速而高效地完成项目开发，增强系统的可维护队精神快速而高效地完成项目开发，增强系统的可维护性，使程序设计更加规范化。性，使程序设计更加规范化。n结构化程序设计方法的结构化程序设计方法的特点：特点：自顶向下、逐步求精自顶向下、逐步求精划分功能模块划分功能模块结构化编程结构化编程513.面向对象程序设计方法面向对象程序设计方法 n面向对象程序设计方法面向对象程序设计方法出现在出现在80年代中后期。年代中后期。n随着计算机硬件技术的高速发展，计算机的性能也越来随着计算机硬件技术的高速发展，计算机的性能也越来越强，用途也更

50、加广泛。软件产业所面临的问题需求不越强，用途也更加广泛。软件产业所面临的问题需求不断扩大，程序也就越来越庞大而复杂。断扩大，程序也就越来越庞大而复杂。n在面向过程的程序设计中在面向过程的程序设计中软件设计的主要工作就是软件设计的主要工作就是用不同的功能模块分别描述它们的求解过程。用不同的功能模块分别描述它们的求解过程。n在结构化程序设计中在结构化程序设计中数据和处理数据的过程分离为数据和处理数据的过程分离为相互独立的实体，它只是封装了各个功能模块，而每个相互独立的实体，它只是封装了各个功能模块，而每个功能模块可以随意修改未加封装的数据。功能模块可以随意修改未加封装的数据。n新时期的新问题，以及