大学信息技术基础（第三版）第6章

1、第6章 程序设计基础,主要内容： 6.1 算法与程序 6.2 Alice程序设计初步 *6.3 数据结构 *6.4 软件工程 本章小结 思考与练习,6.1 算法与程序,6.1.1 算法的基本概念 1.什么是算法 通俗点说，算法就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。 计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个具体的算法来实现。 2.算法的特征 （1）可行性 针对实际问题设计的算法，人们总是希望能够得到满意的结果。,6.1 算法与程序,（2）确定性 算法的确定性，是指算法中的每一个步骤都

2、必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。 （3）有穷性 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 （4）输入 通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。 （5）输出 一个算法有一个或多个输出，以反映对输入数据加工后的结果。,6.1 算法与程序,6.1.2 算法的表示 1.自然语言 自然语言是人们日常所用的语言，如汉语、英语、德语等。 2.程序流程图 程序流程图是描述算法的常用工具，可以很方便地表示程序的基本控制结构。 美国国家标准化协会ANSI规定了如下

3、一组图形符号来表示算法。(见课本P142),6.1 算法与程序,3.伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此书写方便，格式紧凑，易于理解，便于向计算机程序设计语言过渡。 4.计算机程序设计语言 计算机不能识别自然语言、流程图和伪代码等算法描述语言，而设计算法的目的就是要用计算机解决问题。,6.1 算法与程序,6.1.3 算法设计的基本方法 1.列举法 列举法又称为穷举法或枚举法，其基本思想是：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 2.归纳法 归纳法的基本思想是，通过列举少量的特殊情况，

4、经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。,6.1 算法与程序,3.递推法 如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。 从上面的递归事例不难看出，递归算法存在的两个必要条件： 必须有递归的终止条件； 过程的描述中包含它本身。 4.分治法 所谓分治法，就是对问题分而治之。尽可能地把复杂问题分解为若干较小的问题，找出各个较小问题的解之后，再组合成整个问题的解。,6.1 算法与程序,5.回溯法 通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成

5、功，就得到了问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。,6.1 算法与程序,6.1.4 算法的评价 1.正确性 正确性是指算法的执行结果应该满足预先规定的功能和性能要求。 2.可读性 一个算法应该思路清晰、层次分明、简单明了、易读易懂。 3.健壮性 算法的健壮性指的是，算法应对非法输入的数据做出恰当反映或进行相应处理。 4.复杂性,6.1 算法与程序,算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。 一个算法的评价主要从时间复杂度和空间复杂度来考虑。 6.1.5 程序与程序设计语言 1.什么是程序 程序就是告诉计算机要做什么的一系列指令，每条指令是一个

6、要执行的动作。编写程序的工作称为程序设计。 程序设计是根据特定的问题，使用某种程序设计语言，按照预定的算法设计计算机执行的指令序列。 2.程序设计语言,6.1 算法与程序,（1）机器语言 为编写计算机所能理解的程序，人们最早使用的语言是机器语言。 （2）汇编语言 汇编语言是用助记符来表示每一条机器指令。 由汇编语言编写的源程序必须经过翻译转变成机器语言程序，计算机才能识别和执行。 （3）高级语言 高级语言是一种与机器指令系统无关，表达形式更接近于被描述问题的程序设计语言。 高级语言处理程序有编译程序和解释程序两种。,6.1 算法与程序,6.1 算法与程序,图6-1 编译型语言处理程序功能示意图

7、,3.程序与算法、数据结构之间的关系 算法是处理问题的方法和步骤，数据结构是算法要处理的数据构造的逻辑表示形式，最后问题的解由计算机程序给出。 程序的构成是和数据结构不可分割的。 算法思想决定了程序的质量和性能，好的算法可大大提高程序运行的效率，减少时间和空间复杂性。 算法是建立在数据结构基础上的，未确定对数据如何操作就无法决定如何构造数据。,6.1 算法与程序,6.2 Alice程序设计初步,Alice系统是一个可视化的编程环境，程序中的状态可以通过三维场景中对象的运动方式得以实现，这样就能在程序结构与表现的动画之间建立一种可视化的关联，使得学生的学习负担从认知系统迁移到了感知系统。 6.2

8、.1 Alice系统简介 Alice系统是由美国卡耐基梅隆（Carnegie Mellon）大学开发的以学习者为中心，支持面向对象程序设计的三维虚拟世界动画教学工具软件，在地址上，可免费下载所提供的Alice系统。,6.2 Alice程序设计初步,与其他动画软件不同，在Alice中，不需要进行动画的建模、关键帧、渲染等复杂的工作，设计者只需像导演一样告诉Alice对象在什么位置应该做什么动作序列，Alice负责生成（绘制）所有序列帧的动画。,6.2 Alice程序设计初步,Alice系统具有其它高级语言所具有的所有特征，包括程序的结构、判断与循环语句、变量、函数与表达

