北京高校精品课件-《大学计算机基础》第5章-程序设计基础

1、1,大学计算机基础,教学课件,2,第5章 程序设计基础,5.3 程序设计步骤与程序设计方法,5.1 程序和程序设计语言,5.2 算法,5.4 常用程序设计语言,5.5 程序设计范型,3,本章重点,程序的概念 程序设计语言的结构 算法的概念与描述方法 程序设计步骤 程序设计方法,4,5.1 程序和程序设计语言,5.1.1 程序的一般概念 5.1.2 程序设计语言的概述 5.1.3 程序设计语言的结构,5,5.1.1 程序的一般概念,生活中程序的概念,何事？,策划,导演,例1：年终总结会的程序： 会议主持宣布会议开始 领导讲话 个人或团队代表发言 领导总结 会议主持宣布会议结束,6,5.1.1 程

2、序的一般概念（续1）,生活中程序的概念,步行 骑车 开车 时间 红绿灯 铁道,依据实际案例并精心计算,解决该计算问题的方法、步骤就包含了程序的概念。,例2：某人从甲地到丙地去。,7,5.1.1 程序的一般概念（续2）,计算机程序的概念：,为实现某一算法而编写的指令序列。 宏观地描述该指令序列，可用计算机的 机器语言 汇编语言 高级语言 用经典的公式可表示为： 程序 = 算法 + 数据结构,8,5.1.2 程序设计语言的概述,程序设计编写程序的全过程。 有学者认为： 程序设计 = 算法 + 数据结构 + 程序设计语言,程序设计语言人和计算机之间对话和交流的一种工具，用于描述计算机所执行的操作。,

3、计算机程序设计语言有几百种，但是最常用的不过10多种，了解一些程序设计语言的不同特性，有助于为特定任务而选择适当的程序设计语言。,9,1. 机器语言（Machine Language）,指令指挥计算机完成某个基本操作的命令。,指令系统所有的指令集合。 （第一代程序设计语言） 机器语言用二进制代码表示指令系统的语言。 机器语言程序由二进制代码按一定规则组成的、能被机器理解和运行的指令序列。（也称可执行程序 ） 例如：计算累加器A=8+10的机器语言程序如下：,10,2. 汇编语言（Assembly Language ）,汇编语言实质就是以容易记忆的代码或英文单词来代替约定的机器指令。（第二代程序

4、设计语言）,例如：用ADD表示加、SUB表示减、JMP表示跳转、MOV表示数据的传送指令等 。 汇编源程序使用汇编语言编写的程序。 例如：上述计算累加器A=8+10的汇编语言程序如下：,11,3. 高级语言（High Level Language）,高级语言类似数学语言或人的自然语言，同时又不依赖于某种计算机硬件，使得设计编制的程序能够在所有机器上通用。 （第三代程序设计语言）,程序设计语言在不同的系统平台使用比较普遍的有：FORTRAN、ALGOL、COBOL、LISP、PL/I、BASIC、SIMULA 67、Pascal、C、Smalltalk 80、Ada、C+、VC、VB、Delph

5、i、Java、JavaScript、C#、Visual BASIC.NET。 可视化语言构成了命令式语言中的另一个子类。最流行的可视化语言Visual BASIC（1999年），已被Visual BASIC.NET（2002年）取代。提供拖拉式生成代码段的功能。一度被认作第四代语言，此说法已不再使用了。,12,程序设计语言的特点,机器语言的特点： 编程难 效率高 需要指令系统 难读 难维护,高级语言的特点： 编程容易 效率低 需要编译系统 易读 易维护,汇编语言的特点： 编程不容易 效率较高 需要汇编程序 不易读 不易维护,13,5.1.3 程序设计语言的结构,程序结构的多样性： 结构化程序

6、模块化程序 面向对象的程序结构,一个良好结构的程序具有以下等特点： 结构清晰 容易阅读 容易理解 容易验证 容易维护 1996年，计算机科学家Boehm和Jacopini提出并从数学上证明 任何一个算法，都能以三种基本控制结构表示，即顺序结构、选择结构和循环结构。,14,结构化程序设计中顺序结构,按照程序语句行的自然顺序，一条语句一条语句地执行程序。,15,结构化程序设计中选择结构,根据条件的判断确定应该执行哪一条分支的语句序列。（又称为分支结构 ）,单分支、多分支结构？,16,结构化程序设计中循环结构,主要用于重复执行相同的语句序列（被称为循环体），直到判定条件为假（或为真）时才可终止执行循

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

8、laus Wirth（也是Pascal语言发明者，1984年获得图灵奖）的专著：,Algorithms Data Structures Programs （算法 十 数据结构 = 程序） 在计算机软件开发行业中产生了极为深远的影响，从而推动了软件开发技术和方法步入正轨，使人们开始深入研究数据结构和算法设计与分析的技术和方法。,20,1. 算法的概念,算法解决某个具体问题而采取的方法与步骤的完整和准确的描述。 是指令的有限序列，其中每一条指令表示一个或多个操作。 是问题的程序化解决方案，这些解决方案本身并不是答案，而是获得答案的精确指令。,算法的分类 顺序算法：是由冯诺依曼型计算机体系结构所决定

