计算机软件技术基础

《计算机软件技术基础》由会员分享，可在线阅读，更多相关《计算机软件技术基础（366页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 软件工程软件工程第二章第二章 数据结构数据结构第三章第三章 操作系统操作系统第四章第四章 数据库技术数据库技术第五章第五章 面向对象程序设计面向对象程序设计第六章第六章 计算机网络计算机网络第七章第七章 网页设计网页设计综合练习题综合练习题第一章第一章 软件工程软件工程本章简单介绍软件工程的形成和发展，重点介绍软件开发的不同方法和软件测试策略与方法，最后就软件开发环境和软件重用技术作一简要介绍。1.1 1.1 概述概述软件工程的提出源于20世记60年代末期出现的“软件危机”，并在较短的时间内发展成一个完整的学科方向，30多年来，在理论研究和工程实践两个方面作了大量的工作。1.1.

2、1 1.1.1 软件工程的形成与发展软件工程的形成与发展1.1.软件发展的三个阶段软件发展的三个阶段 软件开发方法从机器语言编程到软件工程方法，经历了三个阶段。 1.程序设计时期（1946年到60年代中期） 生产方式是手工生产、个体劳动。只有程序，无软件的概念。 2.软件时期（60年代中期至70年代中期） 程序不再是硬件的附属，有软件的概念。 作坊式的生产方式已难满足软件生产的质量和数量上的要求。出现了“软件危机”。3.软件工程时期（70年代至今）1968年、1969年北大西洋公约组织成员国的软件工件者召开了两个研讨会，提出了“软件工程”这一述语，根本目的在于克服“软件危机”中所遇到的困难问题

3、，从此进入软件工程时代。2.2.软件危机软件危机(1) (1) 软件危机的主要表现：软件危机的主要表现：1)软件开发成本和进度的估计常常很不准确。2)用户往往对已完成的软件不满意。3)软件的质量常被怀疑。4)软件极难维护。 5)缺乏良好的软件文档。6)软件开发生产率提高的速度远远跟不上计算机应用迅速普及深入的趋势。(2)(2)软件危机的产生原因软件危机的产生原因 一般以为,软件危机的发生与软件产品的特征和软件产品开发与维护的方法不正确有关。其一：软件是逻辑的系统部件而不是物理的系统部件，以程序和文档形式存在，具有无形性。其二：软件规模越来越大，功能越来越强，导致软件结构非常复杂。(3)(3)解

4、决软件危机的途径解决软件危机的途径 方法是要充分吸取和借鉴人类长期以来从事各种工程项目所积累的行之有效的原理、概念、技术和方法，并应用于软件开发的实践中，将软件开发变成一种组织良好、管理严密、各类人员协同完成的工程项目3 3、软件工程、软件工程 1983年IEEE定义为：“软软件件工工程程是是开开发发、运运行行、维维护护和和修修复复软件的系统方法软件的系统方法”。软件工程学的多个分支 (1)软件工程方法学 方法学是研究软件构造技术的学问。一个软件从定义、开发到维护，都需要有适当的方法。 (2)软件工程环境 对最终用户而言，环境就是他们运行程序所使用的计算机系统。 对于应用软件开发人员，环境是开

5、发活动的舞台。 软件工具是环境中最活跃的成分。所谓工具，在这里泛指一切帮助开发软件的软件。在软件开发的各个方面都研制了许多有效的工具。集成化工具的自动切换，可以明显提高软件的生产率。 (3)软件工程管理 软件工程管理的目的，是为了按照软件的预算和进度完成项目计划，实现预期的经济和社会效益。1.1.2 1.1.2 软件工程范型软件工程范型 1、传统的软件工程范型、传统的软件工程范型瀑布模型瀑布模型瀑布模型是1976年由BWBoehm提出的，是基于软件生存周期的一种范型。它它将将软软件件生生存存周周期期分分为为定定义义、开开发发、维维护护三三个个阶阶段段，每个阶段又分为若干个子阶段，各子阶段的工作

6、顺序展开，如自上而下的瀑布。(见后图)定义阶段定义阶段：分析用户需求。问题定义问题定义：收集、分析、理解、确定用户的要求。可行性研究可行性研究：确定对问题是否有可行的解决办法。需求分析需求分析：确定用户对软件系统的全部需求。开发阶段开发阶段：设设计计：设计软件系统的模块层次结构、数据库结构、模块控制流程等。编程：编程：将每个模块的控制流程纺出相应的程序。测试：测试：检查并排除软件中的错误，提高软件的可靠性。维护阶段维护阶段：运行与维护运行与维护：维护软件系统的正常运行。各个阶段确均有相应的文档。问题定义或行性研究需求分析设计编程测试运行与维护（目标与范围说明）（可行性论证报告）（需求说明书）（

7、设计文档）（程序）（测试报告）（维护报告）定义阶段开发阶段维护阶段传统的软件工程范型传统的软件工程范型瀑布模型瀑布模型1.2 1.2 软件开发方法软件开发方法 两种不同的开发方法：结构化开发方法和面向对象的开发方法。1.2.1 1.2.1 结构化开发方法结构化开发方法一、结构化分析 1.结构化分析方法，亦称SA（Structured Analysis）方法。 (1)SA方法的特点： 核心思想：自顶向下和逐步求精。 基本手段：分解和抽象。 分解：把大问题分割成若干小问题，然后分别解决。 抽象： 略去细节，先考虑问题最本质的属性。 使用了描述需求说明书的几个规范工具。 即数据流图、数据词典、小说明

8、（加工逻辑的描述）等，使文档规范化。 (2)数据流图（Data Flow Diagram，简称DFD图） SA方法采用“分解”的方法来描述一个复杂的系统，数据流图是描述系统中数据流程的图形工具，它标识了一个系统的逻辑输入和逻辑输出以及把逻辑输入转换为逻辑输出所需要的加工处理。1数据数据 流图的基本符号：流图的基本符号：(1)数据流(2)加工(3)数据存储(4)数据源点或终点。画各层数据流图应注意的问题：画各层数据流图应注意的问题：(1)父图和子图平衡(2)子图的编号(3)数据守恒(3)数据词典（Data Dictionary，简称DD）对数据流图中包含的所有元素的定义的集合构成了数据字典。 数

9、据词典中有四种类型的条目：数据流、文件、数据项和加工。（1）数据流条目 数据流条目给出某个数据流的定义，它通常是列出该数据流的各组成数据项。 如：课程=课程名+教员+教材+课程表课程表=星期几+第几节+教室（2）文件条目 文件条目给出某个文件的定义。订单文件=订单编号+顾客名称+产品名称+订货数量+交货日期（3）数据项条目 数据项条目给出某个数据单项的定义。学号编号=19999（4）加工条目 加工条目又称小说明。小说明中应精确地描述用户要求某个加工做什么。2 2、结构化设计、结构化设计 结构化设计方法，亦称SD（Structured Design）方法。是一种面向数据流的设计方法，目的在于确定

10、软件的结构。(1)SD方法的基本思想 其基本思想是：根据SA方法中的数据流图建立一个良好的模块结构图（例如SC图或软件层次方框图）；运用模块化的设计原理控制系统的复杂性，即设计出模块相对独立的，模块结构图深度、宽度都适当的，单入口单出口的，单一功能的模块结构的软件结构图或软件层次方框图。 此方法提供了描述软件系统的工具，提出了评价模块结构图质量的标准，即模块之间的联系越松散越好，而模块内各成分之间的联系越紧凑越好。(2)SD方法的设计原理1）模块化: 模块化就是把系统划分为若干个模块，从而获得满足问题需要的一个解的过程。2）模块的独立性: 模块独立性有两个定性的度量标准，即内聚和耦合。耦合有六

11、种，从小到大如下：两个模块完全独立（没有任何联系）；数据耦合:即两个模块只通过数据进行交换；状态耦合:即两个模块之间通过控制状态进行传递；环境耦合:即两个模块之间通过公共环境进行数据存取；公共块耦合:即多个模块引用一个全程数据区； 内容耦合:即一个模块使用保存在另一模块内部的数据或控制信息，或转移进入另一个模块中间时，或一个模块有多个入口时。 由此看出模块间耦合性越小越好。内聚有六种，从小到大如下：偶然内聚，即一个模块由多任务组成，这些任务之间关系松散或根本没联系；逻辑内聚:即一个模块完成的任务在逻辑上相同或相似；时间内聚:即一个模块所包含的任务必须在同一时间内执行；通信内聚:即一个模块内所有

12、处理元素集中于相同的数据结构；顺序内聚:即一个模块中所有处理元素都是为完成同一功能而且必须顺序执行；功能内聚:一个模块所有处理都完成一个而且仅完成一个功能。内聚性给出模块的内在联系，因此内聚性越大越好。3）模块的设计准则 通过模块的分解和合并，提高模块的独立性；模块调用个数最好不要超过五个；降低模块接口的复杂性；一个模块的所有下属模块应该包括该模块受某一判定影响的所有模块的集合；模块应设计成单入口和单出口；模块的大小要适中，一般在50句左右。(3)数据流图的类型 数据流图通常分为两大类型:转换处理型和事务处理型. 转换处理型: 由于大多数数据流图都可看成是对输入数据进行转换而得到输出数据的处理

13、，因此可把这类处理抽象为转换处理型。转换处理过程大致分为输入数据，变换数据和输出数据三步；它包含的数据流有输入流、转换流、输出流三个部分。在输入流中，信息由外部形式转换为内部形式的结果；在输出流中，信息由内部形式的结果转换为外部形式数据流出系统。转换处理型的数据流图。事务处理型:另一类数据流图可看成是对一个数据流经过某种加工后，按加工的结果选择一个输出数据流继续执行的处理。这种类型的处理可以抽象为事务处理型。在事务处理中，输入数据流称为事务流，加工称为事务中心，若干平行数据流称为事务路径。当事务流中的事务送到事务中心后，事务中心分析每一事务，根据事务处理的特点和性质选择一个事务路径继续进行处理

14、。(4)SD方法的设计过程 使用SD方法的基础是数据流图。正如前面所述，几乎所有软件在分析阶段都可以表示为数据流图，所以SD方法基本上可适用于任何软件的开发工作。 用SD方法进行总体设计的过程大致如下：（1）研究、分析和审查数据流图，从软件的需求说明书弄清楚数据流加工的过程；（2）根据数据流图确定数据流图的类型；（3）从数据流图导出系统的初始软件结构图；（4）改进初始软件结构图，直到符合要求为止；（5）复查。(5)软件结构的描述方式在SD方法中，软件结构用一种结构图来描述，它是设计说明书的一部分。结构图描述了软件模块结构，并反映了模块和模块间联系等特性。3、详细设计和编码(1)详细设计的任务为

15、软件结构图中的每一个模块确定采用的算法和块内数据结构，用某种选定的表达工具给出清晰的描述。(2)详细设计的描述工具程序流程图也称为程序框图，独立于任何一种程序设计语言，比较直观、清晰、易于掌握。任何复杂的程序流程图都可以由以下不同类型的基本结构组合或嵌套而成：顺序结构选择结构(IF-THEN-ELSE)多分支选择结构(CASE)先判定循环结构(WHILE)后判定循环结构(UNTIL)(2)方框图（N-S图）：图形描述工具。限制了随意的控制转移。顺序结构选择结构多分支选择结构先判定型循环结构后判定型循环结构(3)结构化编码方法结构化编码方法对源程序的编码要求:最基本要求是源程序的正确性，同时还要

16、考虑其可读性、可理解性、可测试性和可维护性。写程序的风格:一个好的源程序意味着源程序代码逻辑简明清晰，易读易懂。编码原则：程序内部文档应选取含义鲜明的名字，注解正确，程序清单层次清晰，布局合理。数据说明和次序应该标准化，个别复杂的数据结构应加注释。每个语句应该简单直接，不能为提高效率而使程序变得过份复杂。对输入数据应进行合法性检查；对输出数据要加输出数据的标志。在程序编码阶段以不影响程序的清晰度和可读性为前提，尽可能提高效率。1.2.2 面向对象开发方法面向对象开发方法面向对象技术是一种非常实用而强有力的软件开发方法。面向对象软件开发方法又称OOSD（Object-OrientedSoftwa

17、reDevelopment）。OOSD包括面向对象分析（OOA）、面向对象设计（OOD）和面向对象程序设计（OOP）三个方面。其中OOP是基础，OOA和OOD是应用OOP的机制。面向对象方法和技术是自80年代以来逐渐形成的一种分析问题和解决问题的新方法，其基本出发点就是尽可能按照人类认识世界的方法和思维方式来分析和解决问题。客观世界是由许多具体的事物或事件、抽象的概念和规则等组成的，因此，我们将要加以研究的事、物、概念都称为对象。面向对象的方法正是以对象作为最基本的元素，以对象作为分析问题，解决问题的核心。1、面向对象分析（OOA）把对象作为现实世界的抽象表示，然后定义对象的属性和专门操纵那些

18、属性的服务，属性和服务被看成对象的特征。具有相同的属性和服务抽象的一系列对象组成类。因此在面向对象模型中，它可以包含若干类，并且它对应于模型的不同层次，因此这些类有一定的层次关系和属性继承关系。面向对象分析由五个主要步骤构成：(1)标识对象(2)标识对象属性(3)定义对象的服务(4)识别对象所属的类(5)定义主题2、面向对象的设计（OOD）OOA是一个分类活动，而OOD模型由主体部件、用户界面部件、任务管理部件和数据管理部件四部分构成。每个部件又由主题词、对象及类、结构、属性和外部服务五层组成，它们分别对应OOA中的五个活动：定义主题词、标识对象、标识类、标识对象的属性和标识对象的服务。其中主

19、体部件是整个设计的主体，它包括完成目标软件系统主要功能的所有对象，用户界面部件给出人机交互需要的对象，任务管理部件提供协调和管理目标软件各个任务的对象，数据管理部件定义专用对象。要将目标软件系统中依赖于开发平台的数据存取操作与其他功能分开，以提高对象独立性。概括地说，OOD方法是以OOA模型为基础，不断填入和扩展有关软件设计的信息。3、面向对象编程完成OOD以后，将开始进入编程阶段。目前主要选取面向对象语言(如C+)、基于对象的语言(如Ada)、过程式语言(如C语言)。1.3 1.3 软件测试与质量保证软件测试与质量保证1.3.1 软件测试原则1、基本概念 软件测试定义:软件测试是为了发现错误

20、而执行程序的过程。 软件测试分为：单元测试和综合测试。 软件测试在软件生存周期中横跨了两个阶段：通常在编写出第一个模块之后就对它做必要的测试（称作单元测试）。编码与单元测试属于软件生存周期中的同一阶段。在结束这个阶段之后，对软件系统还要进行各种综合测试，这是软件生存周期的另一个独立的阶段，即测试阶段。2、目标和原则 软件测试的目标可以归纳为以下几点： 1.测试是为了发现软件中的错误而去运行软件的过程。 2.好的测试方案是尽可能地发现至今尚未发现的错误的测试方案。 3.成功的测试则是发现出至今未发现的错误的测试。1.3.2 软件测试策略与技术软件测试策略与技术1、软件测试策略、软件测试策略测试过

21、程是按单元测试、组装测试、确认测试和系统测试四个步骤进行的。1.1.单元测试（模块测试）单元测试（模块测试） 目的是发现模块的子程序或过程的实际功能与该模块的功能和接口描述是否相符，以及是否有编码错误存在。单元测试的主要内容有:模块接口测试；局部数据结构测试；重要路径测试；出错处理能力测试；边界条件测试.2.2.组装测试（集成测试或联合测试）组装测试（集成测试或联合测试） 它的测试目的是为了发现程序结构的错误。组装测试过程中的模块组织方式有非渐增式和渐增式两种。非渐增式组装测试：又称一次性组装方式或整体拼装。 测试方式是先对每个模块分别进行测试。然后再把所以模块组装在一起整体测试。其优点是对各

22、模块的测试可以并行进行，有利于充分利用人力，加快测试速度。其缺点是由于程序中不可避免的地存在涉及模块间接口、全局数据结构等方面的问题，所以一次试运行成功的可能性不大，结果是发现有错误，但却找不到错误的产生原因。渐增式组装测试 这种方式是对一个个模块进行模块调试，然后将这些模块逐步组装成较大的系统。在组装过程中，每连接一个模块便进行一次测试，直到把所有模块集成为一个整体并进行测试，则软件的组装测试完成。在渐增测试过程中，将模块结合起来的策略有两种：自底向上测试和自顶向下测试。自底向上测试：从程序模块结构的最低层模块进行组装和测试。因为模块是自底向上进行组装的，对给定层次的模块的下层模块处理功能总

23、可以得到，所以这种测试策略不必设计桩模块（存根模块），但要设计驱动模块。自顶向下测试：将模块按系统程序结构，沿控制层次自顶向下进行组装。由主控模块开始，按照程序的层次结构向下移动。逐渐把各个模块组装起来。(3)确认测试(有效性测试)又称有效性测试。组装测试结束后，得到的是一个完整的软件系统。这时需要进行最后的测试，即有效性测试。有效性测试阶段主要进行的测试有：有效性测试（黑盒测试）、软件配置复查、测试和测试以及验收测试。(4)系统测试系统测试是指将经过测试后的软件系统与计算机硬件、外设、其他支持软件以及其他系统元素一起进行测试。测试内容主要有：功能测试、吞吐量测试、可用性测试、保密性测试、安装

24、测试、可恢复性测试、资料测试和程序测试。2、常用的测试方法常用的测试方法有黑盒测试和白盒测试两种。(1)白盒测试白盒测试又称结构测试或逻辑驱动测试。所谓“白盒”是指将对象看作一个打开的盒子，测试人员可利用程序内部的逻辑结构及有关的信息来设计或选择测试用例。白盒测试主要考虑的是测试用例对程序内部逻辑的覆盖程度，而不考虑程序的功能。测试用例对程序的覆盖程序从低到高分别为：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖。需要说明的是，上述各种覆盖准则的侧重点不同，覆盖程度也不同。但它们共同的是：任何一种覆盖都不能做到完全测试。(2)黑盒测试 黑盒测试又称功能测试或数据驱动测试。 在这种测

25、试方法中，程序对测试者是完全透明的。测试者不考虑程序的内部结构和特性，就好像把程序看作一个不能打开的盒子，只根据程序的需求规格说明中的程序功能或程序的外部特性来设计测试用例。 黑盒测试的方法包括：等价分类法、边缘值分析法、因果图法和错误推测法。 测试方法还有回归测试、强度测试等等。每一种测试方法都各有所长，在实际测试中应综合使用。一般来讲，通常用黑盒法设计基本的测试方案，再利用白盒法做必要的补充。1.3.3 软件质量保证软件质量保证1、评审与测试评审和测试都是质量保证的重要活动。验证：我们制造产品的步骤正确吗？确认：我们制造的是正确的产品吗？2、程序正确性证明程序正确性证明就是要通过数学的方法

26、，证明程序具有某些需要的性质。通过多年的研究，现已提出了一些有用的方法和技术，其中包括输入输出断言法、最弱前置条件法、结构归纳法纪等几种常用的方法。如果说程序测试是为了证明程序有错，则程序正确性的证明正好相反，是为了证明程序能够完成某些预定的功能。现有的证明程序正确性的技术与工具包括已研制出来的程序正确性自动证明器，仅适用于很小的程序。要解决大程序的正确性证明，还需要进行大量的工作。1.4 软件重用软件重用重用（Reuse）是软件过程的一部分。为了快速做出复杂的应用，重用是一条捷径。此外，重用也是当今软件系统的重要特征。重用指在一个软件项目中直接使用以前项目中的产物，而非重用某些工具，也就是把