9、式、事件与事件处理，还有递归、列表等。 Alice系统同时又提供了独特的编程环境、可视化的面向对象程序设计，三维虚拟世界动画场景建模与运行，这些又是其他高级语言所没有的。 Alice界面根据功能分为五个区域，如图6-4所示。,6.2 Alice程序设计初步,6.2 Alice程序设计初步,6.2.2 面向对象的基本概念 1.Alice的对象优先学习模式 对象优先的教学法从一开始就强调面向对象的编程和设计原则，这种教学法直接从对象和继承开始，然后才介绍程序设计的结构，即使学习程序设计的结构。 对象优先学习方法首先给学生介绍面向对象的概念，使面向对象的思想“先入为主”。通过面向对象辅助学习软件，学

10、生可以真切地“看到”对象。 面向对象的三个特征继承（Inherit）、封装（Encapsulation）、多态（Polymorphism）均以直观的形象呈现给学生，加深了学生对面向对象概念的理解。,6.2 Alice程序设计初步,对象优先教学，不是对面向对象及程序设计概念的简单灌输，而是让学生通过一些辅助学习软件（如Alice）的帮助，在有趣的学习过程中，不断接触并强化对象的概念，逐步感悟程序的结构和软件工程的过程。 2.面向对象程序设计的主要思想 面向对象的程序从现实世界中客观存在的事物（即对象）出发来构造软件系统，并且在系统构造中尽可能运用人类的自然思维方式。 面向对象的程序设计以对象（O

11、bject）为核心，用这种技术开发出的软件系统由对象组成。 面向对象的基本思想主要有： （1）现实世界中的事物都是对象，对象间存在一定的关系； （2）用对象的属性（Attribute）描述事特的静态特征，用对象的操作（Operation）描述事物的行为特征；,6.2 Alice程序设计初步,（3）对象的属性和特征结合为一体，成为一个独立的、不可分的实体，实体对外屏蔽其内部细节； （4）通过抽象对事物进行分类，类是具有相同属性和相同操作的对象的抽象描述，每个对象是类的一个实例； （5）复杂的对象由简单的对象构成； （6）运用抽象原则，可以得到较一般的类和较特殊的类，特殊类继承一般类的属性和操作；

12、 （7）对象之间通过消息进行通信，实现对象间的动态联系。 需要说明的是，目前面向对象的程序设计模式有取代“数据结构算法”的面向过程的程序设计模式的趋向。 3.类、对象、属性与方法 （1）类（class） 类表示一组相似的对象。将具有相同或相似性质的对象的抽象就得到类。,6.2 Alice程序设计初步,6.2 Alice程序设计初步,在面向对象程序设计里，类是创建对象的模板。它包含所创建对象的属性描述和行为特征的定义。 在Alice中，每个类用一个3D模型表示。类名用第一个字母大写的单词表示，如Bluebird、Boar、Cat等（图6-5）。,6.2 Alice程序设计初步,（2）对象（obj

13、ect） 对象是面向对象程序设计的核心。 在面向对象的程序设计中，对象的概念就是对现实世界中实体的模型化，它是代码和数据的组合，同样具有自己的属性和行为。 （3）属性 属性（attribute）用来表示类（或对象）的特性。 在Alice系统中，在细节区的属性页（Attribute）中列出了每一个类或对象的属性，一般包括对象的颜色（color）、质地或纹理（texture）、尺寸（长、宽、高）以及其他细节。 （4）方法 方法（method）是类（或对象）有能力完成的事情，定义了类（或对象）的行为和操作。,6.2 Alice程序设计初步,图6-6 iceSkater具有的属性与方法,6.2 Ali

14、ce程序设计初步,6.2.3 程序设计的一般过程 一般的程序设计过程，包括问题描述、算法设计、代码编制、调试运行等几个步骤。在面向对象的程序设计中，还包括定义对象的属性和方法。 1.问题描述 程序设计的最终目的是为了利用计算机求解某一特定问题，因此程序设计面临的首要任务是得到问题的完整和确切的定义。 2.算法设计 解题过程都是由一定的规则、步骤组成的，这种规则就是算法。,在计算机专业术语中，文本式的故事板（storyboard）称为算法（algorithm），即一连串为解决问题或执行任务而进行的操作。,6.2 Alice程序设计初步,6.2 Alice程序设计初步,3.编写程序 问题定义和算法

