第3章计算机系统的软件

1、第第3 3章章 计算机系统的软件计算机系统的软件本章要点与学习要求：本章要点与学习要求：计算机软件概念、分类计算机软件概念、分类 （熟悉）（熟悉）程序设计语言程序设计语言 （了解）（了解）数据结构的定义、分类数据结构的定义、分类 （熟悉）（熟悉）编译原理的过程编译原理的过程 （掌握）（掌握）操作系统的分类、功能操作系统的分类、功能 （掌握）（掌握）软件工程的生命周期、模型软件工程的生命周期、模型 （熟悉）（熟悉）第第3 3章章 计算机系统的软件计算机系统的软件计算机软件概述计算机软件概述3.1算法与数据结构算法与数据结构3.2程序设计语言程序设计语言3.3编译原理编译原理3.5操作系统操作系统

2、3.6软件工程软件工程3.7数据库系统数据库系统3.4第第3 3章章 计算机系统的软件计算机系统的软件教学目的教学目的 本讲主要介绍计算机软件的基本概念本讲主要介绍计算机软件的基本概念,对计算机软件有总体上了解对计算机软件有总体上了解教学重点与难点教学重点与难点 软件定义软件定义 软件分类软件分类 计算机系统的组成计算机系统的组成第第3 3章章 计算机系统的软件计算机系统的软件教学引入 在第二章，我们学习了计算机的内部组成，在第二章，我们学习了计算机的内部组成，那么是谁控制这些硬件让它为我们服务？那么是谁控制这些硬件让它为我们服务？ 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算

3、机系统的软件程序作为商品以有形介质为载体进行交易程序作为商品以有形介质为载体进行交易, ,称做软件。即软件是指称做软件。即软件是指为运行、维护、管理及应用计算机所编制的所有程序及其文档资为运行、维护、管理及应用计算机所编制的所有程序及其文档资料的总和。料的总和。软件的特性：软件的特性： 软件是功能、性能相对完备的程序系统 软件是具有使用性能的软设备 软件是信息商品 软件是一种只有过时而无“磨损”的商品 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件系统软件：软件制售商为释放硬件潜能、方便使用而配备的系统软件：软件制售商为释放硬件潜能、方便使用而配备的软件

4、。软件。OS、语言编译/解释系统、网络软件、数据库管理软件、各种服务程序、界面工具箱等支持计算机正常运作和“通用”的软件。应用软件：指解决某一应用领域问题的软件。应用软件：指解决某一应用领域问题的软件。财会软件、通信软件、科技计算软件、CAD/CAM软件等。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件操作操作系统系统群件群件系统系统办公办公软件软件系统工系统工具软件具软件管理计算机系统的软硬件资料，合理地组织计算机工作流程，并为用户使用计算机提供良好的工作环境。如

5、Windows等。 一类日常办公的软件，如Office编程语言一般是以一个集成环境的形式出现的。如：Visual Stutio 。可以帮助操作系统更有效地完成系统的管理和维护。如反病毒软件Internet工具软件工具软件多媒体多媒体处理处理数据库数据库是信息管理的中心，如Access、SQL Server一种基于电子邮件的应用系统软件，它拓宽了电子邮件的内涵，涵养了很多通信协作功能。如Notes、Exchange Server、Group Wise在CPU一级提供多媒体指令，实现对多媒体的直接支持。基于网络环境和Internet 环境的应用软件，如Web服务器、FTP 上一页上一页 返返 回回

6、下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 软件概念；软件概念； 软件分类；软件分类； 计算机系统的组成；计算机系统的组成； P194 1、2 返返 回回 上一页上一页第第3 3章章 计算机系统的软件计算机系统的软件 教学目的教学目的 本讲主要介绍算法和数据结构的基本概念，以及几种常用的数据结构 教学重点与难点教学重点与难点 1. 算法的基本概念 2. 线性表 3. 栈 4. 队列 5. 树第第3 3

7、章章 计算机系统的软件计算机系统的软件教学引入 计算机内部有很多数据需要我们处理，那计算机内部有很多数据需要我们处理，那么计算机是按照什么形式处理这些数据的？么计算机是按照什么形式处理这些数据的？ 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件典型问题典型问题排序问题汉诺塔问题n皇后问题旅行商问题问题类型问题类型排序查找串处理图问题组合问题几何问题数值问题 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件问题的描述问题的描述建立数学模型建立数学模型算法设计算法设计算法的正确性证明算法的正确性证明算法分析算法分析算法的程序实现算法的

