第5章--程序设计知识

1、,第5章 程序设计知识,2,计算机工作步骤： 首先，明确给出工作步骤；算法设计 然后，用某种计算机能理解的方法告诉计算机。程序设计,第5章 程序设计知识,算法设计：给出完成任务的工作步骤。程序设计的高级阶段 程序设计：用计算机能理解的某种语言把算法改写成程序。,提高程序设计能力需要的知识： 1.语言知识：至少熟悉一种程序设计语言，能够根据算法思路 熟练地编写出高质量的程序； 2.数据结构知识：能够为要解决的问题设计出高效的数据逻辑 结构和存储结构，保证程序的运行效率； 3.编译知识：深入理解高级语言源程序的执行过程，有助于编 写出高质量的中大规模程序。,3,第5章 程序设计知识,5.1 程序设

2、计语言 5.2 C语言程序设计 5.3 数据结构 5.4 编译原理 5.5 本章小结,4,程序设计语言（programming language）：是人类与计算机交流的工具。告诉计算机完成某项工作的语言，一种让人与计算机之间进行交流，让计算机理解人的意图并按照人的意图完成工作的符号系统。,5.1 程序设计语言,计算机工作过程：针对要完成任务的步骤，基于某种程序 设计语言编写出程序，提交给计算机执行，从而完成该项任务。,计算机的工作是用程序来控制的。,5,5.1 程序设计语言,程序设计语言: 指令或语句的集合。 指令或语句：让计算机完成某项功能的命令。 指令机器语言或汇编语言中； 语句高级语言中

3、。,6,5.1 程序设计语言,机器语言 汇编语言 高级语言 结构化程序设计语言 面向对象程序设计语言 可视化程序设计语言 人工智能程序设计语言,学习语言是设计程序的基础,7,5.1.1 机器语言,由计算机硬件系统可以识别的二进制指令组成的语言称为机器语言。 机器语言的特点 由二进制编码指令构成的语言。 是一种依附于机器硬件的语言。 机器语言程序可以直接执行。,机器语言指令的组成：操作码+操作数 操作码用于说明指令的功能； 操作数用于说明参与操作的数据或数据所在单元的地址。 操作码和操作数都是以二进制的形式表示。,8,5.1.1 机器语言,【例5.1】机器语言程序示例。 程序功能：把两个内存单元

4、中的数相加，并将结果存入另外 一个单元。,0001 0101 01101100 /把地址为01101100的内存单元中的数装入 0101号寄存器 0001 0110 01101101 /把地址为01101101的内存单元中的数装入 0110号寄存器 0101 0000 0101 0110 /把0101和0110寄存器中的数相加, 结果存入 0000号寄存器 0011 0000 01101110 /把0000号寄存器中的数存入地址为01101110的 内存单元中,9,5.1.1 机器语言,机器语言的优缺点 缺点 ： 指令难以准确记忆； 程序容易写错； 程序难以理解和修改。 优点： 可直接执行，运

5、行效率高,10,5.1.2 汇编语言,汇编语言的特点 由助记符指令构成的语言。 也是一种依附于机器硬件的语言。 汇编语言源程序需要汇编后才能执行。汇编程序/汇编器,汇编语言指令的组成 助记符：表示指令的操作码。 （如MOV表示数据传送操作，ADD表示加法操作等。） 存储单元/寄存器:表示操作数。,11,5.1.2 汇编语言,【例5.2】汇编语言程序示例。 程序功能：把两个内存单元中的数据相加，并将结果存入另外 一个单元。,MOV R5, X /把内存单元X中的数装入R5寄存器 ADD R5, Y /把R5中的数与Y单元中的数相加，结果存入R5 MOV Z, R5 /把R5中的数存入Z单元中,汇

6、编语言的优缺点 优点：指令容易记忆，程序容易编写和理解；相对机器语言 缺点：助记符比较难以记忆，需要编程人员对计算机的硬件结构 有比较深入的了解。抽象层次很低，仍然是低级语言。,12,5.1.3 高级语言,高级语言的特点 由自然语言和数学公式表示的语言。 是一种独立于机器硬件的语言。 高级语言程序需要编译后才能执行。,【例5.3】高级语言程序示例。 程序功能：把两个内存单元中的数相加，并将结果存入另外 一个单元。,Z=X + Y /把内存单元X中的数与Y中的数相加，结果存入Z单元,13,5.1.3 高级语言,高级语言源程序需要先翻译成等价的目标程序， 才能为计算机理解和执行。,翻译程序的两种模

7、式： 编译程序：先把高级语言的源程序翻译成目标程序，然后经过连接装配程序生成可执行程序，最后运行可执行程序。 解释程序：边翻译边执行，不需要翻译成目标程序。,14,5.1.3 高级语言,三种语言的应用比较： 机器语言目前一般不直接用来编写程序。 汇编语言靠近机器，能够充分利用计算机硬件的特性，编写 出的程序效率较高，用于对效率要求较高的规模不 大的程序（如外设驱动程序、计算机控制程序等）。 高级语言用于编写规模较大的程序。,15,5.1.3 高级语言,1. FORTRAN语言 FORmula TRANslator（公式翻译器）的缩写。 用于数学公式的表达和科学计算。 第一个实用高级语言，其编译

