《大学计算机基础》第二层次子课程-C 程序设计基础(2010V1)

大学计算机基础北京航空航天大学教学课件1第二层次子课程——C程序设计基础5.3程序设计步骤与程序设计方法

5.1程序和程序设计语言

5.2算法

5.4常用程序设计语言

5.5程序设计范型2本课程重点程序的概念程序设计语言的结构算法的概念与描述方法程序设计步骤程序设计方法VC集成开发环境35.1程序和程序设计语言5.1.1程序的一般概念

5.1.2程序设计语言的概述

5.1.3程序设计语言的结构

45.1.1程序的一般概念

生活中程序的概念何事？策划导演例1：年终总结会的程序：会议主持宣布会议开始领导讲话个人或团队代表发言领导总结会议主持宣布会议结束55.1.1程序的一般概念（续1）

生活中程序的概念甲地乙地丙地A线8公里B线5公里C线4公里步行骑车开车时间红绿灯铁道上坡、下坡依据实际案例并精心计算

解决该计算问题的方法、步骤就包含了程序的概念。例2：某人从甲地到丙地去。65.1.1程序的一般概念（续2）

计算机程序的概念：为实现某一算法而编写的指令序列。宏观地描述该指令序列，可用计算机的机器语言汇编语言高级语言用经典的公式可表示为：程序=算法+数据结构1976年NiklausWirth（也是Pascal语言发明者，1984年获得图灵奖）的专著：Algorithms＋DataStructures＝Programs75.1.2程序设计语言的概述

程序设计——编写程序的全过程。有学者认为：程序设计=算法+数据结构+程序设计语言程序设计语言——人和计算机之间对话和交流的一种工具，用于描述计算机所执行的操作。计算机程序设计语言有几百种，但是最常用的不过10多种，了解一些程序设计语言的不同特性，有助于为特定任务而选择适当的程序设计语言。8不同类型的计算机语言机器语言（MachineLanguage）汇编语言（AssemblyLanguage）高级语言（HighLevelLanguage）程序设计语言的特点

91.机器语言（MachineLanguage）指令——指挥计算机完成某个基本操作的命令。机器语言程序注解1011000000001000001011000000101011110100把8存放到累加器A中。将10与累加器A中的8相加，结果存在A中。程序结束。指令系统——所有的指令集合。（第一代程序设计语言）机器语言——用二进制代码表示指令系统的语言。机器语言程序——由二进制代码按一定规则组成的、能被机器理解和运行的指令序列。（也称可执行程序）例如：计算累加器A=8+10的机器语言程序如下：102.汇编语言（AssemblyLanguage）汇编语言——实质就是以容易记忆的代码或英文单词来代替约定的机器指令。（第二代程序设计语言）汇编语言源程序注解MOVA,8ADDA,10HLT把8存放到累加器A中。将10与累加器A中的8相加，结果存在A中。程序结束。例如：用ADD表示加、SUB表示减、JMP表示跳转、MOV表示数据的传送指令等。汇编源程序——使用汇编语言编写的程序。例如：上述计算累加器A=8+10的汇编语言程序如下：113.高级语言（HighLevelLanguage）高级语言——类似数学语言或人的自然语言，同时又不依赖于某种计算机硬件，使得设计编制的程序能够在所有机器上通用。（第三代程序设计语言）程序设计语言在不同的系统平台使用比较普遍的有：FORTRAN、ALGOL、COBOL、LISP、PL/I、BASIC、SIMULA67、Pascal、C、Smalltalk80、Ada、C++、VC、VB、Delphi、Java、JavaScript、C#、VisualBASIC.NET。可视化语言——构成了命令式语言中的另一个子类。最流行的可视化语言VisualBASIC（1999年），已被VisualBASIC.NET（2002年）取代。提供拖拉式生成代码段的功能。一度被认作第四代语言，此说法已不再使用了。12程序设计语言的特点

机器语言的特点：编程难效率高需要指令系统难读难维护高级语言的特点：编程容易效率低

需要编译系统易读易维护汇编语言的特点：编程不容易效率较高需要汇编程序不易读不易维护135.1.3程序设计语言的结构

程序结构的多样性：结构化程序模块化程序面向对象的程序结构一个良好结构的程序具有以下等特点：结构清晰容易阅读容易理解容易验证容易维护1996年，计算机科学家Boehm和Jacopini提出并从数学上证明任何一个算法，都能以三种基本控制结构表示，即顺序结构、选择结构和循环结构。14结构化程序设计中——顺序结构

按照程序语句行的自然顺序，一条语句一条语句地执行程序。语句A入口语句B出口15结构化程序设计中——选择结构

根据条件的判断确定应该执行哪一条分支的语句序列。（又称为分支结构）入口出口语句序列A语句序列B条件真假单分支、多分支结构？

16入口假真语句序列出口repeat循环结构

测试条件结构化程序设计中——循环结构

主要用于重复执行相同的语句序列（被称为循环体），当（直到）测试条件为假时才可终止执行循环体。出口入口语句序列假测试条件真while循环结构17结构化程序设计的特点

每种结构，只有一个入口和一个出口，这是结构化设计的一个原则。遵循结构化程序设计的原则，按照结构化程序设计方法设计出的程序具有明显的优点：其一，程序易读、理解和维护。程序员用结构化编程方法，将复杂程序分解成若干子结构，便于控制、降低程序的复杂性，因此容易编写程序，同时便于验证程序。其二，提高编程工作效率，降低软件开发成本。由于结构化编程方法能够把错误控制到最低限度，因此能够减少调试和查错的时间。185.2算法5.2.1算法的定义、分类与特征