8、程序实现 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件算法算法+ +数据结构数据结构= =程序程序对算法的研究主要包括两方面内容：对算法的研究主要包括两方面内容：一是如何设计算法，常用的算法设计方法有分治递归、贪心法、回溯法、动态规划、分支限界等；二是对给定算法，如何分析它的效率和性能。数据的结构分为逻辑结构和物理结构数据的结构分为逻辑结构和物理结构逻辑结构反映数据成员之间的逻辑关系物理结构反映数据成员在计算机内部的存储安排。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件算法概念算法概念算法原意指计算步骤或规则

9、在计算机科学中，算法指用计算机求解某一问题的方法算法特征算法特征有穷性（Finiteness）确定性（Definiteness）有效性（Effectiveness）有0个或多个输入项至少有一个输出项 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件算法描述算法描述自然语言描述流程图描述伪代码描述算法结构算法结构顺序结构选择（分支）结构循环结构 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件算法设计方法算法设计方法递归技术分治法贪心算法回溯法动态规划法算法分析算法分析 时间复杂性指一个算法在计算机上运算所花费的时间 空

10、间复杂性指一个算法在计算机上运算所花费的空间 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件书 名作者名登录号分类号出版年月计算机病毒危机相杰超920253TP306/1092.5实用数据结构霍义兴871470TP31/7187.1计算机系统结构苏东庄841153TP303/1284.1数字逻辑王玉龙875027TP315/2087.5 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数据数据定义：一切可输入计算机并能为计算机所处理的描述客观事物的符号，称为数据。在计算机中，数据的定义是广泛的，数、字符、图形、声音都

11、可是计算机处理的对象，统称为数据分类数值数据：应用于科学计算的程序，它们的组织较为简单，如变量，数组，简单表等。关心的是计算速度与精度。非数值数据：应用于商业或管理的程序，它们组织较为复杂，关心的是按什么规则组织数据，使其占空间少，存取快，并有利于维护（增删、修改） 数据结构就是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数据类型：数据类型：数据的定义域。常见的数据类型有字符型、整数型、逻辑型、数数据的定义域。常见的数据类型有字符型、整数型、逻辑型、数组、集合、记录等。组、集

12、合、记录等。数据项（数据项（date itemdate item）：）：是数据的是数据的最小单位最小单位。 数据元素（数据元素（date elementdate element）：是数据项的：是数据项的集合集合（或称（或称记录记录）。）。 数据对象（数据对象（data objectdata object）：）：它是具有它是具有相同特性相同特性的的数据元素数据元素的集合。的集合。 如整数如整数数据对象的集合。数据对象的集合。结构（结构（data structuredata structure）：）：数据元素之间的相互关系。数据元素之间的相互关系。数据结构（数据结构（data structured

13、ata structure）：）：它是带有结构的它是带有结构的数据元素的集合数据元素的集合。数据结构。数据结构是数据组织形式，反应数据之间的关系，但不涉及数据的具体内容。是数据组织形式，反应数据之间的关系，但不涉及数据的具体内容。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件书 名作者名登录号分类号出版年月计算机病毒危机相杰超920253TP306/1092.5实用数据结构霍义兴871470TP31/7187.1计算机系统结构苏东庄841153TP303/1284.1数字逻辑王玉龙875027TP315/2087.5数据项数据项数据元素数据元素数数 据

14、据第第3 3章章 计算机系统的软件计算机系统的软件数据的逻辑结构：数据的逻辑结构：指数据元素之间的逻辑关系，它与数据在指数据元素之间的逻辑关系，它与数据在计算机中的存储方式无关。计算机中的存储方式无关。线性结构。数据之间存在前后顺序关系，除第一个元素和最后一个元素外，其他结点都有唯一一个前驱和一个后继结点（一对一关系）。包括数组、链表、栈和队列等。树形结构。数据之间存在顺序关系，除了一个根结点外，其他结点都有唯一一个前驱结点，且可以有多个后继结点（一对多关系）。网状结构。每个结点都可以有多个前驱和多个后继结点（多对多关系） 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件

15、计算机系统的软件数据的存储结构：指数据的逻辑结构到计算机存储器的映像。数据的存储结构：指数据的逻辑结构到计算机存储器的映像。顺序存储结构将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。它主要存储线性结构的数据。结点之间的关系由物理相邻关系决定，结点中只有信息域，所以存储密度大，空间利用率高。数据结构中第i个结点的存储地址可由以下公式求得LiL0(i-1)k插入、删除运算会引起相应结点的大量移动。链式存储结构打破了计算机存储单元的连续性，可以将逻辑上相邻的两个数据元素存放在物理上不相邻的存储单元中。结点中除数据外，还有表示链接信息的指针域，因此与顺序存储结构相比，占用更大的存储空间。逻辑上相

16、邻结点物理上不一定相邻，可用于线性表、树、图等多种逻辑结构存储插入、删除等操作灵活方便，不需要大量移动结点，只需修改结点的指针值即可 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件定义定义线性表（Linear List）是 n 个数据元素的有限序列（a1，a2，ai，an）。其中元素ai可以是一个数、或是一个符号、也可以是更复杂的信息。性质性质同一线性表中的元素必定属于同一类数据对