9、的，其主要思想是指令逐条运行，每次执行一步操作。 并行算法：要求在一些更新式的计算机中可以在同一时间执行多条指令。,21,2. 算法的特征,一个算法必须具备五项基本特征：有穷性、确定性、数据输入、数据输出和可行性。,（1）有穷性算法是有序指令的集合，并在执行有穷步骤后能够终止。 （2）确定性每条指令必须有确切的含义，且无二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入数据只能得到相同的输出数据。 （3）输入数据可有零个或多个输入数据。这些输入数据取自于某个特定对象的集合。 （4）输出数据必须有一个或多个输出数据。 （5）可行性描述的操作都可以通过已经实现的基本运算执行有限次来

10、实现，也可以证明整个算法实施后可以得到预期的解。,22,例5.1 一个非算法的计数过程, 令n为0； 置n为n+1； 返回。,结论：不能称为算法。 原因：违背了算法特征中（1）、（4）、（5）。,23,例5.2 计数器算法,用自然语言编写一个不超过1万次的计数器算法： 令n为0； 置n为n+1 若n小于10000，则返回；否则，输出n之值，且算法到此结束。,结论：是算法。 原因：符合算法特征。,在算法设计过程中，其实还有有关正确性、可读性、健壮性、效率与低存储量需求，以及算法效率的度量等问题。,24,5.2.2 算法的描述方法,流程图（FlowChart） PAD图（Problem Analy

11、sis Diafram，问题分析图） N-S图 自然语言 伪代码 UML图 （Unified Modeling Language，统一建模语言）,25,1. 流程图,流程图（框图）用不同形状的几何图形表示不同性质的操作，用流程线指明算法的执行方向。ANSI(美国国家标准化协会)、ISO（国际标准化组织）和我国国家标准中均有类似的规定。常见的流程图符号如下：,向下或向右的流程线可以不画出箭头。当流程线有交叉时，则画一半圆通过交叉点。,26,用流程图描述的计数器算法,27,2. PAD图,由日立公司推出的PAD图是一种二维图。即从上向下顺序执行，从左到右表示层次关系。表示三种基本结构的PAD图如下

12、：,28,3. N-S图,1973年美国两位学者提出无流程线的N-S图（盒图）。,结构化程序设计由三种基本结构而组成，则算法也应采用结构化描述方法，N-S图的基本单元是矩形框，框内可以有三种基本结构，形如堆积木，也只有一个入口和一个出口。三种基本结构的N-S图如下：,29,用N-S图描述的计数器算法,30,4. 自然语言,自然语言是人们日常生活、工作和学习中使用的通用语言，使用自然语言的文字描述算法通俗易懂，但也有它的缺陷：,（1）容易产生歧义性，因为自然语言经常要根据上下文才能判别其含义，不太严格。 （2）自然语言很难清楚地表达算法的逻辑流程，对于算法中的条件判断、循环，尤其是在这些处理中还

13、有多层嵌套，就很难用清晰而直观的语言来表达算法的流程。因此仅适于描述简单问题。,31,5. 伪代码,伪代码是介于自然语言和计算机语言之间的文字和符号，它不能被计算机所理解，但使用伪代码描述的算法很容易转变成某种编程语言。,/用伪代码描述的计数器算法如下： n 0 do n n+1 while n b ) m = a; /* 从 a 与 b 中取大数送 m 中 */ else m = b; if( m c ) ; /* 从 m 与 c 中取大数送 m 中，“；”即m=m */ else m = c; return(m); /* 返回 m 给主函数 */ /* End of max3 functi

14、on */,36,2. 欧几里得算法,求解两个不全为0的非负整数m和n的最大公约数，可以采用以下欧几里得算法。,（1）欧几里得算法主函数描述如下： 输入两个不全为0的非负整数m,n; Ecd = Euclid(m,n); 输出Ecd，且算法到此结束。,（2）Euclid(m,n) 子函数算法描述如下： while n 0 do r m mod n m n n r return m,37,3. 两个变量值的交换算法,计算机实现的两个变量值的交换算法如下：, 令 a=5, b=10 c a, a b, b c 输出 a 和 b 的值。,/* 两个变量值交换算法的 C 源程序 */ void mai

15、n(void) int a=5, b=10, c; /* 定义 a、b、c 3个整型变量 */ printf(“交换前: a=%d, b=%dn”, a, b);/* 交换前输出a和b的值 */ c = a; /* 将 a 中的值赋值给 c */ a = b; /* 将 b 中的值赋值给 a */ b = c; /* 将 c 中的值赋值给 b */ printf(“交换后: a=%d, b=%dn”, a, b); /* 交换后输出a和b的值*/ /* End of main function */,三角对换法,38,4. 排序算法,给定一个有n个元素可排序的序列，例如数字数据或字符串数据等，