8、程序也是史上第一个编译器。 FORTRAN 77 结构化程序设计语言， FORTRAN 2003 面向对象的程序设计语言。 应用领域：计算密集的分子生物学、高能物理学、大气物 理学、地质学和气象学（天气预报）。,16,5.1.3 高级语言,2. ALGOL语言 ALGOL是ALGOrithm Language（算法语言）的缩写。 用于科学计算。 ALGOL 60、 ALGOL 68 曾在我国得到广泛学习和使用； 后随着Pascal出现被逐渐淘汰。,3. COBOL语言 COmmon Business-Oriented Language（面向商业的通用语言）的缩写。 用于企业管理和事务处理，以一

9、种接近于英语书面语言的形 式来描述数据特性和数据处理过程，因而便于理解和学习。 应用领域：银行行业，可运行于大中型机环境。,17,5.1.3 高级语言,4. BASIC语言 Beginners All-purpose Symbolic Instruction Code （初学者通用符号指令码）的缩写。 用于初学者和较小规模的程序开发。简单易学 各种版本： True BASIC、Quick BASIC、Turbo BASIC 结构化程序设计语言 Visual BASIC 面向对象程序设计语言,18,5.1.4 结构化程序设计语言,早期程序设计方法的不足 注重功能的实现和编程技巧/注重内存的节省/

10、注重执行效率的提高。 不注重程序结构的清晰性。 不注重程序的可理解性和可修改性。 结构化程序设计方法的特点 强调从程序结构和风格上来研究程序设计。 结构化程序是由顺序结构、选择结构和循环结构构成； 注重程序结构的清晰性。 注重程序的可理解性和可修改性。 采用模块化程序设计方法。 结构化程序设计方法的精髓：自顶向下、逐步求精,19,5.1.4 结构化程序设计语言,模块: 若干个可单独命名和编址的部分。 模块化实际上是把一个复杂的大程序的编写分解为若干个相互联系、又相对独立的小程序的编写，使程序易于编写、理解和修改。,算法+数据结构=程序设计 Niklaus Wirth,20,5.1.4 结构化程

11、序设计语言,1. PASCAL语言 是在ALGOL语言的基础上发展起来的。 以法国著名科学家帕斯卡（机械式计算机）的名字命名。 主要特点：严格的语法格式与结构化形式，丰富完备的 数据类型，运行效率高，查错能力强。 版本及影响：Turbo Pascal 系列Borland公司 20世纪70-90年代，影响很大。,21,5.1.4 结构化程序设计语言,2. C语言 是在ALGOL60语言的基础上发展起来的。 发展历程：ALGOL60-CPL-BCPL-B-C 为编写UNIX操作系统而研发。 兼具低级语言（精炼、接近硬件，但过于简单、无数据类型）和高级语言（语句结构合理，有数据类型）的特点。 是最为

12、流行的程序设计语言之一。 流行版本：Turbo C、MS C、C+、C#、Visual C+ 和 Visual C+.Net等。,22,5.1.5 面向对象程序设计语言,结构化程序设计方法的不足 面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离，所以很难自然、准确地反映真实世界，因而用编写出来的程序，特别是规模比较大的程序，其质量是难以保证的。 强调了要实现功能的操作方法（模块），而被操作的数据（变量）处于实现功能的从属地位，即程序模块和数据结构是松散地耦合在一起，当程序复杂度较高时，容易出错，而且错误难以查找和修改。,23,5.1.5 面向对象程序设计语言,面向对象程序设计语言的特点

13、 将问题分解为对象。 对象将自己的属性和方法封装成一个整体，供程序设计者使用。 对象之间的相互作用则通过消息传递来实现。 使人们对复杂系统的认识过程与程序设计过程尽可能一致。,数据结构+算法 对象+消息,24,5.1.5 面向对象程序设计语言,常用面向对象程序设计语言 Simula 67 发布于1967年，是面向对象语言的鼻祖。 C+ 发布于1983年，是在C语言的基础上发展起来的。 C+是得到广泛应用的一种面向对象语言。 目前常用的版本有Visual C+, C#, Visual C+ .Net等。 Java 发布于1995年，适合于网络程序设计。 也是目前得到广泛应用的一种面向对象程序设计

14、语言。,25,5.1.6 可视化程序设计语言,可视化程序设计语言的特点 以图形化的编程方式将面向对象技术的特性体现出来。 通过用鼠标拖曳图形化的控件就可以完成Windows风格界面的设计工作，大大减轻了程序设计人员的编程工作量，使开发软件这一原本枯燥、难以理解的工作变得相对轻松快捷。 常用可视化程序设计语言 Visual C+ 功能强大，比较适合专业人员使用。 Visual Basic 易于学习和掌握，比较适合非专业人员和初学者使用。,26,5.1.7 人工智能程序设计语言,人工智能程序设计语言的特点 让计算机具有类似于人的智能，适合于知识表示和逻辑推理。 常用人工智能程序设计语言 LISP

