计程序的基础机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言 5.1 程序设计语言学习语言是设

Size: px

Start display at page:

Download "计程序的基础机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言 5.1 程序设计语言学习语言是设"

特托危
7 years ago
Views:

1 第 5 章程序设计知识 5.1 程序设计语言 5.2 C 语言程序设计 5.3 数据结构 5.4 编译原理 5.5 本章小结

2 计程序的基础机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言 5.1 程序设计语言学习语言是设

3 机器语言的特点机器语言由二进制编码指令构成的语言是一种依附于机器硬件的语言机器语言程序可以直接执行机器语言程序片段 // 把地址为的内存单元中的数装入 0101 号寄存器 // 把地址为的内存单元中的数装入 0110 号寄存器 // 把和中的数相加, 结果存入 0000 号寄存器 // 把 0000 号寄存器中的数存入地址为的内存单元中

4 汇编语言的特点汇编语言由助记符指令构成的语言也是一种依附于机器硬件的语言汇编语言源程序需要汇编后才能执行汇编语言程序片段 MOV R5, X // 把内存单元 X 中的数装入 R5 寄存器 ADD R5, Y MOV Z, R5 // 把 R5 中的数与 Y 单元中的数相加, 结果存入 R5 // 把 R5 中的数存入 Z 单元中

5 高级语言的特点高级语言由自然语言和数学公式表示的语言是一种独立于机器硬件的语言高级语言程序需要编译后才能执行高级语言程序片段 Z=X + Y // 把内存单元 X 中的数与 Y 中的数相加, 结果存入 Z 单元

6 常用高级语言 FORTRAN 语言高级语言 FORTRAN 是 FORmula TRANslator( 公式翻译器 ) 的缩写主要用于复杂的科学计算领域 ALGOL 语言 ALGOL 是 ALGOrithm Language( 算法语言 ) 的缩写主要用于数学与科学计算

7 常用高级语言 COBOL 语言高级语言 COBOL 是 COmmon Business-Oriented Language( 面向商业的通用语言 ) 的缩写主要用于企业管理和事务处理 BASIC 语言 BASIC 是 Beginner s All-purpose Symbolic Instruction Code( 初学者通用符号指令码 ) 的缩写主要用于初学者和较小规模的程序开发

8 5.1.4 结构化程序设计语言早期程序设计方法的不足注重功能的实现 / 注重内存的节省 / 注重执行效率的提高不注重程序结构的清晰性不注重程序的可理解性和可修改性结构化程序设计语言的特点注重程序结构的清晰性注重程序的可理解性和可修改性采用模块化程序设计方法

9 5.1.4 结构化程序设计语言常用结构化程序设计语言 PASCAL 语言是在 ALGOL 语言的基础上发展起来的以法国著名科学家帕斯卡的名字命名严格的语法格式与结构化形式 C 语言是在 ALGOL60 语言的基础上发展起来的兼具低级语言和高级语言的特点是最为流行的程序设计语言之一

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

11 5.1.5 面向对象程序设计语言面向对象程序设计语言的特点将问题分解为对象对象将自己的属性和方法封装成一个整体, 供程序设计者使用对象之间的相互作用则通过消息传递来实现使人们对复杂系统的认识过程与程序设计过程尽可能一致

12 5.1.5 面向对象程序设计语言常用面向对象程序设计语言 Simula 67 C++ Java 发布于 1967 年, 是面向对象语言的鼻祖发布于 1983 年, 是在 C 语言的基础上发展起来的 C++ 是得到广泛应用的一种面向对象语言目前常用的版本有 Visual C++, C#, Visual C++.Net 等发布于 1995 年, 适合于网络程序设计也是目前得到广泛应用的一种面向对象程序设计语言

13 5.1.6 可视化程序设计语言可视化程序设计语言的特点以图形化的编程方式将面向对象技术的特性体现出来使开发软件这一原本枯燥难以理解的工作变得相对轻松快捷常用可视化程序设计语言 Visual C++ 功能强大, 比较适合专业人员使用 Visual Basic 易于学习和掌握, 比较适合非专业人员和初学者使用