16、要求按照升序或降序方式重新排列。,排序算法：如冒泡排序法、选择排序法、插入排序法、合并排序法、快速排序法等等排序算法。,39,蛮力法中的选择排序法,按照降序方式排序的选择排序算法：,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 if Array j Array max max j swap Array i and Array max ,

17、40,选择排序法的 C 程序,/* SelectionSort( Array 0.n-1 )选择排序算法的 C 源程序 */ void SelectionSort( int n, int Array ) int i, j, max, t; /* 定义4个整型变量 */ for( i=0; i Arraymax ) max = j; /* 记录大数元素的下标位置 */ /* 利用 t 变量做三角对换 */ t = Arrayi, Arrayi=Arraymax, Arraymax=t; /* End of SelectionSort function */,41,选择排序法降序方式排序操作过程,

18、例如：对序列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,每行表示该算法的一次迭代，即从尾部到竖线的一遍扫描；找到的最大元素用黑体字表示，竖线左边元素已经位于它们的最终位置，所以在当前和以后的循环中，都不必再操作了。排序操作过程如下：,42,5. 查找算法,查找是指从给定的集

19、合（或者是多重集，它允许几个元素具有相同的值）中查找一个给定的值（称为查找键 K）。,常用的查找算法有顺序查找和折半查找，还有那些将原来的集合表示为另一种形式以方便查找的算法等等。 顺序查找直接从头到尾搜索集合的查找键。 折半查找必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合的查找键，所以，当集合是有序的时候，使用折半查找效率高、速度快。,43,判定哪一种算法是最佳方案,针对排序和查找方面的算法更多，例如，采用分治法、减治法、变治法等等方法中的各种排序和查找算法。,运用经典的算法设计技术时空权衡、动态规划、贪婪技术等；算法能力的极限中的决策树技术、在多项式的时间内求解、数值分析，超

20、越算法能力的极限中的回溯发、分支界限法和近似算法设计技术。,技术和思维方式都是不可或缺的,鞭策学习和掌握程序设计中的算法设计与分析技术,托马斯爱迪生（1847-1931）的名言：“不断关注那些已被他人成功应用的新思路。你的原创思想只应该应用在那些你正在研究的问题上”。,44,5.3 程序设计步骤与程序设计方法,5.3.1 程序设计步骤 5.3.2 程序设计方法,45,5.3.1 程序设计步骤,一般程序设计应该包含以下4个步骤：,（1）针对具体问题进行分析了解问题性质，明确问题解决所达目标，提供的输入是什么？最终实现的输出是什么？执行中要做什么？怎么做？并建立相应的数学模型。 （2）确定数据结构

21、并设计相应的算法对具体问题进行概念抽象，构造出解决问题的轮廓，设计程序的数据结构和算法。 （3）编写实现算法的程序根据算法确定解决问题的详细步骤，通常是通过绘制程序流程图，来描述问题处理的过程；然后按照流程图的描述选用某种程序设计语言编写程序。 （4）测试与调试程序在程序设计过程中，经常不是那么一帆风顺的，尤其是初学者会遇到各种这样或那样的问题，还有一些问题可能是不可预测的，往往不得不返到上一步骤中更改或调整相应的内容，并将相应文档也一并修改，通过举一反三的方法来解决给定问题。,46,测试程序与调试程序,测试程序,为了发现程序中的设计错误而运行程序 。 所使用的测试用例尤其重要，因为不仅需要合

22、法值域用例，而且非法值域用例也是必须的。 程序测试的成功与否直接可以体现程序健壮性。 当软件项目是由团队开发时，测试程序可分为：单元测试、组装测试和确认测试。 调试程序 错误定位和纠错的过程，这一过程的快慢与程序设计人员的编程经历和经验是密切相关的 。,47,高级语言编写和运行过程,48,5.3.2 程序设计方法,早期的程序设计方法 结构化程序设计方法 面向对象程序设计方法,49,1. 早期的程序设计方法,早期的程序设计方法追求程序的高效率，编程过份依赖技巧，忽视程序清晰，而不注重所编写程序的结构，很少考虑程序的规范化问题，也就是没有固定程序设计方法的时期。,程序的可读性、可重用性都很差。其中

23、典型问题是：频繁使用goto语句，特意算计如何节省内存空间。 虽然这些方法存在很多问题，但当时受限于计算机运行速度慢、内存容量小、硬件价格昂贵，程序的规模也比较小，对于单人完成较为简单的任务，事实上这些方法还是经常被采用的。,50,2. 结构化程序设计方法,结构化程序设计方法出现在70年代中期。,随着计算机硬件成本急剧下降，软件需要处理的复杂问题也就越来越多。 为了摆脱6070年代初的软件危机，因为当时编程无章可循，程序常常带有强烈的个人色彩，程序的可读性差，程序的调试和维护更困难，促使人们认真反省和研究程序设计中一系列根本性问题：,程序的基本结构是什么？ 程序设计应当采用什么方法？ 算法设计

