第3章计算机的软件系统

1、 第3章 计算机的软件系统第3章 计算机软件系统n3.1 计算机软件的基本知识 n3.2 数据结构与算法n3.3 操作系统 n3.4 软件工程 第3章 计算机的软件系统3.1 计算机软件的基本知识n3.1.1 计算机软件与硬件的关系n3.1.2 系统软件n3.1.3 应用软件 第3章 计算机的软件系统3.1.1 计算机软件与硬件的关系（1）n1. 计算机软件、硬件的概念 完整的计算机系统包括硬件系统和软件系统 ，它们具有同样重要的作用 计算机硬件是指构成计算机系统的物理实体或物理装置 计算机软件是指用计算机指令和计算机算法语言编写的程序，以及运行程序所需的文档、数据。 根据软件的用途，计算机软

2、件系统又可以分为系统软件和应用软件。 第3章 计算机的软件系统3.1.1 计算机软件与硬件的关系（2）n2. 软件与硬件之间有着极为密切的关系： 硬件是软件运行的基础， 软件是对硬件功能的扩充和完善，软件的运行最终都被转换为对硬件设备的操作。 在实际应用中更是缺一不可，硬件和软件，在实际中更是缺少哪一部分都是无法使用的。 许多硬件所能达到的功能往往需要软件的配合来实现，例如中断保护，既要有硬件实现中断屏蔽保留现场，又要求有软件来完成中断的分析处理。又如，操作系统中诸多功能的实现，都需要硬件支持。返回3.1 第3章 计算机的软件系统3.1.2 系统软件-概念n系统软件是一组为使计算机系统良好运行

3、而编制的基础软件。它是用户所购置的计算机系统的一部分 ，是一种软设备，是提供给用户的系统资源。从功能的角度，系统软件是负责计算机系统的调度管理，提供程序的运行环境和开发环境，向用户提供各种服务的一种软件。 第3章 计算机的软件系统3.1.2 系统软件-分类n1操作系统操作系统 软件系统的核心，是用户与计算机之间的接口，为用户提供软件的开发环境和运行环境。 n2编译、解释程序编译、解释程序 将源程序转换为机器语言代码序列，然后计算机硬件执行这些用机器语言代码表示的指令序列，从而完成用户程序。 n3各种软件平台各种软件平台返回3.1 第3章 计算机的软件系统3.1.3 应用软件n应用软件是指用户在

4、各自应用领域中为解决各类问题而编写的程序，也就是直接面向用户需要的一类软件。常见的有以下几类： 数值计算类 工程设计类 通用管理 办公自动化 返回3.1 第3章 计算机的软件系统3.2 数据结构与算法n3.2.1 数据结构概述n3.2.2 几种常见的数据结构n3.2.3 算法概述n3.2.4 常用算法介绍n3.2.5 算法评价返回目录 第3章 计算机的软件系统3.2.1 数据结构概述n1什么是数据结构？什么是数据结构？ 数据结构是指数据之间的相互关系，数据结构是指数据之间的相互关系，即数据的组织形式。即数据的组织形式。n2基本概念和术语（下一页）基本概念和术语（下一页） 数据数据 数据元素数据

5、元素 数据类型数据类型 数据结构数据结构返回返回3.2 第3章 计算机的软件系统3.2.1 数据结构概述n（1）数据数据。 数据是对客观事物的符号表示，能被计算机识别、存储和处理的符号总称。它是计算机加工的“原料”。例如，数、字符、文字、图像、声音等都是数据。n（2）数据元素数据元素。 数据元素是数据的基本单位。一个数据元素可由若干个数据项组成。数据项是数据不可再分的最小单位。n（3）数据类型数据类型。 数据类型是具有相同性质的数据元素的集合。返回3.2 第3章 计算机的软件系统 （4）数据结构数据结构。数据结构主要是研究程序设计中计算机所操作的对象以及它们之间的关系和运算。n数据结构有三方面

6、内容：n 逻辑结构， 通常有4种基本结构：集合 、线性结构 、树形结构 、图状结构 n 存储结构（或称物理结构）n 基本操作返回上一页 第3章 计算机的软件系统3.2.2 几种常见的数据结构n1线性表线性表n2栈和队列栈和队列n3数组数组n4树与二叉树树与二叉树n5图图返回3.2 第3章 计算机的软件系统数据结构- 1线性表线性表 线性表是最简单、最常用的一种数据结构。n（1）定义 线性表的逻辑结构是n个数据元素的有限序列： （a1，a2，a3， ai，an） 其中，n 为表中数据元素的个数，定义为表的长度。线性表中所有数据元素 ai必须有相同的数据类型。n（2）线性表的存储结构 线性表的存储