17、象； 除a1元素外，每个元素都仅有一个直接前趋； 除an元素外，每个元素都仅有一个直接后继； 各元素的下标表示了该元素在线性表中的位置。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数组。它是数组。它是n n个类型相同的数据元素构成的序列，它们个类型相同的数据元素构成的序列，它们连续存储在计算机的存储器中，且数组中的每个元素占连续存储在计算机的存储器中，且数组中的每个元素占据相同的存储空间。据相同的存储空间。对数组的描述通常包含下列对数组的描述通常包含下列5 5种属性种属性数组名称。声明数组第一个元素在内存中的起始位址。维度。每一元素所含数据项的个数，

18、如一维数组、二维数组等。数组下标。元素在数组中的储存位置。数组元素个数。是数组下标上限与数组下标下限的差+1。数组类型。声明此数组的类型，它决定数组元素在内存所占有的空间大小。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件链表：它是链表：它是0 0个或多个称为结点的元素构成的序列，个或多个称为结点的元素构成的序列，每个结点除了存储数据外还包含一个或多个称为指针每个结点除了存储数据外还包含一个或多个称为指针的链接，指向链表中其他元素。的链接，指向链表中其他元素。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件栈结构

19、栈结构定义：一种插入和删除操作都只能在尾端进行的线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。特点：是一种后进先出(LIFO)的线性表,也就是说，栈的操作是按后进先出(LIFO：Last In First Out) 的原则进行的。栈的存储结构：栈的存储结构：顺序存储：占有一片连续的存储空间链式存储：也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。栈的基本运算：栈的基本运算：入栈（ 在栈的顶部插入元素 ）出栈（删除栈顶元素）外取栈顶位置上的元素置为一个空栈判定是否为空栈。 重点 上一页上一页 返返

20、 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件a1a2an-1an栈底栈底栈顶栈顶入栈入栈出栈出栈 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件栈的顺序存储结构栈的顺序存储结构 栈的链式存储结构栈的链式存储结构 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件队列定义：仅允许在一端进行插入，另一端进行删除的线性表，称为队队列定义：仅允许在一端进行插入，另一端进行删除的线性表，称为队列列(queue)(queue)。允许插入的一端称为队尾。允许插入的一端称为队尾(rear)(rear)，允许删除

21、的一端称为队，允许删除的一端称为队头头队列的特点：先进先出队列的特点：先进先出(FIFO)(FIFO)。队列的存储结构：队列的存储结构：顺序结构顺序结构、链式结构链式结构队列的基本操作：队列的基本操作：入队列（在队列Q的队尾插入元素）； 出队列（删除队列Q的队头元素）； 取出队列Q的队头元素； 置队列Q为一个空队列； 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件顺序存储结构：顺序存储结构：将队列中元素全部存入一个一维数组中将队列中元素全部存入一个一维数组中, ,数组的低下标一数组的低下标一端为队头端为队头, ,高下标一端为队尾，将这样的队列看成是顺序队

22、列高下标一端为队尾，将这样的队列看成是顺序队列 。若一维数。若一维数组中所有位置上都被元素装满，称为队满，即尾指针组中所有位置上都被元素装满，称为队满，即尾指针rearrear指向一维数组最指向一维数组最后后, ,而头指针指向一维数组开头，称为队满。而头指针指向一维数组开头，称为队满。链式存储结构：链式存储结构：称为链队列，可以用带头结点的单链表作为队列的链式称为链队列，可以用带头结点的单链表作为队列的链式存储结构。存储结构。frontA B C D Erear 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件出队列出队列a1 a2 an入队列入队列队头队

23、头队尾队尾 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 一个图G=是一个数据结构，它由两部分组成：一个有限集合V，它的元素称为顶点；另一个有限集合E，它的元素由顶点对构成，称为边。如果每对顶点之间都没有顺序，也就是说，顶点对(u，v)和顶点对(v，u)是相同的，我们说图G是无向的，如图（a）所示。否则，称为有向的，边的方向是从顶点u到达顶点v，如图（b）所示。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 邻接矩阵。邻接矩阵。n n个顶点的邻接矩阵是一个个顶点的邻接矩阵是

24、一个n nn n阶的布尔矩阵，用来表阶的布尔矩阵，用来表示图的结点间的相邻关系。示图的结点间的相邻关系。邻接表。是链表一个集合，其中每一个顶点用一个邻接链表表示，邻接表。是链表一个集合，其中每一个顶点用一个邻接链表表示，该链表包含了和这个顶点邻接的所有顶点（即所有和该顶点有边相连该链表包含了和这个顶点邻接的所有顶点（即所有和该顶点有边相连的顶点）的顶点）赋权图：图的每条边对应一个数值，在实际应用中这些数值往往是赋权图：图的每条边对应一个数值，在实际应用中这些数值往往是距离、运费、时间等。这些值称为边的权或成本。距离、运费、时间等。这些值称为边的权或成本。邻接矩阵。当存在一条从结点i到结点j的边