5.2.2算法的描述方法5.2.3程序设计典型算法195.2.1算法的定义、分类与特征

Algorithms＋DataStructures＝Programs1976年N·Wirth的程序概念，在计算机软件开发行业中产生了极为深远的影响，从而推动了软件开发技术和方法步入正轨，使人们开始深入研究数据结构和算法设计与分析的技术和方法。#include<stdio.h>voidmain()//c1_5.cpp{

inta,b;

printf("Pleaseenteraandb:");

scanf("%d%d",&a,&b);a=a+b;b=a-b;a=a-b;

printf("a=%d,b=%d\n",a,b);}#include<stdio.h>voidmain()//c1_6.cpp{

inta,b,c;

printf("Pleaseenteraandb:");

scanf("%d%d",&a,&b);c=a;a=b;b=c;

printf("a=%d,b=%d\n",a,b);}201.

算法的定义与分类

CPU所遵循的机器周期与下面这个算法一样简单。

只要未发出停机指令就执行以下步骤：取一条指令。解码该指令。执行该指令。生活当中的普通活动——剥豌豆。

获得一篮子未剥皮的豌豆和一只空碗。只要篮中还有豌豆就执行下面的步骤：从篮子里拿出一个豌豆。剥开豌豆的豆荚。把剥落得豆放到碗里面。扔掉空豆荚。211.

算法的定义与分类

（续1）算法的定义——算法是定义一个可终止过程的一组有序的、无歧义的、可执行的步骤的集合。华氏温度与摄氏温度的转换问题算法1：用代数公式表示

算法2：用指令表示将摄氏温度数值乘以，然后在乘积上加32。外行则认为该指令是模糊的、有歧义的。算法的细致程度221.

算法的定义与分类

（续2）用一张正方形的纸折叠成一只鸟该过程通过自然的沟通方式常常会引起误解。有些时候是因为算法描述中使用的术语可能拥有多种含义。计算机科学解决歧义性问题的方法建立一组严格定义的构件块。利用一系列的构件块来构建算法的表示。这种构件块称作原语（primitive）。231.

算法的定义与分类

（续3）原语——被用于消除算法表示中的歧义性问题。语法——是原语的符号表示（air）。语义——是指该原语的含义（气体物质）。原语的集合以及说明如何组合这些原语来表示比较复杂的想法的规则集合就构成了一种程序设计语言。程序、算法和进程既是不同的却又有关联的。程序是一个算法的表示。进程是执行算法的活动。241.

算法的概念算法——解决某个具体问题而采取的方法与步骤的完整和准确的描述。是指令的有限序列，其中每一条指令表示一个或多个操作。是问题的程序化解决方案，这些解决方案本身并不是答案，而是获得答案的精确指令。算法的分类顺序算法：是由冯·诺依曼型计算机体系结构所决定的，其主要思想是指令逐条运行，每次执行一步操作。并行算法：要求在一些更新式的计算机中可以在同一时间执行多条指令。252.算法的特征一个算法必须具备五项基本特征：有穷性、确定性、数据输入、数据输出和可行性。（1）有穷性——算法是有序指令的集合，并在执行有穷步骤后能够终止。（2）确定性——每条指令必须有确切的含义，且无二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入数据只能得到相同的输出数据。（3）输入数据——可有零个或多个输入数据。这些输入数据取自于某个特定对象的集合。（4）输出数据——必须有一个或多个输出数据。（5）可行性——描述的操作都可以通过已经实现的基本运算执行有限次来实现，也可以证明整个算法实施后可以得到预期的解。262.算法的特征（续1）算法的发现程序开发由两个活动组成——发现潜在的算法和以程序的方式表示算法。问题求解的艺术数学家（波利亚G·Polya）在1945年提出非严格定义的问题求解阶段：第1阶段理解问题。第2阶段设计一个解决问题的计划。第3阶段完成计划。第4阶段从准确度及其是否有潜力作为一个解决其他问题的工具这两方面来评估这个计划。上述阶段移植到程序开发中变成：第1阶段理解问题。第2阶段寻找一个可能解决问题的算法过程的思路。第3阶段阐明算法并且用程序将其表达出来。第4阶段从准确度及其是否有潜力作为一个工具解决其他问题这两方面来评估这个程序。阶段与步骤的差异27例.甲承担了确认乙的3个孩子年龄的任务

乙告诉甲3个孩子的年龄乘积是36。

在考虑了这个线索以后，甲要求乙给出另外的线索。

乙告诉甲3个孩子的年龄之和。

甲再次要求乙给出其他线索。

乙告诉甲：他的最大的一个孩子弹钢琴。

在得到这个线索之后，甲得到了乙的3个孩子的年龄。（1，1，36）（1，6，6）（1，2，18）（2，2，9）（1，3，12）（2，3，6）（1，4，9）（3，3，4）（a）乘积为36的三元组这种解决问题过程中的不规则性是开发问题求解的系统方法的基础。另一个不规则性在于，那些还没有得到明显成功的问题解决者所得到的神奇灵感可能在完成其他任务的时候突然成为了原来问题的一个解决方法。

1+1+36=381+6+6=13

1+2+18=212+2+9=13

1+3+12=162+3+6=11

1+4+9=143+3+4=10（b）a中的每个三元组的和2+2+9=1328例.求甲乙丙丁赛跑的名次排序

在甲、乙、丙和丁进行赛跑之前，他们分别对结果进行预测：甲预测乙将会获胜。乙预测丁将是最后一名。丙预测甲是第三名丁预测甲的预测将是正确的。这几个预测只有一个是正确的，并且是最后的获胜者做出的预测。解1：丙、乙、甲、丁解2：丙、丁、甲、乙进入问题后，会发现：获得完整的解决方法的过程仅仅是将我们的知识在此处扩展应用。被排除29算法的入门

