【教学课件】第5章程序设计知识.ppt

第5章 程序设计知识,5.1 程序设计语言5.2 C语言程序设计5.3 数据结构5.4 编译原理,5.1 程序设计语言,机器语言汇编语言高级语言结构化程序设计语言 面向对象程序设计语言可视化程序设计语言 人工智能程序设计语言,学习语言是设计程序的基础,5.1.1 机器语言,机器语言的特点 由二进制编码指令构成的语言。是一种依附于机器硬件的语言。机器语言程序可以直接执行。机器语言程序片段 0001 0101 01101100/把地址为01101100的内存单元中的数装入0101号寄存器 0001 0110 01101101/把地址为01101101的内存单元中的数装入0110号寄存器 0101 0000 01010110/把01101100和01101101中的数相加,结果存入0000号寄存器 0011 0000 01101110/把0000号寄存器中的数存入地址为01101110的内存单元中,5.1.2 汇编语言,汇编语言的特点 由助记符指令构成的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。汇编语言程序片段 MOV R5,X/把内存单元X中的数装入R5寄存器 ADD R5,Y/把R5中的数与Y单元中的数相加，结果存入R5 MOV Z,R5/把R5中的数存入Z单元中,5.1.3 高级语言,高级语言的特点 由自然语言和数学公式表示的语言。是一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。高级语言程序片段 Z=X+Y/把内存单元X中的数与Y中的数相加，结果存入Z单元,5.1.3 高级语言,常用高级语言 FORTRAN语言FORTRAN是FORmula TRANslator（公式翻译器）的缩写。主要用于复杂的科学计算领域。ALGOL语言ALGOL是ALGOrithm Language（算法语言）的缩写。主要用于数学与科学计算。,5.1.3 高级语言,常用高级语言 COBOL语言 COBOL是COmmon Business-Oriented Language（面向商业的通用语言）的缩写。主要用于企业管理和事务处理。BASIC语言 BASIC是Beginners All-purpose Symbolic Instruction Code（初学者通用符号指令码）的缩写。主要用于初学者和较小规模的程序开发。,5.1.4 结构化程序设计语言,早期程序设计方法的不足注重功能的实现/注重内存的节省/注重执行效率的提高。不注重程序结构的清晰性。不注重程序的可理解性和可修改性。结构化程序设计语言的特点 注重程序结构的清晰性。注重程序的可理解性和可修改性。采用模块化程序设计方法。,5.1.4 结构化程序设计语言,常用结构化程序设计语言 PASCAL语言 是在ALGOL语言的基础上发展起来的。以法国著名科学家帕斯卡的名字命名。严格的语法格式与结构化形式。C语言 是在ALGOL60语言的基础上发展起来的。兼具低级语言和高级语言的特点。是最为流行的程序设计语言之一。,5.1.5 面向对象程序设计语言,结构化程序设计方法的不足 面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离，所以很难自然、准确地反映真实世界，因而用编写出来的程序，特别是规模比较大的程序，其质量是难以保证的。强调了要实现功能的操作方法（模块），而被操作的数据（变量）处于实现功能的从属地位，即程序模块和数据结构是松散地耦合在一起，当程序复杂度较高时，容易出错，而且错误难以查找和修改。,5.1.5 面向对象程序设计语言,面向对象程序设计语言的特点 将问题分解为对象。对象将自己的属性和方法封装成一个整体，供程序设计者使用。对象之间的相互作用则通过消息传递来实现。使人们对复杂系统的认识过程与程序设计过程尽可能一致。能够更好地保证程序的质量和开发效率。,5.1.5 面向对象程序设计语言,常用面向对象程序设计语言 Simula 67 发布于1967年，是面向对象语言的鼻祖。C+发布于1983年，是在C语言的基础上发展起来的。C+是得到广泛应用的一种面向对象语言。目前常用的版本有Visual C+,C#,Visual C+.Net等。Java发布于1995年，适合于网络程序设计。也是目前得到广泛应用的一种面向对象程序设计语言。,5.1.6 可视化程序设计语言,可视化程序设计语言的特点 以图形化的编程方式将面向对象技术的特性体现出来。使开发软件这一原本枯燥、难以理解的工作变得相对轻松快捷。常用可视化程序设计语言Visual C+功能强大，比较适合专业人员使用。Visual Basic易于学习和掌握，比较适合非专业人员和初学者使用。,5.1.7 人工智能程序设计语言,人工智能程序设计语言的特点 适合于知识表示和逻辑推理。常用人工智能程序设计语言 LISP LISP是LISt Processing（表处理）的缩写。可以解决人工智能中的符号处理问题。PROLOG 是PROgramming in LOGic（逻辑程序设计）的缩写。自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。,5.2 C语言程序设计,C语言的主要特点简洁、紧凑、灵活。语法限制不太严格，使用方便灵活；数据结构描述能力及表达式能力强；程序书写形式自由。模块化、结构化。用语言编写程序层次清晰，便于按模块组织程序，易于实现程序的结构化。功能强大。C语言除了能实现一般的高级语言的功能外，还能实现汇编语言的大部分功能，兼具高级语言和低级语言的特点。可移植性好。C语言程序可以容易地移植到不同型号计算机、不同操作系统环境下执行。,5.2 C语言程序设计,C语言的基本要素C语言的数据类型 C语言的运算符及表达式 C语言语句 C语言程序的三种基本结构及实现 程序设计风格 算法设计与分析,5.2.1 C语言的基本要素,C语言的基本词法字符集英文字母/数字/特殊字符/转义字符。标识符C语言中各种对象的名字用标识符表示。标识符是由字母、数字和下划线三种字符构成的且第一个字符必须是字母或下划线的字符序列。标识符分为三类 关键字/预定义标识符/用户标识符。,5.2.1 C语言的基本要素,常量在程序的执行过程中其值不能被改变的量。数值型常量 整型常量/浮点型常量（实型常量）。字符型常量字符常量/字符串常量。变量在程序运行过程中，其值可以被改变的量。一般要先定义，再使用，变量定义的一般形式为：数据类型名 变量名；,5.2.2 C语言的数据类型,基本数据类型整型整型变量的定义形式为：int 变量名；实型实型变量的定义形式为：float 变量名；字符型字符型变量的定义格式为：char 变量名；构造数据类型数组/结构体/共用体/枚举类型/用户自定义类型。指针类型在动态数据结构及其应用中有着不可替代的作用。,5.2.3 C语言的运算符及表达式,算术运算符,*,/,%（求余数）。赋值运算符在C语言中，称为赋值运算符，其使用形式为：变量名 表达式自增、自减运算符+是自增运算符，其功能是使变量的值增1。-是自减运算符，其功能是使变量的值减1。关系运算符大小判断（大于）/（大于等于）/（小于）/（小于等于）。相等判断（等于）/!（不等于）。,5.2.4 C语言语句,控制语句 用于实现一定的控制功能。条件语句：用于实现程序执行过程中的条件转移。循环语句：用于实现程序中重复进行某些操作。复合语句由一对花括号 括起来的一组语句。如果要在只执行一条语句的地方执行多条语句，那么这多条语句要写成一条复合语句。,5.2.5 C语言程序的三种基本结构,顺序结构程序的执行按照语句出现的先后次序顺序进行。程序中的每个语句都会被执行到。程序示例：通过键盘输入一个三角形的底和高，计算其面积并输出。main()float width,height,area;/*定义变量*/printf(nEnter width and height:);/*输出提示信息*/scanf(%f,%f,/*输出面积的值*/,5.2.5 C语言程序的三种基本结构,分支结构根据逻辑条件的成立与否，分别选择执行不同的处理。if语句：if（表达式）语句if-else语句：if（表达式）语句1 else 语句2,5.2.5 C语言程序的三种基本结构,分支结构程序示例：根据输入的学生成绩对其进行判断处理，如果成绩及格，则输出Passed，否则输出Failed。main()float score;/*定义变量*/printf(nEnter a score:);/*显示提示信息*/scanf(%f,/*小于60输出Failed*/,5.2.5 C语言程序的三种基本结构,循环结构根据循环条件的变化，决定是否继续重复执行某些语句。for循环语句的格式为：for（表达式1；表达式2；表达式3）循环体语句,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,/*输出累加结果*/,5.2.6 程序设计风格,主要体现在5个方面标识符的命名要风格统一、见名知义。一般一行写一条语句，一条长语句可以写在多行上，但尽量不要把多条语句写在一行上。采用缩进格式，即同一层次的语句要对齐，低层次的语句要缩进若干个字符，增加程序的可读性。适当书写注释信息，有助于阅读者对程序的理解。尽量少用goto语句，否则容易导致程序结构混乱。,5.2.7 算法设计与分析,用计算机解决问题的步骤分析问题、设计算法。选定语言、编写源程序。对源程序进行编译生成目标文件。对目标文件进行连接操作，生成可执行的程序。调试执行可执行程序。,5.2.7 算法设计与分析,程序与算法算法是指为解决某一问题而采取的方法和步骤。程序是程序设计人员编写的、计算机能够理解并执行的命令集合，是算法在计算机中的实现。算法的特点有穷性/确定性/有效性/输入及输出。算法的表示自然语言/流程图/伪码。算法的评价标准正确性/时间复杂度/空间复杂度/可理解性。,5.3 数据结构,概念和术语线性结构树形结构图状结构,5.3.1 概念和术语,数据信息的载体，能够被计算机识别、存储和加工处理。数据项数据不可分割的最小单位。数据元素数据的基本单位，具有完整、确定的实际意义。一般由若干数据项组成。数据对象具有相同性质的数据元素的集合，是数据的一个子集。数据结构互相之间存在着一种或多种关系的数据元素的集合。,5.3.1 概念和术语,数据的逻辑结构描述的是数据元素之间的逻辑关系。数据的物理结构数据在计算机中的表示，包括数据元素的表示及数据元素间关系的表示。,5.3.1 概念和术语,顺序存储逻辑上相邻的元素存储在物理位置也相邻的存储单元中。链式存储逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。,5.3.2 线性结构,线性结构的特点数据元素之间存在着一对一的关系。每个元素有且只有一个前驱（第一个元素除外）。每个元素有且只有一个后继（最后一个元素除外）。应用示例一维数组二维数组,5.3.2 线性结构,一维数组应用示例 main()int i,g,sum,ave;/*定义变量，每一变量代表一内存单元*/int a50;/*定义数组，代表50个内存单元*/for(i=1;i=50;i+)/*循环执行下面大括号中的语句50次*/printf(“nEnter a grade:”);/*在屏幕上显示提示信息*/scanf(“%d”,/*输出平均成绩*/,5.3.3 树形结构,树形结构的特点数据元素之间存在着一对多的关系。树的定义树是n（0）个结点的有限集合。当n=0时，称为空树。在一棵非空树T中：有一个特定的结点称为树的根结点；当n1时，除根结点之外的其余结点被分成m（m1）个互不相交的集合T1，T2，Tm，其中每一个集合Ti（1im）本身又是一棵树，树T1，T2，Tm称为这个根结点的子树。,5.3.3 树形结构,二叉树的定义二叉树是有限个结点的集合，该集合或者为空、或者由一个称为根的结点及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。满二叉树：在二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。,5.3.3 树形结构,二叉树示例,满二叉树,完全二叉树,非完全二叉树,5.3.3 树形结构,二叉树的存储 顺序存储结构用一组连续的存储单元（数组）存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。,5.3.3 树形结构,二叉树的存储 链式存储结构用链表来表示一棵二叉树。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点的左子结点和右子结点所在的链结点的存储地址。,非完全二叉树的链式存储,5.3.3 树形结构,树的应用用于分类的决策树用于各种比赛的博弈树,5.3.4 图状结构,图状结构的特点数据元素之间存在着多对多的关系。图的定义 G（V，E）;其中Vvi|vidataobject；E(vi,vj)|vi,vj V P(vi,vj)。G表示一个图，V是图G中顶点的集合，顶点集合构成数据对象（dataobject），顶点就代表数据元素，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示图中的一条边。,5.3.4 图状结构,图的示例图的存储邻接矩阵用矩阵表示图中各顶点之间的邻接关系，有边相连对应的矩阵元素值为1，否则为0。,5.3.4 图状结构,图的存储邻接表一种顺序存储与链式存储结合的存储方法。对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表。,5.3.4 图状结构,图的应用求最短路径网络性能分析社会网络分析,5.4 编译原理,编译程序概述词法分析语法分析中间代码生成中间代码优化目标代码生成编译程序的开发,5.4.1 编译程序概述,高级语言的特点简单易学，易于编写和修改程序。编写出的源程序不能直接执行。编译程序把用高级语言编写的源程序翻译成等价的机器语言程序的翻译程序。学习编译知识的作用深入理解高级语言程序设计。有助于提高程序设计能力和培养程序设计思维。,5.4.2 词法分析,词法分析的主要任务从源程序中识别出单词。发现词法错误并指出错误位置。以某种机内符的形式表示单词。单词种类基本字：也称关键字，如C语言中的for、do、while等；标识符：用来表示各种名字的符号串，如变量名、函数名等；常数：各种类型的常数，如整数、实数、字符串等；运算符：各种算术运算、关系运算符，如+、-、=等；界限符：如逗号（，）、分号（；）等。,5.4.3 语法分析,语法分析的主要任务确认作为词法分析结果的单词序列是否为给定语言的一个正确程序。给定语言用文法表示，如果给定的单词串能够识别成该文法的句子，则认为程序是正确的，否则认为程序是错误的。自顶向下分析方法/自底向上分析方法。调用语义子程序进行语义处理。审查每个语法结构的静态语义，即确认语法结构合法的程序是否真正有意义。,5.4.4 中间代码生成,中间代码生成的主要任务以某种便于计算机处理的形式表示程序。引入中间代码的优点使编译程序结构在逻辑上更为简单明确。可以将与机器相关的某些实现细节置于代码生成阶段仔细处理。使得计算和代码优化比较容易实现。常用的中间代码形式逆波兰式/三元式/四元式。,5.4.4 中间代码生成,逆波兰式计算的优点a+bc的逆波兰式形式为abc+。对于逆波兰式abc+，计算机先扫描到运算对象a、b和c，然后扫描到运算符，先计算bc（假定结果为t），继续扫描到运算符+，再计算a+t，从而完成a+bc的计算。无论表达式多复杂，只一遍扫描就能完成表达式的计算。对于一般表达式a+bc，计算机先扫描到运算对象a，然后扫描到运算符+和运算对象b，由于不知道后面的运算符是什么，不能决定是否先完成+的运算，继续扫描到运算符和运算对象c，知道的优先级高，先计算bc（假定结果为t），再往回扫描计算a+t。对于比较复杂的表达式，可能需要多次来回扫描表达式，才能完成计算，这会很浪费时间。,5.4.5 中间代码优化,中间代码优化的主要任务对中间代码进行等价变换。变换后的代码运行结果与变换前运行结果相同。运行效率提高（速度提高或/和占用存储空间减少）。常用的优化技术删除多余运算/代码外提/强度削弱。变换循环控制条件/合并已知量与复写传播。删除无用赋值。,5.4.6 目标代码生成,目标代码生成的主要任务把经过优化后的中间代码转换成特定机器的机器语言程序或汇编语言程序。由于一个高级语言源程序的目标代码需多次使用，因此代码生成器的设计要着重考虑目标代码的质量。目标代码的质量主要从占用空间和执行时间两个方面综合考虑。,5.4.7 编译程序的开发,编译程序的特点一个相当复杂的系统软件。编译程序的自动生成主要是语义分析和代码优化问题。完全自动生成编译程序，目前还不现实。,GNU C/C+编译,汇编、链接器,5.5 本章小结,程序设计能力、程序设计思维是计算机专业学生应具备的基本能力和素质。计算机专业人员要想发挥专业特长，在工作中有竞争力，较强的程序设计能力和软件开发能力是坚实的基础。与提高程序设计能力相关的知识有程序设计语言、数据结构、编译原理和算法设计与分析。熟悉一种程序设计语言和基本的程序设计方法是编写程序的基础。对于数据量比较大或数据之间关系比较复杂的程序，要选用合适的数据结构合理地组织数据。计算机专业学生重点还是要培养和提高算法设计能力。用高级语言编写的源程序需要翻译成机器语言程序，才能被计算机执行。编译原理就是介绍如何把高级语言源程序翻译成机器语言程序的。,