25、时，矩阵元素aij的值就是这条边的权重；当不存在这样一条边时，则用一个特殊符号表示。邻接表。邻接表的结点中不仅包含邻接结点的名字，还必须包含相应的边的权重。第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 树和森林：连通无回路的图称为树，如图树和森林：连通无回路的图称为树，如图a a所示。有的所示。有的图虽然不是树，但它的每个子图（连通分支）是树，则图虽然不是树，但它的每个子图（连通分支）是树，则称为森林，如图称为森林，如图b b所示。所示。树有两个性质：树有两个性质：树的边数=树的顶点数减1。树的任意两个顶点之间有且仅有一条通路。图a 树示例 图b 森林

26、示例 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 根树：任选树的一个顶点，将它作为树的根。在对根树根树：任选树的一个顶点，将它作为树的根。在对根树的描述中，根通常放在最顶上（树的第的描述中，根通常放在最顶上（树的第0 0层），与根邻层），与根邻接的顶点放在根的下面（第接的顶点放在根的下面（第1 1层），再下面是和根距离层），再下面是和根距离两条边的顶点（第两条边的顶点（第2 2层），然后依此类推。层），然后依此类推。第第3 3章章 计算机系统的软件计算机系统的软件内部结点与叶子结点：内部结点与叶子结点：除根结点外，有后继的结点称为内部结点除根结点外，

27、有后继的结点称为内部结点没有后继的结点称叶子结点（或树叶）没有后继的结点称叶子结点（或树叶）父结点与子结点：父结点与子结点：某结点的上层结点称为它的父结点；某结点的上层结点称为它的父结点；把其下层结点称为孩子结点把其下层结点称为孩子结点 树的深度：树的深度：从根结点算起的树的层次。从根结点算起的树的层次。树的高度：树的高度：是从根到叶结点的最长路径的长度。是从根到叶结点的最长路径的长度。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 有序树：是一棵根树，树中每一顶点的所有子女都是有序有序树：是一棵根树，树中每一顶点

28、的所有子女都是有序的。的。二叉树：有序树中所有顶点的子女个数都不超过两个的称二叉树：有序树中所有顶点的子女个数都不超过两个的称为二叉树，并且每个子女不是父母的左子女就是父母的右为二叉树，并且每个子女不是父母的左子女就是父母的右子女。子女。 第第3 3章章 计算机系统的软件计算机系统的软件 分析：分析：根据顺序存储和链接存储的线性表优、缺点的分析，可以发现选项C中顺序存储的线性表便于进行增、删操作是不正确的，而本题恰好让我们选择错误的说法，则必是选项C无疑。例例1：下面关干线性表的叙述中，错误的是（：下面关干线性表的叙述中，错误的是（ ）。）。A）线性表采用顺序存储，必须占用一片连续的存储单元）

29、线性表采用顺序存储，必须占用一片连续的存储单元B）线性表采用链接存储，不必占用一片连续的存储单元）线性表采用链接存储，不必占用一片连续的存储单元C）线性表采用顺序存储，便于进行插入和删除操作）线性表采用顺序存储，便于进行插入和删除操作D）线性表采用链接存储，便于插入和删除操作）线性表采用链接存储，便于插入和删除操作结论：答案应选结论：答案应选 C C） 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 上一页上一页 返返 回回下一页下一页 例例2：求下列各图的相邻矩阵：求下列各图的相邻矩阵 第第3 3章章 计算机系统的软件计算机系统的软件 数据结构的基本概

30、念数据结构的基本概念 线性表线性表 栈栈 队列队列 树树P195 7、9、10、13、15。 返返 回回 上一页上一页第第3 3章章 计算机系统的软件计算机系统的软件计算机可以直接识别和执行，效率高指令的二进制代码难记住，人工编写机器语言很繁琐，易出错不同的计算机有不同的机器语言，因而通用性很差。 面向过程的第四代语言。如SQL、PB、Delphi。 面向对象的编程语言和网络语言，如VB、VB、C+、HTML和Java。 各种软件开发工具，如CASE不能为计算机硬件直接识别与执行，必须通过汇编器的系统软件“汇编”，才能被硬件执行。汇编语言指令与机器语言指令一一对应，为低级语言不同的计算机具有不