知道怎样进入问题并不等于知道如何去做这件事。为了得到立足点，也就是认识到如何把对于问题的初始介入扩展为问题的解决方法，就为要求问题解决者创造一个可能的入口。

对于如何入门？波利亚和其他人提出了很多通用的方法。反方向解决问题（白纸与纸鸟）寻找一个相关的、解决起来较简单的并且在此以前已经得到解决的问题，然后尝试把这个解决方法用到当前问题中。逐步求精（stepwiserefinement）数据处理中一种重要设计方法自顶向下方法（top-downmethodology）一般到特殊自底向上方法（bottom-upmethodology）特殊到一般

30算法的入门

（续1）四个人名（David、Alice、Carol和Bob）按照升序排序指令。交换名字David和Alice。将名字Carol移到Alice和David之间。将名字Bob移到Alice和Carol之间。

通常，程序开发并不是去解决一个问题的一个特定实例，而是要去寻找一种适用于求解一个问题的所有实例的一般算法。可以通过考虑一个特殊的情况来进入问题，然后得到一个能够用于开发通用算法的一般原则。（三个人名排序指令）

特定实例31例5.1一个非算法的计数过程①令n为0；②置n为n+1；③返回②。结论：不能称为算法。原因：违背了算法特征中（1）、（4）、（5）。有穷性（有效性）：考察下面这条指令:给出一个所有整数的列表。××32例5.2计数器算法用自然语言编写一个不超过1万次的计数器算法：①令n为0；②置n为n+1③若n小于10000，则返回②；否则，输出n之值，且算法到此结束。结论：是算法。原因：符合算法特征。在算法设计过程中，其实还有有关正确性、可读性、健壮性、效率与低存储量需求，以及算法效率的度量等问题。335.2.2算法的描述方法

流程图（FlowChart）PAD图（ProblemAnalysisDiafram，问题分析图）N-S图自然语言伪代码UML图（UnifiedModelingLanguage，统一建模语言）341.流程图流程图（框图）用不同形状的几何图形表示不同性质的操作，用流程线指明算法的执行方向。ANSI(美国国家标准化协会)、ISO（国际标准化组织）和我国国家标准中均有类似的规定。常见的流程图符号如下：向下或向右的流程线可以不画出箭头。当流程线有交叉时，则画一半圆通过交叉点。35用流程图描述的计数器算法362.PAD图由日立公司推出的PAD图是一种二维图。即从上向下顺序执行，从左到右表示层次关系。表示三种基本结构的PAD图如下：373.N-S图1973年美国两位学者提出无流程线的N-S图（盒图）。结构化程序设计由三种基本结构而组成，则算法也应采用结构化描述方法，N-S图的基本单元是矩形框，框内可以有三种基本结构，形如堆积木，也只有一个入口和一个出口。三种基本结构的N-S图如下：38用N-S图描述的计数器算法394.自然语言自然语言是人们日常生活、工作和学习中使用的通用语言，使用自然语言的文字描述算法通俗易懂，但也有它的缺陷：（1）容易产生歧义性，因为自然语言经常要根据上下文才能判别其含义，不太严格。（2）自然语言很难清楚地表达算法的逻辑流程，对于算法中的条件判断、循环，尤其是在这些处理中还有多层嵌套，就很难用清晰而直观的语言来表达算法的流程。因此仅适于描述简单问题。405.伪代码伪代码是介于自然语言和计算机语言之间的文字和符号，它不能被计算机所理解，但使用伪代码描述的算法很容易转变成某种编程语言。//用伪代码描述的计数器算法如下：

n←0don←n+1whilen<10000

输出n，且算法到此结束。常用的伪代码是用自然语言与类Pascal或类C语言相结合的方法来描述算法。41流程图形的绘制工具当使用图形描述算法时，流程图形的绘制工具有很多。一般比较简单的图形可用Word或PowerPoint中的绘图工具栏来制作完成，若安装了功能强大的MicrosoftOfficeVisio2003，则可以更快地绘制具有专业水平的高质量图形。在Visio2003中：含有丰富的基本流程图形状。能够快速、简便地建立流程图、组织图、日历时间表和其它多种图表。支持缩放矢量图形（SVG），这是一种新的图形格式标准。集合Internet的运用，可使用不同的语言创建绘图、创建包含多种语言的绘图以及跨多种语言共享绘图和展开协作。通过支持新的汉字编码标准GB18030，可从这个新的字符编码集中创建包含汉字的绘图。425.2.3程序设计典型算法算法——数值算法或非数值算法：数值算法——主要用于数值求解或分析，如：求和、求平方根、解方程、用组合梯形法则求定积分等。非数值算法——主要用于各领域管理类的信息处理，如：各种排序、查找等。本节介绍一些简单的常用算法，并假设各数据均能满足值域要求。431.求3个整数的最大值算法为了编写求3个整数最大值的通用实现过程，采用主函数调用子函数的形式描述算法。（1）主函数算法描述如下：①输入三个整数a,b,c;②max=max3(a,b,c);③输出max。（2）max3子函数算法描述如下：

①从a与b中取大数送m中;②从m与c中取大数送m中;③返回m给主函数。44求3个整数的最大值的C程序/*使C预编译包含I/O头文件，则可用scanf、printf函数*/#include<stdio.h>voidmain(void){

inta,b,c,max;/*定义4个整型变量*/

intmax3(inta,intb,intc);/*max3函数原形声明*/