7、结构分为两类，一类是顺序存储结构（又称为静态存储结构），另一类是链式存储结构（又称为动态存储结构），如下页图3-1所示。 第3章 计算机的软件系统图3-1（线性表存储结构示意图） 返回3.2.2 第3章 计算机的软件系统数据结构- 2栈和队列栈和队列n栈又称为堆栈，是一种操作受限的线性表，是限制在表的一端进行插入和删除的线性表。插入、删除的这一端称为栈顶，另一端称为栈底，不含数据元素的栈称为空栈。它的工作方式是先进后出，如图3-2所示。n队列是一种先进先出（FIFO）的线性表，它允许在表的一端进行插入，而在另一端进行删除操作。允许插入的一端称为队尾，允许删除的一端称为队首，如图3-3所示。返回

8、3.2.2 第3章 计算机的软件系统栈的示意图 队列示意图 第3章 计算机的软件系统数据结构- 3数组数组n数组已经广泛应用于各种高级语言中，从结构上看，它是线性表的推广。数组由数组名和下标组成，数组中各元素具有统一类型，并且数组元素的每一维的下标具有固定的下界与上界。n数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。返回 第3章 计算机的软件系统数据结构- 4树与二叉树树与二叉树n树型结构是一类重要的非线性数据结构，在任意一棵树中： （1）有且仅有一个特定的称为根的结点。 （2）其余的结点可分为 m（m0）个互不相交的有限集合 T1

9、， T2 Tm，其中每个子集都是一棵树，并称其为子树。 第3章 计算机的软件系统返回ABEJKFCDHIGL 第3章 计算机的软件系统数据结构- 5图图n图是一种较线性表与树更为复杂的数据结构，图是由顶点集V和边集E构成，记作： G（V，E）n其中V是图中顶点的非空有穷集合，E是两个顶点之间关系的集合，它是顶点的有序或无序对，记作或（vi，vj）。如图3-5所示，它是由顶点和边构成的，顶点集VA，B，C，D，E，F，边的集合E （A，B），（B，C），（A，D），（B，E），（C，E），（C，F），（D，F），（E，F）。若图中每条边都是有向，则称G为有向图，否则称为无向图。 第3章 计算机的

10、软件系统返回ABCDFE 第3章 计算机的软件系统3.2.3 算法概述n1什么是算法什么是算法n2算法的性质算法的性质n3算法与数据结构的关系算法与数据结构的关系n4算法的描述算法的描述返回返回3.2 第3章 计算机的软件系统1什么是算法什么是算法n计算机解题一般可分解成若干操作步骤，通常把完成某一任务的操作步骤称为求解该问题的算法。程序就是用计算机语言描述的算法。n欧几里得算法： 表述了一个数的求解过程，同时又表述了一个判定过程 n给定两个正整数m和n求它们的最大公约数（即能同时整除m和n的最大正整数）的步骤如下： （1）以 n 除 m 并令所得余数为 r，r必小于 n； （2）若 r 0算

11、法结束，输出结果 n。否则继续步骤（3）； （3）将 m 置换为 n，n 置换为 r，并返回步骤 （1）继续进行。返回 第3章 计算机的软件系统2算法的性质算法的性质n算法的性质 ：（1）有穷性（2）确定性（3）有零个或多个输入（4）有一个或多个输出（5）有效性返回 第3章 计算机的软件系统3算法与数据结构的关系算法与数据结构的关系n算法与数据结构都是计算机程序的两个最基本的概念。n在谈到算法与数据结构二者的关系时，瑞士著名计算机科学家尼克劳斯沃思（Niklaus Wirth）在1976年曾提出这样一个公式： 算法+数据结构程序。n准确地说，一个程序规定了某个数据结构上的一个算法。算法是程序的

12、核心，它在程序设计乃至在整个计算机科学中都占据重要地位。返回 第3章 计算机的软件系统4算法的描述算法的描述n算法是对解题过程的精确描述。 n算法的描述方法： （如书47-48）（1）自然语言（2）传统流程图（3）N-S流程图（4）伪代码 第3章 计算机的软件系统【例3-1】 n【例3-1】 求 1+ 2+ 3+ + 100之和。分别用传统流程图、N-S 流程图及自然语言描述其算法，并将该算法转化为BASIC语言源程序。设变量 x 表示被加数，y表示加数。返回 第3章 计算机的软件系统（1）采用传统流程图和N-S流程图描述算法如图所示。 第3章 计算机的软件系统（2）采用自然语言描述算法如下：