14 5.1.7 人工智能程序设计语言人工智能程序设计语言的特点适合于知识表示和逻辑推理常用人工智能程序设计语言 LISP LISP 是 LISt Processing( 表处理 ) 的缩写可以解决人工智能中的符号处理问题 PROLOG 是 PROgramming in LOGic( 逻辑程序设计 ) 的缩写自动实现模式匹配自动回溯这两种人工智能中常用的基本操作

15 C 语言的主要特点 5.2 C 语言程序设计简洁紧凑灵活语法限制不太严格, 使用方便灵活 ; 数据结构描述能力及表达式能力强 ; 程序书写形式自由模块化结构化用 C 语言编写程序层次清晰, 便于按模块组织程序, 易于实现程序的结构化功能强大 C 语言除了能实现一般的高级语言的功能外, 还能实现汇编语言的大部分功能, 兼具高级语言和低级语言的特点可移植性好 C 语言程序可以容易地移植到不同型号计算机不同操作系统环境下执行

16 5.2 C 语言程序设计 C 语言的基本要素 C 语言的数据类型 C 语言的运算符及表达式 C 语言语句 C 语言程序的三种基本结构及实现程序设计风格算法设计与分析

17 5.2.1 C 语言的基本要素 C 语言的基本词法字符集英文字母 / 数字 / 特殊字符 / 转义字符标识符 C 语言中各种对象的名字用标识符表示标识符是由字母数字和下划线三种字符构成的且第一个字符必须是字母或下划线的字符序列标识符分为三类关键字 / 预定义标识符 / 用户标识符

18 常量 C 语言的基本要素在程序的执行过程中其值不能被改变的量变量数值型常量整型常量 / 浮点型常量 ( 实型常量 ) 字符型常量字符常量 / 字符串常量在程序运行过程中, 其值可以被改变的量一般要先定义, 再使用, 变量定义的一般形式为 : 数据类型名变量名 ;

19 5.2.2 C 语言的数据类型基本数据类型整型整型变量的定义形式为 :int 变量名 ; 实型实型变量的定义形式为 :float 变量名 ; 字符型字符型变量的定义格式为 :char 变量名 ; 构造数据类型数组 / 结构体 / 共用体 / 枚举类型 / 用户自定义类型指针类型在动态数据结构及其应用中有着不可替代的作用

20 5.2.3 C 语言的运算符及表达式算术运算符 +, -, *, /, %( 求余数 ) 赋值运算符在 C 语言中,= 称为赋值运算符, 其使用形式为 : 变量名 = 表达式自增自减运算符 ++ 是自增运算符, 其功能是使变量的值增 1 -- 是自减运算符, 其功能是使变量的值减 1 关系运算符大小判断 >( 大于 )/>=( 大于等于 )/<( 小于 )/<=( 小于等于 ) 相等判断 ==( 等于 )/!=( 不等于 )

21 5.2.4 C 语言语句控制语句用于实现一定的控制功能条件语句 : 用于实现程序执行过程中的条件转移循环语句 : 用于实现程序中重复进行某些操作复合语句由一对花括号 { } 括起来的一组语句如果要在只执行一条语句的地方执行多条语句, 那么这多条语句要写成一条复合语句

22 5.2.5 C 语言程序的三种基本结构顺序结构程序的执行按照语句出现的先后次序顺序进行程序中的每个语句都会被执行到程序示例 : 通过键盘输入一个三角形的底和高, 计算其面积并输出 main( ) { float width,height,area; /* 定义变量 */ printf("\nenter width and height:"); /* 输出提示信息 */ scanf("%f,%f",&width,&height); /* 通过键盘输入底和高 */ area=(width*height)/2.0; /* 计算面积 */ printf("\nthe arae is :%f ",area); /* 输出面积的值 */ }

23 5.2.5 C 语言程序的三种基本结构分支结构根据逻辑条件的成立与否, 分别选择执行不同的处理 if 语句 :if( 表达式 ) 语句 if-else 语句 :if ( 表达式 ) 语句 1 else 语句 2