27、以前做过的东西纳入到新项目中。1重用过程 面向对象的语言本身就提供了重用机制，如封装、继承、模板等。技术上可以制成可重用构件（不仅封装数据还封装行为，成为独立的可重用对象），这样可以大幅度提高开发效率。重用的真正价值在于方案、决策的重用。利用集成技术将构件按可重用模式装入可重用框架（相当于建筑中的梁、柱组成的房梁）构成一组装式软件过程。从代码重用到构件重用到设计重用到过程重用（域工程）、从初创到成长到成就到实用。现代的软件平台，或多或少都提供了重用机制。2支持重用的环境从过程重用的观点，以下10种软件过程产物均可以重用：项目计划 费用估算 体系结构 需求模型和规格说明 设计 源代码 各种文档

28、人机界面 测试用例 数据 这些产物作为重用件要作分类、标记，作为对象构件放入构件库。在当今CIS分布系统上，构件库是一个数据库服务器，它提供访问服务。重用环境还必须提供集成工具，使重用的构件能集成到新项目中。3构件与构件重用构件：是可重用的、具有独立性的软件单元，是用来构造其他软件的部件。构件具有以下特点：(1)构件是具有独立性的、被封装好的、具有描述能力的软件单元。(2)构件本身不是一个完整的应用程序。(3)构件都有被定义好的接口，只巴能通过这些接口来操纵构件。(4)构件之间可以交互。(5)构件可以被扩展。构件的可继承性使构件能够被扩充和修改。目前有两个方面的技术，一种是可视化构件，另一种是

29、分布式对象构件。1.5 软件开发环境软件开发环境软件开发由来已久。一台宿主机，一个编译（或汇编）程序，加上编辑、链接、装入等少量实用程序，就构成了早期软件开发的舞台。从这个意义上讲，在软件工程兴起之前就有了软件开发环境。在70年代和80年代初期，开发环境常被称为“软件工程环境”（简称SEE或SE2）或“程序设计支撑环境”。“计算机辅助软件工程”（简称CASE），是今天对开发环境最流行的称呼。成为描述软件开发环境与工具的最通用的名称。另一个常见的名称“工作台”（workshop）。1976年，ICSE第二届会议在一篇文章中发表了一个基于UNIX操作系统的程序设计支撑环境，称之为“UNIX程序员工

30、作台”（UNIXprogrammersworkbench，简写为UNIX/PWB）。这是国际上出现的第一个有影响的软件开发环境。自此之后，工作台也常被用作开发环境的同义词。2集成化工具开发软件用到两类工具。一类工具是画或写在纸上的，包括在不同阶段使用的各种图形与语言；另一类则是用来“开发软件的软件”，又称为“软件工具”或CASE工具。这里讨论的是后一类工具。早期的环境只配置用于编码阶段的工具，也称为“低层”CASE工具。今天在软件分析和总体设计等阶段也有了许多支持开发的工具，即“高层”CASE工具。70年代出现了“工具箱”能部分地实现从一个工具到另一个工具的切换。今天，高、低层CASE工具由一

31、组专用程序和一个用来支持工具间数据交换的环境信息库构成的支持下，共同构成了具有统一的用户界面、并能自动实现工具切换的“集成工具”，对软件开发的自动化提供了有力的支持。CASE环境还可能包括另两个层次。一个是环境体系结构，用于区分开发环境为单机环境或网络环境；另一个是可移植性服务程序，它介于集成工具与宿主机之间，使集成后的CASE工具不需要作重大的修改即可与环境的软、硬件平台适应。小 结软件工程是从工程角度来研究软件开发的方法和技术，它是在克服软件危机的过程中产生而发展起来的。软件工程学是自软件工程出现以后形成的一门新兴学科。它包括的主要内容有：软件工程方法学、软件工程环境和软件工程管理等多个分

32、支。一个软件从用户提出开发要求，到废弃不用为止的全过程，称为软件的生存周期。软件的生存周期划分为若干个阶段（如：需求定义、软件设计、编程、测试、运行维护等），每个阶段有相对独立的任务。需求分析最常用的方法是结构化分析方法（SA方法），SA方法适于分析大型数据处理系统，使用的主要工具有数据流图和数据词典。数据流图以图形形式表示软件信息流向和信息加工，而数据词典对这些信息和加工进行更详细的描述。SA方法简单实用、易于理解、使用广泛。软件设计可分为总体设计和详细设计。总体设计通常使用结构化设计方法。详细设计是根据结构化程序设计原则进行的，只使用顺序、分支、重复三种结构来设计模块的控制流程，使用的表示

33、工具有程序流程图、方框图、PAD图、伪码（PDL语言）等。软件编程的任务是将软件详细设计的结果转换成某种程序设计语言编写的源程序。面向对象的方法是在结构化程序设计的基础上，进一步力图用更自然的方法反映客观世界。在面向对象的系统中，将数据和使用该数据的一组基本操作或过程封装在一起，用“对象”这个概念来完整地反映客观事物的静态属性和动态属性。“面向对象”的基本思想就是把要构造的系统表示为对象的集合。软件测试是为了发现错误而执行程序的过程。软件测试的目的是要暴露软件系统中的隐含错误，然后通过软件测试找出错误的原因和位置并加以改正。在软件开发中，测试是保证软件正确性的最后一个阶段，测试需要制定测试计划

34、，设计测试用例，然后实施测试，测试后进行分析评价，测试结束后，要给出测试报告。软件测试方式分为：人工测试、动态测试和自动测试三种。测试过程按单元测试、组装测试、确认测试和系统测试四个步骤。常用的测试方法有黑盒测试和白盒测试两种。对于不同的测试方法，需要设计不同的测试用例。阶段评审与测试，软件配置管理是保证软件质量的重要环节，软件质量保证计划是确保上述环节实施的关键。软件重用和CASE集成环境是当今软件工程技术重要的两个方面，重用技术已从代码重用发展到域工程，是大规模生产软件的希望。集成技术在对象包装下，当今分布式应用系统上已可实现数据集成、控制集成、表示集成。第二章第二章 数据结构概述数据结构

35、概述随着计算机应用领域的不断扩大，非数值数据的处理变得尤为重要，这些数据的元素之间在多是相互有关的。因此，讨论数据元素之间的逻辑关系、数据元素在计算机中的存储方式及在数据元素集合上设立的运算如何实现，这是研究数据处理的基础。本章在介绍数据结构的有关概念后，着重讨论线性结构、树型结构和图形结构等三类数据结构，最后介绍数据结构中两种特别重要的运算-查找和排序。对数据结构的基本操作，本章采用C语言描述。2.12.1概述概述2.22.2线性表线性表2.32.3树型结构树型结构2.42.4图图2.52.5查找查找2.62.6排序排序小结小结2.1 概述概述l计算机早期运算:原始数据和结果数据不多,重点在

36、于算法。l计算机应用的发展:逐渐变成对数据进行非数值型的加工处理为主。l特点是数据量大，而计算的工作量可能很小。l数据结构的提出：数据结构是为研究和解决诸如数据的分类与查找、情报检索、数据库、企业管理、系统工程、图形识别、人工智能以及日常生活等各领域的非数值问题而提出的理论与方法，即如何合理的组织数据，以提高算法的效率。l 重要性：对实现系统软件，如操作系统、编译程序和数据库管理系统等均有十分重要的意义。2.1.1 2.1.1 数据结构的概念数据结构的概念l数据：描述客观事物的的信息（数，字符，符号等）的集合，是程序处理的对象。l数据元素：是数据集合中的个体，是构成数据对象的基本单位，可由若干

37、个数据项组成。l数据项：是数据的最小单位。l 一组数据元素具有某种结构形式。l 数据结构：就是描述一组数据元素及元素间的相互关系的。l 数据结构描述了一组性质相同的数据元素及元素间的相互关系。 用集合论给出的数据结构的定义为: 数据结构S是一个二元组：S=(D,R)。 其中:D是一个数据元素的非空的有限集合。 R是定义在D上的关系的非空的有限集合数据结构概念一般包括三个方面的内容：数据元素之间的逻辑关系、数据元素在计算机中的存储方式以及在这些数据元素上定义的运算的集合。2.1.2 2.1.2 数据的逻辑结构数据的逻辑结构 数据的逻辑结构有时可直接称为数据结构。 数据的逻辑结构的三种基本类型：线

38、性表、树和图。分别属于两大类：(一)线性结构（线性表）线性结构（线性表） 各数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。 线性表是典型的线性结构，它的数据元素只按先后次序联接。有栈、队列、字串、数组和文件。(二）非线性结构（树，图）非线性结构（树，图） 不满足线性结构特点的数据结构称为非线性结构。 树、图等是非线性结构。 树中的数据元素是分层次的纵向联接。 图中的数据元素则有各种各样复杂联接。 其它种类的数据结构由这三种基本结构派生的。2.1.3 数据的物理结构数据的物理结构 数据的逻辑结构在计算机存储设备中的映象称为数据的存储结构(亦称为物理结构)。同一个逻辑结构可以有不同的存储

39、结构。 最常用的二种方式是： 顺序存储结构和链接存储结构顺序存储结构和链接存储结构。 大多数据结构的存储表示都采用其中的一种方式或两种方式的结合。1.1.顺序存储结构顺序存储结构数据结构的数据元素按某种顺序存放在存储器的连续单元中。即将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，而数据元素之间的关系由存储单元的邻接关系唯一确定。若数据元素存放在以起始地址S开始的连续存储单元中。则第i个元素的存储地址：LOC(i)=LOC(1)+(i-1)*l=S+(i-1)*l假定每个元素所占的存储空间是相同的,长度均为l。数据的这种顺序存储结构叫做向量，以V表示，向量V的分量Vi是数据结构的第i个元素

40、在存储器中的映像。顺序存储的主要特点是： 1.结点中只有自身信息域，没有连接信息域。因此存储密度大，存储空间利用率高； 2.可以通过计算直接确定数据结构中第i个结点的存储地址L。即可以对记录直接进行存取； 3.插入、删除运算会引起大量结点的移动； 4.要求存储在一片连续的地址中。 这种存储方式主要用于线性的数据结构。2.2.链接存储结构链接存储结构 存储数据结构的存储空间可以不连续，而数据元素之间的关系是由指针来确定的。主要特点是：（1）结点由两类域组成：数据域和指针域。（2）逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。（3）插入，删除操作灵活方便，不必移

41、动结点，只要改变结点中的指针值即可。2.1.4 2.1.4 数据结构的运算数据结构的运算 对一些典型数据结构中的结点进行操作处理。1.插入:在数据结构中的指定位置上插入新的数据元素；2.删除:根据一定的条件,将某个结点从数据结构中删除；3.更新:更新数据结构中某个指定结点的值；4.检索:在给定的数据结构中,找出满足一定条件的结点来，条件可以是某个或几个数据项的值；5.排序:根据某一给定的条件，将数据结构中所有的结点重新排列顺序等。从操作的特性来看，所有这些运算的操作可以分为二类: 一类是加工型操作：操作改变了存储结构的值（如插入、删除、更新等）； 另一类是引用操作：操作只是查询或求得结点的值（

42、如检索等）。2.2 2.2 线性表线性表最简单，最常用的一种数据结构2.2.1 2.2.1 线性表线性表 线性是指表中的每个元素呈线性关系，即除第一个外，都有一个直接前趋(predecessor)，同时除最后一个元素外，都仅有一个直接后继(successor)。1.1.线性表的逻辑结构线性表的逻辑结构 线性表L用符号表示为：L=(a1，a2，a3，. ai.，an) 线性表也可以正式定义为： 若数据结构 L=（D，R）是一个线性表，则：D是包括a1,a2,a3 .an 等元素的集合。R中只包含一个关系，即R= | ai-1，aiD， 2in 。 关系 给出了元素的一种先后次序。a1 称为表的线

43、性起始结点，an 为表的终结点。2.2.线性表的存储结构线性表的存储结构l存储结构:顺序存储结构和链接存储结构。l具有顺序存储结构的线性表称为顺序表，即用一组地址连续的存储单元依次存储线性表中的每个数据元素。l具有链接存储结构的线性表称为线性链表。 链式存储结构是用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。 常用的链表有单链表、循环链表和双向链表。3.3.线性表的基本运算线性表的基本运算l常用的操作有:插入、删除、修改、读值、检索和排序等。l线性表还可以进行一些更为复杂的操作。如将两个或两个以上的具有相同数据对象的线性表合并成一个线

44、性表，将一个线性表拆成若干个线性表，复制一个线性表等等。这些较为复杂的操作都可以利用上述几种常用的操作来实现。( (1)1)顺序表的操作顺序表的操作 顺序表在各种高级语言里经常用一维数组实现。#define MAXSIZE 100 /数组中元素个数的最大值int listMAXSIZE,n; /n为线性表中当前的结点数 插入运算 插入运算是在线性表的第i个元素和第 i+1个元素之间插入一个一个新元素x。 为了实现这个操作，必须把第i+1个元素到第n个元素依次向后移位一个位置，以便把第i+1个存储位置让出来，存储新元素X。 假定已有一个数组,其值是由小到大排列的,现插入一个新的结点p0,要求插入

45、后仍能保持由小到大的顺序。 # #define N 20define N 20intint aN aN；main()main() int int i, data, n=10;i, data, n=10; for(i=0; in-1; i+) for(i=0; in-1; i+) scanf scanf(“%d”, &ai);(“%d”, &ai); scanf scanf(“%d”,&data);(“%d”,&data); insert(a,n,data); insert(a,n,data); for(i=0; in; i+) for(i=0; in; i+) printf printf(“%

46、3d”,ai);(“%3d”,ai); insert(insert(intint a, a, int int n, n, intint data) data) int int i; i; if (an-1data) an=data; if (an-10; i-) for(i=n-1; i0; i-) if (ai-1data) ai=ai-1; if (ai-1data) ai=ai-1; else ai=data; break; else ai=data; break; if(i=0) a0=data; if(i=0) a0=data; 当i=0时,新结点x插在a1之前,这时需移动线性表中的

47、所有元素。 当i=n-1时,新结点x插入在an-1之后,这时不需移动线性表中的元素。在具有n个结点的线性表中，插入一个新结点时，其执行时间主要化费在移动结点的循环上。移动结点的平均次数为：删除运算 线性表的删除运算是指将线性表中第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元素.函数如下：intint delete( dele

48、te(intint a, a,intint n, n,intint data) data) intint i,j,k=0; i,j,k=0; for(i=0;in;i+) for(i=0;in;i+) if(ai=data) if(ai=data) for(j=i;jn-1;j+) aj=aj+1; for(j=i;jnext=NULL; if (h=NULL) h=p0;p0-next=NULL; else else while(p0-datap1-data)&(p1-next!=NULL) while(p0-datap1-data)&(p1-next!=NULL) p2=p1; p1=p1

49、-next; p2=p1; p1=p1-next; if (p0-data data) if (p0-data data) if(h=p1) h=p0; else p2-next=p0; if(h=p1) h=p0; else p2-next=p0; p0-next=p1; p0-next=p1; else else p1-next=p0;p0-next=NULL; p1-next=p0;p0-next=NULL; return (h); return (h); 单链表的删除在已给定的链表h中,删除data值为m的结点。 1.链表h是否指向空表,如果是空表,则报告空表信息。2.若h不为空: 一

50、直查到表尾还找不到该结点,则在此链表中无此结点。 查找到该结点: 若该结点在头部,则h指向该结点的下一个结点。 若该结点在中部,则前趋结点的指针指向后趋结点。 若该结点在尾部,则前趋结点的指针为NULL。p2p1 structstruct node *del( node *del(structstruct node *h, node *h,intint m) m) struct struct node *p1,*p2; node *p1,*p2; if(h=NULL) if(h=NULL) printf printf(n This null!n); return(h); (n This nul

51、l!n); return(h); p1=h; p1=h; while (p1-data!=m)&(p1-next!=NULL) while (p1-data!=m)&(p1-next!=NULL) p2=p1;p1=p1-next; p2=p1;p1=p1-next; if(p1-data=m) if(p1-data=m) if(p1=h) h=p1-next; if(p1=h) h=p1-next; else p2-next=p1-next; else p2-next=p1-next; free(p1); free(p1); else else printf printf(%d nod(%d

52、 nod beed beed found! n,m); found! n,m); return(h); return(h); 实例：单链表的建立、打印和插入：实例：单链表的建立、打印和插入：#define NULL 0#define LEN sizeof(struct node)#include stdio.hstruct node int data; struct node *next; ;struct node * create() /* 建立链表 */ struct node *h=NULL,*p,*q; int x; for(;) printf(Input data:); scanf(

53、%d,&x); if(xdata=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(%dn,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(

54、p0-datap1-data)&(p1-next!=NULL) p2=p1; p1=p1-next; if(p0-datadata) 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; h=insert(h,p); print(h); 二.循环链表（1）循环链表的

55、最后一个结点的指针域不为NULL，而是指向头结点，整个链表形成一个环。（2）在循环链表中设置一个表头结点，使空表与非空表的运算统一起来。(a) 非空表 (b) 空表图 2-2-5 带表头结点的循环链表（1）插入算法：在头指针为h的循环链表中元素b的结点前插入新元素a. structstruct node * node *inscstinscst( (structstruct node *h, node *h, intint b, b, intint a) a) structstruct node *q, *p; node *q, *p; q=( q=(structstruct node *)

56、node *)mallocmalloc(LEN);(LEN); q-data=a; q-data=a; p=h; p=h; while (p-next !=h )&(p-next)-data !=b) while (p-next !=h )&(p-next)-data !=b) p=p-next; /* p=p-next; /*寻找寻找指定元素的前一结点指定元素的前一结点*/*/ q-next=p-next; p-next=q ;q-next=p-next; p-next=q ; return (h); return (h); hpqba(2)删除算法：在头指针为h的循环链表中删除元素为b的结

57、点delcstdelcst( (structstruct node *h, node *h, intint b) b) structstruct node *p,*q; node *p,*q; p=h; p=h; while (p-next !=h )&(p-next)-data !=b) while (p-next !=h )&(p-next)-data !=b) p=p-next; /* p=p-next; /*寻找寻找指定元素的前一结点指定元素的前一结点*/*/ if (p-next =h)if (p-next =h) printf printf(“ No this node in th

58、e listn”); (“ No this node in the listn”); return(h); return(h); q=p-next ; p -next=q-next; q=p-next ; p -next=q-next; free(q); free(q); return(h); return(h); bpq三.多项式相加A(x)=3x14+2x8+1B(x)=8x14-3x10+10x6C(x)=A(x)+B(x)设pa,pb指针（1）若指针相等，则系数相加，c(x)中建项（系数为0，不建）（2）若pa-exppb-exp复抄pa所指项，反之，复抄pb所指项。-13 14281

59、0ah-18 14-31010 6bhcofexpch-11411-3102 810 61 0papbpcstructstruct node1 * node1 *addpolyaddpoly( (structstruct node1 *ah, node1 *ah, struct struct node1 * node1 *bhbh) ) struct struct node1 *pa,* node1 *pa,*pbpb,*pc,*,*pc,*chch,*pp;,*pp; intint x,e; x,e; chch=(=(structstruct node1 *) node1 *)mallocm

60、alloc(LEN);(LEN); chch-exp=-1; -exp=-1; chch-next=-next=chch; pc=; pc=chch; /*; /*建立新表头结点建立新表头结点*/*/ pa=ah-next; pa=ah-next; pbpb= =bhbh-next; -next; while(pa-exp!=-1)|( while(pa-exp!=-1)|(pbpb-exp!=-1)-exp!=-1) if( pa-exp= if( pa-exp=pbpb-exp)-exp) x=pa- x=pa-cofcof+ +pbpb-cofcof; e=pa-exp; /*; e=p

61、a-exp; /*系数相加系数相加*/*/ pa=pa-next; pa=pa-next; pbpb= =pbpb-next-next； /* /*修改指针修改指针*/*/ else if (pa-exppb-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

62、; 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) s