13、n步骤 1：将 1赋值给 x；n步骤 2：将 2赋值给 y；n步骤 3：将 x 与 y相加，结果存放在 x 中；n步骤 4：将 y加 1结果存放在 y中；n步骤 5：若 y小于或等于 100 转到步骤 3 继续执行，否则算法结束，结果为 x。 第3章 计算机的软件系统（3）将上述算法转化为BASIC语言源程序： x1 y2 WHILE y100 xx+y yy+1 WEND print x；x END返回3.2.3 第3章 计算机的软件系统3.2.4 常用算法介绍n算法包括数值计算算法和非数值计算算法两类 ，一些典型的简单的算法概要介绍 ：1递归递归2枚举法枚举法3查找查找4排序排序返回返回

14、第3章 计算机的软件系统3.2.5 算法评价n1算法的时间复杂度算法的时间复杂度 n2算法的空间复杂度算法的空间复杂度 n3算法是否易理解、易维护算法是否易理解、易维护返回返回3.2 第3章 计算机的软件系统1算法的时间复杂度算法的时间复杂度 算法时间复杂度是指依据算法编制程序后在计算机中运行时所耗费的时间的大小决定的。 通常，把整个程序中语句的重复执行次数之和作为该程序运行的时间特性，称为算法的时间复杂度，用T（n）表示。T为英文单词Time的第一个字母，T（n）中的n表示问题规模的大小。如在累加求和中n表示待加数的个数，在矩阵相加问题中n表示矩阵的阶数，在图中n表示顶点数等。算法的时间复杂

15、度T（n）实际上是表示当问题的规模n充分大时该程序占用时间的一个数量级。例如，若某程序运行时的时间复杂度为（n）2n3+2n2+2n+2，则表明程序运行所需要的时间与n3成正比，引入符号“O”进行算法复杂度分析，则有T（n） O（n3）。若T（n）2n-1，则该问题的时间复杂度T（n）O（2n）。返回 第3章 计算机的软件系统2算法的空间复杂度算法的空间复杂度 n算法的空间复杂度是指依据算法编制成程序后在计算机中运行时所需的空间的大小。一个程序在计算机上运行所占的空间也是n的一个函数，称为算法的空间复杂度，记为S（n）。n如果S（n） O（n2），表示运行时所占用的空间与n2成正比。例如，在两

16、个nn阶矩阵相乘后送入另一矩阵，在运算中用到的辅助空间（循环变量的个数）与n无关，也就是说不会随着n的增加而增加，所以其空间复杂度S（n）1。返回 第3章 计算机的软件系统3.3 操作系统n3.3.1 什么是操作系统n3.3.2 操作系统的功能n3.3.3 操作系统的特征和体系结构n3.3.4 操作系统的分类n3.3.5 几种常见的操作系统返回目录 第3章 计算机的软件系统3.3.1 什么是操作系统n操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。 1、操作系统是软件，而且是系统软件，也就是说，它由一套程序组成。如：

17、UNIX 系统就是一个很大的程序，它由上千个程序模块组成。 2、它的基本职能是控制管理系统内各种资源，有效地组织多道程序的运行。 3、它提供众多服务，方便用户使用，扩充硬件功能。如用户使用其提供的命令完成对文件、输入输出、程序运行等许多方面的控制、管理工作等。 第3章 计算机的软件系统用户、软件和硬件的层次关系图 第3章 计算机的软件系统n计算机启动后，总是先把操作系统装入内存，然后才能运行其他的软件。 n计算机启动后，操作系统就被自动装入内存，用户看到的是已经加载了操作系统的计算机，用户也是通过操作系统来使用计算机的。所以说，操作系统是用户与计算机硬件设备之间的接口 n启动计算机就是把操作系

18、统装入内存，这个过程又称为引导系统。n在计算机电源关闭的情况下，打开电源开关启动计算机被称为冷启动；n在电源打开的情况下，重新启动计算机，被称为热启动。返回3.3 第3章 计算机的软件系统3.3.2 操作系统的功能n目前有许多不同种类的操作系统，微机操作系统大多面向单用户，而大型操作系统大多把焦点集中在计算机系统的多用户或多道处理方面。由于操作系统的大部分程序用于计算机资源的管理，因此可以用操作系统管理资源的观点来研究操作系统。通常把计算机资源分成四类，即处理机、存储器、外部设备和文件。因此也可以把操作系统分成这样几个部分：处理机管理、存储器管理、设备管理、文件管理、用户接口。返回3.3 第3