15、描述已经为程序设计规划好了蓝本，下一步就是用计算机语言表达了。不同的语言有各自的特点，因此先要针对问题选用合适的开发设计环境和平台，尽管写出的程序有时会有较大差别，但它必须是忠实于算法描述的。 4.调试运行 调试的过程就是检查程序的运行方式和结果是否与设计要求相一致，也是对程序进行语法和逻辑进行查错的一个过程。 语法错误是最常见的错误类型，是由于不正确地书写代码，在计算机执行时就会错误，这一类错误编译系统都会给以相应的提示，所以比较容易检查。,5.编写程序文档 文档记录程序设计的算法、实现以及修改的过程，保证程序的可读性和可维护性。对于有上千行代码的较复杂程序，在没有文档的情况下，经过一段时间

16、，即使是程序员本人也很难记清其中某些程序是完成什么功能的。 程序中的“注释”就是一种很好的文档，注释的内容并不要求计算机理解它们，但可被读程序的人理解，这就足够了。,6.2 Alice程序设计初步,6.2.4 变量、常量与表达式 1.变量与常量 变量，是指没有固定的值，可以改变的数。变量以非数字的符号来表达，变量的名称一般用英文字母来命名，称为变量名，例如x、y。 常量是指在各种运算过程中一个具体的、保持不变的值。 2.变量的赋值 通常确定一个变量，需要三个要素，即变量名、变量类型和变量的值。 3.表达式 表达式一种有值的语法结构，它一般由运算符将变量、常量、函数调用返回值结合而成。,6.2

17、Alice程序设计初步,6.2 Alice程序设计初步,（1）算术表达式： 算术表达式是最常用的表达式。它是通过算术运算符来进行运算的数学公式。常见的算术运算符包括、等。 （2）逻辑表达式 逻辑运算的结果只有两个：True（真）和False（假），Alice提供了三种逻辑运算符：not（非）、and（与）、or（或），如图6-13所示。 （3）关系表达式 用关系运算符将两个表达式连接起来的式子，称关系表达式。关系表达式的值是逻辑值True和False。,6.2 Alice程序设计初步,图6-12 算术运算符 图6-13 逻辑表达式 图6-14关系表达式,6.2.5 程序的结构顺序执行与同步执行

18、 1.顺序执行结构（Do in order） 在程序设计中，如果指令是一个个按照先后顺序依次执行的，这种程序结构就称为顺序结构。 Do in order是Alice使用的顺序执行结构。 2.同步执行结构 在程序设计中，如果若干条指令是同时执行的，这种程序结构就属于同步执行结构。同步执行结构是一种并行方式，相对于其他编程语言来讲，需要专门进行复杂的程序设计才能实现。 在Alice中，让若干条指令同步执行非常简单，因为Alice专门提供了同步执行结构Do together。,6.2 Alice程序设计初步,6.2.6 条件执行控制语句 条件执行控制语句取决于一个决策。 无论采用哪种编程语言，条件执

19、行控制语控制结构表示都是类似的。图6-18中给出了If/Else语句的程序流程图表示。,6.2 Alice程序设计初步,6.2 Alice程序设计初步,图6-18 If/else语句结构,图6-19 单路径的If语句,6.2 Alice程序设计初步,6.2.7 循环语句 循环用于重复执行一组语句。 1.Loop循环 Loop循环语句在很多编程语言中都能见到（有时语法格式不尽相同）。Loop循环是让一组指令（或动作）重复执行有限次的简单方法。要创建一个Loop语句，只需把Loop模块拖动到代码编辑器中。 2.While语句 在某些情况下，有时并不确定循环的次数，但是知道只要某个条件满足就应该一直

20、循环下去，While循环语句适用于这种情况，其循环控制结构如图6-26所示。,6.2 Alice程序设计初步,图6-26 While循环控制结构,6.2 Alice程序设计初步,6.2.8 函数 一个函数用来计算得到一个结果（或者一个数值）。各种高级程序设计语言都提供了许多函数供编程者使用。函数不是一个独立的指令，它总是嵌套在指令中来使用的。 Alice为虚拟场景中的每一个对象都提供了函数，这些函数称为内置函数，调用这些函数可获得对象的属性和对象间的关系。 在Alice中要查看对象的内置函数列表，可以选中对象树上的对象，然后点击函数页（functions），就能看到所有提供的函数。,6.2 A

21、lice程序设计初步,6.2.9 方法的参数 一个程序可以由多个方法组成，每个方法都包含一个指令集，当方法被调用时会执行特定的任务。在前面示例程序中都是对方法的直接调用，并没有将运动参数传递给方法。 参数是用来与方法进行通信的，如果要把一个值或一个对象名传递给方法，首先就要创建参数，然后在其它程序中将参数传递给被调用的方法中去。,6.2 Alice程序设计初步,6.2.10 事件交互程序设计 对象的事件是指由系统事先设定的、能被对象识别和响应的动作。 事件驱动程序设计（Event-driven programming）是现代程序设计的主要思想，是在交互程序（Interactive progra