15、LISP是LISt Processing（表处理）的缩写。 包含一套符号处理函数，具有符号集上的递归函数的计算能力，可以解决人工智能中的符号处理问题。 不足：一是数据类型少，表达能力有限； 二是程序执行速度较慢。,27,5.1.7 人工智能程序设计语言,PROLOG 是PROgramming in LOGic（逻辑程序设计）的缩写。 基于一阶谓词逻辑，既有坚实的理论基础，又有较强的表达能力；自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。 不足：系统开销较大，程序执行效率较低。,28,5.2 C语言程序设计,C语言的主要特点 简洁、紧凑、灵活。语法限制不太严格，使用方便灵活；数据结构

16、描述能力及表达式能力强；程序书写形式自由。 模块化、结构化。用语言编写程序层次清晰，便于按模块组织程序，易于实现程序的结构化。 功能强大。C语言除了能实现一般的高级语言的功能外，还能实现汇编语言的大部分功能，兼具高级语言和低级语言的特点。 可移植性好。C语言程序可以容易地移植到不同型号计算机、不同操作系统环境下执行。,29,5.2.1 C语言程序设计,自然语言的学习过程：（语法规则） 单字-组词-造句-句子构成文章 计算机语言的学习过程：（语法规则） 合法符号-单词符号（标识符、常量、表达式等）-语句-程序,程序的运行： 首先，手工检查是否正确； 一是语法是否正确，有无错误的符号、表达式、语句

17、等； 二是功能（语义）是否正确，是否实现了预期的功能。 然后，提交编译，如发现错误，继续修改，直至成功执行。,30,5.2.1 C语言程序设计,一般的编程操作流程为： 编辑（edit） 编译（compile） 链接（link或make或build） 调试运行（debug或run）该过程循环往复，直至完成。,31,5.2.1 C语言程序设计,C语言集成开发环境 1. Turbo C2.0 4.Visual C+ 2.C+ Builder 3.Dev-C+ 使用Turbo C2.0创建C语言程序的过程 1、创建工作文件夹 2、启动Turbo C2.0 3、创建C源程序：File菜单-New 4、编

18、译、连接和运行程序 5、保存源程序,32,最简单的C语言程序举例,例1.1 要求在屏幕上输出以下一行信息。 Hello world!,解题思路： 在主函数中用printf函数原样输出以上文字。,5.2.1 C语言程序设计,33,#include int main( ) printf(” Hello world!n”); return 0; ,函数的名字，表示主函数,C程序必须有一个 main 函数,5.2.1 C语言程序设计,34,#include int main( ) printf (” Hello world!.n”); return 0; ,主函数类型,5.2.1 C语言程序设计,35

19、,#include int main( ) printf (” Hello world!.n”); return 0; ,函数体,5.2.1 C语言程序设计,36,#include int main( ) printf (” Hello world!.n”); return 0; ,输出函数,输出语句,5.2.1 C语言程序设计,37,#include int main( ) printf (” Hello world!.n”); return 0; ,换行符,5.2.1 C语言程序设计,38,#include int main( ) printf (” Hello world!.n”); r

20、eturn 0; ,当main函数执行结束前 将整数0作为函数值,5.2.1 C语言程序设计,39,#include int main( ) printf (” Hello world!.n”); return 0; ,表示语句结束,用到函数库中的输入输出函数时,5.2.1 C语言程序设计,40,5.2 C语言程序设计,5.2.1 C语言的基本要素 5.2.2 C语言的数据类型 5.2.3 C语言的运算符及表达式 5.2.4 C语言语句 5.2.5 C语言程序的三种基本结构及实现 5.2.6 程序设计风格 5.2.7 算法设计与分析,41,5.2.1 C语言的基本要素,1. C语言的基本词法

21、字符集 (1) 英文字母(大、小写) (2) 数字：0,1,2,9。 (3) 特殊字符:+,-,*,/,%,=,_,(,),!,#,$, /class是关键字，不能用做变量名 char 89_name; / 变量名不能以数字开头 int is-loan; / 中划线不能出现在变量名中， / 字符间的连接应该采用下划线,47,5.2.1 C语言的基本要素,2.常量 在程序的执行过程中其值不能被改变的量。 数值型常量 整型常量 浮点型常量（实型常量）。 字符型常量 字符常量:由单引号括起来的单个字符，如A。 字符串常量:由双引号括起来的字符序列，如”Computer”，”a”.,48,5.2.1

22、C语言的基本要素,2.常量 字符型常量 字符串常量中字符的个数称为字符串长度。 在C中，字符串常量总是以0结束。 CHINA a a 字符常量和字符串常量区别开来 字符串长度和字符串所占内存空间数的区别,49,5.2.1 C语言的基本要素,3.变量 在程序运行过程中，其值可以被改变的量；用来存放初始值、中间结果或最终结果。 变量的作用是存取程序中需要处理的数据，对应内存中的一块存储区域，该区域的名称即为变量名，该区域的内容是变量的值。 变量有3个基本要素 合法的变量名 变量的数据类型 变量的数值,50,5.2.1 C语言的基本要素,例：int a = 12 ;,3.变量 一般要先定义，再使用，

