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