24 5.2.5 C 语言程序的三种基本结构分支结构程序示例 : 根据输入的学生成绩对其进行判断处理, 如果成绩及格, 则输出 Passed, 否则输出 Failed main( ) { float score; /* 定义变量 */ } printf("\nenter a score :"); /* 显示提示信息 */ scanf("%f",&score); /* 通过键盘输入一个成绩 */ if (score>=60.0) printf("\npassed "); else printf("\nfailed "); /* 大于等于 60 输出 Passed*/ /* 小于 60 输出 Failed*/

25 5.2.5 C 语言程序的三种基本结构循环结构根据循环条件的变化, 决定是否继续重复执行某些语句 for 循环语句的格式为 : for ( 表达式 1; 表达式 2; 表达式 3) 循环体语句

26 5.2.5 C 语言程序的三种基本结构循环结构程序示例 : 从键盘上输入 10 个整数, 求其累加和并输出 main( ) { int i, num, sum; /* 定义变量 */ sum=0; /* 累加变量清零 */ for (i=1; i<=10;i++) /* 循环次数为 10*/ { printf("enter a data:\n "); /* 显示提示信息 */ scanf("%d ",&num); /* 通过键盘输入一个整数 */ sum=sum+num; /* 累加求和 */ } printf( \nsum=%d,sum); /* 输出累加结果 */ }

27 主要体现在 5 个方面程序设计风格标识符的命名要风格统一见名知义一般一行写一条语句, 一条长语句可以写在多行上, 但尽量不要把多条语句写在一行上采用缩进格式, 即同一层次的语句要对齐, 低层次的语句要缩进若干个字符, 增加程序的可读性适当书写注释信息, 有助于阅读者对程序的理解尽量少用 goto 语句, 否则容易导致程序结构混乱

28 5.2.7 算法设计与分析用计算机解决问题的步骤分析问题设计算法选定语言编写源程序对源程序进行编译生成目标文件对目标文件进行连接操作, 生成可执行的程序调试执行可执行程序

29 程序与算法算法设计与分析算法是指为解决某一问题而采取的方法和步骤程序是程序设计人员编写的计算机能够理解并执行的命令集合, 是算法在计算机中的实现算法的特点有穷性 / 确定性 / 有效性 / 输入及输出算法的表示自然语言 / 流程图 / 伪码算法的评价标准正确性 / 时间复杂度 / 空间复杂度 / 可理解性

30 5.3 数据结构概念和术语线性结构树形结构图状结构

31 5.3.1 概念和术语数据信息的载体, 能够被计算机识别存储和加工处理数据项数据不可分割的最小单位数据元素数据的基本单位, 具有完整确定的实际意义一般由若干数据项组成数据对象具有相同性质的数据元素的集合, 是数据的一个子集数据结构互相之间存在着一种或多种关系的数据元素的集合

32 数据的逻辑结构概念和术语描述的是数据元素之间的逻辑关系数据的物理结构数据在计算机中的表示, 包括数据元素的表示及数据元素间关系的表示顺序存储逻辑上相邻的元素存储在物理位置也相邻的存储单元中链式存储逻辑上相邻的元素不要求其物理位置相邻, 元素间的逻辑关系通过附设的指针字段来表示

33 线性结构的特点线性结构数据元素之间存在着一对一的关系每个元素有且只有一个前驱 ( 第一个元素除外 ) 每个元素有且只有一个后继 ( 最后一个元素除外 ) 应用示例一维数组二维数组

34 5.3.2 线性结构一维数组应用示例 main() { int i, g, sum, ave; /* 定义变量, 每一变量代表一内存单元 */ int a[50]; /* 定义数组, 代表 50 个内存单元 */ for (i=1; i<=50; i++) /* 循环执行下面大括号中的语句 50 次 */ { printf( \nenter a grade: ); /* 在屏幕上显示提示信息 */ scanf( %d,&g); /* 通过键盘输入一个学生的成绩给变量 g*/ a[i-1]=g; /* 把 g 单元中的成绩存入数组的相应位置 */ } sum=0; /* 作为累加器的单元初值清零 */ for (i=1; i<=50; i++) /* 循环执行下面的累加语句 40 次 */ sum=sum+a[i-1]; /* 把第 i 个学生的成绩加到累加器 */ ave=sum/50; /* 求平均成绩 */ printf( \nave=%d, ave); /* 输出平均成绩 */ }