24、先于程序编码？ 清晰第一，效率第二？ 程序设计技术与方法如何规范化和工程化？,解决手工作坊式软件开发的弊端,51,结构化程序设计方法的特点,使得程序层次分明、逻辑清晰、功能独立，简化了开发程序的复杂性，增加了程序的可靠性，能够充分发扬团队精神快速而高效地完成项目开发，增强系统的可维护性，使程序设计更加规范化。,结构化程序设计方法的特点： 自顶向下、逐步求精 划分功能模块 结构化编程,52,3. 面向对象程序设计方法,面向对象程序设计方法出现在80年代中后期。,随着计算机硬件技术的高速发展，计算机的性能也越来越强，用途也更加广泛。软件产业所面临的问题需求不断扩大，程序也就越来越庞大而复杂。 在面

25、向过程的程序设计中软件设计的主要工作就是用不同的功能模块分别描述它们的求解过程。 在结构化程序设计中数据和处理数据的过程分离为相互独立的实体，它只是封装了各个功能模块，而每个功能模块可以随意修改未加封装的数据。 新时期的新问题，以及软件产业的更高要求，迫使人们再次寻求更加科学、更加先进的程序设计方法。,53,面向对象程序设计（ OOP ）,Object-Oriented Programming 是建立在结构化程序设计基础上的，但它不再是从功能入手，而是从对象入手。,采用的是一种结构模拟的方法。用“类”描述具有相同属性特征的一组对象，用“封装”将对象的属性和行为分别用适当的数据结构和方法来描述，

26、并将它们绑定在一起形成一个可供访问的基本逻辑单元，利用“继承”实现类与类之间的数据和方法的共享。,54,面向对象程序设计的重要概念,面向对象程序设计的重要概念： 对象（Object） 类（Class） 消息（Message） 方法（Method）,55,对象（Object）,面向对象程序设计中的对象现实世界中的客体在应用程序中的具体体现，其中封装了客体的属性信息和行为方式，并用数据表示属性，用方法表示行为方式。,对象中的数据记录了客体的属性状态，方法决定了客体所能够实施的操作行为和与其它对象进行通信的接口方式。 对象并非孤立存在，消息传递是对象之间相互联系的唯一途径，发送者发送消息，接收者通过

27、调用相应的方法响应消息，这个过程被不断地重复，从而驱动整个程序的运转。,56,类（Class）,人类在认知客观世界时，将众多的事物归纳、划分成一些类，这是经常采用的思维方法。分类所依据的原则是抽象。,类是具有相同属性和行为方式的一组对象的集合，或者说，类是指对一组具有相同特征（包括属性、操作、方法、关系、行为）的对象的抽象描述，任何对象都是某个类的实例。 对象是系统运行时将类作为生成对象实例的模板，通过分配私有存储空间，然后对相应的属性赋初始值而创建的，这个过程在面向对象程序设计中称为“实例化”。 类与对象的关系犹如模具与铸件之间的关系。,57,消息（Message）,消息一个对象要求另一个对

28、象实施某项操作的请求。,在一条消息中，需要包含消息的接收者和要求接收者执行某项操作的请求，但具体的操作过程由接收者自行决定，这样可以很好地保证系统的模块性。 消息传递是对象之间相互联系的唯一途径。发送者发送消息，接收者通过调用相应的方法响应消息，这个过程被不断地重复，从而驱动整个程序的运转。,58,方法（Method）,面向对象技术中的方法针对对象的属性的各种操作。,将一些通用的过程或函数编写好并封装起来，作为方法直接提供给用户调用。,59,面向对象程序设计几个重要的基本特征,面向对象程序设计几个重要的基本特征： 抽象（Abstract） 封装（Encapsulation） 继承（Inheri

29、tance） 多态（Polymorphism）,60,抽象（Abstract）,抽象忽略事物的非本质特征，只注意那些与当前目标有关的本质特征，从而找出事物的共性，把具有共同性质的事物划分为一类，得出一个抽象的概念。,在理解复杂的现实世界和解决复杂的特定问题时，如何从繁杂的信息集中抽取出有用的、能够反映事物本质的东西，降低其复杂程度是解决问题的关键，而抽象正是降低复杂度的最佳途径。 抽象可分为过程抽象和数据抽象 过程抽象即功能抽象，舍弃个别功能，抽取共同拥有的功能。 数据抽象一种更高级别的抽象，它将现实世界中存在的客体作为抽象单元，其抽象内容既包括客体的属性特征，也包括行为特征（起到信息隐藏的作

30、用）。它是面向对象程序设计所采用的核心方法。,61,封装（Encapsulation）,面向对象程序设计中的封装将对象的属性和行为分别使用适当的数据结构和方法来描述，并将它们绑定在一起形成一个可供访问的基本逻辑单元。,用户对数据结构的访问只能通过使用类提供的外部接口。这样，将描述这些属性的数据结构和访问这些数据结构的方法封装在一个对象中，从而使数据结构得到隐藏，不允许外界直接访问。 其它对象只能通过封装提供的外部接口（这些方法）对该对象实施各项操作，保证了数据结构的安全，提高了系统的可维护性和可移植性。,62,继承（Inheritance）,继承是面向对象技术提高软件开发效率的重要措施，如果类