printf(“Input3integernumbers:”);/*

输出双引号中的提示信息*/

scanf(“%d%d%d”,&a,&b,&c);/*

输入3个整数*/max=max3(a,b,c);/*调用max3函数求最大值*/

printf(“Themaxis:%d\n”,max);/*输出max中的最大值*/}

/*Endofmainfunction*//*

求3个整数的最大值的子函数max3*/intmax3(inta,int

b,intc)/*max3函数将返回整型值*/{

intm;/*定义m整型变量

*/

if(a>b)m=a;/*从a与b中取大数送m中*/elsem=b;if(m>c);/*从m与c中取大数送m中，“；”即m=m*/elsem=c;

return(m);/*返回m给主函数*/}

/*Endofmax3function*///Lab2.c452.欧几里得算法求解两个不全为0的非负整数m和n的最大公约数，可以采用以下欧几里得算法。（1）欧几里得算法主函数描述如下：①输入两个不全为0的非负整数m,n;②Ecd=Euclid(m,n);③输出Ecd，且算法到此结束。（2）Euclid(m,n)子函数算法描述如下：

whilen≠0dor←mmodnm←nn←rreturnm463.

两个变量值的交换算法计算机实现的两个变量值的交换算法如下：①令a=5,b=10②c←a,a←b,b←c③输出a和b的值。/*两个变量值交换算法的C源程序*/voidmain(void){inta=5,b=10,c;/*定义a、b、c3个整型变量*/

printf(“交换前:a=%d,b=%d\n”,a,b);/*

交换前输出a和b的值*/c=a;/*

将a中的值赋值给c*/a=b;/*将b中的值赋值给a*/b=c;/*将c中的值赋值给b*/

printf(“交换后:a=%d,b=%d\n”,a,b);/*交换后输出a和b的值*/}

/*Endofmainfunction*/三角对换法

474.排序算法给定一个有n个元素可排序的序列，例如数字数据或字符串数据等，要求按照升序或降序方式重新排列。排序算法：如冒泡排序法、选择排序法、插入排序法、合并排序法、快速排序法等等排序算法。48蛮力法中的选择排序法按照降序方式排序的选择排序算法：SelectionSort（Array[0..n-1]）/*本算法用选择排序法对给定数组按照降序方式排序*//*Array[0..n-1]是有n个元素的可排序数组*//*本算法的结果在Array数组中*/fori←0ton-2domax←iforj←i+1ton-1doifArray[j]>Array[max]max←jswapArray[i]andArray[max]49选择排序法的

C

程序/*SelectionSort(Array[0..n-1])选择排序算法的C源程序*/voidSelectionSort(intn,intArray[]){inti,j,max,t;/*定义4个整型变量*/for(i=0;i<=n-2;i++)/*做n-1遍扫描寻找最大元素*/{max=i;/*记录当前扫描最大元素的位置*/for(j=i+1;j<=n-1;j++)/*在n-i

个元素中找最大元素*/if(Array[j]>Array[max])max=j;/*记录大数元素的下标位置*/

/*利用t变量做三角对换*/t=Array[i],Array[i]=Array[max],Array[max]=t;}}/*EndofSelectionSortfunction*/50选择排序法降序方式排序操作过程例如：对序列89，29，68，90，17，34，45操作。|8929689017344590|2968891734459089|6829173445908968|2917344590896845|1734299089684534|1729908968453429|17每行表示该算法的一次迭代，即从尾部到竖线的一遍扫描；找到的最大元素用黑体字表示，竖线左边元素已经位于它们的最终位置，所以在当前和以后的循环中，都不必再操作了。排序操作过程如下：51插入排序的基本思想每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。初始状态：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]排序52在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序法，这里只介绍最简单的直接插入排序法。直接插入排序排序将姓名列表用伪代码表达的插入排序算法:procedureSort(list)N←2;while(N的值不超过列表的长度）do(把列表的第N项作为主元项；把主元项移到一个临时位置使该列表留出一个空位置；while(如果这个空位置上面存在一个名字并且那个名字比主元大)do(把这个名字向下移到空位置上使该名字上面留出一个空位置)把主元项插到列表的空位置上；N←N+1)53直接插入排序函数模板//用直接插入排序法对数组A中的元素进行升序排列template<classT>//9-11.h源10-1.hvoidInsertionSort(TA[],intn){inti,j;Ttemp;

for(i=1;i<n;i++)

//将下标为1～n-1的元素逐个插入到已排序序列中适当的位置

{

//从A[i-1]开始向A[0]方向扫描各元素,寻找适当位置插入A[i]

j=i;temp=A[i];while(j>0&&temp<A[j-1]){

//逐个比较，直到temp>=A[j-1]时，j便是应插入的位置。

//若达到j==0，则0是应插入的位置。

A[j]=A[j-1];

//将元素逐个后移，以便找到插入位置时可立即插入。

j--;}A[j]=temp;

//插入位置已找到，立即插入。

}}直接插入排序54应用直接插入排序函数模板排序//9-11.cpp源10-1.cpp#include"10-1.h"voidmain(){ inti,data[]={1,3,5,7,9,2,4,6,8,10};constintMax=10;

cout<<"排序前的原始数据："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;

cout<<“开始以直接插入排序。。。"<<endl;

InsertionSort(data,Max);

cout<<“直接插入排序结果："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;}直接插入排序

//9_11.cpp55选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。[541020123]初始状态：3[41020125]34[1020125]第i次选择后，将选出的那个记录与第i个记录做交换。345[201210]......排序56直接选择排序在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。排序57直接选择排序函数模板template<classT>voidSwap(T&x,T&y){Ttemp;temp=x;x=y;y=temp;}直接选择排序template<classT>//9-12.hvoidSelectionSort(TA[],intn){int