23、变量定义的一般形式为： 数据类型名 变量名；,51,5.2.2 C语言的数据类型,数据类型,52,5.2.2 C语言的数据类型,1. 基本数据类型 整型 int 在32位计算机中是用4字节（32位长）来存储。 整型变量的定义形式为：int 变量名； int num; 实型 用于表示实数， float ，double 实型变量的定义形式为：float/double 变量名； 在32位计算机中是用float占4字节，double占8字节。 float f; double d;,53,5.2.2 C语言的数据类型,1. 基本数据类型 字符型 char 字符型变量的定义格式为：char 变量名； 注：

24、一个字符变量只能存放一个字符； 系统表示字符型数据时，不是将字符本身的形状存 入内存，而是将字符的ASCII码存入内存。 char mychar=a;,54,5.2.2 C语言的数据类型,2. 构造数据类型 构造数据类型包括：数组、结构体、共用体、枚举类型。 数组是相同类型元素的有序集合，每一个元素占用相同大小的内存单元，且按序连续存放。 数组一旦定义之后，就可在程序中引用和操作这些元素。,55,5.2.2 C语言的数据类型,2. 构造数据类型,一维数组的定义格式为： 数据类型 数组名数组长度； 一维数组元素的引用方式为： 数组名下标 注意：数组的下标序号总是从0开始的,int iArray5

25、=1,2,3,4,5; iArray0表示第1个元素； iArray4表示第5个元素；,（1）一维数组,56,5.2.2 C语言的数据类型,2. 构造数据类型,二维数组的定义格式为： 数据类型 数组名长度1长度2；,二维数组元素的引用方式为： 数组名下标1下标2,（2）二维数组,int iArray23=1,2,3,4,5,6; iArray00表示第1个元素； iArray01表示第2个元素； iArray12表示第6个元素；,57,5.2.2 C语言的数据类型,2. 构造数据类型,结构体：将不同类型的数据组合成一个有机的整体，以便于 引用，组合在一个整体中的数据是互相联系的。,共用体：几个

26、不同类型的变量共占同一段内存结构。,枚举类型：一个变量只有几种可能的值，将变量的值一一 列举出来，变量的值只限于列举出来的值的范围内。,3.指针类型 在动态数据结构及其应用中有着不可替代的作用。,58,例：求圆的面积 #include int main() float r,result; printf(Please input radius : ); scanf(%f, ,59,5.2.3 C语言的运算符及表达式,在C中，运算符和表达式是实现数据操作的两个重要组成部分。 运算符：即操作符，+，-，*，/等 操作数：是运算符的运算对象，变量、常量、函数等。 表达式：是由运算符和操作数按照一定规则

27、组合而成的式子。,例：(2*x+a)*sin(b)-20,60,根据运算符的操作数的个数不同，可将其分为： 单目运算符（一元）：对一个操作数运算 双目运算符（二元）：对二个操作数运算 三目运算符（三元）：对三个操作数运算,5.2.3 C语言的运算符及表达式,61,5.2.3 C语言的运算符及表达式,1. 算术运算符：, , *, /, %（求余数） 2. 赋值运算符: (=及其扩展赋值运算符) 3. 自增、自减运算符: (+、-) 4. 关系运算符：、! 5. 逻辑运算符：！ ,63,3. 自增、自减运算符单目运算符 自增： + +i ：先加1后使用 i+ ：先使用后加1 例：i=3; j1=

28、+i; j1=4 相当于执行：i=i+1; j1=i; j2=i+; j2=3 相当于执行：j2=i; i=i+1; 自减： - -i ：先减1后使用 i- ：先使用后减1 例：i=3; j1=-i; j1=2 相当于执行：i=i-1; j1=i; j2=i-; j2=3 相当于执行：j2=i; i=i-1;,5.2.3 C语言的运算符及表达式,64,5.2.3 C语言的运算符及表达式,4. 关系运算符双目运算符，结果值为真/假。 大小判断 、。 相等判断 、!。,2 = 8,a = 3 a = 3,2 + 3 4 - 1 2 + ( 3 4 ) - 1,65,5.2.4 C语言语句,1. 控

