程序设计及软件开发知识.pptx

计算机导论1第第5 5讲讲 计算机计算机软件系统软件系统及软件开发及软件开发（2 2）5.5 程序设计语言程序设计语言 C语言程序设计语言程序设计5.6 数据结构数据结构5.7 编译原理编译原理5.8 软件工程本本讲讲小结小结25.5 5.5 程序设计语言程序设计语言机器语言机器语言汇编语言汇编语言高级语言高级语言结构化程序设计语言结构化程序设计语言 面向对象程序设计语言面向对象程序设计语言可视化程序设计语言可视化程序设计语言 人工智能程序设计语言人工智能程序设计语言学习语言是设计程序的基础35.5.1 5.5.1 机器语言机器语言机器语言的特点机器语言的特点 由二进制编码指令构成的语言。由二进制编码指令构成的语言。是一种依附于机器硬件的语言。是一种依附于机器硬件的语言。机器语言程序可以直接执行。机器语言程序可以直接执行。机器语言程序片段机器语言程序片段 0001 0101 01101100 /把地址为把地址为01101100的内存单元中的数装入的内存单元中的数装入0101号寄存器号寄存器 0001 0110 01101101 /把地址为把地址为01101101的内存单元中的数装入的内存单元中的数装入0110号寄存器号寄存器 0101 0000 01010110 /把把01101100和和01101101中的数相加中的数相加,结果存入结果存入0000号寄存器号寄存器 0011 0000 01101110 /把把0000号寄存器中的数存入地址为号寄存器中的数存入地址为01101110的内存单元中的内存单元中45.5.2 5.5.2 汇编语言汇编语言汇编语言的特点汇编语言的特点 由助记符指令构成的语言。由助记符指令构成的语言。也是一种依附于机器硬件的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。汇编语言源程序需要汇编后才能执行。汇编语言程序片段汇编语言程序片段 MOV R5,X /把内存单元把内存单元X中的数装入中的数装入R5寄存器寄存器 ADD R5,Y /把把R5中的数与中的数与Y单元中的数相加，结果存入单元中的数相加，结果存入R5 MOV Z,R5 /把把R5中的数存入中的数存入Z单元中单元中 55.5.3 5.5.3 高级语言高级语言高级语言的特点高级语言的特点 由自然语言和数学公式表示的语言。由自然语言和数学公式表示的语言。是一种独立于机器硬件的语言。是一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。高级语言程序需要编译后才能执行。高级语言程序片段高级语言程序片段 Z=X+Y /把内存单元把内存单元X中的数与中的数与Y中的数相加，结果存入中的数相加，结果存入Z单元单元 65.5.3 5.5.3 高级语言高级语言常用高级语言常用高级语言 FORTRAN语言语言FORTRAN是是FORmula TRANslator（公式翻译器）的缩写。（公式翻译器）的缩写。主要用于复杂的科学计算领域。主要用于复杂的科学计算领域。ALGOL语言语言ALGOL是是ALGOrithm Language（算法语言）的缩写。（算法语言）的缩写。主要用于数学与科学计算。主要用于数学与科学计算。7高级语言高级语言常用高级语言常用高级语言 COBOL语言语言 COBOL是是COmmon Business-Oriented Language（面向商（面向商业的通用语言）的缩写。业的通用语言）的缩写。主要用于企业管理和事务处理。主要用于企业管理和事务处理。BASIC语言语言 BASIC是是Beginners All-purpose Symbolic Instruction Code（初学者通用符号指令码）的缩写。（初学者通用符号指令码）的缩写。主要用于初学者和较小规模的程序开发。主要用于初学者和较小规模的程序开发。85.5.4 5.5.4 结构化程序设计语言结构化程序设计语言早期程序设计方法的不足早期程序设计方法的不足注重功能的实现注重功能的实现/注重内存的节省注重内存的节省/注重执行效率的提高。注重执行效率的提高。不注重程序结构的清晰性。不注重程序结构的清晰性。不注重程序的可理解性和可修改性。不注重程序的可理解性和可修改性。结构化程序设计语言的特点结构化程序设计语言的特点 注重程序结构的清晰性。注重程序结构的清晰性。注重程序的可理解性和可修改性。注重程序的可理解性和可修改性。采用模块化程序设计方法。采用模块化程序设计方法。95.5.4 5.5.4 结构化程序设计语言结构化程序设计语言常用结构化程序设计语言常用结构化程序设计语言 PASCAL语言语言 是在是在ALGOL语言的基础上发展起来的。语言的基础上发展起来的。以法国著名科学家帕斯卡的名字命名。以法国著名科学家帕斯卡的名字命名。严格的语法格式与结构化形式。严格的语法格式与结构化形式。C语言语言 是在是在ALGOL60语言的基础上发展起来的。语言的基础上发展起来的。兼具低级语言和高级语言的特点。兼具低级语言和高级语言的特点。是最为流行的程序设计语言之一。是最为流行的程序设计语言之一。105.5.5 5.5.5 面向对象程序设计语言面向对象程序设计语言结构化程序设计方法的不足结构化程序设计方法的不足 面向过程的设计方法与人们习惯的思维方式仍然存在面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离，所以很难自然、准确地反映真实世界，一定的距离，所以很难自然、准确地反映真实世界，因而用编写出来的程序，特别是规模比较大的程序，因而用编写出来的程序，特别是规模比较大的程序，其质量是难以保证的。其质量是难以保证的。强调了要实现功能的操作方法（模块），而被操作的强调了要实现功能的操作方法（模块），而被操作的数据（变量）处于实现功能的从属地位，即程序模块数据（变量）处于实现功能的从属地位，即程序模块和数据结构是松散地耦合在一起，当程序复杂度较高和数据结构是松散地耦合在一起，当程序复杂度较高时，容易出错，而且错误难以查找和修改。时，容易出错，而且错误难以查找和修改。115.5.5 5.5.5 面向对象程序设计语言面向对象程序设计语言面向对象程序设计语言的特点面向对象程序设计语言的特点 将问题分解为对象。将问题分解为对象。对象将自己的属性和方法封装成一个整体，供程序设对象将自己的属性和方法封装成一个整体，供程序设计者使用。计者使用。对象之间的相互作用则通过消息传递来实现。对象之间的相互作用则通过消息传递来实现。使人们对复杂系统的认识过程与程序设计过程尽可能使人们对复杂系统的认识过程与程序设计过程尽可能一致。一致。125.5.5 5.5.5 面向对象程序设计语言面向对象程序设计语言常用面向对象程序设计语言常用面向对象程序设计语言 Simula 67 发布于发布于1967年，是面向对象语言的鼻祖。年，是面向对象语言的鼻祖。C+发布于发布于1983年，是在年，是在C语言的基础上发展起来的。语言的基础上发展起来的。C+是得到广泛应用的一种面向对象语言。是得到广泛应用的一种面向对象语言。目前常用的版本有目前常用的版本有Visual C+,C#,Visual C+.Net等。等。Java发布于发布于1995年，适合于网络程序设计。年，适合于网络程序设计。也是目前得到广泛应用的一种面向对象程序设计语言。也是目前得到广泛应用的一种面向对象程序设计语言。135.5.6 5.5.6 可视化程序设计语言可视化程序设计语言可视化程序设计语言的特点可视化程序设计语言的特点 以图形化的编程方式将面向对象技术的特性体现出来。以图形化的编程方式将面向对象技术的特性体现出来。使开发软件这一原本枯燥、难以理解的工作变得相对使开发软件这一原本枯燥、难以理解的工作变得相对轻松快捷。轻松快捷。常用可视化程序设计语言常用可视化程序设计语言Visual C+功能强大，比较适合专业人员使用。功能强大，比较适合专业人员使用。Visual Basic易于学习和掌握，比较适合非专业人员和初学者使用。易于学习和掌握，比较适合非专业人员和初学者使用。14155.5.7 5.5.7 人工智能程序设计语言人工智能程序设计语言人工智能程序设计语言的特点人工智能程序设计语言的特点 适合于知识表示和逻辑推理。适合于知识表示和逻辑推理。常用人工智能程序设计语言常用人工智能程序设计语言 LISP LISP是是LISt Processing（表处理）的缩写。（表处理）的缩写。可以解决人工智能中的符号处理问题。可以解决人工智能中的符号处理问题。PROLOG 是是PROgramming in LOGic（逻辑程序设计）的缩写。（逻辑程序设计）的缩写。自动实现模式匹配、自动回溯这两种人工智能中常用的基本操自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。作。165.5.8 5.5.8 C C语言程序设计语言程序设计C语言的主要特点语言的主要特点简洁、紧凑、灵活。简洁、紧凑、灵活。语法限制不太严格，使用方便灵活；数语法限制不太严格，使用方便灵活；数据结构描述能力及表达式能力强；程序书写形式自由。据结构描述能力及表达式能力强；程序书写形式自由。模块化、结构化。模块化、结构化。用语言编写程序层次清晰，便于按模块组用语言编写程序层次清晰，便于按模块组织程序，易于实现程序的结构化。织程序，易于实现程序的结构化。功能强大。功能强大。C语言除了能实现一般的高级语言的功能外，还能语言除了能实现一般的高级语言的功能外，还能实现汇编语言的大部分功能，兼具高级语言和低级语言的特点。实现汇编语言的大部分功能，兼具高级语言和低级语言的特点。可移植性好。可移植性好。C语言程序可以容易地移植到不同型号计算机、语言程序可以容易地移植到不同型号计算机、不同操作系统环境下执行。不同操作系统环境下执行。17C C语言程序设计语言程序设计C语言的基本要素语言的基本要素C语言的数据类型语言的数据类型 C语言的运算符及表达式语言的运算符及表达式 C语言语句语言语句 C语言程序的三种基本结构及实现语言程序的三种基本结构及实现 程序设计风格程序设计风格 算法设计与分析算法设计与分析181.1.C C语言的基本要素语言的基本要素C语言的基本词法语言的基本词法字符集字符集英文字母英文字母/数字数字/特殊字符特殊字符/转义字符。转义字符。标识符标识符C语言中各种对象的名字用标识符表示。语言中各种对象的名字用标识符表示。标识符是由字母、数字和下划线三种字符构成的且标识符是由字母、数字和下划线三种字符构成的且第一个字符必须是字母或下划线的字符序列。第一个字符必须是字母或下划线的字符序列。标识符分为三类标识符分为三类 关键字关键字/预定义标识符预定义标识符/用户标识符。用户标识符。192.2.C C语言的基本要素语言的基本要素常量常量在程序的执行过程中其值不能被改变的量。在程序的执行过程中其值不能被改变的量。数值型常量数值型常量 整型常量整型常量/浮点型常量（实型常量）。浮点型常量（实型常量）。字符型常量字符型常量字符常量字符常量/字符串常量。字符串常量。变量变量在程序运行过程中，其值可以被改变的量。在程序运行过程中，其值可以被改变的量。一般要先定义，再使用，变量定义的一般形式为：一般要先定义，再使用，变量定义的一般形式为：数据类型名数据类型名 变量名；变量名；20C C语言的数据类型语言的数据类型基本数据类型基本数据类型整型整型整型变量的定义形式为：整型变量的定义形式为：int 变量名；变量名；实型实型实型变量的定义形式为：实型变量的定义形式为：float 变量名；变量名；字符型字符型字符型变量的定义格式为：字符型变量的定义格式为：char 变量名；变量名；构造数据类型构造数据类型数组数组/结构体结构体/共用体共用体/枚举类型枚举类型/用户自定义类型。用户自定义类型。指针类型指针类型在动态数据结构及其应用中有着不可替代的作用。在动态数据结构及其应用中有着不可替代的作用。213.3.C C语言的运算符及表达式语言的运算符及表达式算术运算符算术运算符,*,/,%（求余数）。（求余数）。赋值运算符赋值运算符在在C语言中，语言中，称为赋值运算符，其使用形式为：称为赋值运算符，其使用形式为：变量名变量名 表达式表达式自增、自减运算符自增、自减运算符+是自增运算符，其功能是使变量的值增是自增运算符，其功能是使变量的值增1。-是自减运算符，其功能是使变量的值减是自减运算符，其功能是使变量的值减1。关系运算符关系运算符大小判断大小判断（大于）（大于）/（大于等于）（大于等于）/（小于）（小于）/（小于等于）。（小于等于）。相等判断相等判断（等于）（等于）/!（不等于）。（不等于）。224.4.C C语言语句语言语句控制语句控制语句 用于实现一定的控制功能。用于实现一定的控制功能。条件语句：用于实现程序执行过程中的条件转移。条件语句：用于实现程序执行过程中的条件转移。循环语句：用于实现程序中重复进行某些操作。循环语句：用于实现程序中重复进行某些操作。复合语句复合语句由一对花括号由一对花括号 括起来的一组语句。括起来的一组语句。如果要在只执行一条语句的地方执行多条语句，那么如果要在只执行一条语句的地方执行多条语句，那么这多条语句要写成一条复合语句。这多条语句要写成一条复合语句。235 5.C 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);/*输出面积的输出面积的值值*/24C C语言语言程序的三种基本结构程序的三种基本结构分支结构分支结构根据逻辑条件的成立与否，分别选择执行不同的处理。根据逻辑条件的成立与否，分别选择执行不同的处理。if语句：语句：if（表达式）（表达式）语句语句if-else语句：语句：if（表达式）语句（表达式）语句1 else 语句语句225C 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*/26C C语言程序的三种基本结构语言程序的三种基本结构循环结构循环结构根据循环条件的变化，决定是否继续重复执行某些语根据循环条件的变化，决定是否继续重复执行某些语句。句。for循环语句的格式为：循环语句的格式为：for（表达式（表达式1；表达式；表达式2；表达式；表达式3）循环体语句循环体语句 27C 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);/*输出累加结果输出累加结果*/286.6.程序设计风格程序设计风格主要体现在主要体现在5个方面个方面标识符的命名要风格统一、见名知义。标识符的命名要风格统一、见名知义。一般一行写一条语句，一条长语句可以写在多行上，一般一行写一条语句，一条长语句可以写在多行上，但尽量不要把多条语句写在一行上。但尽量不要把多条语句写在一行上。采用缩进格式，即同一层次的语句要对齐，低层次的采用缩进格式，即同一层次的语句要对齐，低层次的语句要缩进若干个字符，增加程序的可读性。语句要缩进若干个字符，增加程序的可读性。适当书写注释信息，有助于阅读者对程序的理解。适当书写注释信息，有助于阅读者对程序的理解。尽量少用尽量少用goto语句，否则容易导致程序结构混乱。语句，否则容易导致程序结构混乱。297 7.算法设计与分析算法设计与分析用计算机解决问题的步骤用计算机解决问题的步骤分析问题、设计算法。分析问题、设计算法。选定语言、编写源程序。选定语言、编写源程序。对源程序进行编译生成目标文件。对源程序进行编译生成目标文件。对目标文件进行连接操作，生成可执行的程序。对目标文件进行连接操作，生成可执行的程序。调试执行可执行程序。调试执行可执行程序。30算法算法设计与分析设计与分析程序与算法程序与算法算法是指为解决某一问题而采取的方法和步骤。算法是指为解决某一问题而采取的方法和步骤。程序是程序设计人员编写的、计算机能够理解并执行程序是程序设计人员编写的、计算机能够理解并执行的命令集合，是算法在计算机中的实现。的命令集合，是算法在计算机中的实现。算法的特点算法的特点有穷性有穷性/确定性确定性/有效性有效性/输入及输出。输入及输出。算法的表示算法的表示自然语言自然语言/流程图流程图/伪码。伪码。算法的评价标准算法的评价标准正确性正确性/时间复杂度时间复杂度/空间复杂度空间复杂度/可理解性。可理解性。315.6 5.6 数据结构数据结构概念和术语概念和术语线性结构线性结构树形结构树形结构图状结构图状结构325.6.1 5.6.1 概念和术语概念和术语数据数据描述客观事物的数、字符以及所有能输入到计算机并被计算机程序处理的符号的集合，如数值、字符、图形、图像、声音等。数据项数据项数据不可分割的最小单位。数据不可分割的最小单位。数据元素数据元素数据的基本单位，具有完整、确定的实际意义。一般由若干数据的基本单位，具有完整、确定的实际意义。一般由若干数据项组成。数据项组成。数据对象数据对象具有相同性质的数据元素的集合，是数据的一个子集。具有相同性质的数据元素的集合，是数据的一个子集。数据结构数据结构带有结构的数据元素的集合，结构反映了数据元素相互之间存在的某种联系。335.6.1 5.6.1 概念和术语概念和术语数据的逻辑结构数据的逻辑结构描述的是数据元素之间的逻辑关系。描述的是数据元素之间的逻辑关系。数据的物理结构数据的物理结构数据在计算机中的表示，包括数据元素的表示及数据数据在计算机中的表示，包括数据元素的表示及数据元素间关系的表示。元素间关系的表示。顺序存储顺序存储逻辑上相邻的元素存储在物理位置也相邻的存储单元中。逻辑上相邻的元素存储在物理位置也相邻的存储单元中。链式存储链式存储逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。逻辑关系通过附设的指针字段来表示。345.6.2 5.6.2 线性结构线性结构线性结构的特点线性结构的特点数据元素之间存在着一对一的关系数据元素之间存在着一对一的关系。每个每个元素元素有且只有一个前驱（第一个有且只有一个前驱（第一个元素元素除外）除外）。每个每个元素元素有且只有一个后继（最后一个有且只有一个后继（最后一个元素元素除外）。除外）。应用示例应用示例一维数组一维数组二维数组二维数组355.6.2 5.6.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称为这个根结点的子树。称为这个根结点的子树。395.6.3 5.6.3 树形结构树形结构二叉树的定义二叉树的定义二叉树是有限个结点的集合，该集合或者为空、或者二叉树是有限个结点的集合，该集合或者为空、或者由一个称为根的结点及两个不相交的、被分别称为左由一个称为根的结点及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。叉树为空二叉树。满二叉树满二叉树：在二叉树中，如果所有分支结点都存在左子树和右：在二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。作满二叉树。完全二叉树完全二叉树：一棵深度为：一棵深度为k的有的有n个结点的二叉树，对树中的个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为结点按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的结点与满二叉树中编号为）的结点与满二叉树中编号为i的结点在二叉树中的的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。位置相同，则这棵二叉树称为完全二叉树。405.6.3 5.6.3 树形结构树形结构二叉树示例二叉树示例满二叉树满二叉树完全二叉树完全二叉树非完全二叉树非完全二叉树415.6.3 5.6.3 树形结构树形结构图5.7 满二叉树8DHIEJKFLGBCA2345679101112M13OP1415图5.8 完全二叉树18DHIEJKFLGBCA2345679101112二叉树的存储二叉树的存储 顺序存储结构顺序存储结构用一组连续的存储单元（数组）用一组连续的存储单元（数组）存放二叉树中的结点。一般是存放二叉树中的结点。一般是按照二叉树结点从上至下、从按照二叉树结点从上至下、从左到右的顺序存储。左到右的顺序存储。完全二叉树和满二叉树采用顺完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序存储比较合适，树中结点的序号可以唯一地反映出结点之序号可以唯一地反映出结点之间的逻辑关系，这样既能够最间的逻辑关系，这样既能够最大可能地节省存储空间，又可大可能地节省存储空间，又可以利用数组元素的下标值确定以利用数组元素的下标值确定结点在二叉树中的位置以及结结点在二叉树中的位置以及结点之间的关系。点之间的关系。425.6.3 5.6.3 树形结构树形结构二叉树的存储二叉树的存储 链式存储结构链式存储结构用链表来表示一棵二用链表来表示一棵二叉树。链表中每个结叉树。链表中每个结点由三个域组成，除点由三个域组成，除了数据域外，还有两了数据域外，还有两个指针域，分别用来个指针域，分别用来给出该结点的左子结给出该结点的左子结点和右子结点所在的点和右子结点所在的链结点的存储地址。链结点的存储地址。非完全二叉树的链式存储非完全二叉树的链式存储435.6.3 5.6.3 树形结构树形结构树的应用树的应用用于分类的决策树。用于分类的决策树。用于各种比赛的博弈树。用于各种比赛的博弈树。有有7根火柴，甲乙两人依次从中取走根火柴，甲乙两人依次从中取走1根或根或2根，但不能不取，根，但不能不取，取走最后一根火柴的就是获胜者。取走最后一根火柴的就是获胜者。可以用二叉树来解。可以用二叉树来解。445.6.4 5.6.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)表示图中的一条边。表示图中的一条边。455.6.4 5.6.4 图状结构图状结构图的示例图的示例图的存储图的存储邻接矩阵邻接矩阵用矩阵表示图中各顶点之间的邻接关系，有边相连对应的矩阵用矩阵表示图中各顶点之间的邻接关系，有边相连对应的矩阵元素值为元素值为1，否则为，否则为0。465.6.4 5.6.4 图状结构图状结构图的存储图的存储邻接表邻接表一种顺序存储与链式存储结合的存储方法。对于图一种顺序存储与链式存储结合的存储方法。对于图G中的每个中的每个顶点顶点vi，将所有邻接于，将所有邻接于vi的顶点的顶点vj链成一个单链表，这个单链链成一个单链表，这个单链表就称为顶点表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表。组中，就构成了图的邻接表。475.6.4 5.6.4 图状结构图状结构图的应用图的应用求最短路径求最短路径网络性能分析网络性能分析48495.7 5.7 编译原理编译原理编译程序概述编译程序概述词法分析词法分析语法分析语法分析中间代码生成中间代码生成中间代码优化中间代码优化目标代码生成目标代码生成编译程序的开发编译程序的开发50515.7.1 5.7.1 编译程序概述编译程序概述高级语言的特点高级语言的特点简单易学，易于编写和修改程序。简单易学，易于编写和修改程序。编写出的源程序不能直接执行。编写出的源程序不能直接执行。编译程序编译程序把用高级语言编写的源程序翻译成等价的机器语言程把用高级语言编写的源程序翻译成等价的机器语言程序的翻译程序。序的翻译程序。学习编译知识的作用学习编译知识的作用深入理解高级语言程序设计。深入理解高级语言程序设计。有助于提高程序设计能力和培养程序设计思维。有助于提高程序设计能力和培养程序设计思维。525.7.2 5.7.2 词法分析词法分析词法分析的主要任务词法分析的主要任务从源程序中识别出单词。从源程序中识别出单词。发现词法错误并指出错误位置。发现词法错误并指出错误位置。以某种机内符的形式表示单词。以某种机内符的形式表示单词。单词种类单词种类基本字：也称关键字，如基本字：也称关键字，如C语言中的语言中的for、do、while等；等；标识符：用来表示各种名字的符号串，如变量名、函数名等；标识符：用来表示各种名字的符号串，如变量名、函数名等；常数：各种类型的常数，如整数、实数、字符串等；常数：各种类型的常数，如整数、实数、字符串等；运算符：各种算术运算、关系运算符，如运算符：各种算术运算、关系运算符，如+、-、=等；等；界限符：如逗号（，）、分号（；）等。界限符：如逗号（，）、分号（；）等。535.7.3 5.7.3 语法分析语法分析语法分析的主要任务语法分析的主要任务确认作为词法分析结果的单词序列是否为给定语言的确认作为词法分析结果的单词序列是否为给定语言的一个正确程序。一个正确程序。给定语言用文法表示，如果给定的单词串能够识别成给定语言用文法表示，如果给定的单词串能够识别成该文法的句子，则认为程序是正确的，否则认为程序该文法的句子，则认为程序是正确的，否则认为程序是错误的。是错误的。自顶向下分析方法自顶向下分析方法/自底向上分析方法。自底向上分析方法。调用语义子程序进行语义处理。调用语义子程序进行语义处理。审查每个语法结构的静态语义，即确认语法结构合法的程序是审查每个语法结构的静态语义，即确认语法结构合法的程序是否真正有意义。否真正有意义。545.7.4 5.7.4 中间代码生成中间代码生成中间代码生成的主要任务中间代码生成的主要任务以某种便于计算机处理的形式表示程序。以某种便于计算机处理的形式表示程序。引入中间代码的优点引入中间代码的优点使编译程序结构在逻辑上更为简单明确。使编译程序结构在逻辑上更为简单明确。可以将与机器相关的某些实现细节置于代码生成阶段可以将与机器相关的某些实现细节置于代码生成阶段仔细处理。仔细处理。使得计算和代码优化比较容易实现。使得计算和代码优化比较容易实现。常用的中间代码形式常用的中间代码形式逆波兰式逆波兰式/三元式三元式/四元式。四元式。555.7.4 5.7.4 中间代码生成中间代码生成逆波兰式计算的优点逆波兰式计算的优点a+bc的逆波兰式形式为的逆波兰式形式为abc+。对于逆波兰式对于逆波兰式abc+，计算机先扫描到运算对象，计算机先扫描到运算对象a、b和和c，然，然后扫描到运算符，先计算后扫描到运算符，先计算bc（假定结果为（假定结果为t），继续扫描），继续扫描到运算符到运算符+，再计算，再计算a+t，从而完成，从而完成a+bc的计算。的计算。无论表达无论表达式多复杂，只一遍扫描就能完成表达式的计算。式多复杂，只一遍扫描就能完成表达式的计算。对于一般表达式对于一般表达式a+bc，计算机先扫描到运算对象，计算机先扫描到运算对象a，然后扫，然后扫描到运算符描到运算符+和运算对象和运算对象b，由于不知道后面的运算符是什么，由于不知道后面的运算符是什么，不能决定是否先完成不能决定是否先完成+的运算，继续扫描到运算符和运算对的运算，继续扫描到运算符和运算对象象c，知道的优先级高，先计算，知道的优先级高，先计算bc（假定结果为（假定结果为t），再往），再往回扫描计算回扫描计算a+t。对于比较复杂的表达式，可能需要多次来回对于比较复杂的表达式，可能需要多次来回扫描表达式，才能完成计算，这会很浪费时间。扫描表达式，才能完成计算，这会很浪费时间。565.7.5 5.7.5 中间代码优化中间代码优化中间代码优化的主要任务中间代码优化的主要任务对中间代码进行等价变换。对中间代码进行等价变换。变换后的代码运行结果与变换前运行结果相同。变换后的代码运行结果与变换前运行结果相同。运行效率提高（速度提高或运行效率提高（速度提高或/和占用存储空间减少）。和占用存储空间减少）。常用的优化技术常用的优化技术删除多余运算删除多余运算/代码外提代码外提/强度削弱。强度削弱。变换循环控制条件变换循环控制条件/合并已知量与复写传播。合并已知量与复写传播。删除无用赋值。删除无用赋值。575.7.6 5.7.6 目标代码生成目标代码生成目标代码生成的主要任务目标代码生成的主要任务把经过优化后的中间代码转换成特定机器的机器语言把经过优化后的中间代码转换成特定机器的机器语言程序或汇编语言程序。程序或汇编语言程序。由于一个高级语言源程序的目标代码需多次使用，因由于一个高级语言源程序的目标代码需多次使用，因此代码生成器的设计要着重考虑目标代码的质量。此代码生成器的设计要着重考虑目标代码的质量。目标代码的质量主要从占用空间和执行时间两个方面目标代码的质量主要从占用空间和执行时间两个方面综合考虑。综合考虑。585.7.7 5.7.7 编译程序的开发编译程序的开发编译程序的特点编译程序的特点一个相当复杂的系统软件。一个相当复杂的系统软件。编译程序的自动生成编译程序的自动生成主要是主要是语义分析语义分析和和优化优化问题。问题。完全自动生成编译程序，目前还不现实。完全自动生成编译程序，目前还不现实。595.8 5.8 软件工程软件工程软件开发的复杂性软件开发的复杂性软件工程的基本原则软件工程的基本原则软件开发方法软件开发方法系统分析系统分析系统设计系统设计系统实施系统实施系统运行与维护系统运行与维护应用工程化方法来开发大型软件，以保证软件开发的质量和效率。605.8.1 5.8.1 软件开发的复杂性软件开发的复杂性软件危机软件危机 软件开发成本和开发进度的估计往往很不准确。软件开发成本和开发进度的估计往往很不准确。用户对用户对“已完成已完成”的软件系统不满意的现象经常发生。的软件系统不满意的现象经常发生。软件产品的质量往往不可靠。软件产品的质量往往不可靠。软件没有适当的文档资料。软件没有适当的文档资料。软件通常是不可维护的。软件通常是不可维护的。软件工程软件工程采用工程的概念、原理、技术和方法来开发和维护软采用工程的概念、原理、技术和方法来开发和维护软件。件。61软件开发软件开发的复杂性的复杂性复杂性的表现复杂性的表现开发环境的复杂性开发环境的复杂性用户需求的多样性用户需求的多样性技术手段的综合性技术手段的综合性计算机硬件和软件技术。计算机硬件和软件技术。数据通信与网络技术。数据通信与网络技术。数据采集与存储技术。数据采集与存储技术。多媒体技术。多媒体技术。625.8.2 5.8.2 软件工程的基本原则软件工程的基本原则B.W.Boehm总结的总结的7条基本原则条基本原则用分阶段的生命周期计划进行严格的管理。用分阶段的生命周期计划进行严格的管理。坚持进行阶段评审。坚持进行阶段评审。实行严格的产品控制。实行严格的产品控制。采用现代程序设计技术。采用现代程序设计技术。结果应能清楚地审查结果应能清楚地审查 。开发小组的人员应该少而精。开发小组的人员应该少而精。承认不断改进软件工程实践的必要性。承认不断改进软件工程实践的必要性。635.8.3 5.8.3 软件开发方法软件开发方法生命周期法生命周期法含义含义：将整个软件的开发过程分解成若干个阶段，并：将整个软件的开发过程分解成若干个阶段，并对每个阶段的目标、任务、方法作出规定，使整个软对每个阶段的目标、任务、方法作出规定，使整个软件的开发过程具有合理的组织和科学的秩序。件的开发过程具有合理的组织和科学的秩序。生命周期的四个主要阶段生命周期的四个主要阶段系统分析系统分析/系统设计系统设计/系统实施系统实施/系统运行与维护。系统运行与维护。遵循的原则遵循的原则用户参与的原则用户参与的原则/先逻辑后物理的原则。先逻辑后物理的原则。自顶向下的原则自顶向下的原则/工作成果描述标准化原则。工作成果描述标准化原则。64软件开发软件开发方法方法快速原型法快速原型法含义含义：以少量代价快速地构造一个可执行的软：以少量代价快速地构造一个可执行的软件系统，使用户和开发人员可以较快地确定需件系统，使用户和开发人员可以较快地确定需求。求。需求规格原型。需求规格原型。渐进原型。渐进原型。65软件开发软件开发方法方法面向对象法面向对象法 含义含义：把数据和对数据的操作同等看待，是一把数据和对数据的操作同等看待，是一种以数据为主线，把数据和对数据的操作紧密种以数据为主线，把数据和对数据的操作紧密结合起来的方法。结合起来的方法。主要特点主要特点把对象作为融合了数据及在数据上的操作行为的统把对象作为融合了数据及在数据上的操作行为的统一软件构件，用对象分解取代了结构化方法的功能一软件构件，用对象分解取代了结构化方法的功能分解。分解。把所有对象都划分为类。每个类定义了一组数据和把所有对象都