smallIndex;//每一次选出的最小元素之下标

inti,j;for(i=0;i<n-1;i++){smallIndex=i;

//在元素A[i+1]…A[n-1]中逐个比较显出最小值

for(j=i+1;j<n;j++)if(A[j]<A[smallIndex])

smallIndex=j;Swap(A[i],A[smallIndex]);}}58应用直接选择排序函数模板排序//9-12.cpp#include"10-2.h"voidmain(){ inti,data[]={1,3,5,7,9,2,4,6,8,10};constintMax=10;

cout<<"排序前的原始数据："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;

cout<<"开始以直接选择排序。。。"<<endl;

SelectionSort(data,Max);

cout<<"直接选择排序结果："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;}直接选择排序

//9_12.cpp59交换排序的基本思想两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。最简单的交换排序方法是起泡排序。排序60对具有n个元素的序列按升序进行起泡排序的步骤：①首先将第1个元素与第2个元素进行比较，若为逆序，则将两元素交换。然后比较第2、第3个元素，依次类推，直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟起泡排序，最大的元素便被交换到第n个位置。②对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。③如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。起泡排序61起泡排序过程示意图对整数序列85243按升序排序起泡排序8524352438243582345823458初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的62起泡排序函数模板//用起泡法对数组A的n个元素进行排序template<classT>//9-13.hvoidBubbleSort(TA[],intn){inti,j;

int

lastExchangeIndex;

//用于记录每趟被交换的最后一对元素中较小的下标

i=n-1;

//i是下一趟需参与排序交换的元素之最大下标

while(i>0)

//持续排序过程，直到最后一趟排序没有交换发生，或已达n-1趟

{lastExchangeIndex=0;

//每一趟开始时，设置交换标志为0（未交换）

for(j=0;j<i;j++)

//每一趟对元素A[0]…A[i]进行比较和交换

if(A[j+1]<A[j])

//如果元素A[j+1]<A[j]，交换之

{Swap(A[j],A[j+1]);

lastExchangeIndex=j;

//记录被交换的一对元素中较小的下标

}

i=lastExchangeIndex;//将i设置为本趟被交换的最后一对元素中较小的下标}}起泡排序63应用起泡排序函数模板排序//9-13.cpp#include"10-3.h"voidmain(){ inti,data[]={1,3,5,7,9,2,4,6,8,10};constintMax=10;

cout<<"排序前的原始数据："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;

cout<<"开始以起泡排序。。。"<<endl;

BubbleSort(data,Max);

cout<<"起泡排序结果："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;}起泡排序

//9_13.cpp64顺序查找基本思想从数组的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个数组中没有与待查找关键字相等的元素，就是查找不成功。查找65顺序查找函数模板#ifndefSEARCH_METHODS//9-14.h#defineSEARCH_METHODS//用顺序查找法在数组list中查找值为key的元素//若找到，返回该元素下标，否则返回-1template<classT>int

SeqSearch(Tlist[],intn,Tkey){

for(inti=0;i<n;i++)if(list[i]==key)returni;return-1;}#endif

//SEARCH_METHODS查找66用伪代码表达的顺序搜索算法procedureSearch(List,TargetValue)if(List空)then(宣布查找失败)else(选择列表中的第一个表项作为TestEntry;while(TargetValue>TestEntry

并且还有表项没有检查)

（选择列表中下一个表项作为TestEntry）；if(TargetValue=TestEntry)then(宣布查找成功)else

(宣布查找失败))endif顺序搜索是以一种循环的方式重复执行一个过程。List：空列表或升序列表67折半查找的基本思想如果是在一个元素排列有序的数组中进行查找，可采用折半查找方法。对已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。查找68折半查找过程示意图用折半查找法，在下列序列中查找值为21的元素：513192137566475808892H=11M=(L+H)/2=6513192137L=1H=M-1=5M=(L+H)/2=3M2137HL=M+1=4L21==list[M]MLow——LMid——MHigh——H21>list[M]M=(L+H)/2=4L=121<list[M]查找69折半查找函数模板//用折半查找方法，在元素呈升序排列的数组list中查找值为key的元素template<classT>//9-15.hint

BinSearch(Tlist[],intn,Tkey){intmid,low=0,high=n-1;Tmidvalue;while(low<=high)//low<=high表示整个数组尚未查找完

{mid=(low+high)/2;//求中间元素的下标

midvalue=list[mid];//取出中间元素的值

if(key==midvalue)returnmid;//若找到,返回下标

elseif(key<midvalue)high=mid-1;//若key<midvalue将查找范围缩小到数组的前一半

elselow=mid+1;//否则将查找范围缩小到数组的后一半

}return-1;//没有找到返回-1}折半查找70用伪代码表达的二分搜索算法procedureSearch(List,TargetValue)if(List空)then(报告查找失败)else[选择列表的中间项作为TestEntry;

执行以下与条件相符case指令块case1:TargetValue=TestEntry（报告查找成功）case2:TargetValue<TestEntry

(应用Search过程查看TargetValue是否在List中位于TestEntry

项之前的部分，并报告查找结果)case3:TargetValue>TestEntry

(应用Search过程查看TargetValue是否在List中位于TestEntry

项之后的部分，并报告查找结果)]endif二分搜索是把每一阶段重复当作前一阶段的子任务，该技术被称作递归（recursion）71算法的有效性和准确性尽管当今的计算机每秒可以处理数百万条指令，有效性仍旧是算法设计中所关注的一个主要问题。通常，在效率高低的两个算法之间的选择能够产生对于问题的实用或者不实用的两种解。