63、truct node *p1 p1=h-next; while(p0-datap1-data)&(p1!=h) p1=p1-next; p0-prio=p1-prio; p1-prio-next=p0; p0-next=p1; p1-prio=p0; return(h);p0p1hb.删除操作在已给定的头结点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) p

64、1-prio-next=p1-next; p1-next-prio=p1-prio; free(p1); else printf(“%d not been found!n”,m); return(h);hmp12.2.2 2.2.2 栈栈栈是限定在一端进行插入与删除的线性表。允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。例如，给定栈(a0,a1,an-1）称a0为栈底元素，an-1为栈顶元素。 栈是一种后进先出(LIFO-Last In First Out)或先进后出（FILO)的线性表。 在栈中，元素的插入称为进栈，元素的删除称为出栈。1.顺序存储的栈顺序栈：利用一组地址

65、连续的存储单元依次存放自栈底到栈顶的数据元素,同时设指针top指示栈顶元素的当前位置。 假设用一维数组smax表示栈，指针top指向栈顶元素.s0为最早进入栈的元素，stop为最迟进入栈的元素。当top=max-1时，为满栈.初始化 top=-1 注：top,max 为全局变量（1）进栈 push(push(intint s, s,intint x) x) if(top=max-1) if(top=max-1) printfprintf(“Stack overflow!n”); /*(“Stack overflow!n”); /*上溢上溢*/*/ else s+top=x;else s+top

66、=x; （2）出栈 intint pop( pop(intint s) s) intint y=-1; y=-1; if(top=-1) if(top=-1) printfprintf(“Stack underflow!n”); /* (“Stack underflow!n”); /* 下溢下溢*/*/ else y=stop-;else y=stop-; return(y); return(y); 图图 2-2-8 2-2-8 数据元素和栈顶指针之间的对应关系数据元素和栈顶指针之间的对应关系 假设有两个栈，我们让它们共享一数组sm，因为栈底位置是不变动的，所以可将两个栈底分别设在数组空间的两

67、端，然后各自向中间伸展(如下图所示)，显然，仅当两个栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺，使得每个栈实际可利用的最大空间大于m/2。2.链存储的栈 当栈的最大容量事先不能估计时，也可采用链式存储结构的栈，称为链栈。一个链栈由它的栈顶指针top唯一确定。如图2.11所示。 这里栈空的判别条件是top是否为NULL，而栈满将不会发生,除非计算机的全部可利用空间都被占满。对一个元素多变的栈来说，链式存储结构似乎更适宜。栈链的运算实现也比较简单。3.栈的应用(1)(1)子程序的调用和返回子程序的调用和返回 当多个过程构成嵌套调用时，按照后调用先返回的原则，通过栈来实现。(2)表达式

68、求值 栈的另一个重要的应用是在编译中用来求表达式的值。 任何一个表达式由三部分组成：操作数、运算符和界限符。其中，操作数可以是常量或标识符（表示常量或变量）；运算符有算术运算符、关系运算符、逻辑运算符等，在这里，我们只讨论算术运算符。算术运算符的规则：界限运算符有左，右括号(左括号运算级最高，右括号运算级最低)及表达式结束符#(#号的运算级最低)。要正确解释表达式，必须先了解算术四则运算的规则。即：先乘除,后加减； 从左计算到右； 先括号内,后括号外为 实现算符优先法必须使用两个工作栈. 一个数栈（opnd），一个运算符栈(optr)，系统自左至右扫描表达式，遇到操作数，则送入数栈，遇到运算符

69、，则把它的优先度与当前运算符栈顶运算符的优先度比较，若大于栈顶优先符的优先度，则入栈，否则退栈，并以这个退栈运算符和从数栈顶上退出的两个操作数形成一条机器指令。这样，一边形成相应的机器指令，直到扫描到结束符，所有的栈空为止计算表达式运算符:* / * + - X=A*(B+C/D)-E*F*G 优先数:43322ABCDOptrOpnd(a)进栈后*（+/ABT1*(+(b)T1=C/DAT2*(c)T2=B+T1AT2*(d)弹出左括号T3(e)T3=A*T2T3EFG_*(f)进栈后T3ET4_*(g)T4=F*GT3T5_(h)T5=E*T4T6(i)T6=T3_T5求表达式 3*（7-

70、2）的值。 optr opnd optr opnd 输入字符输入字符 主要操作主要操作1 # 3*1 # 3*（7-27-2）# # push(push(opndopnd,3),3)2 # 3 *2 # 3 *（7-27-2）# push(# push(optroptr,*),*)3 #* 3 3 #* 3 （7-27-2）# push(# push(optroptr,(),()4 #*( 3 7-24 #*( 3 7-2）# push(# push(opndopnd,7),7)5 #*( 3 7 -25 #*( 3 7 -2）# push(# push(optroptr,-),-)6 #*(

71、- 3 7 26 #*(- 3 7 2）# push(# push(opndopnd,2),2)7 7 #*(- #*(- 3 3 7 7 2 2 ）# # operate(7,-operate(7,-,2),2)8 #*( 3 5 )# pop(8 #*( 3 5 )# pop(optroptr) ) & & 一对（）出栈一对（）出栈 9 9 #* #* 3 3 5 5 # # operate(3,*,5)operate(3,*,5)10 # 15 # return10 # 15 # return2.2.3队列 队列（Queue）也是操作受限的线性表. 队列是一种先进先出(FIFO)的线性表

72、.(a1,a2,an) 允许在表的一端进行插入，而在表的另一端进行删除，允许插入的一端叫做队尾（rear），允许删除的一端则称队头（front）。 若限制插入和删除能在表的两端进行，称此队列为“双向队”。 若限制插入在表的一端进行，而限制删除在表的另一端进行, 称此队列为“单向队”。允许插入的一端称为队尾，允许删除的一端称为队首。队列是一种先进先出（FIFO)的线性表。队列的基本运算有以下四种:获得队列的队首结点之值： gethead(q,x)； 读取q队列的队头元素于变量x中,队列不变。队列q中插入一个结点：(进队) add(q,x)； 在队尾插入一个元素x。队列q中删除一个结点：（出队）

73、del(q)； 删除队头元素。判队列q是否为空： empty(q)；1.顺序存储的队设置二个指针 front(队头)和rear(队尾).存在“假溢出”现象，解决方法：采用循环队列（反转技术）假设存储空间为数组qmqm，把队列数组的元素q0和qm-1连接起来，形成一个环形的表。初始值front=rear=0front=rear=0（1）进队 rear=(rear+1)% m;rear=(rear+1)% m; qrear=x; qrear=x;出队 front=(front+1) % m;front=(front+1) % m; y=qfront; y=qfront;01m-1frontrear