31、与类之间有is-a（是一种）的关系，则可用继承机制来表示。,其定义是：特殊类的对象拥有其一般类的全部属性和服务，称作特殊类对一般类的继承。它体现了类与类之间的不同抽象级别。根据继承与被继承的关系，可分为派生类（或称子类）和基类（或称父类）。 继承机制其实质是反映了从一般到特殊的关系，父类表现出的是共性和一般性，子类表现出的是个性和特殊性，子类从父类那里获得所有的属性和方法，并且可以对这些获得的属性和方法加以改造，使之具有自己的特点。 继承对于软件复用和扩充有着及其重要的意义，利用代码重用技术，能够降低开发投入，加快软件开发速度、提高软件质量，减少维护成本。 继承可分为公有继承（public）、

32、私有继承（private）和保护继承（protected）三种访问控制方式。,63,多态（Polymorphism）,多态不同层次的类中，以及在一个类的内部，同名成员函数之间的关系问题，是解决功能和行为的再抽象。,多态是指不同的对象收到相同的消息时产生多种不同的行为方式。它是一种用统一的方式来处理一组各具个性却同属一族的不同个体的机制，这就使得同样的消息被不同的对象接收时，将被解释为不同的语义。 例如：定义了多个“add”相加的同名函数，但它们的参数类型各不相同，如果用整型之间、实型之间、双精度浮点型之间分别表示相加运算，则当同样的消息（相加）被不同类型的对象（变量）接收后，不同类型的变量将采

33、用不同的方式进行加法运算。,64,5.4 常用程序设计语言,5.4.1 科学计算语言 5.4.2 结构化程序设计语言 5.4.3 面向对象程序设计语言 5.4.4 其它程序设计语言 5.4.5 标记式语言HTML和XHTML 5.4.6 脚本语言,65,5.4.1 科学计算语言,FORTRAN（FORmula TRANslating）可称之为第一个高级编译语言，从其用词及涵义即把应用领域的目标锁定在科学计算（或称数值计算）上。,Fortran 90中有Pascal特征，如指针、递归、动态数组等概念。 Fortran 95中简化了开发并行程序的任务，去除了Fortran 90中的许多特性，还有一

34、些特性被置入“待废弃之列”。,从John Backus（1977年获得图灵奖）的Fortran 0到目前的Fortran 95，版本不断更新，程序设计人员只要面对解决科学计算问题时，就会自然想到使用公式翻译语言。 Fortran高级程序设计语言历经如此漫长的年代变迁，还是具有那么长久的生命力，这与它为适应计算机时代的需求而不断创新是分不开的。在该语言的发展历史中，最为重要的版本如下： Fortran Fortran 66 Fortran 77 Fortran 90 Fortran 95,66,5.4.2 结构化程序设计语言,摆脱60年代末软件危机的最佳解决方案，使开发软件编写代码的过程中能够循

35、规蹈矩地步入正轨，各类开发人员能够不谋而合地使用结构化程序设计的算法最小集来完成。,语言完整性而言，有非结构化语句，例如：goto、continue、break等语句，用到它们的话，也会严格按照结构化程序设计的要求和约定用法限制来使用。 结构化程序设计开发方法使得软件代码可读性、可维护性、以及可扩充性都得到了有力支持。 Pascal、C是最成功的结构化程序设计语言，既是在面向对象程序设计中结构化程序设计开发方法依然在发挥着极其重要的作用。,67,1. Pascal 语言,1971年，Niklaus Wirth推出了Pascal语言（以法国数学家Blaise Pascal为命名），这应该属于wi

36、rth前期研究ALGOL 60，以及吸取COBOL和PL/的优良特性后，而专门设计用于程序设计教学的语言。,Pascal语言的语法非常严谨，类型丰富，层次分明，易读易写，是第一个结构化程序设计语言，它是简单性和易于表达的完美结合。 在70年代中期之前，通常在大学的计算机程序设计课程教学都是采用Fortran、PL/、或ALGOL语言，但以后都被Pascal语言所取代，其主要原因是Pascal语言是最适合于结构化程序设计的教学。,68,2. C 语言,1972年，美国贝尔实验室的Kenneth Lane Thompson和Dennis MacAlistair Ritchie（1983年获得图灵奖

37、）为了重新改写UNIX操作系统，而共同设计、开发了C语言。,C是由CPL、BCPL、B和ALGOL 68等继承发展而来的。 CPL在60年代初开发于剑桥大学。BCPL是1967年由Martin Richards开发的一种简单的系统语言。 60年代末Thompson用汇编语言编写了第一版UNIX操作系统。1970年他以BCPL为基础，在UNIX下实现了第一个高级语言B。,69,5.4.3 面向对象程序设计语言,面向对象程序设计语言经历了一个很长的发展阶段，面向对象程序设计概念的许多原始思想都来之于Simula 67，但是直到Smalltalk演化到Smalltalk 80时（1980年），面向对