35 树形结构的特点树形结构数据元素之间存在着一对多的关系树的定义树是 n( 0) 个结点的有限集合当 n=0 时, 称为空树在一棵非空树 T 中 : 有一个特定的结点称为树的根结点 ; 当 n>1 时, 除根结点之外的其余结点被分成 m(m 1) 个互不相交的集合 T1,T2,,Tm, 其中每一个集合 Ti(1 i m) 本身又是一棵树, 树 T1,T2,,Tm 称为这个根结点的子树

36 5.3.3 树形结构二叉树的定义二叉树是有限个结点的集合, 该集合或者为空或者由一个称为根的结点及两个不相交的被分别称为左子树和右子树的二叉树组成当集合为空时, 称该二叉树为空二叉树满二叉树 : 在二叉树中, 如果所有分支结点都存在左子树和右子树, 并且所有叶子结点都在同一层上, 这样的一棵二叉树称作满二叉树完全二叉树 : 一棵深度为 k 的有 n 个结点的二叉树, 对树中的结点按从上至下从左到右的顺序进行编号, 如果编号为 i(1 i n) 的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同, 则这棵二叉树称为完全二叉树

37 5.3.3 树形结构二叉树示例完全二叉树满二叉树非完全二叉树

38 5.3.3 树形结构二叉树的存储顺序存储结构 B A 2 C 3 用一组连续的存储单元 ( 数组 ) 存放二叉树中的结点一般是按 D 4 E 5 F 6 G 7 照二叉树结点从上至下从左到右的顺序存储 H I J K L M O P 完全二叉树和满二叉树采用顺序存储比较合适, 树中结点的序号可以唯一地反映出结点之间的逻辑关系 1 A 图, 5.7 满二叉树这样既能够最大可能地节省存储空间, 又可以利用数组元素的下标值确定结点在二叉树 2 C 3 中的位置以及结点之间的关系 B D 4 E 5 F 6 G 7 H I J K L 图 5.8 完全二叉树

39 5.3.3 树形结构二叉树的存储链式存储结构 B A 2 C 3 用链表来表示一棵二叉树链表中每个结点由三个域组成, 除了 D 4 E 5 F 6 G 7 数据域外, 还有两个指针域, 分别用来给出该结点的左子结点和右子结点所在的链结点的存储地址 H I J K L M O P A 图 5.7 满二叉树 B 2 C 3 非完全二叉树的链式存储 D 4 E 5 F 6 G 7 H I J K L 图 5.8 完全二叉树

40 5.3.3 树形结构树的应用用于分类的决策树用于各种比赛的博弈树有 7 根火柴, 甲乙两人依次从中取走 1 根或 2 根, 但不能不取, 取走最后一根火柴的就是获胜者可以用二叉树来解

41 图状结构的特点图状结构数据元素之间存在着多对多的关系图的定义 G=(V,E); 其中 V={v i v i dataobject}; E={( v i,v j ) v i, v j V P(v i, v j )} G 表示一个图,V 是图 G 中顶点的集合, 顶点集合构成数据对象 (dataobject), 顶点就代表数据元素,E 是图 G 中边的集合, 集合 E 中 P(v i,v j ) 表示顶点 v i 和顶点 v j 之间有一条直接连线, 即偶对 (v i,v j ) 表示图中的一条边

42 5.3.4 图状结构图的示例图的存储邻接矩阵用矩阵表示图中各顶点之间的邻接关系, 有边相连对应的矩阵元素值为 1, 否则为 0

43 5.3.4 图状结构图的存储邻接表一种顺序存储与链式存储结合的存储方法对于图 G 中的每个顶点 v i, 将所有邻接于 v i 的顶点 v j 链成一个单链表, 这个单链表就称为顶点 v i 的邻接表, 再将所有顶点的邻接表表头放到数组中, 就构成了图的邻接表

44 图的应用求最短路径网络性能分析图状结构

45 编译程序概述词法分析语法分析中间代码生成中间代码优化目标代码生成编译程序的开发 5.4 编译原理