例如：一个大学的教务主任需要面对检索和更新学生记录的任务。假设：给定一个学生的学号（目标值），要在“当前学生”文件（包括3万多条学生记录）中找到。72算法的有效性和准确性（续）使用顺序搜索算法：不能推断究竟要查找多少条记录才能得到结果。可以假定在多次查找之后，认为平均查找深度是表的一半长度。所以估计平均每次大概需要寻找15000条记录。

10ms/一条记录则：150s1ms/一条记录则：15s结论：无法容忍。使用二分搜索算法：通过比较目标值和表的中间项来进行查找。如果不是期望的记录，则至少将查找限制在原始表的一半。因此,30000、15000、7500、3750……最多15次之后，目标值应该被找到。

10ms/一条记录则：0.15s结论：瞬间完成。

73算法的有效性和准确性（续）总结：使用搜索方法的选择将对该应用产生了巨大影响。该例子表现了计算机科学领域中对大家熟知的算法分析的重要性，这种分析包含了对于资源的研究，比如算法需要消耗的时间或者存储空间资源。这种研究的一个主要应用在于给出了二选一算法之间不同优点的评估。算法分析通常包括最优情况分析、最差情况分析和平均情况分析。不能关注于表的特定长度，而是要尝试列出某种可以表示任何长度的表中进行查找的算法的性能公式。具体而言，当需要在长度为n的表中应用时：顺序搜索算法的平均查找长度是——n/2。二分搜索算法在最差情况下的查找长度不超过——lgn

（lgn表示以2为底n的对数）74插入排序算法的最差情况分析图执行算法所需要的时间列表的长度增加列表长度时时间的长度列表长度均匀增长长度为n的列表中进行最多需要次比较。75二分搜索法的最差情况分析图执行算法所需要的时间列表的长度增加列表长度时时间的长度列表长度均匀增长在长度为n的列表中进行查找的时候最多需要查询lgn项。76查找算法查找是指从给定的集合（或者是多重集，它允许几个元素具有相同的值）中查找一个给定的值（称为查找键K）。常用的查找算法有顺序查找和折半查找，还有那些将原来的集合表示为另一种形式以方便查找的算法等等。顺序查找——直接从头到尾搜索集合的查找键。折半查找——必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合的查找键，所以，当集合是有序的时候，使用折半查找效率高、速度快。77判定哪一种算法是最佳方案针对排序和查找方面的算法更多，例如，采用分治法、减治法、变治法等等方法中的各种排序和查找算法。运用经典的算法设计技术——时空权衡、动态规划、贪婪技术等；算法能力的极限中的决策树技术、在多项式的时间内求解、数值分析，超越算法能力的极限中的回溯发、分支界限法和近似算法设计技术。技术和思维方式都是不可或缺的鞭策学习和掌握程序设计中的算法设计与分析技术托马斯·爱迪生（1847-1931）的名言：“不断关注那些已被他人成功应用的新思路。你的原创思想只应该应用在那些你正在研究的问题上”。785.3程序设计步骤与程序设计方法

5.3.1程序设计步骤

5.3.2程序设计方法795.3.1程序设计步骤

一般程序设计应该包含以下4个步骤：（1）针对具体问题进行分析——了解问题性质，明确问题解决所达目标，提供的输入是什么？最终实现的输出是什么？执行中要做什么？怎么做？并建立相应的数学模型。（2）确定数据结构并设计相应的算法——对具体问题进行概念抽象，构造出解决问题的轮廓，设计程序的数据结构和算法。（3）编写实现算法的程序——根据算法确定解决问题的详细步骤，通常是通过绘制程序流程图，来描述问题处理的过程；然后按照流程图的描述选用某种程序设计语言编写程序。（4）测试与调试程序——在程序设计过程中，经常不是那么一帆风顺的，尤其是初学者会遇到各种这样或那样的问题，还有一些问题可能是不可预测的，往往不得不返到上一步骤中更改或调整相应的内容，并将相应文档也一并修改，通过举一反三的方法来解决给定问题。80测试程序与调试程序测试程序为了发现程序中的设计错误而运行程序。

——所使用的测试用例尤其重要，因为不仅需要合法值域用例，而且非法值域用例也是必须的。——程序测试的成功与否直接可以体现程序健壮性。

——当软件项目是由团队开发时，测试程序可分为：单元测试、组装测试和确认测试。调试程序