29、制语句 用于实现一定的控制功能。 条件语句：用于实现程序执行过程中的条件转移。 循环语句：用于实现程序中重复进行某些操作。 2. 复合语句 由一对花括号 括起来的一组语句。 如果要在只执行一条语句的地方执行多条语句，那么这多条语句要写成一条复合语句。,66,5.2.5 C语言程序的三种基本结构,1. 顺序结构 程序的执行按照语句出现的先后次序顺序进行。 程序中的每个语句都会被执行到。,【例5.4】通过键盘输入一个三角形的底和高， 计算其面积并输出。,main( ) float width,height,area; /*定义变量*/ printf(nEnter width and height:

30、); /*输出提示信息*/ scanf(%f,%f, /*输出面积的值*/ ,67,5.2.5 C语言程序的三种基本结构,说明： （1）C语言程序由函数构成，可以包含多个函数， 但最少也要包含一个函数，即main()函数。 （2）C程序书写格式自由。 （3） C程序可以包含语句的注释，有助于对程序的理解，不参与程序的运行。 /*/是多行注释； / 单行注释,68,5.2.5 C语言程序的三种基本结构,1. 顺序结构数据输出,(1) 字符输出函数putchar 作用：向终端输出一个字符。,例如：putchar(a); 作用：输出字符变量a的值。a可以是字符型变量或整型变量。,例如： putcha

31、r(a); putchar(n); putchar(101); 作用：输出字符a；输出换行符;输出字符A； 。,69,5.2.5 C语言程序的三种基本结构,1. 顺序结构数据输出,(2)格式输出函数printf printf (格式控制，输出表列),“格式控制”是用双引号括起来的字符串，包括两种信息： 格式说明由“%”和格式字符组成，如%d, %f等。其作用是 将输出的数据转换为指定的格式输出。 普通字符即需要原样输出的字符。 “输出表列”是需要输出的一些数据，可以是变量、表达式。,例如：int a=3; char b=s; printf(“a=%d,b=%c n”, a, b); 结果：a=

32、3,b=s,70,5.2.5 C语言程序的三种基本结构,1. 顺序结构数据输出,(2) 格式输出函数printf,71,5.2.5 C语言程序的三种基本结构,1. 顺序结构数据输入,(1) 字符输入函数getchar() 作用：从终端输入一个字符。,# include main() char c; c=getchar(); putchar(c); ,从终端输入字符a并按回车键， 运行结果： a a,注：在一个函数中调用getchar函数，应该在函数前加上 “包含命令”：#include ,72,5.2.5 C语言程序的三种基本结构,1. 顺序结构数据输入,(2)格式输出函数scanf scan

33、f (格式控制，地址表列),“格式控制”的含义同printf函数； “地址表列”是由若干个地址组成的表列，可以是变量的地 址，或字符串的首地址。,main() int a,b,c; scanf (“%d%d%d”, ,运行结果： 3 4 5 3,4,5,73,5.2.5 C语言程序的三种基本结构,2. 分支结构if语句 根据逻辑条件的成立与否，分别选择执行不同的处理。 if语句：if（表达式） 语句 if-else语句：if （表达式） 语句1 else 语句2,说明: if 后的 ( ) 不能省略。 语句可以是0条、1条或多条语句。若为多条语句，语句前后须加上，变成复合语句。,74,5.2.

34、5 C语言程序的三种基本结构,【例5.5】根据输入的学生成绩对其进行判断处理， 如果成绩及格，则输出Passed，否则输出Failed。,main( ) float score; /*定义变量*/ printf (nEnter a score :);/*显示提示信息*/ scanf (%f, /*小于60输出Failed*/ ,75,5.2.5 C语言程序的三种基本结构,2.分支结构switch语句 switch (表达式) case : s1; break ; case : s2; break ; . case : sn; break ; default : sn+1 another,可以是

35、多个语句，但不必用 。,匹配失败时默认处理分支。,76,5.2.5 C语言程序的三种基本结构,3. 循环结构for语句 根据循环条件的变化，决定是否继续重复执行某些语句。 for循环语句的格式为：,for （表达式1；表达式2；表达式3） 循环体语句,77,5.2.5 C语言程序的三种基本结构,【例5.6】从键盘上输入10个整数，求其累加和并输出。,main( ) int i, num, sum;/*定义变量*/ sum=0;/*累加变量清零*/ for (i=1; i=10;i+)/*循环次数为10*/ printf(Enter a data:n );/*显示提示信息*/ scanf(%d

36、,/*输出累加结果*/ ,78,5.2.5 C语言程序的三种基本结构,3.循环结构while语句,while （表达式） 循环体语句,while ( ) another,while ( ) another,int nNum=1, nTotal=0; while ( nNum=50 ) nTotal += nNum ; nNum+ ; ,79,5.2.5 C语言程序的三种基本结构,3.循环结构do-while语句,do 循环体语句 while （表达式）,注意：循环体至少执行1次,int nNum = 1, nTotal = 0; do nTotal += nNum; nNum+; while

37、( nNum=50 ) ;,80,5.2.5 C语言程序的三种基本结构,4. break语句和continue语句,break语句： 用来使流程跳出switch结构，继续执行switch语句下面的一个语句； 用来从循环体内跳出循环体，即提前结束循环，接着执行循环下面的语句。 不能用于循环语句和switch语句之外的任何其他语句中。,例如： for (r=1;r100) break; printf (“%f”,area); ,运行结果： area100时，执行break 语句，提前结束循环。,81,5.2.5 C语言程序的三种基本结构,4. break语句和continue语句,continue

38、语句： 作用为结束本次循环，即跳过循环体中下面尚未执行的语句，接着进行下一次是否执行循环的判定。 continue语句和break语句的区别： continue语句只结束本次循环，而不是终止整个循环的执行； 而break语句则是结束整个循环过程，不再判断执行循环的条件是否成立。,82,5.2.5 C语言程序的三种基本结构,4. break语句和continue语句,例如： main() int n; for (n=100;n=200;n+) if (n%3=0) continue; printf (“%d”, n); ,运行结果： 当n被3整除时，执行continue 语句，结束本次循环。,8

39、3,5.2.6 程序设计风格,主要体现在5个方面： 标识符的命名要风格统一、见名知义。 一般一行写一条语句，一条长语句可以写在多行上，但尽量不要把多条语句写在一行上。 采用缩进格式，即同一层次的语句要对齐，低层次的语句要缩进若干个字符，增加程序的可读性。 适当书写注释信息，有助于阅读者对程序的理解。 尽量少用goto语句，否则容易导致程序结构混乱。,84,5.2.7 算法设计与分析,1. 用计算机解决问题的步骤 （1）分析问题、设计算法：认真分析要解决的问题及要实现的功能，给出解决问题的明确步骤，即设计出针对要解决问题的算法。 （2）选定语言、编写源程序：根据问题的性质，选定一种合适的程序设计

40、语言(及相应的开发环境)，依据设计出的算法编写源程序。 （3）编译：对编写出的源程序进行编译，程序中如果没有错误的话，则编译生成目标文件（与源程序对应的机器语言文件）。如果发现程序中有错误，设法找到错误并改正。 （4）连接：对生成的目标文件进行连接操作，把目标文件与 相应的环境（运行系统、函数库）连接成可执行的程序。,85,5.2.7 算法设计与分析,1. 用计算机解决问题的步骤 （5）调试执行：执行可执行程序，选用一些有代表性的数据 对程序进行测试，经过一定的测试，如果没有发现错误， 程序就可以交付使用了。 如果在测试中发现错误，就要分析错误的性质： 如果是算法设计有问题，就应重新分析问题、

41、修改算法或重新设计算法； 如果是程序编写有问题，就设法在程序中找到错误所在并改正（程序查错排错）。 对于较大规模的程序，程序查错排错是一项困难的工作，既需要经验，也需要一定的方法和工具支持。,86,5.2.7 算法设计与分析,2. 计算机专业人员水平考试 程序员：主要工作是编写功能比较单一的程序，并完成模块 程序的调试、测试工作。 系统分析师：可以担任项目组长或项目经理，主要工作是进 行软件开发项目的总体分析和设计工作。 高级程序员：其承担的工作介于程序员和系统分析师之间， 一般是协助系统分析师完成系统分析和算法设 计工作，或组织程序员完成大型模块的开发工作。,程序员的主要工作是编写程序； 高

42、级程序员、系统分析师的主要工作是设计算法和软件系统 的总体设计。,87,5.2.7 算法设计与分析,1.程序与算法,算法：指为解决某一问题而采取的方法和步骤。 算法是被精确定义的一组规则，规定先做什么，再做什么，以及判断某种情况下做哪种操作；或说算法是步进式的完成任务的过程。,程序：指为让计算机完成特定的任务而设计的指令序列或语句 序列。 机器语言或汇编语言源程序由指令序列构成； 高级语言源程序由语句序列构成。 程序设计是沟通算法与计算机的桥梁。 程序是程序设计人员编写的、计算机能够理解并执行的命令集合，是算法在计算机中的实现。,88,5.2.7 算法设计与分析,2.算法的特点 有穷性：一个算

43、法必须总是在执行有限个操作步骤和可以 接受的时间内完成其执行过程。即对于一个算法，要求其在 时间和空间上均是有穷的。 确定性：算法中的每一步都必须有明确的含义，不允许存在二义性。 有效性：算法中描述的每一步操作都应该能有效地执行， 并最终得到确定的结果。 输入及输出：一个算法应该有零个或多个输入数据，有一 个或多个输出数据。执行算法的目的是为了求解，而“解”就 是输出，因此没有输出的算法是没有意义的。,89,5.2.7 算法设计与分析,3.算法的表示 自然语言表示：人们日常使用的语言，例如中文、英文等。 流程图表示：用规定的一组图形符号、流程线和文字说明 来表示各种操作的算法表示方法。 伪码表

44、示: 用一种介于自然语言和计算机语言之间的文字和 符号来描述算法。接近计算机语言，便于向计算机程序过渡。,90,5.2.7 算法设计与分析,4.算法的评价标准,算法的正确性：指算法能正确地完成所要解决的问题。,就目前的研究来看，要想通过理论方式证明一个算法的正确 性是非常复杂和困难的，一般采用测试的方法，基于算法编 写程序，然后对程序进行测试。 针对所要解决的问题，选定一些有代表性的输入数据，经程 序执行后，查看输出结果是否和预期结果一致，如果不一 致，则说明程序中存在错误，应予以查找并改正。 经过一定范围的测试和程序改正，不再发现新的错误，程序 可以交付使用，在使用过程中仍有可能发现错误，再

45、继续改 正，这时的改正称为程序维护。,91,5.2.7 算法设计与分析,4.算法的评价标准,算法的时间复杂度：指依据算法编写出程序后在计算机 上运行时所耗费的时间度量。,一个程序在计算机上运行的时间取决于程序运行时输入的数据量、对源程序编译所需要的时间、执行每条语句所需要的时间及语句重复执行的次数等。 把整个程序中语句的重复执行次数之和作为该程序的时间复杂度，记为T(n)，其中n为问题的规模。 例如：线性表的长度n，即线性表中数据的个数，也即是问题 的规模。,92,5.2.7 算法设计与分析,4.算法的评价标准,算法的时间复杂度,算法的时间复杂度T(n)实际上表示：当问题规模n充分大时， 该程

46、序运行时间的一个数量级，用O表示。 比较两个算法的时间复杂度时，不是比较两个算法对应程序 的具体执行时间，这涉及编程语言、编程水平和计算机速度 等多种因素，而是比较两个算法相对于问题规模n所耗费时间 的数量级。 例如：线性表的顺序查找和折半查找算法。,93,5.2.7 算法设计与分析,4.算法的评价标准,算法的空间复杂度：依据算法编写出程序后在计算机上 运行时所需内存空间大小的度量，也是和问题规模n有关的度量。,算法的可理解性：算法是为了人们的阅读与交流，可理 解性好的算法有利于人们的正确理解，有利于程序员据此 编写出正确的程序。,94,5.3 数据结构,5.3.1 概念和术语 5.3.2 线

47、性结构 5.3.3 树形结构 5.3.4 图状结构,95,数据处理： 数据：数值数据和非数值数据； 处理：既可以是算术运算，也可以是插入、删除、查找和排序 等操作。,5.3 数据结构,数据结构要解决的问题： 编写程序时：面对的是逻辑结构（数据的一种抽象表示，更符 合人们习惯）； 程序执行时：由支持相应结构的编译程序自动把逻辑结构映射 成物理结构，从而简化程序的编写，减轻编程 人员的工作量。,96,5.3.1 概念和术语,数据 信息的载体，能够被计算机识别、存储和加工处理。即计算机加工处理的对象，可以是数值数据，也可以是非数值数据。例如：图像、声音、文本等。 数据项 数据不可分割的最小单位。分为

48、数据项名和数据项值。 例如：年龄（数据项名）19、20（数据项值） 数据元素 数据的基本单位，具有完整、确定的实际意义。一般由 若干数据项组成。 例如：学生的基本情况学号、姓名、性别、年龄等。,97,5.3.1 概念和术语,数据对象（数据元素类） 具有相同性质的数据元素的集合，是数据的一个子集。 在某个具体问题中，数据元素都具有相同的性质，属于 同一数据对象，数据元素是数据元素类的一个实例。 例如：学生管理系统某大学学生的基本情况（数据） 本科生的基本情况（数据对象） 数据结构 互相之间存在着一种或多种关系的数据元素的集合。,98,5.3.1 概念和术语,根据数据元素间关系的不同特性，可以分成

49、如下三种基本结构： 线性结构 数据元素之间存在着一对一的关系，例如线性表、栈、队列和数组等。例如：按学号排列的学生数据。 树形结构 数据元素之间存在着一对多的关系，例如树、二叉树和森林等。例如：一个单位的工作人员之间的关系。 图状结构 数据元素之间存在着多对多的关系，也称网状结构，如无向图和有向图等。例如：铁路交通图。,99,5.3.1 概念和术语,数据的逻辑结构 从具体问题抽象出来的数学模型，描述的是数据元素之 间的逻辑关系。 数据的物理结构 数据在计算机中的表示，研究数据结构在计算机中的实 现方法，包括数据结构中元素的表示及数据元素间关系的表示。,100,5.3.1 概念和术语,顺序存储

50、逻辑上相邻的元素存储在物理位置也相邻的存储单元中。 常借助于程序设计语言中的数组来实现。 链式存储 逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。常借助于程序设计语言中的指针来实现。,101,5.3.2 线性结构,线性结构的特点 只有一个首结点和一个尾结点。 每个元素有且只有一个直接前驱（第一个元素除外）。 每个元素有且只有一个直接后继（最后一个元素除外）。 数据元素之间存在着一对一的关系。,线性结构表达式：（a1 , a2 , , an）,应用示例 一维数组 二维数组,102,5.3.2 线性结构,1. 一维数组,C语言中一维数组的定义格式为： 数据类型 数

51、组名数组长度； 一维数组元素的引用方式为： 数组名下标,注：对一维数组的访问(引用)是通过对其元素的访问来实现的， 即只能按元素访问，不能对数组进行整体访问。,103,5.3.2 线性结构,【例5.7】一个班有50名学生，学完计算机导论课程并参加考 试，有50个成绩，把这些成绩存储起来并能完成求平均成绩 等操作，这时的数据存储就可以选用一维数组。,【分析】： 把这50个考试成绩按顺序存放在连续的50个内存单元中， 假定第一个单元的地址为a,则第i个学生成绩所在单元的地址 为a+(i-1)，通过这样的计算方式，就可以把某个学生的成绩存 入相应的单元或从单元中取出。,104,5.3.2 线性结构,

52、main() int i, g, sum, ave; /*定义变量，每一变量代表一内存单元*/ int a50; /*定义数组，代表50个内存单元*/ printf(“nEnter grades:”); /*在屏幕上显示提示信息*/ for (i=1; i=50; i+) /*循环执行下面大括号中的语句50次*/ scanf( “%d”, /*输出平均成绩*/ ,105,5.3.2 线性结构,2. 二维数组,C语言中二维数组的定义格式为： 数据类型 数组名长度1长度2；,注： 数组名后的长度1和长度2分别为数组的第一维长度和第二 维长度，数组元素的个数就是两维长度之积。 可以认为二维数组是一维

53、数组的延伸，二维数组是特殊的 一维数组，它的元素类型又是一维数组。,106,5.3.2 线性结构,2. 二维数组,从逻辑结构上看，二维数组元素间的关系相当于矩阵。 从存储结构上看，内存是一维的线性空间，故要采取一定 的方式将二维的数组映射到一维的内存中去。一般采用行 优先的方式来存储二维数组。,上述矩阵行优先的存储顺序为：a00, a01, a02, a03, a04, a10, a34.,107,5.3.2 线性结构,2. 二维数组,编写程序时可以按逻辑结构引用数组元素，相应语言的编 译程序会自动转换成对相应线性内存单元的访问。这样编 程人员就不用计算每个数组元素在内存中的位置，直接按 下标

54、使用即可，方便了程序的编写。,二维数组元素的引用方式为： 数组名下标1下标2,【例5.8】一个班有50名学生，一个学期学完计算机导论、高等 数学、线性代数和大学英语4门课程，期末考试后，便有 50*4=200个成绩，如果要对这些成绩进行存储和处理，就可以 选用二维数组。,108,5.3.2 线性结构,main() int grade504, sum50, ave50; /* 定义3个二维整型数组 */ int i, j; /*定义两个整型变量*/ printf(“nPlease input the students grades:n”); /*显示提示信息*/ for ( i=1; i50;

55、i+) /*通过二重循环输入每个学生的4门课程成绩*/ for( j=0; j4; j+) scanf( “%d”, i50; i+) sumi =0; /*每个学生的初始总成绩清零*/ for ( j=0; j4; j+) sum i = sum i + grade i j; /*求每个学生的总成绩*/ avei = sumi /4; /*求每个学生的平均成绩*/ printf (“The students average grades are: ”); for ( i=0; i50; i+) printf(“n%3d”, avei); /*输出每个学生的平均成绩*/ ,110,5.3.3

56、树形结构,树形结构的特点 数据元素之间存在着一对多的关系。 非线性结构，一个直接前驱，但可能有多个直接后继 树形结构的应用 人类社会的族谱、各种社会机构的组织形式等具有明显层次关系的结构。,111,5.3.3 树形结构,树是n（0）个结点的有限集合。当n=0时，称为空树。 在一棵非空树T中： 有一个特定的结点称为树的根结点； 当n1时，除根结点之外的其余结点被分成m（m1）个互不相交的集合T1，T2，Tm，其中每一个集合Ti （1im）本身又是一棵树，并且称为根结点的子树。,1. 树,112,5.3.3 树形结构,1. 树,有序树：一棵树中结点的各子树从左到右是有次序的，即若 交换了某结点各子

57、树的相对位置，则构成不同的树， 则称为有序树。 无序树：反之，若结点各子树可互换位置，则称为无序树。 森林：零棵或有限棵不相交的树的集合成为森林。,根结点：即没有前驱的结点。 叶子结点：即终端结点(没有后继的结点)。,113,5.3.3 树形结构,1. 树,父结点：即上层的那个结点(直接前驱)。 孩子结点：即下层结点的子树的根(直接后继)。 兄弟结点：具有同一个父结点的子结点互称为兄弟结点。 堂兄弟：即双亲位于同一层的结点（但并非同一双亲）。 祖先：即从根到该结点所经分支的所有结点。 子孙：即该结点下层子树中的任一结点。,114,5.3.3 树形结构,1. 树,结点的层数：从根到该结点的层数（根结点算第一层）。 树的深度：指所有结点中最大的层数（Max各结点的层次）。 树的度：所有结点度中的最大值（Max各结点的度）。,结点的度：结点所拥有的子树的个数称为结点的度。 终端结点：即叶结点，度为0的结点称为终端结点。 分支结点：度不为0的结点称为分支结点。,115,5.3.3 树形结构,1）二叉树的概念 二叉树：有限个结点（n0）的集合，该集合或者为空、 或者由一个称为根的结点及两个不相交的、被分别 称为左子树和右子树的二叉树组成。当集合为空 时，称该二叉树为空二叉树。,2. 二叉树,逻辑结构： 一对二（1：2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树