38、象程序设计才得到了充分的发展。同时对以前的思想作了新的解释。,可以说面向对象程序设计语言与面向对象思想几乎是同步发展并相互促进的。 早先的面向对象语言，如：LISP、Simula 67、Smalltalk、CLU、C with Classes、Ada 83、Modula-2和Smalltalk 80等语言。,70,1. C+ 语言,1980年，Bjarne Stroustrup博士（1993年获得了ACM Grace Murray Hopper奖）在贝尔实验室开始研究从C到C+的开发。,经历了漫长的5年时间，在1985年推出了第一个可以实现的C+ 1.0版本，被称为Cfront。 随后至199

39、0年推出了C+ 3.0版本。 1998年ISO对C+ 进行了标准化。 1990年有了ANSI C+标准。,71,2. Java 语言,Java是Sun Microsystems公司在1995年推出的一种编程语言。通常我们以JDK（Sun开发的一套Java开发工具）的版本来定义Java的版本。目前最新的版本是6.0 。,Java是一种简单、面向对象、平台无关、分布式、解释型、安全可靠、性能优异、多线程、动态的高级程序设计语言，特别适合在网络环境下的编程使用。,72,3. C# 语言,C#（读作C sharp）是一种为生成在.NET Framework上运行的多种应用程序而设计的面向对象的编程语言

40、。,简单、功能强大、类型安全。 起源于C语言家族，凭借它的许多创新，在保持C样式语言的表示形式和优美的同时，实现了应用程序的快速开发。 语法表现力强，易学。语法方面简化了C+的诸多复杂性，同时提供了很多强大的功能， 例如，可为空的值类型、枚举、委托、匿名方法和直接内存访问，这些都是Java所不具备的。 支持泛型方法和类型，从而提供了更出色的类型安全和性能。 提供了迭代器，允许集合类的实现者自定义迭代方法，简化了客户端代码对它的使用。,73,5.4.4 其它程序设计语言,ALGOL语言 COBOL语言 BASIC语言 Ada语言 LISP函数型程序设计语言 Prolog逻辑程序设计语言,74,1

41、. ALGOL 语言,ALGOL（ALGOrithmic Language）称为算法语言 。,ALGOL语言的版本58、60、68，它是第一种国际性的团体GAMM（Society for Applied Mathematics and Mechanics的德文缩写）和ACM（Association for Computing Machinery，美国计算机学会）共同设计的程序设计语言，也是第一种与机器无关的语言。 第一种语法得到正式描述的语言。巴科斯范式（Backus-Naur form，BNF）形式化的成功应用促进了计算机科学许多重要领域的发展。 其地位维持了长达二十余年之久。从1960年以

42、来所设计的每一种命令式程序设计语言都与ALGOL 60不无干系。实际上，它们大多数都可直接或间接地算是ALGOL 60的新版本。例如，PL/、SIMULA 67、ALGOL 68、C、Pascal、Ada、C+、Java等。,75,2. COBOL 语言,COBOL（COmmon Business Oriented Language）称为商业应用通用语言 。,1959年5月，美国国防部提供资助，由一个委员会通过会议在相当短的时间内设计出来的。 首次实现了层次数据结构。每个变量都在数据划分中详细定义，包括小数位数和小数点的位置。 文件记录的描述也同样详细，它们被描述为输出至打印机的行，这就使CO

43、BOL非常适合于打印报表。 支持长名（30个字符）和连字符，使编写出的程序能够望文生义。 经历了不同版本的更新，1968年、1974年和1985年都有ANSI标准化。 导致财会电算化，从任何意义上讲，这都是一个极其重要的革新。目前，我国还有不少群体在使用该语言，国外使用则依然比较普遍，而该语言本身仍然在继续发展中。,76,3. BASIC 语言,BASIC（Beginners All-purpose Symbolic Instruction Code）语言是一种得到广泛使用但声誉不太高的程序设计语言 。,数学家John Kemeny和Thomas Kurtz在新汉普郡的Dartmouth学院（

44、现为大学）设计出来的（60年代初曾参与过许多版本的Fortran和ALGOL 60编译器的研制）。 早期BASIC是第一种通过连接至远程终端加以使用的语言，当时终端刚刚出现，而在此之前，大多数程序都只能通过打孔卡片或纸带输入计算机。1964年5月1号凌晨4点，终于诞生了第一个使用分时BASIC的程序。 随着微机的诞生，BASIC又被配置在微机上，以解释性或编译性方式运行程序，因为易学，对计算机的推广应用起到了重要作用。 BASIC也经历了各种版本，例如，Turbo BASIC、Quick BASIC等，由于用BASIC编写的程序结构性很差，在其发展过程中几乎没有进行过标准化。,77,Visua