22、m）的应用背景下而产生的程序设计模式。在这种编程模式下，程序的执行流程是由使用者的动作或者是由其他程序的信息来决定的。当一个事件发生时，程序可以对其做出响应，用来响应该事件的方法称为事件处理方法（Event Handling method）。一个交互式程序就是由很多这样的事件及其对应的处理方法组成的。,6.2 Alice程序设计初步,在Alice交互式程序中，每当用户按下键盘或者点击鼠标，就会产生一个事件从而触发一个响应。在对一个事件做出响应时，程序就会执行一个或一系列动作。应该创建一个方法和触发的事件相连接，让它来描述当事件发生时，对象应做什么动作。 在Alice中，可以在事件编辑器中创建事

23、件类型并与某个方法连接。,6.2 Alice程序设计初步,6.2.11 继承的概念及Alice实现过程 继承（inheritance）是面向对象程序设计中最重要的机制。它支持层次分类的观点，继承使得程序员可以在一个已有类的基础上很快地建立一个新类，复用已有类的全部属性和方法，而不必从零开始设计每个类。 继承的概念十分重要，一般来说需要弄清楚下面几个术语： 保持已有类的特性而构造新类的过程称为继承。 在已有类的基础上新增自己的特性而产生新类的过程称为派生。 被继承的已有类称为基类（或父类）。,6.2 Alice程序设计初步,派生出的新类称为派生类（或子类）。 继承表达了对象的一般与特殊的关系。继

24、承使派生类自动的拥有或隐含地复制其基类的全部属性和操作。 Alice提供了类的继承机制，可以为对象创建新的方法（新的动作），然后将新创建的对象保存为一个新的三维模型类。,6.2 Alice程序设计初步,6.2.12 面向对象的全局方法按方法组织程序结构 按照模块化设计思想，一个复杂问题，肯定是由若干个稍简单的问题构成。模块化是把程序要解决的目标分解为子目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。 在Alice程序设计中，提供了模块化设计的代码组织方式，这就是按照将复杂问题分解的思想，设计不同的方法，每个方法是

25、若干指令的集合，用于解决一个子任务。,作为程序设计的入门知识，在本章的学习中，尝试将Alice用于程序设计的基础教学中，这是对计算机教学内容与教学方法的较大革新。这种全新的教学方式的目标就是让传统的编程概念更容易讲解和接受。对于培养大学生的计算思维和快乐学习都具有重要的意义。 Alice系统是面向对象编程教学的一个突破。它从最初的虚拟场景快速原型工具，逐步演变成为一个面向对象程序设计入门课程的教育软件。Alice环境采用了目前流行的面向对象的教学策略，通过将对象的可视化进行面向对象程序设计概念的教学。每个Alice虚拟世界中的可视单元中都是一个对象，因此非常容易地遵循对象优先的教学方法，也为以

26、后学习面向对象的程序设计奠定了基础。,本章小结,本章只要求学习者通过Alice程序的演示，理解程序设计的基本概念，对掌握Alice程序设计暂不做要求。数据结构与软件工程两个章节均作为选学内容，为有兴趣的学习者提供更深一步了解软件设计技术的阅读材料。,本章小结,一、思考题 1.什么是算法？算法的特征和基本设计方法有哪些？ 2.请介绍表示算法的几种基本方法。 3.简述进行程序设计的一般步骤。 4.计算机能不能直接执行高级语言程序？为什么？ 5.Alice是一个什么样的软件系统？与一般程序设计语言相比，它有哪些特点？ 6.Alice的对象优先学习模式具有哪些特点？ 7.面向对象程序设计的主要思想与特

27、点是什么？ 8.在面向对象程序设计中，类、对象、属性与方法的概念是什么？ 9.理解变量、常量与表达式的一般概念。 10.Alice程序设计中，顺序执行与同步执行有什么不同？ 11.Alice程序设计中，条件执行控制语句如何应用？ 12.Alice程序设计中，循环控制语句的两种结构是什么？如何应用？,思考与练习,13.Alice程序设计中，如何使用方法的参数调用程序？ 14.Alice程序设计中，什么是事件？如何使用事件编程？ 15.什么是继承？Alice中怎样实现类级方法的继承？ 16.Alice程序设计中，理解面向对象的全局方法与类级方法。 *二、练习与实践 1.创建新场景小岛和鲨鱼 【题目描述】：创建一个海中小岛和鲨鱼的虚拟场景。选择水世界(water)的模板，然后添加一个小岛(EnvironmentsIsland)，使用场景编辑器让小岛位于场景中心的右方，在场景中添加一条鲨鱼（OceanShark)。这条鲨鱼如果看不见，可能是把它放到了小岛的后面或者其他不合适的位置，