计算机科学导论.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章,计算机系统的软件,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,3,章,计算机系统的软件,本章要点与学习要求：,计算机软件概念、分类 （熟悉）,程序设计语言 （了解）,数据结构的定义、分类 （熟悉）,编译原理的过程 （掌握）,操作系统的分类、功能 （掌握）,软件工程的生命周期、模型（熟悉）,教学章节,计算机软件概述,3.1,算法与数据结构,3.2,程序设计语言,3.3,编译原理,3.5,操作系统,3.6,软件工程,3.7,数据库系统,3.4,教学目的,本讲主要介绍计算机软件的基本概念,对计算机软件有总体上了解,教学重点与难点,软件定义,软件分类,计算机系统的组成,3.1,计算机软件概述,教学,引入,在第二章，我们学习了计算机的内部组成，那么是谁控制这些硬件让它为我们服务？,返 回,下一页,程序作为商品以有形介质为载体进行交易,称做软件。即软件是指为运行、维护、管理及应用计算机所编制的所有程序及其文档资料的总和。,软件的特性：,软件是功能、性能相对完备的程序系统,软件是具有使用性能的软设备,软件是信息商品,软件是一种只有过时而无,“,磨损,”,的商品,3.1.1,什么是软件,P106,上一页,返 回,下一页,系统软件：软件制售商为释放硬件潜能、方便使用而配备的软件。,OS,、语言编译,/,解释系统、网络软件、数据库管理软件、各种服务程序、界面工具箱等支持计算机正常运作和,“,通用,”,的软件。,应用软件：指解决某一应用领域问题的软件。,财会软件、通信软件、科技计算软件、,CAD/CAM,软件等。,3.1.2,软件的分类,P107,上一页,返 回,下一页,三类软件的关系,上一页,返 回,下一页,常用软件,操作,系统,群件,系统,办公,软件,系统工,具软件,管理计算机系统的软硬件资料，合理地组织计算机工作流程，并为用户使用计算机提供良好的工作环境。如,Windows,等。,一类日常办公的软件，如,Office,编程语言一般是以一个集成环境的形式出现的。如：,Visual Stutio,。,可以帮助操作系统更有效地完成系统的管理和维护。如反病毒软件,程序开,发工具,Internet,工具软件,多媒体,处理,数据库,是信息管理的中心，如,Access,、,SQL Server,一种基于电子邮件的应用系统软件，它拓宽了电子邮件的内涵，涵养了很多通信协作功能。如,Notes,、,Exchange Server,、,Group Wise,在,CPU,一级提供多媒体指令，实现对多媒体的直接支持。,基于网络环境和,Internet,环境的应用软件，如,Web,服务器、,FTP,上一页,返 回,下一页,3.1.4,计算机系统的组成,P108-109,上一页,返 回,下一页,计算机系统的体系结构,上一页,返 回,下一页,软件概念；,软件分类；,计算机系统的组成；,P194 1,、,2,教 学 小 结,作 业,返 回,上一页,教学目的,本讲主要介绍算法和数据结构的基本概念，以及几种常用的数据结构,教学重点与难点,1.,算法的基本概念,2.,线性表,3.,栈,4.,队列,5.,树,3.2,算法与数据结构,教学,引入,计算机内部有很多数据需要我们处理，那么计算机是按照什么形式处理这些数据的？,返 回,下一页,典型问题,排序问题,汉诺塔问题,n,皇后问题,旅行商问题,问题类型,排序,查找,串处理,图问题,组合问题,几何问题,数值问题,3.2.1,为什么要学习算法与数据结构,上一页,返 回,下一页,问题的描述,建立数学模型,算法设计,算法的正确性证明,算法分析,算法的程序实现,2.,计算机求解问题的过程,上一页,返 回,下一页,算法,+,数据结构,=,程序,对算法的研究主要包括两方面内容：,一是如何设计算法，常用的算法设计方法有分治递归、贪心法、回溯法、动态规划、分支限界等；,二是对给定算法，如何分析它的效率和性能。,数据的结构分为逻辑结构和物理结构,逻辑结构反映数据成员之间的逻辑关系,物理结构反映数据成员在计算机内部的存储安排。,3.,学习算法与数据结构的意义,上一页,返 回,下一页,算法概念,算法原意指计算步骤或规则,在计算机科学中，算法指用计算机求解某一问题的方法,算法特征,有穷性（,Finiteness,）,确定性（,Definiteness,）,有效性（,Effectiveness,）,有,0,个或多个输入项,至少有一个输出项,3.2.2,算法基础,P113,上一页,返 回,下一页,算法描述,自然语言描述,流程图描述,伪代码描述,算法结构,顺序结构,选择（分支）结构,循环结构,3.2.2,算法基础 （序）,上一页,返 回,下一页,算法设计方法,递归技术,分治法,贪心算法,回溯法,动态规划法,算法分析,时间复杂性指一个算法在计算机上运算所花费的时间,空间复杂性指一个算法在计算机上运算所花费的空间,3.2.2,算法基础 （序）,上一页,返 回,下一页,书 名,作者名,登录号,分类号,出版年月,计算机病毒危机,相杰超,920253,TP306/10,92.5,实用数据结构,霍义兴,871470,TP31/71,87.1,计算机系统结构,苏东庄,841153,TP303/12,84.1,数字逻辑,王玉龙,875027,TP315/20,87.5,例子：图书书目表,P122,上一页,返 回,下一页,数据,定义：一切可输入计算机并能为计算机所处理的描述客观事物的符号，称为数据。在计算机中，数据的定义是广泛的，数、字符、图形、声音都可是计算机处理的对象，统称为数据,分类,数值数据：,应用于科学计算的程序，它们的组织较为简单，如变量，数组，简单表等。关心的是计算速度与精度。,非数值数据：,应用于商业或管理的程序，它们组织较为复杂，关心的是按什么规则组织数据，使其占空间少，存取快，并有利于维护（增删、修改）,3.2.3,数据结构基础,P121,数据结构就是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科。,上一页,返 回,下一页,数据类型：,数据的定义域。常见的数据类型有字符型、整数型、逻辑型、数组、集合、记录等。,数据项（,date item,）：,是数据的,最小单位,。,数据元素（,date element,）,：是数据项的,集合,（或称,记录,）。,数据对象（,data object,）：,它是具有,相同特性,的,数据元素,的集合。如整数数据对象的集合。,结构（,data structure,）：,数据元素之间的相互关系。,数据结构（,data structure,）：,它是带有结构的,数据元素的集合,。数据结构是数据组织形式，反应数据之间的关系，但不涉及数据的具体内容。,1.,基本概念,P122,上一页,返 回,下一页,书 名,作者名,登录号,分类号,出版年月,计算机病毒危机,相杰超,920253,TP306/10,92.5,实用数据结构,霍义兴,871470,TP31/71,87.1,计算机系统结构,苏东庄,841153,TP303/12,84.1,数字逻辑,王玉龙,875027,TP315/20,87.5,数据项,数据元素,数 据,例子：图书书目表,数据的逻辑结构：,指数据元素之间的逻辑关系，它与数据在计算机中的存储方式无关。,线性结构。数据之间存在前后顺序关系，除第一个元素和最后一个元素外，其他结点都有唯一一个前驱和一个后继结点（一对一关系）。包括数组、链表、栈和队列等。,树形结构。数据之间存在顺序关系，除了一个根结点外，其他结点都有唯一一个前驱结点，且可以有多个后继结点（一对多关系）。,网状结构。每个结点都可以有多个前驱和多个后继结点（多对多关系）,3.2.3,数据结构（序）,上一页,返 回,下一页,数据的存储结构：指数据的逻辑结构到计算机存储器的映像。,顺序存储结构将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。它主要存储线性结构的数据。,结点之间的关系由物理相邻关系决定，结点中只有信息域，所以存储密度大，空间利用率高。,数据结构中第,i,个结点的存储地址可由以下公式求得,Li,L0,(i-1)k,插入、删除运算会引起相应结点的大量移动。,链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中。,结点中除数据外，还有表示链接信息的指针域，因此与顺序存储结构相比，占用更大的存储空间。,逻辑上相邻结点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构存储,插入、删除等操作灵活方便，不需要大量移动结点，只需修改结点的指针值即可,3.2.3,数据结构（序）,上一页,返 回,下一页,顺序存储结构,上一页,返 回,下一页,链式存储结构,上一页,返 回,下一页,定义,线性表（,Linear List,）是,n,个数据元素,的有限序列（,a,1,，,a,2,，,，,a,i,，,，,a,n,）。其中元素,a,i,可以是一个数、或是一个符号、也可以是更复杂的信息。,性质,同一线性表中的元素必定,属于同一类数据,对象,；,除,a,1,元素外，每个元素都,仅有一个直接前趋,；,除,a,n,元素外，每个元素都,仅有一个直接后继,；,各元素的,下标表示,了该元素在线性表中的,位置,。,2.,线性表,P123,上一页,返 回,下一页,数组。它是,n,个类型相同的数据元素构成的序列，它们连续存储在计算机的存储器中，且数组中的每个元素占据相同的存储空间。,对数组的描述通常包含下列,5,种属性,数组名称。声明数组第一个元素在内存中的起始位址。,维度。每一元素所含数据项的个数，如一维数组、二维数组等。,数组下标。元素在数组中的储存位置。,数组元素个数。是数组下标上限与数组下标下限的差,+1,。,数组类型。声明此数组的类型，它决定数组元素在内存所占有的空间大小。,2.,线性表 （序）,上一页,返 回,下一页,链表：它是,0,个或多个称为结点的元素构成的序列，每个结点除了存储数据外还包含一个或多个称为指针的链接，指向链表中其他元素。,2.,线性表 （序）,上一页,返 回,下一页,栈结构,定义：一种插入和删除操作都只能在尾端进行的线性表。允许插入和删除的一端，为变化的一端，称为栈顶,(Top),，另一端为固定的一端，称为栈底,(Bottom),。,特点：是一种后进先出,(LIFO),的线性表,也就是说，栈的操作是按后进先出,(LIFO,：,Last In First Out),的原则进行的。,栈的存储结构：,顺序存储：占有一片连续的存储空间,链式存储：也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。,栈的基本运算：,入栈（在栈的顶部插入元素）,出栈（删除栈顶元素）外,取栈顶位置上的元素,置为一个空栈,判定是否为空栈。,2.,线性表 （序）,重点,上一页,返 回,下一页,a,1,a,2,a,n-1,a,n,栈底,栈顶,入栈,出栈,入栈和出栈的动画演示,上一页,返 回,下一页,栈的顺序存储结构 栈的链式存储结构,上一页,返 回,下一页,队列定义：仅允许在一端进行插入，另一端进行删除的线性表，称为队列,(queue),。允许插入的一端称为队尾,(rear),，允许删除的一端称为队头,队列的特点：先进先出,(FIFO),。,队列的存储结构：,顺序结构,、,链式结构,队列的基本操作：,入队列,（在队列,Q,的队尾插入元素）；,出队列,（删除队列,Q,的队头元素）；,取,出队列,Q,的,队头元素,；,置,队列,Q,为一个,空,队列；,2.,线性表 （序）,上一页,返 回,下一页,顺序存储结构：,将队列中元素全部存入一个一维数组中,数组的低下标一端为队头,高下标一端为队尾，将这样的队列看成是顺序队列。若一维数组中所有位置上都被元素装满，称为队满，即尾指针,rear,指向一维数组最后,而头指针指向一维数组开头，称为队满。,链式存储结构：,称为链队列，可以用带头结点的单链表作为队列的链式存储结构。,front,A B C D E,rear,队列的存储结构,上一页,返 回,下一页,出队列,a1,a2,an,入队列,队头,队尾,入队列和出队列的动画演示,上一页,返 回,下一页,一个图,G,=,是一个数据结构，它由两部分组成：一个有限集合,V,，它的元素称为顶点；另一个有限集合,E,，它的元素由顶点对构成，称为边。如果每对顶点之间都没有顺序，也就是说，顶点对,(,u,，,v,),和顶点对,(,v,，,u,),是相同的，我们说图,G,是无向的，如图（,a,）所示。否则，称为有向的，边,的方向是从顶点,u,到达顶点,v,，如图（,b,）所示。,3.,图,上一页,返 回,下一页,3.,图（序）,上一页,返 回,下一页,邻接矩阵。,n,个顶点的邻接矩阵是一个,n,n,阶的布尔矩阵，用来表示图的结点间的相邻关系。,邻接表。是链表一个集合，其中每一个顶点用一个邻接链表表示，该链表包含了和这个顶点邻接的所有顶点（即所有和该顶点有边相连的顶点）,赋权图：图的每条边对应一个数值，在实际应用中这些数值往往是距离、运费、时间等。这些值称为边的权或成本。,邻接矩阵。当存在一条从结点,i,到结点,j,的边时，矩阵元素,a,ij,的值就是这条边的权重；当不存在这样一条边时，则用一个特殊符号,表示。,邻接表。邻接表的结点中不仅包含邻接结点的名字，还必须包含相应的边的权重。,4.,树,上一页,返 回,下一页,树和森林：连通无回路的图称为树，如图,a,所示。有的图虽然不是树，但它的每个子图（连通分支）是树，则称为森林，如图,b,所示。,树有两个性质：,树的边数,=,树的顶点数减,1,。,树的任意两个顶点之间有且仅有一条通路。,图,a,树示例 图,b,森林示例,4.,树（序）,上一页,返 回,下一页,根树：任选树的一个顶点，将它作为树的根。在对根树的描述中，根通常放在最顶上（树的第,0,层），与根邻接的顶点放在根的下面（第,1,层），再下面是和根距离两条边的顶点（第,2,层），然后依此类推。,内部结点与叶子结点：,除根结点外，有后继的结点称为内部结点,没有后继的结点称叶子结点（或树叶）,父结点与子结点：,某结点的上层结点称为它的父结点；,把其下层结点称为孩子结点,树的深度：,从根结点算起的树的层次。,树的高度：,是从根到叶结点的最长路径的长度。,上一页,返 回,下一页,5.,有序树,上一页,返 回,下一页,有序树：是一棵根树，树中每一顶点的所有子女都是有序的。,二叉树：有序树中所有顶点的子女个数都不超过两个的称为二叉树，并且每个子女不是父母的左子女就是父母的右子女。,分析：,根据顺序存储和链接存储的线性表优、缺点的分析，可以发现选项,C,中顺序存储的线性表便于进行增、删操作是不正确的，而本题恰好让我们选择错误的说法，则必是选项,C,无疑。,例,1,：下面关干线性表的叙述中，错误的是（）。,A,）线性表采用顺序存储，必须占用一片连续的存储单元,B,）线性表采用链接存储，不必占用一片连续的存储单元,C,）线性表采用顺序存储，便于进行插入和删除操作,D,）线性表采用链接存储，便于插入和删除操作,结论：答案应选,C,）,上一页,返 回,下一页,上一页,返 回,下一页,例,2,：求下列各图的相邻矩阵,教学小结,数据结构的基本概念,线性表,栈,队列,树,作 业,P195 7,、,9,、,10,、,13,、,15,。,返 回,上一页,计算机可以直接识别和执行，效率高,指令的二进制代码难记住，人工编写机器语言很繁琐，易出错,不同的计算机有不同的机器语言，因而通用性很差。,面向过程的第四代语言。如,SQL,、,PB,、,Delphi,。,面向对象的编程语言和网络语言，如,VB,、,VB,、,C+,、,HTML,和,Java,。,各种软件开发工具，如,CASE,不能为计算机硬件直接识别与执行，必须通过汇编器的系统软件,“,汇编,”,，才能被硬件执行。,汇编语言指令与机器语言指令一一对应，为低级语言,不同的计算机具有不同的汇编语言，记忆指令助记符较记忆指令二进制代码容易，但仍然繁琐。,用高级语言编写的源程序必须通过,“,翻译,”,生成目标程序，才能被计算机所执行。,不同计算机只要配备某种高级语言编译程序，可运行该高级语言源程序，通用性强,与一般的自然语言相比，具有严格、小巧、没有二义性特点,第一代,语言,第二代,语言,第三代,语言,第四代,语言,第五代,语言,智能化语言，如,PROLOG,3.3.1,程序设计语言发展概述,P129,重点,FORTRAN,COBOL,PASCAL,C,过程化编程语言,面向对象编程语言,面向人工智能的语言,专 用 语 言,常用程序设计语言,C+,Java,HTML,SQL,LISP,语言,Prolog,上一页,返 回,下一页,概述,面向过程的程序中，程序划分成一个主模块和若干个子模块。,数据公用,数据与代码相互分离,面向对象程序中，将数据以及处理这些数据的例程全部封装在一起形成一个类。,3.3.3,面向对象程序设计,P141,上一页,返 回,下一页,对象、类、方法,对象是相关数据和方法的结合体。各个对象既是独立的实体，又通过消息相互作用。,类是同种对象的集合与抽象。类是一种抽象的数据类型，它是所有具有一定共性的对象的抽象。,属于类的某一个对象则被称为是类的一个实例，是类的一次实例化的结果。,方法是对数据的一种操作。,对象、方法和消息,“消息”是程序语句实现的一个命令。,对象间的联系通过消息来完成。,方法可以通过外界发“消息”来激活。,面向对象的基本概念,P120,上一页,返 回,下一页,面向对象程,序语言特征,继承性,多态性,封装性,将数据和操作这些数据的方法代码组织到一起，即将数据和方法放在同一个对象中，可提高数据的安全性,一,个接口能够做多种用途，而其特定的用途由其特定的环境所决定,一个新类可以从现有的类中派生出来，新类具有父类中的所有特性，直接继承了父类的数据和方法,上一页,返 回,下一页,教学目的,对数据库系统作进一步的介绍，包括数据库系统特点、数据库管理系统的组成和分类，使大家对数据库系统有进一步的了解。,教学重点与难点,数据库创建,数据库操作,3.4,数据库管理系统,教学,引入,我们知道，计算机要处理大量的数据，那么计算机是如何保存这些数据？,返 回,下一页,数据库,DB,：相关信息或数据的有规则的集合。,数据库管理系统,DBMS,：一种数据库管理软件，其职能是维护数据库，接受并完成用户程序或命令提出的对数据进行输入、编辑、排序、检索、合并和输出等操作请求。,数据库系统：由数据库、数据库管理系统和用户组成,数据库系统的有关术语,P145,上一页,返 回,下一页,数据库图书馆,数据图书,外存书库,用户读者,数据模型书卡格式,数据库管理系统图书馆管理员,数据的物理组织方法 图书存放方法,用户对数据库的操作读者对图书馆的访问,（使用数据操纵语言对数据借书、还书等,检索、插入、删除、修改）,数据库系统与图书馆的比较,上一页,返 回,下一页,层次模型,满足的条件：,有一个记录类型没有父结点。,其它记录类型有且只有一个父结点。,3.4.2,数据模型,P146,上一页,返 回,下一页,网状模型,满足的条件：,有一个以上记录类型没有父结点。,至少有一个记录类型多于一个父结点,3.4.2,数据模型（序）,上一页,返 回,下一页,关系模型,满足的条件：,事物与事物之间的联系用二维表格的形式来描述。表中,每一行,是一个,记录,，在关系中称为,元组,；表中每,一列,是一个,字段,，在关系中称为,属性,。,3.4.2,数据模型（序）,上一页,返 回,下一页,基本概念：,表：,存储和管理数据的基本单元。它是一种格式化的二维数组。,字段：,二维表的每一列在关系中称为属性，每个属性都有一个属性名，属性值则是各个元组属性的取值。,字段类型：,字段的数据类型及其长度。,记录：,是一组相关数据项的集合，用于描述一个对象在某方面的属性。,主键：,能够,唯一确定,表中的一条记录的,一个或几个,字段。,外键：,关系中某个属性或属性组合并非主键，但却是另一个关系的主键，称此属性或属性组合为本关系的外部关键字。关系之间的联系是通过外部关键字实现的。,索引：,提供对数据项的快速访问。,关系数据库,上一页,返 回,下一页,学生与所在系的关系,系与负责人的关系,学生、课程与成绩的关系,学号,学生名,系名,940101,940202,940301,940401,李春梅,刘,力,陈文秀,徐,兵,计算机系,自动化系,机械系,化工系,学号,课程名,成绩,940101,940202,940301,940401,：,：,语言,：,：,：,：,系名,系主任名,计算机系,自动化系,机械系,化工系,郑,敏,李龙 江,金 剑,齐 晶,上一页,返 回,下一页,数据定义语言,DDL,：用来定义数据库的数据模型,数据操作语言：用来表达用户对数据库的操作请求。,查询数据库中的信息,向数据库插入新的信息,从数据库中删除信息,修改数据库中的信息,SQL,语言是一个通用型的、功能强大的关系数据库语言,数据定义语句：数据库的定义由,CREATE TABLE,、,ALTER TABLE,和,DROP TABLE3,种语句构成。,数据库查询是数据库的核心操作。,SQL,语言提供了,SELECT,语句进行数据库查询,数据更新语句的作用是在当前表中添加、删除和修改记录。包括,INSERT,、,DELETE,和,UPDATE,三条语句。,3.4.3,数据库语言,上一页,返 回,下一页,设计步骤,需求分析,概念结构设计,逻辑结构设计,物理结构设计,应用程序设计,系统运行与维护,3.4.4,数据库设计,上一页,返 回,下一页,常用数据库开发平台,Access,SQL Server,Visual FoxPro,Power Builder,Oracle,Sybase,3.4.4,数据库设计（序）,上一页,返 回,下一页,数据库,发展史,文件系统阶段,人工管理阶段,关系数据库系统,上一页,返 回,下一页,64,主要是指,50,年代中期以前的这段时间，此时的计算机还很简陋，连完整的操作系统都没有。因此，数据只能放在卡片上或其他介质上，由人来手工管理。,人工管理阶段,上一页,返 回,下一页,65,主要是指,50,年代后期到,60,年代中期的这段时间，此时的计算机已经有了操作系统。在操作系统基础之上建立的文件系统已经成熟并广泛应用。因此，人们自然想到用文件把大量的数据存储在磁盘这种介质上，以实现对数据的永久保存和自动管理以及维护；,文件系统阶段,上一页,返 回,下一页,66,与文件系统相比的优点,：,数据是结构化的,面向系统，减少了数据冗余,可以用数据结构化查询语言对数据库中的数据进行操作,关系数据库系统,上一页,返 回,下一页,XML/RDBMS,混合数据处理将在未来得到快速的发展,数据集成和数据仓库将向内容管理过渡,基于,Internet,的自动化管理,支持商业智能成重点,数据库技术与多学科技术的有机结合,2,数据库技术发展趋势,P154,上一页,返 回,下一页,分析：,在数据库系统阶段，数据的冗余度只能说明显减小了,节约了存储空间而没有完全消除，因此说“无数据冗余”不够准确。,例,3,：数据管理技术随着计算机技术的发展而发展。数据库阶段具有很多特点，但下面列出的特点中哪一个不是数据库阶段的特点？（）,A,）无数据冗余,B,）采用复杂的数据结构,C,）数据共享,D,）数据具有较高的独立性,结论：答案应选,A,）,上一页,返 回,下一页,数据库管理系统的分类,关系数据库,数据库的发展历史,现阶段常用数据库简介,数据库技术的新发展,P195 17,、,18,、,19,教 学 小 结,作 业,返 回,上一页,教学目的,介绍高级语言源程序是如何被计算机识别，对编译原理有大致了解,教学重点与难点,词法分析,语法分析,中间代码生成,代码优化,目标代码生成,表格管理和出错处理,3.5,编译原理,教学,引入,我们向计算机编写的代码如何被计算机识别？,返 回,下一页,编译程序,是实现将源程序“翻译”为目标程序的系统软件，它由若干个程序组成，故又称为,编译系统,。,翻译外文资料的大致过程：,识别单词,语法分析,初译,加工,高级语言程序（源程序,.C,）,C,语言编译器,连接装配程序,运行机器语言程序,目标程序,.obj,可执行程序,.exe,结果,上一页,返 回,下一页,词法分析：对源程序逐个字符地进行扫描，以识别出各个单词符号，并分别归类。,语法分析：根据程序设计语言的语法规则，将词法分析器所提供的单词符号串构成一个语法分析树。,语义分析：检查各句子的语法树。,中间代码的生成：向目标代码过度的一种编码，其形式尽可能和机器的汇编语言相似，以便于下一步的代码生成。,代码优化：对中间代码程序做局部或全局优化，可使最后生成的目标代码程序运行更快，占用存储空间更小。,目标代码生成：由代码生成器生成目标机器的目标代码程序，并完成数据分段、选定寄存器等工作，然后生成机器可执行的代码。,高级语言源程序的执行过程,重点,上一页,返 回,下一页,高级语言的单词属性的类型：,基本字（保留字）,标识符（如变量名、数组名、过程名等）,常数,运算符,+-*/,栈顶运算符，则将其,压入,运算符栈；,若当前运算符,栈顶运算符，则,弹出,栈顶运算符和操作数栈中的相应操作数，完成其运算，并把,计算结果压入操作数栈,中；,若当前运算符,=,栈顶运算符，则,弹出,运算符栈的栈顶符号，并,读入下一单词,，什么计算也不进行。,反复执行上述过程，直至句末符“,#”,，操作数栈中只剩下一个结果值，表明分析正确。否则出错。,算符优先分析法（具体算法,）,上一页,返 回,下一页,中间代码的定义,中间代码是一种结构简单、含义明确的记号系统，它的表现形式应该既有利于后阶段的代码优化，又要在逻辑上便于理解和最终机器（目标）指令代码生成。,常用的中间代码形式,三元式,四元式,逆波兰式,3.5.4,中 间 代 码 生 成,上一页,返 回,下一页,三元式表示：,(OP ARG1 ARG2 ),即,:(,运算符 第一运算项 第二运算项,),例：对于,K=(I+J)*K,可翻译成：,（,1,）,+I J,(2)*(1)K,(3)=K (2),三元式表示实质上是一种树形结构的矩阵描述，它等价于上面语法树。,三 元 式,上一页,返 回,下一页,表示：,(OP ARG1 ARG2 RESULT ),(,运算符 第一运算项 第二运算项 运算结果,),例：对于,K=(I+J)*K,可翻译成：,+I J T1,*T1 K T2,=T2 K,四元式与三元式的相似与区别,相似：排列顺序和实际计算顺序相同,区别：四元式之间的联系是通过临时变量实现的，较三元式易于改变，有利于后一阶段的代码优化操作。,四 元 式,上一页,返 回,下一页,逆波兰表示法是一种把运算符号写在运算项之后的表示方法，也称,后缀表示法,：,例：,a+b,可表示为,ab+,a*b,可表示为,ab*,对于赋值语句,K=,（,I+J,）*,K,，可翻译成,I J+K*K=,逆 波 兰,上一页,返 回,下一页,代码优化的分类及常用方法,逻辑优化（纯代码优化）：在目标代码生成之前，对语法分析后的中间代码进行优化，主要完成程序结构上的等价变换。,在生成目标代码过程中，根据机器所提供的设备条件，为充分利用机器指令系统和通用寄存器等而进行的优化，这类优化于具体的机器有关。,常用方法,删除多余的运算、合并已知量、代码外提、强度削弱、变换循环控制条件、复写传播、删除无用赋值等。,物理优化与具体的机器有关。,3.5.4,代码优化,上一页,返 回,下一页,例如，有代码序列：,A=B+C+D,E=B+C+F,W=B+C+Y,删除多余的运算可优化为：,T=B+C,A=T+D,E=T+F,W=T+Y,代码优化（举例）,上一页,返 回,下一页,基本概念,把语法分析后生成的中间代码或经过代码优化后的中间代码变换成目标代码,目标代码一般有以下三种形式,可立即执行的机器语言代码，代码中的所有地址已是真正的机器指令地址。,待装配的机器语言模块。当需要执行时，由连接装配程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码,汇编语言代码，运行时尚需经过汇编程序汇编，转换成可执行机器语言代码,目标代码生成时应着重解决两个问题,如何使生成的目标代码尽量短；,如何充分利用计算机的寄存器，以减少目标代码中访问内存的次数,。,3.5.6,目标代码生成,上一页,返 回,下一页,例,4.,写出赋值语句,K=,（,I+J,）,-K,的四元式中间代码表示形式及其转换后的汇编语言指令,上一页,返 回,下一页,表格管理的主要任务就是对各类编译信息进行登录、查询和更新等工作。,出错处理的主要任务是对程序中所包含的各种错误,(,如语法,语义错误等,),进行诊断和处理。,常能处理的错误有如下三种,：,不正确地使用语言的各种成分。,输入和书写时可能出现的错误。,超出编译程序或计算机的某些限制，如数组维数太多、下标越界、数组占用空间太大等。,可分为语法和语义错误两大类。,语法错误是指程序结构,不符合词法或语法规则,。,语义错误是指程序结构,不符合语义规则或超越,具体,计算机系统的限制,。,3.5.7,表格管理和出错处理,上一页,返 回,下一页,处理源程序错误的方法有两种：,一是试图对错误进行校正；,二是尽可能把错误限制在一个局部范围内，避免这种错误影响程序其他部分的分析和检查。,3.5.7,表格管理和出错处理（序）,上一页,返 回,下一页,词法分析,语法分析,语义分析与中间代码产生,优化,目标代码生成,P195 25,补充：写出赋值语句,y=(A+2*B)-4*C,的三种中间代码形式。,教学小结,作 业,返 回,上一页,教学目的,本讲主要介绍操作系统的定义、分类、功能,教学重点与难点,操作系统分类,操作系统功能,3.6,操作系统,教学,引入,在前面的学习中，我们知道计算机由硬件和软件组成，那么由谁来协调两者的工作？,返 回,下一页,操作系统：是由程序和数据结构组成的大型系统软件，它负责计算机的全部软硬件资源的分配、调度与管理，控制各类程序的正常执行，并为用户使用计算机提供良好的环境,从用户角度看：操作系统可以看成是计算机的,硬件扩充,人机交互方式来看：操作系统是用户与机器的,接口,管理者角度看：操作系统也是管理资源的,程序扩充,操作系统的概念,上一页,返 回,下一页,五大类型,批处理操作系统：用户布置任务后，直到运行结束无法干涉,单道批处理系统,多道批处理系统,分时操作系统,实时操作系统,网络,操作系统,分布式,操作系统,传统,现代,操作系统的分类,重点,上一页,返 回,下一页,重要概念,单道：每次只调一个用户程序进入内存让它运行。,多道：是指内存中驻留多个程序或一个程序的多个程序段。,多重处理系统：一般指多,CPU,系统。,终端：一个具有显示设备和键盘控制台，既是输入设备，又是输出设备。,单道批处理系统：用户一次可以提交多个作业，系统逐个处理作业，一个作业处理完毕再处理另一个作业。,多道程序设计技术：就是在内存中同时存放并运行几道相互独立的程序。它是一种宏观上并行，微观上串行的运行方式。,多道批处理操作系统系统,=,批处理系统,+,多道程序设计技术；,其优点是成批处理作业，提高了作业吞吐量、可靠性、计算能力、并行处理能力。缺点是缺乏交互性。主要运用在大计算量的科学计算上。,批处理操作系统,上一页,返 回,下一页,分时技术：将,CPU,的时间分成很短的时间片（几十毫秒,-,几百毫秒）轮流为每个用户工作，采用这种技术的操作系统称为分时操作系统。,优点：系统交互性好、及时性、多用户同时性、每个终端的独占性,缺点：用户的优先级不易控制。,与批处理系统的区别,批处理系统中，一个作业可以长时间占用,CPU,直至作业执行完成；,分时系统中，一个作业只能在一个时间片的时间内使用,CPU,。,分时操作系统,上一页,返 回,下一页,实时操作系统要求计算机对外来信息能以足够快的速度进行处理，并在被控对象允许的时间范围内作出快速响应。主要应用在实时处理之中。,优点：是响应速度快，可靠性高。,缺点：交互能力差、资源利用率低。,与分时系统的相似与区别：,相似：均采用时间片分时技术，具有交互性和及时性。,实时系统：一般是专用的，交互能力差、只允许用户访问数量有限的专用程序；系统响应时间短（微秒,毫秒）,分时系统：具有很强的通用性，有很强的交互功能，允许用户运行或修改自己的应用程序；系统响应时间长（,23,秒）,实时操作系统,上一页,返 回,下一页,网络操作系统是通过通信设施将物理上分散的具有自治功能的多个计算机系统相互联起来，实现信息交换、资源共享、可互操作和协作处理的系统。,示例：,Netware,、,Windows NT,。,网络软件配置：网络通信协议、网址（,IP,地址或域名地址）,网络硬件配置：服务器、配置了网卡的工作站、路由器、交换机、,HUB,等。,网络操作系统,上一页,返 回,下一页,通过通信网络将物理上分布的具有自治功能的计算机系统互连起来，实现信息交换和资源共享、协作完成任务,与网络操作系统的区别,分布式系统,网络系统,协议,没有制定标准,一系列协议,操作系统数量,一个,/,或将多个操作系统统一管理,独立的多个,透明性,系统对用户透明,用户要了解细节,联系程度,逻辑上紧偶合系统,松偶合,分布式操作系统,上一页,返 回,下一页,DOS,Microsoft,Windows,Unix,Linux,Mac OS,典型操,作系统,上一页,返 回,下一页,操作系统,五大功能,存储器,文件,设备,作业,处理器,实现多道程序运行下对处理器的分配和调度，使一个处理器为多个程序交替服务，最大限度地提高,CPU,的利用率,主存的分配与回收,主存的保护,主存的扩充,主要包括对,I/O,设备的分配、启动、完成及回收。,主要的技术：虚拟设备技 术、屏蔽技术,向用户提供实现作业控制的手段。,按一定策略实现作业调度,又称为信息管理，它是对计算机的软件资源的管理，其中包括文件的存储、检索、共享、保护等的方法、技术及算法,重点,上一页,返 回,下一页,操作系,统特性,并发执行,资源共享,虚拟技术,并发性,也叫,“,共行性,”,，多个作业并发执行或一个用户作业的多个程序段间并发执行；多个输入输出设备间并发工作,计算机系统的硬、软件资源可供多个拥有授权的程序或用户共同使用,“,虚拟,”,就是把物理实体映射为一个或多个逻辑实体,.,上一页,返 回,下一页,主要功能,解决多道程序运行下如何把,CPU,的工作时间合理、自动地分配给所要执行的各个程序，以提高,CPU,的利用率，并使用户满意。,在操作系统中通常把,CPU,的管理分为两级：,作业管理,进程管理,3.6.2,处理器管理,上一页,返 回,下一页,作业（,job,）：是用户提交给计算机系统的独立运行单位，它由程序极其所需数据和有关的命令所组成。,经历四个阶段：,作业及其状态转换,上一页,返 回,下一页,进程组成,程序，数据，进程控制块（,PCB,）,单击下面按钮进行运行演示,进程概念,1,2,进程状态,3,进程及其状态的转换,指一个程序在给定的工作空间和数据集合上的一次执行过程，它是操作系统进行资源分配和调度的一个独立单位,就绪状态：该进程已获得除,CPU,之外的所有资源。,执行状态：正在,CPU,上执行的进程。,阻塞状态：需等待除,CPU,之外其他资源,进程状态动画演示,程序管理器,上一页,返 回,下一页,提高,CPU,的利用率,对进程时行,“,细分,”,，一个进程可再分为多个线程,UNIX,：进程是,CPU,的分,配单位,Windows,：线程是,CPU,的分配单位,除了,CPU,以外，进程是在,UNIX,和,WINDOWS,中资源分配单位,线程（,threads,）,上一页,返 回,下一页,查看线程方法,上一页,返 回,下一页,虚拟内存用硬盘空间模拟内存,存储器分配,地址的转换,信息的保护,程序员编写程序内存中程