31、同的汇编语言，记忆指令助记符较记忆指令二进制代码容易，但仍然繁琐。用高级语言编写的源程序必须通过“翻译”生成目标程序，才能被计算机所执行。不同计算机只要配备某种高级语言编译程序，可运行该高级语言源程序，通用性强 与一般的自然语言相比，具有严格、小巧、没有二义性特点第一代第一代语言语言第二代第二代语言语言第三代第三代语言语言第四代第四代语言语言第五代第五代语言语言智能化语言，如PROLOG 重点第第3 3章章 计算机系统的软件计算机系统的软件 FORTRAN COBOL PASCAL C过程化编程语言过程化编程语言面向对象编程语言面向对象编程语言面向人工智能的语言面向人工智能的语言 专专 用用

32、语语 言言 C+ JavaHTMLSQLLISP语言 Prolog 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 概述概述面向过程的程序中，程序划分成一个主模块和若干个子模块。 数据公用 数据与代码相互分离面向对象程序中，将数据以及处理这些数据的例程全部封装在一起形成一个类。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件对象、类、方法对象、类、方法对象是相关数据和方法的结合体。各个对象既是独立的实体，又通过消息相互作用。类是同种对象的集合与抽象。类是一种抽象的数据类型，它是所有具有一定共性的对象的抽象。属于类的

33、某一个对象则被称为是类的一个实例，是类的一次实例化的结果。方法是对数据的一种操作。对象、方法和消息对象、方法和消息“消息”是程序语句实现的一个命令。 对象间的联系通过消息来完成。 方法可以通过外界发“消息”来激活。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件将数据和操作这些数据的方法代码组织将数据和操作这些数据的方法代码组织到一起，即将数据和方法放在同一个对象到一起，即将数据和方法放在同一个对象中，可提高数据的安全性中，可提高数据的安全性一个接口能够做多种用途，个接口能够做多种用途，而其特定的用途由其特定的而其特定的用途由其特定的环境所决定环境所决定

34、一个新类可以从现有的一个新类可以从现有的类中派生出来，新类具有类中派生出来，新类具有父类中的所有特性，直接父类中的所有特性，直接继承了父类的数据和方法继承了父类的数据和方法 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 教学目的教学目的 对数据库系统作进一步的介绍，包括数据库系统特点、数据库管理系统的组成和分类，使大家对数据库系统有进一步的了解。 教学重点与难点教学重点与难点 数据库创建 数据库操作第第3 3章章 计算机系统的软件计算机系统的软件教学引入 我们知道，计算机要处理大量的数据，那我们知道，计算机要处理大量的数据，那么计算机是如何保存这些数据

35、？么计算机是如何保存这些数据？ 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数据库数据库DBDB：相关信息或数据的有规则的集合。：相关信息或数据的有规则的集合。数据库管理系统数据库管理系统DBMSDBMS：一种数据库管理软件，其职能是维护数据：一种数据库管理软件，其职能是维护数据库，接受并完成用户程序或命令提出的对数据进行输入、编辑、库，接受并完成用户程序或命令提出的对数据进行输入、编辑、排序、检索、合并和输出等操作请求。排序、检索、合并和输出等操作请求。 数据库系统：由数据库、数据库管理系统和用户组成数据库系统：由数据库、数据库管理系统和用户组成 上一页上一页 返

36、返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数据库图书馆数据图书外存书库用户读者数据模型书卡格式数据库管理系统图书馆管理员数据的物理组织方法 图书存放方法 用户对数据库的操作读者对图书馆的访问用户对数据库的操作读者对图书馆的访问 （使用数据操纵语言对数据借书、还书等（使用数据操纵语言对数据借书、还书等 检索、插入、删除、修改）检索、插入、删除、修改） 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件层次模型层次模型满足的条件：有一个记录类型没有父结点。 其它记录类型有且只有一个父结点。 上一页上一页 返返 回回下一页下一页 第第3

37、 3章章 计算机系统的软件计算机系统的软件网状模型网状模型满足的条件： 有一个以上记录类型没有父结点。 至少有一个记录类型多于一个父结点 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件关系模型关系模型 满足的条件： 事物与事物之间的联系用二维表格的形式来描述。表中每一行是一个记录，在关系中称为元组；表中每一列是一个字段，在关系中称为属性。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件基本概念：基本概念：表：存储和管理数据的基本单元。它是一种格式化的二维数组。字段：二维表的每一列在关系中称为属性，每个属性都有一个属

38、性名，属性值则是各个元组属性的取值。 字段类型：字段的数据类型及其长度。记录：是一组相关数据项的集合，用于描述一个对象在某方面的属性。主键：能够唯一确定表中的一条记录的一个或几个字段。外键：关系中某个属性或属性组合并非主键，但却是另一个关系的主键，称此属性或属性组合为本关系的外部关键字。关系之间的联系是通过外部关键字实现的。索引：提供对数据项的快速访问。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件学生与所在系的关系学生与所在系的关系系与负责人的关系系与负责人的关系学生、课程与成绩的关系学生、课程与成绩的关系学号学号学生名学生名系名系名94010194