19、章 计算机的软件系统1处理机管理处理机管理n什么是进程？ 是一个程序在一个数据集上的一次执行。 n进程在执行过程中有三种基本状态： 挂起状态（也称为等待状态）、就绪状态和运行状态。 功能功能：有效地、合理地分配有效地、合理地分配CPUCPU的时间。的时间。 第3章 计算机的软件系统单道程序系统单道程序系统 第3章 计算机的软件系统多道程序系统多道程序系统各程序轮流地占用各程序轮流地占用CPUCPU，交替执行，交替执行 第3章 计算机的软件系统进程进程动态性 程序的一次执行过程 并发性 系统中可以同时有几个进程在活动 独立性 能独立运行的基本单位，资源分配基本单位 异步性 进程按各自独立的、不可

20、预知的速度前进基本特征有：基本特征有： 动态性动态性 并发性并发性 独立性独立性 异步性异步性 第3章 计算机的软件系统线程：线程：(threads) 对进程时行对进程时行“细分细分”，一个进程可再分为多个线程，一个进程可再分为多个线程 第3章 计算机的软件系统1处理机管理处理机管理n处理机管理主要包括作业调度和进程调度、进程控制和进程通信。 （1）作业和进程调度。一个作业通常要经过两级调度才能得以在 CPU 上执行。首先是作业调度，它把选中的一批作业放入内存，并为它们分配其必要资源，建立相应的进程，然后进程调度按一定的算法从就绪进程中选出一个合适进程，使之在 CPU 上运行。 （2）进程控制

21、。进程是系统中活动的实体。进程控制包括创建进程、撤消进程、封锁进程、唤醒进程等。 （3）进程通信。多个进程在活动过程中彼此间发生的相互依赖或者相互制约的关系，具体体现为信息的发送和接收。 第3章 计算机的软件系统2存储管理存储管理n存储管理就是对计算机内存的分配、保护和扩充进行协调管理 n存储管理主要包括：（1）内存分配。其主要任务是为每道正在处理的程序或数据分配内存空间。 （2）地址映射。把逻辑地址转换为物理地址的过程 （3）内存保护。 （4）内存扩充。也就是“虚拟存储技术” 返回3.3.2 第3章 计算机的软件系统虚拟内存用硬盘空间模拟内存虚拟内存用硬盘空间模拟内存真正内存真正内存虚拟内存

22、虚拟内存内存空间内存空间WindowsWindows中：中：Pagefile.sys Pagefile.sys 默认默认RAMRAM的的1.51.5可调整可调整 第3章 计算机的软件系统3设备管理设备管理n设备管理主要包括 ：（1）缓冲区管理。缓冲区管理目的是解决 CPU 与外设之间速度不匹配的矛盾。 （2）设备分配。有时多道作业对设备的需要量会超过系统的实际设备拥有量。 （3）设备驱动。实现 CPU 与通道和外设之间的通信。 （4）设备无关性。 返回3.3.2 第3章 计算机的软件系统4文件管理文件管理n文件管理的对象是系统的软件资源，在操作系统中由文件系统来实现对文件的管理。 n例如，“C

23、：Program FilesMicrosoft OfficeOfficeWinword.exe”就指明了文字处理软件Word在硬盘上的存放位置。n文件是存储在外存储器上的。 返回3.3.2 第3章 计算机的软件系统5用户接口用户接口n用户在机器上运行程序过程中，需要告诉机器各种运行要求、出错处理方式等，因此操作系统应向用户提供一系列操作命令，作为机器和用户的接口。操作系统与用户之间的接口大致有两种。（1）程序一级的接口（2）作业控制语言和操作命令返回3.3.2 第3章 计算机的软件系统3.3.3 操作系统的特征和体系结构（1）n1操作系统的操作系统的特征特征（1）并发）并发 并发性是指两个或多

24、个活动在同一时间间隔并发性是指两个或多个活动在同一时间间隔中进行，对用户来说，好像同时都在使用计算中进行，对用户来说，好像同时都在使用计算机，这是宏观上的概念。而从微观上看，是多机，这是宏观上的概念。而从微观上看，是多个进程交替使用个进程交替使用 CPU。（2）共享）共享 共享是指计算机系统中的资源被多个任务所共享是指计算机系统中的资源被多个任务所共用。可以共享的资源包括内存、共用。可以共享的资源包括内存、CPU、外存、外存等。等。（3）异步性）异步性 异步性是指在多道程序环境下，各程序的执异步性是指在多道程序环境下，各程序的执行过程有着各自的起始和终止，彼此是以不同行过程有着各自的起始和终止

