第10章 程序设计基础

第十章程序设计基础《大学计算机》（第三版）高等教育出版社10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.1程序设计的概念程序：是解题方法和步骤的描述，是供计算机执行并能完成特定功能的指令序列。程序的核心：数据结构和算法。程序设计（Programming）：先对问题进行分析并建立数学模型，然后考虑数据的组织方式和算法，并用某一种程序设计语言编写程序，最后调试程序，使之运行后能产生预期的结果。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.1程序设计的概念程序设计的基本步骤：

(1)分析问题，确定数学模型或方法。

(2)设计算法，画出流程图。

(3)选择编程工具，按算法编写程序。

(4)调试程序，分析输出结果。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2算法计算机解决问题的方法和步骤，就是计算机解题的算法(Algorithm)。

算法举例：

（1）将两个变量的值互换。

（2）欧几里德（Euclid）算法求两个正整数m和n的最大公约数。（3）非数值计算算法：有9枚铜币，其中有1枚略轻的是假币，用一台没有砝码的天平将假币找出来，应怎样找称。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.1算法的概念10.2算法(1)有穷性。算法中执行的步骤总是有限次数的，不能无止境地执行下去。

(2)确定性。算法中的每一步操作必须具有确切的含义，不能有二义性。

(3)有效性。算法中的每一步操作必须是可执行的。

(4)要有数据输入。算法中操作的对象是数据，因此应提供有关数据。

(5)要有结果输出。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.2算法的特性10.2算法1．算法评价标准（1）正确性。

（2）可读性。

（3）通用性。

（4）高效率。

2.算法效率的度量

（1）时间度量

（2）空间度量10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.3算法的评价10.2算法用传统的流程图描述算法传统的流程图是用一些几何框图、流程线和文字说明表示各种类型的操作。一般用矩形框表示进行某种处理，有一个入口，一个出口。用菱形框表示判断，有一个入口，两个出口。在框内写上简明的文字或符号表示具体的操作，用带箭头的流向线表示操作的先后顺序。

10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.4算法的描述10.2算法2.用结构化流程图描述算法

（1）程序的三种基本结构：顺序结构、选择结构和循环结构。

（2）结构化流程图（N-S图）10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.4算法的描述10.2算法2.用结构化流程图描述算法

（1）程序的三种基本结构：顺序结构、选择结构和循环结构。

（2）结构化流程图（N-S图）10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.4算法的描述10.2算法3．用伪代码描述算法计算2+4+…+100并输出，设计算法并用VisualBasic伪代码描述如下：0→sum1→iDoWhilei≤100Ifi/2的余数为0THENsum+i→sumi+1→iLoopPrintsum10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.4算法的描述10.2算法1．迭代算法迭代是一种建立在循环基础上的算法。在数学中，迭代经常被用来进行数值计算，例如求方程的解，不断用变量原来的值递推求新的值的过程。讨论求若干个数之和或乘积的问题。

10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.5算法示例10.2算法2．穷举算法穷举法也叫枚举法，它的基本思路是对众多可能解，按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的可能解，作为问题的解。穷举的计算量是相当大的，但对于计算机来说，做起来很容易。穷举算法是一种重要的算法设计策略，可以说是计算机解题的一大特点。求方程x+2y+5z=100的整数解。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.5算法示例10.2算法3．排序算法

所谓排序，就是将一组数据元素按照某个关键字递增或递减的次序排列起来。

（1）选择排序(SelectionSort)

选择排序法的实现过程是：首先找出表中关键字最小的元素，将其与第一个元素进行交换，然后，再在其余元素中找出关键字最小的元素，将其与第二个元素进行交换。依次类推，直到将表中所有关键字按由小到大的顺序排列好为止。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.5算法示例10.2算法（2）冒泡排序(BubbleSort)冒泡法排序法是每趟将相邻的两个数两两进行比较，若满足升序次序，则进行下一次比较，若不满足升序次序，则交换这两个数，直到最后。总的比较次数为n-1次，此时最后的元素为最大数，此为一趟排序。接着进行第二趟排序，方法同前，只是这次最后一个元素不再参与比较，比较次数为n-2次，依次类推。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.5算法示例10.2算法4．查找算法查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素，若表中存在这样的数据元素，称此查找是成功的。若表中不存在关键字等于给定值的数据元素，称此查找是不成功的。

（1）顺序查找