错误定位和纠错的过程，这一过程的快慢与程序设计人员的编程经历和经验是密切相关的。81高级语言编写和运行过程yesyes源文件目标文件可执行文件其它目标文件库函数开始编辑源程序检查确认有错？编译程序有错？有错？运行程序有错？yesnonoyes连接程序no结束no数据825.3.2程序设计方法早期的程序设计方法结构化程序设计方法面向对象程序设计方法831.早期的程序设计方法早期的程序设计方法追求程序的高效率，编程过份依赖技巧，忽视程序清晰，而不注重所编写程序的结构，很少考虑程序的规范化问题，也就是没有固定程序设计方法的时期。程序的可读性、可重用性都很差。其中典型问题是：频繁使用goto语句，特意算计如何节省内存空间。虽然这些方法存在很多问题，但当时受限于计算机运行速度慢、内存容量小、硬件价格昂贵，程序的规模也比较小，对于单人完成较为简单的任务，事实上这些方法还是经常被采用的。842.结构化程序设计方法结构化程序设计方法出现在70年代中期。随着计算机硬件成本急剧下降，软件需要处理的复杂问题也就越来越多。为了摆脱60~70年代初的软件危机，因为当时编程无章可循，程序常常带有强烈的个人色彩，程序的可读性差，程序的调试和维护更困难，促使人们认真反省和研究程序设计中一系列根本性问题：程序的基本结构是什么？程序设计应当采用什么方法？算法设计先于程序编码？清晰第一，效率第二？程序设计技术与方法如何规范化和工程化？解决手工作坊式软件开发的弊端85结构化程序设计方法的特点使得程序层次分明、逻辑清晰、功能独立，简化了开发程序的复杂性，增加了程序的可靠性，能够充分发扬团队精神快速而高效地完成项目开发，增强系统的可维护性，使程序设计更加规范化。结构化程序设计方法的特点：自顶向下、逐步求精划分功能模块结构化编程863.面向对象程序设计方法面向对象程序设计方法出现在80年代中后期。随着计算机硬件技术的高速发展，计算机的性能也越来越强，用途也更加广泛。软件产业所面临的问题需求不断扩大，程序也就越来越庞大而复杂。在面向过程的程序设计中——软件设计的主要工作就是用不同的功能模块分别描述它们的求解过程。在结构化程序设计中——数据和处理数据的过程分离为相互独立的实体，它只是封装了各个功能模块，而每个功能模块可以随意修改未加封装的数据。新时期的新问题，以及软件产业的更高要求，迫使人们再次寻求更加科学、更加先进的程序设计方法。87面向对象程序设计（OOP）Object-OrientedProgramming是建立在结构化程序设计基础上的，但它不再是从功能入手，而是从对象入手。采用的是一种结构模拟的方法。用“类”描述具有相同属性特征的一组对象，用“封装”将对象的属性和行为分别用适当的数据结构和方法来描述，并将它们绑定在一起形成一个可供访问的基本逻辑单元，利用“继承”实现类与类之间的数据和方法的共享。88面向对象程序设计的重要概念面向对象程序设计的重要概念：对象（Object）类（Class）消息（Message）方法（Method）89对象（Object）面向对象程序设计中的对象——现实世界中的客体在应用程序中的具体体现，其中封装了客体的属性信息和行为方式，并用数据表示属性，用方法表示行为方式。对象中的数据记录了客体的属性状态，方法决定了客体所能够实施的操作行为和与其它对象进行通信的接口方式。对象并非孤立存在，消息传递是对象之间相互联系的唯一途径，发送者发送消息，接收者通过调用相应的方法响应消息，这个过程被不断地重复，从而驱动整个程序的运转。90类（Class）人类在认知客观世界时，将众多的事物归纳、划分成一些类，这是经常采用的思维方法。分类所依据的原则是抽象。类是具有相同属性和行为方式的一组对象的集合，或者说，类是指对一组具有相同特征（包括属性、操作、方法、关系、行为）的对象的抽象描述，任何对象都是某个类的实例。对象是系统运行时将类作为生成对象实例的模板，通过分配私有存储空间，然后对相应的属性赋初始值而创建的，这个过程在面向对象程序设计中称为“实例化”。类与对象的关系犹如模具与铸件之间的关系。91消息（Message）消息——一个对象要求另一个对象实施某项操作的请求。

在一条消息中，需要包含消息的接收者和要求接收者执行某项操作的请求，但具体的操作过程由接收者自行决定，这样可以很好地保证系统的模块性。消息传递是对象之间相互联系的唯一途径。发送者发送消息，接收者通过调用相应的方法响应消息，这个过程被不断地重复，从而驱动整个程序的运转。92方法（Method）面向对象技术中的方法——针对对象的属性的各种操作。将一些通用的过程或函数编写好并封装起来，作为方法直接提供给用户调用。93面向对象程序设计几个重要的基本特征面向对象程序设计几个重要的基本特征：抽象（Abstract）封装（Encapsulation）继承（Inheritance）多态（Polymorphism）94抽象（Abstract）抽象——忽略事物的非本质特征，只注意那些与当前目标有关的本质特征，从而找出事物的共性，把具有共同性质的事物划分为一类，得出一个抽象的概念。在理解复杂的现实世界和解决复杂的特定问题时，如何从繁杂的信息集中抽取出有用的、能够反映事物本质的东西，降低其复杂程度是解决问题的关键，而抽象正是降低复杂度的最佳途径。抽象可分为过程抽象和数据抽象过程抽象——即功能抽象，舍弃个别功能，抽取共同拥有的功能。数据抽象——一种更高级别的抽象，它将现实世界中存在的客体作为抽象单元，其抽象内容既包括客体的属性特征，也包括行为特征（起到信息隐藏的作用）。它是面向对象程序设计所采用的核心方法。95封装（Encapsulation）面向对象程序设计中的封装——将对象的属性和行为分别使用适当的数据结构和方法来描述，并将它们绑定在一起形成一个可供访问的基本逻辑单元。用户对数据结构的访问只能通过使用类提供的外部接口。这样，将描述这些属性的数据结构和访问这些数据结构的方法封装在一个对象中，从而使数据结构得到隐藏，不允许外界直接访问。其它对象只能通过封装提供的外部接口（这些方法）对该对象实施各项操作，保证了数据结构的安全，提高了系统的可维护性和可移植性。96继承（Inheritance）继承是面向对象技术提高软件开发效率的重要措施，如果类与类之间有is-a（是一种）的关系，则可用继承机制来表示。其定义是：特殊类的对象拥有其一般类的全部属性和服务，称作特殊类对一般类的继承。它体现了类与类之间的不同抽象级别。根据继承与被继承的关系，可分为派生类（或称子类）和基类（或称父类）。继承机制其实质是反映了从一般到特殊的关系，父类表现出的是共性和一般性，子类表现出的是个性和特殊性，子类从父类那里获得所有的属性和方法，并且可以对这些获得的属性和方法加以改造，使之具有自己的特点。继承对于软件复用和扩充有着及其重要的意义，利用代码重用技术，能够降低开发投入，加快软件开发速度、提高软件质量，减少维护成本。继承可分为公有继承（public）、私有继承（private）和保护继承（protected）三种访问控制方式。97多态（Polymorphism）多态——不同层次的类中，以及在一个类的内部，同名成员函数之间的关系问题，是解决功能和行为的再抽象。多态是指不同的对象收到相同的消息时产生多种不同的行为方式。它是一种用统一的方式来处理一组各具个性却同属一族的不同个体的机制，这就使得同样的消息被不同的对象接收时，将被解释为不同的语义。例如：定义了多个“add”相加的同名函数，但它们的参数类型各不相同，如果用整型之间、实型之间、双精度浮点型之间分别表示相加运算，则当同样的消息（相加）被不同类型的对象（变量）接收后，不同类型的变量将采用不同的方式进行加法运算。985.4常用程序设计语言

