计算机二级公共基础知识（全）

1.1 算法

考点1 算法的基本概念

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1算法的基本特征

(1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。

(3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。

(4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2算法的基本要素

(1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。

计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括“与”、“或”、“非”等运算； ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。

(2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

(3)算法设计的基本方法

计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法

列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。

(2)归纳法

归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。

(3)递推

递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。 (4)递归

人们在解决一些复杂问题时，为了降低问题的复杂程度(如问题的规模等)，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。 递归分为直接递归与间接递归两种。 (5)减半递推技术

实际问题的复杂程度往往与问题的规模有着密切的联系。因此，利用分治法解决这类实际问题是有效的。工程上常用的分治法是减半递推技术。 所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。

(6)回溯法 在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。 4算法设计的要求

通常一个好的算法应达到如下目标： (l)正确性(correctness)

正确性大体可以分为以下4个层次： ①程序不含语法错误；

②程序对于几组输入数据能够得出满足规格说明要求的结果； ③程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；

④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 (2)可读性(readability)

算法主要是为了方便入的阅读与交流，其次才是其执行。可读性好有助于用户对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。 (3)健壮性(robustness) 当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

(4)效率与低存储量需求 效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间 考点2 算法的复杂度

1算法的时间复杂度 算法的时间复杂度，是指执行算法所需要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，

可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模(通常用整数n表示)，它是问题的规模函数。即

算法的工作量=f(n)

例如，在N×N矩阵相乘的算法中，整个算法的执行时间与该基本操作(乘法)重复执行的次数n3成正比，也就是时间复杂度为n3，即

f(n)=O(n3)

在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时，基本操作的执行次数为氏当初始序列为自大至小有序时，基本操作的执行次数为n(n- 1)/2。对这类算法的分析，可以采用以下两种方法来分析。 (1)平均性态(Average Behavior)

所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为

其中Dn表示当规模为n时，算法执行的所有可能输入的集合。 (2)最坏情况复杂性(Worst-case Complexity)

所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。 2算法的空间复杂度

算法的空间复杂度是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。 考点3 数据结构的定义

数据结构(data structure)是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：

(l)数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；

(2)在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

(3)对各种数据结构进行的运算。

讨论以上问题的日的是为了提高数据处理的效率，所谓提高数据处理的效率有两个方面：

(l)提高数据处理的速度；

(2)尽量节省在数据处理过程中所占用的计算机存储空间。

数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(data element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象(data object)：是性质相同的数据元素的集合，是数据的一个子集。 在一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系(即连续)，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通

常把数据元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描述。

前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。 1数据的逻辑结构

数据结构是指反映数据元素之间的关系的数据元素集合的表示。更通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。 一个数据结构应包含以下两方面信息： (1)表示数据元素的信息；

(2)表示各数据元素之间的前后件关系。

数据的逻辑结果是对数据元素之间的逻辑关系的描述。它可以用一嘎数据元素的集合和定义在此集合中的若干关系来表示。

数据的逻辑结构包括集合、线性结构、树型结构和图形结构四种。 线性结构:数据元素之间构成一种顺序的线性关系。 树型结构：数据元素之间形成一种树型的关系

数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D; 二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成B=（C,R） 其中B表示数据结构。为了反映D中各元素之间的前后件关系，一般用二元组来表示。 例如，复数是一种数据结构，在计算机科学中，复数可取如下定义： B=（C,R）

其中，C是含有两个实数的集合｛c1,c2｝;R是定义在集合C上的一种关系{}，其中有序偶{}表示c1是复数的实部，c2是复数的虚部。 2数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式，称为数据的存储结构（也称为数据的物理结构）。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的结构有顺序、链接、索引等存储结构而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理是，选择合适的存储结构是很重要的。 考点4 数据结构的图形表示

数据结构除了用二元关系表示外，还可以直观地用图形表示。

在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。

在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点(也称为叶子结点)。

一个数据结构中的结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点(称为插入运算)，也可以删除数据结构中的某个结点(称为删除运算)。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。 考点5 线性结构与非线性结构

如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。 非空数据结构满足：

(l)有且只有一个根结点；

(2)每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。线性结构又称为线性表。一个线性表是n个数据元 素的有限序列。至于每个元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。如果一个数据结构不是线性结构，称之为非线性结构。线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。 1.3 线性表及顺序存储结构 考点6 线性表的定义

线性表是n(n≥0)个元素构成的有限序列(a1，a2，?，an)。表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表是一个空表，或可以表示为 (a1，a2，?，an)

其中ai(i=1，2，?，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。 其中，每个元素可以简单到是一个字母或是一个数据，也可能是比较复杂的由多个数据项组成的。在复杂的线性表中，由若干数据项组成的数据元素称为记录(record)，而由多个记录构成的线性表又称为文件(file)。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。非空线性表有如下一些结构特征： (1)有且只有一个根结点a1，它无前件； (2)有且只有一个终端结点an，它无后件；

(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。 考点7 线性表的顺序存储结构

线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构具备如下两个基本特征： (l)线性表中的所有元素所占的存储空间是连续的；

(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

假设线性表的每个元素需要占用k个存储单元，并以所占的存储位置ADR(ai+1)和第i个数据元素的存储位置ADR(ai)之间满足下列关系： ADR(ai+1)=ADR(ai)+k

线性表第i个元素ai的存储位置为 ADR(ai)=ADR(a1)+(i-1)×k

式中ADR(ai)是线性表的第一个数据元素a，的存储位置，通常称做线性表的起始位置或基址。

线性表的这种表示称做线性表的顺序存储结构或顺序映像，这种存储结构的线性表为顺序表。表中每一个元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比例的常数。如图1-4所示。由此只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进

行各种运算，特别是插入运算。在线性表的顺序存储结构下，可以对线性表做以下运算： (l)在线性表的指定位置处加入一个新的元素(即线性表的插入)； (2)在线性表中删除指定的元素(即线性表的删除)；

(3)在线性表中查找某个(或某些)特定的元素(即线性表的查找)； (4)对线性表中的元素进行整序(即线性表的排序)；

(5)按要求将一个线性表分解成多个线性表(即线性表的分解)； (6)按要求将多个线性表合并成一个线性表(即线性表的合并)； (7)复制一个线性表(即线性表的复制)； (8)逆转一个线性表(即线性表的逆转)等。

考点8 顺序表的插入运算

线性表的插入运算是指在表的第i(1≤i≤n+l)个位置上，插入一个新结点x，使长度为n的线性表

(a1，?，ai-1，ai，?，an) 变成长度为n+1的线性表

(a1，?，ai-1，x，ai，?，an)

现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环结点后移语句上，该语句的执行次数(即移动结点的次数)是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。

当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O(1)；

当i=1时，结点后移语句，将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O(n)。

由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。 在长度为n的线性表中第i个位置上插入一个结点，令Eis ( n )表示移动结点的期望值(即移动的平均次数)，则在第i个位置上插入一个结点的移动次数为n-i+1。故 不失一般性，假设在表中任何位置(1≤i≤n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=pn+1=1/(n+1) 因此，在等概率插入的情况下，

也就是说，在顺序表上做插入运算，平均要移动表上一半的结点。当表长n较大时，算法的效率相当低。虽然Eis ( n )中n的的系数较小，但就数量级而言，它仍然是线性级的。因此算法的平均时间复杂度为O(n)。 考点9 顺序表的删除运算

线性表的删除运算是指将表的第i(1≤i≤n)个结点删除，使长度为n的线性表： (a1，?，ai-1，ai，ai+1，?，an) 变成长度为n-l的线性表

(a1，?，ai-1，ai+1，?，an)

该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i=1，则前移语句将循环执行n一1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。

删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故

式子中，pi表示删除表中第i个结点的概率。在等概率的假设下， p1=p2=p3=…=pn=1/n 由此可得：

即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。

1.4 栈和队列

考点10 栈及其基本运算 1什么是栈

栈实际也是线性表，只不过是一种特殊的线性表。栈(Stack)是只能在表的一端进行插入和删除运算配线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈(栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。

假设栈S=(al，a2，a3，?，an)，则a1，称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，?，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为先进后出表(FILO，First In Last Out)，或“后进先出”表(LIFO，Last In First Out)，如图1-7所示。

2栈的顺序存储及其运算

(l)入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1)，然后将元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。如图1-8所示。

(2)退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针减一(即t叩减1)。当栈顶指针为。时，说明栈空，不可进行退栈操作。这种情况称为栈的“下溢”错误。 (3)读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。 考点11 队列及其基本运算 1什么是队列

队列(queue)是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)，

当队列中没有元素时称为空队列。在空队列中依次加入元素a1，a2，?，an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1，a2，?，an也就是说队列的修改是依先进先出的原则进行的。因此队列亦称作先进先出(FIFO，First In First Out)的线性表，或后进后出(LILO，Last In Last Out)的线性表。往队列队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算，如图1-10所示。 一个队列币。删除个儿素后的队列间插入元素E后的队列 2循环队列及其运算

在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间

在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

可以将向量空间想象为一个首尾相接的圆环，如图1-12所示，并称这种向量为循环向量，存储在其中的队列称为循环队列( Cireular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界(Queuesize-l)时，其加1操作的结果是指向向量的下界0。

由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。

在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志、，、值的定义如下：当s=0时表示队列空；当s=1时表示队列非空。 (l)入队运算

入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进一(即rear=rear+1)，并当rear=m+l时置rear=1；然后将新元素插入到队尾指针指向的位置。当循环队列非空(s=l)且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。 (2)退队运算

退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针一进一(即from=front +1)，并当front = m+1时，置front=1然后将排头指针指向的元素赋给指定的变量。当循环队列为空(s =0)时，不能进行退队运算，这种情况称为“下溢”。转贴于：计算机二级考试_考试大【责编:daiy 纠错】 1.5 线性链表

考点12 线性单链表的结构及其基本运算 1什么是线性链表

(l)线性表顺序存储的缺点 ①在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。因此采用顺序存储结构进行插入或删除的运算效率很低； ②当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时栈会发生“上溢”错误；

③计算机空间得不到充分利用，并且不便于对存储空间的动态分配。 (2)线性表链式的基本概念 在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。如图1-13所示。 2线性单链表的存储结构

用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后件结点的地址(或位置)信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构，

链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表(Single Linked)。

显然，单链表中每个结点的存储地址是存放在其前驱结点Next域中，而开始结点无前驱，故应设头指针HEAD指向开始结点。同时，由于终端结点无后件，故终端结点的指针域为空，即NULL。

3带链的栈与队列

(1)栈也是线性表，也可以采用链式存储结构。在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈 (2)队列也是线性表，也可以采用链式存储结构， 考点13 线性链表的基本运算

线性链表的运算主要有以下几个：

(l)在线性链表中包含指定元素的结点之前插入一个新元素； (2)在线性链表中删除包含指定元素的结点； (3)将两个线性链表按要求合并成一个线性表； (4)将一个线性链表按要求进行分解； (5)逆转线性链表； (6)复制线性链表； (7)线性链表的排序； (8)线性链表的查找。 1在线性镬表中查找指定元素

在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个结点。

在线性链表中，即使知道被访问结点的序号a，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域Next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。

在链表中，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的其值为x的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值x作比较。 2线性链表的插入

线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。

插入运算是将值为X的新结点插入到表的第i个结点的位置上，即插入到ai-1，与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点，p的指针域指向新结点，新结点的指针域指向结点ai

由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结点的指针即可，从而提高了插入的效率。 3多线性链表的删除

线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。 删除运算是将表的第i个结点删去。因为在单链表中结点a的存储地址是在其直接前趋结点ai-1，的指针域Next中，所以我们必须首先找到ai-1的存储位置p。然后令p->Next指向ai的直接后件结点，即把ai从链上摘下。最后释放结点a的空间。 从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在结点的前一个结点的指针域即可。另外，由于可利用栈是用于收集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将空闲结点送回到可利用栈。 考点14 线性双向链表的结构及其基本运算 1什么是双向链表

在单链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度为O(1)，但无法直接找到它的互接前件；在单循环链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度仍为O(1)，直接找到它的直接前件，时间复杂度为O(n)。有时，希望能快速找到一个结点的直接前件，这时，可以在单链表中的结点中增加一个指针域指向它的直接前件，这样的链表，就称为双向链表(一个结点中含有两个指针)。如果每条链构成一个循环链表，则会得到双向循环链表 2双向链表的基本运算

(l)插入：在HEAD为头指针的双向链表中，在值为Y的结点之后插入值为X的结点，插入结点的指针变化。如图1-20所示(若改为在值为Y的结点之前插入值为X的结点，可以做类似分析)。

(2)删除：在以HEAD为头指针的双向链表中删除值为X的结点，删除算法的指针变化，如图1-21所示。

考点15 循环链表的结构及其基本运算

单链表上的访问是一种顺序访问，从其中的某一个结点出发，可以找到它的直接后件，但无法找到它的直接前件。

在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。

因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存贮空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一个结点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个结点的指针域改为存放链表中头结点(或第一个结点)的地址，就使得整个链表构成一个环，又没有增加额外的存储空间

循环链表具有以下两个特点：

(1)在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点；

(2)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。 在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。

由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表的运算统一。 1.6 树与二叉树 考点16 树的定义

树是由n( n≥0)个结点组成的有限集合。若n =0，称为空树；若n>0，则： (1)有一个特定的称为根(root)的结点。它只有直接后件，但没有直接前件；

(2)除根结点以外的其他结点可以划分为m(m≥0)个互不相交的有限集合T0，T1，?，Tm-1，每个集合Ti(i=0，1，?，m-l)又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件，但可以有0个或多个直接后件。 树型结构具有如下特点：

(1)助每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根；

(2)每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点；

(3)一个结点所拥有的后件个数称为树的结点度； (4)树的最大层次称为树的深度。

在计算机中，可以用树结构来表示算术表达式，用树来表示算术表达式的原则是： (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点；

(2)运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为从左到右)；

(3)运算对象中的单变量均为叶子结点。 树在计算机中通常用多重链表表示。 考点17 二叉树的定义及其基本性质 1什么是二叉树

二叉树(binary tree)是由n(≥0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。 二叉树具有如下两个特点：

(1)非空二叉树只有一个根结点；

(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树(树为无序树)，其子树的顺序不能颠倒，因此，二叉树有5种不同的形态 在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点) 2二叉树的基本性质

性质1：在二叉树的第入层上至多有2k-1个结点(k≥1)。 性质2：深度为m的二叉树至多有2m-1个结点。

深度为m的二叉树的最大的结点数是为二叉树中每层上的最大结点数之和，由性质1得到最大结点数。

性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。 如果叶子结点n0，度为2的结点数为n2，则n0=n2+l。

设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有 N=n0+n1+n (1)

再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设m为二叉树中的分支总数，则有

N=m+1 (2)

又由于二叉树中这m个分支是分别由非叶子结点射出的。其中度为1的每个结点射出1个分支，度为2的每个结点射出2个分支。因此，二叉树中所有度为1与度为2的结点射出的分支总数为n1+2n2 ，而在二叉树中，总的射出分支数应与总的进入分支数相等，即 m=n1+2n2 (3) 将(3)代入(2)式有 N=n1+2n2+1

比较(1)和(4)并化简得

n0=n2+1

性质4：具有n个结点的完全二叉树的深度至少为[log2n]+ 1，其中[log2n]表示log2n的整数部分。

3满二叉树与完全二叉树 (l)满二叉树

满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。深度为k的二叉树具有2k-1个结点。即在满二叉树的第k层上有2k-1个结点。 从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。 (2)完全二叉树

完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 转贴于：计算机二级考试_考试大【责编:daiy 纠错】 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应。

为满二叉树和完全二叉树的结构比较。

从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。完全二叉树除最后一层外每一层的结点数都达到最大值，最后一层只缺少右边的若干结点。

满二叉树也是完全二叉树，反之完全二叉树不一定是满二叉树。 性质5：具有n个结点的完全二叉树深度为[log2n]+ 1或[log2(n+1)]。 性质6：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第[log2n]+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：

(1)如果i=1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点[i/2]； (2)如果2i≤n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i； (3)如果2i+1≤n，则结点i无右孩子；否则，其右孩子是结点2i+1。 4二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。但在二叉树中，由于每一个元素可以有两个后件(两个子结点)，因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。 考点18 二叉树的遍历

所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。

1前序遍历

前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：

若二叉树为空，则执行空操作。否则：①访问根结点；②前序遍历左子树；③前序遍历右子树。

2中序遍历

中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访间根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历描述为：

若二叉树为空，则执行空操作。否则：①中序遍历左子树；②访问根结点；③中序遍历右子树。

3后序遍历

后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历描述为：

若二叉树为空，则执行空操作。否则：①后序遍历左子树；②后序遍历右子树；③访问根结点

第2章 程序设计基础

2．1 程序设计方法与风格

就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。

一般来讲。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要新闻记者和跟踪程序，因此程序设计的风格总体而言应该强调得意和清晰，程序必须是可以理解的。

要形成良好的程序设计风格，主要应注重和考虑下述一些因素。 1、源程序文档化

2、源程序文档化应考虑如下几点： （1） 符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。 （2） 程序注释：下克的注释能够帮助读者理解程序。

（3） 礼堂组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进待技巧使程序层次清晰。

2、数据说明的方法 在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护。一般应注意如下几点：

（1） 数据说明的次序规范化鉴于程序理解、新闻记者和维护的需要，使数据说明次序固定，可以使数据的发生容易查找，也有利于测试、排错和维护。

（2） 说明语句中变量安排有序化。当一个说明语句说明多个变量时，变量按照字母顺序为好。

（3） 使用注释来说明复杂数据的结构。 3、 语句的结构

程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般应注意如下：

（1） 在一行内只写一条语句；

（2） 程序编写应优先考虑清晰性；

（3） 除非对效率有特殊要求，程序编写要做清晰第一，效率第二； （4） 首先要保证程序正确，然后才要求提高速度； （5） 避免使用临时变量而使程序的可读性下降； （6） 避免不必要的转移； （7） 尽可能使用库函数；

（8） 避免采用复杂的条件语句；

（9） 尽量减少使用“否定”条件的条件语句； （10） 数据结构要有利于程序的简化；

（11） 要模块化，使模块功能尽可能单一化；

（12） 利用住处隐蔽，确保每一个模块的独立性； （13） 从数据出发去构造程序；

（14） 不要修补不好的程序，要重新编写； 4、输入和输出

无论是批处理的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应该考虑如下原则：

（1） 对所有的输入数据都要检验数据的合法性； （2） 检查输入项的各种重要组合的合理性；

（3） 输入格式要简单，以使得输入的步骤和操作尽可能简单； （4） 输入数据时，应允许使用自由格式； （5） 应允许缺省值；

（6） 输入一批数据时，最好使用输入结束标志；

（7） 在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中的输入结束时，应在屏幕上给出状态信息。

（8） 当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输入出加注释，并设计输出报表格式。

2．2结构化程序设计

一、结构化程序设计的原则

结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。

1、 自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。

2、 逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化。

3、 模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。

4、 限制使用goto语句 使用goto语句经实验证实：

（1）滥用GOTO语句确实有害，应昼避免；

（2）完全避免使用GOTO语句也并非是个明智的方法，有些地方使用GOTO语句，会使程序流程更清楚、效率更高；

（3）争论的焦点不应该放在是否取消GOTO语句，而应该放在用什么样的程序结构上。 其中最关键的是，肯定以提高程序清晰性为目标的结构化方法。 二、结构化程序的基本结构与特点

1、顺序结构：顺序结构是简单的程序设计，它是最基本、最常用的结构，所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序程序。

2、选择结构：选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。

3、重复结构：重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。分为两类：一是先判断后执行，一是先执行后判断。

优点：一是程序易于理解、使用和维护。二是编程工作的效率，降低软件开发成本。 三、结构化程序设计原则和方法的应用

要注意把握如下要素：

1、 使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。 2、 选用的控制结构只准许有一个入口和一个出口；

3、 程序语句组成容易识别的块，每块只有一个入口和一个出口； 4、 复杂结构应该嵌套的基本控制结构进行组合嵌套来实现； 5、 语言中所没有的控制结构，应该采用前后一致的方法来模拟； 6、 严格控制GOTO语句的使用。其意思是指：

（1） 用一个非结构化的程序设计语言去实现一个结构化的构造； （2） 若不使用GOTO语句会使功能模糊；

（3） 在某种可以改善而不损害程序可读性的情况下。 2．3面向对象的程序设计 一、关于面向对象方法 面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域，也就是说，系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。

优点：1、与人类习惯的思维方法一致 面向对象方法和技术以对象为核心。对象是由数据和容许的操作组成的封装体，与客观实体有直接的关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。

面向对象的设计方法与传统的面向过程的方法有本质不同，这种方法的基本原理是：使用现实世界的概念抽象地思考问题从而自然地解决问题。它强调模拟现实世界中的概念而不强调算法，它鼓励开发者在软件开发的绝大部分过程中都用应用领域的要领去思考。

2、稳定性好 3、可重用性好

软件重用是指在不同的软件开发过程中重复作用相同或相似软件元素的过程。重用是提高软件生产率的最主要的方法。

4、易于开发大型软件产品 5、可维护性好

（1）用面向对象的方法开发的软件稳定性比较好 （2）用面向对象的方法开发的软件比较容易修改； （3）用面向对象的方法开发的软件比较容易理解。 （4）易于测试和调试。

二、面向对象方法的基本概念 1、对象（object）

对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体，也就是说，应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象，它既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界的意义的东西。总之，对象是对问题域中某个实体的抽象，设立某个对象就反映软件系统保存有关它的信息并具有与它进行交互的能力。

面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。

对象可以做的操作表示它的动态行为，在面向对象分析和面向对象设计中，通常把对象的操作也称为方法或服务。

属性即对象所包含的信息，它在设计对象时确定，一般只能通过挂靠对象的操作来改变。 操作描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。操作的过程对外是封闭的，即用户只能看到这一操作实施后的结果。这相当于事先已经设计好的各种过程，只需要调用就可以了，用户不必去关心这一过程是如何编写的。事实上，这个过程已经封装在对象中，用户也看不到。对的这一特性即是对象的封装性。

对象有如下一些基本特点：

（1） 标识惟一性。指对象是可区分的，并且由对象有的内在本质来区分，而不是通过描述来区分。

（2） 分类性。指可以将具有相同属性的操作的对象抽象成类。 （3） 多太性。指同一个操作可以是不同对象的行为。

（4） 封装性。从外面看只能看到对象的外部特性，即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。对象的内部，即处理能力的实行和内部状态，对外是不可见的。从外面不能直接使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能由其自身改变。

（5） 模块独立性好。对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作从模块的独立性考虑，对象内部各种元素彼此结合得很紧密，内聚性强。

2、类（Class）和实例(Instance)

将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。所以，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。

要注意的是，当使用“对象”这个术语时，既可以指一个具体的对象，也可以泛指一般的对象，但是，当使用“实例”这个术语时，必然是指一个具体的对象。

例如：Integer是一个整数类，它描述了所有整数的性质。因此任何整数都是整数类的对象，而一个具体的整数“123”是类Integer的实例。

由类的定义可知，类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。

3、消息（Message）

面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递信息，它请示对象执行某一处理或回答某一要求的信息，它统一了数据流的控制流。消息的使用类似于函数调用，消息中指定了某一个实例，一个操作名和一个参数表（可空）。接收消息的实例执行消息中指定的操作，并将形式参数数与参数表中相应的值结合起来。消息传递过程中，由发送消息的对象（发送对象）的触发操作产生输出结果，作为消息传送至接受消息的对象（接受对象），引发接受消息的对象一系列的操作。所传送的消息实质上是接受对象所具有的操作/方法名称，有时还包括相应参数。

消息中只包含传递者的要求，它告诉接受者需要做哪些处理，但并不指示接受者应该怎样完成这些处理。消息完全由接受者解释，接受者独立决定采用什么方式完成所需的处理，发送者对接受者不起任何控制作用。一个对象能够接受不同形式、不同内容的多个消息；相同形式的消息可以送往不同的对象，不同的对象对于形式相同的消息可以有不同的解释，能够做出不同的反映。一个对象可以同时往多个对象传递信息，两个对象也可以同时向某个对象传递消息。

例如，一个汽车对象具有“行驶”这项操作，那么要让汽车以时速50公里行驶的话，

需传递给汽车对象“行驶”及“时速50公里”的消息。

通常，一个消息由下述三部分组成： （1） 接收消息的对象的名称； （2） 消息标识符（也称为消息名）； （3） 零个或多个参数。 4、继承（Inheritance）

继承是面向对象的方法的一个主要特征。继承是使用己有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。

广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。 面向对象软件技术的许多强有力的功能和突出的优点，都来源于把类组成一个层次结构的系统：一个类的上层可以有父类，下层可以有子类。这种层次结构系统的一个重要性质是继承性，一个类直接继承其父类的描述（数据和操作）或特性，子类自动地共享基类中定义的数据和方法。

继承具有传递性，如果类C继承类B，类B继承类A，则类C继承类A。因此一个类实际上继承了它上层的全部基类的特性，也就是说，属于某类的对象除了具有该类所定义的特性外，还具有该类上层全部基类定义的特性。

继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。多重继承的类可以组合多个父类的性质构成所需要的性质。因此，功能更强，使用更方便；便是，使用多重继承时要注意避免二义性。继承性的优点是，相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余信息，提高软件的可重用性，便于软件个性维护。此外，继承性便利用户在开发新的应用系统时不必完全从零开始，可以继承原有的相似系统的功能或者从类库中选取需要的类，再派生出新的类以实现所需要的功能。

5、多太性（Polymorphism）

对象根据所接受 的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。在面向对象的软件技术中，多态性是指类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。

多态性机制不仅增加了面向对象软件系统的灵活性，进一步减少了信息冗余，而且显著地提高了软件的可重用性和可扩充性。当扩充系统功能增加新的实体类型时，只需派生出与新实体类相应的新的子类，完全无需修改原有的程序代码，甚至不需要重新编译原有的程序。利用多态性，用户能够发送一般形式的消息，而将所有的实现细节都留给接受消息的对象。

软件工程(Software Engineering，简称为SE)是一门研究用工程化方法构建和维护有效的、实用的和高质量的软件的学科。它涉及到程序设计语言，数据库，软件开发工具，系统平台，标准，设计模式等方面。

在现代社会中，软件应用于多个方面。典型的软件比如有电子邮件，嵌入式系统，人机界面，办公套件，操作系统，编译器，数据库，游戏等。同时，各个行业几乎都有计算机软件的应用，比如工业，农业，银行，航空，政府部门等。这些应用促进了经济和社会的发展，使得人们的工作更加高效，同时提高了生活质量。

软件工程师是对应用软件创造软件的人们的统称，软件工程师按照所处的领域不同可以分为系统分析员，软件设计师，系统架构师，程序员，测试员等等。人们也常常用程序员来泛指各种软件工程师。

软件工程(SoftWare Engineering)的框架可概括为：目标、过程和原则。

(1)软件工程目标：生产具有正确性、可用性以及开销合宜的产品。正确性指软件产品达到预期功能的程度。可用性指软件基本结构、实现及文档为用户可用的程度。开销合宜是指软件开发、运行的整个开销满足用户要求的程度。这些目标的实现不论在理论上还是在实践中均存在很多待解决的问题，它们形成了对过程、过程模型及工程方法选取的约束。

(2)软件工程过程：生产一个最终能满足需求且达到工程目标的软件产品所需要的步骤。软件工程过程主要包括开发过程、运作过程、维护过程。它们覆盖了需求、设计、实现、确认以及维护等活动。需求活动包括问题分析和需求分析。问题分析获取需求定义，又称软件需求规约。需求分析生成功能规约。设计活动一般包括概要设计和详细设计。概要设计建立整个软件系统结构，包括子系统、模块以及相关层次的说明、每一模块的接口定义。详细设计产生程序员可用的模块说明，包括每一模块中数据结构说明及加工描述。实现活动把设计结果转换为可执行的程序代码。确认活动贯穿于整个开发过程，实现完成后的确认，保证最终产品满足用户的要求。维护活动包括使用过程中的扩充、修改与完善。伴随以上过程，还有管理过程、支持过程、培训过程等。

(3)软件工程的原则是指围绕工程设计、工程支持以及工程管理在软件开发过程中必须遵循的原则。

一、软件工程概述

概念：应需而生

软件工程是一类工程。工程是将理论和知识应用于实践的科学。就软件工程而言，它借鉴了传统工程的原则和方法，以求高效地开发高质量软件。其中应用了计算机科学、数学和管理科学。计算机科学和数学用于构造模型与算法，工程科学用于制定规范、设计范型、评估成本及确定权衡，管理科学用于计划、资源、质量和成本的管理。

软件工程这一概念，主要是针对20世纪60年代“软件危机”而提出的。它首次出现在1968年NATO（北大西洋公约组织）会议上。自这一概念提出以来，围绕软件项目，开展了有关开发模型、方法以及支持工具的研究。其主要成果有：提出了瀑布模型，开发了一些结构化程序设计语言（例如PASCAL语言，Ada语言）、结构化方法等。并且围绕项目管理提出了费用估算、文档复审等方法和工具。综观60年代末至80年代初，其主要特征是，前期着重研究系统实现技术，后期开始强调开发管理和软件质量。

70年代初，自“软件工厂”这一概念提出以来，主要围绕软件过程以及软件复用，开展了有关软件生产技术和软件生产管理的研究与实践。其主要成果有：提出了应用广泛的面向对象语言以及相关的面向对象方法，大力开展了计算机辅助软件工程的研究与实践。尤其是近几年来，针对软件复用及软件生产，软件构件技术以及软件质量控制技术、质量保证技术得到了广泛的应用。目前各个软件企业都十分重视资质认证，并想通过这些工作进行企业管理和技术的提升。软件工程所涉及的要素可概括如下：

根据这一框架，可以看出：软件工程涉及了软件工程的目标、软件工程原则和软件工程活动。

目标：我的眼里只有“产品”

软件工程的主要目标是：生产具有正确性、可用性以及开销合宜的产品。正确性意指软件产品达到预期功能的程度。可用性指软件基本结构、实现及文档为用户可用的程度。开销合宜性是指软件开发、运行的整个开销满足用户要求的程度。这些目标的实现不论在理论上还是在实践中均存在很多问题有待解决，它们形成了对过程、过程模型及工程方法选取的约束。

软件工程活动是“生产一个最终满足需求且达到工程目标的软件产品所需要的步骤”。主要包括需求、设计、实现、确认以及支持等活动。需求活动包括问题分析和需求分析。问题分析获取需求定义，又称软件需求规约。需求分析生成功能规约。设计活动一般包括概要设计和详细设计。概要设计建立整个软件体系结构，包括子系统、模块以及相关层次的说明、每一模块接口定义。详细设计产生程序员可用的模块说明，包括每一模块中数据结构说明及加工描述。实现活动把设计结果转换为可执行的程序代码。确认活动贯穿于整个开发过程，实现完成后的确认，保证最终产品满足用户的要求。支持活动包括修改和完善。伴随以上活动，还有管理过程、支持过程、培训过程等。

框架：四项基本原则是基石

软件工程围绕工程设计、工程支持以及工程管理，提出了以下四项基本原则：

第一，选取适宜开发范型。该原则与系统设计有关。在系统设计中，软件需求、硬件需求以及其他因素之间是相互制约、相互影响的，经常需要权衡。因此，必须认识需求定义的易变性，采用适宜的开发范型予以控制，以保证软件产品满足用户的要求。

第二，采用合适的设计方法。在软件设计中，通常要考虑软件的模块化、抽象与信息隐蔽、局部化、一致性以及适应性等特征。合适的设计方法有助于这些特征的实现，以达到软件工程的目标。

第三，提供高质量的工程支持。“工欲善其事，必先利其器”。在软件工程中，软件工具与环境对软件过程的支持颇为重要。软件工程项目的质量与开销直接取决于对软件工程所提供的支撑质量和效用。

第四，重视开发过程的管理。软件工程的管理，直接影响可用资源的有效利用，生产满足目标的软件产品，提高软件组织的生产能力等问题。因此，仅当软件过程得以有效管理时，才能实现有效的软件工程。

这一软件工程框架告诉我们，软件工程的目标是可用性、正确性和合算性；实施一个软件工程要选取适宜的开发范型，要采用合适的设计方法，要提供高质量的工程支撑，要实行开发过程的有效管理；软件工程活动主要包括需求、设计、实现、确认和支持等活动，每一活动可根据特定的软件工程，采用合适的开发范型、设计方法、支持过程以及过程管理。

根据软件工程这一框架，软件工程学科的研究内容主要包括：软件开发范型、软件开发方法、软件过程、软件工具、软件开发环境、计算机辅助软件工程(CASE) 及软件经济学等。

作用：高效开发高质量软件

自从软件工程概念提出以来，经过30多年的研究与实践,虽然“软件危机”没得到彻底解决，但在软件开发方法和技术方面已经有了很大的进步。尤其应该指出的是，自80年代中期，美国工业界和政府部门开始认识到，在软件开发中，最关键的问题是软件开发组织不能很好地定义和管理其软件过程，从而使一些好的开发方法和技术都起不到所期望的作用。也就是说，在没有很好定义和管理软件过程的软件开发中，开发组织不可能在好的软件方法和工具中获益。

根据调查，中国的现状几乎和美国10多年前的情况一样，软件开发过程没有明确规定，文档不完整，也不规范，软件项目的成功往往归功于软件开发组的一些杰出个人或小组的努力。这种依赖于个别人员上的成功并不能为全组织的软件生产率和质量的提高奠定有效的基础，只有通过建立全组织的过程改善，采用严格的软件工程方法和管理，并且坚持不懈地付诸实践，才能取得全组织的软件过程能力的不断提高。

这一事实告诉我们，只有坚持软件工程的四条基本原则，既重视软件技术的应用，又重视软件工程的支持和管理，并在实践中贯彻实施，才能高效地开发出高质量的软件。

二、软件工程的七条基本原理

自从1968年提出“软件工程”这一术语以来，研究软件工程的专家学者们陆续 提出了100多条关于软件工程的准则或信条。 美国著名的软件工程专家 Boehm 综合这些专家的意见，并总结了TRW公司多年的开发软件的经验，于1983年提出了软件工程的七条基本原理。

Boehm 认为，着七条原理是确保软件产品质量和开发效率的原理的最小集合。 它们是相互独立的，是缺一不可的最小集合；同时，它们又是相当完备的。

人们当然不能用数学方法严格证明它们是一个完备的集合，但是可以证明，在此之前已经提出的100多条软件工程准则都可以有这七条原理的任意组合蕴含或派生。

下面简要介绍软件工程的七条原理：

1 用分阶段的生命周期计划严格管理

这一条是吸取前人的教训而提出来的。统计表明，50%以上的失败项目是由于计划不周而造成的。在软件开发与维护的漫长生命周期中，需要完成许多性质各异的工作。这条原理意味着，应该把软件生命周期分成若干阶段，并相应制定出切实可行的计划，然后严格按照计划对软件的开发和维护进行管理。 Boehm 认为，在整个软件生命周期中应指定并严格执行6类计划：项目概要计划、里程碑计划、项目控制计划、产品控制计划、验证计划、运行维护计划。

2 坚持进行阶段评审

统计结果显示： 大部分错误是在编码之前造成的，大约占63%; <2> 错误发现的越晚，改正它要付出的代价就越大，要差2到3个数量级。 因此，软件的质量保证工作不能等到编码结束之后再进行，应坚持进行严格的阶段评审，以便尽早发现错误。

3 实行严格的产品控制

开发人员最痛恨的事情之一就是改动需求。但是实践告诉我们，需求的改动往往是不可避免的。这就要求我们要采用科学的产品控制技术来顺应这种要求。也就是要采用变动控制，又叫基准配置管理。当需求变动时，其它各个阶段的文档或代码随之相应变动，以保证软件的一致性。

4 采纳现代程序设计技术

从六、七时年代的结构化软件开发技术，到最近的面向对象技术，从第一、第二代语言，到第四代语言，人们已经充分认识到：方法大似气力。采用先进的技术即可以提高软件开发的效率，又可以减少软件维护的成本。

5 结果应能清楚地审查

软件是一种看不见、摸不着的逻辑产品。软件开发小组的工作进展情况可见性差，难于评价和管理。为更好地进行管理，应根据软件开发的总目标及完成期限， 尽量明确地规定开发小组的责任和产品标准，从而使所得到的标准能清楚地审查。

6 开发小组的人员应少而精

开发人员的素质和数量是影响软件质量和开发效率的重要因素，应该少而精。 这一条基于两点原因：高素质开发人员的效率比低素质开发人员的效率要高几倍到几十倍，开发工作中犯的错误也要少的多； 当开发小组为N人时，可能的通讯信道为N(N-1)/2, 可见随着人数N的增大，通讯开销将急剧增大。

7 承认不断改进软件工程实践的必要性

遵从上述六条基本原理，就能够较好地实现软件的工程化生产。但是，它们只是对现有的经验的总结和归纳，并不能保证赶上技术不断前进发展的步伐。因此，Boehm提出应把承认不断改进软件工程实践的必要性作为软件工程的第七条原理。根据这条原理，不仅要积极采纳新的软件开发技术，还要注意不断总结经验，收集进度和消耗等数据，进行出错类型和问题报告统计。这些数据既可以用来评估新的 软件技术的效果，也可以用来指明必须着重注意的问题和应该优先进行研究的工具和技术。

面向方面的编程（Aspect Oriented Programming，简称AOP）被认为是近年来软件工程的另外一个重要发展。这里的方面指的是完成一个功能的对象和函数的集合。在这一方面相关的内容有泛型编程（Generic Programming）和模板。

参考

胡崑山，《中国软件产业发展现状与人才需求》，2003年9月1日， http://software.ccidnet.com/pub/article/c372_a62973_p1.html

三、软件工程的目标与常用模型

软件工程的目标是提高软件的质量与生产率，最终实现软件的工业化生产。质量是软件需求方最关心的问题，用户即使不图物美价廉，也要求个货真价实。生产率是软件供应方最关心的问题，老板和员工都想用更少的时间挣更多的钱。质量与生产率之间有着内在的联系，高生产率必须以质量合格为前提。如果质量不合格，对供需双方都是坏事情。从短期效益看，追求高质量会延长软件开发时间并且增大费用，似乎降低了生产率。从长期效益看，高质量将保证软件开发的全过程更加规范流畅，大大降低了软件的维护代价，实质上是提高了生产率，同时可获得很好的信誉。质量与生产率之间不存在根本的对立，好的软件工程方法可以同时提高质量与生产率。

软件供需双方的代表能在餐桌上谈笑风生，归功于第一线开发人员的辛勤工作。质量与生产率的提高就指望程序员与程序经理。对开发人员而言，如果非得在质量与生产率之间分个主次不可，那么应该是质量第一，生产率第二。这是因为：（1）质量直接体现在软件的每段程序中，高质量自然是开发人员的技术追求，也是职业道德的要求。（2）高质量对所有的用户都有价值，而高生产率只对开发方有意义。（3）如果一开始就追求高生产率，容易使人急功近利，留下隐患。宁可进度慢些，也要保证每个环节的质量，以图长远利益。

软件的质量因素很多，如正确性，性能、可靠性、容错性、易用性、灵活性、可扩充性、可理解性、可维护性等等。有些因素相互重叠，有些则相抵触，真要提高质量可不容易啊！

软件工程的主要环节有：人员管理、项目管理、可行性与需求分析、系统设计、程序设计、测试、维护等，如图1.1所示。

软件工程模型建议用一定的流程将各个环节连接起来，并可用规范的方式操作全过程，如同工厂的生产线。常见的软件工程模型有：线性模型（图1.2），渐增式模型（图1.3），螺旋模型，快速原型模型，形式化描述模型等等 [Pressmam 1999, Sommerville 1992]。

最早出现的软件工程模型是线性模型（又称瀑布模型）。线性模型太理想化，太单纯，已不再适合现代的软件开发模式，几乎被业界抛弃。偶而被人提起，都属于被贬对象，未被留一丝惋惜。但我们应该认识到，“线性”是人们最容易掌握并能熟练应用的思想方法。当人们碰到一个复杂的“非线性”问题时，总是千方百计地将其分解或转化为一系列简单的线性问题，然后逐个解决。一个软件系统的整体可能是复杂的，而单个子程序总是简单的，可以用线性的方式来实现，否则干活就太累了。线性是一种简洁，简洁就是美。当我们领会了线性的精神，就不要再呆板地套用线性模型的外表，而应该用活它。例如渐增式模型实质就是分段的线性模型，如图1.3所示。螺旋模型则是接连的弯曲了的线性模型。在其它模型中都能够找到线性模型的影子。

套用固定的模型不是程序员的聪明之举。比如“程序设计”与“测试”之间的关系，习惯上总以为程序设计在先，测试在后，如图1.4（a）所示。而对于一些复杂的程序，将测试分为同步测试与总测试更有效，如图1.4（b）所示。

不论是什么软件工程模型，总是少不了图1.1中的各个环节。本书擗开具体的软件工程模型，顺序讲述人员管理、项目管理、可行性与需求分析、系统设计、程序设计、测试，以及维护与再生工程。其中程序设计部分以C++/C语言为例。

四、软件体系结构和工具的选择

软件体系结构表示了一个软件系统的高层结构，主要特点有：1）软件系统结构是一个高层次上的抽象，它并不涉及具体的系统结构（比如B/S还是C/S），也不关心具体的实现。2）软件体系结构必须支持系统所要求的功能，在设计软件体系结构的时候，必须考虑系统的动态行为。3）在设计软件体系结构的时候，必须考虑有现有系统的兼容性、安全性和可靠性。同时还要考虑系统以后的扩展性和伸缩性。所以有时候必须在多个不同方向的目标中进行决策。

当前已经有一些关于规范化软件体系结构，比如：ISO的开放系统互联模型、X Window系统等等。软件系统的结构通常被定义为两个部分：一个是计算部件。另一个就是部件之间的交互。如果把软件系统看成一幅图的话，计算部件就是其中的节点，而部件之间的交互就是节点之间的弧线。部件之间的连接可以被认为是一种连接器，比如过程调用、事件广播、数据库查询等等。正确的体系结构设计是软件系统成功的关键。

我们理解了软件工程的重要性以后，我们没有相应的工具，我们也很难很好的完成一个系统。在需求分析和设计阶段，我们需要什么样的工具呢？

当然最好是基于UML的CASE工具。当前比较流行的就是Rose，它是一个很好的分析和建立对象和对象关系的工具。在具体编码的时候，我们需要版本控制工具，MS的SourceSafe就是一个很好的版本管理工具和项目管理工具。具体的开发工具当然很多，但是如果你是一个对VC侵淫了多年的程序员，你一定会选择它，因为它会让你感到什么是真正的面向对象的编程，而你在用VB，PowerBuilder，Delphi时很少会有同样的感受。至于数据库模式构建，我一向是采用Sybase的S-Design，更好的工具就不知道了。

另外需要注意的是，我们需要建立文档编写的若干模板，以便开发人员按照这个模板编写规范的技术和说明文档。帮助文档可以用微软的HTML Help Workshop(hhw.exe)制作，你也可以编译成.chm格式，它打包了文本和图形，只有一个文件，使用和分发比较方便。最后，如果开发人员不是集中在一个地方的话，最好建立一个邮件列表，开发人员可以通过邮件系统讨论开发中的各项事宜。

五、软件开发方法综述

国外大的软件公司和机构一直在研究软件开发方法这个概念性的东西，而且也提出了很多实际的开发方法，比如：生命周期法、原型化方法、面向对象方法等等。下面介绍几种流行的开发方法：

1、结构化方法

结构化开发方法是由E.Yourdon 和 L.L.Constantine 提出的，即所谓的SASD 方 法， 也可称为面向功能的软件开发方法或面向数据流的软件开发方法。Yourdon方法是80年代 使用最广泛的软件开发方法。它首先用结构化分析（SA）对软件进行需求分析，然后

用结构化设计（SD）方法进行总体设计，最后是结构化编程（SP）。它给出了两类典型的软件结构（变换型和事务型）使软件开发的成功率大大提高。

2、面向数据结构的软件开发方法

Jackson方法是最典型的面向数据结构的软件开发方法，Jackson方法把问题分解为可由三种基本结构形式表示的各部分的层次结构。三种基本的结构形式就是顺序、选择和重复。三种数据结构可以进行组合，形成复杂的结构体系。这一方法从目标系统的输入、输出数据结构入手，导出程序框架结构，再补充其它细节，就可得到完整的程序结构图。这一方法对输入、输出数据结构明确的中小型系统特别有效，如商业应用中的文件表格处理。该方法也可与其它方法结合，用于模块的详细设计。

3、 面向问题的分析法

PAM（Problem Analysis Method）是80年代末由日立公司提出的一种软件开发方法。 它的基本思想是考虑到输入、输出数据结构，指导系统的分解，在系统分析指导下逐步综 合。这一方法的具体步骤是：从输入、输出数据结构导出基本处理框；分析这些处理框之间的先后关系；按先后关系逐步综合处理框，直到画出整个系统的PAD图。这一方法本质上是综合的自底向上的方法，但在逐步综合之前已进行了有目的的分解，这个目的就是充分考虑系统的输入、输出数据结构。PAM方法的另一个优点是使用PAD图。这是一种二维树形结构图，是到目前为止最好的详细设计表示方法之一。当然由于在输入、输出数据结构与整个系统之间同样存在着鸿沟，这一方法仍只适用于中小型问题。

4、原型化方法

产生原型化方法的原因很多，主要随着我们系统开发经验的增多，我们也发现并非所有的需求都能够预先定义而且反复修改是不可避免的。当然能够采用原型化方法是因为开发工具的快速发展，比如用VB，DELPHI等工具我们可以迅速的开发出一个可以让用户看的见、摸的着的系统框架，这样，对于计算机不是很熟悉的用户就可以根据这个样板提出自己的需求。

开发原型化系统一般由以下几个阶段： （1） 确定用户需求 （2） 开发原始模型

（3） 征求用户对初始原型的改进意见 （4） 修改原型。

原型化开发比较适合于用户需求不清、业务理论不确定、需求经常变化的情况。当系统规模不是很大也不太复杂时采用该方法是比较好的。

5、面向对象的软件开发方法

当前计算机业界最流行的几个单词就是分布式、并行和面向对象这几个术语。由此可以看到面向对象这个概念在当前计算机业界的地位。比如当前流行的两大面向对象技术DCOM和CORBA就是例子。当然我们实际用到的还是面向对象的编程语言，比如C++。

不可否认，面向对象技术是软件技术的一次革命，在软件开发史上具有里程碑的意义。

随着OOP（面向对象编程）向OOD（面向对象设计）和OOA（面向对象分析）的发展，最终形成面向对象的软件开发方法OMT (Object Modeling Technique）。这是一种自底向上和自顶向下相结合的方法，而且它以对象建模为基础，从而不仅考虑了输入、输出数据结构，实际上也包含了所有对象的数据结构。所以OMT彻底实现了PAM没有完全实现的目标。不仅如此，OO技术在需求分析、可维护性和可靠性这三个软件开发的关键环节和质量指标上有了实质性的突破，基本地解决了在这些方面存在的严重问题。

综上所述，面向对象系统采用了自底向上的归纳、自顶向下的分解的方法，它通过对对象模型的建立，能够真正建立基于用户的需求，而且系统的可维护性大大改善。当前业界关于面向对象建模的标准是UML（Unified Modeling Language）。

这里我们需要谈一下微软的MSF（Microsoft Solutions Framework）的框架，它简单的把系统设计分成三个阶段：概念设计、逻辑设计和物理设计。概念设计阶段就是从用户的角度出发可以得到多少个对象，并且以对象为主体，画出业务框架。逻辑设计阶段就是对概念设计阶段的对象进行再分析、细分、整合、删除。并建立各个对象的方法属性以及对象之间的关系。而物理设计实际上就是要确定我们实际需要的组件、服务和采用的框架结构、具体的编程语言等。MCF整个结构比较清楚是基于对象开发的一个比较好的可操作的框架系统。

6、可视化开发方法

其实可视化开发并不能单独的作为一种开发方法，更加贴切的说可以认为它是一种辅助工具，比如用过SYBASE的S-Design的人都知道，用这个工具可以进行显示的图形化的数据库模式的建立，并可以导入到不同的数据库中去。当然用过S-Design的人不一定很多，但用过VB，DELPHI，C++ Builder等开发工具的人一定不少，实际上你就是在使用可视化开发工具。

当然，不可否认的是，你只是在编程这个环节上用了可视化，而不是在系统分析和系统设计这个高层次上用了可视化的方法。实际上，建立系统分析和系统设计的可视化工具是一个很好的卖点，国外有很多工具都致力于这方面产品的设计。比如Business Object就是一个非常好的数据库可视化分析工具。

可视化开发使我们把注意力集中在业务逻辑和业务流程上，用户界面可以用可视化工具方便的构成。通过操作界面元素，诸如菜单、按钮、对话框、编辑框、单选框、复选框、 列表框和滚动条等，由可视开发工具自动生成应用软件。

六、怎样培养软件工程的思维与方法

作为软件开发人员的一个通病是在项目初期的时候，就喜欢谈论实现的细节，并且乐此不疲。我们更喜欢讨论如何用灵活而简短的代码来实现一个特定的功能，而忽略了对整个系统架构的考虑。所以作为一个开发人员，尤其是一个有经验的开发人员，应该把自己从

代码中解脱出来，更多的时候在我们的脑子里甚至暂时要放弃去考虑如何实现的问题，而从项目或产品的总体去考虑一个软件产品。

以下是我个人的一些经验：

1．考虑整个项目或者产品的市场前景。作为一个真正的系统分析人员，不仅要从技术的角度来考虑问题，而且还要从市场的角度去考虑问题。也就是说我们同时需要考虑我们产品的用户群是谁，当我们产品投放到市场上的时候，是否具有生命力。比如即使我们采用最好的技术实现了一个单进程的操作系统，其市场前景也一定是不容乐观的。

2．从用户的角度来考虑问题。比如一些操作对于开发人员来讲是非常显而易见的问题。但是对于一般的用户来说可能就非常难于掌握，也就是说，有时候，我们不得不在灵活性和易用性方面进行折中。另外，在功能实现上，我们也需要进行综合考虑，尽管一些功能十分强大，但是如果用户几乎不怎么使用它的话，就不一定在产品的第一版的时候就推出。从用户的角度考虑，也就是说用户认可的才是好的，并不是开发人员觉的好才好。

3．从技术的角度考虑问题。虽然技术绝对不是唯一重要的，但是技术一定是非常重要的，是成功的必要环节。在产品设计的时候，必须考虑采用先进的技术和先进的体系结构。比如，如果可以采用多线程进行程序中各个部分并行处理的话，就最好采用多线程处理。在Windows下开发的时候，能够把功能封装成一个单独的COM构件就不作成一个简单的DLL或者是以源代码存在的函数库或者是对象。比如能够在B/S结构下运行并且不影响系统功能的话就不一定要在C/S下实现。

4．合理进行模块的分割。从多层模型角度来讲，一般系统可以分成用户层、业务层和数据库层三部分。当然每以部分都还可以进行细分。所以在系统实现设计的时候，尽量进行各个部分的分割并建立各个部分之间进行交互的标准。并且在实际开发的时候，确实有需要的话再进行重新调整。这样就可以保证各个部分齐头并进，开发人员也可以各施其职。

5．人员的组织和调度。这里很重要的一点是到考虑人员的特长，有的人喜欢做界面，有的人喜欢做核心。如果有可能要根据人员的具体的情况进行具体的配置。同时要保证每一个开发人员在开发的时候首先完成需要和其他人员进行交互的部分，并且对自己的项目进度以及其他开发人员的进度有一个清晰的了解，保证不同部分的开发人员能够经常进行交流。

6．开发过程中文档的编写。在开发过程中会碰到各种各样的问题和困难，当然还有各种各样的创意和新的思路。应该把这些东西都记录下来并进行及时整理，对于困难和问题，如果不能短时间解决的，可以考虑采用其他的技术替代，并在事后做专门的研究。对于各种创意，可以根据进度计划安排考虑是在本版本中实现还是在下一版本中实现。

7．充分考虑实施时可能遇到的问题。开发是一回事情，用户真正能够使用好它又是另外一回事情。比如在MIS系统开发中，最简单的一个问题就是用户如果数据输入错误的时候，如何进行操作。在以流程方式工作的时候，如何让用户理解自己在流程中的位置和作用，如何让用户真正利用计算机进行协作也是成败的关键。

以上是我个人的一点体会，实际上，作为一个软件开发人员，我也喜欢看到问题就

坐在计算机前面直接编码，但是我确实认为软件工程对于我们系统开发的指导作用是巨大的。作为软件工程的拥戴者，下面我简单结合自己的开发经历介绍基于软件工程的开发方法、编程规范和工具使用等方面的问题。

七、软件开发的发展变化

国外很多项目的开发都是基于一些图形化的东西来做的，他们的目的是尽量少写代码甚至不写代码。代码能够通过图形化的方式自动生成，这样的一个好处就是如果用户的需求变化或者业务逻辑发生变化，我们需要做的就是对图形表示的调整，然后重新自动生成代码，这也就是国外开发很注重对项目的概念和逻辑分析的原因。

他们的重点是把业务规则和需求用图形化的方式表现出来，然后通过CASE工具自动生成代码。所以当国人还在不停的开发一个又一个的MIS工具的时候，国外已经把很多精力放到了CASE工具的制作上。

我们很多公司人员忙着写具体业务过程的相关代码，而国外很多都把精力放到对不同应用，不同行业的模型的建立和共性的提取上。所以，他们做出来的东西就相对具有很强的灵活性和扩展性，而我们是用户的需求稍微有一点变化，就要忙着改代码，甚至改体系结构。

另外，因为他们注重模型的建立，所以在建立其他应用的时候，能够借鉴原先的模型，在高层次上做调整和优化，同时能够有效的提取原有系统中可以被使用的部分。所以我们应该从以代码为核心的软件开发模式转化到以模型为中心的、基于CASE的开发上来。

关于协作与个人英雄主义

社会进步的一个很明显的现象就是社会分工越来越细，软件的开发也不例外。为什么在软件开发的今天已经不能出现象裘伯君这样的软件英雄的原因也在这里，单凭个人之力，我们也许穷尽有生之年也开发不出象Windows这样的操作系统。

因为，当前软件行业的壁垒无非就是两个，一个就是以技术创新取胜，你模仿的了其中的界面，但是你没有办法实现其中的核心功能。结果是你只能购买其技术核心，而你作一些边角工作。不举别的例子，比如VB这样的开发工具，其核心部分是它和第三方提供的COM控件或者是DLL函数库，你所做的就是一个整合的工作。

第二个就是以细致取胜，也就是说功能很多而且做的很精致，即使技术本身不是很复杂，你真要想做出一个这样的东西来没有一两年的工夫是不可能的。而真等你做出来了，它的新版本也早已经推出。真正能够在市面上叫得想、经得起考验得产品都是具有这两方面的特点。

这两方面的特点决定了你一个人绝对是不可能胜任的，也许你可以独立的完成技术创新，但是你绝对不可能一个人实现所有这些纷繁复杂的功能。所以，这个时代需要创新的英雄，也更需要人与人之间的协作。

当今的软件发展已经不是一个人可以包打天下的年代。软件开发的管理、系统体系结构的设计、模块之间的衔接、核心算法的实现、灵活界面的制定、软件再开发接口的实现都需要专门的人来做。而把这些有效的集成显然就需要有效的利用软件工程的思想和方法。所以，真正的软件英雄绝对不再是写着别人看不懂代码的程序员，而是整个体系结构的分析、设计、标准制定、协调人员。

八、我们是否需要软件工程

有一点大家可以达成共识的就是，如果一个象Windows这样的操作系统，不进行全面的规划，不采用软件工程的思想和方法，是绝对搞不出来的。

Windows的成功不在于它在进程管理和调度，文件系统、内存管理、界面设计等方面有多少成功的创新，它的成功最大的一点就是把所有的技术能够合理的整合起来，并集中到一个Window操作系统特有的框架结构中去。

更为重要的是，Windows的每一项技术创新都能够有效的整合到Windows框架中去，比如COM、XML等技术，通过ActiveX、DCOM等技术使Windows从桌面操作系统发展成为一个基于网络的操作系统。

OLE2技术把整个Office中相关的软件进行了有效的整合，显然，这里我们可以把Office的设计和WPS的设计进行比较，客观的讲，WPS对中国用户来说实在也是一个很好的产品。但是从整个系统设计概念上来讲，Office显然要比WPS高一个层次，它能够把WORD，EXCEL，POWERPOINT，ACCESS有效的整合在一起，使我们所有办公相关的文档、图表、数据库、演示变成了一个一体化的东西。而且通过宏调用，用户可以自己定制用户界面并编制适当的模板，单是这个二次开发功能就不是WPS现在所能及项背的，当然限于当前用户的水平还很少有人使用二次开发的功能。

从微软产品系列可以看到软件工程的作用，微软的所有产品都有一个整体的框架结构，比如Office软件，通过OLE技术进行有效的通讯和联系。比如Visual系列开发工具，提供了相似的开发界面使用户学会一种开发工具以后能够很容易的学习其他的开发工具。比如SQL SERVER和ACCESS，尽管它们适用的范围不同，但是它们表现给用户的界面，特别是在查询和分析上表现了高度的一致性。

更值得一提的是，因为设计结构的合理性，因为在开发前期作了很多分析和调研，考虑了扩展性和伸缩性，微软的系列产品能够很快的利用新的技术并采用统一的结构形式表现出来。比如当网络成为计算机发展的主流的时候，几乎微软所有的工具都能够快速的支持基于网络的开发和应用。

相比之下，我们国内很多公司的产品很少具有连续性，往往是新的一个产品完全重起炉灶，和老的产品没有半点关系。这就是我们在设计产品的时候，没有很好的进行抽象和概念、逻辑设计，造成的结果是从旧的产品中提取不出一些有用的、共性的东西为后来的产品所使用。

当然，很多开发人员从心里也承认一个大的系统确实需要软件工程的依托，但是一个小的工程项目是否就可以仓促上马呢？答案是否定的。所谓麻雀碎小，五脏俱全。无论是大项目、还是小项目。它们作为一个项目，都需要有一个需求分析、系统结构建立、设计、编码、测试等阶段。这是任何一个项目都不可缺少的。

往往可以看到很多大公司的IT部门的人员都在不停的作各种各样的报表，当各个部门提出一种新类型的报表的时候，就从数据库中提取相应的数据并画出业务人员所需要的样式结构，很少是提供了一个通用的模板，当然提供高层API接口进行这种操作的就更少了。这样不可避免的使开发人员陷入一些琐碎的报表编制工作。而造成这个局面的很重要的一个原因就是没有在系统开发的前期进行很好的调研、需求分析和系统体系结构的设计。

这里就我们开发过的一些小型软件项目来谈一些开发的总结和体会，一般来说，小型软件项目功能比较单一，而且模块与模块之间的衔接不是很多，同时对开发周期要求比较短。

小项目虽然看起来比较简单，所以很多开发人员容易犯一些错误，记得我们在开发一个基于Internet的有偿服务系统的时候，有三个开发人员：一个负责前端界面的编写，一个负责数据通讯协议和实现（基于TCP基础上的应用协议），一个负责对数据库数据的查询、整理和提取。我们在开发的时候没有认真地进行项目实际前途和工作量的估计。没有认真地估计项目难度，比如对于通讯中多用户并发访问时的多线程问题和缓存处理问题，用户批量请求处理的实现复杂度问题等等。三个人之间的接口也是在开发中休息的时候，口头定义一下。结果发现有不严密的地方(比如在通讯服务器端是用VC编写的，开发人员是通过stream来传送数据的，客户端是用Delphi编写，在接收数据的时候发现数据不准确，后来研究发现VC利用CSocket在传送数据流的时候对数据进行了自己定义的格式化，结果服务器端数据发送模块只好重写)，而且其中关于一个接口双方的理解不同，然后又返工重新修改。最后到系统基本完成的时候没有一份较正式的文档。然后因为有人毕业离开这个项目，然后他编写的模块需要升级，新的接收的人不得不花很多时间去阅读他的源代码。

所以在开发小项目的时候也必须要建立合理的模式：而所谓合理的模式就是软件工程告诉我们的在开发一个项目的时候所需要的五步曲：获取需求、需求分析、设计、编码、测试。

1．理解用户真正的需求。在进入正式开发之前，必须先从用户处获取准确的需求。在这上面花费相当时间是很必要的。

我们软件项目可以大致分为专用软件和通用软件两大类。对于专用软件，一般用户对于软件要完成哪些功能已经有了一个比较清楚的轮廓，而且往往在开发合同中已经大致地规定了。

但是，开发合同上规定的只是一个大概的框架，在进入开发之前必须与用户进行比较具体的交流和讨论，了解清楚用户心目中的产品究竟是什么样子，这里最好就采用原型化的方法作出一个简单的框架给用户看。

对于通用软件，在开发之前必须做一定的市场调查工作，一方面是从经济效益考虑，

调查产品的潜在市场有多大，一方面是从技术的角度，了解清楚潜在用户对软件的各种技术上的要求，另一方面是确定我们软件的定位，即我们软件具体是为哪一些用户群体服务的。然后对该群体用户现有硬件配置，软件配置，网络使用情况，数据库使用情况，计算机熟悉程度做一定的调研，根据调查的统计结果决定即将开发的软件的一些技术指标。

2．需求分析。需求分析需要做的事情有：高层构思、确立系统目标、划分业务领域、现行业务分析、建立业务模型(Enterprise Model)、信息需求分析、用户视图规范化、数据元素标准化与一致性控制。

在了解用户的需求之后，将需求用一种模型来表示，就是需求分析，一般我们可以面向对象的方法，通过分析用户需求，用类、类之间的各种关系来表示整个系统。

为了讨论软件运行的流程，可以采用UML的Use Case图。在系统分析的时候需要明确应用域（application domain）的范围，然后明确我们系统需要做什么。同时我们需要决定用什么方法来完成需求的获取，这在很大程度上影响了需求分析的做法。

例如可以采用Use Case来表示用户需求，那么从各种序列图中选出相互交互的各个实体，就是一个个类。另外分析需要与设计过程相衔接。分析过程的内容是用对象和对象之间的关系来表示整个系统和系统的流程的，并不设计具体实现，如采用什么编程语言，在什么操作系统平台上运行等等。这些具体实现是在设计阶段来完成的。

面向对象方法的优点是分析、设计、编码过程表示法统一，能比较好的衔接。现在很多CASE工具并不区分分析和设计的阶段。但是，这并不意味着开发就可以对分析和设计不加区分，如何用好辅助设计(case)工具还是开发人员的事情。

3．设计过程。设计阶段的工作包括对分析模型进行必要的修改，同时可能需要对某些类结构做一些修改，确定用户表示层(也就是通俗所说的界面定义)、用户服务层、业务逻辑层、数据库服务层和具体数据库所需要做的工作。同时需要确定使用的体系结构（比如B/S还是C/S）和开发工具（如VB，VC，VI，C++ Builder，DELPHI，PowerBuiler等等）

4．编码。进入编码工作之后，依然可能会发现前面分析或设计阶段的某些错误，这时应返回到前面的阶段进行必要的修改。同时在编码前规定编码的风格并在开发过程中保持一致的风格。

5．测试。测试是系统投入使用前最关键的一个步骤。即使是小项目也应该严格地进行测试。就实际上就是一个把错误留给自己还是留给客户的问题。

最后，我们知道软件项目主要是由开发人员完成的，所以对人员的合理安排和配置也很重要，一般在开发过程中，需要有一位项目负责人，负责分析、设计和协调的工作。另外需要几个程序员完成不同层的代码（比如用户服务层、业务逻辑层、数据库服务层等等）。

同时需要有一个文档整理人员随时整理系统开发过程中相关的文档。如果条件可能的话，要配置一个测试工程师，专门进行代码的测试工作，当然如果条件不允许的话，也可以由开发人员交叉测试。这里需要注意的是，对于项目负责人而言，协调几个人的工作比自

己完成一段编码更重要。

由于协调上出了漏洞，可能导致很大的问题，所以项目负责人必须随时监控各开发人员的工作，包括内容是否与要求发生偏差，进度是否滞后等等。同时必须给每个开发人员明确的任务书。具体开发时每个开发人员必须非常明确自己的任务，这些任务应该采用明确的文档来表示。每个开发人员需要清楚自己所做的工作在整个系统中处于什么地位，这样就有可能会发现设计模型中的漏洞，避免了各人的代码编写完毕之后又要修改的后果。

九、我国软件工程发展的现状

很多国内搞计算机的专家都认为：国内的软件研发过程，个人色彩比较浓。过分地依靠个人无法形成产业规模，而没有规模就谈不上产业化了。

不管怎么样，我们大家还是先要来看一看国内软件厂商到底提供给我们多少有震撼力的软件产品，从技术和利润的角度讲，软件系统最核心的部分还是操作系统、编译系统然后就是开发平台之类的东西，接下来就是一些应用系统，比如图形开发、游戏开发、企业应用、网站建设、杀毒、网络工具等等。

操作系统以中科院为中心，做了一个COSIX，这个本质上是一个UNIX系统，UNIX最初的源代码是公开的，尽管COSIX是一个被称为中国的操作系统并是UNIX系列的（IX就代表UNIX系列），但是其中到底有多少独创的技术成分我们暂时还不知道，但有一点可以肯定，它现在的市场覆盖率绝对不大，而且能否在上面运行各种各样的编译系统、数据库、群件和应用系统可能还需要进一步测试。然后就是对硬件平台的支持也需要进一步完善。

然后就是轰轰烈烈的Linux系统，Linux是遵守GNU标准的操作系统，中国有很多家公司推出了自己的Linux并且还有汉化的Linux，这就有比较疑惑的一点，为什么不在Linux上构架一个类似UNICODE这样的东西，而只做汉化这么本地化的产品呢？不知道是眼光还是市场的问题了。

MIS系统、财务软件是中国软件行业的重头戏，它们彻底的暴露了中国软件开发无序和重复低效劳动的一面。教育软件在某一种层面上看就是电子题库，当然也有优点，比如加入了多媒体教学（可视化程度不错）和所谓寓教于乐的特点，但是从本质上说还是题库。杀毒软件据说是中国软件的骄傲，由中国权威机构评测是达到了世界领先水平，但是好象还没有得到国际权威机构的认可。游戏软件就不用提了，国内业界能够流行的游戏软件成功的秘诀众所周知，不是技术和创意，实在是归功于我们悠久的历史。字处理软件和排版软件客观的说国内的也做的不错，但是从系统的扩展性和体系结构上说和MS和Adobe相比，差距也放在那里。其实这种现状的原因很简单，一个是我们缺少创新的能力，另一个就是我们欠缺软件工程的概念，系统开发前期的需求分析、设计没有做好或者做的不够好。

当然，我们很少怀疑自己的技术能力，我们很多时候认为这是地理环境和经济环境的原因造成了中国软件业现在的局面。当然中国软件开发人员绝对可以算是优秀的，但是想想我们软件行业龙头企业到底有多少有技术创新和专利技术呢？姑且不论这个，实际上把一个操作系统分解开来，比如文件系统、进程管理和调度、IO调度等等，也许我们可以实现其中某一块的内容，但是如何把它们合理的整合起来绝对是一个涉及到软件工程的问题。

作为一个开发人员，我们已经习惯了自己那一套编程模式，而且我们的这种习惯也不自觉的影响着新的开发人员。所以在头脑中建立一个软件工程的作用，从某种角度上讲，要比会几种开发语言、几个编程技巧实在是重要的多。

举一个例子来说，我们也许可以写MFC中的几个类或者是用自己的类扩展MFC，但是我们又有几个人真正去认真分析和考虑MFC架构的设计和原理呢？扪心自问，我们又有多少人能够设计出MFC这样的框架系统呢？下面就我们的题目谈一些相关的话题。

十、我有一个梦

毋庸质疑的是，计算机的发展和人类的历史相比甚至和其他很多科技产品相比都是非常短的，从第一台计算机的研制成功到现在也没有百年的历史，但是计算机及其相关技术的发展却绝对可以说是最快的。抛开硬件的发展（硬件的发展基本上是按照摩尔定律来的，每18个月，机器的速度性能都要提高一倍），单从软件的发展来说，从体系结构来讲，我们经历了从主机结构到文件服务器结构，从客户服务器系统到基于Internet的服务器浏览器结构的体系结构的变化。从编码的角度来讲，我们经历了从最开始的机器代码到汇编代码，从高级程序语言到人工智能语言，从专用的程序设计语言到通用的程序设计语言。从开发工具来讲，我们经历了从分离的开发工具（有代码编辑器，中间代码生成器和连接器）到集成的开发系统，从最简单的单行命令式调试器到方便灵活的多功能的调试器。

但是，今天所有的软件厂商和软件开发人员依然会想起当年的黑人人权运动领袖马丁？路德？金曾经说过的一句名言我有一个梦想。是的，所有的开发人员依然怀着梦想，希望能够有一个万能的系统开发的框架和方法，只要我们沿着这个框架，我们将能开发出适合所有领域的应用系统，于是，我们在念书的时候把这个希望投到了一门课上，这么课就是软件工程。但是当我们在学完这门课的时候，我们依然没有找到这么一个框架甚至连接近这么一个框架的东西也没有碰到。

不管我们认为软件工程可能是多么的虚无，但是所有学工科并且有逻辑头脑的人都坚信理论对实践的指导意义，因为有了爱因斯坦及其许多伟大的科学家关于能量和质量方面的理论以后，我们才造出了原子弹。但是，遗憾的是软件工程并不是一个具体的理论，它更象一门抽象的科学。软件工程是一种方法论，而不是一种具体的摸的着，看的见的产品。它告诉我们在设计一个系统的时候，我们需要进行可行性研究、计划制订、需求分析、系统设计、编码、测试、维护等等。并且对这些过程中应该做什么提出了一个指导性的东西。但是没有任何专家和标准委员会保证只要按照这些标准，我们的系统肯定会顺利完成。而且事实上，软件开发针对的领域是如此之多并不没有一种对所有领域适用的万能框架。

不管认为软件工程已经到了非常成熟的阶段还是认为软件工程依然是一个搞不懂的黑箱子，软件工程确实已经经历了三个不同的阶段。第一个阶段是软件结构化生产阶段，以结构化分析与设计、结构化评审、结构化程序设计以及结构化测试为特征。从80年代中期，软件生产开始进入以过程为中心的第二阶段，以提出过程成熟模型CMM、个体软件过程PSP和群组软件过程TSP为标志。第三个阶段就是以软件过程、面向对象和构件重用三把斧头出现的软件工业化生产阶段。

言归正传，我们还是回到我们的文章标题上来，我们在开发的时候是兵马未动、粮草先行还是摸着石子过河。兵马未动、粮草先行当然意味着我们在开发的时候先不忙着编写

代码做程序，我们先要制订一个关于开发的方法。这点就象元数据（metadata）的概念，元数据并不定义数据，它是对数据的说明，也就是通常所说的关于数据的数据。我们设计的时候也是这样，定义开发的标准，如何进行开发、怎样开发。摸着石子过河就意味着我们先不管什么理论，方法，科学的问题，我们先动手做起来，如果做的也算成功的话，那就可以按照这种模式来，实际上，在任何事情的最初，我们都是这样。从辨证唯物主义者的观点来说，就是从实践中来，然后升华到理论，再用理论来指导实践。记得一个笑话说：外国人搞软件工程是在一个黑屋子里面抓黑猫，不过到现在还是没有抓住，而中国人是在一个黑屋子里面，而里面连猫都没有，然后有人说，我已经抓到猫了。这个笑话一方面是说明直到现在，软件工程还是一个在继续探索、发展的过程，另一个侧面也说明中国搞软件工程摸不着边的局面。

实际上，不管有没有软件工程，不管是否存在一个万能的框架系统，我们的应用系统还是要做，各种各样的软件还是要开发。说到底，软件系统是因为有需求才存在的。有了应用域才有了软件存在的意义。很多时候，我们可以看到国外有各种各样的软件和创新，而我们没有，我们更多的是模仿和一些重复的功能相近的软件的原因就是因为我们没有这方面的需求，这也正解释了为什么ERP系统能在国外开展的很好，而在国内失败多于成功的原因。一方面当然是因为我们的企业按照市场经济发展的时间还不长，另一方面是我们的企业确实也没有这方面的需求。

十一、软件工程的发展方向

“敏捷开发”（Agile Development）被认为是软件工程的一个重要的发展。它强调软件开发应当是能够对未来可能出现的变化和不确定性作出全面反应的。

敏捷开发被认为是一种“轻量级”的方法。在轻量级方法中最负盛名的应该是“极限编程”（Extreme Programming，简称为XP）。而与轻量级方法相对应的是“重量级方法”的存在。重量级方法强调以开发过程为中心，而不是以人为中心。重量级方法的例子比如CMM/PSP/TSP。

．1 数据库系统的基本概念

数据：实际上就是描述事物的符号记录。

数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。而数据的值给出了符合定型的值，如整型值15。

数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。

数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。

数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。

数据库管理系统功能：

（1）数据模式定义：即为数据库构建其数据框架； （2）数据存取的物理构建：为数据模式的物理存取与构建提供有效的存取方法与手段； （3）数据操纵：为用户使用数据库的数据提供方便，如查询、插入、修改、删除等以及简单的算术运算及统计；

（4）数据的完整性、安生性定义与检查；

（5）数据库的并发控制与故障恢复；

（6）数据的服务：如拷贝、转存、重组、性能监测、分析等。 为完成以上六个功能，数据库管理系统提供以下的数据语言：

（1）数据定义语言：负责数据的模式定义与数据的物理存取构建； （2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；

（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。

数据语言按其使用方式具有两种结构形式：交互式命令(又称自含型或自主型语言)宿主型语言（一般可嵌入某些宿主语言中）。

数据库管理员：对数据库进行规划、设计、维护、监视等的专业管理人员。 数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。

数据库应用系统：由数据库系统、应用软件及应用界面三者组成。

文件系统阶段：提供了简单的数据共享与数据管理能力，但是它无法提供完整的、统一的、管理和数据共享的能力。

层次数据库与网状数据库系统阶段 ：为统一与共享数据提供了有力支撑。 关系数据库系统阶段 数据库系统的基本特点：数据的集成性 、数据的高共享性与低冗余性 、数据独立性（物理独立性与逻辑独立性）、数据统一管理与控制。

数据库系统的三级模式：

（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图； （2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；

（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。 数据库系统的两级映射：

（1）概念模式到内模式的映射； （2）外模式到概念模式的映射。 4.2 数据模型

数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。

E-R模型的基本概念

（1）实体：现实世界中的事物； （2）属性：事物的特性；

（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。

E-R模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。

E-R模型的图示法：（1）实体集表示法； （2）属性表法； （3）联系表示法。 层次模型的基本结构是树形结构，具有以下特点： （1）每棵树有且仅有一个无双亲结点，称为根； （2）树中除根外所有结点有且仅有一个双亲。

从图论上看，网状模型是一个不加任何条件限制的无向图。

关系模型采用二维表来表示，简称表，由表框架及表的元组组成。一个二维表就是一个

关系。

在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。

关系中的数据约束：

（1）实体完整性约束：约束关系的主键中属性值不能为空值； （2）参照完全性约束：是关系之间的基本约束；

（3）用户定义的完整性约束：它反映了具体应用中数据的语义要求。 4.3关系代数

关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算。

关系模型的基本运算：

（1）插入 （2）删除 (3)修改 （4）查询（包括投影、选择、笛卡尔积运算） 4.4 数据库设计与管理

数据库设计是数据应用的核心。 数据库设计的两种方法：

（1）面向数据：以信息需求为主，兼顾处理需求； （2）面向过程：以处理需求为主，兼顾信息需求。

数据库的生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。

需求分析常用结构析方法和面向对象的方法。结构化分析（简称SA）方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。对数据库设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果。

数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流（可以是数据项，也可以是数据结构）、数据存储、处理过程。

数据库概念设计的目的是分析数据内在语义关系。设计的方法有两种 （1）集中式模式设计法（适用于小型或并不复杂的单位或部门）； （2）视图集成设计法。

设计方法：E-R模型与视图集成。

视图设计一般有三种设计次序：自顶向下、由底向上、由内向外。 视图集成的几种冲突：命名冲突、概念冲突、域冲突、约束冲突。 关系视图设计：关系视图的设计又称外模式设计。 关系视图的主要作用：

（1）提供数据逻辑独立性；

（2）能适应用户对数据的不同需求； （3）有一定数据保密功能。

数据库的物理设计主要目标是对数据内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。

数据库管理的内容： （1）数据库的建立； （2）数据库的调整； （3）数据库的重组；

（4）数据库安全性与完整性控制；

（5）数据库的故障恢复； （6）数据库监控。

本文来源：https://www.bwwdw.com/article/upvw.html