45、l BASIC 的出现,直到1991年，微软推出基于Windows环境，采用可视化界面设计和事件驱动的编程机制，以及基于对象的开发工具Visual BASIC 1.0版本之后，才又激发了广大计算机爱好者的兴趣。,VB已经更新到Visual BASIC 6.0版本。 微软现在的Visual BASIC.NET网络功能更强（它还只是微软Visual Studio.NET中的成员之一），是VB的替代品。因为它们存在着显著的不同差异，有些使用者开始转向使用C#。,78,4. Ada 语言,Ada语言是为美国国防部（Department of Defense，DoD）开发的 。,1975年，美国国防部研

46、究和工程部主任Malcolm Currie成立了高级语言工作组，其成员来自军界各个行业，另外还与英国、法国和西德保持着联系。 Ada语言的研究与开发可分为： 前三个阶段（1983年之前）围绕Ada 83版本。 后三个阶段（1988年之后）围绕Ada 9X版本。 中间Ada语言设计则封冻了至少5年。,79,5. LISP 函数型程序设计语言,LISP（List Processor）是一个全面而强大的语言 。,早期人们视其为一个外观和表现很奇怪的语言，而且认为使用LISP的开销相当大。 LISP的开发是为了用于符号计算和表处理应用，主要是AI（Artificial Intelligence，人工智

47、能）领域的计算。在许多AI应用中，LISP及其以后的版本仍是标准语言。 在AI中，许多领域都已经得到开发，这主要归功于LISP的应用。尽管也可以使用其它类型的语言（主要是逻辑程序设计语言），但大多数现有的专家系统都是用LISP开发的。 LISP还在知识表示、机器学习、智能训练系统和语音建模等领域占据着主导地位。,80,在 AI 领域之外,在AI领域之外，LISP也相当成功。,例如，EMACS文本编辑器就是用LISP编写的，符号数学系统MACSYMA也是用LISP编写的，此系统除了提供其它功能外，还可以完成符号区分和集成。 LISP机器是一种个人计算机，其整个系统软件均用LISP编写。 LISP

48、还成功地用于为大量应用领域构造专家系统。,81,6. Prolog 逻辑程序设计语言,逻辑程序设计起源要归功于Robinson为逻辑推导所开发的规约规则。,Prolog主要由Aix-Marseille大学的Alain Colmeraur和Phillippe Roussel所开发，并得到了Edinburgh大学的Robert Kowalski的一些帮助 。 关系数据库管理系统（Relational Database Management Systems，RDBMS）以表的形式存储数据。查询通常用关系算子表示，这是一种符号逻辑形式。 这些系统查询语言是非过程性的，而逻辑程序设计也是非过程性的，因此

49、二者从这个意义上讲是相同的，用户不必描述如何检索出答案，只需描述答案的特征即可。,82,6. Prolog 逻辑程序设计语言（续）,逻辑程序设计和RDBMS之间的关联是很显然的。,简单的信息表可以由Prolog结构来描述，而表之间的关系则可以方便而容易地描述为Prolog规则。 检索过程交由规约操作完成，Prolog的目标语句提供了对RDBMS的查询。因此，逻辑程序设计恰能满足RDBMS实现的需求。 符号逻辑提供了逻辑程序设计和语言的基础。 逻辑程序设计的方法是将一组事实和规则（表示事实间关系）用作为一个数据库，并使用一个自动推导过程来检查新命题的合法性，在此假设数据库中的事实和规则均为真，这

50、种方法正是为自动定理证明开发的。,83,5.4.5 标记式语言HTML和XHTML,HTML（Hypertext Markup Language ）即超文本标记语言。 XHTML（eXtensible HTML） 是一种在HTML 基础上优化和改进的新语言。,84,1. HTML 超文本标记语言,HTML（超文本标记语言）是WWW（World Wide Web ）的描述语言。由Tim Berners-lee提出。,设计目的 能把存放在一台电脑中的文本或图形与另一台电脑中的文本或图形方便地联系在一起，形成有机的整体，人们不用考虑具体信息是在当前电脑上还是在网络的其它电脑上。 用鼠标在某一文档中点

51、取一个图标，Internet就会马上转到与此图标相关的内容上去，而这些信息可能存放在网络的另一台电脑中。 HTML是由HTML命令组成的描述性文本，HTML命令可以说明文字、图形、动画、声音、表格、链接等。 HTML的结构包括头部（Head）、主体（Body）两大部分。头部描述浏览器所需的信息，主体包含所要说明的具体内容。,85,2. XHTML,2000年底，国际W3C（WWW Consortium）组织公布发行了XHTML 1.0版本。XHTML 1.0是一种在HTML 4.0基础上优化和改进的新语言。,设计目的 基于XML（eXtensible Markup Language）应用。 X