顺序查找是最常用的查找方法，其查找过程为：从第一个元素起，逐个将给定值与数据元素的关键字进行比较，若某个元素的关键字与给定值相等，则认为查找是成功的，否则，查找失败。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.5算法示例10.2算法（2）折半查找作为折半查找的表必须是顺序存储的有序表，即表采用顺序结构存储，表中的元素按关键字值递增（或递减）排列。

假设表中的关键字值递增排列，则折半查找的实现方法是：首先取整个有序表的中间元素Am的关键字同给定值x比较，若相等，则查找成功；否则，若Am的关键字小于x，则说明待查元素只可能落在表的后半部分中，接着只要在表的后半部分子表中查找即可；若Am的关键字大于x，则说明待查元素只可能落在表的前半部分中，接着只要在表的前半部分子表中查找即可。这样，经过一次关键字的比较，就缩小一半的查找空间，重复进行下去，直到找到关键字为x的元素，或者表中没有待查元素（此时查找区间为空）为止。10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.2.5算法示例10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.1程序设计语言的分类机器语言汇编语言高级语言面向过程面向对象10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.1程序设计语言的分类1．机器语言（Machinelanguage）

机器语言：机器指令的总称。

特点：繁琐冗长、不直观、容易出错、程序不通用。

2．汇编语言（Assemblylanguage）

用助记符表示的机器指令。

特点：直观性增强了，但与机器指令一一对应。

3．高级语言（Highlevellanguage）

高级语言：接近自然语言和数学表达式的一种语言。

特点：直观、通用性，便于推广交流。

两种执行方式：编译方式和解释方式。10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.1程序设计语言的分类高级语言程序的编译执行过程：编译程序工作过程:10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.2高级语言的基本特征1．数据类型

各种高级语言都提供了丰富的数据类型，这些数据类型可以分为两大类：简单类型和构造类型。其中简单类型一般有整型、实型、字符型、逻辑型、指针类型等，构造类型有数组类型、集合类型、记录类型、文件类型等。10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.2高级语言的基本特征2．运算与表达式

（1）常量

（2）变量

（3）表达式

3．语句

（1）赋值语句

（2）输入输出语句

（3）程序的控制结构语句

4．子程序、函数与过程

10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.3常用高级语言1.传统高级语言

（1）FORTRAN语言：FORTRAN66、FORTRAN77、FORTRAN90。

（2）BASIC语言：BASIC、VisualBasic、VisualBasic.NET。

（3）PASCAL语言

（4）C语言：C、C++、C＃。

（5）COBOL语言10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.3常用高级语言2．网络编程语言

（1）Java语言

（2）脚本语言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科学计算语言：MATLAB10.3程序设计语言10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.3.3常用高级语言2．网络编程语言

（1）Java语言

（2）脚本语言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科学计算语言：MATLAB讨论：如何学习一种高级语言？如何选择高级语言？10.4程序设计方法10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.4.1结构化程序设计结构化程序设计采用自顶向下、逐步求精和模块化的分析方法，从而有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子程序，便于开发和维护。10.4程序设计方法10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.4.2面向对象程序设计(Object-OrientedProgramming,OOP)传统的程序设计是基于求解过程来组织程序流程。在这类程序中，数据和施加于数据的操作是独立设计的，以对数据进行操作的过程作为程序的主体。面向对象程序设计则以对象作为程序的主体。对象是数据和操作的“封装体”，封装在对象内的程序通过“消息”来驱动运行。在图形用户界面上，消息可通过键盘或鼠标的某种操作来传递。10.4程序设计方法10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.4.2面向对象程序设计(Object-OrientedProgramming,OOP)（1）对象(Object)对象是指现实世界中具体存在的实体。每一个对象都有自己的属性（包括自己特有的属性和同类对象的共同属性）。属性反映对象自身状态变化，表现为当前的属性值。

方法是用来描述对象动态特征的一个操作序列。

（2)类(Class)类是具有相同属性和方法的一组对象的集合，它为属于该类的全部对象提供了统一的抽象描述。10.4程序设计方法10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法OPP与OOP比较10.4程序设计方法10.1程序设计的概念10.2算法10.3程序设计语

言10.4程序设计方

法10.4.3可视化程序设计让程序设计人员利用语言工具本身所提供的各种控件，像搭积木式地构造应用程序的各种界面，使得整个界面设计是在“所见即所得”的可视化状态下完成。相对于编写代码方式的程序设计而言的，可视化程序设计具有直观形象、方便高效等优点。10.