39、0202940301940401 李春梅李春梅刘刘 力力陈文秀陈文秀徐徐 兵兵 计算机系计算机系自动化系自动化系机械系机械系化工系化工系 学号学号课程名课程名成绩成绩940101940202940301940401 ：语言语言：系名系名系主任名系主任名计算机系计算机系 自动化系自动化系 机械系机械系 化工系化工系 郑郑 敏敏李龙李龙 江江金金 剑剑 齐齐 晶晶 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数据定义语言数据定义语言DDLDDL：用来定义数据库的数据模型：用来定义数据库的数据模型数据操作语言：用来表达用户对数据库的操作请求。数据操作语言：用

40、来表达用户对数据库的操作请求。查询数据库中的信息向数据库插入新的信息从数据库中删除信息修改数据库中的信息SQLSQL语言是一个通用型的、功能强大的关系数据库语言语言是一个通用型的、功能强大的关系数据库语言数据定义语句：数据库的定义由 CREATE TABLE、ALTER TABLE和DROP TABLE3种语句构成。数据库查询是数据库的核心操作。SQL语言提供了SELECT语句进行数据库查询数据更新语句的作用是在当前表中添加、删除和修改记录。包括INSERT、DELETE和UPDATE三条语句。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件设计步骤设计

41、步骤需求分析 概念结构设计逻辑结构设计物理结构设计应用程序设计系统运行与维护 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件常用数据库开发平台常用数据库开发平台AccessSQL ServerVisual FoxProPower BuilderOracleSybase 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数据库数据库发展史发展史文件系统阶段文件系统阶段人工管理阶段人工管理阶段关系数据库系统关系数据库系统 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件64主要是指主要

42、是指5050年代中期以前的这段时间，此时的计算机年代中期以前的这段时间，此时的计算机还很简陋，连完整的操作系统都没有。因此，数据只还很简陋，连完整的操作系统都没有。因此，数据只能放在卡片上或其他介质上，由人来手工管理。能放在卡片上或其他介质上，由人来手工管理。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件65主要是指主要是指5050年代后期到年代后期到6060年代中期的这段时间，此时的年代中期的这段时间，此时的计算机已经有了操作系统。在操作系统基础之上建立的计算机已经有了操作系统。在操作系统基础之上建立的文件系统已经成熟并广泛应用。因此，人们自然想到用

43、文件系统已经成熟并广泛应用。因此，人们自然想到用文件把大量的数据存储在磁盘这种介质上，以实现对数文件把大量的数据存储在磁盘这种介质上，以实现对数据的永久保存和自动管理以及维护；据的永久保存和自动管理以及维护； 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件66与文件系统相比的优点与文件系统相比的优点：数据是结构化的面向系统，减少了数据冗余可以用数据结构化查询语言对数据库中的数据进行操作 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件XML/RDBMSXML/RDBMS混合数据处理将在未来得到快速的发展混合数据处理将

44、在未来得到快速的发展数据集成和数据仓库将向内容管理过渡数据集成和数据仓库将向内容管理过渡基于基于InternetInternet的自动化管理的自动化管理支持商业智能成重点支持商业智能成重点数据库技术与多学科技术的有机结合数据库技术与多学科技术的有机结合 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 分析：分析：在数据库系统阶段，数据的冗余度只能说明显减小了,节约了存储空间而没有完全消除，因此说“无数据冗余”不够准确。例例3：数据管理技术随着计算机技术的发展而发展。数据库阶段具：数据管理技术随着计算机技术的发展而发展。数据库阶段具有很多特点，但下面列出的

45、特点中哪一个不是数据库阶段的特点？有很多特点，但下面列出的特点中哪一个不是数据库阶段的特点？（ ）A）无数据冗余）无数据冗余 B）采用复杂的数据结构）采用复杂的数据结构C）数据共享）数据共享 D）数据具有较高的独立性）数据具有较高的独立性结论：答案应选结论：答案应选 A A） 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件数据库管理系统的分类数据库管理系统的分类 关系数据库关系数据库 数据库的发展历史数据库的发展历史 现阶段常用数据库简介现阶段常用数据库简介 数据库技术的新发展数据库技术的新发展 P195 17P195 17、1818、1919 返返 回

46、回 上一页上一页第第3 3章章 计算机系统的软件计算机系统的软件教学目的教学目的介绍高级语言源程序是如何被计算机识别，对编译原理有大致了解教学重点与难点教学重点与难点 词法分析 语法分析 中间代码生成 代码优化 目标代码生成 表格管理和出错处理第第3 3章章 计算机系统的软件计算机系统的软件教学引入 我们向计算机编写的代码如何被计算机识别？我们向计算机编写的代码如何被计算机识别？ 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 编译程序编译程序是实现将源程序是实现将源程序“翻译翻译”为目标程序的系统为目标程序的系统软件，它由若干个程序组成，故又称为软件，它由若干个程序

