计算机软件技术基础（部分章节）：计算机软件技术基础教案.PPT

第一章 软件工程
第二章 数据结构
第三章 操作系统
第四章 数据库技术
第五章 面向对象程序设计
第六章 计算机网络
第七章 网页设计
综合练习题
第一章 软件工程
本章简单介绍软件工程的形成和发展，重点介绍软件开发
的不同方法和软件测试策略与方法，最后就软件开发环境和
软件重用技术作一简要介绍。
1.1 概述
软件工程的提出源于 20世记 60年代末期出现的, 软件危
机,, 并在较短的时间内发展成一个完整的学科方向, 30多
年来, 在理论研究和工程实践两个方面作了大量的工作 。
1.1.1 软件工程的形成与发展
1.软件发展的三个阶段
软件开发方法从机器语言编程到软件工程方法, 经历了三个阶段 。
1.程序设计时期 （ 1946年到 60年代中期 ）
生产方式是手工生产, 个体劳动 。 只有程序, 无软件的概念 。
2.软件时期 （ 60年代中期至 70年代中期 ）
程序不再是硬件的附属, 有软件的概念 。
作坊式的生产方式已难满足软件生产的质量和数量上的要求 。
出现了, 软件危机, 。
3.软件工程时期 （ 70年代至今）
1968年,1969年北大西洋公约组织成员国的软件工件者召开了两
个研讨会，提出了“软件工程”这一述语，根本目的在于克服
“软件危机”中所遇到的困难问题，从此进入软件工程时代。
2.软件危机
(1) 软件危机的主要表现：
1)软件开发成本和进度的估计常常很不准确 。
2)用户往往对已完成的软件不满意 。
3)软件的质量常被怀疑 。
4)软件极难维护 。
5)缺乏良好的软件文档。
6)软件开发生产率提高的速度远远跟不上计算机应用迅速普及深
入的趋势。
(2)软件危机的产生原因
一般以为,软件危机的发生与软件产品的特征和软件产品开
发与维护的方法不正确有关。
其一：软件是逻辑的系统部件而不是物理的系统部件，以程
序和文档形式存在，具有无形性。
其二：软件规模越来越大，功能越来越强，导致软件结构非
常复杂。
(3)解决软件危机的途径
方法是要充分吸取和借鉴人类长期以来从事各种工程项目
所积累的行之有效的原理、概念、技术和方法，并应用于软
件开发的实践中，将软件开发变成一种组织良好、管理严密、
各类人员协同完成的工程项目
3,软件工程
1983年 IEEE定义为：, 软件工程是开发, 运行, 维护和修
复软件的系统方法, 。
软件工程学的多个分支
(1)软件工程方法学
方法学是研究软件构造技术的学问 。 一个软件从定义, 开发
到维护, 都需要有适当的方法 。
(2)软件工程环境
对最终用户而言, 环境就是他们运行程序所使用的计算机系
统 。
对于应用软件开发人员, 环境是开发活动的舞台 。
软件工具是环境中最活跃的成分 。 所谓工具, 在这里泛指一
切帮助开发软件的软件 。 在软件开发的各个方面都研制了许多
有效的工具 。 集成化工具的自动切换, 可以明显提高软件的生
产率 。
(3)软件工程管理
软件工程管理的目的, 是为了按照软件的预算和进度完成项
目计划, 实现预期的经济和社会效益 。
1.1.2 软件工程范型
1,传统的软件工程范型 ―― 瀑布模型
瀑布模型是 1976年由 B·W·Boehm提出的, 是基于软件生存周
期的一种范型 。 它将软件生存周期分为定义, 开发, 维护三个
阶段, 每个阶段又分为若干个子阶段, 各子阶段的工作顺序展
开, 如自上而下的瀑布 。 (见后图 )
定义阶段,分析用户需求 。
问题定义, 收集, 分析, 理解, 确定用户的要求 。
可行性研究,确定对问题是否有可行的解决办法 。
需求分析,确定用户对软件系统的全部需求 。
开发阶段,
设计,设计软件系统的模块层次结构, 数据库结构, 模块控制
流程等 。
编程,将每个模块的控制流程纺出相应的程序 。
测试,检查并排除软件中的错误, 提高软件的可靠性 。
维护阶段,
运行与维护,维护软件系统的正常运行 。
各个阶段确均有相应的文档 。
问题定义
或行性研究
需求分析
设 计
编 程
测 试
运行与维护
（目标与范围说明）
（可行性论证报告）
（需求说明书）
（设计文档）
（程序）
（测试报告）
（维护报告）
定义
阶段
开发
阶段
维护
阶段
传统的软件工程范型 ―― 瀑布模型
1.2 软件开发方法
两种不同的开发方法,结构化开发方法和面向对象的开发方法 。
1.2.1 结构化开发方法
一, 结构化分析
1.结构化分析方法, 亦称 SA（ Structured Analysis） 方法 。
(1)SA方法的特点,
① 核心思想：自顶向下和逐步求精 。
② 基本手段：分解和抽象 。
分解：把大问题分割成若干小问题, 然后分别解决 。
抽象,略去细节, 先考虑问题最本质的属性 。
③ 使用了描述需求说明书的几个规范工具 。
即数据流图, 数据词典, 小说明 （ 加工逻辑的描述 ） 等, 使文
档规范化 。
(2)数据流图（ Data Flow Diagram，简称 DFD图）
SA方法采用, 分解, 的方法来描述一个复杂的系统，数据流图
是描述系统中数据流程的图形工具，它标识了一个系统的逻辑输
入和逻辑输出以及把逻辑输入转换为逻辑输出所需要的加工处理 。
1
数据 流图的基本符号：
(1)数据流 (2)加工 (3)数据存储 (4)数据源点或终点。
画各层数据流图应注意的问题：
(1)父图和子图平衡 (2)子图的编号 (3)数据守恒
(3)数据词典 （ Data Dictionary,简称 DD）
对数据流图中包含的所有元素的定义的集合构成了数据字典 。
数据词典中有四种类型的条目：数据流, 文件, 数据项和加工 。
（ 1） 数据流条目
数据流条目给出某个数据流的定义, 它通常是列出该数据流的
各组成数据项 。
如,课程 =课程名 +教员 +教材 +课程表
课程表 ={星期几 +第几节 +教室 }
（ 2） 文件条目
文件条目给出某个文件的定义 。
订单文件 =订单编号 +顾客名称 +产品名称 +订货数量 +交货日期
（ 3） 数据项条目
数据项条目给出某个数据单项的定义 。
学号编号 =1～ 9999
（ 4） 加工条目
加工条目又称小说明 。 小说明中应精确地描述用户要求某个加工
做什么 。
2,结构化设计
结构化设计方法, 亦称 SD（ Structured Design） 方法 。 是
一种面向数据流的设计方法, 目的在于确定软件的结构 。
(1)SD方法的基本思想
其基本思想是：根据 SA方法中的数据流图建立一个良好的
模块结构图 （ 例如 SC图或软件层次方框图 ） ；运用模块化的
设计原理控制系统的复杂性, 即设计出 模块相对独立的, 模
块结构图深度, 宽度都适当的, 单入口单出口的, 单一功能
的模块结构的软件结构图或软件层次方框图 。
此方法提供了描述软件系统的工具, 提出了 评价模块结构
图质量的标准, 即模块之间的联系越松散越好, 而模块内各
成分之间的联系越紧凑越好 。
(2)SD方法的设计原理
1） 模块化,
模块化就是把系统划分为若干个模块, 从而获得满足问题需要
的一个解的过程 。
2） 模块的独立性,
模块独立性有两个定性的度量标准, 即内聚和耦合 。 耦合有六
种, 从小到大如下：
① 两个模块完全独立 （ 没有任何联系 ） ；
② 数据耦合,即两个模块只通过数据进行交换；
③ 状态耦合,即两个模块之间通过控制状态进行传递；
④ 环境耦合,即两个模块之间通过公共环境进行数据存取；
⑤ 公共块耦合,即多个模块引用一个全程数据区；
⑥ 内容耦合,即一个模块使用保存在另一模块内部的数据或控制
信息, 或转移进入另一个模块中间时, 或一个模块有多个入口时 。
由此看出 模块间耦合性越小越好 。
内聚有六种, 从小到大如下,
① 偶然内聚, 即一个模块由多任务组成, 这些任务之间关系松
散或根本没联系；
② 逻辑内聚,即一个模块完成的任务在逻辑上相同或相似；
③ 时间内聚,即一个模块所包含的任务必须在同一时间内执行；
④ 通信内聚,即一个模块内所有处理元素集中于相同的数据结
构；
⑤ 顺序内聚,即一个模块中所有处理元素都是为完成同一功能
而且必须顺序执行；
⑥ 功能内聚,一个模块所有处理都完成一个而且仅完成一个功
能 。
内聚性给出模块的内在联系, 因此 内聚性越大越好 。
3）模块的设计准则
①通过模块的分解和合并，提高模块的独立性；
②模块调用个数最好不要超过五个；
③降低模块接口的复杂性；
④一个模块的所有下属模块应该包括该模块受某一
判定影响的所有模块的集合；
⑤模块应设计成单入口和单出口；
⑥模块的大小要适中，一般在 50句左右。
(3)数据流图的类型
数据流图通常分为两大类型,转换处理型和事务处理型,
转换处理型,
由于大多数数据流图都可看成是对输入数据进行转换而得
到输出数据的处理, 因此可把这类处理抽象为转换处理型 。
转换处理过程大致分为输入数据, 变换数据和输出数据三步 ；
它包含的数据流有输入流, 转换流, 输出流三个部分 。 在输
入流中, 信息由外部形式转换为内部形式的结果；在输出流
中, 信息由内部形式的结果转换为外部形式数据流出系统 。
转换处理型的数据流图 。
事务处理型,
另一类数据流图可看成是对一个数据流经过某种加工后,
按加工的结果选择一个输出数据流继续执行的处理 。 这种
类型的处理可以抽象为事务处理型 。 在事务处理中, 输入
数据流称为事务流, 加工称为事务中心, 若干平行数据流
称为事务路径 。 当事务流中的事务送到事务中心后, 事务
中心分析每一事务, 根据事务处理的特点和性质选择一个
事务路径继续进行处理 。
(4)SD方法的设计过程
使用 SD方法的基础是数据流图。正如前面所述，几乎所有软
件在分析阶段都可以表示为数据流图，所以 SD方法基本上可适
用于任何软件的开发工作。
用 SD方法进行总体设计的过程大致如下,
（ 1） 研究, 分析和审查数据流图, 从软件的需求说明书弄清
楚数据流加工的过程；
（ 2） 根据数据流图确定数据流图的类型；
（ 3） 从数据流图导出系统的初始软件结构图；
（ 4） 改进初始软件结构图, 直到符合要求为止；
（ 5） 复查 。
(5)软件结构的描述方式
在 SD方法中, 软件结构用一种结构图来描述, 它是设计说明
书的一部分 。 结构图描述了软件模块结构, 并反映了模块和模
块间联系等特性 。
3,详细设计和编码
(1)详细设计的任务
为软件结构图中的每一个模块确定采用的算法和块内数据
结构, 用某种选定的表达工具给出清晰的描述 。
(2)详细设计的描述工具
① 程序流程图
也称为程序框图, 独立于任何一种程序设计语言, 比较直
观, 清晰, 易于掌握 。
任何复杂的程序流程图都可以由以下不同类型的基本结构
组合或嵌套而成：
顺序结构
选择结构 (IF-THEN-ELSE)
多分支选择结构 (CASE)
先判定循环结构 (WHILE)
后判定循环结构 (UNTIL)
(2)方框图 （ N-S图 ）,图形描述工具 。 限制了随意的控制转移 。
顺序结构 选择结构 多分支选择结构
先判定型循环结构 后判定型循环结构
(3)结构化编码方法
① 对源程序的编码要求,最基本要求是源程序的正确性, 同时
还要考虑其可读性, 可理解性, 可测试性和可维护性 。
② 写程序的风格,一个好的源程序意味着源程序代码逻辑简明
清晰, 易读易懂 。
编码原则：
? 程序内部文档应选取含义鲜明的名字, 注解正确, 程序清单
层次清晰, 布局合理 。
? 数据说明和次序应该标准化, 个别复杂的数据结构应加注释 。
? 每个语句应该简单直接, 不能为提高效率而使程序变得过份
复杂 。
? 对输入数据应进行合法性检查；对输出数据要加输出数据的
标志 。
? 在程序编码阶段以不影响程序的清晰度和可读性为前提, 尽
可能提高效率 。
1.2.2 面向对象开发方法
面向对象技术是一种非常实用而强有力的软件开发方法 。
面向对象软件开发方法又称 OOSD（ Object-Oriented Software
Development） 。 OOSD包括 面向对象分析 （ OOA）, 面向对
象设计 （ OOD） 和 面向对象程序设计 （ OOP） 三个方面 。 其
中 OOP是基础, OOA和 OOD是应用 OOP的机制 。
面向对象方法和技术是自 80年代以来逐渐形成的一种分析问
题和解决问题的新方法，其基本出发点就是尽可能按照人类认
识世界的方法和思维方式来分析和解决问题。客观世界是由许
多具体的事物或事件、抽象的概念和规则等组成的，因此，我
们将要 加以研究的事、物、概念都称为对象 。面向对象的方法
正是以对象作为最基本的元素，以对象作为分析问题，解决问
题的核心。
1,面向对象分析 （ OOA）
把对象作为现实世界的抽象表示, 然后定义对象的属性
和专门操纵那些属性的服务, 属性和服务被看成对象的特
征 。 具有相同的属性和服务抽象的一系列对象组成类 。 因
此在面向对象模型中, 它可以包含若干类, 并且它对应于
模型的不同层次, 因此 这些类有一定的层次关系和属性继
承关系 。
面向对象分析由五个主要步骤构成：
(1)标识对象
(2)标识对象属性
(3)定义对象的服务
(4)识别对象所属的类
(5)定义主题
2,面向对象的设计 （ OOD）
OOA是一个分类活动, 而 OOD模型由主体部件, 用户界面部件,
任务管理部件和数据管理部件四部分构成 。 每个部件又由主题词,
对象及类, 结构, 属性和外部服务五层组成, 它们分别对应 OOA
中的五个活动：定义主题词, 标识对象, 标识类, 标识对象的属
性和标识对象的服务 。 其中主体部件是整个设计的主体, 它包括
完成目标软件系统主要功能的所有对象, 用户界面部件给出人机
交互需要的对象, 任务管理部件提供协调和管理目标软件各个任
务的对象, 数据管理部件定义专用对象 。 要将目标软件系统中依
赖于开发平台的数据存取操作与其他功能分开, 以提高对象独立
性 。
概括地说, OOD方法是以 OOA模型为基础, 不断填入和扩展有关
软件设计的信息 。
3,面向对象编程
完成 OOD以后, 将开始进入编程阶段 。 目前主要选取面向对
象语言 (如 C++),基于对象的语言 (如 Ada),过程式语言 (如 C语
言 )。
1.3 软件测试与质量保证
1.3.1 软件测试原则
1,基本概念
软件测试定义,软件测试是为了发现错误而执行程序的过程 。
软件测试分为,单元测试和综合测试 。
软件测试在软件生存周期中横跨了两个阶段：通常在编写出
第一个模块之后就对它做必要的测试 （ 称作单元测试 ） 。 编
码与单元测试属于软件生存周期中的同一阶段 。 在结束这个
阶段之后, 对软件系统还要进行各种综合测试, 这是软件生
存周期的另一个独立的阶段, 即测试阶段 。
2,目标和原则
软件测试的目标可以归纳为以下几点：
1.测试是为了发现软件中的错误而去运行软件的过程 。
2.好的测试方案是尽可能地发现至今尚未发现的错误的测试
方案 。
3.成功的测试则是发现出至今未发现的错误的测试 。
1.3.2 软件测试策略与技术
1,软件测试策略
测试过程是按单元测试, 组装测试, 确认测试和系统测试四
个步骤进行的 。
1.单元测试（模块测试）
目的是发现模块的子程序或过程的实际功能与该模块的功
能和接口描述是否相符，以及是否有编码错误存在。单元测
试的主要内容有,模块接口测试；局部数据结构测试；重要路
径测试；出错处理能力测试；边界条件测试,
2.组装测试（集成测试或联合测试）
它的测试目的是为了发现程序结构的错误。组装测试过程中
的模块组织方式有非渐增式和渐增式两种。
① 非渐增式组装测试,又称一次性组装方式或整体拼装。
测试方式是先对每个模块分别进行测试。然后再把所以模块
组装在一起整体测试。
其 优点 是对各模块的测试可以并行进行, 有利于充分利用人力,
加快测试速度 。
其 缺点 是由于程序中不可避免的地存在涉及模块间接口, 全局
数据结构等方面的问题, 所以一次试运行成功的可能性不大,
结果是发现有错误, 但却找不到错误的产生原因 。
② 渐增式组装测试
这种方式是对一个个模块进行模块调试，然后将这些模块逐步
组装成较大的系统。在组装过程中，每连接一个模块便进行一次
测试，直到把所有模块集成为一个整体并进行测试，则软件的组
装测试完成。
在渐增测试过程中, 将模块结合起来的策略有两种：自底向上测
试和自顶向下测试 。
?自底向上测试,从程序模块结构的最低层模块进行组装和测试 。
因为模块是自底向上进行组装的, 对给定层次的模块的下层模块
处理功能总可以得到, 所以这种测试策略不必设计桩模块 （ 存根
模块 ）, 但要设计驱动模块 。
?自顶向下测试,将模块按系统程序结构, 沿控制层次自顶向下进行
组装 。 由主控模块开始, 按照程序的层次结构向下移动 。 逐渐把各
个模块组装起来 。
(3)确认测试 (有效性测试 )
又称有效性测试 。 组装测试结束后, 得到的是一个完整的软件
系统 。 这时需要进行最后的测试, 即有效性测试 。 有效性测试
阶段主要进行的测试有：有效性测试 （ 黑盒测试 ）, 软件配置
复查, α测试和 β测试以及验收测试 。
(4)系统测试
系统测试是指将经过测试后的软件系统与计算机硬件, 外设,
其他支持软件以及其他系统元素一起进行测试 。 测试内容主要
有：功能测试, 吞吐量测试, 可用性测试, 保密性测试, 安装
测试, 可恢复性测试, 资料测试和程序测试 。
2,常用的测试方法
常用的测试方法有黑盒测试和白盒测试两种 。
(1)白盒测试
白盒测试又称结构测试或逻辑驱动测试 。 所谓, 白盒, 是指
将对象看作一个打开的盒子, 测试人员可利用程序内部的逻辑
结构及有关的信息来设计或选择测试用例 。
白盒测试主要考虑的是测试用例对程序内部逻辑的覆盖程度,
而不考虑程序的功能 。
测试用例对程序的覆盖程序从低到高分别为,语句覆盖, 判
定覆盖, 条件覆盖, 判定 /条件覆盖, 条件组合覆盖 。
需要说明的是, 上述各种覆盖准则的侧重点不同, 覆盖程度
也不同 。 但它们共同的是,任何一种覆盖都不能做到完全测试 。
(2)黑盒测试
黑盒测试又称功能测试或数据驱动测试。
在这种测试方法中，程序对测试者是完全透明的。测试者
不考虑程序的内部结构和特性，就好像把程序看作一个不能打
开的盒子,只根据程序的需求规格说明中的程序功能或程序的
外部特性来设计测试用例。
黑盒测试的方法包括,等价分类法、边缘值分析法、因果
图法和错误推测法。
测试方法还有 回归测试, 强度测试 等等。每一种测试方法
都各有所长，在实际测试中应综合使用。一般来讲，通常用黑
盒法设计基本的测试方案，再利用白盒法做必要的补充。
1.3.3 软件质量保证
1,评审与测试
评审和测试都是质量保证的重要活动 。
验证：我们制造产品的步骤正确吗？
确认：我们制造的是正确的产品吗？
2,程序正确性证明
程序正确性证明就是要通过数学的方法, 证明程序具有某
些需要的性质 。 通过多年的研究, 现已提出了一些有用的方
法和技术, 其中包括输入 ——输出断言法, 最弱前置条件法,
结构归纳法纪等几种常用的方法 。
如果说程序测试是为了证明程序有错, 则程序正确性的证
明正好相反, 是为了证明程序能够完成某些预定的功能 。 现
有的证明程序正确性的技术与工具包括已研制出来的程序正
确性自动证明器, 仅适用于很小的程序 。 要解决大程序的正
确性证明, 还需要进行大量的工作 。
1.4 软件重用
重用 （ Reuse） 是软件过程的一部分 。 为了快速做出复杂的应用,
重用是一条捷径 。 此外, 重用也是当今软件系统的重要特征 。 重
用指在一个软件项目中直接使用以前项目中的产物, 而非重用某
些工具, 也就是把以前做过的东西纳入到新项目中 。
1,重用过程
面向对象的语言本身就提供了重用机制，如封装、继承、模板
等。技术上可以制成可重用构件（不仅封装数据还封装行为，成
为独立的可重用对象），这样可以大幅度提高开发效率。
重用的真正价值在于方案, 决策的重用 。 利用集成技术将构件按
可重用模式装入可重用框架 （ 相当于建筑中的梁, 柱组成的房梁 ）
构成一组装式软件过程 。
从代码重用到构件重用到设计重用到过程重用 （ 域工程 ）, 从初
创到成长到成就到实用 。 现代的软件平台, 或多或少都提供了重
用机制 。
2,支持重用的环境
从过程重用的观点, 以下 10种软件过程产物均可以重用：
① 项目计划 ② 费用估算 ③ 体系结构
④ 需求模型和规格说明 ⑤ 设计 ⑥ 源代码
⑦ 各种文档 ⑧ 人机界面 ⑨ 测试用例 ⑩ 数据
这些产物作为重用件要作分类, 标记, 作为对象构件放入构件
库 。 在当今 CIS分布系统上, 构件库是一个数据库服务器, 它
提供访问服务 。 重用环境还必须提供集成工具, 使重用的构件
能集成到新项目中 。
3,构件与构件重用
构件,是可重用的, 具有独立性的软件单元, 是用来构造其
他软件的部件 。
构件具有以下特点：
(1)构件是具有独立性的, 被封装好的, 具有描述能力的软件
单元 。
(2)构件本身不是一个完整的应用程序 。
(3)构件都有被定义好的接口, 只巴能通过这些接口来操纵构
件 。
(4)构件之间可以交互 。
(5)构件可以被扩展 。
构件的可继承性使构件能够被扩充和修改 。 目前有两个方面
的技术, 一种是可视化构件, 另一种是分布式对象构件 。
1.5 软件开发环境
软件开发由来已久 。 一台宿主机, 一个编译 （ 或汇编 ） 程序, 加
上编辑, 链接, 装入等少量实用程序, 就构成了早期软件开发的
舞台 。 从这个意义上讲, 在软件工程兴起之前就有了软件开发环
境 。
在 70年代和 80年代初期, 开发环境常被称为, 软件工程环境,
（ 简称 SEE或 SE2） 或, 程序设计支撑环境, 。
,计算机辅助软件工程, （ 简称 CASE）, 是今天对开发环境最流
行的称呼 。 成为描述软件开发环境与工具的最通用的名称 。
另一个常见的名称 ——“工作台, （ workshop） 。 1976年, ICSE第
二届会议在一篇文章中发表了一个基于 UNIX操作系统的程序设计
支撑环境, 称之为, UNIX程序员工作台, （ UNIX programmer?s
workbench,简写为 UNIX/PWB） 。 这是国际上出现的第一个有影
响的软件开发环境 。 自此之后, 工作台也常被用作开发环境的同
义词 。
2,集成化工具
开发软件用到 两类工具 。 一类工具是画或写在纸上的, 包括在不同
阶段使用的各种图形与语言；另一类则是 用来, 开发软件的软件,,
又称为, 软件工具, 或 CASE工具 。 这里讨论的是后一类工具 。
早期的环境只配置用于 编码阶段的工具, 也称为, 低层, CASE工
具 。 今天在 软件分析和总体设计等阶段也有了许多支持开发的 工具,
即, 高层, CASE工具 。 70年代出现了, 工具箱, 能部分地实现从
一个工具到另一个工具的切换 。 今天, 高, 低层 CASE工具由一组
专用程序和一个用来支持工具间数据交换的环境信息库构成的支持
下, 共同构成了具有统一的用户界面, 并能自动实现工具切换的
,集成工具,, 对软件开发的自动化提供了有力的支持 。
CASE环境还可能包括另 两个层次 。 一个是环境体系结构, 用于区
分开发环境为单机环境或网络环境；另一个是 可移植性服务程序,
它介于集成工具与宿主机之间, 使集成后的 CASE工具不需要作重
大的修改即可与环境的软, 硬件平台适应 。
小 结
软件工程是从工程角度来研究软件开发的方法和技术, 它
是在克服软件危机的过程中产生而发展起来的 。 软件工程学是
自软件工程出现以后形成的一门新兴学科 。
它包括的主要内容有,软件工程方法学, 软件工程环境和
软件工程管理等多个分支 。
一个软件从用户提出开发要求, 到废弃不用为止的全过程,
称为 软件的生存周期 。
软件的生存周期划分为 若干个阶段 （ 如：需求定义, 软件
设计, 编程, 测试, 运行维护等 ）, 每个阶段有相对独立的任
务 。
需求分析最常用的方法是 结构化分析方法 （ SA方法 ）, SA
方法适于分析大型数据处理系统, 使用的主要工具有数据流图
和数据词典 。 数据流图以图形形式表示软件信息流向和信息加
工, 而数据词典对这些信息和加工进行更详细的描述 。 SA方
法简单实用, 易于理解, 使用广泛 。
软件设计 可分为总体设计和详细设计 。
总体设计 通常使用 结构化设计方法 。 详细设计 是根据结构化
程序设计原则进行的, 只使用 顺序, 分支, 重复 三种结构来
设计模块的控制流程, 使用的表示工具有程序流程图, 方框
图, PAD图, 伪码 （ PDL语言 ） 等 。
软件编程 的任务是将软件详细设计的结果转换成某种程序设
计语言编写的源程序。
面向对象的方法 是在结构化程序设计的基础上, 进一步力图
用更自然的方法反映客观世界 。 在面向对象的系统中, 将数
据和使用该数据的一组基本操作或过程封装在一起, 用, 对
象, 这个概念来完整地反映客观事物的静态属性和动态属性 。
,面向对象, 的基本思想就是把要构造的系统表示为对象的
集合 。
软件测试 是为了发现错误而执行程序的过程。软件测试的 目的是
要暴露软件系统中的隐含错误,然后通过软件测试找出错误的原
因和位置并加以改正。在软件开发中，测试是保证软件正确性的
最后一个阶段，测试需要制定测试计划，设计测试用例，然后实
施测试，测试后进行分析评价，测试结束后，要给出测试报告。
软件测试方式分为,人工测试、动态测试和自动测试三种。测试
过程按单元测试、组装测试、确认测试和系统测试四个步骤。
常用的测试方法有黑盒测试和白盒测试两种 。对于不同的测试方
法，需要设计不同的测试用例。
阶段评审与测试,软件配置管理是保证软件质量的重要环节，软
件质量保证计划是确保上述环节实施的关键。
软件重用 和 CASE集成环境 是当今软件工程技术重要的两个方面,
重用技术已从代码重用发展到域工程, 是大规模生产软件的希望 。
集成技术在对象包装下, 当今分布式应用系统上已可实现数据集成,
控制集成, 表示集成 。
第二章 数据结构概述
随着计算机应用领域的不断扩大，非数值数据的处理变得尤
为重要，这些数据的元素之间在多是相互有关的。因此，讨论
数据元素之间的逻辑关系、数据元素在计算机中的存储方式及
在数据元素集合上设立的运算如何实现，这是研究数据处理的
基础。本章在介绍数据结构的有关概念后，着重讨论线性结构、
树型结构和图形结构等三类数据结构，最后介绍数据结构中两
种特别重要的运算 -查找和排序。
对数据结构的基本操作，本章采用 C语言描述。
2.1 概述
2.2 线性表
2.3 树型结构
2.4 图
2.5 查找
2.6 排序
小结
2.1 概述
?计算机早期运算,原始数据和结果数据不多,重点在于算法。
?计算机应用的发展,逐渐变成对数据进行非数值型的加工处
理为主。
?特点是数据量大，而计算的工作量可能很小。
?数据结构的提出：
数据结构是为研究和解决诸如数据的分类与查找, 情报检
索, 数据库, 企业管理, 系统工程, 图形识别, 人工智能以
及日常生活等各领域的非数值问题而提出的理论与方法, 即
如何合理的组织数据, 以提高算法的效率 。
? 重要性：对实现系统软件, 如操作系统, 编译程序和数据
库管理系统等均有十分重要的意义 。
2.1.1 数据结构的概念
? 数据,描述客观事物的的信息（数，字符，符号等）的集合，
是程序处理的对象。
? 数据元素,是数据集合中的个体，是构成数据对象的基本单位，
可由若干个数据项组成。
? 数据项,是数据的最小单位。
? 一组数据元素具有某种结构形式 。
? 数据结构,就是描述一组数据元素及元素间的相互关系的 。
? 数据结构描述了一组性质相同的数据元素及元素间的相互关系 。
用集合论给出的 数据结构的定义 为,
数据结构 S是一个二元组,S=(D,R)。
其中,D是一个数据元素的非空的有限集合 。
R是定义在 D上的关系的非空的有限集合
数据结构概念一般包括三个方面的内容：数据元素之间的逻辑
关系, 数据元素在计算机中的存储方式以及在这些数据元素上定
义的运算的集合 。
2.1.2 数据的逻辑结构
数据的逻辑结构有时可直接称为数据结构 。
数据的逻辑结构的三种基本类型：线性表, 树和图 。
分别属于两大类：
(一 )线性结构（线性表）
各数据元素之间的逻辑关系可以用一个线性序列简单地表
示出来 。
线性表是典型的线性结构, 它的数据元素只按先后次序联
接 。 有栈, 队列, 字串, 数组和文件 。
(二） 非线性结构（树，图）
不满足线性结构特点的数据结构称为非线性结构 。
树, 图等是非线性结构 。
树中的数据元素是分层次的纵向联接。
图中的数据元素则有各种各样复杂联接。
其它种类的数据结构由这三种基本结构派生的。
2.1.3 数据的物理结构
数据的逻辑结构在计算机存储设备中的映象称为数据的
存储结构 (亦称为物理结构 )。
同一个逻辑结构可以有不同的存储结构。
最常用的二种方式是：
顺序存储结构和链接存储结构 。
大多数据结构的存储表示都采用其中的一种方式或两种
方式的结合。
1.顺序存储结构
数据结构的 数据元素按某种顺序
存放在存储器的连续单元中。 即将逻
辑上相邻的数据元素存储在物理上相
邻的存储单元中，而数据元素之间的
关系由存储单元的邻接关系唯一确定。
若数据元素存放在以起始地址 S开始
的连续存储单元中 。 则第 i个元素的存
储地址：
LOC(i)=LOC(1)+(i-1)*l=S+(i-1)*l
假定每个元素所占的存储空间是相同的,长度均为 l。
数据的这种顺序存储结构叫做向量, 以 V表示, 向量 V的分量 V[i]
是数据结构的第 i个元素在存储器中的映像 。
顺序存储的主要特点 是：
1.结点中只有自身信息域，没有连接信息域。因此存储
密度大，存储空间利用率高；
2.可以通过计算直接确定数据结构中第 i个结点的存储地
址 L。 即可以对记录直接进行存取；
3.插入, 删除运算会引起大量结点的移动；
4.要求存储在一片连续的地址中 。
这种存储方式主要用于线性的数据结构 。
2.链接存储结构
存储数据结构的存储空间可以不连续,而数据元素之间的
关系是由指针来确定的。
主要特点是：
（ 1）结点由两类域组成：数据域和指针域。
（ 2）逻辑上相邻的结点物理上不必邻接，既可实现线性数据
结构，又可用于表示非线性数据结构。
（ 3）插入，删除操作灵活方便，不必移动结点，只要改变结
点中的指针值即可。
2.1.4 数据结构的运算
对一些典型数据结构中的结点进行操作处理 。
1.插入,在数据结构中的指定位置上插入新的数据元素；
2.删除,根据一定的条件,将某个结点从数据结构中删除；
3.更新,更新数据结构中某个指定结点的值；
4.检索,在给定的数据结构中,找出满足一定条件的结点来,
条件可以是某个或几个数据项的值；
5.排序,根据某一给定的条件, 将数据结构中所有的结点重
新排列顺序 等 。
从操作的特性来看, 所有这些运算的操作可以分为二类,
一类是加工型操作,操作改变了存储结构的值 （ 如插入,
删除, 更新等 ） ；
另一类是引用操作,操作只是查询或求得结点的值 （ 如
检索等 ） 。
2.2 线性表 ——最简单, 最常用的一种数据结构
2.2.1 线性表
线性是指表中的每个元素呈线性关系, 即除第一个外, 都
有一个直接前趋 (predecessor),同时除最后一个元素外, 都
仅有一个直接后继 (successor)。
1.线性表的逻辑结构
线性表 L用符号表示为：
L=(a1,a2,a3,.,ai...,an)
线性表也可以正式定义 为：
若数据结构 L=（ D,R） 是一个线性表,
则,D是包括 a1,a2,a3,....an 等元素的集合 。 R中只包含一个
关系, 即 R={<ai-1,ai> | ai-1,ai∈D, 2≤i≤n }。
关系 <ai-1,ai> 给出了元素的一种先后次序 。 a1 称为表的
线性起始结点, an 为表的终结点 。
2.线性表的存储结构
?存储结构,顺序存储结构和链接存储结构。
?具有顺序存储结构的线性表称为 顺序表,即用一组地址连续
的存储单元依次存储线性表中的每个数据元素。
?具有链接存储结构的线性表称为 线性链表 。
链式存储结构是用一组任意的存储单元来存储线性表中数据
元素的，这组存储单元可以是连续的，也可以是不连续的。通
常亦称为链表。
常用的链表有单链表、循环链表和双向链表。
3.线性表的基本运算
?常用的操作有,插入, 删除, 修改, 读值, 检索和排序等 。
?线性表还可以进行一些更为复杂的操作 。 如将两个或两个以
上的具有相同数据对象的线性表合并成一个线性表, 将一个线
性表拆成若干个线性表, 复制一个线性表等等 。 这些较为复杂
的操作都可以利用上述几种常用的操作来实现 。
(1)顺序表的操作
顺序表在各种高级语言里经常用一维数组实现。
#define MAXSIZE 100 //数组中元素个数的最大值
int list[MAXSIZE],n; //n为线性表中当前的结点数
① 插入运算
插入运算是在线性表的第 i个元素和第 i+1个元素之间插入一
个 一个新元素 x。
为了实现这个操作，必须把第 i+1个元素到第 n个元素依次向后
移位一个位置，以便把第 i+1个存储位置让出来，存储新元素 X。
假定已有一个链表 h,其 data域的值是由小到大排列的,现插入
一个新的结点 p0,要求插入后仍能保持由小到大的顺序 。
#define N 20
int a[N]；
main()
{ int i,data,n=10;
for(i=0; i<n-1; i++) scanf(“%d”,&a[i]);
scanf(“%d”,&data);
insert(a,n,data);
for(i=0; i<n; i++) printf(“%3d”,a[i]);
}
insert(int a[],int n,int data)
{ int i;
if (a[n-1]<data) a[n]=data;
else
{ a[n]=a[n-1];
for(i=n-1; i>0; i--)
if (a[i-1]>data) a[i]=a[i-1];
else { a[i]=data; break; }
if(i==0) a[0]=data;} }
当 i=0时,新结点 x插在 a1之前,这时需移动线性表中的所有元
素。
当 i=n-1时,新结点 x插入在 an-1之后,这时不需移动线性表中的
元素。
在具有 n个结点的线性表中，插入一个新结点时，其执行时间
主要化费在移动结点的循环上。移动结点的平均次数为：
?
?
?
n
i
i )n(p
0
1
22
1
1
1
1
1
1
1
10
n)n(n.
)n(in)in(n
n
i
n
i
???????? ??
??
② 删除运算
线性表的删除运算是指将线性表中第 i个数据元素除掉，
即把长度为 n的线性表
（ a1,a2,..,ai-1,ai,ai+1,...an)
中的 ai除去,变成长度为 n-1的线性表
（ a1,a2,..,ai-1,ai+1,...an)。
这只需将第 i+1数据元素到 n数据元素依次向前移动一个位
置即可。
设线性表用一维数组 a(N)存放，则在长度为 n的线性表中
删除值为 data元素,
函数如下：
int delete(int a[],int n,int data)
{ int i,j,k=0;
for(i=0;i<n;i++)
if(a[i]==data)
{ for(j=i;j<n-1;j++) a[j]=a[j+1];
/* 数据元素依次向前移动 */
a[n-1]=0; n--;k=1;break;
}
if(k==0) printf("No this element!");
return (n);
}
head,............,an 0a0 a1 a2
(2)线性链表的操作
单链表结点一般用结构体说明如下：
struct node
{ int data;
struct node *next;
};
① 单链表的插入
假定已有一个链表的表头为 h,其 data域的值是由小到大排列
的,现插入一个新的结点 p0,要求 插入后仍能保持由小到大 的顺
序,
考虑,
1.链表 h若为空,则将 p0的 next值为 NULL，并将 h指向 p0。
2.链表 h不是空表,则首先确定 p0的插入位置。则分三种情况,
① p0插在第一个结点之前：将 p0的 next指向 h的第一个结点，
然后将 h指向 p0。
② p0插在链表中间：若在 ai-1和 ai之间插入,可将 p0的 next指
向 ai; ai-1的 next指向 p0.
③ p0插在链表的末尾：将最后一个结点的 next指向 p0,而使
p0的 next置为 NULL。
......
p2 p1
p0
struct node *insert(struct node *h,struct node *p0)
{ struct node *p1=h,*p2;
if (h==NULL) { h=p0;p0->next=NULL;}
else
{ while((p0->data>p1->data)&&(p1->next!=NULL))
{ p2=p1; p1=p1->next;}
if (p0->data <= p1->data)
{ if(h==p1) h=p0; else p2->next=p0;
p0->next=p1;}
else
{ p1->next=p0;p0->next=NULL; }
}
return (h);
}
② 单链表的删除
在已给定的链表 h中,删除 data值为 m的结点。
1.链表 h是否指向空表,如果是空表,则报告空表信息。
2.若 h不为空,
① 一直查到表尾还找不到该结点,则在此链表中无此结
点。
②查找到该结点,
若该结点在头部,则 h指向该结点的下一个结点。
若该结点在中部,则前趋结点的指针指向后趋结点。
若该结点在尾部,则前趋结点的指针为 NULL。p2 p1
struct node *del(struct node *h,int m)
{ struct node *p1,*p2;
if(h==NULL)
{ printf("\n This null!\n"); return(h); }
p1=h;
while ((p1->data!=m)&&(p1->next!=NULL))
{ p2=p1;p1=p1->next; }
if(p1->data==m)
{ if(p1==h) h=p1->next;
else p2->next=p1->next;
free(p1);}
else printf("%d nod beed found! \n",m);
return(h);
}
实例：单链表的建立、打印和插入：
#define NULL 0
#define LEN sizeof(struct node)
#include "stdio.h"
struct node
{ int data; struct node *next; };
struct node * create() /* 建立链表 */
{ struct node *h=NULL,*p,*q; int x;
for(;;){ printf("Input data:"); scanf("%d",&x);
if(x<0) break;
p=(struct node *)malloc(LEN); p->data=x;
if(h==NULL) h=p; else q->next=p;
q=p; }
if(h!=NULL) p->next=NULL;
return(h); }
void print(struct node *h)
{ struct node *p=h;
while(p!=NULL) { printf("%d\n",p->data); p=p->next; }
}
struct node *insert(struct node *h,struct node *p0)
{ struct node *p1=h,*p2;
if (h==NULL) { h=p0;p0->next=NULL;}
else { while((p0->data>p1->data)&&(p1->next!=NULL))
{ p2=p1; p1=p1->next;}
if(p0->data<=p1->data)
{ if(h==p1) h=p0; else p2->next=p0;
p0->next=p1; }
else { p1->next=p0;p0->next=NULL; }
} return (h); }
main()
{ struct node *h,*p;int x;
h=create(); print(h);
p=(struct node *)malloc(LEN);
scanf("%d",&x); p->data=x;
insert(h,p); print(h); }
二, 循环链表
（ 1）循环链表的最后一个结点的指针域不为 NULL，而是指向头结
点，整个链表形成一个环。
（ 2）在循环链表中设置一个表头结点，使空表与非空表的运算统
一起来。
(a) 非空表 (b) 空表
图 2-2-5 带表头结点的循环链表
（ 1）插入算法,在头指针为 h的循环链表中元素 b的结点前插
入新元素 a.
struct node *inscst(struct node *h,int b,int a)
{ struct node *q,*p;
q=(struct node *)malloc(LEN);
q->data=a;
p=h;
while ((p->next !=h )&&((p->next)->data !=b))
p=p->next; /*寻找 指定元素的前一结点 */
q->next=p->next; p->next=q ;
return (h);
}
h
p
q
b
a
(2)删除算法,在头指针为 h的循环链表中删除元素为 b的结点
delcst(struct node *h,int b)
{ struct node *p,*q;
p=h;
while ((p->next !=h )&&((p->next)->data !=b))
p=p->next; /*寻找 指定元素的前一结点 */
if (p->next ==h)
{ printf(,No this node in the list\n”);
return(h);}
q=p->next ; p ->next=q->next;
free(q);
return(h);
}
b
p
q
三, 多项式相加
A(x)=3x14+2x8+1 B(x)=8x14-3x10+10x6
C(x)=A(x)+B(x)
设 pa,pb 指针
（ 1）若指针相等，则系数相加,c(x)中建项（系数为 0，不建）
（ 2）若 pa->exp>pb->exp 复抄 pa所指项，反之，复抄 pb所指项。
-1 3 14 2 8 1 0ah
-1 8 14 -3 10 10 6bh
cof exp
ch -1 1411 -310 2 8 10 6 1 0
pa
pb
pc
struct node1 *addpoly(struct node1 *ah,struct node1 *bh)
{ struct node1 *pa,*pb,*pc,*ch,*pp;
int x,e;
ch=(struct node1 *)malloc(LEN);
ch->exp=-1; ch->next=ch; pc=ch; /*建立新表头结点 */
pa=ah->next; pb=bh->next;
while((pa->exp!=-1)||(pb->exp!=-1))
{ if( pa->exp==pb->exp)
{ x=pa->cof+pb->cof; e=pa->exp; /*系数相加 */
pa=pa->next; pb=pb->next； /*修改指针 */
}
else if (pa->exp>pb->exp)
{ x=pa->cof; e=pa->exp; /*复抄 A(x)*/
pa=pa->next; }
else { x=pb->cof; e=pb->exp; /*复抄 B(x)*/
pb=pb->next; }
if (x!=0) /*形成新结点链入 C(x)*/
{ pp=(struct node1 *)malloc(LEN);
pp->cof=x; pp->exp=e;
pp->next=ch; pc->next=pp; pc=pp;
}
}
return(ch); }
多重链表,每个结点均有两个或两个以上指针的链表。
双重链表
设两个指针域：一个指向后继结点，另一个指向前趋结
点。
struct node
{ int data;
struct node *prio;
struct node *next;
}
图 2-2-6带表头结点的双向循环链表
a.插入运算
在已由小到大排列的带表头结点的双向循环链表 h中, 插入一
个新的结点 p0插入后, 要求仍保持由小到大的排列次序 。
struct node *insert2(struct node *h,struct node * p0)
{ struct node *p1
p1=h->next;
while((p0->data>p1->data)&&(p1!=h))
p1=p1->next;
p0->prio=p1->prio;
p1->prio->next=p0;
p0->next=p1;
p1->prio=p0;
return(h);
}
p0
p1
h
b.删除操作
在已给定的头结点 h的双向链表中, 删除一个 data值为 m的
结点 。
struct node * data(struct node *h,int m)
{ struct node *p1；
p1=h->next;
while((p1->data!=m)&&(p1!=h))
p1=p1->next;
if (p1->data==m)
{ p1->prio->next=p1->next;
p1->next->prio=p1->prio;
free(p1);
}
else printf(“%d not been found!\n”,m);
return(h);
}
h
m
p1
2.2.2 栈
栈是限定在一端进行插入与删除的线性表。允许插入和
删除的一端称为栈顶，而不允许插入和删除的另一端称为
栈底。
例如，给定 栈 (a0,a1,…,a n-1 ）
称 a0为栈底元素,an-1为栈顶元素。
栈是一种 后进先出 (LIFO--
Last In First Out)或先进后出
（ FILO)的线性表。
在栈中，元素的插入称为 进栈,
元素的删除称为 出栈 。
1.顺序存储的栈
顺序栈, 利用一组地址连续的存储单元依次存放自栈底到栈顶
的数据元素,同时设指针 top指示栈顶元素的当前位置。
假设用一维数组 s[max]表示栈，指针 top 指向栈顶元素, s[0]为最
早进入栈的元素,s[top] 为最迟进入栈的元素。当 top=max-1时，
为满栈,
初始化 top=-1 注,top,max 为全局变量
（ 1）进栈
push(int s[],int x)
{ if(top==max-1) printf(“Stack overflow!\n”); /*上溢 */
else s[++top]=x;
}
（ 2） 出栈
int pop(int s[])
{ int y=-1;
if(top==-1) printf(“Stack underflow!\n”); /* 下溢 */
else y=s[top--];
return(y); }
图 2-2-8 数据元素和栈顶指针之间的对应关系
假设有两个栈, 我们让它们共享一数组 s[m],因为栈
底位置是不变动的, 所以可将两个栈底分别设在数组空间
的两端, 然后各自向中间伸展 (如下图所示 ),显然, 仅当
两个栈顶相遇时才可能发生上溢 。 由于 两个栈之间可以做
到互补余缺, 使得每个栈实际可利用的最大空间大于 m/2。
2.链存储的栈
? 当栈的最大容量事先不能估计时，也可采用链式存储
结构的栈，称为 链栈 。
?一个链栈由它的 栈顶指针 top唯一确定。
如图 2.11所示。
这里 栈空的判别条件是 top是否为 NULL，而栈满将不
会发生,除非计算机的全部可利用空间都被占满。对一个
元素多变的栈来说，链式存储结构似乎更适宜。栈链的
运算实现也比较简单。
3.栈的应用
(1)子程序的调用和返回
当多个过程构成嵌套调用时，按照后调用先返回的原则，通
过栈来实现。
(2)表达式求值
栈的另一个重要的应用是在编译中用来求表达式的值 。
任何 一个表达式由三部分组成,操作数, 运算符和界限符 。
其中, 操作数可以是常量或标识符 （ 表示常量或变量 ） ；运算
符有算术运算符, 关系运算符, 逻辑运算符等, 在这里, 我们
只讨论算术运算符 。
算术运算符的规则：界限运算符有左, 右括号 (左括号运算级最
高, 右括号运算级最低 )及表达式结束符 #(#号的运算级最低 )。
要正确解释表达式，必须先了解 算术四则运算的规则 。
即：①先乘除,后加减；
②从左计算到右；
③先括号内,后括号外为
实现算符优先法必须使用两个工作栈,
一个 数栈 （ opnd），一个 运算符栈 (optr)，系统自左至右扫
描表达式，遇到操作数，则送入数栈，遇到运算符，则把它的
优先度与当前运算符栈顶运算符的优先度比较，若大于栈顶优
先符的优先度，则入栈，否则退栈，并以这个退栈运算符和从
数栈顶上退出的两个操作数形成一条机器指令。这样，一边形
成相应的机器指令，直到扫描到结束符，所有的栈空为止
计算表达式 运算符, ** / * + -
X=A*(B+C/D)-E*F**G 优先数, 4 3 3 2 2
A
B
C
D
Optr Opnd
(a)进栈后
*
（
+
/
A
B
T1
*
(
+
(b) T1=C/D
A
T2
*
(
(c) T2=B+T1
A
T2
*
(d)弹出左括号
T3
(e)T3=A*T2
T3
E
F
G
_*
**
(f)进栈后
T3
E
T4
_*
(g) T4=F* * G
T3
T5 _
(h)T5=E*T4
T6
(i)T6=T3_T5
求表达式 3*（ 7-2） 的值 。
optr opnd 输入字符 主要操作
1 # 3*（ 7-2） # push(opnd,3)
2 # 3 *（ 7-2） # push(optr,?*?)
3 #* 3 （ 7-2） # push(optr,?(?)
4 #*( 3 7-2） # push(opnd,7)
5 #*( 3 7 -2） # push(optr,?-?)
6 #*(- 3 7 2） # push(opnd,2)
7 #*(- 3 7 2 ） # operate(?7?,?-?,?2?)
8 #*( 3 5 )# pop(optr)
&& 一对 （ ） 出栈
9 #* 3 5 # operate(?3?,?*?,?5?)
10 # 15 # return
2.2.3队列
队列 （ Queue） 也是操作受限的线性表,
队列是一种先进先出 (FIFO)的线性表, (a1,a2,…,an )
允许在表的一端进行插入, 而在表的另一端进行删除, 允
许插入的一端叫做 队尾 （ rear）, 允许删除的一端则称 队头
（ front） 。
若限制插入和删除能在表的两端进行, 称此队列为, 双向
队, 。 若限制插入在表的一端进行, 而限制删除在表的另
一端进行,称此队列为, 单向队, 。
允许插入的一端称为队尾,允许删除的一端称为队首。
队列是一种先进先出（ FIFO)的线性表。
队列的基本运算 有以下四种,
① 获得队列的队首结点之值：
gethead(q,x)； 读取 q队列的队头元素于变量 x中,队
列不变 。
② 队列 q中插入一个结点,(进队 )
add(q,x)； 在队尾插入一个元素 x。
③ 队列 q中删除一个结点,（ 出队 ）
del(q)； 删除队头元素 。
④ 判队列 q是否为空：
empty(q)；
1.顺序存储的队
设置二个指针 front(队头 )和 rear(队尾 ).
存在“假溢出”现象,解决方法：采用循环队列（反转技术）
假设存储空间为数组 q[m],把队列数组的元
素 q[0]和 q[m-1]连接起来，形成一个环形的表。
初始值 front=rear=0
（ 1）进队 rear=(rear+1)% m;
q[rear]=x;
出队 front=(front+1) % m;
y=q[front];0
1
m-1
front
rear
a1
a2
a3
a4
(2)环形队列的队空和队满都有 rear == front
专门设立一个标志符
少用一个元素空间，用 (rear+1)/m == front作为队满的判
别条件
循环队列中入队和出队操作的具体算法
int front,rear,m; /*全局变量 */
addque(int q[],int x) /*进队算法 */
{ rear=(rear+1) % m;
if(rear == front) printf("Queen overflow!\n");
else q[rear]=x;
}
delque(int q[]) /*出队算法 */
{ int y=-1;
if(front == rear) printf("Queen undelflow!\n");
else { front=(front+1) % m;
y=q[front];
}
return (y);
}
2,链接存储的队
采用链式存储结构的队列称为 链队列 。
一个链队列需要队头和队尾的两个指针才能唯一确定 。
b,链式存储的队列
(1)进队算法 注,front,rear 是全局变量
add (int x)
{ struct node *q;
q=(struct node *)malloc(LEN);
q->data=x; q->next=NULL;
if (front==NULL)
{front =q; rear=q;}
else { rear->next=q; rear=q; }
}
(2) 出队算法 注,front,rear是全局变量
del( )
{ struct node *q;
int y=-1;
if(front==NULL)printf(“Queen nderflow!\n”);
else { q=front;
y=q->data;
front=q->next;
free(q);
}
return (y);
}
3．队列的应用
分时操作系统中,多个用户程序排成队列,分时地循环使
用 CPU和主存。
缓冲技术 ——系统为了解决高速的主机和低速的输入输出
设备之间的矛盾，在主存中开辟缓冲区，主机将要输入或输
出的信息先送至缓冲区，然后输入或输出设备从缓冲区中按
队列的先进先出原则依次取出数据，在这种情况下，主机不
必等待外部设备操作完就可以继续做其它的工作。
通常，缓冲区的结构为一个循环队列。
2.2.4 串
串 (String)也是一种特殊的线性表，即当线性表中的元素为
字符时的情形。
串定义：由零个或多个字符组成的有限序列，称为串。
一般记为,s=?a1a2… an? (n>=0)
线性表上的操作通常是对其中的单个元素进行的，如插入一
个元素，删除一个元素等。
对于串，经常要对其连续的字符组进行操作，如从正文中取
一个单词，替换一个单词等。
串的基本运算有：求串 s的长度的函数 len(s)； 求串 s的第 m位
置开始且长度为 n的子串的函数 sub(s,m,n)； 求子串 t在主串 s中
的位置的函数 index(s,t)； 串 v的值替换所有在串 s中出现的子串
t的值的函数 rep(s,t,v)及将串 s2的值紧接着放在串 s1的值的末
尾，联接成一个新串的函数 concat(s1,s2)等。
1.串的顺序存储
用一组地址连续的存储单元来存放字符串的值 。
为了唯一确定串, 需要设置两个变量, 一个是指向串第一
个字符位置的指针 sp,一个是指示串长度的整型变量 sl。
可以将串的长度和串值一起存于内存, 也可以用一个特定字
符作为串结束标志和串值一起存放, 这样就不需要设置 sl了 。
C语言就是用 NULL(?\0?)作为串结束标志的 。
不同的字符所占据的内存空间都是一个字节
c o m p u t e r \0
l l+1 l+2 …… l+8
图 2-2-14 顺序存储 r的串
2.串的链式存储
链表存储串值时,由于串中每个数据元素是一个字符,
因而存在一个结点大小的选择问题, 即结点中是存放一
个字符, 还是存放多个字符,
结点大小的选择直接影响对串和处理效率 。 结点越小,
串处理越方便, 但所占内存也随之扩大 。 反之, 结点越
大, 串处理越不方便, 但可以节省内存 。
串的基本运算
一, 求串的长度
main()
{ long le; long len(char [ ]);
char s[30];
scanf("%s",s); le=len(s);
printf("len(s)=%d\n",le);
}
long len(char s[])
{ long i=0;
while(s[i]!='\0') i++; return i;
}
二, 求子串 sub(s,m,n) 求串 s的第 m位置开始且长度为 n的子串。
三, 求子串 t在主串 s中的位置 index(s,t)
从主串 S的第一个字符起和模式 t的另一个字符比较，若相等，
则继续逐个比较后继字符，如果全部相等，则匹配成功，返回子
串的位置。否则从 S的第二个字符起重新开始新的比较，直至某
一步匹配成功或 S结束，无法再进行比较为止，此时返回 -1作为
匹配失败的标志。
index(char s[],char t[])
{ int i=0,j=0;
while (s[i]!='\0'&&t[j]!='\0')
{ if(s[i]==t[j]) { i=i+1; j=j+1;}
else {i=i-j+1; j=0;}
}
if(t[j]=='\0') return(i-j);
else return(-1);
}
四,字符串置换
rep(s,t,v)以串 v的值替换所有在串 s中出现的子串 t的值。
五,字符串连接
char *concat (char * s1,char *s2)
{ char *p;
p=s1;
while(*p++);
--p;
while(*p++=*s2++);
return(s1);
}
六, 字符串比较
int cmp(char s1[],char s2[])
{ int i=0,r;
while(s1[i]= =s2[i]&&s1[i]!='\0')i++;
if(s1[i]=='\0'&&s2[i]=='\0') r=0;
else r=s1[i]-s2[i];
return (r);
}
以下是 C语言提供的一些有关字符串的库函数：
unsigned strlen(char *str) /*字符串长度函数 */
char *strcat(char *str1,char *str2) /*连接函数 */
char *strcpy(char *str1,char *str2) /*拷贝函数 */
2.3 树形结构
树形结构是结点之间有分支、层次关系的结构，是一种
重要的非线性结构。树型结构在客观世界中广泛存在，如人
类的族谱和各种社会组织机构都可以用, 树, 来表示。
2.3.1 树的定义及其基本概念
树可以定义如下,
1)有且仅有一个称为根的结点；
2)除根结点之外的结点可分为 m(m>=0)个互不相交的有限集
T1,T2,...Tm,其中每一个集合本身又是一棵树, 并且称为
根的子树 。
这是一个递归的定义, 即在树的定义中又用到树本身这个术
语 。
树的基本概念
树的根结点,是树中一个特定的结点, 它是没有前趋的结
点 。
结点的度,树中每个结点拥有的子树的数目 。 度为 0的结
点为终端结点或叶子 。 度不为 0的结点称为非终端结点或
分支结点 。 树中各结点度的最大值称为树的度 。
子女与双亲,
兄弟,同一双亲的各子女间互称为兄弟 。
树的高度 (或深度 ):树中结点的最大层次 。
有序树和无序树,
m(m>0)棵互不相交的树的集合, 称为 森林 。
树结构有广泛的应用，经常被用来定义层次关系 。
用树表示算术表示式
(A+B)*5/(2*(C_D))
/
*
-
*
+ 5
A B C D
2
用树表示家庭结构
老张
张一 张二
张小一 张小二 张小三
2.3.3 二叉树
1.二叉树的概念：
二叉树定义 为：或为空, 或由一个根结点加上两棵分别称为左
子树和右子树的二叉树组成 。
二叉树不是树的特殊情况 。
它们之间最重要的区别是：二叉树的结点的子树要区分为左子
树和右子树, 即使在结点只有一棵子树的情况下, 也要明确指出
该子树是左子树还是右子树 。 二叉树允许空,而一般的树至少有
一个结点 。
完全二叉树 (见后图 )
一棵二叉树, 若所有的结点其度数或者为 0,或者为 2,则称
为完全二叉树 。
满二叉树,深度为 K且有 2K-1个结点的二叉树称为满二叉树 。
此时, 每一层上的结点数都是该层上的最大结点数 。
顺序二叉树,一棵深度为 K的二叉树, 如果它的叶结点都在第 K
层或第 K-1层上, 且对任一结点, 若其右子树中有叶结点在第 K
层, 则其左子树的叶结点都应在第 K层 。
从上述定义可以看出, 如果对一棵深度为 K的满二叉树和一棵
深度为 K,具有相同个结点的完全二叉树从根结点开始, 从上
到下, 从左到右进行连续编号那么相同位置上结点的编号完全
相同 。
完全二叉树 满二叉树 顺序二叉树
2.二叉树的性质
性质 1 在二叉树中,第 i层最多有 2i-1个结点 。
性质 2 在深度为 K的二叉树中,结点总数最多为 2K-1个, K≥ 1。
性质 3 对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2
的结点数为 n2,则 n0=n2+1。
设 n1为二叉树 T度为 1的结点数 。 因为二叉树 T中结点的度数
均小于或等于 2,所以其结点总数为,
n=n0+n1+n2 (1)
设 m为二叉树 T中总的分支数目 。 因为除根结点外, 其余结
点都有一个分支进入, 所以 m=n-1。 但这些分支是由度为 1或
2的结点射出的, 所以 m=n1+2n2,于是得
n=n1+2n2+1 (2)
由 (1)式和 (2)式得 n0=n2+1
性质 4 具有 n个结点的顺序二叉树的深度为 [log2n]+1。
假设树的深度为 K。 则根据性质 2和顺序二叉树为定义, 有
2K-1-1<n≤ 2k-1
或
2K-1≤n< 2k
于是 K-1≤log 2n<K
因为 K 是整数
所以 K=[ log2n ]+1
性质 5 如果对一棵有 n个结点的顺序二叉树的结点自上而下，
自左至右连续地从 1开始编号，则对任一结点 i(1≤i≤n),有
1)如果 i=1，则结点 i是二叉树的根，无双亲；如果 i>1，则其
双亲结点数是 [i/2]。
2)如果 2i>n，结点 i无左孩子 (此时结点 i为叶子 )；否则其左
孩子是结点 2i。
3)如果 2i+1>n,结点 i无右孩子；否则其孩子是结点 2i+1。
3.二叉树的存储结构
（ 1） 二叉树的顺序存储
用一组连续的存储单元存储顺序二叉树中的数据元素, 编号
为 i的结点的数据元素存放在相应向量中序号为 i 的位置上 。 根
据二叉树性质 5,结点 i的双亲存放在序号为 [i/2]的位置上, 结
点 i的左, 右孩子 (如果有的话 )将依次存放在序号为 2i和 2i+1的
位置上 。
这种方法对于一般二叉树空间浪费大，特别是单支树。
（ 2）二叉树的链式存储方式
当用链表表示二叉树时，结点至少包含数据域、左指针域
和右指针域，其结点 binode结构如下,
struct binode
{ int data;
struct binode *lchild;
struct binode *rchild;
}
A
B
D E
C
F G
A
B C
D E
F G
0 0
0 0
0 0 0 0
T
链表中会有许多空指针。
4.二叉树的遍历
所谓二叉树的遍历，是指树的每个结点按某种规律恰好被处理
（访问）一次的过程。
二叉树的遍历是一种最基本的算法 。 其含义是逐一访问树中的
各结点, 且只访问一次 。 从二叉树的递归定义可知, 二叉树是由
三个基本单元组成, 即根结点 (D),左子树 (L),右子树 (R)。 因此,
若能依次遍历这三部分, 便是遍历了整个二叉树 。
根据排列组合, 共有六种方案, 即 DLR,LDR,LRD,DRL,RDL，
RLD。
若对左右子树的访问次序限定是先左后右, 则只有前三种情况,
分别称为 先序遍历, 中序遍历和后序遍历 。 基于二叉树的递归定
义, 可得下述遍历二叉树的递归算法定义 。
遍历二叉树的递归算法：
三种方法：
先序遍历,若二叉树空，则空操作：否则：
(1)处理根 (2)按先序遍历左子树 (3)按先序遍历右子树
中序遍历,若二叉树空，则空操作：否则：
(1)按中序遍历左子树 (2)处理根 (3)按中序遍历右子树
后序遍历,若二叉树空，则空操作：否则：
(1)按后序遍历左子树 (2)按后序遍历右子树 (3)处理根
A
B
D E F G
C
H I
对左图的三种遍历：
先序,ABDEHICFG
中序,DBHEIAFCG
后序,DHIEBFGCA
先序遍历,ABDEGCF；
中序 遍历,DBGEACF；
后序 遍历,DGEBFCA。
若二叉树采用链式存储结构, 结点为,
struct binode
{ int data;
struct binode *lchild;
struct binode *rchild;
}
二叉树的 先序遍历算法的递归过程 描述如下,
preorder(struct binode *t) /* 先序遍历 */
{ while (t!=NULL)
{ printf("%d\n",t->data); /* 处理根结点 */
preorder(t->lchild); /* 遍历左子树 */
preordee(t->rchild); /* 遍历右子树 */
}
}
二叉树的 中序遍历算法的递归过程 描述如下,
midorder(struct binode *t) /* 中序遍历 */
{ while (t!=NULL)
{ midorder(t->lchild); /* 遍历左子树 */
printf("%d\n",t->data);
midordee(t->rchild); /* 遍历右子树 */
}
}
递归形式的算法描述过程精练，算法的正确性也容易得
到证明。
缺点：一是执行效率较低；二是要求编写程序用的高级
语言允许过程递归调用。
二叉树先序遍历的 非递归的过程 描述如下：
（ 此时需要用到栈 。 用指针数组 a表示栈, 记下尚待遍历的子
树根结点指针, 这也是栈的一种典型应用 。 ）
ppreorder(struct binode *t)
{ int i=0; struct binode *a[],*p;
a[0]=t;
while(i>=0) { p=a[i]; printf("%d\n",p->data);
/* 处理根结点 */
i--; if(p->rchild!=NULL)
{ i++; a[i]=p->rchild;}
/* 若右指针不为空, 则进栈 */
if(p->lchild!=NULL)
{ i++; a[i]=p->lchild;}
/* 若左指针不为空, 则进栈 */
}
}
二叉树 中序遍历的非递归 的过程描述如下：
（此时用到栈为链接栈。栈用于存放正在遍历的子树根结点指
针。）
struct snode
{ struct binode *addr;
struct snode *link; //定义链栈
};
midorder(struct binode *t) //t为树根
{ struct snode *top,*p; //链栈指针
top=NULL;
while(t!=NULL||top!=NULL)
{ while(t!=NULL)
{ p=(struct snode *)malloc(sizeof(struct snode));
p->addr=t;p->link=top;
top=p; t=t->lchild;
}
if (top!=NULL)
{ t=top->addr;
printf(“%c”,t->data);
p=top;
top=top->link;
free(p);
t=t->rchild;
}
}
}
实例：先建立一棵二叉树, 然后用中序遍历二叉树 。
#include "stdio.h"
#include "stdlib.h"
#define NULL 0
typedef struct node
{ char data;
struct node *le,*re;
}TREENODE;
TREENODE *root;
TREENODE * create_tree() /*建立二叉树 */
{ TREENODE *t;
char c;
c=getchar();
if(c=='#')return (NULL);
else{ t=(TREENODE *)malloc(sizeof(TREENODE));
t->data=c;
t->le=create_tree();
t->re=create_tree();
return(t);
}
}
void inorder(TREENODE *p)
{ if (p!=NULL)
{ inorder(p->le); printf("%c",p->data);
inorder(p->re); }
}
main()
{ TREENODE *root;
printf("Create Bin_Tree:"); root=create_tree();
printf("print Bin_Tree inorder:");
inorder(root);
}
运行情况：
Create Bin_Tree:a#bc###
print Bin_Tree inorder:acb
Create Bin_Tree:abd##ef##g##c##
print Bin_Tree inorder:dbfegac
如果给出一棵二叉树的 先序遍历结果和中序遍历结果,
或者给出 后序遍历结果和中序遍历结果, 我们就可画出该
二叉树；
如果只给此二叉树出先序遍历结果和后序遍历结果, 就
无法画出该二叉树 。
有两棵二叉树 T1和 T2,它们的先序和后序遍历结果完全
相同 。 显然只凭先序和后序遍历结果无法确定到底是哪一
棵二叉树 。
2.3.3 树的存储结构
树在计算机内有多种表示方法，下而介绍三种常用的方法。
1.双亲表示法
用一组连续空间存储树的结点, 同时在每一个结点中附设一个
指示器, 指示其双亲结点的位置 。
此结构很容易找到结点的双亲；但若要找到结点的孩子, 则
需遍历整个向量 。
2.孩子表示法
每个结点可能有多个孩子, 用多重链表来存储一棵树 。 链表
中的结点由一个数据域和若干个指针域组成, 每个指针域指向
该结点的一个孩子 。 由于树中每个结点的度数不同, 所以链表
中的结点可以采用定长表示, 也可以采用不定长表示 。
若树的度数为 d,则在定长结点表示中, 结点的结构为：
这里 data表示自身的数据，而 ch1,ch2...chd表示 1,2...d孩
子的指针，不同的结点其度数 d不同，因而结点的结构也不同。
在一棵有 n个结点度为 d的树中必有 n*d个指针域, 而有用的指
针域为 n-1,而有 n*(d-1)+1个空指针域 。
在不定长表示中, 结点的结构为,
(a)定长结点表示 (b)不定长结点表示
3.兄弟表示法
兄弟表示法又称 二叉链表示法 。 在这种表示法中, 结点
的结构为：
first_child data next_brother
把双亲表示法和孩子表示法结合起来 。
2.3.4 森 树与二叉树的转化,
在用多重链表表示一般的树时，若结点不定长，则对树的处理
很不方便；若用定长结点，则会浪费存储空间。另外，由于树中
各结点的度各不相同，因此，对树中各结点的搜索比较困难。在
实际应用中，往往将一般的树结构转化成二叉树。
转化方法：
（ 1） 在兄弟之间加一连线；
（ 2） 对每个结点, 除了其左孩子外, 去除其与其余孩子之间
的联系；
（ 3） 以树的根结点为核心, 将整树顺时针转 45度 。
A
B C D
E
J K
F G H I
L M N
A
B C D
E F G H I
J K L M N
任何一棵树所对应的二叉树，其 右子树必空 。也就是说，所有的
树都可以转化为二叉树，但 不是所有的二叉树都可以转化为 树。
森林转换成二叉树：
?若有三个结点，则就可能组成五种二叉树形式。
?若先序为 ABCDEFGHI
中序为 BCAEDGHFI
原则：根据先序定义,A必为根结点。
根据中序定义,A前的结点为左子树
A后的结点为右子树。
则组成的二叉树为：
二叉树的应用
二叉树的应用十分广泛, 常用于判定和对策, 例如假设有
12外表完全相同的球, 但其中有一个重量不合标准, 要求用
天平以最少的次数找出这个不标准球, 并判定它比标准球轻
还是重, 便可以用一系列的判定所构成的树来描述和解决 。
编制一个将百分数的成绩转化为优、良、中、及格和不及
格五级制表示的程序。
switch(grade/10)
{ case 10:case 9,g=”优, ; break;
case 8,g=”良, ; break;
case 7,g=”中, ; break;
case 6,g=”及格, ; break;
default,g=”不及格, }
成绩分布规律表
分数 0-59 60-69 70-79 80-89 90-100
比例 0.05 0.15 0.40 0.30 0.10
假设有 10000个学生成绩,a树需比较 31500次,b树需比较 20500
次,C树需比较 22000次。由此可见，结构不同的树是有优劣之分的。
而哈夫曼树是一类带权路径长度最短的树。亦称 最优二叉树 。
最优二叉树（ Huffman 树）
一,概念
路径：从树中一个结点到另一个结点之间的分支。
路径长度：路径上的分支数目 。
树的路径长度：从树根到每一个结点的路径长度之和 。
树的带权路径长度：为各端结点的权 Wk与相应的路径长度 Lk乘
积的代数和 。
即可表示为：
其中,Wk为各结点的权 （ 每个结点对应一个实数 Wk） 。
Lk为结点的路径长度 （ Lk为树的根结点到该结点长度,
实际为该叶子的祖先数, 也等于层次减一 ） 。
n为叶子结点数目 。
k
n
k
k LW P L W?
?
?
1
Huffman树的定义
给定一组正数 {w1,w2,.....wn}作为 n个权值，构成一特定的二
叉树（ n个叶子）使该树的 WPL为最小（ WPLmin)。
三, 构成 Huffman树的规则
（ 1） 根据给定的 n个权重 {W1,W2,...Wn}构成 n棵二叉树的森
林,F={T1,T2,...Tn},其中每棵二叉树 Ti中只有一个带权为 Wi的
根结点, 其左, 右子树为空 。
（ 2） 在 F中选取两棵结点的权植最小的树作为左, 右子树, 构
造一棵新的二叉树, 且置新的二叉树的根结点的权值为其左,
右子树上根结点的权值之和 。
（ 3） 在 F中删除这二棵树, 同时将新得到的二叉树加入 F中 。
（ 4） 重复 （ 2） 和 （ 3）, 直到只含一棵树为止 。
例如图 2.42中五个点 a,b,c,d,e(权重分别为 2,7,5,5、
4)来构造哈夫曼树的过程如下
Huffman算法的一个应用：
为信息 M0,M1....Mn-1求一组最佳编码，每个编码都是二进
制位串。若把 M0,M1....Mn-1的使用频率看作是对应的权，就可
用以 Huffman算法构造出一棵具有最小加权长度的译码树，使
得译码时间达到最小。
例：给定一些仅由五个字母 a,b,c,d,e组成的单词，它们使用
的频率依次为 10,5,20,10,18.
组成最优二叉树后，把向左分支记为 0，而向右的分支记为 1，
于是就得到一种编码。
a:011 b:010 c:11 d,00 e:10
0100110010的相应译码是 bade
001110111就得不到相应的译码。
2.4图
图是较线性表和树更为复杂的数据结构 。 在线性表中, 数
据元素之间仅有线性关系, 而在树中, 数据元素之间有着层
次关系 。 在图中, 任何两个数据元素之间都可能存在关系 。
2.4.1图的定义和基本概念
图的定义：
图 G(Graph)是由两个集合 V(G)和 E(G)组成的,记为,
G=(V,E)
其中,V(G)是顶点 (Vertex)的非空有限集合；
E(G)是边 (Edge)的有限集合, 边是顶点的有序对或无序对 。
图的基本概念
有向图 G的 E(G)是有向边 (也称为弧 )的有限集合，弧记为
<V,W>。
无向图 G的 E(G)是边的有限集合，记为 (V,W)或 (W,V)，因
为 (V,W)=(W,V)。
V1到 Vn的路径 (Path)：在一个图中，若从顶点 V1出发，沿
一些边经过顶点 V2,V3,...Vn-1到达顶点 V则称顶点序列
(V1,V2,V3,...,Vn-1,Vn)
与每个顶点相连的边数，称为该 顶点的度 。对于有向图，
顶点的度有 入度和出度 的区别，以顶点 V为头的弧的数目称
为 V的入度，以顶点 V为尾的弧的称为 V的出度。
2.4.2 图的存储结构
1.邻接矩阵表示法
邻 接矩阵表示各顶点间的邻 接关系 。
邻接矩阵的元素规定如下,
邻接矩阵表示法对求顶点的度很方便
在无向图中每个顶点的 度数 就等于邻接矩阵中与该顶点相
应的行或列中非零元素的个数；
在有向图中，每行的非零个数等于相应顶点的 出度,每列
的非零元素个数等于相应顶点的 入度 。
邻接矩阵用二维数组就可以存储。
2.邻接表
邻接表有一个顺序存储的结点表和 n个链接存储的边表组成 。
结点表的每个表目对应于图的一个结点, 每个表目包括两个字段,
结点的数据和指向此结点的边表的指针 。 图的每个结点都有一个
边表, 一个结点的边表的每个表目对应于该结点相关联的一条边,
每个表目包括两个字段：一个是与此边相关联的另一个结点的序
号,
2.4.3图的遍历
从图中某一顶点出发系统地访问图中所有顶点，且使每一
顶点仅被访问一次,这一过程就叫做图的遍历,
一, 深度优先搜索 (类同于树的先序遍历 )
从图中某个顶点 v0出发找到邻接顶点 w，再从 w出发找与 w邻
接的未访问的顶点，直至一个所有邻接点都被访问过的顶点 u，
然后退到尚有邻接点未被访问的顶点，从其出发重复上述过程
直至从任一被访问过顶点都无未被访问之邻接点为止。
1
3 2 4
5
visit
0
0
0
0
0
link
1
2
3
4
5
0
0
0
0
0
2 3 4
1 3 4 5
1 2
1 2 5
2 4
vertex next
深度优先搜索为, 1-2-3-4-5
一个图的深度优先搜序列不一定唯一，它与算法、图的存
储结构和初始出发点有关。
深度优先搜序列为, 1-2-4-8-5-3-6-7
1
32
5 6
0
0
0
0
0
1
2
3
4
5
0
0
0
0
2 3
3
1 4 5
1 6
2 8
2 8
6
7
8
4
8
7
07
0
3 0
04 5
0
0
0
遍历算法：
1.访问数初始化,visited的所有元素均为 false.
2.对尚未访问的数组调用深度搜索算法 dfs(g,v)。
3.深度搜索算法：
访问第 i个顶点，使 visited[i]=true,并访问。
对 i的尚未访问过的顶点的邻接顶点递归调用 dfs。
A.从 1出发,dfs(1),visited[1]=true
B.dfs(2),visited[2]=true
C.dfs(4),visited[4]=true
D.dfs(8),visited[8]=true
E.dfs(5),visited[5]=true
F.dfs(3),visited[3]=true
G.dfs(6),visited[6]=true
H.dfs(7),visited[7]=true
用一个 递归的过程 。假定图有 n个结点，采用相邻矩阵表示法。
那末图的深度优先搜索算法 dtraver具体描述如下：
dfs(int a[][n],int i,int n)
{ int j;
printf(“V=%-4d”,i);
visited[i]=1;
for(j=0;j<n;j++)
if(a[i][j]!=0 && visited[j]==0)
dfs(a,j,n);
}
dtraver(int a,int n)
{ int i;
for(i=0;i<n;i++)visited[i]=0;
for(i=0;i<n;i++)
if(visited[i]==0) dett(a,i,n);
}
数组 visited应作为全局变量来说明
非递归算法：要用栈。
dtraver1( struct node *link[],int visit[],int n,int v0)
{ int i,w; struct node *p;
for (i=1; i<=n; i++) visit[i]=0;
top=-1; printf(“v%5d”,v0);
visit[v0]=1; p=link[v0];
while((p!=NULL)||(top!=-1))
{ if(p!=NULL)
{ w=p->vertex;
if(visit[w]==0)
{ printf(“v%5d,”,w); visit[w]=1;
push(s,p->next); p=link[w]; }
else p=p->next;
}
else p=pop(s);
}
}
2,广 度优先搜索
从图中某顶点 V0出发，访问 V0后依次访问与 V0邻接的各个未
曾访问过的顶点，然后，分别从这些邻接点出发再访问与其相邻
接的但未被访问过的顶点，如此下去，直至所有邻接的顶点均被
访问过为止。
前图的 广度优先搜索为,1-2-3-4-5-6-7-8
需要使用一个队列 。实现遍历的处理过程如下：
1.把队列置空。
2.打印出发顶点，置该顶点已被访问的标志。
3.让出发顶点进队。
4.若队列不空，则：
(a)取出队首中的顶点 V。
(b)在邻接表中，依次取得与顶点 V邻接的各个顶点。
(1)若当前取得的邻接顶点未被访问，
则 ?打印该顶点，置该顶点已被访问的标志。
?该顶点进队。
(2)取得下一个邻接顶点。
(c)转 4
5.若队列空，则处理过程结束。
btraver1( struct node *link[],int visit[],int n,int v0)
{ int i,w; struct node *p;
for (i=1; i<=n; i++) visit[i]=0;
front=rear=m-1; printf(“v%=5d,”,v0);
visit[v0]=1; p=link[v0];
while((p!=NULL)||(front!=rear))
{ if(p!=NULL)
{ w=p->vertex;
if( visit[w]==0)
{ printf(“v%5d”,w); visit[w]=1;
addque(q,w);}
p=p->next; }
else
{ v0=delque(q );
p=link[v0];}
}
} /* 非递归算法 */
递归算法：
bfs(int a[][n],int i,int n)
{ int j,k,b1=-1,b2=0,b[n];
b[b2]=i;
while (b1<b2)
{ b1=b1+1;
k=b[b1];
visited[k]=1; printf(“V%=4d”,k++);
for(j=0;j<n;j++)
if(a[k][j]!= && visited[j]==0)
{ b2=b2+1; b[b2]=j;}
} }
btraver(int a[][n],int n)
{ int i;
for(i=0;i<n;i--) visited[i]=0;
for(i=0;i<n;i--) if(visited[i]==0) bfs(a,i,n);
}
练习：已知一个图如下所示, 若从顶点 a出发 深度优先搜索法
进行遍历, 则可能得到的一种顶点序列为,
按 广度优先搜索 进行遍历，则可能得到序列为
a-b-e-d-f-c
a-b-c-e-f-d
最短路径
求解最短路径有二种算法：
（ 1）求从某个顶点到其它顶点的最短路径。
（ 2）求每一对顶点之间的最短路径。
以下介绍第一种方法。
最短路径是指：如果从某个顶点出发，这个顶点称为源点，经
图的边到达另一顶点，这个顶点称为终点，所经过的路径不止
一条，找出一条路径使得沿此路径上各边的权值之和为最小。
最短路径也称为最小生成树。
构造最小生成树的方法：
1.设 V(T)初态为空
2.在连通图中任选一顶点加入到 V(T)集合中
3.下列步骤重复 n-1次
(1)在 i属于 V(T),j不属于 V(T)的边中选数值最小的边 (i,j)
(2)将顶点 j加入 V(T)中
(3)输出 i,j及 Wij
设图 G是一个具有 n个顶点的带权有向图，用代价邻接矩阵容
cost(i,j)表示图 G，矩阵元素定义为：
wij i≠j <i,j>∩E(G),w ij是 <i,j>边上的权
cost(i,j)= 0 i=j
∞ i≠j,<i,j> 不在 E(G)中
0 10 ∞ ∞ 19 21
10 0 5 6 ∞ 11
∞ 5 0 6 ∞ ∞
∞ 6 6 0 18 14
19 ∞ ∞ 18 0 33
21 11 ∞ 14 33 0
第 1次, U={v1} TE={}LW={((v1,v2)10,(v1,v3) ∞,(v1,v4)
∞,(v1,v5)19,(v1,v6)21}其中 min=（ v1,v2)10
第 2次, U={v1,v2} TE={(v1,v2)}LW={(v2,v3)5,(v2,v4)6,
(v1,v5)19,(v2,v6)11}其中 min=（ v2,v3)5
第 3次, U={v1,v2,v3} TE={(v1,v2),(v2,v3)}
LW={(v2,v4)6,(v1,v5)19,(v2,v6)11}其中 min=（ v2,v4)6
第 4次, U={v1,v2,v3,v4} TE={(v1,v2),(v2,v3),(v2,v4)}
LW={(v4,v5)18,(v2,v6)11}其中 min=（ v2,v6)11
第 5次, U={v1,v2,v3,v4,v6} TE={(v1,v2),(v2,v3),(v2,v4),(v2,v6)}
LW={(v4,v5)18}其中 min=（ v2,v6)18
#include,stdio.h”
main()
{ int i,j,k,l,p,q,w,wmin; /* nv 网的结点个数 */
int nv,ne,v0,nw(46),t(11); /* ne— 网的边数 */
scanf(“%d,%d”,&nv,&ne); /* w—— 权值 */
for( i=1; i<=nv*(nv-1)/2; i++) nw(i)=1e4;
for( k=1; k<=ne; k++) { scanf(“%d,%d,%d”,i,&j,&w);
/* 输入 i<j 上半三角形 */
l=(j-2)*(j-1)/2+i; nw(l)=w; }
scanf(“%d”,&v0);
t(v0)=1;
for(k=1; k<=nv-1; k++)
{ wmin=1e4;
for(i=1; i<=nv; i++)
{ if( t(i)==1)
for( j=1; j<=nv; j++)
{ if( t(j)!=1)
{ if(i<j) l=(j-2)*(j-1)/2+i;
else l=(i-2)*(i-1)/2+j;
if( nw(l)<wmin)
{ wmin=nw(l);
p=i; q=j;
}
}
}
}
t(q)=1;
printf(,i=%d,j=%d,%d”,p,q,wmin);
}
}
2.5 查找
查找就是在数据结构中找出满足某种条件的数据元素 。 若
在数据结构中找到了这样的元素, 则称查找成功, 否则称查找
失败 。
2.5.1 线性查找法
1,顺序查找法
其 查找 过程为,从表的第一个元素开始, 将给定的值与表中各
元素的关键字逐个进行比较, 一直到找到相等的关键字, 则 查
找 成功；否则就是表中没有要找的元素, 查找 失败 。
seqsrch(int a[],int n,int k)
{ int i=0；
while(a[i]!=k && i<n) i++;
if(i<n) return(i);
else return(-1);
}
链表的查找：
#include <stdio.h>
struct node { int data;
struct node *link;}head;
struct node *seqe(struct *head,int v)
{ for( ; head!=NULL&&head->data!=v ; )
head=head->link;
return(head);
}
2.对半查找法,只适用于有序线性表
以顺序方式存放的有序表的查找可采用对半 查找 。
将被查关键字 k与线性表中间位置 m上的数据元素的关键字进行
比较：
（ 1）若 k==a[m]，则查找成功，过程结束。
（ 2）若 k>a[m],则取表的后半部分作为新表再去查找。
（ 3） 若 k<a[m],则取表的前半部分作为新表再进行查找。
这个过程一直进行到查找成功或子表的长度 为 0为止。
binsrch(int a[],int n,int k)
{ int l,h,m;
l=0;
h=n-1;
while (l<=h)
{ m=(l+h)/2;
if (a[m]==k) return(m);
else if(a[m]<k) l=m+1;
else h=m-1;
}
return(-1);
}
二分查找法要比顺序查找法快得多 ！
3,分块查找 (又称索引顺序查找）
,分块有序”表
(1) 表中数据分块 (2) 每块中的数据不必有序 (需知最大关
键字 ) (3) 块之间有序
,分块有序”表的结构有两部分：
(1) 顺序存储结构的线性表 (2) 索引表
分块查找过程：
(1) 用对半查找法查找索引表，确定待查项 x 所在的块。
(2) 在相应的块中用顺序查找法查找待查项 x。
2.5.2 二叉排序树及其查找
对半查找是基于关键字比较的最优方法。
但如果在查找失败时，想把待查关键字 k所对应的元素插入
到表中，或者在查找成功时，想把所查到的元素从表中删除，
对半查找就不太合适，因为它要化费大量的时间来移动有序表
中的元素，以达到插入、删除的目的。
二叉排序树定义,它或是一棵空树，或具有如下性质：
（ 1）若它的左子树不空，则左子树上所有的关键字均小于它
的根结点的关键字；
（ 2）若它的右子树不空，则右子树上所有的关键字均大于或
等于它的根结点的关键字；
（ 3）它的左、右子树也是二叉排序树。
如果按中序遍历二叉排
序树，那未就得到一个排
好序的结点序列。
10,17,18,20,40,50
二叉排序树的查找算法
在给定的二叉排序树 t中查找给定待查关键字 K：
1.如果树 t为空，那么查找失败。算法结束；否则，转 2。
2.如果 t->data等于 K，则查找成功。算法结束。否则转 3。
3.如果 K<t->data，那么 t=t->lchild,转（ 1） 。
否则 t=t->rchild,转（ 1） 。
递归算法
struct bnode
{ int data;
struct bnode * lchild;
struct bnode * rchild;
}
struct bnode *bansrch1(int k,struct bnode *t)
{ if (t==NULL) return(NULL);
else if(t->data==k) return(t);
else
if(t->data>k) return (k,bansrch1(t->lchild));
else return (bansrch1(k,t->rchild));
}
非递归算法
struct bnode
{ int data;
struct bnode * lchild;
struct bnode * rchild;
}
struct bnode *bansrch2(int k,struct bnode *t)
{ struct bnode *p;
p=t;
while((p!=NULL)&&(p->data!=k))
{ if ( p->data>k ) p=p->lchild;
else p=p->rchile;
}
return(p);
}
二叉排序树的插入过程
若二叉排序树为空, 则插入结点应为新的根结点, 否则根据
关键字比较的结果确定是在左子树还是在右子树中继续查找, 直
至某个结点的左子树或右子树空为止, 则插入结点应为该结点的
左孩子或右孩子 。
1,递归算法
insbtree(int k,struct bnode **t)
{ if(*t==NULL)
{ struct bnode *p;
p=(struct bnode *)malloc(sizeof(struct bnode));
p->lchild=NULL; p->rchild=NULL;
p->data=k;
* t=p;
}
else if((*t)->data>k) insbtree(&(*t)->lchild,k);
else insbtree(&(*t)->rchild,k);
}
2,非递归算法
struct bnode *insbtree(int k,struct bnode *t)
{ struct bnode *p,*q;
q=(struct bnode *)malloc(sizeof(struct bnode));
q->lchild=q->rchild=NULL; q->data=k;
if(t==NULL){ t=q; return(t); }
p=t;
while((p->lchild!=q)&&(p->rchild!=q))
{ if(k<p->data)
{ if(p->lchild!=NULL) p=p->lchild;
else p->lchild=q; } /*插入到左子树 */
else
{ if(p->rchild!=NULL) p=p->rchild;
else p->rchild=q;} /*插入到右子树 */
}
return(t);
}
二叉排序树的构造 就是从空树出发，依次输入表中的元素作为
结点，逐个插入二叉排序树的过程。
如果给定一个数据元素的集合，则数据元素的读入顺序不同，
其构造出的 二叉排序树的形态 也不同。
例, 序列 (53,61,12,37,90,100,3,78,45)，
(61,37,90,45,100,78,12,3,53),(3,12,37,45,53,61,78,90,100)
构造的二叉排序树分别为图 1，图 2 和图 3。
53
12 61
3 37 90
45 78 100
61
37 90
12 45
3 53
78 100
图 1 图 2
3
12
37
45
53
61
78
90
100
图 3
删除结点的算法：
1.首先调用 search（），从而确定被删结点在树中的位置。
2.如果被删结点不在树中，则算法结束。
3.如果被删结点在树中。则进行下面的删除：
(i)如果被删结点是根结点，那么
(a)若被删点无左子结点,则用被删结点的右子树作为删除后的树。
(b)若被删点有左子结点,则用被删结点的左子结点为根结点，同
时把被删结点的右子树作为被删结点的左子树按中序最后一个结
点的右子树。
(ii)如果被删结点是不是根结点，那么
(a)若被删结点无左子树，则
(1)如果被删结点是它的父结点的左子结点，那么把被删结点的右
子树作为被删结点的父结点的左子树。
(2)如果被删结点是它的父结点的右子结点，那么把被删结点的右
子树作为被删结点的父结点的右子树。
(b)若被删点有左结点，则把被删结点的右子树作为删结点的
左子树按中序最后一个结点的右子树。同时进行
（ 1）如果被删结点是它的父结点的左子结点，那么把被删结
点的左子树作为被删结点的父结点的左子树。
（ 2）如果被删结点是它的父结点的右子结点，那么把被删结
点的左子树作为被删结点的父结点的右子树。
（ iii)回收被删结点的存储单元，算法结束。
以上的删除算法并不是唯一的，可以采用其它算法，只要在删
除结点后，使得树仍然是一棵查找树就行。
删除结点算法
struct bnode *destree( struct bnode *t,struct bnode *p,
struct bnode *f)
{ struct bnode *s,*q;
if (p->l == NULL) /*被删结点 p没有左子树 */
{ if (p ==t ) t=p->r;
else s=p->r;
}
else if (p->r== NULL) /*被删结点 p没有右子树 */
{ if (p==t) t=p->l;
else s=p->l;
}
else /*被删结点 p有左, 右子树 */
{ q=p； /*找左子树中的极右结点代替删去结点的位置 */
s=q->l;
while( s->r!=NULL) { q=s; s=s->r ; }
s->r =p->r ;
if ( q!=p){ q->r =s->l; s->l=p->l; }
if ( p==t) t=s ;
}
if ( p!=t)
{ if ( p==f->l) f->l=s;
else f->r=s;
}
free(p);
return(t);
}
注,t —— 指向根结点指针
f —— 指向被删除结点的双亲结点的指针
p —— 指向被删结点的指针
2.6 排序
就是将一个数据元素的无序序列，按其关键字的大小重新排列，
最后变成一个有序序列。
内部排序：整个排序过程都在计算机内存中进行。
外部排序,排序过程必须借助外存储器进行。
2.6.1 选择排序
基本思想,每一趟在 n-i-1个记录中选出关键字最小的记录作为有
序序列的第 i个记录。
1.直接选择排序
基本方法 是：每次从待排序的文件中，选出关键字最小的 (或最
大的 )记录，放在已排序的记录的后面，直到全部排好序为止。
具体操作 为：先在待排序文件中选出关键字最小的记录，把它
与第一个记录交换存储位置，然后在余下的记录中再选出关键字
次最小的记录与第二个记录交换，重复此过程，直至所有记录为
有序序列为止 。
初始状态 45 21 34 19 52 60 34 24
第一趟 [19] 21 34 45 52 60 34 24
第二趟 [19 21] 34 45 52 60 34 24
第三趟 [19 21 24] 45 52 60 34 34
第四趟 [19 21 24 34] 52 60 45 34
第五趟 [19 21 24 34 34] 60 45 52
第六趟 [19 21 24 34 34 45] 60 52
第七趟 [19 21 24 34 34 45 52] 60
有序文件 19 21 24 34 34 45 52 60
具体算法 描述如下,
selsort(int a[],int n)
{ int i,j,k,x;
for(i=0;i<n-1;i++)
{ k=i;
for(j=i+1;j<n;j++) if(a[j]<a[k]) k=j;
if(k!=i) { x=a[i]; a[i]=a[k]; a[k]=x;}
}
}
2.堆排序
堆排序是对选择排序的改进。
基本思想,当用 n-1次比较选择出最小的一个关键字后, 在余下
的关键字选择中, 若能利用前面己进行的比较所得的有用信息, 则
可以减少关键字的比较次数 。
堆,对于树 T中的任一结点的值不大于它的左子结点的值, 且不
大于它的右子结点的值, 那么称树 T是一个堆 。
即对任意 i,若 R2i+1,R2i+2 存在, 并且满足
Ki<=K2i+1
Ki<=K2i+2 i=0,1,2… [n/2]
则称之为堆 。
从定义可以看出, 堆顶记录的关键字 K0,必是所有记录中关键字
最小的一个 。
则从根结点开始, 从上到下, 从左到右, 对顺序二叉树进行遍
历, 所得结点序列就是一个从小到大的序列 。
这样的处理过程为 堆排序 。
堆的输出,
先输出堆顶记录之后, 用堆中最后一个记录代替 。 如下图
(A)所示, 此时根结点的左, 右子树均为堆 。 比较左, 右子树
的根结点, 由于右子树的根结点的值小, 交换根结点和右子
树根结点的值, 如下图 (B)所示的状态 。 对右子树重复上述过
程, 直至叶子结点 。 这时便建成了一个新堆, 如下图 (C)所示 。
(A) (B) (C)
堆 {5,20,10,40,30,50,25,60}形成的顺序二叉树 。
堆排序的基本思想是,
将一组待排序的关键字，按堆的定义排成一个序列，这
就找到了最小关键字。然后将最小关键字取出，用余下的关
键字再建堆，便得到了次最小的关键字。如此反复，直到将
全部关键字排好序为止。
从堆顶至叶子的调整过程称为筛选。一般地，如果以
a[s+1],a[s+2],a[s+3],… a[t]为根的子树都是堆，则将 a[s]筛选
到合适位置，使得以 a[s],a[s+1],a[s+2],a[s+3],… a[t]为根的子
树都是堆。
堆的筛选算法：
soft(int a[],int s,int t)
{ int i=s,j=2*i+1,k=a[i];
while(j<=t)
{ if (j<t && a[j]>a[j+1]) j++;
/* j为两叶子结点中小结点的下标 */
if (k>a[j])
{ a[i]=a[j]; i=j; j=2*i+1;
} /* 如果根大于叶子结点, 则交换 */
else j=t+1; /* */
}
a[i]=k;
}
建堆过程,对一棵顺序二叉树, 各叶子结点没有孩子, 它们
自然符合堆的定义 。 对具有 n个结点的顺序二叉树来说, 最后一
个非终端结点是第 [n/2]个记录 。 我们从第 [n/2]个记录起开始
筛选, 直到第 1个记录止, 则 a[n]就是一个堆 。
heepsort(int a[],int n)
{ int i,k;
for(i=n/2;i>=0;i--)
soft(a,i,n-1); /*将 a[0..n-1]建成一个堆 */
for(i=n-1;i>0;i--) { k=a[i]; a[i]=a[0]; a[0]=k;
/* 将堆顶和未排序子序列 a[0..i-1]中最后一个记录相交换 */
soft(a,0,i-1); }/*将 a[0.,i-1]重新调整为堆 */
for(i=0;i<n/2;i++) /*建的堆是从大到小排序, 再交换 */
{ k=a[i];a[i]=a[n-1-i]; a[n-1-i]=k;}
}
例：有序 列 a(15,17,33,22,51,41,90,28,67)利用堆排序过程。
首先将序列 a建成堆, a(15,17,33,22,51,41,90,28,67)
第 8次,a[0]与 a[8]交换为,a(67,17,33,22,51,41,90,28,15)
再建堆为,a(17,22,33,28,51,41,90,67,15)
第 7次,a[0]与 a[7]交换为,a(67,22,33,28,51,41,90,17,15)
再建堆为,a(22,28,33,67,51,41,90,17,15)
第 6次,a[0]与 a[6]交换为,a(90,28,33,67,51,41,22,17,15)
再建堆为,a(28,51,33,67,90,41,22,17,15)
第 5次,堆为,a(33,51,41,67,90,28,22,17,15)
第 4次,堆为,a(41,51,90,67,33,28,22,17,15)
第 3次,堆为, a(51,67,90,41,33,28,22,17,15)
第 2次,堆为, a(67,90,51,41,33,28,22,17,15)
第 1次,堆为, a(90,67,51,41,33,28,22,17,15)
最后交换得, a(15,17,22,28,33,41,51,67,90)
2.6.2 交换排序
基本方法,两两比较待排序记录的关键字，并交换不满足顺序要求
的那些偶对,直至全部满足为止。
1.冒泡排序
将待排序文件中的记录两两比较, 若为逆序, 则进行交换 。 按此
方法将文件从头到尾处理一遍称作一趟起泡 。 一趟起泡的结果是将
关键字最大的记录交换到了表尾 。 对余下 n-1个记录, 重复此过程,
直至文件排好序为止 。 若某一趟起泡过程中没有任何交换发生, 则
表明此时文件已经排好序了, 不必再继续重复起泡过程 。
初始状态 [45 21 34 19 52 60 34 24]
第一趟 [21 34 19 45 52 34 24] 60
第二趟 [21 19 34 45 34 24] 52 60
第三趟 [19 21 34 34 24] 45 52 60
第四趟 [19 21 34 24] 34 45 52 60
第五趟 [19 21 24] 34 34 45 52 60
第六趟 19 21 24 34 34 45 52 60
具体算法：
bubsort(int a[],int n)
{ int i,j,k,s;
k=1; j=n-1;
while (k==1 && j>=0)
{ k=0;
for(i=0; i<j; i++)
if(a[i]>a[i+1])
{ k=1;
s=a[i]; a[i]=a[i+1]; a[i+1]=s;
}
j--;
}
}
开关量 K的作用是当其趟无交换时, 即终止程序的运算 。
2.快速排序
基本思想,通过一趟分割将线性表分成两部分，其中前一部
分的所有元素值均不大于后一部分中的每一元素值；然后对
每一部分再进行分割，直到整个线性表有序为止。
具体算法,设置两个指针 i和 j，其初始状态分别指向文件
中第一个记录和最后一个记录。先将第一个记录移向辅助变
量 x中，然后从 j所指位置起向前搜索第一个关键字小于 x的记
录，找到后，将 a[j]移至 a[i]的位置；再从 i 所指向的位置后
搜索第一个关键字大于 x的记录，找到后，将 a[i]移至 a[j]的
位置；重复这两步过程，直至 i==j，最后将 x送至 a[i]中去。
至此一趟排序完成，文件划分为两个子文件。
初始状态 45 21 34 19 52 60 34 24
i j
一次交换 24 21 34 19 52 60 34 24
i→ j
二次交换 24 21 34 19 52 60 34 52
i ←j
三次交换 24 21 34 19 34 60 34 52
i→ j
[24 21 34 19 34] 45 [60 52]
ij
(a) 一趟排序
初始状态 [45 21 34 19 52 60 34 24]
第一趟 [24 21 34 19 34] 45 [60 52]
第二趟 [19 21] 24 [34 34]
第三趟 19 21
第四趟 34 34
第五趟 52 60
有序文件 19 21 24 34 34 45 52 60
(b) 全部快速排序
一趟快速排序算法,
int i,j;
qkpass(int s,int t,int a[] )
{ int x,i,j;
i=s;j=t;x=a[i];
do{while(i<j && a[j]>=x) j--; /*自右向左扫描 */
if(i<j)
{ a[i]=a[j]; i++;}
while(i<j && a[i]<=x) i++; /*自左向右扫描 */
if(i<j)
{ a[j]=a[i]; j--;}
}while(i!=j);
a[i]=x;
return i;
}
递归算法
qksort(int a[],int s,int t)
{int i;
if (s<t)
{ i=qkpass(s,t,a); qksort(a,s,i-1);
qksort(a,i+1,t);
}
}
非递归算法,
qksort1(int a[],int n)
{ int l=0,p=n-1;
top=-1; push(s,l,p);
while(top!=-1)
{ pop(s,&l,&p);
while(l<p)
{ qkone(a,l,p); push(s,i+1,p); p=i-1;}
}
}
2.6.3 归并排序
前面介绍的几种排序方法, 对排序文件的初始状态都不作
任何要求, 而归并排序是另一种类型的排序方法 。
基本思想,采用二路归并技术, 即每次将数组 a中两个相邻的
有序序列归并为一个有序序列 。 类似地还有三路归并技术和
多路归并技术 。
整个排序过程 为：
假设待排序文件含有 n个记录，则可看成是 n个有序的子
序列，每个子序列的长度为 1，然后两两归并，得到 [n/2]个
长度为 2或 1的有序子序列，再两两归并。如此重复，直到得
到一个长度为 n的有序文件为止。
初始状态 [45] [21] [34] [19] [52] [60] [34] [24]
┕━━┙ ┕━━┙ ┕━━┙ ┕━━┙
第一趟 [21 45] [19 34] [52 60] [24 34]
┕━━┙ ┕━━┙
第二趟 [19 21 34 45] [24 34 52 60]
┕━━━━━━┙
第三趟 19 21 24 34 34 45 52 60
二路归并排序过程示例
有序文件 a[s..m]和 a[m+1...t]归并为 b[s..t]的算法,
merge(int a[],int s,int m,int t,int b[])
{ int i,j,k;
i=s; j=m+1; k=s-1;
while(i<=m && j<=t)
{ k++;
if(a[i]<=a[j])
{ b[k]=a[i];i++; }
else { b[k]=a[j];j++; }
}
if(i>m) for(;j<=t;j++){ k++;b[k]=a[j];}
else for(;i<=m;i++){ k++;b[k]=a[i];}
}
其中,i是 a[s..m] 的指示器；
j是 a[m+1..t] 的指示器；
k是 b[s..t] 的指示器 。
有了 merge算法，就可以写出 一趟归并算法 。假设每个子文件的
长度为 k，归并结果存放在数组 b中，则一趟归并描述如下,
mergepass(int a[],int k,int n,int b[])
{ int i=0;
while (n-i>=2*k)
{ merge(a,i,i+k-1,i+2*k-1,b);
i=i+2*k;}
if(n-i>k) merge(a,i,i+k-1,n-1,b);
else for(;i<n;i++) b[i]=a[i];
}
第一趟归并后, 有序子文件长度为 2,结果在 b中；第二趟归并后,
有序子文件长度为 4,结果在 a中 。 重复此过程, 直到有序子文件为
n,则归并排序结束 。 具体算法描述 如下,
mergesort(int a[],int n)
{ int k=1,b[n];
while(k<n)
{ mergepass(a,k,n,b); k=2*k; mergepass(b,k,n,a); k=2*k;
} }
小 结
本章介绍了数据结构的一些基本概念和主要的运算 。
数据结构 是描述数据元素及元素间的相互关系 。 数据结构的
概念一般包括三个方面内容：数据之间的逻辑关系, 数据在计
算机中的存储方式以及在这些数据上定义的运算的集合 。
数据的 逻辑结构 直接称作数据结构, 它抽象地反映数据元素间
的逻辑关系 。 数据的逻辑结构有三种基本数据结构：线性表,
树和图 。 这三种基本数据结构又分为线性结构 （ 线性表 ） 和非
线性结构 （ 树和图 ） 。
数据的逻辑结构在计算机存储设备中的映象称为数据的 存储
结构 (亦称为物理结构 )。 最常用的二种方式是：顺序存储结构
和链接存储结构 。 大多数据结构的存储表示都采用其中的一种
方式, 或两种方式的结合 。
线性表是最简单的, 也是最基本的一种数据结构 。 栈和队列
是两种操作受限的线性表 。 串也是一种特殊的线性表 。
树形结构 是一种重要的非线性结构 。 二叉树是另一种树形
结构, 二叉树有三种遍历方法, 称为先序遍历, 中序遍历和
后序遍历 。 二叉树的应用十分广泛, 可以用于判定和对策,
其中哈夫曼树是一类带权路径长度最短的树 。
图 是较线性表和树更为复杂的数据结构, 同一个图可以有
多种多样的遍历顺序 。 通常采用的遍历顺序有两种, 深度优
先搜索和广度优先搜索 。 它们对有向图和无向图都适用 。 图
的一个重要应用就是求网络的最小生成树 。
查找 就是在数据结构中找出满足某种条件的数据元素 。 查
找的方法有线性查找和二叉排序树查找等 。
排序 又称分类, 是数据结构中另一种十分重要的运算 。 其
功能就是将一个数据元素的无序序列, 按其关键字的大小重
新排列, 最后变成一个有序序列 。
第三章 操作系统
3.1 概论
3.2 处理机管理
3.3 存储管理
3.4 设备管理
3.5 文件管理
3.6 作业管理与用户界面
3.7 常见的操作系统
小结
3.1概论
计算机系统,由硬件和软件两部分组成。
硬件部分,指计算机物理装置本身 (裸机 )，即各种处理机、存
储器、输入 /输出设备和通讯装置。
软件部分,各种程序。
计算机系统中的软件一般分为 系统软件和应用软件 。
系统软件,用于计算机的管理、维护、控制和运行，其中最重
要的是操作系统。
应用软件,是指用户为了解决某一特定问题而编制的程序。
软件的作用,在计算机硬件基础上对硬件性能进行扩充和完善。
操作系统 是对硬件的首次扩充。
操作系统已成为现代计算机系统中必不可少的系统关键组成部
分。
3.1.1 操作系统的基本概念
CPU是 计算机硬件的核心和基础 -心脏。
操作系统是 软件的核心和基础 -大脑。
操作系统 控制和管理 计算机所有的系统硬件和软件。
计算机系统通常分为四个层次,
操作系统是加在裸机上的第一层软件。它是对裸机功能的首次扩
充。从结构看，操作系统是用户程序及系统软件与物理计算机之
间的接口。
对操作系统的描述一般有以下二种观点：
一是虚拟机的观点,把硬件全部隐藏起来，给用户提供一个友好
的、易于操作的界面。
操作系统的虚拟扩展功能体现在二个方面,
一是 系统功能的扩展,操作系统提供了系统调用，扩展了裸
机的基本指令系统，组成了虚拟机的高级指令系统。
二是 数量上的扩展,使多个用户可以同时使用一台机器,
二是资源管理的观点,操作系统管理计算机资源，并提供一个有
序的和可控的分配，使各种资源得到充分的使用和方便用户。
总之，操作系统是一种系统软件，由它来统一管理系统的资
源和控制程序的执行，是所有其它软件运行的基础，是用户使
用计算机的接口。
3.1.2 操作系统的特征和功能
由于多道程序系统出现, 使处理机与输入 /输出以及其它资源
得到充分利用, 但也由此带来不少新的复杂问题 。 因此, 一般
支持多道程序的操作系统具有并发执行, 共享, 虚拟技术 等一
些明显的特征 。
1.操作系统的特征
(1)迸发性
所谓 并发, 指两个或多个事件在 同一时间间隔 内发生 。 在
多道程序环境下, 并发性是指在一段时间内, 宏观上有多个程
序在同时运行, 但在单 CPU系统中, 每一时刻却仅能有一道程
序执行, 故微观上这些程序只能分时地交替执行 。
并发和并行 是两个不同的概念, 并行是一种物理的或微观的
同时性概念, 而并发是一种逻辑的或宏观上的同时性概念 。
(2） 共享性
即多个用户, 多道程序同时使用某个有限的系统资源 。 共
享性是多道程序计算机系统的一个最大特点, 是操作系统所追
求的主要目标之一 。
,并发, 和, 共享, 是操作系统的两个最基本特征, 它们
互为存在条件, 即资源共享是以程序的并发执行为存在条件,
没有并发执行, 就不可能有共享；反之, 若不能很好地实现共
享, 则程序的并发执行必将受到影响 。
(3） 虚拟技术
虚拟技术的目的在于向用户提供一个方便, 高效, 易于使
用的操作系统 。
所谓, 虚拟,, 就是把物理实体映射为一个或者多个逻辑
实体 。 物理实体是实际存在的, 而逻辑实体则是, 虚拟,
的, 只是用户的一种看法和感觉 。
例如, 在多道分时系统中, 虽然只有一个 CPU,但每一个终
端用户却都认为是有一个 CPU专门为他服务 。
多道程序技术的目的：
是在于充分利用处理机, 减少处理机等待时间 。
多道程序技术给操作系统带来了如下复杂性,
(1)多用户作业共享 CPU和输入 /输出设备, 操作系统要解决各
道程序之间的同步, 互斥和死锁问题；
(2)要有较大容量的存储器, 以便尽可能多的装入用户作业,
又必须防止各道程序之间的交叉和冲突, 及有意无意地破坏；
(3)必须有高效, 可靠和方便的文件系统, 能有效地管理文件 。
多道程序的操作系统是个大而复杂的系统软件, 并发性, 共享
性是导致操作系统复杂化的主要因素, 它们贯穿于整个操作系
统 。
2.操作系统的功能要点
操作系统的功能要点,系统资源的管理 。
操作系统的主要功能是使各种系统资源得到充分的, 合理
的使用, 及提供良好的用户界面 。 为了解决用户作业因争夺资
源而产生的矛盾和使多道程序有条不紊地运行, 操作系统应具
有以下 五个功能,
(1)处理机管理,主要解决在多道程序并发执行时如何合理分
配处理机
(2)存储器管理,使有限的内存尽可能装入多的作业 。
(3)设备管理,进行设备分配和具体的输入, 输出 。
(4)文件管理,外存空间管理及文件按名存取 。
(5)作业管理：,提供良好的用户接口 。
3.1.3 操作系统的发展
?计算机初创时,这一阶段没有操作系统,采用 人工操作方式 。
?50年代中期,用监控程序来管理用户所提交的程序, 这种自动定
序的处理方式称为, 批处理, 方式, 而且是串行执行作业, 因此称
为单道 批处理 。
?60年代中后期,允许多个程序同时存在于内存中, 由处理机以切
换的方式使多个程序可以同时运行 。 这时, 管理程序已经迅速地发
展成为一个重要的软件分支 --操作系统 。
?80年代中期, 通过通信系统, 把地理上分散的计算机群和工作站
设备联结起来, 达到数据通信和资源共享的目的, 发展成了 网络操
作系统 。
?操作系统进一步发展, 随着计算机硬件技术的飞速发展, 微处理
机的出现和发展, 出现了 分布式操作系统, 分布式操作系统是由多
个相互连接的处理资源组成的计算机系统, 它们在整个系统的控制
下可合作执行一个共同任务, 最少依赖于集中的程序, 数据或硬件 。
这些资源可以是物理上相邻的, 也可以是在地理上分散的 。 21世纪
将是分布式系统的时代 。
3.1.4 操作系统的分类
从操作系统工作的角度简介几种主要的操作系统 。
1.批处理操作系统
批处理,是指用户作业的成批输入并处理 ;
即系统将作业成批地输入系统并暂存在外存中, 组成一个后备
作业队列, 每次按一定的调度原则从后备作业中挑选一个或多个
装入主机处理, 作业完成后退出主机和后备作业装入主机运行均
由系统自动实现 。
批处理操作系统的目的,是减少人工操作, 减少作业建立和结
束过程的时间浪费 。
优点,是系统的吞吐量大, 资源利用率高, 系统开销较小 。
缺点,用户在其作业运行期间不能控制其作业的运行过程 。
同时在作业输入和输出过程中, CPU处于等待状态 。
主要配置在大型计算机系统上，希望有作业的大呑吐量，以
便充分利用系统资源。
2,分时操作系统
所谓, 分时,, 就是多个用户对系统资源进行时间上的分享 。
分时系统中 主机是一台功能强大的计算机, 连接多个终端, 主
机采用时间分片的方式轮流地为各终端上的用户服务 。 对每个
用户而言, 都仿佛, 独占, 了整个计算机系统 。
分时系统的基本特征是：
(1)多路性,系统按时间分片的原则为每个终端服务 。 宏观上,
多个用户通过终端同时工作, 共享资源；微观上, 各终端作业
轮流在时间片内进行处理 。
(2)独立性,每个用户的感觉自已好象独占着计算机系统 。
(3)及时性,系统对每一用户的输入请求能作出及时的响应 。
(4)交互性,用户通过终端采用人 -机会话的方式直接控制程序
运行 。
最早的分时系统是美国麻省理工学院在 1963年研制的 CTSS,用
于 IBM 7904机 。 IBM公司于 1968年推出的 TSS/360也是一个成功
的分时系统 。 目前最流行的分时操作系统为 UNIX。
3．实时操作系统
所谓, 实时, 是表示, 及时, 的意思。
实时系统又分为 实时控制系统 和 实时信息系统 (航空定票系
统、情报检索系统、信息查询系统等。 )二种。
实时系统的特征是：
（ 1）简单的交互能力（ 2）及时性响应（ 3）高可靠性。
实时系统与分时系统之间的 主要区别 在于：
?实时系统 一般是专用的, 其交互能力比较差, 只允许用户访
问数量有限的专用程序, 但系统响应时间要求极高 。
?分时系统 具有很强的通用性, 有很强的交互功能, 但响应时
间可以稍长, 以不超过用户的忍受范围为限 。
批处理系统, 分时系统和实时系统 是操作系统的三个基本类
型 。 而一个实用的操作系统可以是分别独立的一种系统, 也
可以是两两结合的或是三者兼而有之的通用操作系统 。
4,网络操作系统
计算机网络是地域位置不同, 具有独立功能的多台计算机系统,
通过通信线路与设备彼此互连, 在网络系统软件的支持下, 实现更
广泛的硬件资源, 软件资源及信息资源的共享 。
网络操作系统除了具有基本类型操作系统中所应具备的管理功
能和服务功能外, 还具有网络管理和服务功能, 这主要包括：
（ 1） 网络资源共享 （ 2） 网络通信 （ 3） 作业迁移 。
5,分布式操作系统
分布式操作系统也是通过通信网络将物理上分布的具有自治功能
的数据处理系统或计算机系统互连起来, 实现信息交换和资源共享,
协作完成任务 。 分布式系统要求一个统一的操作系统, 实现系统操
作的统一性 。 分布式操作系统管理分布式系统中的所有资源, 负责
全系统的资源分配和调度, 任务划分, 信息传输, 控制协调等, 并
为用户提供一个统一的界面 。
分布式操作系统是当今操作系统发展的一个重要方向 。
3.2处理机管理
在操作系统中处理机的管理被归结为 进程管理 。
进程 是操作系统分配资源及运行调度的基本单位。
进程管理的任务 是：协调各进程之间的运行活动；为各进程合理
分配资源；为进程提供各种系统服务；使所有的进程都能够正确而
有效地运行 。
3.2.1 进程与线程
进程 (process)的引入：
在单道程序系统中, 一个复杂的程序可以分为若干个程序段, 它
们必须依某种次序逐次执行, 且运行时独占整个计算机资源 。 在这
种环境下, 程序的顺序执行有如下特点,
1)顺序性,不同程序之间是顺序执行的 。
2)程序的封闭性,程序运行期间对其所占有的资源是封闭的 。
3)程序的可再现性,只要程序执行时的环境和初始条件相同, 程序
经多次运行后所得的结果也相同 。
程序顺序执行的优点为程序员检测和校正程序的错误带来很大方
便 。 它的缺点是系统的资源利用率很低 。
例,有三道程序在一个系统中运行, 该系统有输入设备, 输出设
备各一台 。 三道程序构成如下,
A:输入 32秒, 计算 8秒, 输出 5秒 。 共计 45秒 。
B:输入 21秒, 计算 14秒, 输出 35秒 。 共计 70秒 。
C:输入 12秒, 计算 32秒, 输出 15秒 。 共计 59秒 。
若程序按 A-B-C 的 次序顺序 执行, 则系 统运行时 间为
45+70+59=174秒 。
若使各设备并发执行, 也按 A-B-C顺序执行, 则执行情况为：
总计执行时间, 32+21+14+35+15=114秒
并发执行 提高了系统吞吐量, 但也产生了下述一些新特征 。
并发程序的特点,
1)异步性,每个程序都以各自独立的速度向前推进, 没有时
间上的规律性, 呈现走走停停的状态 。
2)失去程序的封闭性,并发执行时, 多个程序共享一台机器,
因而机内资源的状态将由多个程序来改变 。
例如,有两个 Pra和 Prb进程共同
对一个公共变量 n进行操作，变
量 n的初值为 0。
则运行次序可能为：
情况 1:Pra(n=n+1)
Prb(打印 n)(结果 n=1)
n=0；
情况 2:Prb(打印 n)(结果 n=0)
情况 3:Pra(n=n+1)
n=n+1；
Prb( 打印 n)(结果 n=2)
3)相互独立又相互制约,
各个程序作为独立的实体申请系统资源 。
但由于并发性和共享性, 并发程序之间常常相互依赖, 彼
此制约 。
相互制约有直接制约和间接制约 。
这时程序已不能很好地描述并发性问题, 引进了进程 。
1.进程
为了能对并发程序的执行加以描述而引入了进程的概念 。 进
程可以定义为,一个具有独立功能的程序关于某个数据集合的
一次运行活动 。
进程的基本特征
动态性,进程实质上是程序的一次执行过程 。
并发性,多个进程能在一段时间内同时运行 。
独立性,进程是一个能独立运行 。 独立分配资源和独立调度
的基本单位 。
异步性,每个进程按各自独立的,不可预知的速度向前推进 。
结构特征,称为, 进程控制块, 的数据结构, 简称为 PCB。
进程与程序并不一一对应, 一个程序可以对应一个进程,
也可以对应几个进程 。 反之, 一个进程可以对应一个程序,
也可以一段程序 。
2.进程的实体
进程的实体是如何来表示一个进程存在 。 进程的实体由程序,
数据集合, 进程控制块 PCB(Process Control Block)及相应表
格组成 。
3.线程
线程是 处理机调度的独立单位,更好描述 多机 上进程的并发处
理,
线程是进程中可独立执行的子程序, 一个进程中可以有多个
线程, 每个线程用唯一的标识符进行标识 。 线程可以并发执行,
它们之间的切换比进程之间的切换快得多, 所以线程又称为
,轻型进程, 。
线程和进程的根本区别在于进程是系统作为资源分配的单位,
而线程是处理机进行调度和执行的单位 。 每个进程都有自已的
内存空间, 同一进程的各线程共享该进程的内存空间, 并且该
进程中所有线程对进程的整个内存空间都有存取权限 。
目前, Mach,Windows NT,Windows 2000等操作系统都已
有管理线程的机制 。
3.2.2进程的状态与转换
进程状态是指进程的当前行为 。 由于进程运行的间断性,决
定了进程至少具有三种状态 。 最基本的代表进程生命周期的状
态有,就绪, 运行, 阻塞 。
(1)就绪状态 (ready)
当进程已经获得除 CPU之外的
所有运行必要资源 。
(2)执行状态 (runing)
指进程已经获得处理机,其程
序正在执行 。
(3)阻塞状态 (block)
进程因发生某事件 (如请求
I/O。 申请缓冲空间等 )而暂停
执行的状态
就绪, 执行, 阻塞是进程的三种基本状态 。 执行态进程是物
理运行, 就诸态和阻塞状进程是逻辑运行, 宏观上, 它们都是活
动的 （ 即都处在运行之中 ） 。
进程在某个时刻总是处于某种状态, 随着其自身的推进和外
界条件的变化, 进程的状态也随之而变 。 状态之间的转换为进程
控制 。
就绪状态 ->执行状态,进程调度程序为之分配了处理机,
执行状态 ->就绪状态,因时间片已用完而被暂停执行时,
执行状态 ->阻塞状态,等待某事件发生而使进程的执行受阻,
阻塞状态 ->就绪状态,等待事件发生了,
说明,1.就绪进程有多个, 形成就绪队列 。
2.进程调度是从就绪队列中挑选进程分配 CPU。
3.进程在阻塞结束后回到就绪队列 。
除此基本状态外还有其它状态, 在这里就不再一一介绍了 。
3.2.3 进程的控制和调度
1.进程控制
进程控制, 就是对进程在整个生命周期中各种状态之间的转
换进行有效的控制 。
进程控制的基本功能 就是为作业创建进程, 撤消进程, 以及
控制进程在运行过程中的状态转换 。
这些操作对应于一组程序, 亦称为特殊的系统调用 。 这些特
殊的系统调用也称为原语 。
原语 （ Primitive） 是机器指令的延伸, 一条原语由若干机器
指令所组成, 有时也称之为, 软指令,, 用以完成特定功能的
一段程序 。 为保证操作的正确性和完整性, 大多数原语的在执
行必须是连续的, 即 一条原语在执行中不允许被中断, 大部分
原语通过系统调用方式使用 。
2.进程调度
进程调序决定就绪队列中哪个进程先获得处理机,然后再
由分派程序执行将处理机分配给进程的操作 。
进程调序程序一般在下述情况下发生的,
?当正在运行的进程缺乏资源不能继续运行而进入阻塞状态时；
?当运行的进程因时间片到而退回到就绪状态时；
?当运行的进程因外部中断而暂停时；
?当运行的进程提前结束时 。
这些情况都会引起进程调度, 重新分配处理机 。 进程调度
按一定算法, 选择一新进程, 把处理机分配给它, 并为它设
置运行现场再投入运行 。
进程调度要解决二个问题, (1)从就绪队列中选择哪个进
程？ (2)选中进程之后, 进程能占用 CPU多久?
进程调度的二种方式,
剥夺式调度,(抡占式调度 )进程在运行时,系统可根据某种原则,
剥夺已分配给它的处理机,并分配给其它进程的一种调度方式 。
剥夺的原则有,
?优先权原则,优先权高的进程可以剥夺优先权低的进程而运行 。
?短进程优先原则,短进程到达后可以剥夺长进程的运行 。
?时间片原则,运行一个 CPU时间片后重新调度 。
非剥夺方式,以这种调度方式运行时,调度程序一旦把处理机分
配给某进程后, 除非它自愿放弃, 否则它就一直运行下去 。
几种进程调度算法
(1)先进先出 (First In First Out)
(2)短执行进程优先 (SCBF)
(3)优先级调度 (FPF)
(4)时间片轮转法 （ RR）
(5)多级反馈队列
3.2.4进程的协调和通信
由于进程合作与资源共享,使进程之间产生两种形式的制约
关系,
(1)间接相互制约,
系统的重要的资源, 如处理机, 内存空间, 设备, 文件等
由系统协调资源共享 。 进程的间接相互制约又称为互斥 。 互
斥实质是对进程的异步运行在时间上施加某些限制 。
(2)直接制约关系,
一个进程在没有获得合作进程提供的必要信息之前不能超
越某一执行点或无法继续工作 。 进程的直接制约关系称为同
步, 由进程间自行协调,
可见,绪进程在并发执行时,必须按照一定的次序执行 。 互
斥与同步实质上都是在执行时序上的某种限制 。 因此, 它们
是广义同步概念 。 故在广义上, 互斥是一种特殊的同步 。
1,临界区和临界资源
一次只允许一个进程使用的资源称为 临界资源 。
程序中使用临界资源的那段程序称为 临界区 。
对临界区调用的原则归纳为：
有空则进, 无空等待, 有限等待：
2.同步机构
1） 锁机制
锁机制提供一个锁变量 S。 S变量只能由上锁或开锁原语改变,
若 S=0 表示锁开可使用, 若 S=1 表示已加锁 。
加锁原语为,测试 S是否为 0？ 若 S=0,让 S=1。 若 S=1,继续测试 。
开锁原语则为, 使 S为 0。
锁机制解决互斥是安全可靠的 。 锁机制不能解决进程的同步问
题 。
2） 信号量和 P,V操作
荷兰的著名计算机科学家 Dijkstra把 互斥 的关键含义抽象成
信号量 （ semaphore） 概念, 并引入在信号量上的 P,V操作作
为同步原语 。 信号量是个被保护的量, 只有 P,V操作和信号量
初始化操作才能访问和改变它的值 。 Dijkstra把信号量为 S定
义为一个非负整型量 。 在信号量 S上的 P操作和 V操作定义如下：
P(S)：
（ 1） S:=S-1；
（ 2） 若 S<0,阻塞当前进程, 将其插入等待 S队列, 调度另一
进程运行 。 若 S>=0,当前进程继续运行 。
V(S)：
（ 1） S:=S+1；
（ 2） 若 S<=0,从等待 S的队列中移出一个进程, 由阻塞状态进
入就绪状态, 当前进程继续运行 。 若 S>0,当前进程继续运行 。
P,V操作从资源观点上看, S值表示可用资源数, 0表示无可用资
源, 负数表示还欠缺的资源数 。 而 P(s)表示请求分配一个资源,
V(s)表示归还一个单位资源 。
P,V操作既可以用于进程互斥, 也可以用于进程同步 。
一个简单的同步关系的问题,
信号量 Sa初值为 1,信号量 Sb初值为 0,其中 n为临界资源, 进程 A和
进程 B必须互斥使用 。 这二个进程不管分别以什么速度向前推进,
但打印的结果肯定是从 1开始的连续数值 。
生产者与消费者 问题是最著名的进程同步问题, 生产者与
消费者共享一个有界缓冲池, 生产者向池中投入消息, 消费
者从中取得消息 。 生产者 —消费者问题实际上是相互合作进程
关系的一种抽象, 常用于检验进程同步机制 。
假定缓冲池中具有 n个缓冲区, 每个缓冲区存放一个消息,
可利用互斥信号量 mutex使进程对缓冲区实现互斥访问；利用
资源信号量 empty和 full分别表示缓冲池中空缓冲区及满缓冲
区的数量 。 只要缓冲区未满, 生产者便可将消息送入缓冲区；
只要缓冲池未空, 消费者便可从缓冲池取走一个消费 。
信号量的初值：互斥信号量 mutex=1,空缓冲区 empty=n，
满缓冲区 full=0。
在生产者 —消费者问题中应当注意：
1） 在每个程序中用于实现互斥的 P(mutex）和 V(mutex)必须 成对 出
现。
2） 对资源信号量 empty和 full的 P,V操作同样需要成对出现，但它
们分别处于不同的程序中。
3） 在每个程序中的 P操作 顺序不能颠倒,否则可能引起进程 死锁 。
V操作的次序无关紧要。
3．进程的通信
进程以各自独立的速度向前推进 。 它们之间经常需要交
换一定数据的信息, 以便协调一致共同完成指定的任务 。
所交换的信息量, 少则一个状态或数值, 多则成百上千个
字节 。
进程间信息交换方式有：
低级通信,
交换少量数据 。 这种交换的方法常用变量, 数组等 。 前面
介绍的 P,V操作也可以交换少量信息 。
高级通信：
进程间交换大量数据信息, 也称为消息通信 。 常用有消息
缓冲方式, 信箱通信, 管道通信等方式, 以较高的效率传
输大批数据 。
实现进程高级通信的机制有,
(1)消息缓冲,也称作直接通信方式, 即一个进程直接发送
一个消息给接收进程 。 这种通信方式必须知道对方存在 。
靠原语 send(发送 )和 receive(接收 )来实现 。
(2)信箱通信,称作间接通信方式, 指进程之间的通信需要
通过某种中间实体, 通常把这种中间实体称为信箱 。 利用
信箱可实现非实时通信 。
(3)管道通信,建立在文件系统的基础上,它利用共享文件
来连接两个相互通信的进程, 此共享文件称为管道 (pipe)，
因而这种通信方式也称为管道通信 。 管道通信的实质是利
用外存来进行数据通信, 故具有传送数据量大的优点 。
3.2.5死锁
在多道程序系统中, 计算机系统中有限的资源与众多的请
求分配资源的进程间会存在矛盾, 如果管理和分配不当会引
起进程相互等待资源的情况, 形成这些进程都在等待资源而
无法继续执行, 然而也不可能归还已占用的资源 。
1.死锁的产生
产生死锁的主要原因有两点,
,竞争资源而引起死锁
,进程推进不当引起死锁
产生死锁的四个必要条件,
(1)互斥条件
(2)请求和保持条件
(3)不剥夺条件
(4)循环等待条件
2,死锁的解除与预防
目前用于解决死锁的办法有如下几种,
(1)预防死锁,
破坏产生死锁的四个必要条件中的一个或几个 ( 除第一条件
外的其它条件 ),来防止死锁发生 。
(2)回避死锁,
系统不需要采取各种限制措施去破坏产生死锁的必要条件 。
在资源的动态分配中, 采用某种方法防止系统进入不安全状
态, 以避免死锁的最终发生, 如著名的银行家算法 。
(3)检测死锁,
系统运行过程事先不采取任何防止和避免的措施 。 但通过
系统的检测机构, 及时检测出死锁的发生, 采取措施清除 。
(4)解除死锁,
一旦死锁发生, 采取措施解除死锁, 方法是撤消或挂起一
些进程, 或剥夺资源, 以便释放出一些资源 。
3.3 存储管理
3.3.1存储管理的概念及功能
1,系统存储器的配置
系统的存储器由内, 外存储器组成 。 程序的指令和数据只
有存放在 CPU能直接访问的内存中, 这个程序或这个程序的部
分才能够被执行 。
系统使用的存储器由二部分组成：物理内存和逻辑内存 。
物理内存由系统实际提供, 由字节组成, 容量受实际存储单
元的限制 。 逻辑内存也称虚拟内存, 它把内存和外存统一进
行管理, 它的容量受计算机地址的位数和辅存容量限制 。
内存的使用分为二部分, 一部分为系统区, 即系统程序使
用的区域, 主要存放操作系统, 一些标准子程序, 例行程序
和系统数据等 。 另一部分为用户区 。 由操作系统存储管理系
统管理 。
2.存储空间的地址
高级语言编制的源程序, 存在于由程序员建立的符号名字空
间 (名空间 )内, 与存储器地址无任何直接关系, 仅是符号名的
集合, 称作名空间 。
源程序经编译后所形成的目标程序, 其地址总是从零开始,
因此称目标程序中的地址为虚拟地址空间 (地址空间 )。
目标地址经过链接再装入内存时, 其分配到的物理地址与编
译后的相对地址是不同的 。 称为物理地址空间, 即绝对的地址
集合 (存储空间 )。
3.地址重定位
用户在各自的逻辑空间内编程 。 一个作业在装入时分配到的
存储空间和它的编程地址空间是不一致的 。 即程序在运行时需要
把逻辑地址转换为物理地址 。
地址重定位,
一个作业的逻辑地址向物理地址的转换 。
重定位分为静态重定位和动态重定位 。
静态重定位,
是在目标程序装入指定内存区的时候由装配程序在程序执行
之前一次完成逻辑地址至物理地址的转换, 以后地址不再改变 。
动态重定位,
是在目标程序执行中, 每当形成一个访问内存的有效地址时,
就动态进行地址变换 。 由于每形成一条指令都需变换, 所以需要
硬件支持, 如基地址寄存器和限长寄存器等, 以加快地址变换 。
4.存储器管理的功能
存储器管理有两个基本目的：
一是方便用户；二是充分发挥内存的利用率 。
存储器管理具有以下几个功能,
(1)内存分配
(2)地址映射
(3)存储扩充
(4)存储共享和保护
5.内存扩充技术
内存的扩充的二种方法：一是物理上的扩充, 为系统配置更
多的存储器芯片 。 二是逻辑上的扩充, 借用软件技术实现主存
容量的扩充目的 。
逻辑扩充技术有 覆盖技术 和 交换技术 二种 。
覆盖技术,是指同一内存区可以被不同的程序段重复使用
（ a）作业的调用结构 （ b）覆盖结构及内存分配
若把作业 P全部进入内存需要 190K,而使用覆盖技术后只占
用 110K内存 。 通常覆盖技术主要用于系统程序的内存管理上 。
交换技术,
是指在内外存之间交换程序和数据 。 在内存中只驻留
一部分甚至只是少数几个用户进程, 其余用户进程驻在
外存, 当用到时进入内存 。
交换技术使用户可以得到大容量的存储器和内存的运
行速度 。 但从存储管理的角度, 交换并不是一种独立的
存储管理方案 。 它与分区技术结合, 形成交换式分区管
理；也可以与分页或分段技术结合, 形成交换式分页或
分段管理 。
交换技术实质上是系统把内存和外存统一进行管理,
形成一个存储容量比实际内存大的存储器, 这个存储器
就是虚拟存储器 。 它的最大容量受二个因素决定, 一是
由计算机的地址结构而定, 二是内外存容量之和所确定 。
3.3.2分区式管理
基本思想,将内存划分成若干连续区域 (分区 ),每个分区中装
入一个运行作业 。
1.固定式分区 (静态分区 ):系统初始化时, 内存分为若干区,
每个区的大小可以不同, 但每一个区中只能存放一个作业 。 一
旦分好, 则每个分区的大小和分区总数均不再变化 。
分区分配表
区号 分区大小 起始地址 使用状态
1 8k 16k 1
2 16k 24k 0
3 32k 40k 1
4 64k 72k 0
5 120k 136k 0
存储区的分配策略是顺序查找分区分配表, 将满足作业请求容
量的, 且未使用的第一个分区分配给该作业 （ 将其使用状态置为
,1”） 。 回收时将分区表中的使用状态改为, 0”即可
2.可变分区 (动态分区 )
存储区的分配,预先不划分分区的大小, 在装入作业时使分
配的分区大小正好适应作业的需要量, 且分区的个数也不
固定 。 系统初启时, 除操作系统占据一块内存外, 其余为
一个完整的大空闲区 。 有作业要求装入时, 则分配作业要
求大小的空闲区, 余下的为空闲区 。
如某时刻内存的状态为,
可变分区中对内存状态的记录和管理使用有如下几种方法：
(1)表格法 (双表法 ):使用两个表格 (占用区表 P和空闲区表 F)管理
内存 。 这二个表的内容均为存储区的大小和起始地址 。 这二个表
的长度均可变 。
(2)位图法,将内存按分配单元划分, 单元可以是若干字节或几个
KB。 每个分配单元对应于位图中的一位 。
如, 0 1 2 3 4 5 6 7 位
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
.,,,,, 其中,0-空闲, 1-已分配 。
(3)链表法,用链表记录内存的占用或空闲情况 。 链表的每项的内
容有,
分配状态 分区起始地址 分区大小 链接指针
链接指针可以是单向指针或双向指针 。 链接表也可以分别设置
为已分配链表和未分配链表 。
(4)分配策略
链表记录通常有如下三种分配策方法,
A.首次适配法 (FF)
把内存中的空闲区按起始地址递增顺序排列 。 分配内存时,
从链表首端开始查找, 选择第一个满足要求的空闲块分配, 而
不管它究竟有多大 。 剩余的空间仍留在空闲链中 。
B.最佳适配法 (BF)
把内存中的空闲区按分区大小递增次序排列 。 分配内存时,
按链表顺序查找适合用户需求的空闲块, 必定是最接近用户申
请的块大小 。 然后按用户申请量进行分配, 残余部分留在链中,
并重新排列 。
C.最坏适配法 (WF)
把空闲块按其大小递减的顺序组成链表, 大块在先, 小块在
后 。 分配时先挑选大的进行分配, 使剩余空间不致太小 。
需要指出的是, 最佳适应算法不一定是最佳的, 最坏适应算
法也不一定最坏 。
假设内存中现有两个空闲区,F1为 110K,F2为 60K。 现
依次有 A,B,C三个作业请求装入运行, 它们的内存需求
分别是 20K,80K和 50K。
若 采用 WF算法, 作业 A可获得 F1中的 20K,作业 B获得 F1
中的 80K,作业 C获得 F2中的 50K,三个作业的需求都得到
了满足 。
若 采用 BF算法, 作业 A获得 F2中的 20K,作业 B获得 F1中的
80K,而作业 C的需求却不能满足 。
若 采用 FF算法, 如果 F1的地址低于 F2,可得到与 WF算法
同样的结果, 否则, 则得到与 BF算法同样的结果 。 这里,
最坏适应算法倒是, 最佳, 的 。
分区管理实现了多道程序共享内存, 提高了 CPU的利用
率, 管理算法简单, 容易实现 。 但它导致内存碎片多, 拼
接又化费时间, 降低了内存利用率 。
3.3.3分页式管理
分页式管理的出发点是为了消除碎片而打破存储分配的连
续性, 使得一个作业的地址空间可以分布在 若干离散的内存
块 上, 从而充分利用内存空间, 提高内存利用率 。
页,用户作业的空间划分为若干个大小相等的块 。 不足一
块的补齐为一页, 页面大小通常为 512字节至 4K大小 。
所有的页从 0开始依次编号每个页内部相对于 0连续编址 。
页帧,系统将内存空间中也划分与页大小相等的若干块 。
于是作业地址空间构成一个二维地址空间, 其中的任一逻辑
地址都可表示成 （ p,d）,其中 p是页号, d是页内位移量即相
对地址 。
系统装入作业时, 以页为单位给作业分配页帧 。 因此, 作
业可以按页为单位, 离散地放在内存中不连续的页帧中 。
1.简单页式管理 （ 静态分页管理 ）
基本思想,如果内存当前可用页帧数不小于作业要求的页
数, 系统就实施分配, 否则不于分配 。
简单页式用 页表 (PMT)来进行管理 。
每个作业有一张相应的页表,
如某作业有 4页，内存中以 1K为一帧进行分配，则可能
的页表及对应的页帧关系。
2.请求页式管理 (动态分页管理 )
实现原理,开始时把整个作业的一部分装入内存, 其它部分则在
运行过程中动态装入 。 系统对页表进行扩充, 扩充后的页表组成
如,
页表结构
页帧号 存取控制 存在位 访问位 修改位
1 RWE 1 1 1
2 RWE 1 1 0
3 RE 0 0 0
其中存在位为 0表示该页不在内存, 存在位为 1时表示在内存 。
系统在运行时动态检查页表, 当存在位为 0时, 系统就把所需的
页调入内存 。 但当内存中没有空闲页帧时, 则先淘汰内存中的页,
若淘汰的页已被修改过 （ 修改位为 1）, 则回写磁盘, 否则直接
淘汰 。
系统淘汰页面时有常见的策略有,
(1)先进先出法 (FIFO)
算法适合于程序按顺序访问地址空间 。 不适合于程序中有循环的
情况 。
(2)最近最少使用法 (LRU)
过去一段时间内未被访问过的页, 近期也可能不会被访问 。 该算
法较为复杂 。 实际中常使用近似的 LRU算法, 如最不经常使用的页
面淘汰算法 LFU及最近没有使用页面淘汰算法 NUR等 。
,颠簸,, 对于刚被淘汰出去的页, 进程可能马上又要访问它, 故
又需将它调入, 因无空闲内存页帧又要淘汰另一页, 而后者很可能
是即将被访问的页 。 于是造成了系统需花费大量的时间忙于进行这
种频繁的页面交换, 致使系统的实际效率很低, 严重时将导致系统
的瘫痪 。
请求页式管理能有效地消除内存碎片, 且作业地址空间不受内存
容量大小的限制, 提高内存利用率 。 但由于建立和管理页表及动态
地址, 增大了系统时间和空间开销, 如算法选择不当可能引起系统
,颠簸,, 致使系统性能下降 。
3.3.4 段式管理
分页并不是依据作业内存的逻辑关系, 而是对连续的
地址空间一种固定长度的连续划分 。
实际上, 一个作业通常是由若干逻辑程序段和数据段
所组成, 从用户角度希望作业能按照自已的逻辑关系分
成若干自然段, 每段都有自己的名子, 且都从 0开始编址
的一维地址空间, 这样有利于程序设计, 又可方便地按
段名进行访问 。
段式管理就是为了解决这个问题而提出的 。
段式管理也分有二种形式：简单段式管理和段页结合
式管理 。
1.简单段式管理
一个段定义为一组逻辑信息 。 一个作业由若干个具有逻
辑意义的段 (如主程序, 子程序, 数据, 工作区等 )组成 。
每个段有段名, 且都从 0开始编址的连续空间 。 段的长度不
固定, 仅由相应逻辑信息组的大小所决定, 一个作业由 (s，
d)组成, 其中 s是二维地址空间中的段号, d是段内相对地
址 。 整个作业地址空间是二维的 。
简单段式管理 以段为单元进行内存分配, 一段分配在一
个连续的内存区, 各段的长度可以不同, 段与段之间可不
连续 。 一个作业的连续地址空间可以对应若干个不连续的
内存分区 。
系统为每一个运行的作业建立一个段表 (SMT) 。
段表：段长 内存起始地址 状态标志
段的替换算法与释放算法类同页式管理 。
段是逻辑意义的如,cos(x),sin(x)等 。 所以 段式管理易
实现共享 同一内存块里的程序或数据 。 不同的段表调用一个共
享段时, 共享段可以具有不同的段号 。 也可以设置 "共享段表 "
来实现段的共享 。
为了保证各作业之间相互不干扰, 系统设置段保护 。 一般的
段保护措施 如下,
?建立存取控制,段表中有, 存取方式, 项, 存取方式有三种：
写, 读和执行, 用 R,W,E表示 。
?段地址越界保护措施,段表中每段的表目中有段长值, 以指
明该段的长度, 使每个作业被限制在自己的地址空间中运行 。
页式, 段式管理提供了内外存统一管理的虚拟存储器的概念,
为用户提供了一个非常大的运行空间 。 段式管理中允许段长动
态增长, 便于段的共享和保护, 便于程序动态链接 。 但是段式
管理需要更多硬件支持, 同时段长受内存限制, 给系统增加了
复杂性, 也有可能产生, 颠簸, 。
2.段页式结合管理
基本思想,是利用分段向用户提供二维的编程空间, 以方
便用户编程, 利用分页来管理内存空间, 以提高内存利用率 。
在段页式系统中, 作业的地址仍按逻辑意义分段, 是用户
定义的二维逻辑地址 （ s,d）, 其中 s是段号, d是段内位移
量, d又可以被系统变换为, （ p,w） p是页号, w为页内位
移量 。 这样形成三维地址映射 。
段页式管理,系统为每个作业建立一个段表和若干个页表,
页表的个数等于段表的表目数 。
访问主存的物理地址就要访问段表, 页表和实际地址, 所
以访问主存中的一条指令或一个数据, 至少要 访问内存三次 。
段式管理与页式管理有如下不同之处：
? 段是信息的逻辑单位, 分段是出于作业逻辑上的要求, 对用户
来说, 分段是可见的, 分页是不可见的；页是信息物理单位, 段
是信息的逻辑单位；分页并不是用户作业的要求, 而仅仅是为了
系统管理内存的需要 。 也就是说, 段是面向使用, 页是面向管理 。
? 分段地址空间是二维的, 分页地址空间是一维的 。
? 段的长度不固定, 由用户决定；页的长度是等长的, 由系统决
定 。
段页式管理实现了分段、分页管理的优势互补,方便了用户，
提高了内存利用率。但也增加了硬件成本和系统开销。
3.4 设备管理
3.4.1设备的有关概念
1,设备
系统的设备是指进行实际 I/O操作的物理设备, 及控制这
些设备并进行 I/O操作的支持部件 。
从 数据组织 的角度, 设备可以分为,
?块设备：以块为单位组织和传送数据 。
?字符设备：以字符为单位组织和传送数据 。
从 资源分配 的角度, 设备可以分为,
?独享设备：在作业整个运行期间为此作业独占 。
?共享设备：允许若干用户同时共同使用的设备 。
?虚拟设备：通过假脱机技术, 把原来的独享设备改造成共
享设备 。
2,设备管理的任务
(1)设备分配 (2)启动设备完成实际的输入 /输出操作
(3)设备无关性 (4)提高设备的利用率
3.中断的概念
中断是指计算机在执行期间, 系统内发生急需处理事件, 使得 CPU
暂时中断当前正在执行的程序而转去执行相应的事件处理程序, 待
处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过
程 。
中断源,引起中断发生的事件 。
中断请求,中断源向 CPU发出的请求中断处理信号,
中断响应,而 CPU收到中断请求后转相应的事件处理程序 。
根据中断源产生的条件, 可把中断分为 硬件中断 和 软件中断 。
4,通道的概念
程序中断 I/O方式中每处理一个字, 要进行一次中断处理, 当
有大批数据需要传递时, 中断次数就很多 。
通道的出现建立了 I/O的独立管理机构, 这时只要 CPU发一条
I/O指令给通道, 告诉通道要执行的 I/O操作要访问的设备, 通道
便向内存索取通道程序以完成 I/O控制管理 。
5.缓冲技术
目的：为解决高速的 CPU与低速的外设之间的速度不匹配 。
缓冲技术实质上是在内存中开辟一个具有 n个单元的区域作为
缓冲区 。 缓冲区的大小可以按实际应用需要来确定 。
其结构形式可以有多种形式, 有循环队列形式, 单缓冲区及多
缓冲区形式, 缓冲池结构等 。
3.4.2 设备管理程序
1.逻辑设备与物理设备
设备的无关性, 用户可不必指定特定的设备, 而代之指定逻
辑设备 。 使得用户程序与实际使用的物理设备无关, 可以脱离
具体的物理设备来使用设备 。
逻辑设备, 为了方便用户使用设备, 通常用符号名代替设备
的类型名 。 如 LPT表示打印机 。
为了实现与设备的无关性, 系统中必须有一张联系逻辑设备
和物理设备名称的映象表 。
2.设备分配程序
设备分配程序应按照一定的算法, 决定把某一台设备分配给
那一个要求该设备的进程 。
设备分配时的算法有先请求先服务, 优先数法等 。
3,设备驱动程序
设备驱动程序实现 I/O操作 。
3.4.3虚拟设备 --假脱机系统
虚拟设备技术 (Spooling技术 ):
利用高速的直接存储设备 （ 一般使用硬盘 ） 来模拟低
速的独占设备, 使独占设备转化成共享设备 。
3.5 文件管理
3.5.1 文件及文件系统
1.文件
文件是逻辑上具有完整意义的数据或字符序列的集合 。
2,文件系统
文件系统是负责存取和管理文件的机构 。
3.5.2文件结构及存取方式
1.文件的逻辑结构
(1)流式文件：流式文件是由一串连续的字符序列组成 。
(2)记录式文件：记录式文件由若干个记录组成 。
2.文件的物理结构
文件的物理结构是指文件在外存储器上的组织形式 。 文件
的物理结构一般有三种类型：连续结构, 链结构和索引结构 。
连续结构,把逻辑上连续的文件存放在一个连续的物理
介质上 。
链接结构,文件可以分别存放在物理介质的不同块中, 块
与块之间通过指针取得联系 。
索引结构,文件的全部记录分别存放在物理介质的不同
块中, 系统为每一个文件建立一张索引表,
3.文件的存取方式
一般有 顺序存取, 随机存取 两种方式 。
顺序存取,
对文件的每次存取是在上次存取的基础上进行 。 对于
记录式文件, 它总是在上次存取的基础上顺序存取下一
个记录 。 而对流式文件, 则在读 /写指针的当前位置顺序
存取文件的下一串字符 。
随机存取 (直接存取 ):
以任意次序直接存取文件中某一个记录, 对于流式文
件, 需要把读 /写指针调整到要访问的位置 。 同时, 直接
存取技术的具体实现还与存取文件的物理介质结构有关 。
3.5.3文件存储空间管理
也称为外存管理, 它和内存管理有许多相似之处, 最大区别
是内存管理以字节为单位, 而外存管理以字符块为单位 。
根据文件的物理结构不同, 文件在外存储器中存放的方式有
连续和不连续 两种 。
文件存储空间管理常用的技术有以下几种,
1.空白文件目录,把一个连续的未分配的外存储区称为, 空白文
件,, 系统为所有的, 空白文件, 建立一个目录, 表目的内容为
空白块地址和空白块数目 。
序号 第一个空白块号 空白块个数 表示的物理块号
1 2 4 2,3,4,5
2 9 3 9,10,11
3 15 5 15,16,17,18,19
4,...,...,...
2.空闲块索引表
空闲块索引表的每个表目登记一个空闲块号, 相邻表
目中的块号不一定相邻 。 分配时, 从索引表的一个非空
表目中取出一个空闲块号, 分配后将该块号从相应表目
中删去, 回收一个物理块时, 将其块号填索引表的一个
空表目中 。 这种方法对物理块的分配和回收处理都比较
容易, 但索引表需要占用较大的存储空间 。
3.位示图
利用一个二进制位来表示一个物理块的分配状态, 系
统为文件的存储空间建立一张位示图, 参见前面的图 3-
3-5所示 。 其中每一位对应一个外存物理块, 图中, 1”表
示对应块已分配,, 0”表示对应块为, 空闲, 。 位示图
方法既可用于非连续文件, 也可用于连续文件和分配,
当进行连续文件分配时, 需要在位示图中找到足够多的
连续为 0的二进位 。
3.5.4 文件目录
文件目录组织方式有：
1,一级目录结构
整个系统只设置一个目录表, 目录表就是文件控制块 。
2,二级目录结构
文件的目录被分成二部分, 第一级是主目录表, 第二
级是用户目录表 。
3,目录树结构
是一棵倒置的有根的树 。 树型结构目录可以更确切地
反映系统内部文件的分支系统, 用户可将部分文件构成
子树与其它部分分开以便处理 。 系统或用户还可以规定
不同层次或子树文件有不同的存取权限, 以便更好地对
文件加以保护 。
3.5.5 文件的共享与安全性
文件的共享和安全是一个问题的二个方面 。
1.文件的共享
(1)由系统来实现文件的共享
当要共享系统文件或其它已知用户的文件, 且已知道文件的路
径, 则可以通过从根目录出发的路径来共享文件 。
(2)采用基本文件目录和符号文件目录
把文件目录分成二部分：一部分为基本文件目录, 包括文件的
结构信息,物理地址,存取控制及其它管理信息说明, 并用系统赋
予的标识符来标识 。 另一部分包括符号名和与之相应的标识符组
成, 称为符号文件目录 。
对欲共享的文件进行联接, 即在用户自己的符号文件目录中对
欲共享的文件建立起相应的表目, 称为联接 。
2.文件的存取控制
(1)存取控制矩阵
用一个二维矩阵, 行坐标表示系统中全部用户, 列坐标表示
系统中全部文件, 矩阵元素 aij的值为, 1”时, 表示用户 i允许
访问 j文件 。 反之, 当 aij为, 0”时, 表示用户 i不允许访问 j文
件 。
(2)按用户分类存取控制
系统中的用户往往分类为,a.文件主 b.同组用户 c.一般用户 。
在 UNIX系统中, 每个文件的存取权力说明用一个 9位二进制数
表示, 每类用户占 3位, 每一位代表读, 写和执行三种访问权力 。
(3)口令
用户为自己的每一个文件规定一个口令, 附在文件目录中,
凡请求访问该文件的用户, 必须先提供口令 。
3.5.6 文件的主要操作
最基本的命令有：
建立文件, 打开文件, 读文件, 写文件, 关闭文件和撤
消文件等 。
3.6作业管理与用户界面
作业管理的主要对 用户作业进行合理调度, 以提高系统的吞吐
量和缩短作业的周转时间, 并 提供用户与操作系统的接口 。
在实际操作中, 用户通过输入设备, 如键盘, 鼠标器, 触摸屏
等将用户要求, 告诉, 计算机, 计算机收到这些请求后再为用户
服务 。
1.用户是通过命令或者程序向计算机发出请求, 多个用户的请
求以用户作业的方式在后备存储设备中等待 。
2.计算机收到用户请求后, 利用操作系统提供的命令解释和系
统调用, 以及相应的处理程序, 有序有效地使用系统提供的各种
资源, 完成用户作业的处理 。
3.6.1作业管理
作业管理主要包括作业的组织, 作业的控制以及作业的调度
等内容 。
1.作业管理的概念
作业 (job)是指用户在一次计算过程中, 或者一次事物处理过
程中, 要求计算机系统所作的工作的集合 。 通常, 一个作业又可
分为若干个顺序处理的作业步, 作业步的集合完成了一个作业 。
2.作业的类型
从控制的角度可把作业分成脱机作业和联机作业 。
脱机作业,是在整个作业运行过程中, 根据作业说明书中的说
明对作业进行控制,
联机作业,通常是用键盘命令直接控制作业的运行 。
3,作业的状态
（ 1） 进入状态
提交的作业通过某种输入方式将作业输入到外存上时, 称此
作业处于进入状态 。
（ 2） 后备状态
由作业建立程序为之建立了作业控制块 (PCB),并插入到后备
作业队列中等待调度运行为止 。
（ 3） 运行状态
作业调度程序从处于后备状态的作业队列中选出一个作业调
入内存, 并为之建立相应的进程后, 由于此时的作业已具有独
立运行的资格, 如果处理机空闲, 便可立即开始执行, 故称此
时的作业是进入了运行状态 。
（ 4） 终止状态
当作业 （ 进程 ） 的运行正常或异常结束时, 进程便自我终止,
或被迫终止, 此时作业便进入终止状态 。
图 3-6-1作业的状态及其转换
4.用户如何提交作业
交互式作业也称 联机用户作业,
主要通过直接命令方式提供用户作业 。
间接的方式也称 脱机作业方式,
由用户事先写好作业步的说明, 一次提交给系统, 由
系统按照作业步说明依次处理 。
3.6.2操作系统的用户接口
1.操作系统的程序接口
程序接口通常采用若干系统调用组成, 也称编程接口 。
用户通过在程序中使用这些系统调用命令来请求系统提
供的服务 。
用汇编语言编写程序可以直接使用这组系统调用命令,
向系统提出各种控制 I/O等要求 。
用高级语言则可以在程序中使用过程调用语句 。 这些调
用语句在源程序被编绎时翻译成有关的系统调用命令 。
2.操作系统的命令接口
命令接口由一组键盘操作命令组成。通过控制台或终
端打入操作命令，向系统提出各种要求。命令接口有两
个基本任务：
（ 1）判别和解释用户键入的操作命令，并将相应的命令
操作转向对应的命令处理程序。
（ 2）接收从操作系统传来的信息，然后通过屏幕提示等
方式提呈给用户。
命令接口有多种形式：有直接命令方式和间接命令方式。
3.7几种常见的操作系统
3.7.1 Windows 发展简史
Windows是美国微软公司开发的 PC操作系统, 自 1983年
Windows1.0诞生以来, 迄今已发布了 20余种版本, 成为当今流
行最广, 用户最多的一个操作系统家族 。
Windows发展大至经过三个阶段：
1。 成长阶段,(1983-1993)
Windows 1.0于 1983年研制成功 。
Windows 2.0于 1987年发布 。
特点：引入了图形界面, 但只能起, 技术演示, 作用 。
Windows 3.0与 3.1于 1990年推出 。
特点：优美图形, 高级的鼠标操作和多任务运行 。
引发 PC操作系统第一次历史性的变革 。
2。新技术 阶段,(1993-2000)
Windows 3.1为至，附加在 DOS 上。
Windows NT3.11(1993.8)
特点：抢占式、多任务、存储保护模式等新技术。
至后,Windows分成二路：
个人 /家族,Windows 3.2,(1994)
Windows 95,Windows 98
企业 /办公,Windows NT3.5 Windows NT4.0
3。新一统阶段 (2001-)
2000年 2 月公布了 Windows 2000，希望既能有 Windows
NT的稳定性，又集成 Windows 9X娱乐性。但它虽然是一个
优秀的商用操作系统，却不适用于家族 /个人用户使用。
2000.10又公布 Windows Me。
2001.10 在 Windows 2000及 Windows Me的基础上合二为
一推出 Windows XP
3.7.2 Windows 操作系统的基本功能
(1)支持应用程序的多任务运行
? 多个任务迸发运行，互不干扰。
? 抡占式 CPU调度
(2)高效、方便的文件管理
?文件管理器扩展为“资源管理器”、“我的电脑”、“网上邻
居”等多种资源管理窗口。
?有关文件操作的常用命令集中在：“文件”、“编辑”菜单中。
(3)支持 PnP等标准，使新设备的安装更加简化。
(4)支持联网已成为 Windows 的标准功能。
(5)出色的多媒体功能。
3.7.3 Windows 操作系统的主要特点
(1)丰富多彩、易学易用的图形用户界面。
(2)多媒体支持已发展成 Windows 操作系统的标准功能。
(3)PC操作系统已经跨越网络操作系统的鸿沟，两种操作系统
正在普及网络应用的大趋势下开始合二为一。
(4)操作系统继续保持小核心、大系统、多版本的发展趋势，
大批实用程序以附件的形式捆绑在不同版本的操作系统上，
可供用户按需选用。
3.8 其它常见的操作系统
3.8.1 MS-DOS操作系统
MS-DOS是美国 Microsoft公司为 IBM PC开发的一个单用户、单
任务磁盘操作系统,1981年有了 MS DOS 1.0。
它具有很强的文件管理功能，为用户提供丰富的系统资源，有
较多的外部和内部命令，功能强大的系统调用等，为用户生成和
管理文件，调度系统的软硬件资源和运行各种程序。
3.8.2 UNIX/XENIX操作系统
UNIX是分时多用户多任务操作系统。汉化后成为 XENIX操作系
统 。
3.8.3 Linux操作系统
Linux是一个 32位的多任务、多用户的操作系统。是一个免费
的，源代码开放的操作系统。 Linux版本众多，现在主要流行的
版本有,Red Hat Linux,Turbo Linux,S.u.S.E Linux等。我
国自己开发的版本有：红旗 Linux、蓝点 Linux等。
小结
操作系统 是加在裸机上的第一层软件。它是系统应用程序和
用户程序与硬件之间的接口，而且是整个计算机系统的核心，起
着控制和管理和中心作用。
操作系统的主要类型,操作系统可分为批处理系统, 分时系统,
实时系统, 单用户交互系统, 网络操作系统及分布式操作系统 。
操作系统的功能,可被划分为处理机管理, 存储器管理, 设备
管理, 文件管理及作业管理五大部分 。
处理机管理 也称为进程管理 。 进程管理中重要的问题是处理好
进程的同步与互斥, 同步 是并发进程因相互合作而产生的一种制
约关系, 互斥 是并发进程因共享资源而产生的一种制约关系 。
内存管理 的基本目的是提高内存利用率以及方便用户使用,
它涉及四个基本问题：内存分配, 地址映射, 内存保护和内存扩
充 。 内存管理有各种方法, 有分区管理, 分页管理, 分段管理和
段页式管理等 。 虚拟存储器是广泛采用的内存扩充技术 。
设备管理 涉及主机之外的所有外设的管理 。 它的基本目标是：
向用户提供方便的设备使用接口以及充分发挥设备的利用率 。 缓
冲区是 I/O系统的主要数据结构, 缓冲区管理是逻辑 I/O系统的基
本功能之一 。 在 SPOOLing系统的管理下, 独享设备的分配变为虚
拟设备的分配 。
文件管理 负责存取和管理文件的机构 。 文件系统的目的是充分
利用外存储器和方便用户 。 为此, 文件系统应能统一管理文件存
储空间, 实施外存储空间的分配与回收；实现文件的按名存取；
实现对文件的各种控制和存取操作；实现文件信息的共享, 并且
提供可靠的文件保密的保护措施 。
作业管理 提供了操作系统与用户之间的使用接口 。
最后, 我们给大家介绍了一些当前常用的操作系统, 有 MS-
DOS,Windows,Windows NT,NUIX,Linux等 。
第四章 数据库技术
在计算机的三大应用 （ 科学计算, 数据处理与过程控
制 ） 中, 数据处理所占比重约为 70%左右 。
本章先介绍数据管理技术的发展和数据库中的一些主
要概念, 然后重点阐述 ACCESS数据库的基本操作和应用；
最后对关系数据库理论作一些简要介绍 。
4.1 概述
4.1.1 数据与数据处理
1.数据与信息
数据,通常指用符号记录下来的, 可以识别的信息 。
信息,关于现实世界事物存在方式或运动状态的反映 。
数据与信息是分不开的，它们既有联系又有区别。
2、数据处理与数据管理
数据处理
是指从某些已知的数据出发, 推导加工出一些新的数
据, 这些新的数据又表示了新的信息 。 在具体操作中,
涉及到数据收集, 管理, 加工利用乃至信息输出的演变
与推导全过程 。
数据管理
是指数据的收集, 整理, 组织, 存储, 维护, 检索,
传送等操作, 这部分操作是数据处理业务的基本环节,
而且是任何数据处理业务中必不可少的共有业务 。
4.1.2 数据管理技术的发展
数据管理大致经历了如下四个阶段：
手工管理阶段
文件系统阶段
数据库系统阶段
高级数据库技术阶段
1.手工管理阶段
50年代中期以前, 计算机主要用于
科学计算 。 数据处理方式基本是批处理 。 数据与应用程序之间的
关系如图所示 。
特点,据与程序没有独立性；数据不能长期保存；只有程序的
概念，没有文件的概念；系统中没有对数据进行管理的软件。
主要缺点,数据没有独立性，数据的冗余度比较大。
2、文件系统阶段
50年代后期至 60年代中后期 。 文件系统是专门管理外存的数
据管理软件 。 数据处理方式有批处理, 也有联机实时处理 。
在文件系统的支持下, 数据的 逻辑结构与物理结构 之间可以
有一定的差别, 逻辑结构与物理结构之间的转换由文件系统的
存取方法来实现 。 数据与程序之间有设备独立性, 程序只需用
文件名访问数据, 不必关心数据物理位置 。
文件系统阶段有三个方面的问题没有彻底解决：
1,数据冗余度大
2,缺乏数据独立性
3,数据无集中管理
文件是无弹性、无结
构的数据集合。
3、数据库系统阶段
从 60年代后期开始, 为了解决数据独立性问题, 实现数据的
统一管理, 达到数据共享的目的, 发展了数据库技术 。
数据库 （ Database） 是通用化的相关数据集合, 它不仅包括
数据本身, 而且包括关于数据之间的联系 。
数据库也是以文件方式存储数据的, 在应用程序和数据之间,
有一个数据库管理系统 DBMS.
数据库管理系统和文件系统的区别如下,
高度独立性,数据库对数据的存储是按同一结构进行的 。
数据的充分共享性, DBMS对数据的完整性, 唯一性和安全性
都有一套有效的管理手段, 使得数据可以被各个应用程序正确
地访问 。
操作的方便性,数据库管理系统还提供管理和控制数据的各种
简单命令, 使用户编写应用程序时易于掌握 。
数据库系统的主要特点如下：
1．实现数据共享，减小数据冗余
2．采用特定的数据模型
3．数据具有较高的独立性
4．具有统一的数据控制功能
目前较流行的数
据库管理系统有
Oracle,Infirmix,Sy
base,dBase,FoxBa
se,FoxPro,Access,
Clipper,WNIBase
等。
4.高级数据库技术阶段
20世纪 80年代开始, 出现了分布式数据库和面向对象数据库系统
(1)分布式数据库系统,
主要有下面两个特点：
（ 1） 多数处理就地完成：数据库分布在各地, 大多数处理由网
络上各点的局部处理机进行 。
（ 2） 各地的计算机由数据通信网络相联系 。
分布式数据库系统兼顾了集中管理和分布处理两个方面, 因而有
良好的性能 。
(2)面向对象数据库系统
现实世界存在着许多复杂数据结构的实际应用领域, 已有的 层
次, 网状, 关系 三种数据模型对这些应用领域都显得力不从心 。
需要更高级的数据库技术来表达, 管理, 构造与维护大容量的持
久数据 。 面向对象数据库正是适应这种形势发展起来的, 它是面
向对象的程序设计技术与数据库技术结合的产物 。
主要特点,
1.面向对象数据模型能完整地描述现实世界的数据结构, 能表达
数据间嵌套, 递归的联系 。
2.具有面向对象技术的封装性 (把数据与操作定义在一起 )和继承
性 (继承数据结构和操作 )的特点, 提高了软件的可重用性 。
4.1.3 数据库系统
1.数据库系统的组成
数据库系统由五部分组成：
? 硬件系统,有容量足够大的内存, 磁盘和较高的通道能力 。
? 数据库集合,系统有若干个设计合理, 满足应用需要的数据
库 。
? 数据库管理系统软件,数据库管理系统 （ DBMS） 是为数据库
建立, 使用和维护而配置的软件 。
? 数据库管理员,系统一般需要专人来对数据库进行管理, 此
人称为 DBA。
? 用户,用户分两类：一类是最终用户, 对数据库进行联机查
询或通过数据库应用系统提供的界面来使用数据库 。。 另一类
是专业用户, 负责设计应用系统的程序模块, 对数据库进行操
作 。
2.DBMS的主要功能
DBMS作为数据库系统的核心软件，主要目标是使数据库成为
方便用户共享使用的资源，并提高数据的安全必、完整性和可
用性。
DBMS支持三级结构和两级独立性。
数据库管理系统具有 三级结构,也称为三级模式。
即：用户数据逻辑结构、数据的整体逻辑结构和数据的物理
存储结构。
数据库管理系统保证了数据和程序之间的 物理独立性和逻辑
独立性。
DBMS一般具有以下几个功能：
(1)数据库的定义功能, DDL
(2)数据的操纵功能, DML
(3)数据库运行控制功能：
DBMS必须提供以下三方面的数据控制功能：
? 并发控制功能
对多用户并发操作加以控制, 协调 。 DBMS应对要修改的记
录采取一定的措施 。
? 数据的安全性控制
对数据库采用的一种保护措施, 防止非授权用户存取数据,
造成数据泄密或破坏 。
? 数据的完整性控制
是数据的准确性和一致性的测试 。 系统应采取一定的措施
确保数据有效, 确保与数据库的定义一致 。
(4)数据字典, DD
数据字典 DD中存放着对实际数据库各级模式所作的定
义, 即对数据库结构的描述 。 这些数据是数据库管理系
统中有关数据的数据, 称之为元数据 。 DD提供了对数据
库数据描述的集中管理手段, 对数据库的使用的操作都
要通过查阅数据字典进行 。
4.2 Access创建数据库
4.2.1 数据库示例
在 Access中, 一个数据库文件包含该数据库中的所有对象, 如
表, 窗体, 查询, 报表等等, Access数据库文件的扩展名为
,.mdb”。
1.创建新数据库
启动 Access2000 空 Access数据库 确定
保存新数据库为 文件名 gzl
创建
Access将创建一个新的数据库, gzl.mdb”,并在 Access的开
发环境中打开该数据库的, 数据库窗口, 。
如果要在 Access已经打开的情况下创建新数据库, 可
以使用, 新建, 对话框 。
可以使用下面三种方法之一打开, 新建, 对话框：
? 选择, 文件, 菜单中的, 新建, 命令
? 单击工具条中的, 新建, 按钮 。
? 按 [Ctrl+N] 键
打开, 新建, 对话框后, 我们选中, 数据库, 图标,
单击, 确定, 按钮, 输入数据库名称并选择存储路径后
即可创建该数据库 。
1．数据库窗口的组成 工具条
对象列表
对象条
数据库窗口
2.创建新表
表 是关系型数据库中用来存储数据的对象 。
Accese创建一个数据库管理系统时, 首先应设计并创建若干表 。
可以使用多种方法创建表,
? 使用设计器创建表,通过表设计器手工创建表 。
? 使用向导创建表,使用 Accese提供的, 表向导, 迅速创建表 。
? 通过输入数据创建表,直接向表中输入数据的方式创建新表 。
? 导入表,将其它数据库中已经存在的表直接导入到当前的数
据库中 。
? 链接表,将其它数据库中已经存在的表链接到当前数据库中,
从而实现对远程数据的访问和操作 。
3.输入数据
在 Accese中，向表中输入数据有两种方式：
一种方式是通过, 数据表视图, 来输入数据。
? 打开表的, 数据表视图,
? 在, 数据表视图, 中的每一行相应字段下输入所需的数据。
? 当所有的记录输入完之后，单击, 文件, 菜单下的, 保
存,,保存表中的数据。
另一种方式是表创建一个窗体来输入数据 。
4.2.2 在 Access中创建与编辑表
1.表的创建
建立数据库表是一个多步骤的过程 。 具体步骤为：
1） 打开一个数据库；
2） 建立一个新表格；
3） 输入每一个字段名, 数据类型和说明；
4） 确定为每一个字段定义的属性；
5） 设置一个主关键字；
6） 为某些字段建立索引；
7） 保存数据库表 。
2.表的编辑
1,删除字段,
?单击, 设计视图, 的行选择器来选择要删除的字段, 然后按下 Delete鍵
?将鼠标移动到要删除字段, 然后在, 编辑, 菜单中选取, 删除行, 选项；
?将鼠标移动到要删除字段, 然后单击工具栏中, 删除行, 命令按钮；
?将鼠标移动到要删除字段, 然后单击刀标右键, 在弹出的菜单是选择中, 删
除行, 选项 。
2,插入字段,
将光标移到插入字段后的位置, 在, 插入, 菜单中选择, 行, 项即可 。
3,移动字段：
在表的, 设计视图, 中简单地先单击字段的行选择器选中字段, 然后单击
字段并按住鼠标左键将该字段拖运至所要的新位置即可 。
4,修改字段名：
先在, 字段名称, 列中单击所要修改名称的字段, 然后将框中的原字段名删
除, 并输入新字段保即可 。
5,设置主关键字：
主关键字的值用于唯一地标识表中每一条记录 。
主关键字具有下列性质：不允许为空, 不允许重复, 主关
键字一般不允许修改 。
6,设置表间关联
当数据库中的表建成之后, 往往还要将各个不同表中的信息
联系在一起, 这就需要定义表间的关联 。 表之间的关联亦称
表之间的关系 。
1） 关系的作用
来达成各个表中的字段协调一致, 并通过匹配主关键字字
段中的数据来实现这种功能 。
2） 关系的分类
根据两个表中记录的匹配有一对多的关系, 多对多的关系和
一对一的关系
3） 参照完整性,
在输入或删除记录时, 为维护表之间已定义的关系而必须遵循
的规则 。
4） 定义表间的关系
在建立 Access数据库时, 除非不想使关系永久有效, 一般都
应当使用关系建立器在表格间建立关系 。 如果需要, 在以后还
可以中断表格之间的关系 。
操作如下：
A） 打开要操作的数据库, 并关闭所有打开的表 。
B） 单击工具栏上的, 关系, 按钮
C） 如数据库没有定义任何关系, 将会显示一个空白的, 关系, 窗口 。 如需
要添加一个关系表, 可单击工具栏上的, 显示表, 按钮 。
D） 在, 显示表, 对话框中双击选取要作为定义关系的表的名称, 然后关闭
,显示表, 对话框, 会发现, 关系, 窗口中添加了选中的表 。
E） 从某个表中将所要的相关字段拖动到其它表中的相关字段 。
F） 在, 编辑关系, 对话框中可以检查显示在两个表格字段列中的名称以确保
正确性, 必要情况下, 可以进行更改 。
G） 单击, 创建, 按钮创建关系 。
H） 对每一对要关联的表, 重复步骤 5到步骤 8。
建立关系完毕之后, 关闭, 关系, 窗口时, Access将询问是
否要保存用户的布局配置 。 不论是否保存此配置, 所创建的关系都
已保存在此数据库中 。
3.数据输入
数据输入的方法除前面所述的在数据表视图中输入外, 还可以从
外部导入各种类型数据库或各种格式文件中的数据 。 在 Accese 中可
以导入的数据库和文件格式格式包括,dBase,Excel,Exchange，
Lotus 1-2-3,Outlook,Paradox,HTML文件, 文本文件, ODBC数
据库 。
4.3 数据查询与 SQL语言
4.3.1 数据查询概述
查询的结果也是由列和行组成的表, 是在原始数据上的二次加工 。
每一个查询都基于表或其它的查询 。
查询的基本作用如下,
? 可以通过查询 浏览表中的数据
? 利用查询可以使用户的注意力只 集中在感兴趣的数据上 。
? 将经常需要处理的原始数据或统计计算定义为查询, 这将大大
简化数据的处理工作 。
? 查询可以为窗体, 报表以及数据访问页提供数据 。
4.3.2 Access中的数据查询
1,选择查询
它从一个或多个表中检索数据, 选择查询可以用来对记录进行分
组, 并且对记录作总计, 计数, 平均以及其他类型的总和的计算 。
2,交叉查询
利用表格的行和列来统计数据, 结果动态集中的每个单元都是根
据一定运算求解过的表值 。
3,操作查询
在一个操作中对查询所生成的动态集进行更改的查询 。 可以同时
对多个记录进行修改 。 可以把操作查询分为四种类型：删除, 更新,
追加和生成表 。
4,SQL查询
使用 SQL语句来创建的一种查询 。 SQL查询可以包括如下的应用：
联合查询, 传递查询, 数据定义查询和子查询 。
5,参数查询
一种在执行时显示设计好的对话框, 以提示输入信息的查询 。
4.3.3 在 Accese中建立查询
1.查询设计视图：
在 Accese中与查询有关的视图有, 设计,, SQL视图和, 数据表,
视图等三种。这三种视图都可以用来显示一个查询，但是, 设计,
视图和 SQL视图是用来建立查询的，而, 数据表视图主要中显示查
询的动态集。
2.查询中常见的基本操作：
(1)选择添加表或查询
(2)删除表或查询
(3)在查询中实现表或查询的联接
(4)在查询设计表格中添加字段
1.选择
查询
2.双击在设计视
图中创建查询
3.选择查
询类型
Accese查询操作的进入。
4.若选择 SQL
查询在视图中
4.3.4 结构化查询语言 ——SQL
SQL语言,结构化查询语言 (Structured Query Language )
SQL语言是 数据库通用的标准语言,ANSI/ISO给出 SQL的标准文本 。
SQL是 集数据查询, 数据操作, 数据定义和数据控制功能 于一体
的语言 。
目前, 几乎所有的关系 DBMS都支持 SQL。 但不同系统对它都有
不同程度的扩充 。
SQL作为查询标准语言的影响已波及到数据库领域之外, 在人
工智能, 软件工程等领域的产品中也开始采用 SQL作为数据和图
形及其他对象的检索语言 。
SQL的使用方法一般有两种：
一种是以与用户交互的方式联机使用, 称为 交互式 SQL；
另一种是作为子语言嵌入到其他程序设计语言中使用, 称为 嵌
入式 SQL。
两种方式的语法结构基本一致 。
1.Access中的 SQL查询
(1)SELECT语句
SELECT语句完整的语法定义如下：
SELECT[范围 ]{*|表名,*|[表名,]字段 1[AS 别名 1][,[表
名,] 字段 2[AS 别名 2][,… ]]}
FROM 表的描述 [, ][IN 外部数据库 ]
[WHERE 条件表达式 ]
[GROUP BY 列名 1]
[HAVING 内部表达式 ]
[ORDER BY 列名 2]
[WITH OWNERACCESS OPTION]
SELECT语句各个关键词描述如下：
? 范围, 范 围使 用 下 列名 词 之 一,ALL, DISTINCT,
DISTINCTROW或 TOP。 缺省则默认值为 ALL。
? *,从特定的表中指定全部字段 。
? 表名,指定表的名称, 该表中应该包含已被选择的记录的字
段 。
? 字段 1,字段 2：指定字段的名称, 该字段包含了所要获取的
数据 。 如果数据包含多个字段, 则按列举的顺序依次获取它们 。
? 别名 1,别名 2：查询名称,用来作列标头,代替表中原有的列
名 。
? 表的描述,指定表的具体名称, 这些表包含要获得的数据 。
? 外部数据库,专指外部数据库的名称, 有时使用一些不在当
前数据库中的表
整个语句的含义是：
根据 WHIRE子名中的条件表达式, 从基本表中找出满
足条件的元组, 按 SELECT子句中的目标列, 选出元组中的
分量形成结果表, 如果有 ORDER子句, 则结果表要根据指
定的列名 2按升序或降序排序, GROUP子句将结果按列名 1
分组, 每个组产生结果表中的一个元组, 通常在每组中作
用库函数 。 分组的附加条件用 HAVING给出 。
SELECT...INTO语句 是用来创建一个表查询的 。 可以使用造成表
查询来存档记录, 生成表的复制备份, 可输出至另一个数据库的
表的副本, 可用作定期显示数据的报表的依据 。
SELECT … INTO语句完整语法定义如下,
SELECT 字段 1,字段 2[,...] INTO新表 [IN外部数据库 ]]
FROM 操作表
其中各关键词描述如下：
? 字段 1,字段 2：想要复制的新表的字段名称 。
? 新表：欲创建表的名称 。
? 外部数据库：专指外部数据库的名称 。
? 操作表：从其中选择记录的现存表的名称 。 它可以是单一表或
多重表或一个查询 。
(2)联合查询
联合查询可以在查询动态集中将两个以上的表或查询中的字
段合并为一个字段。
(3)传递查询
Accese传递查询可直接将命令发送到 ODBC数据库服务器 。 使
用传递查询, 不必使用链接与服务器上的表进行连接就可以直
接使用相应的表 。
(4)数据定义查询
数据定义查询与其他查询的不同是：利用它可以直接创建、
删除或更改表，或者在当前的数据库中创建索引。
数据定义查询语名：
CREATE TABLE：创建表。
ALTER TABLE,在已有表中添加新字段或约束。
DROP,从数据库中删除表，或者从字段中删除索引。
CREATE INDEX：为字段或字段组创建索引。
三个关系
S（ 学生 ）,SNO（ 学号）,SN（ 学生姓名），
SD（ 所属系名）,SA（ 学生年龄）
SC（学生选课关系）,SNO（学号）,CNO（课程号），
G（学习成绩）
C（课程关系 ）,CNO（课程号）,CN（课程名子），
PCNO（先行课号码）
SQL例
1.求数学系学生的学号、姓名
SELECT SNO,SN
FROM S
WHERE SD=?MA?;
2.求选修了课程的学生的学号
SELECT DISTINCT SNO
FROM SC;
3.求全体学生的详细信息
SELECT *
FROM S;
或 SELECT SNO,SN,SD,SA
FROM S;
4.求学生学号和学生的出生年份
SELECT SNO,2000-SA
FROM S;
5.求选修 C1课程的学生学号和得分，结果按分数降序排列。
SELECT SNO,G
FROM SC
WHERE CNO=?C1?
ORDER BY G DESC;
6.求年龄在 20岁与 22岁之间的学生学号和年龄。
SELECT SNO,SA
FROM S
WHERE SA BETWEEN 20 AND 22;
7.求在下列各系的学生,MA(数学系 ),CS(计算机系 )
SELECT * FROM S
WHERE SD IN (?MA?,?CS?);
8.求缺少学习成绩的学生学号和课程号。
SELECT SNO,CNO
FROM SC
WHERE G IS NULL;
9.求学生以及他选修课程的课程号码和成绩。
SELECT S.*,SC.*
FROM S,SC
WHERE S.SNO=SC.SNO;
10.求选修 C1课程且成绩为 B以上的学生及成绩。
SELECT S.SNO,SN,SD,SA,G
FROM S,SC
WHERE S.SNO=SC.SNO AND SC.CNO=?C1?
AND (SC.G=?A?OR SC.G=?B?);
11.求选修了课程名为 ‘ J?的学号和姓名。
SELECT S.SNO,S.SN,SC.CNO,C.CN
FROM S,SC,C
WHERE S.SNO=SC.SNO AND
SC.CNO=C.CNO AND
C.CN=?J?;
12.求选修了 C2课程学生姓名。
SELECT SN
FROM S
WHERE EXISTS
(SELECT *
FROM SC
WHERE SNO=S.SNO AND CNO=?C2?);
13.求不选修 C3课程学生姓名。
SELECT SN FROM S
WHERE NOT EXISTS
(SELECT *
FROM SC
WHERE SNO=S.SNO AND CNO=?C3?);
14.求选修了全部课程的学生姓名。
SELECT SN FROM S
WHERE NOT EXISTS
(SELECT * FROM C
WHERE NOT EXISTS
(SELECT * FROM SC
WHERE SNO=S.SNO AND CNO=C.CNO));
15.求计算机系的学生以及年龄小于 18岁的学生。
SELECT * FROM S
WHERE SD=?CS? UNION
SELECT * FROM S WHERE SA<18；
16.求学生总人数。
SELECT COUNT(*)
FROM S;
17.求选修了课程的学生人数。
SELECT COUNT(DISTINCT SNO)
FROM S;
18.求计算机系学生的平均年龄。
SELECT AVG(SA)
FROM S;
19.求课程号及修选该课程的学生人数。
SELECT CNO,COUNT(SNO)
FROM SC
GROUP BY CNO;
20.求选修课程超过 3门的学生学号。
SELECT SNO
FROM SC
GROUP BY SNO
HAVING COUNT (*)>3
2.SQL数据操纵
数据操纵是指对关系中的具体数据进行增加, 删除, 修改等操作 。
(1)增加记录
往表里增加记录,有两种格式, 一种是插入常量数据, 实现一条
记录的插入；另一种方法是把子查询的结果插入到另一个表中, 可
以插入多条记录 。 INSERT INTO语句,
多重记录追加查询：
INSERT INTO 表名 [IN 外部数据库 ] [字段 1[,字段 2[,...]])]
SELECT [数据库,]字段 1[,字段 2[,...]
FROM 表
单一记录追加查询：
INSERT INTO 表名 [(字段 1[,字段 2[,...]])]
VALUES (值 1[,值 2[,...])
例如, INSERT INTO S
(SNO,SN,SD,SA) VALUES(“S9”,”WANG”,”男,,19)
(2)数据更新
是对数据进行修改，一般在 WHERE子句中指明具体的条件，
以限定修改的范围。数据更新用 UPDATE语句。
UPDATE S SET SA =30 WHERE SNO =“S9”;
3．数据删除
删除的对象是记录，用 DELETE语句。
DELETE * FROM S WHERE SD ="CS";
3.SQL数据控制
通过对数据库各种权限的授予或回收可以对整个数据库进
行合理的管理。
这些权限包括：
修改 (ALTER)、插入 (INSERT)、删除 (DELETE)、
更新 (UPDATE)、创建索引 (CREATE INDEX)、
查询 (SELECT)和所有权限。
4.嵌入式 SQL
SQL语言可以单独地使用，这就是 交互式 SQL语言,也可以在应用
程序中 嵌入使用,应用程序使用的高级语言称为主语言。
嵌入式 SQL在使用时有几个规定：
(1)在程序中要区分 SQL语句与主语言的语句：
所有的 SQL语句前在加 EXEC SQL，结束一般加 (； )。
(2)数据库的表和列与程序之间的通信
?SQL语句中可以使用主语言的程序变量，使用时，这些变量名前面
要冒号 (:)作为标识，以与列名区别。
?程序中使用的所有的表或视图，都要用 EXEC SQL DECLARE 语句
说明。
?由于 SQL SELECT语句执行的结果是一个元组集，要用游标
（ Cursor)机制作为桥梁，将集合操作转化为一条记录的操作。
4.4 关系数据库
4.4.1 数据描述
1.从现实世界到机器世界
（ 1） 现实世界：事物与事物之间存在着一定的联系
（ 2） 信息世界：现实世界在人们头脑中有反映 。
（ 3） 机器世界：用数据模型来表示数据的组织, 将信息世界
中的实体, 以及实体间的联系抽象为便于计算机处理的方式 。
2.信息世界的概念模型
E－ R模型 （ 实体 -联系模型 ）
E－ R图一般有实体, 属性以及实体间的相互联系三个要素 。
实体间的联系一般有如下三种类型：
?1,1（ 一对一联系 ）
?1,N（ 一对多联系 ）
?M,N（ 多对多联系 ）
E－ R方法为抽象的描述现实世界提供了一种有力工具, 它表
示的概念模型是各种数据模型的共同基础, 进行数据库设计
时必然要用到它
4.4.2 数据模型
1.非关系模型
层次模型和网状模型统称为格式化模型。
(1)层次模型
用树形结构表示实体及其之间联系的模型称为层次模型 。
层次模型一般有以下特点：
1） 有且仅有一个结点无父结点, 此即为树的根；
2） 其他结点有且仅有一个父结点 。
(2)网状模型
用网状结构表示实体及其之间联系的模型称网状模型。
2.关系模型
关系模型是由二维表格结构作为基础。
关系模型是由若干个关系模式组成的集合。每个关系模式
实际上是一张二维表。
（ 1） 二维表
关系模型是用二维表的形式表示实体和实体间联系的数据
模型。从用户观点来看，关系的逻辑结构是一个二维表，在
磁盘上以文件形式存储。
关系模型和网状、层次模型的最大差别 是：关系模型用
关键码而不是用指针来表示和实现实体间联系。表格简单、
易懂，用简单的查询语句就可以对数据库进行操作。并不涉
及存储结构。是一种具有严格的设计理论模型,
2．基本术语
关系,一个关系就是一张二维表, 每个关系有一个关系名 。
元组,表中的行称为元组 。 一行为一个元组, 对应于存储文件中
的一个记录值 。
属性,表中的列称为属性, 每一列有一个属性名 。 属性值相当于
记录中的数据项或者字段值 。
域,属性的取值范围, 即不同元组对同一个属性的取值所限定的
范围 。
关键字,属性或属性组合, 其值能够唯一地标识一个元组 。 例如,
零件关系中的零件编号；项目关系中的项目编号 。
关系模式,对关系的描述 。 格式为：关系名 (属性名 1,属性名
2....属性名 n),如：零件 （ 零件编号, 零件名称, 颜色, 重量 ） ；
项目 （ 项目编号, 项目名称, 开工日期 ） 等 。
元数,关系模式中属性的数据项目是关系的元数 。
关系模型中, 记录之间的联系是通过关键码来体现的 。 例
如, 要查询项目 S2所选课程是什么名称？ 首先要在学生－选课
关系中找到学号 S2,然后在关系中找到对应课程号为 C6。 再在
课程关系中找到 C6对应的课程名 。 在上述查询过程中, 关键码
课程号起到了连接两个关系的作用 。
关系模型中的各个关系模式不应当孤立起来，不是随意拼
凑的一组二维表，它必须满足一定的要求。
（ 3） 关系模型的特点
① 关系必须规范化,
关系模型中的每一个关系模式都必须满足一定的要求, 如每
个属性值必须是不可分割的数据单元, 即表中不能再包含表 。
② 模型概念单一,
在关系模型中, 无论实体本身还是实体间的联系均用关系表
示 。 多对多联系在非关系模型中不能直接表示, 在关系模型中
则变得简单了 。 如学生选课 。
③ 集合操作,
在关系模型中，操作的对象和结果都是元组的集合即关系。
例如，要查询项目 J02所用零件的名称、颜色和重量，操作结
果是零件关系的一个子集。这个子集本身也是一张二维表。
3,面向对象模型
面向对象的数据库是面向对象的概念与数据库技术相结合的产物 。
面向对象模型中最基本的要领是对象 （ object） 和类 （ class） 。
（ 1） 对象,现实世界中实体的模型化, 每个对象有唯一的标识符,
把一个状态和一个行为封装在一起 。
（ 2） 类,每个类由两部分组成, 一是对象类型, 二是对这个对象
类型进行的操作方法 。 对象的状态是描述该对象属性值的集合,
对象的行为是对对象操作的集合 。
（ 3） 类层次,一个系统中所有的类和子类组成一个树状的类层次,
一个类继承其直接或间接祖先的所有属性和方法 。
4.4.3 关系的规范化
1.规范化
在下表学生选课表 。 如果删除学号为 150的学生的选课记录, 那
么不仅丢掉了学生 150选修, 市场营销学, 的事实, 而且还失去了
,市场营销学, 的学分是 2的事实, 即更新异常 。 若有一门, 法律,
课, 学分为 3,但无学生选修时, 不能输入 。 即存在插入异常 。
学号 课程 学分
100 人工智能 3
125 文化学 2
150 市场营销学 2
175 数理逻辑 2
190 文化学 2
把选修关系分解成两个关系, 每个关系处理一个不同的主
题来 消除更新异常和插入异常 。
如分解成学生 -选课, 课程 -学分关系
（ a） 学生 选课表 （ b） 课程学分表
学号 课程 课程 学分
100 人工智能 人工智能 3
125 文化学 文化学 2
150 市场营销 市场营销 2
175 数理逻辑 数理逻辑 2
190 文化学
这样更新异常和插入异常都消除了, 对关系进行分解的过
程就叫做规范化 。 关系的规范就是对有异常的关系进行分解
以消除异常的过程 。 在分解关系时, 同时注意到多个关系之
间的相互参照性 。
2.函数依赖
函数依赖 是关系属性之间的一种联系。如果给定了一个属性的值，
就可以获得（或找到）另一个属性的值。例如，如果我们知道了
,课程名, 的值，我们就可以知道, 授课学时, 的值。我们说, 授
课学时, 函数依赖于, 课程名,,或, 课程名, 可以决定, 授课学
时, 。记作课程名 → 授课学时。 表 4-7 课程表
436面向对象X002
354数值分析X001
672编译原理Z006
572操作系统Z004
254C程序设计J003
672数据库J001
授课学期授课学时课程名课程号
函数依赖关系反过来不一定成立 。 比如, 授课学时, 值为 72
的课程有好几门：数据库, 操作系统, 编译原理 。 也就是说,
如果 A决定 B,但反过来不一定 B就决定 A。 一般来说, 如果 A决定
B,则 A和 B之间的关系是多对一的关系 。
我们再来看一看学生选课表 。 在这个表中, 主要关键字是属
性集合 {学号, 课程 }。 主关键字决定了, 学分, 的值, 即, 学
分, 函数依赖于主关键字 {学号, 课程 }。 如果我们再进一步分
析, 我们就会发现, 决定, 学分, 的只是, 课程,, 与, 学号,
无关, 我们把这种依赖称为 部分依赖
下表中, 该表的主关键字是, 学号,, 学生住宿的楼号依
赖于学号, 但是, 学生应交的住宿费是由楼号决定的, 也就
是说,, 收费, 依赖于, 楼号,, 这是一种新的依赖关系：
,楼号, 依赖于, 学号,, 而, 收费, 又依赖于, 楼号, 。
一般把这种依赖关系称为, 传递依赖, 。
8008150
6004120
5002130
5002100
2
楼号
500180
收费学号
属性间的三种联系
至此, 我们讨论了关于属性间的三种联系：依赖, 部
分依赖和传递依赖 。 下面我们将看到, 关系属性间的依
赖关系与关系的更新异常有着密切的联系 。
实质上, 关系中分为二类属性,主属性和非主属性 。
规范化理论讨论主属性之间的关系及非主属性与主属
性之间的关系 。
3.范式
需要对关系进行规范化以减少更新异常 。
在规范化过程中, 必须遵循一定的准则以指导关系的规范化,
一般把这些准则称为 范式 （ Normal forms,简记 NF） 。
范式对关系中各属性间的联系提出了不同级别的要求, 根
据要求级别的高低, 将关系分为第一范式 （ 1NF）, 第二范式
（ 2NF）, 第三范式 （ 3NF）, Boyec-Code范式 （ BCNF）, 第四
范式, 第五范式, 域关键字范式等几种 。 其中, 高级别的范式
包含在低级别的范式中 。
第一范式
任何符合关系定义的表都是第一范式的 。
即表的每一属性的域必须是基本类型的, 集合, 数组和结构
都不能作为属性的类型, 每一列的名字必须是唯一的 。 符合第
一范式的关系有插入, 删除, 异常 。 修改复杂 。
造成异常的原因是因为表中描述了两个不同的主题 。 在关系
中, 存在着部分依赖：该关系的主关键字是 {学号, 课程 },但
,学分, 只由, 课程, 决定, 与, 学号, 无关, 也就是, 学分,
属性只由主关键字 {学号, 课程 }的一部分而不是全部来决定 。
这就是导致异常的原因 。
第二范式
第二范式的定义为：
如果一个关系的所有非主关键字属性都完全依赖于整个主关
键字 （ 也就是说, 不存在部分依赖 ）, 那么该关系就属于第二
范式 。
根据这一定义, 凡是以单个属性作为主关键字的关系自动就
是第二范式 。 因为主关键字只有一个, 不会存在部分依赖的情
况 。 因此, 第二范式只是针对主关键字是组合属性的关系 。
第二范式中的关系也有异常情况由于存在传递函数依赖关
系，因此，如（学号、楼号、收费），虽然学号是单属性主关
键字，属于第二范式，而楼号、收费都由学号决定，但此关系
仍然有异常。
第三范式
第三范式的定义为：
一个关系如果是第二范式的, 并且没有传递依赖关系,
则该关系就是第三范式的 。
例如：学生住宿关系可以分解为两个关系：学生 -楼号
关系 （ 学号, 楼号 ） 和楼号 -收费关系 （ 楼号, 收费 ） 。 这
两个关系已经是第三范式的了 。
在数据库规范化理论中, 除了我们这里所介绍的三种
范式外, 还有 Boyec-Code范式, 第四范式和第五范式,
随着范式级别的增高, 对关系的分析越细致, 要求也越
高 。
1NF
消除非主属性对码的部分函数依赖
2NF
消除非主属性对码的传递函数依赖
3NF
4.设计折中
规范化可以消除更新异常, 但有时不见得就值得 。 比如, 考
虑关系：客户 （ 客户编号, 客户名, 省, 城市, 邮政编码 ）, 其
中, 客户编号, 是主关键字 。 该关系不是第三范式的, 因为存在
传递依赖关系：
客户编号 → 邮政编码, 邮政编码 → (省, 城市 )
该关系可以分解为如下两个关系,
·客户 （ 客户编号, 客户名, 邮政编码 ） 。
其中, 客户编号, 是主关键字；
·编码 （ 邮政编码, 省, 城市 ） 。
其中, 邮政编码, 是主关键字 。
现在这两个关系都属于第三范式了, 但这样做可能并不一定
就是好的设计 。 有时分解前的非规范化的表 可能更好, 因为处
理起来可能比较容易, 尽管这样会造成, 省, 和, 城市, 的数据
重复 (称数据冗余 ）, 但有时并不十分计较这个缺点 。
小 结
本章主要讨论了数据与信息的联系和区别,数据管理技
术的发展过程,数据库系统的组成和数据库管理系统的主要
功能 。
以 Access数据库管理系统为背景重点介绍了数据库建立
和数据库查询的方法, 也对结构化查询语言与 SQL作了简要
介绍, 最后对数据之间关系的描述和数据库模型, 特别对
关系数据库作了讨论 。
综合练习题
一．选择题：
1.（ db）已知某二叉树的前序序列是 ABDC，中序序列是 DBAC，问它的后序序
列是＿＿＿。
(A) ADBC (B) DBCA (C) CABD (D)DCBA
2.(db)在一个具有 n个顶点的无向完全图中，包含有 _______多边；在一个具
有 n个顶点的有向完全图中包含有 _______条边。
(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)n2
3.(db)从逻辑上可以把数据结构分为 ________.
(A)动态结构和静态结构 (B)顺序组织和链接组织
(C)线性结构和非线性结构 (D)初等类型和组合类型
4.(db)单链表的每个结点中包含一个指针 next,它指向该结点的后继结点,
现在要将指针 q指向的新结点插入到指针 p指向的单链表结点之后, 下面的操
作序列中哪一个是正确的 ______。
(A)q=p->next;p->next=q->next; (B)p->next=q->next;q=p->next;
(C)q->next=p->next;p->next=q; (D)p->next=q->next;q->next=p->next;
5.(db)以下那一个不是队列的基本操作 。
(A)从队尾插入一个新元素 (B)从队列中删除第 j个元素
(C)判断一个队列是否为空 (D)读取队头元素的值
6.(db)若进栈序列为 1,2,3,4,假定进栈和出栈可以穿插进行, 则可能
出栈的序列是 _____.
(A)2,4,1,3 (B)3,1,4,2 (C)3,4,1,2 (D)1,2,3,4
7.(db)若进栈序列为 1,2,3,4,假定进栈和出栈可以穿插进行, 则不可
能出栈的序列是 _____.
(A)1,4,3,2 (B)2,3,4,1 (C)3,1,4,2 (D)3,4,2,1
8.(db)在一个具有 n个顶点的无向图中, 要连通全部顶点至少需要 _______
条边 。
(A)n (B)n+1 (C)n-1 (D)n/2
9.(db)对于一个具有 n个顶点的图, 若采用邻接距阵表示, 则该距阵的大小
为 _______。
(A)n (B)(n-1)2 (C)(n+1)2 (D)n2
10.(db)对于一个具有 n个顶点和 e条边的无向图, 若采用邻接表表示, 则表头
向量的大小为 ___(1)____,所有顶点邻接表中的接点总数为 __(2)_____。
(1)(A)n (B)n+1 (C)n-1 (D)n+e
(2)(A)e/2 (B)e (C)2e (D)n+e
11.(db)已知一个图如图习题 -1所示, 当从顶点 v1出发构造最小生成树的过程
中, 依次得到的各条边为 ____________。
(A)(v1,v5)5,(v5,v2)7,(v5,v3)9,(v3,v4)3
(B)(v1,v5)5,(v1,v2)8,(v2,v5)7,(v3,v4)3
(C)(v3,v4)3,(v1,v5)5,(v2,v5)7,(v3,v5)9
(D)(v3,v4)3,(v2,v5)7,(v1,v5)5,(v3,v5)9 图习题 -1
12.(db)已知一个图如图习题 -2所示, 从 VA 到 VD 的最短路径长度为
_(1)______,最短路径为 ___(2)____
(1)(A)16 (B)18 (C)15 (D)20
(2)(A)(va,vb,vc,vd) (B)(va,vb,ve,vc,vd)
(C)(va,vc,vd) (D)(va,vd) (E)(va,vb,ve,vd)
13.(os)临界区是指进程中用于 _____的那段代码。
(A)实现进程互斥 (B)实现进程同步
(C)实现进程通信 (D)访问临界资源的那段代码
14.(os)分区管理要求对每一个作业都分配 _____的内存单元。
(A)地址连续 (B)若干地址不连续的
(C)若干连续的页框 (D)若干不连续的页框
15.(os)由分页系统发展为分段系统的主要动力是 _____。
(A)满足用户需要 (B)提高系统吞吐量
(C)提高内存利用率 (D)更好地满足多道程序运行的需要
16.(os)在请求式分页存储管理系统中有多种置换算法，其中选择在最近一段
时间内最久没有被访问的页面淘汰的算法称为 _____。
(A)最佳淘汰算法 (B)先进先出算法
(C)最久未用算法 (D)最近最久未用算法
17.(os)内存分配的基本任务是为每道程序分配内存。使每道程序能在不受干
扰的环境下运行，主要是通过 ______功能实现的。
(A)内存保护 (B)动态连接 (C)内存扩充 (D)内外存交换
18.(SOFT)白盒法考虑的是测试用例对程序内部逻辑的覆盖程度, 条件组
合覆盖标准虽然较强, 但仍不能保证覆盖程序中的 ________。
(A)每一条语句 (B)每一个判定 (C)每一个条件 (D)每一条路径
19.(SOFT)结构化程序的控制结构是由 ________三种基本控制结构组成的 。
(A)顺序, 分支和条件 (B)顺序, 转向和分支
(C)分支, 转向和循环 (D)顺序, 分支和循环
20.(SOFT)在软件生命周期的各阶段中, 工作量最大的是 __________阶
段 。
(A)设计 (B)编程 (C)测试 (D)维护
21.(SOFT)在软件工程中, 盒图 (N-S)图是在 __________阶段产生的 。
(A)需求分析 (B)概要设计 (C)详细设计 (D)编程
22.(SOFT)数据流图是描述一起目标系统的 _____________的 。
(A)数据流 (B)系统分解 (C)处理逻辑 (D)数据存储
二, 填空题：
23.(db)已知一个有序表为 （ 12,18,24,35,47,50,62,83,90,115，
134）, 当二分查找值为 90的元素时, ___次比较后成功；二分查找值为 47的元素
时, __次比较后成功 。
24.(db)在一棵具有 n个结点的顺序二叉树中, 若编号为 i的结点有左孩子, 则左
孩子结点的编号为 ______,若有右孩子, 则右孩子的编号为 ______;若有双亲结点,
则当 i为偶数时, 双亲结点的编号为 ______;当 i为奇数时, 双亲结点的编号为
______。
25.(os)虚拟设备是指采用某种 ________,将某个 ____设备改进为多用户可共享
的设备 。
26.(os)从资源分配角度,外设可分为独占设备, _____设备, 虚拟设备 。
27.(os)当仅有两个并发进程共享临界资源时, 互斥信号量取值范围为 _____三个
值 。
28.(soft)1983年 IEEE把软件工程定义为：软件工程是开发, 运行, ____,维护
和修复软件的系统方法 。
29.(os)_______(PCB)是进程状态和控制进程转换的标志 。
30.(os)进程的 ______就是两个进程不能同时进入访问同一临界资源的临界区 。
31.(os)产生死锁的四个必要条件,互斥条件, _____,保持与再请求条件, 环路等待条件 。
32.(os)已经获得 CPU及其他运行资源, 正在运行的进程处于 _____状态 。
33.(os)共享资源的方式与进程的合作带来了进程间的相互制约关系, 称为直
接制约关系 。 直接制约的关系带来了进程的 ______。
34.(os) 当阻塞进程的阻塞原因清除后, 该进程转为 _____状态 。
35.(os) 仅允许一个进程使用的资源称为 ________；一个进程访问这种资源的
那段代码称为 __________。
36.(os) 地址重定位是指 __________到物理地址的转换 。
37.(os) 分页存储管理中, 地址变换机构把逻辑地址分成两部分 _______。
38.(os) 内存分配算法中, 首次适配法的空闲区应按 ______顺序排列；在最佳
适配法中, 空闲区应按 ________次序排列 。
39.(os) 页是信息的 _______单位, 进行分页是于 _______的需要；分段信息的
______单位, 分段是出于 _______需要 。
40.(os) 在生产者 -消费者问题中, 应设置互斥信号量 muter,资源信号量 full
和 emtry。 它们的初值分别是 ______,________,_______。
41.(os) 为解决高速 CPU与低速外设之间的速度不匹配,系统采用 _____技术 。
42.(os) 逻辑设备是 _____属性的表示, 它并不指某个具体的设备, 而是对
应于一批设备 。
43.(os) 文件的逻辑结构有二种,一种是字符流式文件 。 另一种是 _____。
44.(os) 文件的顺序存取是按 _______进行读 /写操作 。
45.(os) 为方便用户使用文件,只需知道文件的符号名就可以对文件进行存
取,称为 ________。
46.(db)已知一个有向图的邻接表如图习题 -3所示, 则从顶点 V1出发按深度
优先搜索进行遍历得到的顶点序列为 _______,按广度优先搜索遍历得到的
顶点序列为 _______。
三, 改错题：
47,段页式存储管理中, 段是作业地址空间的最小管理单位 。
48,当阻塞进程的阻塞原因消除后, 该进程恢复到执行状态 。
49,使用了 P,V操作, 系统就不会死锁 。
50,设备的无关性是指用户程序与实际使用的物理设备无关 。
51,顺序文件适于建立在顺序存储设备上,而不适合于建立在磁盘上 。
52.二叉树中每个结点有二个子结点, 而对一般的树则无此限制, 因此二叉
树是树的特殊情况 。
四．问答题：
53.(os) 进程的三种状态间转换的原因是什么?
54.(db) 已知一组记录的排序码为（ 46,74,18,53,14,26,40,38,86,65）利
用快速排序的方法,写出每次划分后的排列结果。
55.(os),加锁, 和, 开锁, 原语的作用是什么?
56.(os) 述 P(S),V(S)操作过程。
57.(os) 什么是虚拟存储器?虚存的容量是什么决定的?
58.(os) 分页与分段存储管理的区别是什么?
59.(os) 进程的三种状态间转换的原因是什么?
60.(os) 文件按文件系统对文件施加的保护可分为几类?
61.(os) 什么是逻辑文件?什么是物理文件?
62.(Soft) 什么是软件危机？产生软件危机的原因是什么？
63.(Soft)什么是软件工程？什么是软件工程学？
64.(Soft)什么是软件生存周期？软件生存周期为什么要划分阶段？常用的
软件生存周期模型有哪几种？它们的主要特点是什么？
65.(Soft)软件设计分哪两个步骤？ 每一步骤的任务是什么？
66.(Soft)软件测试阶段分哪几个步骤？ 什么是白盒法？ 什么是黑盒法？
67.(dbf) 数据和信息的关系如何？
68.(dbf) DBMS有哪些主要功能？
69.(dbf) 数据模型有哪几种？
70.(dbf) 举例说明层次模型, 网状模型和关系模型 。
71.(dbf) 关系模型有什么特点？
72.(dbf) SQL语言有哪些功能？
73.(db) 数据结构 S是一个二元组 S=（ D,R）, 其中的 D和 R各代表什么？
74.(db) 什么是数据的逻辑结构和物理结构？
75.(db) 栈与队列是两种特殊的线性表, 栈的特点是什么？ 队的特点是什么？
76.(db) 由 a,b,c三个结点构成的二叉树, 共有多少种不同的结构？
77.(db) 一组有序的关键字如下 51,22,28,67,90,33,17,15,33,41,设法画出
一棵具有平衡性的二叉排序树 。 （ 提示：以中间位置元素为根 ）
78.(db) 一组记录的关键码为 （ 46,79,56,38,40,84）, 利用快速排序的
方法, 写出以第一个记录为基淮得到的一次划分结果 。
79.(db) 一组记录的排序码为 (48,25,16,35,79,23,40,36,72,90),其中含有
５个长度为２的有序表, 写出按归并排序方法对该序列进行一趟归并后的结果 。
五, 程序填空：
81.设 t是 —棵结点值为整数的查找树 (即二叉检索树或二叉排序树 ),a是一个任意
给定的整数 。 在下面的程序段中, 函数 free_tree(t)对二叉树 t进行后序遍历时
释放二叉树 t的所有结点, 函数 delete_subtree(t,a),首先在查找树 t中查找值
为 a的结点, 根据查找情况分别进行如下处理：
1)若找不到值为 a的结点, 则不进行删除, 仅返回根结点的地址 。
2)若找到了值为 a的结点, 则删除以此结点为根的子树, 并释放此子树中所的结
点 。 在删除非空子树时, 如果值为 a的结点是查找树的根结点, 删除后变成空的
二叉树, 那么返回 NULL／ nil;否则, 返回树 t的根结点的地址 。
typedef struct node{ int data; struct node *lchild,*rchild;
}NODE;
void free_tree(NODE *t)
{ if(t!=NULL)
{ free_tree(t->lchild); free_tree(t->rchild);
_____(A)_______ ;
}
}
NODE *delete_subtree(NODE *t,int a)
{ NODE *p=NULL,*q=t;
while(___(B)___)
{ p=q;
if(a<q->data) q=q->lchild; else q=q->rchild;
}
if(q!=NULL)
{ free_tree(q);
if(p==NULL) t=NULL;
else
if (a<p->data) __(C)___;
else ___(D)___;
}
return(t);
}
81,在下面的程序段中, 函数 union(A,B)求出给定的集合 A和集合 B之并集 C。
这里用链键表按值从小到大依次存放集合中各元素 。 所谓集合 C是集合 A和集
合 B的并集, 即：若 e属于集合 A或属于集合 B,则 e是集合 C的元素 。 但当 e既属
于集合 A,也属于集合 B时, e只能在集合 C中出现 — 次 。 在执行求并运算之前,
链表 C首先增加 — 个附加的表头结点, 以便新结点的添加, 当运算执行完毕,
再删除并释放链表中附加的表头结点 。 函数 append(last,d)在链表中把为 d的
新结点添加到 last所指的结点的后面并返回新结点的地址 。
程序
typedef struct node{ int element;
struct node *link;
}NODE;
NODE *A,*B,*C;
NODE *append(NODE *last,int d)
{ last->link=(NODE*)malloc(sizeof(NODE));
____(A)___;
last->element=d;
return(last);
}
NODE *union(NODE *A,NODE *B)
{ NODE *C,*last;
C=last=(NODE *)malloc(sizeof(NODE));
while(_________(B)_______)
if(A->element<B->element)
{ last=append(last,A->element);
A=A->link; }
else
if(A->element==B->element)
{ last=append(last,A->element);
A=A->link;_____(C)__;}
else { last=append(last,B->element);
B=B->link; }
while(A!=NULL)
{ last=append(last,A->element);
A=A->link; }
while(B!=NULL)
{ last=append(last,B->element);
B=B->link; }
________(D)____;
last=C; C=C->link;
free(last); return(C);
}
82,在下面的程序段中, 非递归函数 Count_leaf(t)住给定的二叉树 t中, 利用
遍历二义树的方法, 统计出叶子结点的个数 。 程序中使用一个顺序存储的栈
stack存放正在遍历的子树的根结点的地址, 栈顶指针是 top,我们置 top为 -1表
示栈空 ;栈非空时,top总是指向最后进栈结点存放在数组 slack中的位置 。 栈中
可用单元共有 100个, 它们依次为 stack[0],?, stack[99]。 为简单起见, 这
里假设栈不会出现溢出情况, 故没有进行栈溢出处理 。
#define MAXN 100
typedef struct node{ int data; struct node *lchild,*rchild;}NODE
int count_leaf(NODE *t)
{ NODE *stack[MAXN]; int top=-1,count=0;
while(______(A) ____)
{ while(t!=NULL)
{ if(＿ (B) ________) count++;
stack[++top]=t;____(C)__; }
if(top>=0)
{ t=stack[top--]; _(D)___;}
}
return(count);
}
83,设 t是一棵结点值为整数的二叉查找树, a是任意整数 。 下面的程序段实
现了在给定的查找树 t中查找值为 a的结点的伯父或叔父 (父亲的兄弟 )结点 。
如果树 t不存在值为 a的结点或存在值为 a的结点而找不到它的伯父或叔父结
点, 那么返回 NULL；否则, 值为 a的结点在树 t中且存在伯父或叔父, 那么
返回伯父或叔父结点的存放地址 。
#include <stdio.h>
typedef struct node { int data; struct node *lchild,*rchild;
} NODE;
NODE *find_uncle(NODE *t,int a)
{ NODE *p=NULL; *pp=NULL;
while(_____A______)
{ pp=p; p=t;
if(a<t->data) ____B__;
else ____C__;
}
if(t==NULL||pp==NULL) return(NULL);
else if(____D____)return (pp->rchild);
else return (pp->lchild);
}
84.下面的程序段以给定的链表 head的第一个结点的值为标准, 对链表 head的结
点重新排列, 把小于第一个结点值的结点排在链表前面, 把大于等于第一个结点
值的结点排在链表后面, 而把第一个结点排在中间 。 在程序段中使用一个链接队
列, 用于链接小于第一个结点值的所有结点 。 在程序段的执行中, 始终没有改动
结点中的值, 而只改变结点的链接指针值 。
#include <stdio.h>
typedef struct node { int data;struct node *like; } NODE;
NODE *re_order(NODE *head)
{ NODE *h,*p,*q,*r; int t;
if(head==NULL||head->link==NULL) return (head);
h=NULL; t=head->data; p=head;
while(______A_______)
if(p->link->data<t)
{ q=p->link;p->link=q->link;
if(h==NULL) h=q;
else ________B______;
r=q; }
else ________C________;
if (h==NULL) return (head);
else {_____D_____; return(h);} }
85.下列程序是把一单链表反转 (置换 )算法：请把程序填完全 。
struct node *invert_last(struct node *head)
{ struct node *mid,*last;
mid=NULL;
while(head!=NULL)
{ last=mid; mid=head; head=head->next;
_____________;
}
last=mid;
return(___________);
}
86.单链表的删除：在已给定的链表 h中,删除 data值为 m的结点 。
相应算法,
struct node *del(struct node *h,int m)
{ struct node *p1,*p2;
if(h==NULL)
{ printf("\n This null!\n");return(h);
}
p1=h;
while((p1->data!=m)&&(p1->next!=NULL)){ p2=p1;_____________;}
if(p1->data==m)
{ if(p1==h) h=p1->next;
else _________________;
}
else printf("%d nod beed found! \n",m);
return(h);
}
87．设有四个关系，码用下横线来表示：
供应商 (供应商代码, 姓名, 地址, 电话 )
工程 (工 程代码, 工程名, 负责人, 预算 )
零件 (零件代码, 零件名, 规格, 产地, 颜色 )
供应零件 (供应商代码, 工程代码, 零件代码, 数量 )
要求用 SQL语句完成如下查询：
(1)找出所有供应商的姓名和地址、电话。
(2)找出所有零件的名称、规格、产地。
(3)找出使用供应商代码为 S1供应零件的工程号。
(4)找出工程代码为 J2的工程使用的所有零件名称、数量。
(5)找出产地为上海的所有零件代码和规格。
(6)找出使用上海产的零件的工程名称。
(7)找出没有使用天津产的零件的工程号。
(8)找出使用供应商 S2供应的全部零件的工程号。
(9)找出工程代码为 J2的工程使用的所有零件名称、数量。
(10)找出使用上海产的零件的工程号。
(11)把全部红色零件的颜色改成蓝色。
(12)由 S10供给 J4的零件 P6改为由 S8供应。请作必要的修改。
(13)从供应商关系中删除 S2的记录，并删从供应零件关系中删除
相应的记录。
(14)请将 (S2,J8,P4,200)插入供应零件关系。
(15)将工程 J2的预算改为 40万元。
(16)删除工程 J8订购的 S4的零件。