25、，彼此是以不同的步伐行进的。的步伐行进的。 第3章 计算机的软件系统3.3.3 操作系统的特征和体系结构（2）n操作系统有如下三种结构： （1）模块结构（2）层次结构（3）微内核结构返回3.3 第3章 计算机的软件系统3.3.4 操作系统的分类n1多道批处理操作系统多道批处理操作系统 ： 最早问世的操作系统，又分为单道批处理操作系统和多道批处理操作系统。 n2分时操作系统：分时操作系统： 允许多个用户（从一个到几百个）通过各自的终端同时交互地使用一个计算机系统 n3实时操作系统：实时操作系统： 时间性强、响应快 返回3.3 第3章 计算机的软件系统按任务数按任务数图形用户界面操作系统图形用户界

26、面操作系统命令行界面命令行界面操作系统操作系统多用户操作系统多用户操作系统单用户操作系统单用户操作系统多任务操作系统多任务操作系统单任务操作系统单任务操作系统分时操作系统分时操作系统批处理系统批处理系统实时操作系统实时操作系统网络操作系统网络操作系统按用户界面按用户界面按用户数按用户数按系统功能按系统功能DOSDOSWindowsWindowsUNIXUNIXNetwareNetwareWindows NTWindows NT 第3章 计算机的软件系统3.3.5 几种常见的操作系统1DOS操作系统操作系统2Windows操作系统操作系统3UNIX操作系统操作系统4Linux操作系统操作系统nD

27、OS：单用户单任务操作系统nWindows：单用户多任务操作系统nUnix：多用户多任务分时操作系统nNetware/Windows NT：网络操作系统返回返回3.3 第3章 计算机的软件系统3.4 软件工程n3.4.1 软件工程概述n3.4.2 软件的生命期及模型n3.4.3 软件需求分析n3.4.4 软件设计n3.4.5 编码n3.4.6 软件测试n3.4.7 软件维护返回目录 第3章 计算机的软件系统3.4.1 软件工程概述n早期的软件主要是指程序，程序的开发采用个体方式，开发工作主要依赖于开发人员的个人技能和程序设计技巧。随着计算机应用的需求不断增长，软件的规模也越来越大，然而软件开发

28、的生产率远远跟不上计算机应用的迅速增长，20世纪60年代中期，人们把软件开发和维护过程中的各种问题称为“软件危机”。n“软件工程” 为了解决“软件危机”而提出来的，因此，所谓“软件工程”，就是研究大规模程序设计的方法、工具和管理的一门工程学科。“软件工程”这个词第一次正式提出是在1968年北约组织的一次学术讨论会上。n软件工程是从管理和技术两方面研究如何更好地开发和维护计算机软件的学科。返回3.4 第3章 计算机的软件系统3.4.2 软件的生命期及模型n软件的生存期 ：同任何事物一样，软件也有一个孕育、诞生、成熟、衰亡的许多阶段，一般称其为软件的生存期。 n软件生存期的6个阶段，即制定计划、需

29、求分析、概要设计、详细设计和编码、测试、运行维护。n几种主要的模型 （下一页） 第3章 计算机的软件系统几种主要的模型- 1瀑瀑布模型布模型n1瀑布模型瀑布模型软件计划需求分析软件设计软件编码软件测试软件维护 第3章 计算机的软件系统2渐增模型渐增模型问题描述软件需求分析软件设计和编码软 件 运 行和测试满意？YN 第3章 计算机的软件系统3喷泉模型喷泉模型n对于复杂大型的软件，开发一个原型往往达不到要求，于是后来便出现了螺旋模型。螺旋模型将瀑布模型与渐增模型结合起来，并且加入了被这两种模型都忽略了的风险分析，弥补了两者的不足。它适合于大型软件的开发。应该说它是最为实际的方法，它吸收了软件工程“演化”的概念，使得开发人员和客户对每个演化层出现的风险都有所了解，从而做出相应的反应。 第3章 计算机的软件系统4智能模型智能模型n智能模型也称为基于知识的软件开发模型。它综合了上述若干种模型，并把专家系统结合起来。该模型应用基于规则系统，采用规约和推理机制，帮助软件人员完成开发工作，并使维护在系统规格说明一级进行。返回3.4 第3章 计算机的软件系统3.4.3 软件需求分析n1需求分析的