74、a1a2a3a4(2)环形队列的队空和队满都有rear = = front 专门设立一个标志符 少用一个元素空间，用( (rear+1)/m = frontrear+1)/m = front作为队满的判别条件循环队列中入队和出队操作的具体算法intint front,rear,m; /* front,rear,m; /*全局变量*/addqueaddque( (intint q, q,intint x) /* x) /*进队算法进队算法*/*/ rear=(rear+1) % m;rear=(rear+1) % m; if(rear = front) if(rear = front) prin

75、tfprintf(Queen overflow!n);(Queen overflow!n); else qrear=x; else qrear=x; delquedelque( (intint q) /* q) /*出队算法出队算法*/*/ intint y=-1; y=-1; if(front = rear) if(front = rear) printfprintf(Queen (Queen undelflowundelflow!n);!n); else front=(front+1) % m; else front=(front+1) % m; y=qfront; y=qfront; r

76、eturn (y); return (y); 2链接存储的队 采用链式存储结构的队列称为链队列。 一个链队列需要队头和队尾的两个指针才能唯一确定。b. 链式存储的队列链式存储的队列 (1)进队算法进队算法 注：注：front ,rear 是全局变量是全局变量 add (add (intint x) x) structstruct node *q; node *q; q=( q=(structstruct node *) node *)mallocmalloc(LEN);(LEN); q-data=x; q-next=NULL; q-data=x; q-next=NULL; if (front=

77、NULL) if (front=NULL) front =q; rear=q; front =q; rear=q; else rear-next=q; rear=q; else rear-next=q; rear=q; (2)出队算法注：front ,rearfront ,rear是全局变量del( )del( ) structstruct node *q; node *q; intint y=-1; y=-1; if(front=NULL) if(front=NULL)printfprintf(“Queen(“Queen nderflownderflow!n”);!n”); else q=f

78、ront; else q=front; y=q-data; y=q-data; front=q-next; front=q-next; free(q); free(q); return (y); return (y); 3队列的应用 分时操作系统中，多个用户程序排成队列，分时地循环使用CPU和主存。 缓冲技术系统为了解决高速的主机和低速的输入输出设备之间的矛盾，在主存中开辟缓冲区，主机将要输入或输出的信息先送至缓冲区，然后输入或输出设备从缓冲区中按队列的先进先出原则依次取出数据，在这种情况下，主机不必等待外部设备操作完就可以继续做其它的工作。 通常，缓冲区的结构为一个循环队列。2.2.4 2.

79、2.4 串串 串(String)也是一种特殊的线性表，即当线性表中的元素为字符时的情形。 串定义：由零个或多个字符组成的有限序列，称为串。一般记为： s=a1a2an (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的

80、值的末尾，联接成一个新串的函数concat(s1,s2)等。1.串的顺序存储 用一组地址连续的存储单元来存放字符串的值。 为了唯一确定串，需要设置两个变量，一个是指向串第一个字符位置的指针sp，一个是指示串长度的整型变量sl。可以将串的长度和串值一起存于内存，也可以用一个特定字符作为串结束标志和串值一起存放，这样就不需要设置sl了。C语言就是用NULL(0)作为串结束标志的。不同的字符所占据的内存空间都是一个字节computer0 l l+1 l+2 l+8图 2-2-14 顺序存储r的串2.串的链式存储 链表存储串值时,由于串中每个数据元素是一个字符，因而存在一个结点大小的选择问题，即结点中

81、是存放一个字符，还是存放多个字符. 结点大小的选择直接影响对串和处理效率。结点越小，串处理越方便，但所占内存也随之扩大。反之，结点越大，串处理越不方便，但可以节省内存。串的基本运算串的基本运算一一. 求串的长度求串的长度main() long le; long len(char ); char s30; scanf(%s,s); le=len(s); printf(len(s)=%dn,le); long len(char s) long i=0; while(si!=0) i+; return i; 二.求子串sub(s,m,n)求串s的第m位置开始且长度为n的子串。三. 求子串t在主串s中

82、的位置 index(s,t) 从主串S的第一个字符起和模式t的另一个字符比较，若相等，则继续逐个比较后继字符，如果全部相等，则匹配成功，返回子串的位置。否则从S的第二个字符起重新开始新的比较，直至某一步匹配成功或S结束，无法再进行比较为止，此时返回-1作为匹配失败的标志。 index(char s,char t)index(char s,char t) int int i=0,j=0; i=0,j=0; while (si!=0&tj!=0) while (si!=0&tj!=0) if(si=tj) i=i+1; j=j+1; if(si=tj) i=i+1; j=j+1; else i=i

83、-j+1; j=0; else i=i-j+1; j=0; if(tj=0) return(i-j); if(tj=0) return(i-j); else return(-1); else return(-1); 四.字符串置换 rep(s,t,v)rep(s,t,v)以串以串v v的值替换所有在串的值替换所有在串s s中出现的子串中出现的子串t t的值。的值。五.字符串连接 char *char *concatconcat (char * s1, char *s2) (char * s1, char *s2) char *p; char *p; p=s1; p=s1; while(*p+)

84、; while(*p+); -p; -p; while(*p+=*s2+); while(*p+=*s2+); return(s1); return(s1); 六. 字符串比较 int cmpint cmp(char s1,char s2)(char s1,char s2) intint i=0,r; i=0,r; while(s1i= =s2i&s1i!=0)i+; while(s1i= =s2i&s1i!=0)i+; if(s1i=0&s2i=0) r=0; if(s1i=0&s2i=0) r=0; else r=s1i-s2i; else r=s1i-s2i; return (r); r

85、eturn (r); 以下是C语言提供的一些有关字符串的库函数：unsigned unsigned strlenstrlen(char *(char *strstr) ) /* /*字符串长度函数字符串长度函数*/*/char *char *strcatstrcat(char *str1,char *str2) /*(char *str1,char *str2) /*连接函数连接函数*/*/char *char *strcpystrcpy(char *str1,char *str2) /*(char *str1,char *str2) /*拷贝函数拷贝函数*/*/2.32.3树形结构 树形结构

86、是结点之间有分支、层次关系的结构，是一种重要的非线性结构。树型结构在客观世界中广泛存在，如人类的族谱和各种社会组织机构都可以用“树”来表示。2.3.1树的定义及其基本概念树可以定义如下树可以定义如下:1)有且仅有一个称为根的结点；2)除根结点之外的结点可分为m(m=0)个互不相交的有限集T1,T2,.Tm，其中每一个集合本身又是一棵树，并且称为根的子树。这是一个递归的定义，即在树的定义中又用到树本身这个术语。树的基本概念树的基本概念树的根结点:是树中一个特定的结点，它是没有前趋的结点。结点的度:树中每个结点拥有的子树的数目。度为0的结点为终端结点或叶子。度不为0的结点称为非终端结点或分支结点。

87、树中各结点度的最大值称为树的度。子女与双亲:兄弟:同一双亲的各子女间互称为兄弟。树的高度(或深度):树中结点的最大层次。有序树和无序树:m(m0)棵互不相交的树的集合，称为森林。树结构有广泛的应用，经常被用来定义层次关系。用树表示算术表示式(A+B)*5/(2*(C_D)/*-*+5ABCD2用树表示家庭结构老张张一张二张小一张小二张小三2.3.3 2.3.3 二叉树二叉树1.二叉树的概念： 二叉树定义为：或为空，或由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。二叉树不是树的特殊情况。 它们之间最重要的区别是：二叉树的结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，

88、也要明确指出该子树是左子树还是右子树。二叉树允许空.而一般的树至少有一个结点。完全二叉树完全二叉树 ( (见后图) ) 一棵二叉树，若所有的结点其度数或者为0，或者为2，则称为完全二叉树。 满满二二叉叉树树：深度为K且有2K-1个结点的二叉树称为满二叉树。此时，每一层上的结点数都是该层上的最大结点数。顺顺序序二二叉叉树树：一棵深度为K的二叉树，如果它的叶结点都在第K层或第K-1层上，且对任一结点，若其右子树中有叶结点在第K层，则其左子树的叶结点都应在第K层。从上述定义可以看出，如果对一棵深度为K的满二叉树和一棵深度为K，具有相同个结点的完全二叉树从根结点开始，从上到下，从左到右进行连续编号那么

89、相同位置上结点的编号完全相同。完全二叉树满二叉树顺序二叉树2.2.二叉树的性质二叉树的性质性质1 在二叉树中,第i层最多有2i-1个结点。性质2 在深度为K的二叉树中,结点总数最多为2K-1个，K1。性质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)由(

90、1)式和(2)式得 n0=n2+1性质4 具有n个结点的顺序二叉树的深度为log2n+1。假设树的深度为K。则根据性质2和顺序二叉树为定义，有 2K-1-1n2k-1 或 2K-1n2k 于是 K-1log2n1，则其双亲结点数是i/2。 2)如果2in，结点i无左孩子(此时结点i为叶子)；否则其左孩子是结点2i。 3)如果2i+1n,结点i无右孩子；否则其孩子是结点2i+1。3.二叉树的存储结构二叉树的存储结构（1）二叉树的顺序存储 用一组连续的存储单元存储顺序二叉树中的数据元素，编号为i的结点的数据元素存放在相应向量中序号为i的位置上。根据二叉树性质5，结点i的双亲存放在序号为i/2的位置

91、上，结点i的左、右孩子(如果有的话)将依次存放在序号为2i和2i+1的位置上。这种方法对于一般二叉树空间浪费大，特别是单支树。（2）二叉树的链式存储方式 当用链表表示二叉树时，结点至少包含数据域、左指针域和右指针域，其结点binode结构如下:struct binodestruct binode intint data; data; struct binodestruct binode * *lchildlchild; ; struct binodestruct binode * *rchildrchild; ; ABDECFGABCDEFG00000000T链表中会有许多空指针。4.4.二叉

92、树的遍历二叉树的遍历所谓二叉树的遍历，是指树的每个结点按某种规律恰好被处理（访问）一次的过程。 二叉树的遍历是一种最基本的算法。其含义是逐一访问树中的各结点，且只访问一次。从二叉树的递归定义可知，二叉树是由三个基本单元组成，即根结点(D)，左子树(L)，右子树(R)。因此，若能依次遍历这三部分，便是遍历了整个二叉树。 根据排列组合，共有六种方案，即DLR，LDR，LRD，DRL，RDL，RLD。 若对左右子树的访问次序限定是先左后右，则只有前三种情况，分别称为先序遍历，中序遍历和后序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。遍历二叉树的递归算法：三种方法：先序遍历：若二叉树

93、空，则空操作：否则：(1)处理根(2)按先序遍历左子树(3)按先序遍历右子树中序遍历：若二叉树空，则空操作：否则：(1)按中序遍历左子树(2)处理根(3)按中序遍历右子树后序遍历：若二叉树空，则空操作：否则：(1)按后序遍历左子树(2)按后序遍历右子树(3)处理根ABDEFGCHI对左图的三种遍历：先序：ABDEHICFG中序：DBHEIAFCG后序：DHIEBFGCA先序遍历:ABDEGCF；中序遍历:DBGEACF；后序遍历:DGEBFCA。若二叉树采用链式存储结构，结点为: struct binodestruct binode int int data; data; struct bin

94、ode struct binode * *lchildlchild; ; struct binode struct binode * *rchildrchild; ; 二叉树的先序遍历算法的递归过程描述如下: preorder(preorder(struct binodestruct binode *t) /* *t) /* 先序遍历先序遍历 */ */ while (t!=NULL)while (t!=NULL) printf printf(%dn,t-data); /* (%dn,t-data); /* 处理根结点处理根结点 */ */ preorder(t-preorder(t-lchi

95、ldlchild); /* ); /* 遍历左子树遍历左子树 */ */ preordeepreordee(t-(t-rchildrchild); /* ); /* 遍历右子树遍历右子树 */ */ 二叉树的中序遍历算法的递归过程描述如下: midordermidorder( (struct binodestruct binode *t) /* *t) /* 中序遍历中序遍历 */ */ while (t!=NULL)while (t!=NULL) midordermidorder(t-(t-lchildlchild); /* ); /* 遍历左子树遍历左子树*/ */ printfprint

96、f(%dn,t-data);(%dn,t-data); midordee midordee(t-(t-rchildrchild); /* ); /* 遍历右子树遍历右子树 */ */ 递归形式的算法描述过程精练，算法的正确性也容易得到证明。 缺点：一是执行效率较低；二是要求编写程序用的高级语言允许过程递归调用。二叉树先序遍历的非递归的过程描述如下：（此时需要用到栈。用指针数组a表示栈，记下尚待遍历的子树根结点指针，这也是栈的一种典型应用。）ppreorderppreorder( (struct binodestruct binode *t) *t) int int i=0; i=0; stru

97、ct binode struct binode *a *a，*p;*p; a0=t; a0=t; while(i=0) p=ai; while(i=0) p=ai; printf printf(%dn,p-data); (%dn,p-data); /* /* 处理根结点处理根结点 */ */ i-; if(p-i-; if(p-rchildrchild!=NULL)!=NULL) i+; ai=p- i+; ai=p-rchildrchild; /* /* 若右指针不为空，则进栈若右指针不为空，则进栈 */ */ if(p-if(p-lchildlchild!=NULL)!=NULL) i+;

98、 ai=p- i+; ai=p-lchildlchild; ; /* /* 若左指针不为空，则进栈若左指针不为空，则进栈 */ */ 二叉树中序遍历的非递归的过程描述如下：（此时用到栈为链接栈。栈用于存放正在遍历的子树根结点指针。）struct snode struct snode struct binode struct binode * *addraddr; ; struct snode struct snode *link; / *link; /定义链栈定义链栈 ; ;midordermidorder( (struct binodestruct binode *t) /t *t) /t为

99、树根为树根 struct snodestruct snode *top,*p; / *top,*p; /链栈指针链栈指针 top=NULL;top=NULL; while(t!=NULL|top!=NULL) while(t!=NULL|top!=NULL) while(t!=NULL) while(t!=NULL) p=( p=(struct snodestruct snode *) *)mallocmalloc( (sizeofsizeof( (struct snodestruct snode);); p- p-addraddr=t;p-link=top;=t;p-link=top; to

100、p=p; t=t- top=p; t=t-lchildlchild; ; if (top!=NULL)if (top!=NULL) t=top- t=top-addraddr; ; printf printf(“%c”,t-data);(“%c”,t-data); p=top; p=top; top=top-link; top=top-link; free(p); free(p); t=t- t=t-rchildrchild; ; 实例：先建立一棵二叉树，然后用中序遍历二叉树。# #include include stdiostdio.h .h #include #include stdlib

101、stdlib.h.h#define NULL 0#define NULL 0typedef structtypedef struct node node char data; char data; struct struct node *le,*re; node *le,*re;TREENODE;TREENODE;TREENODE *root;TREENODE *root;TREENODE * create_tree() /*TREENODE * create_tree() /*建立二叉树建立二叉树 */ */ TREENODE *t;TREENODE *t; char c; char c;

102、c= c=getchargetchar();(); if(c=#)return (NULL); if(c=#)return (NULL); else t=(TREENODE *) else t=(TREENODE *)mallocmalloc( (sizeofsizeof(TREENODE);(TREENODE); t-data=c; t-data=c; t-le=create_tree(); t-le=create_tree(); t-re=create_tree(); t-re=create_tree(); return(t); return(t); voidvoid inorder in

103、order(TREENODE *p)(TREENODE *p) if (p!=NULL) if (p!=NULL) inorder inorder(p-le);(p-le); printf printf(%c,p-data);(%c,p-data); inorder inorder(p-re); (p-re); main()main() TREENODE *root; TREENODE *root; printf printf(Create Bin_Tree:); root=create_tree();(Create Bin_Tree:); root=create_tree(); printf

104、 printf(print Bin_Tree(print Bin_Tree inorder inorder:);:); inorder inorder(root);(root); 运行情况：运行情况：Create Bin_Tree:a#bc#Create Bin_Tree:a#bc#print Bin_Treeprint Bin_Tree inorder inorder: :acbacbCreate Bin_Tree:Create Bin_Tree:abdabd#efef#g#c#g#c#print Bin_Treeprint Bin_Tree inorder inorder: :dbfega

105、cdbfegac 如果给出一棵二叉树的先序遍历结果和中序遍历结果，或者给出后序遍历结果和中序遍历结果，我们就可画出该二叉树； 如果只给此二叉树出先序遍历结果和后序遍历结果，就无法画出该二叉树。 有两棵二叉树T1和T2，它们的先序和后序遍历结果完全相同。显然只凭先序和后序遍历结果无法确定到底是哪一棵二叉树。2.3.3 2.3.3 树的存储结构树的存储结构 树在计算机内有多种表示方法，下而介绍三种常用的方法。1.双亲表示法 用一组连续空间存储树的结点，同时在每一个结点中附设一个指示器，指示其双亲结点的位置。此结构很容易找到结点的双亲；但若要找到结点的孩子，则需遍历整个向量。2.孩子表示法 每个结点

106、可能有多个孩子，用多重链表来存储一棵树。链表中的结点由一个数据域和若干个指针域组成，每个指针域指向该结点的一个孩子。由于树中每个结点的度数不同，所以链表中的结点可以采用定长表示，也可以采用不定长表示。 若树的度数为d，则在定长结点表示中，结点的结构为： 这里data表示自身的数据，而ch1、ch2.chd表示1、2.d孩子的指针，不同的结点其度数d不同，因而结点的结构也不同。在一棵有n个结点度为d的树中必有n*d个指针域，而有用的指针域为 n-1，而有 n*(d-1)+1个空指针域。在不定长表示中，结点的结构为: (a)定长结点表示 (b)不定长结点表示3.兄弟表示法 兄弟表示法又称二叉链表示

107、法。在这种表示法中，结点的结构为：first_child datanext_brother 把双亲表示法和孩子表示法结合起来。2.3.4 森树与二叉树的转化：在用多重链表表示一般的树时，若结点不定长，则对树的处理很不方便；若用定长结点，则会浪费存储空间。另外，由于树中各结点的度各不相同，因此，对树中各结点的搜索比较困难。在实际应用中，往往将一般的树结构转化成二叉树。转化方法：（1）在兄弟之间加一连线；（2）对每个结点，除了其左孩子外，去除其与其余孩子之间 的联系；（3）以树的根结点为核心，将整树顺时针转45度。ABCDEJKFGHILMNABCDEFGHIJKLMN任何一棵树所对应的二叉树，其

108、右子树必空。也就是说，所有的树都可以转化为二叉树，但不是所有的二叉树都可以转化为树。森林转换成二叉树：若有三个结点，则就可能组成五种二叉树形式。若先序为ABCDEFGHI中序为BCAEDGHFI原则：根据先序定义：A必为根结点。根据中序定义：A前的结点为左子树A后的结点为右子树。则组成的二叉树为：二叉树的应用二叉树的应用 二叉树的应用十分广泛，常用于判定和对策，例如假设有12外表完全相同的球，但其中有一个重量不合标准，要求用天平以最少的次数找出这个不标准球，并判定它比标准球轻还是重，便可以用一系列的判定所构成的树来描述和解决。 编制一个将百分数的成绩转化为优、良、中、及格和不及格五级制表示的程

109、序。switch(grade/10)switch(grade/10) case 10:case 9: g= case 10:case 9: g=”优优”; ; break;break; case 8: g= case 8: g=”良良”; ; break;break; case 7: g= case 7: g=”中中”; ; break;break; case 6: g= case 6: g=”及格及格”; ; break;break; default: g= default: g=”不及格不及格” 成绩分布规律表分数分数0-590-5960-6960-69 70-7970-79 80-898

110、0-89 90-10090-100比例比例0.050.050.150.150.400.400.300.300.100.10 假设有10000个学生成绩，a树需比较31500次，b树需比较20500次，C树需比较22000次。由此可见，结构不同的树是有优劣之分的。而哈夫曼树是一类带权路径长度最短的树。亦称最优二叉树。最优二叉树（Huffman树）一.概念路径：从树中一个结点到另一个结点之间的分支。路径长度：路径上的分支数目。树的路径长度：从树根到每一个结点的路径长度之和。树的带权路径长度：为各端结点的权Wk与相应的路径长度Lk乘积的代数和。即可表示为：其中：Wk为各结点的权（每个结点对应一个实数

111、Wk）。Lk为结点的路径长度（Lk为树的根结点到该结点长度，实际为该叶子的祖先数，也等于层次减一）。 n为叶子结点数目。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中删除这二棵树，

112、同时将新得到的二叉树加入F中。（4）重复（2）和（3），直到只含一棵树为止。例如图2.42中五个点a、b、c、d、e(权重分别为2、7、5、5、4)来构造哈夫曼树的过程如下HuffmanHuffman算法的一个应用：算法的一个应用： 为信息为信息M M0 0,M,M1 1.M Mn n-1-1求一组最佳编码，每个编码都是二进制求一组最佳编码，每个编码都是二进制位串。若把位串。若把M M0 0,M,M1 1.M Mn n-1-1的使用频率看作是对应的权，就可用以的使用频率看作是对应的权，就可用以HuffmanHuffman算法构造出一棵具有最小加权长度的译码树，使得译码算法构造出一棵具有最小加权

113、长度的译码树，使得译码时间达到最小。时间达到最小。例：给定一些仅由五个字母例：给定一些仅由五个字母a,b,c,d,ea,b,c,d,e组成的单词，它们使用的组成的单词，它们使用的频率依次为频率依次为10,5,20,10,18.10,5,20,10,18. 组成最优二叉树后，把向左分支记为组成最优二叉树后，把向左分支记为0 0，而向右的分支记为，而向右的分支记为1 1，于是就得到一种编码。，于是就得到一种编码。 a:011 b:010 c:11 d :00 e:10a:011 b:010 c:11 d :00 e:1001001100100100110010的相应译码是的相应译码是badebad

114、e001110111001110111就得不到相应的译码。就得不到相应的译码。2.42.4图图 图是较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，而在树中，数据元素之间有着层次关系。在图中，任何两个数据元素之间都可能存在关系。2.4.12.4.1图的定义和基本概念图的定义和基本概念 图的定义： 图G(Graph)是由两个集合V(G)和E(G)组成的,记为: G=(V,E) 其中:V(G)是顶点(Vertex)的非空有限集合； E(G)是边(Edge)的有限集合，边是顶点的有序对或无序对。图的基本概念图的基本概念 有向图G的E(G)是有向边(也称为弧)的有限集合，弧记为。

115、 无向图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 2.4.2 图的存储结构图的存储结构1.1.邻接矩阵表示法邻接矩阵表示法邻接矩阵表示各顶点间的邻接关系。邻接矩阵的元素规定如下:邻接矩阵表示法对求顶点的度很方便 在无向图中每个顶点的度数

116、就等于邻接矩阵中与该顶点相应的行或列中非零元素的个数； 在有向图中，每行的非零个数等于相应顶点的出度,每列的非零元素个数等于相应顶点的入度。邻接矩阵用二维数组就可以存储。2.2.邻接表邻接表 邻接表有一个顺序存储的结点表和n个链接存储的边表组成。结点表的每个表目对应于图的一个结点，每个表目包括两个字段，结点的数据和指向此结点的边表的指针。图的每个结点都有一个边表，一个结点的边表的每个表目对应于该结点相关联的一条边，每个表目包括两个字段：一个是与此边相关联的另一个结点的序号，2.4.32.4.3图的遍历图的遍历 从图中某一顶点出发系统地访问图中所有顶点，且使每一顶点仅被访问一次，这一过程就叫做图

117、的遍历.一. 深度优先搜索(类同于树的先序遍历) 从图中某个顶点v0出发找到邻接顶点w，再从w出发找与w邻接的未访问的顶点，直至一个所有邻接点都被访问过的顶点u，然后退到尚有邻接点未被访问的顶点，从其出发重复上述过程直至从任一被访问过顶点都无未被访问之邻接点为止。13245visit00000link123450000023413451212524vertexnext深度优先搜索为：1-2-3-4-51-2-3-4-5 一个图的深度优先搜序列不一定唯一，它与算法、图的存储结构和初始出发点有关。深度优先搜序列为: 1-2-4-8-5-3-6-713256000001234500002331451

118、6282867848707030045000遍历算法：1.访问数初始化，visited的所有元素均为false.2.对尚未访问的数组调用深度搜索算法dfs(g,v)。3.深度搜索算法：访问第i个顶点，使visitedi=true,并访问。对i的尚未访问过的顶点的邻接顶点递归调用dfs。 A.从1出发，dfs(1),visited1=true B.dfs(2), visited2=true C.dfs(4), visited4=true D.dfs(8), visited8=true E.dfs(5), visited5=true F.dfs(3), visited3=true G.dfs(6)

119、, visited6=true H.dfs(7), visited7=true用一个递归的过程。假定图有n个结点，采用相邻矩阵表示法。那末图的深度优先搜索算法dtraver具体描述如下：dfs(int an,int i,int n) int j; printf(“V=%-4d”,i); visitedi=1; for(j=0;jn;j+) if(aij!=0 & visitedj=0) dfs(a,j,n); dtraver(int a,int n) int i; for(i=0;in;i+)visitedi=0; for(i=0;in;i+) if(visitedi=0) dett(a,i,

120、n);数组visited应作为全局变量来说明非递归算法：要用栈。dtraver1( struct node *link,int visit,int n,int v0) int i,w; struct node *p; for (i=1; ivertex; if(visitw=0) printf(“v%5d,”,w); visitw=1; push(s,p-next); p=linkw; else p=p-next; else p=pop(s); 2. . 广广度优先搜索度优先搜索 从图中某顶点V0出发，访问V0后依次访问与V0邻接的各个未曾访问过的顶点，然后，分别从这些邻接点出发再访问与其相邻

121、接的但未被访问过的顶点，如此下去，直至所有邻接的顶点均被访问过为止。前图的广度优先搜索为：1-2-3-4-5-6-7-8需要使用一个队列。实现遍历的处理过程如下：1.把队列置空。2.打印出发顶点，置该顶点已被访问的标志。3.让出发顶点进队。4.若队列不空，则：(a)取出队首中的顶点V。(b)在邻接表中，依次取得与顶点V邻接的各个顶点。(1)若当前取得的邻接顶点未被访问，则打印该顶点，置该顶点已被访问的标志。该顶点进队。(2)取得下一个邻接顶点。(c)转45.若队列空，则处理过程结束。btraver1( struct node *link,int visit,int n,int v0) int

122、i,w; struct node *p; for (i=1; ivertex; if( visitw=0) printf(“v%5d”,w); visitw=1; addque(q,w); p=p-next; else v0=delque(q ); p=linkv0; /* 非递归算法 */递归算法：bfs(int an,int i,int n) int j,k,b1=-1,b2=0,bn; bb2=i; while (b1b2) b1=b1+1; k=bb1; visitedk=1; printf(“V%=4d”,k+); for(j=0;jn;j+) if(akj!= & visitedj

123、=0) b2=b2+1; bb2=j; btraver(int an,int n) int i; for(i=0;in;i-) visitedi=0; for(i=0;in;i-) if(visitedi=0) bfs(a,i,n);练习：已知一个图如下所示，若从顶点a出发深度优先搜索法进行遍历，则可能得到的一种顶点序列为:按广度优先搜索进行遍历，则可能得到序列为 a-b-e-d-f-ca-b-e-d-f-ca-b-c-e-f-da-b-c-e-f-d最短路径最短路径 求解最短路径有二种算法：（1）求从某个顶点到其它顶点的最短路径。（2）求每一对顶点之间的最短路径。以下介绍第一种方法。最短路径

124、是指：如果从某个顶点出发，这个顶点称为源点，经图的边到达另一顶点，这个顶点称为终点，所经过的路径不止一条，找出一条路径使得沿此路径上各边的权值之和为最小。最短路径也称为最小生成树。构造最小生成树的方法： 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 ij E(G),wij是边上的权 cost(i,j)= 0 i=j

125、 ij,不在E(G)中 0 10 19 210 10 19 2110 0 5 6 1110 0 5 6 11 5 0 6 5 0 6 6 6 0 18 14 6 6 0 18 1419 18 0 3319 18 0 3321 11 14 33 021 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,v

126、2,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 网的结点个数

127、*/ 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); /* 输入 ij 上半三角形 */ 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

128、(i)=1) for( j=1; j=nv; j+) if( t(j)!=1) if(ij) 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 查找查找 查找就是在数据结构中找出满足某种条件的数据元素。若在数据结构中找到了这样的元素，则称查找成功，否则称查找失败。2.5.1 线性查找法线性查找法1. 顺序查找法其查找过程为：从表的第一个元素开始，将给定的值与表中各元素的关键字逐

129、个进行比较，一直到找到相等的关键字，则查找成功；否则就是表中没有要找的元素，查找失败。 seqsrch(int a,int n,int k) int i=0； while(ai!=k & in) i+; if(in) return(i); else return(-1); 链表的查找：#include 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.

130、2.对半查找法：对半查找法：只适用于有序线性表只适用于有序线性表以顺序方式存放的有序表的查找可采用对半查找。 将被查关键字k与线性表中间位置m上的数据元素的关键字进行比较：（1）若k=am，则查找成功，过程结束。（2）若kam, 则取表的后半部分作为新表再去查找。（3）若kam, 则取表的前半部分作为新表再进行查找。 这个过程一直进行到查找成功或子表的长度为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 (am=k) return(m); else if(amdata等于K，则查找

131、成功。算法结束。否则转3。3.如果Kdata，那么t=t-lchild，转（1）。 否则 t=t-rchild，转（1）。递归算法struct bnodestruct bnode intint data; data; struct bnodestruct bnode * * lchild lchild; ; struct bnode struct bnode * * rchild rchild; ; struct bnodestruct bnode *bansrch1( *bansrch1(intint k k，struct bnodestruct bnode *t) *t) if (t=NU

132、LL) return(NULL); if (t=NULL) return(NULL); else if(t-data=k) return(t); else if(t-data=k) return(t); else else if(t-datak) return (k,bansrch1(t- if(t-datak) return (k,bansrch1(t-lchildlchild);); else return (bansrch1(k,t- else return (bansrch1(k,t-rchildrchild);); 非递归算法struct bnodestruct bnode inti

133、nt data; data; struct bnodestruct bnode * * lchild lchild; ; struct bnode struct bnode * * rchild rchild; ; struct bnodestruct bnode *bansrch2( *bansrch2(intint k k，struct bnodestruct bnode *t) *t) struct bnodestruct bnode *p; *p; p=t; p=t; while(p!=NULL)&(p-data!=k) while(p!=NULL)&(p-data!=k) if (

134、p-datak ) p=p- if ( p-datak ) p=p-lchildlchild; ; else p=p- else p=p-rchilerchile; ; return(p); return(p); 二叉排序树的插入过程二叉排序树的插入过程 若二叉排序树为空，则插入结点应为新的根结点，否则根据关键字比较的结果确定是在左子树还是在右子树中继续查找，直至某个结点的左子树或右子树空为止，则插入结点应为该结点的左孩子或右孩子。1. 递归算法insbtree(int k,struct bnode *t) if(*t=NULL) struct bnode *p; p=(struct bnod

135、e *)malloc(sizeof(struct bnode); p-lchild=NULL; p-rchild=NULL; p-data=k; * t=p; else if(*t)-datak) 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

136、; q-data=k; if(t=NULL) t=q; return(t); p=t; while(p-lchild!=q)&(p-rchild!=q) if(kdata) 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); 二叉排序树的构造就是从空树出发，依次输入表中的元素作为结点，逐个插入二叉排序树的过程。 如果给定一个数据元素的集合，则数据元素的读入顺序不同，其构造出的二叉排

137、序树的形态也不同。例. 序列(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。5312613379045 78100613790124535378100图1图2312374553617890100图3删除结点的算法：1.首先调用search（），从而确定被删结点在树中的位置。2.如果被删结点不在树中，则算法结束。3.如果被删结点在树中。则进行下面的删除：(i)如果被删结点是根结点，那么(a)若被删点无左子结点,则用被删结点的右

138、子树作为删除后的树。(b)若被删点有左子结点,则用被删结点的左子结点为根结点，同时把被删结点的右子树作为被删结点的左子树按中序最后一个结点的右子树。(ii)如果被删结点是不是根结点，那么(a)若被删结点无左子树，则(1)如果被删结点是它的父结点的左子结点，那么把被删结点的右子树作为被删结点的父结点的左子树。(2)如果被删结点是它的父结点的右子结点，那么把被删结点的右子树作为被删结点的父结点的右子树。(b)若被删点有左结点，则把被删结点的右子树作为删结点的左子树按中序最后一个结点的右子树。同时进行（1）如果被删结点是它的父结点的左子结点，那么把被删结点的左子树作为被删结点的父结点的左子树。（2）

139、如果被删结点是它的父结点的右子结点，那么把被删结点的左子树作为被删结点的父结点的右子树。（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) /*被删结

140、点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 排序排序 就是

141、将一个数据元素的无序序列，按其关键字的大小重新排列，最后变成一个有序序列。 内部排序：整个排序过程都在计算机内存中进行。外部排序：排序过程必须借助外存储器进行。2.6.1 2.6.1 选择排序选择排序基本思想：每一趟在n-i-1个记录中选出关键字最小的记录作为有序序列的第i个记录。1.1.直接选择排序直接选择排序 基本方法是：每次从待排序的文件中，选出关键字最小的(或最大的)记录，放在已排序的记录的后面，直到全部排好序为止。 具体操作为：先在待排序文件中选出关键字最小的记录，把它与第一个记录交换存储位置，然后在余下的记录中再选出关键字次最小的记录与第二个记录交换，重复此过程，直至所有记录为有序

142、序列为止。初始状态 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

143、; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(ajak) k=j; if(k!=i) x=ai; ai=ak; ak=x; 2.2.堆排序堆排序 堆排序是对选择排序的改进。 基本思想：当用n-1次比较选择出最小的一个关键字后，在余下的关键字选择中，若能利用前面己进行的比较所得的有用信息，则可以减少关键字的比较次数。 堆：对于树T中的任一结点的值不大于它的左子结点的值，且不大于它的右子结点的值，那么称树T是一个堆。即对任意i，若R2i+1,R2i+2 存在，并且满足 Ki=K2i+1 Ki=K2i+2 i=0,1,2n/2则称之为堆。 从定义可以看出，堆

144、顶记录的关键字K0，必是所有记录中关键字最小的一个。 则从根结点开始，从上到下，从左到右，对顺序二叉树进行遍历，所得结点序列就是一个从小到大的序列。 这样的处理过程为堆排序。堆的输出堆的输出： 先输出堆顶记录之后，用堆中最后一个记录代替。如下图(A)所示，此时根结点的左、右子树均为堆。比较左、右子树的根结点，由于右子树的根结点的值小，交换根结点和右子树根结点的值，如下图(B)所示的状态。对右子树重复上述过程，直至叶子结点。这时便建成了一个新堆，如下图(C)所示。(A)(B)(C)堆5,20,10,40,30,50,25,60形成的顺序二叉树。堆排序的基本思想是堆排序的基本思想是： 将一组待排序

145、的关键字，按堆的定义排成一个序列，这就找到了最小关键字。然后将最小关键字取出，用余下的关键字再建堆，便得到了次最小的关键字。如此反复，直到将全部关键字排好序为止。 从堆顶至叶子的调整过程称为筛选。一般地，如果以as+1,as+2,as+3,at为根的子树都是堆，则将as筛选到合适位置，使得以as,as+1,as+2,as+3,at为根的子树都是堆。堆的筛选算法：堆的筛选算法：soft(int a, int s, int t) int i=s, j=2*i+1, k=ai; while(j=t) if (jaj+1) j+; /* j为两叶子结点中小结点的下标*/ if (kaj) ai=aj;

146、 i=j; j=2*i+1; /* 如果根大于叶子结点，则交换*/ else j=t+1; /* */ ai=k; 建建堆堆过过程程：对一棵顺序二叉树，各叶子结点没有孩子，它们自然符合堆的定义。对具有n个结点的顺序二叉树来说，最后一个非终端结点是第n/2个记录。我们从第n/2个记录起开始筛选，直到第1个记录止，则an就是一个堆。heepsort(int a,int n) int i,k; for(i=n/2;i=0;i-) soft(a,i,n-1); /*将a0.n-1建成一个堆 */ for(i=n-1;i0;i-) k=ai; ai=a0; a0=k;/* 将堆顶和未排序子序列a0.i-

147、1中最后一个记录相交换 */ soft(a,0,i-1); /*将 a0. .i-1重新调整为堆*/ for(i=0;i=0) k=0; for(i=0; iai+1) k=1; s=ai; ai=ai+1; ai+1=s; j-; 开关量K的作用是当其趟无交换时，即终止程序的运算 。2.2.快速排序快速排序 基本思想:通过一趟分割将线性表分成两部分，其中前一部分的所有元素值均不大于后一部分中的每一元素值；然后对每一部分再进行分割，直到整个线性表有序为止。 具体算法：设置两个指针i和j，其初始状态分别指向文件中第一个记录和最后一个记录。先将第一个记录移向辅助变量x中，然后从j所指位置起向前搜索

148、第一个关键字小于x的记录，找到后，将aj移至ai的位置；再从i所指向的位置后搜索第一个关键字大于x的记录，找到后，将ai移至aj的位置；重复这两步过程，直至i=j，最后将x送至ai中去。至此一趟排序完成，文件划分为两个子文件。初始状态 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

149、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=ai; dowhile(i=x) j-; /*自右向左扫描*/ if(ij) ai=aj; i+; while(ij & ai=x) i+; /*自左向右扫描*/ if(ij) aj=ai; j-; while(i!=j); ai=x;

150、 return i;递归算法递归算法qksort(int a,int s,int t)int i; if (st) 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(lp) qkone(a, l, p); push(s, i+1, p); p=i-1; 2.6.3 2.6.3 归并排序归并排序 前面介绍的几种排序方法，对排序文

151、件的初始状态都不作任何要求，而归并排序是另一种类型的排序方法。基本思想:采用二路归并技术，即每次将数组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 4

152、5 52 60二路归并排序过程示例 有序文件as.m和am+1.t归并为bs.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(aim) for(;j=t;j+) k+;bk=aj; else for(;i=2*k) merge(a,i,i+k-1,i+2*k-1,b); i=i+2*k; if(n-ik) merge(a,i,i+k-1,n-1,b); else for(;in;i+) bi=ai; 第一趟归并后，有序子文件长度为2，结果在b中；第二趟

153、归并后，有序子文件长度为4，结果在a中。重复此过程，直到有序子文件为n，则归并排序结束。具体算法描述如下:mergesort(int a,int n) int k=1,bn; while(k执行状态:进程调度程序为之分配了处理机. 执行状态-就绪状态:因时间片已用完而被暂停执行时. 执行状态-阻塞状态:等待某事件发生而使进程的执行受阻. 阻塞状态-就绪状态:等待事件发生了.说明:1.就绪进程有多个，形成就绪队列。 2.进程调度是从就绪队列中挑选进程分配CPU。 3.进程在阻塞结束后回到就绪队列。除此基本状态外还有其它状态，在这里就不再一一介绍了。3.2.3 3.2.3 进程的控制和调度进程的控

154、制和调度1.1.进程控制进程控制 进程控制，就是对进程在整个生命周期中各种状态之间的转换进行有效的控制。 进程控制的基本功能就是为作业创建进程、撤消进程，以及控制进程在运行过程中的状态转换。 这些操作对应于一组程序，亦称为特殊的系统调用。这些特殊的系统调用也称为原语。原原语语（Primitive）是机器指令的延伸，一条原语由若干机器指令所组成，有时也称之为“软指令”，用以完成特定功能的一段程序。为保证操作的正确性和完整性，大多数原语的在执行必须是连续的，即一条原语在执行中不允许被中断，大部分原语通过系统调用方式使用。2.2.进程调度进程调度 进程调序决定就绪队列中哪个进程先获得处理机,然后再由

155、分派程序执行将处理机分配给进程的操作。进程调序程序一般在下述情况下发生的：l当正在运行的进程缺乏资源不能继续运行而进入阻塞状态时；l当运行的进程因时间片到而退回到就绪状态时；l当运行的进程因外部中断而暂停时；l当运行的进程提前结束时。 这些情况都会引起进程调度，重新分配处理机。进程调度按一定算法，选择一新进程，把处理机分配给它，并为它设置运行现场再投入运行。 进程调度要解决二个问题：(1)从就绪队列中选择哪个进程？(2)选中进程之后，进程能占用CPU多久?进程调度的二种方式进程调度的二种方式: :剥剥夺夺式式调调度度:(抡占式调度)进程在运行时,系统可根据某种原则,剥夺已分配给它的处理机,并分

156、配给其它进程的一种调度方式。 剥夺的原则有:l优先权原则:优先权高的进程可以剥夺优先权低的进程而运行。l短进程优先原则:短进程到达后可以剥夺长进程的运行。l时间片原则:运行一个CPU时间片后重新调度。非非剥剥夺夺方方式式:以这种调度方式运行时,调度程序一旦把处理机分配给某进程后，除非它自愿放弃，否则它就一直运行下去。几种进程调度算法几种进程调度算法(1)先进先出(First In First Out)(2)短执行进程优先(SCBF)(3)优先级调度(FPF)(4)时间片轮转法（RR）(5)多级反馈队列3.2.43.2.4进程的协调和通信进程的协调和通信由于进程合作与资源共享,使进程之间产生两种

157、形式的制约关系:(1)间接相互制约： 系统的重要的资源，如处理机、内存空间、设备、文件等由系统协调资源共享。进程的间接相互制约又称为互斥。互斥实质是对进程的异步运行在时间上施加某些限制。(2)直接制约关系： 一个进程在没有获得合作进程提供的必要信息之前不能超越某一执行点或无法继续工作。进程的直接制约关系称为同步，由进程间自行协调，可见,绪进程在并发执行时,必须按照一定的次序执行。互斥与同步实质上都是在执行时序上的某种限制。因此，它们是广义同步概念。故在广义上，互斥是一种特殊的同步。1 1临界区和临界资源临界区和临界资源 一次只允许一个进程使用的资源称为临界资源。 程序中使用临界资源的那段程序称

158、为临界区。 对临界区调用的原则归纳为： 有空则进、无空等待、有限等待：2.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操作和信号量初始化操作才能访问和改变它的

159、值。Dijkstra把信号量为S定义为一个非负整型量。在信号量S上的P操作和V操作定义如下：P(S)：（1）S:=S-1；（2）若S=0，当前进程继续运行。V(S)：（1）S:=S+1；（2）若S0，当前进程继续运行。 P，V操作从资源观点上看，S值表示可用资源数，0表示无可用资源，负数表示还欠缺的资源数。而P(s)表示请求分配一个资源，V(s)表示归还一个单位资源。 P，V操作既可以用于进程互斥，也可以用于进程同步。 一个简单的同步关系的问题: 信号量Sa初值为1,信号量Sb初值为0,其中n为临界资源，进程A和进程B必须互斥使用。这二个进程不管分别以什么速度向前推进，但打印的结果肯定是从1开

160、始的连续数值。 生生产产者者与与消消费费者者问题是最著名的进程同步问题，生产者与消费者共享一个有界缓冲池，生产者向池中投入消息，消费者从中取得消息。生产者消费者问题实际上是相互合作进程关系的一种抽象，常用于检验进程同步机制。 假定缓冲池中具有n个缓冲区，每个缓冲区存放一个消息，可利用互斥信号量mutex使进程对缓冲区实现互斥访问；利用资源信号量empty和full分别表示缓冲池中空缓冲区及满缓冲区的数量。只要缓冲区未满，生产者便可将消息送入缓冲区；只要缓冲池未空，消费者便可从缓冲池取走一个消费。 信号量的初值：互斥信号量mutex=1，空缓冲区empty=n，满缓冲区full=0。在生产者消费

161、者问题中应当注意：1）在每个程序中用于实现互斥的P(mutex）和V(mutex)必须成对出现。2）对资源信号量empty和full的P、V操作同样需要成对出现，但它们分别处于不同的程序中。3）在每个程序中的P操作顺序不能颠倒，否则可能引起进程死锁。V操作的次序无关紧要。3 3进程的通信进程的通信 进程以各自独立的速度向前推进。它们之间经常需要交换一定数据的信息，以便协调一致共同完成指定的任务。所交换的信息量，少则一个状态或数值，多则成百上千个字节。进程间信息交换方式有： 低级通信低级通信: : 交换少量数据。这种交换的方法常用变量，数组等。前面介绍的P，V操作也可以交换少量信息。 高级通信：

162、高级通信： 进程间交换大量数据信息，也称为消息通信。常用有消息缓冲方式、信箱通信、管道通信等方式，以较高的效率传输大批数据。实现进程高级通信的机制有实现进程高级通信的机制有:(1)(1)消消息息缓缓冲冲：也称作直接通信方式，即一个进程直接发送一个消息给接收进程。这种通信方式必须知道对方存在。靠原语send(发送)和receive(接收)来实现。(2)(2)信信箱箱通通信信：称作间接通信方式，指进程之间的通信需要通过某种中间实体，通常把这种中间实体称为信箱。利用信箱可实现非实时通信。(3)(3)管管道道通通信信：建立在文件系统的基础上,它利用共享文件来连接两个相互通信的进程，此共享文件称为管道(

163、pipe)，因而这种通信方式也称为管道通信。管道通信的实质是利用外存来进行数据通信，故具有传送数据量大的优点。3.2.53.2.5死锁死锁 在多道程序系统中，计算机系统中有限的资源与众多的请求分配资源的进程间会存在矛盾，如果管理和分配不当会引起进程相互等待资源的情况，形成这些进程都在等待资源而无法继续执行、然而也不可能归还已占用的资源。1.1.死锁的产生死锁的产生 产生死锁的主要原因有两点:竞争资源而引起死锁进程推进不当引起死锁 产生死锁的四个必要条件: (1)互斥条件 (2)请求和保持条件 (3)不剥夺条件 (4)循环等待条件2 2死锁的解除与预防死锁的解除与预防目前用于解决死锁的办法有如下

164、几种:(1)预防死锁: 破坏产生死锁的四个必要条件中的一个或几个(除第一条件外的其它条件)，来防止死锁发生。(2)回避死锁: 系统不需要采取各种限制措施去破坏产生死锁的必要条件。在资源的动态分配中，采用某种方法防止系统进入不安全状态，以避免死锁的最终发生，如著名的银行家算法。(3)检测死锁: 系统运行过程事先不采取任何防止和避免的措施。但通过系统的检测机构，及时检测出死锁的发生，采取措施清除。(4)解除死锁: 一旦死锁发生，采取措施解除死锁，方法是撤消或挂起一些进程，或剥夺资源，以便释放出一些资源。3.3 3.3 存储管理存储管理3.3.13.3.1存储管理的概念及功能存储管理的概念及功能1

165、1系统存储器的配置系统存储器的配置 系统的存储器由内、外存储器组成。程序的指令和数据只有存放在CPU能直接访问的内存中，这个程序或这个程序的部分才能够被执行。 系统使用的存储器由二部分组成：物理内存和逻辑内存。物理内存由系统实际提供，由字节组成，容量受实际存储单元的限制。逻辑内存也称虚拟内存，它把内存和外存统一进行管理，它的容量受计算机地址的位数和辅存容量限制。 内存的使用分为二部分，一部分为系统区，即系统程序使用的区域，主要存放操作系统、一些标准子程序、例行程序和系统数据等。另一部分为用户区。由操作系统存储管理系统管理。2.2.存储空间的地址存储空间的地址 高级语言编制的源程序，存在于由程序

166、员建立的符号名字空间(名空间)内，与存储器地址无任何直接关系，仅是符号名的集合，称作名空间。 源程序经编译后所形成的目标程序，其地址总是从零开始，因此称目标程序中的地址为虚拟地址空间(地址空间)。 目标地址经过链接再装入内存时，其分配到的物理地址与编译后的相对地址是不同的。称为物理地址空间，即绝对的地址集合(存储空间)。3.3.地址重定位地址重定位 用户在各自的逻辑空间内编程。一个作业在装入时分配到的存储空间和它的编程地址空间是不一致的。即程序在运行时需要把逻辑地址转换为物理地址。地址重定位地址重定位: 一个作业的逻辑地址向物理地址的转换。重定位分为静态重定位和动态重定位。静态重定位静态重定位

167、: 是在目标程序装入指定内存区的时候由装配程序在程序执行之前一次完成逻辑地址至物理地址的转换，以后地址不再改变。动态重定位动态重定位: : 是在目标程序执行中，每当形成一个访问内存的有效地址时，就动态进行地址变换。由于每形成一条指令都需变换，所以需要硬件支持，如基地址寄存器和限长寄存器等，以加快地址变换。4.4.存储器管理的功能存储器管理的功能存储器管理有两个基本目的： 一是方便用户；二是充分发挥内存的利用率。存储器管理具有以下几个功能:(1)内存分配(2)地址映射(3)存储扩充(4)存储共享和保护5.5.内存扩充技术内存扩充技术 内存的扩充的二种方法：一是物理上的扩充，为系统配置更多的存储器

168、芯片。二是逻辑上的扩充，借用软件技术实现主存容量的扩充目的。 逻辑扩充技术有覆盖技术和交换技术二种。 覆盖技术:是指同一内存区可以被不同的程序段重复使用（a）作业的调用结构 （b）覆盖结构及内存分配 若把作业P全部进入内存需要190K，而使用覆盖技术后只占用110K内存。通常覆盖技术主要用于系统程序的内存管理上。交换技术: 是指在内外存之间交换程序和数据。在内存中只驻留一部分甚至只是少数几个用户进程，其余用户进程驻在外存，当用到时进入内存。 交换技术使用户可以得到大容量的存储器和内存的运行速度。但从存储管理的角度，交换并不是一种独立的存储管理方案。它与分区技术结合，形成交换式分区管理；也可以与

169、分页或分段技术结合，形成交换式分页或分段管理。 交换技术实质上是系统把内存和外存统一进行管理，形成一个存储容量比实际内存大的存储器，这个存储器就是虚拟存储器。它的最大容量受二个因素决定，一是由计算机的地址结构而定，二是内外存容量之和所确定。3.3.23.3.2分区式管理分区式管理基本思想：将内存划分成若干连续区域(分区)，每个分区中装入一个运行作业。1.1.固固定定式式分分区区(静态分区):系统初始化时，内存分为若干区，每个区的大小可以不同，但每一个区中只能存放一个作业。一旦分好，则每个分区的大小和分区总数均不再变化。 分区分配表 区号分区大小 起始地址使用状态 18k 16k 1 216k

170、24k 0 332k 40k 1 464k 72k 0 5120k 136k 0 存储区的分配策略是顺序查找分区分配表，将满足作业请求容量的、且未使用的第一个分区分配给该作业（将其使用状态置为“1”）。回收时将分区表中的使用状态改为“0”即可2.可变分区可变分区(动态分区动态分区)存存储储区区的的分分配配:预先不划分分区的大小，在装入作业时使分配的分区大小正好适应作业的需要量，且分区的个数也不固定。系统初启时，除操作系统占据一块内存外，其余为一个完整的大空闲区。有作业要求装入时，则分配作业要求大小的空闲区，余下的为空闲区。 如某时刻内存的状态为:可变分区中对内存状态的记录和管理使用有如下几种方

171、法：(1)表格法(双表法):使用两个表格(占用区表P和空闲区表F)管理内存。这二个表的内容均为存储区的大小和起始地址。这二个表的长度均可变。 (2)位图法:将内存按分配单元划分，单元可以是若干字节或几个KB。每个分配单元对应于位图中的一位。 如: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 位位 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . . . . . . . . . . 其中：0-空闲，1-已分配。(3)链表法:用链表记录内存的占用或空闲情况。链表的每项的内容有:分配状态 分

172、区起始地址 分区大小 链接指针 链接指针可以是单向指针或双向指针。链接表也可以分别设置为已分配链表和未分配链表。(4)分配策略 链表记录通常有如下三种分配策方法:A.首次适配法(FF) 把内存中的空闲区按起始地址递增顺序排列。分配内存时，从链表首端开始查找，选择第一个满足要求的空闲块分配，而不管它究竟有多大。剩余的空间仍留在空闲链中。B.最佳适配法(BF) 把内存中的空闲区按分区大小递增次序排列。分配内存时，按链表顺序查找适合用户需求的空闲块，必定是最接近用户申请的块大小。然后按用户申请量进行分配，残余部分留在链中，并重新排列。C.最坏适配法(WF) 把空闲块按其大小递减的顺序组成链表，大块在

173、先，小块在后。分配时先挑选大的进行分配，使剩余空间不致太小。 需要指出的是，最佳适应算法不一定是最佳的，最坏适应算法也不一定最坏。 假设内存中现有两个空闲区：F1为110K，F2为60K。现依次有A、B、C三个作业请求装入运行，它们的内存需求分别是20K、80K和50K。 若采采用用WFWF算算法法，作业A可获得F1中的20K，作业B获得F1中的80K，作业C获得F2中的50K，三个作业的需求都得到了满足。 若采采用用BFBF算算法法，作业A获得F2中的20K，作业B获得F1中的80K，而作业C的需求却不能满足。 若采采用用FFFF算算法法，如果F1的地址低于F2，可得到与WF算法同样的结果，

174、否则，则得到与BF算法同样的结果。这里，最坏适应算法倒是“最佳”的。 分区管理实现了多道程序共享内存，提高了CPU的利用率，管理算法简单，容易实现。但它导致内存碎片多，拼接又化费时间，降低了内存利用率。3.3.33.3.3分页式管理分页式管理 分页式管理的出发点是为了消除碎片而打破存储分配的连续性，使得一个作业的地址空间可以分布在若干离散的内存块上，从而充分利用内存空间，提高内存利用率。 页：用户作业的空间划分为若干个大小相等的块。不足一块的补齐为一页，页面大小通常为512字节至4K大小。 所有的页从0开始依次编号每个页内部相对于0连续编址。 页帧：系统将内存空间中也划分与页大小相等的若干块。

175、 于是作业地址空间构成一个二维地址空间，其中的任一逻辑地址都可表示成（p,d）,其中p是页号，d是页内位移量即相对地址。 系统装入作业时，以页为单位给作业分配页帧。因此，作业可以按页为单位，离散地放在内存中不连续的页帧中。1.1.简单页式管理（静态分页管理）简单页式管理（静态分页管理）基本思想：如果内存当前可用页帧数不小于作业要求的页数，系统就实施分配，否则不于分配。简单页式用页表(PMT)来进行管理。每个作业有一张相应的页表， 如某作业有4页，内存中以1K为一帧进行分配，则可能的页表及对应的页帧关系。2.2.请求页式管理请求页式管理( (动态分页管理动态分页管理) )实现原理：开始时把整个作

176、业的一部分装入内存，其它部分则在运行过程中动态装入。系统对页表进行扩充，扩充后的页表组成如: 页表结构页帧号 存取控制 存在位 访问位 修改位1 RWE 1 1 1 2 RWE 1 1 0 3 RE 0 0 0 其中存在位为0表示该页不在内存，存在位为1时表示在内存。 系统在运行时动态检查页表，当存在位为0时，系统就把所需的页调入内存。但当内存中没有空闲页帧时，则先淘汰内存中的页，若淘汰的页已被修改过（修改位为1），则回写磁盘，否则直接淘汰。系统淘汰页面时有常见的策略有：(1)先进先出法(FIFO) 算法适合于程序按顺序访问地址空间。不适合于程序中有循环的情况。(2)最近最少使用法(LRU)

177、过去一段时间内未被访问过的页，近期也可能不会被访问。该算法较为复杂。实际中常使用近似的LRU算法，如最不经常使用的页面淘汰算法LFU及最近没有使用页面淘汰算法NUR等。“颠簸”: 对于刚被淘汰出去的页，进程可能马上又要访问它，故又需将它调入，因无空闲内存页帧又要淘汰另一页，而后者很可能是即将被访问的页。于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重时将导致系统的瘫痪。 请求页式管理能有效地消除内存碎片，且作业地址空间不受内存容量大小的限制，提高内存利用率。但由于建立和管理页表及动态地址，增大了系统时间和空间开销，如算法选择不当可能引起系统“颠簸”，致使系

178、统性能下降。3.3.4 3.3.4 段式管理段式管理分页并不是依据作业内存的逻辑关系，而是对连续的地址空间一种固定长度的连续划分。实际上，一个作业通常是由若干逻辑程序段和数据段所组成，从用户角度希望作业能按照自已的逻辑关系分成若干自然段，每段都有自己的名子，且都从0开始编址的一维地址空间，这样有利于程序设计，又可方便地按段名进行访问。 段式管理就是为了解决这个问题而提出的。段式管理也分有二种形式：简单段式管理和段页结合式管理。1.1.简单段式管理简单段式管理一个段定义为一组逻辑信息。一个作业由若干个具有逻辑意义的段(如主程序、子程序、数据、工作区等)组成。每个段有段名，且都从0开始编址的连续空

179、间。段的长度不固定，仅由相应逻辑信息组的大小所决定，一个作业由(s，d)组成，其中s是二维地址空间中的段号，d是段内相对地址。整个作业地址空间是二维的。 简单段式管理以段为单元进行内存分配，一段分配在一个连续的内存区，各段的长度可以不同，段与段之间可不连续。一个作业的连续地址空间可以对应若干个不连续的内存分区。 系统为每一个运行的作业建立一个段表(SMT) 。段表：段长内存起始地址状态标志段的替换算法与释放算法类同页式管理。 段是逻辑意义的如：cos(x)，sin(x)等。所以段段式式管管理理易易实实现现共共享享同一内存块里的程序或数据。不同的段表调用一个共享段时，共享段可以具有不同的段号。也

180、可以设置共享段表来实现段的共享。 为了保证各作业之间相互不干扰，系统设置段保护。一般的段保护措施段保护措施如下:l建立存取控制：段表中有“存取方式”项，存取方式有三种：写、读和执行，用R、W、E表示。l段地址越界保护措施：段表中每段的表目中有段长值，以指明该段的长度，使每个作业被限制在自己的地址空间中运行。页式、段式管理提供了内外存统一管理的虚拟存储器的概念，为用户提供了一个非常大的运行空间。段式管理中允许段长动态增长，便于段的共享和保护，便于程序动态链接。但是段式管理需要更多硬件支持，同时段长受内存限制，给系统增加了复杂性，也有可能产生“颠簸”。 2.2.段页式结合管理段页式结合管理 基本思

181、想：是利用分段向用户提供二维的编程空间，以方便用户编程，利用分页来管理内存空间，以提高内存利用率。 在段页式系统中，作业的地址仍按逻辑意义分段，是用户定义的二维逻辑地址（s，d），其中s是段号，d是段内位移量，d又可以被系统变换为，（p，w）p是页号，w为页内位移量。这样形成三维地址映射。 段页式管理:系统为每个作业建立一个段表和若干个页表，页表的个数等于段表的表目数。 访问主存的物理地址就要访问段表，页表和实际地址，所以访问主存中的一条指令或一个数据，至少要访问内存三次。段式管理与页式管理有如下不同之处：段式管理与页式管理有如下不同之处：l段是信息的逻辑单位，分段是出于作业逻辑上的要求，对用

182、户来说，分段是可见的，分页是不可见的；页是信息物理单位，段是信息的逻辑单位；分页并不是用户作业的要求，而仅仅是为了系统管理内存的需要。也就是说，段是面向使用，页是面向管理。l 分段地址空间是二维的，分页地址空间是一维的。l 段的长度不固定，由用户决定；页的长度是等长的，由系统决定。 段页式管理实现了分段、分页管理的优势互补，方便了用户，提高了内存利用率。但也增加了硬件成本和系统开销。3.4 3.4 设备管理设备管理3.4.13.4.1设备的有关概念设备的有关概念1 1设备设备 系统的设备是指进行实际I/O操作的物理设备，及控制这些设备并进行I/O操作的支持部件。从数据组织的角度，设备可以分为:

183、l块设备：以块为单位组织和传送数据。l字符设备：以字符为单位组织和传送数据。从资源分配的角度，设备可以分为:l独享设备：在作业整个运行期间为此作业独占。l共享设备：允许若干用户同时共同使用的设备。l虚拟设备：通过假脱机技术，把原来的独享设备改造成共享设备。2 2设备管理的任务设备管理的任务 (1)(1)设备分配 (2)(2)启动设备完成实际的输入/输出操作 (3)(3)设备无关性 (4)(4)提高设备的利用率3.3.中断的概念 中断是指计算机在执行期间，系统内发生急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或调度新的进程

184、执行的过程。中断源:引起中断发生的事件。中断请求:中断源向CPU发出的请求中断处理信号.中断响应:而CPU收到中断请求后转相应的事件处理程序。 根据中断源产生的条件，可把中断分为硬件中断和软件中断。 4 4通道的概念通道的概念 程序中断I/O方式中每处理一个字，要进行一次中断处理，当有大批数据需要传递时，中断次数就很多。 通道的出现建立了I/O的独立管理机构，这时只要CPU发一条I/O指令给通道，告诉通道要执行的I/O操作要访问的设备，通道便向内存索取通道程序以完成I/O控制管理。5.5.缓冲技术缓冲技术 目的：为解决高速的CPU与低速的外设之间的速度不匹配。 缓冲技术实质上是在内存中开辟一个

185、具有n个单元的区域作为缓冲区。缓冲区的大小可以按实际应用需要来确定。 其结构形式可以有多种形式，有循环队列形式、单缓冲区及多缓冲区形式、缓冲池结构等。3.4.2 3.4.2 设备管理程序设备管理程序1.逻辑设备与物理设备 设备的无关性: 用户可不必指定特定的设备，而代之指定逻辑设备。使得用户程序与实际使用的物理设备无关，可以脱离具体的物理设备来使用设备。 逻辑设备: 为了方便用户使用设备，通常用符号名代替设备的类型名。如LPT表示打印机。 为了实现与设备的无关性，系统中必须有一张联系逻辑设备和物理设备名称的映象表。2.设备分配程序 设备分配程序应按照一定的算法，决定把某一台设备分配给那一个要求

186、该设备的进程。 设备分配时的算法有先请求先服务、优先数法等。3设备驱动程序 设备驱动程序实现I/O操作。 3.4.33.4.3虚拟设备虚拟设备-假脱机系统假脱机系统虚拟设备技术(Spooling技术): 利用高速的直接存储设备（一般使用硬盘）来模拟低速的独占设备，使独占设备转化成共享设备。3.5 3.5 文件管理文件管理3.5.1 3.5.1 文件及文件系统文件及文件系统1.文件 文件是逻辑上具有完整意义的数据或字符序列的集合。2文件系统 文件系统是负责存取和管理文件的机构。3.5.23.5.2文件结构及存取方式文件结构及存取方式1.文件的逻辑结构 (1)流式文件：流式文件是由一串连续的字符序

187、列组成。 (2)记录式文件：记录式文件由若干个记录组成。2.文件的物理结构 文件的物理结构是指文件在外存储器上的组织形式。文件的物理结构一般有三种类型：连续结构、链结构和索引结构。连续结构：把逻辑上连续的文件存放在一个连续的物理介质上。链接结构：文件可以分别存放在物理介质的不同块中，块与块之间通过指针取得联系。索引结构：文件的全部记录分别存放在物理介质的不同块中，系统为每一个文件建立一张索引表.3.3.文件的存取方式文件的存取方式一般有顺序存取、随机存取两种方式。顺序存取: 对文件的每次存取是在上次存取的基础上进行。对于记录式文件，它总是在上次存取的基础上顺序存取下一个记录。而对流式文件，则在

188、读/写指针的当前位置顺序存取文件的下一串字符。随机存取(直接存取): 以任意次序直接存取文件中某一个记录，对于流式文件，需要把读/写指针调整到要访问的位置。同时，直接存取技术的具体实现还与存取文件的物理介质结构有关。3.5.33.5.3文件存储空间管理文件存储空间管理 也称为外存管理，它和内存管理有许多相似之处，最大区别是内存管理以字节为单位，而外存管理以字符块为单位。 根据文件的物理结构不同，文件在外存储器中存放的方式有连续和不连续两种。文件存储空间管理常用的技术有以下几种:1.空白文件目录:把一个连续的未分配的外存储区称为“空白文件”，系统为所有的“空白文件”建立一个目录，表目的内容为空白

189、块地址和空白块数目。 序号 第一个空白块号 空白块个数 表示的物理块号 1 2 4 2，3，4，5 2 9 3 9，10，11 3 15 5 15，16，17，18，19 4 . . .2.2.空闲块索引表空闲块索引表空闲块索引表的每个表目登记一个空闲块号，相邻表目中的块号不一定相邻。分配时，从索引表的一个非空表目中取出一个空闲块号，分配后将该块号从相应表目中删去，回收一个物理块时，将其块号填索引表的一个空表目中。这种方法对物理块的分配和回收处理都比较容易，但索引表需要占用较大的存储空间。3.3.位示图位示图 利用一个二进制位来表示一个物理块的分配状态，系统为文件的存储空间建立一张位示图，参见

190、前面的图3-3-5所示。其中每一位对应一个外存物理块，图中“1”表示对应块已分配，“0”表示对应块为“空闲”。位示图方法既可用于非连续文件，也可用于连续文件和分配，当进行连续文件分配时，需要在位示图中找到足够多的连续为0的二进位。3.5.4 3.5.4 文件目录文件目录文件目录组织方式有：1 1一级目录结构一级目录结构 整个系统只设置一个目录表，目录表就是文件控制块。2 2二级目录结构二级目录结构 文件的目录被分成二部分，第一级是主目录表，第二级是用户目录表。3 3目录树结构目录树结构 是一棵倒置的有根的树。树型结构目录可以更确切地反映系统内部文件的分支系统，用户可将部分文件构成子树与其它部分

191、分开以便处理。系统或用户还可以规定不同层次或子树文件有不同的存取权限，以便更好地对文件加以保护。3.5.5 3.5.5 文件的共享与安全性文件的共享与安全性文件的共享和安全是一个问题的二个方面。1.文件的共享(1)由系统来实现文件的共享 当要共享系统文件或其它已知用户的文件，且已知道文件的路径，则可以通过从根目录出发的路径来共享文件。(2)采用基本文件目录和符号文件目录 把文件目录分成二部分：一部分为基本文件目录，包括文件的结构信息,物理地址,存取控制及其它管理信息说明，并用系统赋予的标识符来标识。另一部分包括符号名和与之相应的标识符组成，称为符号文件目录。 对欲共享的文件进行联接，即在用户自

192、己的符号文件目录中对欲共享的文件建立起相应的表目，称为联接。2.文件的存取控制(1)存取控制矩阵 用一个二维矩阵，行坐标表示系统中全部用户，列坐标表示系统中全部文件，矩阵元素aij的值为“1”时，表示用户i允许访问j文件。反之，当aij为“0”时，表示用户i不允许访问j文件。(2)按用户分类存取控制 系统中的用户往往分类为:a.文件主b.同组用户c.一般用户。 在UNIX系统中，每个文件的存取权力说明用一个9位二进制数表示，每类用户占3位，每一位代表读、写和执行三种访问权力。(3)口令 用户为自己的每一个文件规定一个口令，附在文件目录中，凡请求访问该文件的用户，必须先提供口令。3.5.6 3.

193、5.6 文件的主要操作文件的主要操作 最基本的命令有： 建立文件、打开文件、读文件、写文件、关闭文件和撤消文件等。3.63.6作业管理与用户界面作业管理与用户界面 作业管理的主要对用户作业进行合理调度，以提高系统的吞吐量和缩短作业的周转时间，并提供用户与操作系统的接口。 在实际操作中，用户通过输入设备，如键盘、鼠标器、触摸屏等将用户要求“告诉”计算机，计算机收到这些请求后再为用户服务。 1.用户是通过命令或者程序向计算机发出请求，多个用户的请求以用户作业的方式在后备存储设备中等待。 2.计算机收到用户请求后，利用操作系统提供的命令解释和系统调用，以及相应的处理程序，有序有效地使用系统提供的各种

194、资源，完成用户作业的处理。3.6.13.6.1作业管理作业管理 作业管理主要包括作业的组织、作业的控制以及作业的调度等内容。1.作业管理的概念 作业(job)是指用户在一次计算过程中，或者一次事物处理过程中，要求计算机系统所作的工作的集合。通常，一个作业又可分为若干个顺序处理的作业步，作业步的集合完成了一个作业。2.作业的类型 从控制的角度可把作业分成脱机作业和联机作业。 脱机作业:是在整个作业运行过程中，根据作业说明书中的说明对作业进行控制. 联机作业:通常是用键盘命令直接控制作业的运行。3作业的状态（1）进入状态 提交的作业通过某种输入方式将作业输入到外存上时，称此作业处于进入状态。（2）

195、后备状态 由作业建立程序为之建立了作业控制块(PCB)，并插入到后备作业队列中等待调度运行为止。（3）运行状态 作业调度程序从处于后备状态的作业队列中选出一个作业调入内存，并为之建立相应的进程后，由于此时的作业已具有独立运行的资格，如果处理机空闲，便可立即开始执行，故称此时的作业是进入了运行状态。（4）终止状态 当作业（进程）的运行正常或异常结束时，进程便自我终止，或被迫终止，此时作业便进入终止状态。图3-6-1作业的状态及其转换4.用户如何提交作业交互式作业也称联机用户作业: 主要通过直接命令方式提供用户作业。间接的方式也称脱机作业方式: 由用户事先写好作业步的说明，一次提交给系统，由系统按

196、照作业步说明依次处理。3.6.23.6.2操作系统的用户接口操作系统的用户接口1.操作系统的程序接口 程序接口通常采用若干系统调用组成，也称编程接口。 用户通过在程序中使用这些系统调用命令来请求系统提供的服务。 用汇编语言编写程序可以直接使用这组系统调用命令，向系统提出各种控制I/O等要求。 用高级语言则可以在程序中使用过程调用语句。这些调用语句在源程序被编绎时翻译成有关的系统调用命令。2.操作系统的命令接口 命令接口由一组键盘操作命令组成。通过控制台或终端打入操作命令，向系统提出各种要求。命令接口有两个基本任务：（1）判别和解释用户键入的操作命令，并将相应的命令操作转向对应的命令处理程序。（

197、2）接收从操作系统传来的信息，然后通过屏幕提示等方式提呈给用户。命令接口有多种形式：有直接命令方式和间接命令方式。3.73.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与

198、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.03。新一统阶段(2001-)2000年2月公布了Windows 2000，希望既能有Windows NT的稳定性，又集

199、成Windows 9X娱乐性。但它虽然是一个优秀的商用操作系统，却不适用于家族/个人用户使用。 2000.10又公布Windows Me。 2001.10 在Windows 2000及Windows Me的基础上合二为一推出Windows XP3.7.2 Windows 操作系统的基本功能(1)支持应用程序的多任务运行 多个任务迸发运行，互不干扰。 抡占式CPU调度(2)高效、方便的文件管理文件管理器扩展为“资源管理器”、“我的电脑”、“网上邻居”等多种资源管理窗口。有关文件操作的常用命令集中在：“文件”、“编辑”菜单中。(3)支持PnP等标准，使新设备的安装更加简化。(4)支持联网已成为Wi

200、ndows 的标准功能。(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

201、.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等。小结小结 操作系统是加在裸机上

202、的第一层软件。它是系统应用程序和用户程序与硬件之间的接口，而且是整个计算机系统的核心，起着控制和管理和中心作用。 操作系统的主要类型：操作系统可分为批处理系统、分时系统、实时系统、单用户交互系统、网络操作系统及分布式操作系统。 操作系统的功能：可被划分为处理机管理、存储器管理、设备管理、文件管理及作业管理五大部分。 处理机管理也称为进程管理。进程管理中重要的问题是处理好进程的同步与互斥，同步是并发进程因相互合作而产生的一种制约关系，互斥是并发进程因共享资源而产生的一种制约关系。 内存管理的基本目的是提高内存利用率以及方便用户使用，它涉及四个基本问题：内存分配、地址映射、内存保护和内存扩充。内存

203、管理有各种方法，有分区管理、分页管理、分段管理和段页式管理等。虚拟存储器是广泛采用的内存扩充技术。 设备管理涉及主机之外的所有外设的管理。它的基本目标是：向用户提供方便的设备使用接口以及充分发挥设备的利用率。缓冲区是I/O系统的主要数据结构，缓冲区管理是逻辑I/O系统的基本功能之一。在SPOOLing系统的管理下，独享设备的分配变为虚拟设备的分配。 文件管理负责存取和管理文件的机构。文件系统的目的是充分利用外存储器和方便用户。为此，文件系统应能统一管理文件存储空间，实施外存储空间的分配与回收；实现文件的按名存取；实现对文件的各种控制和存取操作；实现文件信息的共享，并且提供可靠的文件保密的保护措

204、施。 作业管理提供了操作系统与用户之间的使用接口。 最后，我们给大家介绍了一些当前常用的操作系统，有MS-DOS,Windows,Windows NT ,NUIX,Linux等。 第四章第四章 数据库技术数据库技术 在计算机的三大应用（科学计算、数据处理与过程控制）中，数据处理所占比重约为70%左右。 本章先介绍数据管理技术的发展和数据库中的一些主要概念，然后重点阐述ACCESS数据库的基本操作和应用；最后对关系数据库理论作一些简要介绍。4.1 概述4.1.1 数据与数据处理1.数据与信息数据：通常指用符号记录下来的、可以识别的信息。信息：关于现实世界事物存在方式或运动状态的反映。数据与信息是

205、分不开的，它们既有联系又有区别。2、数据处理与数据管理数据处理 是指从某些已知的数据出发，推导加工出一些新的数据，这些新的数据又表示了新的信息。在具体操作中，涉及到数据收集、管理、加工利用乃至信息输出的演变与推导全过程。数据管理 是指数据的收集、整理、组织、存储、维护、检索、传送等操作，这部分操作是数据处理业务的基本环节，而且是任何数据处理业务中必不可少的共有业务。4.1.2 4.1.2 数据管理技术的发展数据管理技术的发展数据管理大致经历了如下四个阶段： 手工管理阶段文件系统阶段数据库系统阶段高级数据库技术阶段1.手工管理阶段 50年代中期以前，计算机主要用于科学计算。数据处理方式基本是批处

206、理。数据与应用程序之间的关系如图所示。特点：据与程序没有独立性；数据不能长期保存；只有程序的概念，没有文件的概念；系统中没有对数据进行管理的软件。主要缺点：数据没有独立性，数据的冗余度比较大。2 2、文件系统阶段、文件系统阶段 50年代后期至60年代中后期。文件系统是专门管理外存的数据管理软件。数据处理方式有批处理，也有联机实时处理。 在文件系统的支持下，数据的逻辑结构与物理结构之间可以有一定的差别，逻辑结构与物理结构之间的转换由文件系统的存取方法来实现。数据与程序之间有设备独立性，程序只需用文件名访问数据，不必关心数据物理位置。文件系统阶段有三个方面的问题没有彻底解决：1数据冗余度大2缺乏数

207、据独立性3数据无集中管理文件是无弹性、无结构的数据集合。3 3、数据库系统阶段、数据库系统阶段 从60年代后期开始，为了解决数据独立性问题，实现数据的统一管理，达到数据共享的目的，发展了数据库技术。 数据库（Database）是通用化的相关数据集合，它不仅包括数据本身，而且包括关于数据之间的联系。 数据库也是以文件方式存储数据的，在应用程序和数据之间，有一个数据库管理系统DBMS. 数据库管理系统和文件系统的区别如下： 高度独立性：数据库对数据的存储是按同一结构进行的。 数据的充分共享性：DBMS对数据的完整性、唯一性和安全性都有一套有效的管理手段，使得数据可以被各个应用程序正确地访问。 操作

208、的方便性:数据库管理系统还提供管理和控制数据的各种简单命令，使用户编写应用程序时易于掌握。数据库系统的主要特点如下：数据库系统的主要特点如下：1实现数据共享，减小数据冗余2采用特定的数据模型3数据具有较高的独立性4具有统一的数据控制功能目前较流行的数据库管理系统有Oracle,Infirmix,Sybase,dBase,FoxBase,FoxPro,Access,Clipper,WNIBase等。4.高级数据库技术阶段20世纪80年代开始，出现了分布式数据库和面向对象数据库系统(1)分布式数据库系统:主要有下面两个特点：（1）多数处理就地完成：数据库分布在各地，大多数处理由网络上各点的局部处理

209、机进行。（2）各地的计算机由数据通信网络相联系。分布式数据库系统兼顾了集中管理和分布处理两个方面，因而有良好的性能。(2)面向对象数据库系统 现实世界存在着许多复杂数据结构的实际应用领域，已有的层次、网状、关系三种数据模型对这些应用领域都显得力不从心。需要更高级的数据库技术来表达、管理、构造与维护大容量的持久数据。面向对象数据库正是适应这种形势发展起来的，它是面向对象的程序设计技术与数据库技术结合的产物。主要特点：1.面向对象数据模型能完整地描述现实世界的数据结构，能表达数据间嵌套、递归的联系。2.具有面向对象技术的封装性(把数据与操作定义在一起)和继承性(继承数据结构和操作)的特点，提高了软

210、件的可重用性。4.1.3 4.1.3 数据库系统数据库系统1.数据库系统的组成 数据库系统由五部分组成： 硬件系统:有容量足够大的内存、磁盘和较高的通道能力。 数据库集合:系统有若干个设计合理、满足应用需要的数据库。 数据库管理系统软件：数据库管理系统（DBMS）是为数据库建立、使用和维护而配置的软件。 数据库管理员：系统一般需要专人来对数据库进行管理，此人称为DBA。 用户：用户分两类：一类是最终用户，对数据库进行联机查询或通过数据库应用系统提供的界面来使用数据库。另一类是专业用户，负责设计应用系统的程序模块，对数据库进行操作。2.2.DBMSDBMS的主要功能的主要功能 DBMS作为数据库

211、系统的核心软件，主要目标是使数据库成为方便用户共享使用的资源，并提高数据的安全必、完整性和可用性。 DBMS支持三级结构和两级独立性。数据库管理系统具有三级结构，也称为三级模式。即：用户数据逻辑结构、数据的整体逻辑结构和数据的物理存储结构。 数据库管理系统保证了数据和程序之间的物理独立性和逻辑独立性。DBMS一般具有以下几个功能：(1)数据库的定义功能：DDL(2)数据的操纵功能：DML(3)数据库运行控制功能： DBMS必须提供以下三方面的数据控制功能： 并发控制功能 对多用户并发操作加以控制、协调。DBMS应对要修改的记录采取一定的措施。 数据的安全性控制 对数据库采用的一种保护措施，防止

212、非授权用户存取数据，造成数据泄密或破坏。 数据的完整性控制 是数据的准确性和一致性的测试。系统应采取一定的措施确保数据有效，确保与数据库的定义一致。(4)数据字典：DD 数据字典DD中存放着对实际数据库各级模式所作的定义，即对数据库结构的描述。这些数据是数据库管理系统中有关数据的数据，称之为元数据。DD提供了对数据库数据描述的集中管理手段，对数据库的使用的操作都要通过查阅数据字典进行。4.2 Access创建数据库4.2.1 数据库示例在Access中，一个数据库文件包含该数据库中的所有对象，如表、窗体、查询、报表等等，Access数据库文件的扩展名为 “.mdb”。1.创建新数据库启动Acc

213、ess2000 空Access数据库 确定 保存新数据库为 文件名 gzl 创建Access将创建一个新的数据库“gzl.mdb”，并在 Access的开发环境中打开该数据库的“数据库窗口”。 如果要在Access已经打开的情况下创建新数据库，可以使用“新建”对话框。可以使用下面三种方法之一打开“新建”对话框： 选择“文件”菜单中的“新建”命令 单击工具条中的“新建”按钮。 按 Ctrl+N 键 打开“新建”对话框后，我们选中“数据库”图标，单击“确定”按钮，输入数据库名称并选择存储路径后即可创建该数据库。1 1数据库窗口的组成数据库窗口的组成工具条对象列表对象条数据库窗口2.2.创建新表创建

214、新表表是关系型数据库中用来存储数据的对象。Accese创建一个数据库管理系统时，首先应设计并创建若干表。可以使用多种方法创建表： 使用设计器创建表:通过表设计器手工创建表。 使用向导创建表:使用Accese提供的“表向导”迅速创建表。 通过输入数据创建表：直接向表中输入数据的方式创建新表。 导入表：将其它数据库中已经存在的表直接导入到当前的数据库中。 链接表：将其它数据库中已经存在的表链接到当前数据库中，从而实现对远程数据的访问和操作。3.3.输入数据输入数据在Accese中，向表中输入数据有两种方式：一种方式是通过“数据表视图”来输入数据。 打开表的“数据表视图” 在“数据表视图”中的每一行

215、相应字段下输入所需的数据。 当所有的记录输入完之后，单击“文件”菜单下的“保存”，保存表中的数据。另一种方式是表创建一个窗体来输入数据。4.2.2 在Access中创建与编辑表1.表的创建建立数据库表是一个多步骤的过程。具体步骤为：1）打开一个数据库；2）建立一个新表格；3）输入每一个字段名、数据类型和说明；4）确定为每一个字段定义的属性；5）设置一个主关键字；6）为某些字段建立索引；7）保存数据库表。2.表的编辑1删除字段:单击“设计视图”的行选择器来选择要删除的字段，然后按下Delete鍵将鼠标移动到要删除字段，然后在“编辑”菜单中选取“删除行”选项；将鼠标移动到要删除字段，然后单击工具栏

216、中“删除行”命令按钮；将鼠标移动到要删除字段，然后单击刀标右键，在弹出的菜单是选择中“删除行”选项。2插入字段： 将光标移到插入字段后的位置，在“插入”菜单中选择“行”项即可。3移动字段： 在表的“设计视图”中简单地先单击字段的行选择器选中字段，然后单击字段并按住鼠标左键将该字段拖运至所要的新位置即可。4修改字段名：先在“字段名称”列中单击所要修改名称的字段，然后将框中的原字段名删除，并输入新字段保即可。5设置主关键字： 主关键字的值用于唯一地标识表中每一条记录。 主关键字具有下列性质：不允许为空、不允许重复、主关键字一般不允许修改。6设置表间关联 当数据库中的表建成之后，往往还要将各个不同表

217、中的信息联系在一起，这就需要定义表间的关联。表之间的关联亦称表之间的关系。1）关系的作用 来达成各个表中的字段协调一致，并通过匹配主关键字字段中的数据来实现这种功能。2）关系的分类根据两个表中记录的匹配有一对多的关系、多对多的关系和一对一的关系3）参照完整性：在输入或删除记录时，为维护表之间已定义的关系而必须遵循的规则。4）定义表间的关系 在建立Access数据库时，除非不想使关系永久有效，一般都应当使用关系建立器在表格间建立关系。如果需要，在以后还可以中断表格之间的关系。操作如下：A）打开要操作的数据库，并关闭所有打开的表。B）单击工具栏上的“关系”按钮C）如数据库没有定义任何关系，将会显示

218、一个空白的“关系”窗口。如需要添加一个关系表，可单击工具栏上的“显示表”按钮。D）在“显示表”对话框中双击选取要作为定义关系的表的名称，然后关闭“显示表”对话框，会发现“关系”窗口中添加了选中的表。E）从某个表中将所要的相关字段拖动到其它表中的相关字段。F）在“编辑关系”对话框中可以检查显示在两个表格字段列中的名称以确保正确性，必要情况下，可以进行更改。G）单击“创建”按钮创建关系。H）对每一对要关联的表，重复步骤5到步骤8。 建立关系完毕之后，关闭“关系”窗口时，Access将询问是否要保存用户的布局配置。不论是否保存此配置，所创建的关系都已保存在此数据库中。3.数据输入数据输入的方法除前面

219、所述的在数据表视图中输入外，还可以从外部导入各种类型数据库或各种格式文件中的数据。在Accese中可以导入的数据库和文件格式格式包括：dBase，Excel，Exchange，Lotus1-2-3，Outlook，Paradox，HTML文件，文本文件，ODBC数据库。4.3 4.3 数据查询与数据查询与SQLSQL语言语言4.3.1 数据查询概述查询的结果也是由列和行组成的表，是在原始数据上的二次加工。每一个查询都基于表或其它的查询。查询的基本作用如下： 可以通过查询浏览表中的数据 利用查询可以使用户的注意力只集中在感兴趣的数据上。 将经常需要处理的原始数据或统计计算定义为查询，这将大大简化

220、数据的处理工作。 查询可以为窗体、报表以及数据访问页提供数据。4.3.2 4.3.2 AccessAccess中的数据查询中的数据查询1选择查询 它从一个或多个表中检索数据，选择查询可以用来对记录进行分组，并且对记录作总计、计数、平均以及其他类型的总和的计算。2交叉查询 利用表格的行和列来统计数据，结果动态集中的每个单元都是根据一定运算求解过的表值。3操作查询 在一个操作中对查询所生成的动态集进行更改的查询。可以同时对多个记录进行修改。可以把操作查询分为四种类型：删除、更新、追加和生成表。4SQL查询 使用SQL语句来创建的一种查询。SQL查询可以包括如下的应用：联合查询、传递查询、数据定义查

221、询和子查询。5参数查询 一种在执行时显示设计好的对话框，以提示输入信息的查询。4.3.3 4.3.3 在在AcceseAccese中建立查询中建立查询1.查询设计视图：在Accese中与查询有关的视图有“设计”、SQL视图和“数据表”视图等三种。这三种视图都可以用来显示一个查询，但是“设计”视图和SQL视图是用来建立查询的，而“数据表视图主要中显示查询的动态集。2.查询中常见的基本操作：(1)选择添加表或查询(2)删除表或查询(3)在查询中实现表或查询的联接(4)在查询设计表格中添加字段1.选择查询2.双击在设计视图中创建查询3.选择查询类型Accese查询操作的进入。4.若选择SQL查询在视

222、图中4.3.4 4.3.4 结构化查询语言结构化查询语言SQLSQLSQL语言:结构化查询语言(Structured Query Language )SQL语言是数据库通用的标准语言,ANSI/ISO给出SQL的标准文本。SQL是集数据查询、数据操作、数据定义和数据控制功能于一体的语言。 目前，几乎所有的关系DBMS都支持SQL。但不同系统对它都有不同程度的扩充。 SQL作为查询标准语言的影响已波及到数据库领域之外，在人工智能、软件工程等领域的产品中也开始采用SQL作为数据和图形及其他对象的检索语言。 SQL的使用方法一般有两种：一种是以与用户交互的方式联机使用，称为交互式SQL；另一种是作为

223、子语言嵌入到其他程序设计语言中使用，称为嵌入式SQL。两种方式的语法结构基本一致。1.1.AccessAccess中的中的SQLSQL查询查询(1)SELECT语句SELECT语句完整的语法定义如下：SELECT范围*|表名.*|表名.字段1AS 别名1，表名. 字段2AS 别名2，FROM 表的描述 ，IN 外部数据库WHERE 条件表达式GROUP BY 列名1 HAVING 内部表达式ORDER BY 列名2WITH OWNERACCESS OPTIONSELECT语句各个关键词描述如下： 范 围 ： 范 围 使 用 下 列 名 词 之 一 ： ALL、 DISTINCT、DISTINC

224、TROW或TOP。缺省则默认值为ALL。 * ：从特定的表中指定全部字段。 表名：指定表的名称，该表中应该包含已被选择的记录的字段。 字段1，字段2：指定字段的名称，该字段包含了所要获取的数据。如果数据包含多个字段，则按列举的顺序依次获取它们。 别名1,别名2：查询名称,用来作列标头,代替表中原有的列名。 表的描述：指定表的具体名称，这些表包含要获得的数据。 外部数据库：专指外部数据库的名称，有时使用一些不在当前数据库中的表整个语句的含义是： 根据WHIRE子名中的条件表达式，从基本表中找出满足条件的元组，按SELECT子句中的目标列，选出元组中的分量形成结果表，如果有ORDER子句，则结果表

225、要根据指定的列名2按升序或降序排序，GROUP子句将结果按列名1分组，每个组产生结果表中的一个元组，通常在每组中作用库函数。分组的附加条件用HAVING给出。SELECT.INTO语句是用来创建一个表查询的。可以使用造成表查询来存档记录、生成表的复制备份，可输出至另一个数据库的表的副本，可用作定期显示数据的报表的依据。SELECT INTO语句完整语法定义如下：SELECT 字段1，字段2，. INTO新表 IN外部数据库FROM 操作表其中各关键词描述如下： 字段1，字段2：想要复制的新表的字段名称。 新表：欲创建表的名称。 外部数据库：专指外部数据库的名称。 操作表：从其中选择记录的现存表

226、的名称。它可以是单一表或多重表或一个查询。(2)联合查询联合查询可以在查询动态集中将两个以上的表或查询中的字段合并为一个字段。(3)传递查询 Accese传递查询可直接将命令发送到ODBC数据库服务器。使用传递查询，不必使用链接与服务器上的表进行连接就可以直接使用相应的表。(4)数据定义查询 数据定义查询与其他查询的不同是：利用它可以直接创建、删除或更改表，或者在当前的数据库中创建索引。数据定义查询语名：CREATE TABLE：创建表。ALTER TABLE ：在已有表中添加新字段或约束。DROP ：从数据库中删除表，或者从字段中删除索引。CREATE INDEX：为字段或字段组创建索引。三

227、个关系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,200

228、0-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.求学生以及他选修课程

229、的课程号码和成绩。 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=AOR 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课程学生姓名。 SELE

230、CT 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.C

231、NO);15.求计算机系的学生以及年龄小于18岁的学生。 SELECT * FROM S WHERE SD=CS UNION SELECT * FROM S WHERE SA32.2.SQLSQL数据操纵数据操纵数据操纵是指对关系中的具体数据进行增加、删除、修改等操作。(1)增加记录 往表里增加记录,有两种格式，一种是插入常量数据，实现一条记录的插入；另一种方法是把子查询的结果插入到另一个表中，可以插入多条记录。INSERT INTO语句.多重记录追加查询：INSERT INTO 表名 IN 外部数据库 字段1, 字段2, .)SELECT 数据库.字段1,字段2, .FROM 表单一记录追加

232、查询：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.SQL3.SQL数据控制数据控制 通过对数据库各种权限的授予或回收可以对整个数据

233、库进行合理的管理。这些权限包括：修改(ALTER)、插入(INSERT)、删除(DELETE)、更新(UPDATE)、创建索引(CREATEINDEX)、查询(SELECT)和所有权限。4.嵌入式SQL SQL语言可以单独地使用，这就是交互式SQL语言，也可以在应用程序中嵌入使用，应用程序使用的高级语言称为主语言。 嵌入式SQL在使用时有几个规定：(1)在程序中要区分SQL语句与主语言的语句： 所有的SQL语句前在加 EXEC SQL，结束一般加(；)。(2)数据库的表和列与程序之间的通信SQL语句中可以使用主语言的程序变量，使用时，这些变量名前面要冒号(:)作为标识，以与列名区别。程序中使用

234、的所有的表或视图，都要用EXEC SQL DECLARE语句说明。由于SQLSELECT语句执行的结果是一个元组集，要用游标（Cursor)机制作为桥梁，将集合操作转化为一条记录的操作。4.4 关系数据库4.4.1 数据描述1.从现实世界到机器世界（1）现实世界：事物与事物之间存在着一定的联系（2）信息世界：现实世界在人们头脑中有反映。（3）机器世界：用数据模型来表示数据的组织，将信息世界中的实体，以及实体间的联系抽象为便于计算机处理的方式。2.信息世界的概念模型ER模型（实体-联系模型）ER图一般有实体、属性以及实体间的相互联系三个要素。实体间的联系一般有如下三种类型：1：1（一对一联系）1

235、：N（一对多联系）M：N（多对多联系）ER方法为抽象的描述现实世界提供了一种有力工具，它表示的概念模型是各种数据模型的共同基础，进行数据库设计时必然要用到它4.4.2 数据模型1.非关系模型层次模型和网状模型统称为格式化模型。 (1)层次模型 用树形结构表示实体及其之间联系的模型称为层次模型。层次模型一般有以下特点： 1）有且仅有一个结点无父结点，此即为树的根； 2）其他结点有且仅有一个父结点。(2)网状模型 用网状结构表示实体及其之间联系的模型称网状模型。 2.关系模型关系模型是由二维表格结构作为基础。关系模型是由若干个关系模式组成的集合。每个关系模式实际上是一张二维表。（1）二维表 关系模

236、型是用二维表的形式表示实体和实体间联系的数据模型。从用户观点来看，关系的逻辑结构是一个二维表，在磁盘上以文件形式存储。 关系模型和网状、层次模型的最大差别是：关系模型用关键码而不是用指针来表示和实现实体间联系。表格简单、易懂，用简单的查询语句就可以对数据库进行操作。并不涉及存储结构。是一种具有严格的设计理论模型. 2 2基本术语基本术语关系：一个关系就是一张二维表，每个关系有一个关系名。元组：表中的行称为元组。一行为一个元组，对应于存储文件中的一个记录值。属性：表中的列称为属性，每一列有一个属性名。属性值相当于记录中的数据项或者字段值。域：属性的取值范围，即不同元组对同一个属性的取值所限定的范

237、围。关键字：属性或属性组合，其值能够唯一地标识一个元组。例如，零件关系中的零件编号；项目关系中的项目编号。关系模式：对关系的描述。格式为：关系名(属性名1，属性名2.属性名n),如：零件（零件编号，零件名称，颜色，重量）；项目（项目编号，项目名称，开工日期）等。元数：关系模式中属性的数据项目是关系的元数。 关系模型中，记录之间的联系是通过关键码来体现的。例如，要查询项目S2所选课程是什么名称？首先要在学生选课关系中找到学号S2，然后在关系中找到对应课程号为C6。再在课程关系中找到C6对应的课程名。在上述查询过程中，关键码课程号起到了连接两个关系的作用。 关系模型中的各个关系模式不应当孤立起来，

238、不是随意拼凑的一组二维表，它必须满足一定的要求。（3）关系模型的特点关系必须规范化: 关系模型中的每一个关系模式都必须满足一定的要求，如每个属性值必须是不可分割的数据单元，即表中不能再包含表。模型概念单一: 在关系模型中，无论实体本身还是实体间的联系均用关系表示。多对多联系在非关系模型中不能直接表示，在关系模型中则变得简单了。如学生选课。集合操作: 在关系模型中，操作的对象和结果都是元组的集合即关系。例如，要查询项目J02所用零件的名称、颜色和重量，操作结果是零件关系的一个子集。这个子集本身也是一张二维表。 3面向对象模型 面向对象的数据库是面向对象的概念与数据库技术相结合的产物。 面向对象模

239、型中最基本的要领是对象（object）和类（class）。（1）对象：现实世界中实体的模型化，每个对象有唯一的标识符，把一个状态和一个行为封装在一起。（2）类：每个类由两部分组成，一是对象类型，二是对这个对象类型进行的操作方法。对象的状态是描述该对象属性值的集合，对象的行为是对对象操作的集合。（3）类层次：一个系统中所有的类和子类组成一个树状的类层次，一个类继承其直接或间接祖先的所有属性和方法。4.4.3 关系的规范化1.规范化 在下表学生选课表。如果删除学号为150的学生的选课记录，那么不仅丢掉了学生150选修“市场营销学”的事实，而且还失去了“市场营销学”的学分是2的事实，即更新异常。若有

240、一门“法律”课，学分为3，但无学生选修时，不能输入。即存在插入异常。 学号学号 课程课程 学分学分 100 100 人工智能人工智能 3 3 125 125 文化学文化学 2 2 150 150 市场营销学市场营销学 2 2 175 175 数理逻辑数理逻辑 2 2 190 190 文化学文化学 2 2 把选修关系分解成两个关系，每个关系处理一个不同的主题来消除更新异常和插入异常。 如分解成学生-选课、课程-学分关系（a）学生 选课表 （b）课程学分表 学号 课程 课程 学分 100 人工智能 人工智能 3 125 文化学 文化学2 150 市场营销 市场营销 2 175 数理逻辑 数理逻辑

241、2 190 文化学 这样更新异常和插入异常都消除了，对关系进行分解的过程就叫做规范化。关系的规范就是对有异常的关系进行分解以消除异常的过程 。在分解关系时，同时注意到多个关系之间的相互参照性。2.函数依赖 函数依赖是关系属性之间的一种联系。如果给定了一个属性的值，就可以获得（或找到）另一个属性的值。例如，如果我们知道了“课程名”的值，我们就可以知道“授课学时”的值。我们说“授课学时”函数依赖于“课程名”，或“课程名”可以决定“授课学时”。记作课程名授课学时。表4-7 课程表436面向对象X002354数值分析X001672编译原理Z006572操作系统Z004254C程序设计J003672数据

242、库J001授课学期授课学时课程名课程号 函数依赖关系反过来不一定成立。比如“授课学时”值为72的课程有好几门：数据库、操作系统、编译原理。也就是说，如果A决定B，但反过来不一定B就决定A。一般来说，如果A决定B，则A和B之间的关系是多对一的关系。 我们再来看一看学生选课表。在这个表中，主要关键字是属性集合学号，课程。主关键字决定了“学分”的值，即“学分”函数依赖于主关键字学号，课程。如果我们再进一步分析，我们就会发现，决定“学分”的只是“课程”，与“学号”无关，我们把这种依赖称为部分依赖 下表中，该表的主关键字是“学号”，学生住宿的楼号依赖于学号，但是，学生应交的住宿费是由楼号决定的，也就是说

243、，“收费”依赖于“楼号”，这是一种新的依赖关系：“楼号”依赖于“学号”，而“收费”又依赖于“楼号”。一般把这种依赖关系称为“传递依赖”。80081506004120500213050021002楼号500180收费学号属性间的三种联系属性间的三种联系 至此，我们讨论了关于属性间的三种联系：依赖、部分依赖和传递依赖。下面我们将看到，关系属性间的依赖关系与关系的更新异常有着密切的联系。 实质上，关系中分为二类属性：主属性和非主属性。 规范化理论讨论主属性之间的关系及非主属性与主属性之间的关系。3.3.范式范式 需要对关系进行规范化以减少更新异常。 在规范化过程中，必须遵循一定的准则以指导关系的规范

244、化. 一般把这些准则称为范式（Normal forms，简记NF）。 范式对关系中各属性间的联系提出了不同级别的要求，根据要求级别的高低，将关系分为第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、Boyec-Code范式（BCNF）、第四范式、第五范式、域关键字范式等几种。其中，高级别的范式包含在低级别的范式中。第一范式第一范式 任何符合关系定义的表都是第一范式的。 即表的每一属性的域必须是基本类型的，集合、数组和结构都不能作为属性的类型，每一列的名字必须是唯一的。符合第一范式的关系有插入、删除、异常。修改复杂。 造成异常的原因是因为表中描述了两个不同的主题。在关系中，存在着部分依

245、赖：该关系的主关键字是学号，课程，但“学分”只由“课程”决定，与“学号”无关，也就是“学分”属性只由主关键字学号，课程的一部分而不是全部来决定。这就是导致异常的原因。第二范式第二范式第二范式的定义为： 如果一个关系的所有非主关键字属性都完全依赖于整个主关键字（也就是说，不存在部分依赖），那么该关系就属于第二范式。 根据这一定义，凡是以单个属性作为主关键字的关系自动就是第二范式。因为主关键字只有一个，不会存在部分依赖的情况。因此，第二范式只是针对主关键字是组合属性的关系。 第二范式中的关系也有异常情况由于存在传递函数依赖关系，因此，如（学号、楼号、收费），虽然学号是单属性主关键字，属于第二范式，

246、而楼号、收费都由学号决定，但此关系仍然有异常。第三范式第三范式第三范式的定义为： 一个关系如果是第二范式的，并且没有传递依赖关系，则该关系就是第三范式的。 例如：学生住宿关系可以分解为两个关系：学生-楼号关系（学号，楼号）和楼号-收费关系（楼号，收费）。这两个关系已经是第三范式的了。 在数据库规范化理论中，除了我们这里所介绍的三种范式外，还有Boyec-Code范式、第四范式和第五范式，随着范式级别的增高，对关系的分析越细致，要求也越高。1NF消除非主属性对码的部分函数依赖2NF消除非主属性对码的传递函数依赖3NF4.4.设计折中设计折中 规范化可以消除更新异常，但有时不见得就值得。比如，考虑

247、关系：客户（客户编号，客户名，省，城市，邮政编码），其中“客户编号”是主关键字。该关系不是第三范式的，因为存在传递依赖关系： 客户编号邮政编码，邮政编码(省，城市) 该关系可以分解为如下两个关系:客户（客户编号，客户名，邮政编码）。 其中“客户编号”是主关键字；编码（邮政编码，省，城市）。 其中“邮政编码”是主关键字。 现在这两个关系都属于第三范式了，但这样做可能并不一定就是好的设计。有时分解前的非规范化的表 可能更好，因为处理起来可能比较容易，尽管这样会造成“省”和“城市”的数据重复(称数据冗余），但有时并不十分计较这个缺点。小小 结结 本章主要讨论了数据与信息的联系和区别,数据管理技术的发

248、展过程,数据库系统的组成和数据库管理系统的主要功能。 以Access数据库管理系统为背景重点介绍了数据库建立和数据库查询的方法，也对结构化查询语言与SQL作了简要介绍，最后对数据之间关系的描述和数据库模型、特别对关系数据库作了讨论。综合练习题综合练习题一选择题：1.（db）已知某二叉树的前序序列是ABDC，中序序列是DBAC，问它的后序序列是。 (A) ADBC (B) DBCA (C) CABD (D)DCBA2.(db)在一个具有n个顶点的无向完全图中，包含有_多边；在一个具有n个顶点的有向完全图中包含有_条边。 (A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)n

249、23.(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)从队

250、尾插入一个新元素 (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,47.(db)若进栈序列为1，2，3，4，假定进栈和出栈可以穿插进行，则不可能出栈的序列是_. (A)1,4,3,2 (B)2,3,4,1 (C)3,1,4,2 (D)3,4,2,18.(db)在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。 (A)n (B)n+1 (C)n-1 (D)n/29.(db)对于一个

251、具有n个顶点的图，若采用邻接距阵表示，则该距阵的大小为_。 (A)n (B)(n-1)2 (C)(n+1)2 (D)n210.(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+e11.(db)已知一个图如图习题-1所示，当从顶点v1出发构造最小生成树的过程中，依次得到的各条边为_。 (A)(v1,v5)5,(v5,v2)7,(v5,v3)9,(v3,v4)3 (B)(v1,v5)5,(v1,v2)8,

252、(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 图习题-112.(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

253、)实现进程同步(C)实现进程通信 (D)访问临界资源的那段代码14.(os)分区管理要求对每一个作业都分配_的内存单元。 (A)地址连续 (B)若干地址不连续的 (C)若干连续的页框 (D)若干不连续的页框15.(os)由分页系统发展为分段系统的主要动力是_。 (A)满足用户需要 (B)提高系统吞吐量 (C)提高内存利用率 (D)更好地满足多道程序运行的需要16.(os)在请求式分页存储管理系统中有多种置换算法，其中选择在最近一段时间内最久没有被访问的页面淘汰的算法称为_。 (A)最佳淘汰算法 (B)先进先出算法 (C)最久未用算法 (D)最近最久未用算法17.(os)内存分配的基本任务是为每

254、道程序分配内存。使每道程序能在不受干扰的环境下运行，主要是通过_功能实现的。 (A)内存保护 (B)动态连接 (C)内存扩充 (D)内外存交换18.(SOFT)白盒法考虑的是测试用例对程序内部逻辑的覆盖程度，条件组合覆盖标准虽然较强，但仍不能保证覆盖程序中的_。(A)每一条语句 (B)每一个判定 (C)每一个条件 (D)每一条路径19.(SOFT)结构化程序的控制结构是由_三种基本控制结构组成的。(A)顺序、分支和条件 (B)顺序、转向和分支(C)分支、转向和循环 (D)顺序、分支和循环20.(SOFT)在软件生命周期的各阶段中，工作量最大的是_阶段 。(A)设计 (B)编程 (C)测试 (D

255、)维护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为偶数时

256、，双亲结点的编号为_;当i为奇数时，双亲结点的编号为_。25.(os)虚拟设备是指采用某种_，将某个_设备改进为多用户可共享的设备。26.(os)从资源分配角度,外设可分为独占设备，_设备，虚拟设备。27.(os)当仅有两个并发进程共享临界资源时，互斥信号量取值范围为_三个值。28.(soft)1983年IEEE把软件工程定义为：软件工程是开发、运行、_、维护和修复软件的系统方法。29.(os)_(PCB)是进程状态和控制进程转换的标志。30.(os)进程的_就是两个进程不能同时进入访问同一临界资源的临界区。31.(os)产生死锁的四个必要条件:互斥条件，_，保持与再请求条件，环路等待条件。3

257、2.(os)已经获得CPU及其他运行资源，正在运行的进程处于_状态。33.(os)共享资源的方式与进程的合作带来了进程间的相互制约关系，称为直接制约关系。直接制约的关系带来了进程的_。34.(os) 当阻塞进程的阻塞原因清除后，该进程转为_状态。35.(os) 仅允许一个进程使用的资源称为_；一个进程访问这种资源的那段代码称为_。36.(os) 地址重定位是指_到物理地址的转换。37.(os) 分页存储管理中，地址变换机构把逻辑地址分成两部分_。38.(os) 内存分配算法中，首次适配法的空闲区应按_顺序排列；在最佳适配法中，空闲区应按_次序排列。39.(os) 页是信息的_单位，进行分页是于

258、_的需要；分段信息的_单位，分段是出于_需要。40.(os) 在生产者-消费者问题中，应设置互斥信号量muter，资源信号量full和emtry。它们的初值分别是_，_，_。41.(os) 为解决高速CPU与低速外设之间的速度不匹配,系统采用_技术。42.(os) 逻辑设备是_属性的表示，它并不指某个具体的设备，而是对应于一批设备。43.(os) 文件的逻辑结构有二种:一种是字符流式文件。另一种是_。44.(os) 文件的顺序存取是按_进行读/写操作。45.(os) 为方便用户使用文件,只需知道文件的符号名就可以对文件进行存取,称为_。46.(db)已知一个有向图的邻接表如图习题-3所示，则从

259、顶点V1出发按深度优先搜索进行遍历得到的顶点序列为_，按广度优先搜索遍历得到的顶点序列为_。三改错题：47段页式存储管理中，段是作业地址空间的最小管理单位。 48当阻塞进程的阻塞原因消除后，该进程恢复到执行状态。 49使用了P，V操作，系统就不会死锁。 50设备的无关性是指用户程序与实际使用的物理设备无关。 51顺序文件适于建立在顺序存储设备上,而不适合于建立在磁盘上。52.二叉树中每个结点有二个子结点，而对一般的树则无此限制，因此二叉树是树的特殊情况。 四问答题：53.(os) 进程的三种状态间转换的原因是什么?54.(db) 已知一组记录的排序码为（46,74,18,53,14,26,40

260、,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)什么是软件生存周期？软件生存周期为什么要划

261、分阶段？常用的软件生存周期模型有哪几种？它们的主要特点是什么？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) 栈与队列是

262、两种特殊的线性表，栈的特点是什么？队的特点是什么？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)，其中含有个长度为的有序表，写出按归并排序方法对该序列进行一趟归并后的结果。五程序填

263、空：81.设t是棵结点值为整数的查找树(即二叉检索树或二叉排序树)，a是一个任意给定的整数。在下面的程序段中，函数free_tree(t)对二叉树t进行后序遍历时释放二叉树t的所有结点，函数delete_subtree(t,a)，首先在查找树t中查找值为a的结点，根据查找情况分别进行如下处理：1)若找不到值为a的结点，则不进行删除，仅返回根结点的地址。2)若找到了值为a的结点，则删除以此结点为根的子树，并释放此子树中所的结点。在删除非空子树时，如果值为a的结点是查找树的根结点，删除后变成空的二叉树，那么返回NULLnil;否则，返回树t的根结点的地址。typedef struct node i

264、nt 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(adata) q=q-lchild; else q=q-rchild; if(q!=NULL) free_tree(q); if(p=NULL) t=NULL; else if (adata

265、) _(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

266、 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-elementelement) last=append(last,A-element);

267、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在下面的程序段中，非递归函数Co

268、unt_leaf(t)住给定的二叉树t中，利用遍历二义树的方法，统计出叶子结点的个数。程序中使用一个顺序存储的栈stack存放正在遍历的子树的根结点的地址，栈顶指针是top，我们置top为-1表示栈空;栈非空时,top总是指向最后进栈结点存放在数组slack中的位置。栈中可用单元共有100个，它们依次为stack0，stack99。为简单起见，这里假设栈不会出现溢出情况，故没有进行栈溢出处理。#define MAXN 100typedef struct node int data; struct node *lchild，*rchild;NODEint count_leaf(NODE *t)

269、NODE *stackMAXN; int top=-1,count=0; while(_(A) _) while(t!=NULL) if(B) _) count+; stack+top=t;_(C)_; if(top=0) t=stacktop-; _(D)_; return(count); 83设t是一棵结点值为整数的二叉查找树，a是任意整数。下面的程序段实现了在给定的查找树t中查找值为a的结点的伯父或叔父(父亲的兄弟)结点。如果树 t不存在值为a的结点或存在值为a的结点而找不到它的伯父或叔父结点，那么返回 NULL；否则，值为a的结点在树 t中且存在伯父或叔父，那么返回伯父或叔父结点的存放

270、地址。#include 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(adata) _B_;else _C_;if(t=NULL|pp=NULL)return(NULL);else if(_D_)return (pp-rchild);elsereturn (pp-lchild);84.下面的程序段以给定的链表head的第一个结点的值为标准，对链表head的结点重

271、新排列，把小于第一个结点值的结点排在链表前面，把大于等于第一个结点值的结点排在链表后面，而把第一个结点排在中间。在程序段中使用一个链接队列，用于链接小于第一个结点值的所有结点。在程序段的执行中，始终没有改动结点中的值，而只改变结点的链接指针值。#include 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;

272、p=head;while(_A_)if(p-link-datalink;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.下列程序是把一单链表反转(置换)算法：请把程序填完全。structnode*invert_last(structnode*head)structnode*mid,*last;mid=NULL;while(head!=NULL)last=mid;mid=head;head=head-next;_;last=mid;return(

273、_);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设有四个关系，码用下横线来

274、表示：供应商(供应商代码，姓名，地址，电话)工程(工程代码，工程名，负责人，预算)零件(零件代码，零件名，规格，产地，颜色)供应零件(供应商代码，工程代码，零件代码，数量)要求用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的零件。