47、组成，故又称为编译系统编译系统。 翻译外文资料的大致过程：翻译外文资料的大致过程：识别单词语法分析初译加工高级语言程序高级语言程序（源程序（源程序.C）C语言语言编译器编译器连接装连接装配程序配程序运行机器运行机器语言程序语言程序目标程序目标程序 .obj可执行程序可执行程序 .exe结果结果 上一页上一页 返返 回回下一页下一页 词法分析：对源程序逐个字符地进行扫描，以识别出各个单词符号，并分别归类。词法分析：对源程序逐个字符地进行扫描，以识别出各个单词符号，并分别归类。语法分析：根据程序设计语言的语法规则，将词法分析器所提供的单词符号串构成语法分析：根据程序设计语言的语法规则，将词法分析器

48、所提供的单词符号串构成一个语法分析树。一个语法分析树。语义分析：检查各句子的语法树。语义分析：检查各句子的语法树。中间代码的生成：向目标代码过度的一种编码，其形式尽可能和机器的汇编语言相中间代码的生成：向目标代码过度的一种编码，其形式尽可能和机器的汇编语言相似，以便于下一步的代码生成。似，以便于下一步的代码生成。代码优化：对中间代码程序做局部或全局优化，可使最后生成的目标代码程序运行代码优化：对中间代码程序做局部或全局优化，可使最后生成的目标代码程序运行更快，占用存储空间更小。更快，占用存储空间更小。目标代码生成：由代码生成器生成目标机器的目标代码程序，并完成数据分段、选目标代码生成：由代码生

49、成器生成目标机器的目标代码程序，并完成数据分段、选定寄存器等工作，然后生成机器可执行的代码。定寄存器等工作，然后生成机器可执行的代码。重点 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件高级语言的单词属性的类型：高级语言的单词属性的类型： 基本字（保留字） 标识符（如变量名、数组名、过程名等） 常数 运算符 + - * / 栈顶运算符，则将其压入运算符栈； 若当前运算符栈顶运算符，则弹出栈顶运算符和操作数栈中的相应操作数，完成其运算，并把计算结果压入操作数栈中； 若当前运算符=栈顶运算符，则弹出运算符栈的栈顶符号，并读入下一单词，什么计算也不进行。反复执

50、行上述过程，直至句末符反复执行上述过程，直至句末符“#”#”，操作数栈中只剩下一个，操作数栈中只剩下一个结果值，表明分析正确。否则出错。结果值，表明分析正确。否则出错。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件中间代码的定义中间代码的定义中间代码是一种结构简单、含义明确的记号系统，它的表现形式应该既有利于后阶段的代码优化，又要在逻辑上便于理解和最终机器（目标）指令代码生成 。 常用的中间代码形式常用的中间代码形式三元式四元式逆波兰式 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件三元式表示：三元式表示： (O

51、P ARG1 ARG2 ) 即: (运算符 第一运算项 第二运算项) 例：对于例：对于K=(I+J)K=(I+J)* *K K可翻译成：可翻译成： （1） + I J (2) * (1) K (3) = K (2)三元式表示实质上是一种树形结构的矩阵描述，它等价于上面语法树。三元式表示实质上是一种树形结构的矩阵描述，它等价于上面语法树。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件表示：表示： (OP ARG1 ARG2 RESULT ) (OP ARG1 ARG2 RESULT ) (运算符 第一运算项 第二运算项 运算结果) 例：对于例：对于K=(

52、I+J)K=(I+J)* *K K可翻译成：可翻译成： + I J T1 * T1 K T2 = T2 K四元式与三元式的相似与区别四元式与三元式的相似与区别相似：排列顺序和实际计算顺序相同区别：四元式之间的联系是通过临时变量实现的，较三元式易于改变，有利于后一阶段的代码优化操作。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件逆波兰表示法是一种把运算符号写在运算项之后的表示方逆波兰表示法是一种把运算符号写在运算项之后的表示方法，也称法，也称后缀表示法后缀表示法： 例： a+b 可表示为 ab+ a*b 可表示为 ab * 对于赋值语句 K=（I+J）*

53、K，可翻译成 I J+K*K= 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件代码优化的分类及常用方法代码优化的分类及常用方法逻辑优化（纯代码优化）：在目标代码生成之前，对语法分析后的中间代码进行优化，主要完成程序结构上的等价变换。 在生成目标代码过程中，根据机器所提供的设备条件，为充分利用机器指令系统和通用寄存器等而进行的优化，这类优化于具体的机器有关。 常用方法常用方法删除多余的运算、合并已知量、代码外提、强度削弱、变换循环控制条件、复写传播、删除无用赋值等。 物理优化与具体的机器有关。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系