52、HTML（eXtensible HTML）是一种增强了的HTML。 它的可扩展性和灵活性将适应未来网络应用更多的需求。,86,HTML 三个主要缺点,XHTML解决HTML语言所存在的严重制约其发展的问题。,HTML发展到今天存在三个主要缺点： 不能适应现在越来越多的网络设备和应用的需要。 （手机、PDA、信息家电都不能直接显示HTML） HTML代码不规范、臃肿。 （浏览器需要足够智能和庞大才能够正确显示HTML） 数据与表现混杂。 （页面要改变显示，就必须重新编写HTML） W3C的XHTML是HTML向XML过渡的一个桥梁。,87,XML 是Web发展的趋势,XHTML是当前替代HTML

53、 4.0标记语言的标准。,使用XHTML 1.0，只要你小心遵守一些简单规则，就可以设计出既适合XML系统，又适合当前大部分HTML浏览器的页面。 也就是说，你可以立刻设计使用XML，而不需要等到人们都使用支持XML的浏览器。 可以使web平滑的过渡到XML。,88,XHTML 的优势,XHTML非常严密。,早期的浏览器接受私有的HTML标签，所以人们在页面设计完毕后必须使用各种浏览器来检测页面，看是否兼容，往往会有许多莫名其妙的差异，人们不得不修改设计以便适应不同的浏览器。 XHTML能与其它基于XML的标记语言、应用程序及协议进行良好的交互工作。 XHTML是Web标准家族的一部分，能很好

54、地应用在无线设备等其它用户代理上。,89,5.4.6 脚本语言,2种不同形式的脚本语言 JavaScript（1998年）：是一种嵌入到HTML中的客户端脚本语言。 PHP（Personal Home Page ，2000年）：是嵌入到HTML中的服务器脚本语言。,脚本语言（Scripting Language）是以脚本的形式定义一项任务，以此控制操作环境，扩展应用程序的性能。,90,1. JavaScript 脚本语言,JavaScript是WWW上的一种功能强大的编程语言 。,由浏览器中的解释器来解释执行。它不仅可以直接应用于HTML文档以获得交互式效果或其他动态效果，而且可以运行于服务器

55、端，从而替代传统的CGI程序。 JavaScript脚本程序的特点： 开发客户端Web应用程序，也就是开发所谓的客户端脚本。 客户端脚本程序通常都是解释执行的。 被嵌入到HTML文件中。,91,1. JavaScript 脚本语言（续）,随着HTML文件一同下载到浏览器端。,浏览器读HTML文件，然后解释执行并显示其中的元素。读取HTML文件并分辨其中的元素的过程称为语法分析或解析（parsing）。如果解析到JavaScript脚本，则浏览器执行其脚本语句。 是最流行的Web脚本语言，其主要原因在于它具有最广泛的兼容性，可以运行于多个浏览器平台上。 VBScript也是一种通用的Web脚本语

56、言，由微软公司开发，但由于它只能被IE浏览器所支持，所以无法与JavaScript抗衡。至于VBScript以外的其他Web脚本语言就更是影响微弱了。,92,2. PHP 脚本语言,PHP是嵌入到HTML文件中的服务器端脚本语言 。,PHP脚本语言的特点 专门用于Web应用。 在Web服务器上解释PHP代码。 （当某个浏览器请求了PHP代码所在的HTML文件后） PHP代码通常会生成HTML代码作为输出。 Web浏览器绝对不会看到PHP代码。,93,5.5 程序设计范型,5.5.1 命令型程序设计语言 5.5.2 函数型程序设计语言 5.5.3 逻辑程序设计语言 5.5.4 面向对象程序设计语

57、言,94,交互式语言和非交互式语言,按照使用方式，程序设计语言有交互式语言和非交互式语言之分：,交互式语言反映人机交互作用的语言（BASIC）。 非交互式语言不反映人机交互作用的语言。如FORTRAN、COBOL、ALGOL 69、Pascal、C等都是非交互式语言。,95,程序设计范型,程序设计范型（Paradigm）是指设计程序的规范、模型和风格，它是一类程序设计语言的基础。,成功的程序设计语言最初都是为某一特殊用途而设计的。 尽管在很多程序设计语言中都含有命令结构和声明结构，但程序设计语言还是可以被划分为4大类型： 命令型程序设计语言。 函数型程序设计语言。 逻辑程序设计语言。 面向对象

58、程序设计语言。 有些程序设计语言（例如，C+、Java等)既是面向对象又是命令型程序设计语言，也可称为多范型程序设计语言。,96,5.5.1 命令型程序设计语言,命令型语言的特点 算法必须详细指定。 赋值语句、变量。 包括指令或语句的具体执行顺序。 绝大多数程序设计语言只要不是纯函数型、逻辑和面向对象程序设计语言，都具有命令型语言的特性。 较有影响力或常用的命令型程序设计语言有：FORTRAN、ALGOL、COBOL、PL/I、SIMULA 67、BASIC、Pascal、C、Ada、C+、Delphi、Java等。,在执行命令型程序设计语言的时候，每次只能执行一步计算，因为程序中的每一步都依赖于它前面的步骤。,97,5.5.2 函数型程序设计语言,函数型程序设计语言的特点 所有计算都是通过将函数应