5.4.1科学计算语言

5.4.2结构化程序设计语言

5.4.3面向对象程序设计语言

5.4.4其它程序设计语言

5.4.5标记式语言HTML和XHTML5.4.6脚本语言995.4.1科学计算语言

FORTRAN（FORmula

TRANslating）可称之为第一个高级编译语言，从其用词及涵义即把应用领域的目标锁定在科学计算（或称数值计算）上。Fortran90中有Pascal特征，如指针、递归、动态数组等概念。Fortran95中简化了开发并行程序的任务，去除了Fortran90中的许多特性，还有一些特性被置入“待废弃之列”。从JohnBackus（1977年获得图灵奖）的Fortran0到目前的Fortran95，版本不断更新，程序设计人员只要面对解决科学计算问题时，就会自然想到使用公式翻译语言。Fortran高级程序设计语言历经如此漫长的年代变迁，还是具有那么长久的生命力，这与它为适应计算机时代的需求而不断创新是分不开的。在该语言的发展历史中，最为重要的版本如下：FortranⅥFortran66Fortran77Fortran90Fortran951005.4.2结构化程序设计语言

摆脱60年代末软件危机的最佳解决方案，使开发软件编写代码的过程中能够循规蹈矩地步入正轨，各类开发人员能够不谋而合地使用结构化程序设计的算法最小集来完成。语言完整性而言，有非结构化语句，例如：goto、continue、break等语句，用到它们的话，也会严格按照结构化程序设计的要求和约定用法限制来使用。结构化程序设计开发方法使得软件代码可读性、可维护性、以及可扩充性都得到了有力支持。Pascal、C是最成功的结构化程序设计语言，既是在面向对象程序设计中结构化程序设计开发方法依然在发挥着极其重要的作用。1011.Pascal语言1971年，NiklausWirth推出了Pascal语言（以法国数学家BlaisePascal为命名），这应该属于wirth前期研究ALGOL60，以及吸取COBOL和PL/Ⅰ的优良特性后，而专门设计用于程序设计教学的语言。Pascal语言的语法非常严谨，类型丰富，层次分明，易读易写，是第一个结构化程序设计语言，它是简单性和易于表达的完美结合。在70年代中期之前，通常在大学的计算机程序设计课程教学都是采用Fortran、PL/Ⅰ、或ALGOL语言，但以后都被Pascal语言所取代，其主要原因是Pascal语言是最适合于结构化程序设计的教学。1022.C语言1972年，美国贝尔实验室的KennethLaneThompson和DennisMacAlistairRitchie（1983年获得图灵奖）为了重新改写UNIX操作系统，而共同设计、开发了C语言。C是由CPL、BCPL、B和ALGOL68等继承发展而来的。CPL在60年代初开发于剑桥大学。BCPL是1967年由MartinRichards开发的一种简单的系统语言。60年代末Thompson用汇编语言编写了第一版UNIX操作系统。1970年他以BCPL为基础，在UNIX下实现了第一个高级语言B。1035.4.3

面向对象程序设计语言

面向对象程序设计语言经历了一个很长的发展阶段，面向对象程序设计概念的许多原始思想都来之于Simula67，但是直到Smalltalk演化到Smalltalk80时（1980年），面向对象程序设计才得到了充分的发展。同时对以前的思想作了新的解释。可以说面向对象程序设计语言与面向对象思想几乎是同步发展并相互促进的。早先的面向对象语言，如：LISP、Simula67、Smalltalk、CLU、CwithClasses、Ada83、Modula-2和Smalltalk80等语言。1041.C++语言1980年，Bjarne

Stroustrup博士（1993年获得了ACMGraceMurrayHopper奖）在贝尔实验室开始研究从C到C++的开发。经历了漫长的5年时间，在1985年推出了第一个可以实现的C++1.0版本，被称为Cfront。随后至1990年推出了C++3.0版本。1998年ISO对C++进行了标准化。1990年有了ANSIC++标准。1052.Java语言Java是SunMicrosystems公司在1995年推出的一种编程语言。通常我们以JDK（Sun开发的一套Java开发工具）的版本来定义Java的版本。目前最新的版本是6.0。Java是一种简单、面向对象、平台无关、分布式、解释型、安全可靠、性能优异、多线程、动态的高级程序设计语言，特别适合在网络环境下的编程使用。1063.C#语言C#（读作Csharp）是一种为生成在.NETFramework上运行的多种应用程序而设计的面向对象的编程语言。简单、功能强大、类型安全。