54、统的软件计算机系统的软件例如，有代码序列：例如，有代码序列： 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 3章章 计算机系统的软件计算机系统的软件基本概念基本概念把语法分析后生成的中间代码或经过代码优化后的中间代码变换成目标代码目标代码一般有以下三种形式目标代码一般有以下三种形式可立即执行的机器语言代码，代码中的所有地址已是真正的机器指令地址。 待装配的机器语言模块。当需要执行时，由连接装配程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码

55、汇编语言代码，运行时尚需经过汇编程序汇编，转换成可执行机器语言代码目标代码生成时应着重解决两个问题目标代码生成时应着重解决两个问题如何使生成的目标代码尽量短； 如何充分利用计算机的寄存器，以减少目标代码中访问内存的次数。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件例例4. 写出赋值语句写出赋值语句K=（I+J）-K的四元式中间代码表示形式及其转换后的汇的四元式中间代码表示形式及其转换后的汇编语言指令编语言指令 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 表格管理的主要任务就是对各类编译信息进行登录、查询和更

56、新表格管理的主要任务就是对各类编译信息进行登录、查询和更新等工作。等工作。 出错处理的主要任务是对程序中所包含的各种错误出错处理的主要任务是对程序中所包含的各种错误( (如语法如语法, ,语义语义错误等错误等) )进行诊断和处理。进行诊断和处理。常能处理的错误有如下三种： 不正确地使用语言的各种成分。 输入和书写时可能出现的错误。 超出编译程序或计算机的某些限制，如数组维数太多、下标越界、数组占用空间太大等。可分为语法和语义错误两大类。 语法错误是指程序结构不符合词法或语法规则。 语义错误是指程序结构不符合语义规则或超越具体计算机系统的限制。 上一页上一页 返返 回回下一页下一页 第第3 3章

57、章 计算机系统的软件计算机系统的软件处理源程序错误的方法有两种：处理源程序错误的方法有两种： 一是试图对错误进行校正； 二是尽可能把错误限制在一个局部范围内，避免这种错误影响程序其他部分的分析和检查。 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 词法分析词法分析 语法分析语法分析 语义分析与中间代码产生语义分析与中间代码产生 优化优化 目标代码生成目标代码生成 P195 25补充：写出赋值语句补充：写出赋值语句y=(A+2*B)-4*C的三种中间代码形式。的三种中间代码形式。 返返 回回 上一页上一页第第3 3章章 计算机系统的软件计算机系统的软件教

58、学目的教学目的 本讲主要介绍操作系统的定义、分类、功能教学重点与难点教学重点与难点 操作系统分类 操作系统功能第第3 3章章 计算机系统的软件计算机系统的软件教学引入 在前面的学习中，我们知道计算机由硬件在前面的学习中，我们知道计算机由硬件和软件组成，那么由谁来协调两者的工作？和软件组成，那么由谁来协调两者的工作？ 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件 操作系统：是由程序和数据结构组成的大型系统软件，它负操作系统：是由程序和数据结构组成的大型系统软件，它负责计算机的全部软硬件资源的分配、调度与管理，控制各类程责计算机的全部软硬件资源的分配、调度与管理，控制各

59、类程序的正常执行，并为用户使用计算机提供良好的环境序的正常执行，并为用户使用计算机提供良好的环境 从用户角度看：操作系统可以看成是计算机的硬件扩充 人机交互方式来看：操作系统是用户与机器的接口 管理者角度看：操作系统也是管理资源的程序扩充 上一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件五大类型五大类型批处理操作系统：用户布置任务后，直到运行结批处理操作系统：用户布置任务后，直到运行结束无法干涉束无法干涉单道批处理系统 多道批处理系统分时操作系统分时操作系统实时操作系统实时操作系统网络网络操作系统操作系统分布式分布式操作系统操作系统传传统统现现代代重点 上

60、一页上一页 返返 回回下一页下一页 第第3 3章章 计算机系统的软件计算机系统的软件重要概念重要概念 单道：每次只调一个用户程序进入内存让它运行。 多道：是指内存中驻留多个程序或一个程序的多个程序段。 多重处理系统：一般指多CPU系统。 终端：一个具有显示设备和键盘控制台，既是输入设备，又是输出设备。单道批处理系统：用户一次可以提交多个作业，系统逐个处理作业，一单道批处理系统：用户一次可以提交多个作业，系统逐个处理作业，一个作业处理完毕再处理另一个作业。个作业处理完毕再处理另一个作业。多道程序设计技术：就是在内存中同时存放并运行几道相互独立的程序多道程序设计技术：就是在内存中同时存放并运行几道