46 高级语言的特点编译程序概述简单易学, 易于编写和修改程序编写出的源程序不能直接执行编译程序把用高级语言编写的源程序翻译成等价的机器语言程序的翻译程序学习编译知识的作用深入理解高级语言程序设计有助于提高程序设计能力和培养程序设计思维

47 词法分析的主要任务词法分析从源程序中识别出单词发现词法错误并指出错误位置以某种机内符的形式表示单词单词种类基本字 : 也称关键字, 如 C 语言中的 for do while 等 ; 标识符 : 用来表示各种名字的符号串, 如变量名函数名等 ; 常数 : 各种类型的常数, 如整数实数字符串等 ; 运算符 : 各种算术运算关系运算符, 如 + - < > <= >= 等 ; 界限符 : 如逗号 (,) 分号(;) 等

48 语法分析的主要任务语法分析确认作为词法分析结果的单词序列是否为给定语言的一个正确程序给定语言用文法表示, 如果给定的单词串能够识别成该文法的句子, 则认为程序是正确的, 否则认为程序是错误的自顶向下分析方法 / 自底向上分析方法调用语义子程序进行语义处理审查每个语法结构的静态语义, 即确认语法结构合法的程序是否真正有意义

49 5.4.4 中间代码生成中间代码生成的主要任务以某种便于计算机处理的形式表示程序引入中间代码的优点使编译程序结构在逻辑上更为简单明确可以将与机器相关的某些实现细节置于代码生成阶段仔细处理使得计算和代码优化比较容易实现常用的中间代码形式逆波兰式 / 三元式 / 四元式

50 逆波兰式计算的优点中间代码生成 a+b*c 的逆波兰式形式为 abc*+ 对于逆波兰式 abc*+, 计算机先扫描到运算对象 a b 和 c, 然后扫描到运算符 *, 先计算 b*c( 假定结果为 t), 继续扫描到运算符 +, 再计算 a+t, 从而完成 a+b*c 的计算无论表达式多复杂, 只一遍扫描就能完成表达式的计算对于一般表达式 a+b*c, 计算机先扫描到运算对象 a, 然后扫描到运算符 + 和运算对象 b, 由于不知道后面的运算符是什么, 不能决定是否先完成 + 的运算, 继续扫描到运算符 * 和运算对象 c, 知道 * 的优先级高, 先计算 b*c( 假定结果为 t), 再往回扫描计算 a+t 对于比较复杂的表达式, 可能需要多次来回扫描表达式, 才能完成计算, 这会很浪费时间

51 5.4.5 中间代码优化中间代码优化的主要任务对中间代码进行等价变换变换后的代码运行结果与变换前运行结果相同运行效率提高 ( 速度提高或 / 和占用存储空间减少 ) 常用的优化技术删除多余运算 / 代码外提 / 强度削弱变换循环控制条件 / 合并已知量与复写传播删除无用赋值

52 5.4.6 目标代码生成目标代码生成的主要任务把经过优化后的中间代码转换成特定机器的机器语言程序或汇编语言程序由于一个高级语言源程序的目标代码需多次使用, 因此代码生成器的设计要着重考虑目标代码的质量目标代码的质量主要从占用空间和执行时间两个方面综合考虑

53 编译程序的特点编译程序的开发一个相当复杂的系统软件编译程序的自动生成主要是语义分析和优化问题完全自动生成编译程序, 目前还不现实

54 5.5 本章小结程序设计能力程序设计思维是计算机专业学生应具备的基本能力和素质计算机专业人员要想发挥专业特长, 在工作中有竞争力, 较强的程序设计能力和软件开发能力是坚实的基础与提高程序设计能力相关的知识有程序设计语言数据结构编译原理和算法设计与分析熟悉一种程序设计语言和基本的程序设计方法是编写程序的基础对于数据量比较大或数据之间关系比较复杂的程序, 要选用合适的数据结构合理地组织数据计算机专业学生重点还是要培养和提高算法设计能力用高级语言编写的源程序需要翻译成机器语言程序, 才能被计算机执行编译原理就是介绍如何把高级语言源程序翻译成机器语言程序的

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用

计程序的基础机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言 5.1 程序设计语言 学习语言是设

计程序的基础机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言 5.1 程序设计语言学习语言是设