国二c语言公共基础知识

《国二c语言公共基础知识》由会员分享，可在线阅读，更多相关《国二c语言公共基础知识（128页珍藏版）》请在金锄头文库上搜索。

1、公共基础知识第1章数据结构与算法1 .1 算法1.1.1 算法的基本概念算法是指对解题方案的准确而完整的描述。简单地说，就是解决问题的操作步骤。值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时, 往往先设计算法, 用某种表达方式( 如流程图) 描述, 然后再用具体的程序设计语言描述此算法( 即编程) 。在编程时由于要受到计算机系统运行环境的限制，因此， 程序的编制通常不可能优于算法的设计。1.1.1.1 算法的基本特征一般来说，一个算法应具有以下4个基本特征。( 1 ) 可 行 性(Effectiveness)：算法在特定的执行环境中执行，应当能够得出满意的结果

2、，即必须有一个或多个输出。( 2 ) 确 定 性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。( 3 ) 有 穷 性 (Finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。（ 4）拥有足够的情报：要使算法有效必需为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。1.1.1.2算法的基本要素通常，一个算法由两种基本要素组成。对数据对象的运算和操作；算法的控制结构，即运算或操作时间的顺序。（ 1） 算法中对数据的运算和操作在一般的计算机系统中， 基本的运算和操

3、作有以下碘， 如表1-1所示。表1-1 磅基本的运算和操作（ 2） 算法的控制结构运算类型噪作实 例苴术运苴、一、X、+a+b 3 1逻辑运算与或（II 非 （？ ） k 1 | Os l&l关系运篁 bs a=c、数据传输赋值、输入、输出a=0s b=3一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。 算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架， 它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循

4、环3种基本控制结构组合而成。1.1.13算法设计的基本方法虽然设计算法是一件非常困难的工作，但是算法设计也不是无章可循，人们经过实践，总结和积累了许多行之有效的方法。常用的几种算法设计方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。1.1.1.4算法设计的要求通常一个好的算法应达到如下目标：( 1 ) 正 确 性 (Correctness)正确性大体可以分为以下4个层次：程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

5、( 2 ) 可 读 性 (Readability)算法主要是为了方便人的阅读与交流，其次才是其执行。可读性好有助于用户对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。( 3 ) 健 壮 性 (Robustness)当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。(4)效率与低存储量需求效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高； 存储量需求指算法执行过程中所需要的最大存储空间。1.1.2算法的复杂度算法的复杂度是算法效率的度量，是评价算法优劣的重要依据。算法复杂度包括算法的时间复杂度和算法的空间复杂的。1.

6、1.2.1 算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时， 不仅应该与所使用的计算机、 程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是问题规模( 通常用整数n表示) 的函数。即算法的工作量=f (n)例如，在NxN矩阵相乘的算法中，整个算法的执行时间与该基本操作( 乘法) 重复执行的次数r?成正比，也就是时间复杂度为即f (n) =0 (n3)在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数

7、据集不同而不同。 例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时， 基本操作的执行次数为0；当初始序列为自大至小有序时，基本操作的执行次数为n (n -1 ) /2 o 对这类算法，可以采用平均性态和最坏情况复杂性两种方法来分析。1.1.2.2算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。 如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)

8、工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。1 .2 数据结构的基本概念1.2.1 数据结构的定义数据结构是计算机科学与技术领域广泛使用的一个基本术语，用来反映数据的内部构成。 在给出数据结构的定义之前， 我们先弄清楚几个概念。数 据 (d a ta )：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(data element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象(data object)：是性质相同的数据元素的集合，是数据的一个子集。简单

9、地说， 数据结构是指相互关联的数据元素的集合，即数据的组织形式。所谓结构，就是指数据元素之间的前后件关系( 或称直接前驱与直接后继关系) 。例如， 在考虑一日三餐的时间顺序关系时， 早餐 是 午餐” 的前件 （ 或直接前驱），而“ 午餐“ 是“ 早餐” 的 后 件 （ 或直接后继）；同样 ， 午餐 是 晚餐 的前件， 晚餐 是 午餐 的后件。又例如，在考虑学历的顺序关系时，“ 小学“ 是“ 初中” 的前件，而“ 初中” 是小学的后件。同 样 , “ 初中” 是“ 高中 的前件，“ 高中 是初中 的后件。前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。

10、一般来说，数据元素之间的任何关系都可以用前后件关系来描述。数据结构的两个要素数据“ 和 “ 结构” 是紧密联系在一起的，”数据” 是有结构的数据，而不是无关联的、松散的；而“ 结构” 就是数据元素间的关系，是由数据的特性所决定的。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面 ：（ 1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。讨论以上问题的目的是为了提高数据处理的效率，即提高数据处理的速度以及尽量节省在数据处理过程中所占用的计算机存储空间。1.2.1.1

11、数据的逻辑结构由数据结构的定义可知，一个数据结构应包含以下两方面信息:（ 1）表示数据元素的信息；（ 2）表示各数据元素之间的前后件关系。在此定义中，并没有考虑数据元素的存储，所以上述的数据结构实际上是数据的逻辑结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素: 一是数据元素的集合, 通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为Ro 一个数据结构可以表示成B= （ D, R）其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，如果把一日三餐看作一

12、个数据结构，则可表示成B= （ D, R）D= 早餐，午餐，晚餐R=（ 早餐，午餐）， （ 午餐，晚餐）数据的逻辑结构包括线性结构、树型结构图、网状结构图和集合图4种。1.2.1.2数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储 结 构 （ 也称数据的物理结构）。在进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中， 而且各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能不同。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系( 即前后件关系) ，在数据的存储结构中，不仅要存放

13、各数据元素的信息， 还需要存放各数据元素之间的前后件关系的信息。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。1.2.2数据结构的图形表示数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中， 对于数据集合D中的每一个数据元素用中间标有元素值的方框表示， 一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。例如，例如，一日三餐的数据结

14、构可以用如图l-5(a)所示的图形来表示。又例如，军职数据结构可以用如图l-5(b)所示的图形来表示。(a) U . 餐数据结构的图形表示图1-5连长班长排长(b)军职数据结构的图形表示数据结构的图形表示在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点( 也称为叶子结点) 。一个数据结构中的结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（ 称为插入运算），也可以删除数据结构中的某个结点（ 称为删除运算）。插入与删除是对数据结构的两种基本运算。除此之外， 对数据结构的运算还有查找、分类、合并、分解、复制和修改等。1.2.3线性结构与非线性结构

15、如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。 在只有一个数据元素的数据结构中， 删除该数据元素，就得到一个空的数据结构； 在一个空的数据结构中插入一个新的元素后变成非空。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：（ 1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称为线性表。由此可见，在线性结构中，各数据元素之间的前后件关系是很简单的。需要特别说明的是，在一个线性表中插入或删除任何一个结点后还应是线性结构。如果

16、一个数据结构不是线性结构，则称之为非线性结构。在非线性结构中， 各数据元素之间的前后件关系要比线性结构复杂。 链式结构是总常用的非线性结构。线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。1.3线性表及顺序存储结构1.3.1 线性表的定义线性表是一种最简单且最常见的线性数据结构。线性表是n (n 0 )个元素构成的有限序列(aI，a2, an) o表中除了第一个外的每个元素， 有且只有一个前件；除最后一个元素外的每个元素，有且只有一个后件。即线性表要么是一个空表，要么可以表示为(a，aQ其中a.

17、(i=l, 2, . n ) 是属于数据对象的元素，通常也称其为线性表中的一个结点。 同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。每个数据元素的具体含义，在不同情况下各不相同，它可以是一个数或一个字符，也可以是一个具体事物， 甚至其他更复杂的信息。例如，英文字母表(A, B, C, Z)是一个长度为26的线性表，其中每个字母字符就是一个数据元素；线性表中元素的个数n (n 0 )定义为线性表的长度，当n=0时，称为空表。 线性表的长度是可以变的，当向线性表中插入一个元素时，线性表的长度加1 ; 当删除线性表中的一个元素时，线性表的长度减1。1.3.2 线性表的顺序存储结构通常

18、，线性表可以采用顺序存储和链式存储，本小节主要讨论顺序存储结构。线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具备如下两个基本特征:( 1 ) 线性表中的所有元素所占的存储空间是连续的；(2 ) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。用顺序存储结构存储的线性表称为顺序表。在顺序表中，其前、后件两个元素在存储空间中是紧邻的， 且前件元素一定存储在后件元素的前面。如f 度为n的线性表(av a2, a, an) 的顺序存储如图1-6所示。图1 6线性表的顺序存储结构示意图存储地址数据兀素在线性表中的序号内存状态 空间分配 ADR(7|)

19、占K个字W1叫ADRq)+K202占K个字节ADRMhHi/JKi5占K个字节 ADR( 勺 出 火n%占K个字节 在顺序表中， 如果每个元素占有K个存储单元， 则下标为i+1的元素的存储位置与下标为i的元素的存储位置之间，满足下列关系：ADR (aj+1) =ADR (a ) +K通常把顺序表中第1个数据元素的存储地址ADR (a)称为线性表的首地址，线性表中第i个元素ai的存储地址为：ADR (a.) =ADR (a。 + (i-1) K例如，在顺序表中存储数据(14, 23, 25, 78, 15, 68, 27),每个数据元素占有2个存储单元，第1个数据元素14的存储地址是2 0 0

20、,则第3个数据元素25的存储地址是：ADR (a3) =ADR (a。 + (3-1) x2=200+4=204从这种表示方法可以看到，它是用元素在计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。1.3.3顺序表的插入运算顺序表的插入运算是指在表的第i (l i ，3n)变成长度为n+1的顺序表(31， 3jx, ap an)在第i个元素之前插入一个新元素，完成插入操作主要有以下3个步骤。( 1 )把原来第n个结点至第i个结点依次往后移一个元素位置。( 2 )把新结点放在第i个位置上。(3) 修正线性表的结点个数。例如，

21、图l-4(a)表示一个存储空间为1 0 ,长度为7的顺序表。为了在顺序表的第6个元素( 即5 6 )之前插入一个值为27的数据元素,则需将第6个和第7个数据元素依次往后移动一个位置，空出第6个元素的位置，如图L4(a)中箭头所示，然后将新元素27插入到第6个位置。 插入一个新元素后， 顺序表的长度增加1 ,蕊8 ,嫡l-4(b)所示。一般情况下，在第i(lWi。)个元素之前插入一个元素时，需将第i个元素之后( 包括第i个元素)的所有元素向后移动一个位置。再例如，在图14(b)的顺序表的第2个元素之前，再插入一个值为35的新元素，采用同样的步骤：将第2个元素之后的元素( 包括第2个 元 素 )，

22、即第2个元素至第8个元素，共n-i+l=8-2+l = 7个元素向后移动一个位置，然后将新元素插入到第2个位置， 如图l-4(b)中箭头所示。插入后，线性表的长度增加1 , 变成9 , 如图l-7(c)所序号数据元素序号数据元素序号数据兀索(a )插入附线性表=7(b )插入元素27后线性表=8线件表的顺序存储结构插入前后的状况( c )插入元素35后线 性 & 片9顺序表的插入运算，其时间主要花费在结点的移动上，所需移动结点的次数不仅与表的长度有关，而且与插入的位置有关。1.3.4顺序表的删除运算线性表的删除运算是指将表的第i (li a / 8|+1，变成长度为n-1的线性表9 , 3j

23、- i9 3j + i9 ， a i该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若i= n ,则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i= l,则前移语句将循环执行n-1次,需移动表中除开始结点外的所有结点。 这两种情况下算法的时间复杂度分别为0(1 )和O ( n )。顺序表的删除运算是指将表的第i (l i n)个结点删除，使长度为n的顺序表：变成长度为n -l的顺序表(31， . 3j-i， 3|+ i， . an)删除时应将第i+1个元素至第n个元素依次向前移一个元素位置,共移动了n-i个元素，完成删除主要有以下几个步骤。( 1 )把

24、第i个元素之后( 不包含第i个元素) 的n-i个元素依次前移一个位置。(2 )修正顺序表的结点个数。例如，图l-8(a)为一个长度为8的顺序表，将第一个元素45删除的过程如下：从第2个元素35开始直到最后一个元素5 6 ,将其中的每一个元素均依次往前移动一个位置，如图l-8(a)中箭头所示。此时，顺序表的长度减少了1 ,变成了7 ,如图l-8(b)所示。一般情况下，要删除第i (l i n)个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，顺序表的长度减少1。倘若再要删除图l-8(b)中顺序表的第3个元素8 2 ,则采用同样的步骤：从第4个元

25、素开始至最后一个元素5 6 ,将其中的每一个元素均依次往前移动一个位置,的长度减少了 1 , 变成了6,如图l-8 (b)中箭头所示。此时，顺序表如图l-8 (c)所示。显然，如果删除运算在顺序表的末尾进行，即删除第n个元素,则不需要移动顺序表中的元素。如果要删除第1个元素，则需要移动表中所有的元素。在一般情况下，如果删除第i (libottom- (a )带链的栈图 IT9 i (b )带链的队列带链的栈和带链的队列1.5.2线性链表的基本运算对线性链表进行的运算主要包括查找、插入、删除、合并、分解、逆转、复制和排序。1.5.2.1 在线性链表中查找指定元素查找指定元素所处的位置是插入和删除

26、等操作的前提，只有先通过查找定位才能进行元素的插入和删除等进一步的运算。在链表中查找指定元素必须从队头指针出发，沿着指针域Next逐个结点搜索， 直到找到指定元素或链表尾部为止， 而不能像顺序表那样，只要知道了首地址，就可以计算出任意元素的存储地址。因此，线性链表不是随机存储结构。在链表中，如果有指定元素，则扫描到等于该元素值的结点时,停止扫描，返回该结点的位置，因此，如果链表中有多个等于指定元素值的结点， 只返回第一个结点的位置。 如果链表中没有元素的值等于指定元素，则扫描完所有元素后，返回NULL。1.5.2.2 线性链表的插入线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。

27、插入运算是将值为x的新结点插入到表的第i 个结点的位置上， 即插入到aii与ai之间。因此， 我们必须首先找到电的存储位置P ,然后生成一个数据域为X 的新结点* p , 并令结点* P的指针域指向新结点，新结点的指针域指向结点ai。如图1-15所示。图1-15 线性表的插入示意图1.5.2.3线性链表的删除线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点a、 1的指针域Next中， 所以我们必须首先找 到 的 存 储 位 置 p。然后令p-Next指向a的直接后件结点，即把ai从链上摘下。

28、最后释放结点ai的空间。如图1-16所示。图1 -1 6 线性表的删除示意图1.5.3线性双向链表的结构及其基本运算1.5.3.1 什么是双向链表在单链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度为0(1 ) ,但无法直接找到它的直接前件；在单循环链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度仍为0 ( 1 ) , 直接找到它的直接前件，时间复杂度为O ( n ) 。有时，希望能快速找到一个结点的直接前件，这时，可以在单链表中的结点中增加一个指针域指向它的直接前件，这样的链表，就称为双向链表( 一个结点中含有两个指针) 。如果每条链构成一个循环链表，则会得到双向循环链表

29、，如图1-17所示。HEAD _ f - _L 0图1-17 双向链表示意图1.5.3.2 双向链表的基本运算( 1 ) 插入在HEAD为头指针的双向链表中，在值为Y的结点之后插入值为X的结点，插入结点的指针变化，如图1-18所示( 若改为在值为Y的结点之前插入值为X的结点，可以做类似分析) 。图1-18 双向链表的插入( 2 ) 删除在以H EAD为头指针的双向链表中删除值为X的结点，删除算法的指针变化，如图1-19所示。图1-19 双向链表的删除1.5.4循环链表的结构及其基本运算从单链表可知，最后一个结点的指针域为NULL,表示单链表已经结束。 如果将单链表最后一个结点的指针域改为存放链

30、表中头结点 （ 或第一个结点）的地址，就使得整个链表构成一个环，又没有增加额外的存储空间，如图1-20所示。这样的链表称为循环链表。HH & I -I HEA1J 非空循环链表-1 （ b）空健表图1-20 循环链表的逻辑结构对单链表的访问是一种顺序访问， 从其中某一个结点出发，只能找到它的直接后继（ 即后件），但无法找到它的直接前驱（ 即前件），而且对于空表和第一个结点的处理必须单独考虑，空表与非空表的操作不统一。在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。并且，由于表头结点是循环链表所固有的结点，因此，即使在表中没有数据元素的情况下，表中也至少有一

31、个结点存在，从而使空表和非空表的运算统一。1 .6 树与二叉树1.6.1树的定义树 (T re e )是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。由于它呈现与自然界的树类似的结构形式，所以称它为树。树结构在客观世界中是大量存在的。例如，一个家族中的族谱关系：A有后代B, C； B有后代D, E,F; C有 后 代 G； E有后代H, I。则这个家族的成员及血统关系可用图1-24这样一棵倒置的树来描述。图1 -2 4树的示例在树的图形表示中，一般认为在用直线连起来的两端结点中，上端结点是前件，下端结点是后件。这样，表示前后件关系的箭头就可以省略。下面结合图1-24介绍树的相

32、关术语。在树结构中，每一个结点只有一个前件，称为父结点；没有前件的结点只有一个， 称为树的根结点， 简称树的根。 例如， 在图1-24中，结点A是树的根结点。在树结构中，每一个结点可以有多个后件，称为该结点的子结点；没有后件的结点称为叶子结点。 例如， 在图1-24中， 结点D、H、I、F、G均为叶子结点。在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。例如，在图1-24中，根结点A和结点E的度为2 ,结点B的度为3 ,结点C的度为1 ,叶子结点D、H、I、F、G的度为0。所以，该树的度为3。定义一棵树的根结点所在的层次为1 ,其他结点所在的层次等于它的父结点

33、所在的层次加1。树的最大层次称为树的深度。例如，在图1-24中，根结点A在第1层，结点B、C在第2层，结点D、E、F、G在第3层，结点H、I在第4层。该树的深度为4。在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。例如，在图1-24中，结点A有2棵子树，它们分别以B、C为根结点；结点B有3棵子树，它们分别以D、E、F为根结点，其中,以D、F为根结点的子树实际上只有根结点一个结点。 树的叶子结点度为0 ,所以没有子树。1 .6.2二叉树的定义及其基本性质1.6.2.1 二叉树的定义二叉树是由n （ n0）个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子

34、树组成，并且左右子树都是二叉树。 二叉树可以是空集合， 根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。二叉树具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（ 树为无序树），其子理的顺序不能颠倒，因此，二叉树有5种不同的形态，如图1-26所O(a) (b) (c) (d) (e)图1 -2 6二叉树的5种基本形态图l-26(a)表示空二叉树；图l-26(b)是仅有根结点的二叉树，即左子树和右子树都为空二叉树；图

35、1-26是左、右子树均非空的二叉树；图l-26(d)是左子树非空，右子树为空的 二叉树；图l-26(e)是右子树非空，左子树为空的二叉树。在二叉树中，当一个非根结点的结点，既没有右子树，也没有左子树时，该结点即是叶子结点。1.6.2.2二叉树的基本性质二叉树具有以下几个性质：性质1：在二叉树的第k层 上 至 多 有(k“)个结点。性质2：深度为m的二叉树至多有2m-l个结点。深度为m的二叉树表示该二叉树共有m层。根据性质1 , 只要将第1层到第m层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值， 21-1+22-1+.+2m-1=2m-lo性质3：对任何一棵二叉树，度为0的结点(

36、即叶子结点) 总是比度为2的结点多一个。证明：设一棵非空二叉树中有n个结点，叶子结点个数为n。 ，度为1的结点个数为n l , 度为2的结点个数为明。所以：n=n( )+ni+n2(1)在二叉树中，除根结点外，其余每个结点都有且仅有一个前件( 直接前驱) 和一条从其前件结点指向它的边。 假设边的总数为B,则二叉树中总的结点数为：n = B + l(2)由于二叉树中的边都是由度为1和度为2的结点发出的。 所以有:B=rh+n2x2(3)综 合(1 ) 、(2)、 (3)式，可得：n0=n2+l性质4：具有n个结点的完全二叉树的深度至少为 logzn +1,其 中 log2n表示log2n的整数部

37、分。1.6.2.3满二叉树与完全二叉树满二叉树和完全二叉树是两种特殊形态的二叉树。( 1 ) 满二叉树满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树的第k层 上 有 个 结 点 。从上面满二叉树定义可知，必须是二叉树每一层上的结点数都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m1个结点。图1-23是两棵满二叉树。图l-23(a)是深度为3的满二叉树，图l-23(b)是深度为4的满二叉树。图1 2 7满 汉 树在满二叉树中，只有度为2和度为。 的结点，没有度为1的结点。所有度为。 的结点即叶子结点都在同一层，即最后一层。(2)完全二叉树完全二叉树是指除最后一层

38、外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。完全二叉树也可以这样来描述：如果对满二叉树的结点进行连续编号，从根结点开始，对二叉树的结点自上而下，自左至右用自然数进行连续编号，则深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点一一对应时，称之完全二叉树。由完全二叉树可知，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。图l-28 (a)是深度为3的3棵完全二叉树，图l-28 (b)是深度为4的一棵完全二叉树。图I 2 8完全. 义树完全二叉树还具有以下两个性质：性质1：具有n个结点的完全二叉树深度为logzn + lo性

39、质2：如果对一棵有n个结点的完全二叉树的结点按层序编号( 从第1层 到 第 Elog2n +1层，每层从左到右) ， 则对任一结点k(l k l,则该结点的父结点编号为INT (k / 2 )；如果2 k 0 ,则结点k的左子结点编号为2k；否则该结点没有左子结点( 显然也没有右子结点) ；如果2k+K n ,则结点k的右子结点编号为2k+l；否则该结点没有右子结点。1.6.2.4二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由两部分组成：数据域与指针域。 但在二叉树中，由于每一个元素可以有两个后件( 两个子结点) ，因此，用于存储二叉树的存储结点的指

40、针域有两个： 一个用于指向该结点的左子结点的存储地址， 称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。如图1-29所示。左指针域 数据域 右指针域L(/) Data R(i)图 -2 9二叉树的一个存储结点由于二叉树的存储结构中每一个存储结点有两个指针域，因此,二叉树的链式存储结构也称为二叉链表。1.6.3二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下， 根据访问根结点的次序不同，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。1 . 前序遍历前序遍历中 前” 的含义是：访问根

41、结点在访问左子树和访问右子树之前。 即首先访问根结点， 然后遍历左子树， 最后遍历右子树;并且在遍历左子树和右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历可以描述为：若二叉树为空，则执行空操作；否则访问根结点，前序遍历左子树，前序遍历右子树。例如，对图1-30中的二叉树进行前序遍历的结果（ 或称为该二叉树的前序序列）为：A, B, D, H , E, , C, F, Go2 . 中序遍历中序遍历中 中 的含义是：访问根结点在访问左子树和访问右子树两者之间。即首先遍历左子树，然后访问根结点，最后遍历右子树。并且在遍历左子树和右子树时，仍然首先遍历左子树，然后访问根结点，最后

42、遍历右子树。中序遍历可以描述为：若二叉树为空，则执行空操作；否则中序遍历左子树，访问根结点，中序遍历右子树。例如，对图1-30中的二叉树进行中序遍历的结果（ 或称为该二叉树的中序序列）为：H, D, B, E, I, A, C, G, Fo3 .后序遍历后序遍历中 后” 的含义是：访问根结点在访问左子树和访问右子树之后。 即首先遍历左子树， 然后遍历右子树， 最后访问根结点;并且在遍历左子树和右子树时，仍然首先遍历左子树， 然后遍历右子树，最后访问根结点。后序遍历可以描述为：若二叉树为空，则执行空操作；否则后序遍历左子树，后序遍历右子树，访问根结点。例如，对图1-30中的二叉树进行后序遍历的结

43、果（ 或称为该二叉树的后序序列）为：H, D, I, E, B, G, F, C, Ao1 .7查找技术查找就是在某种数据结构中，找出满足指定条件的元素。 查找是插入和删除等运算的基础，是数据处理的重要内容。由于数据结构是算法的基础， 因此， 对于不同的数据结构， 应选用不同的查找算法,以获得更高的查找效率。1.7 .1 顺序查找与二分法查找1.7.1.1 顺序查找顺序查找（ 顺序搜索）是最简单的查找方法，它的基本思想是:从线性表的第一个元素开始， 逐个将线性表中的元素与被查元素进行比较，如果相等，则查找成功，停止查找；若整个线性表扫描完毕， 仍未找到与被查元素相等的元素，则表示线性表中没有要

44、查找的元素，查找失败。在进行顺序查找过程中，如果线性表中的第一个元素就是要查找的元素，则比较次数为1 ; 如果最后一个元素才是要找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素， 大约要与线性表中一半的元素进行比较。由此可以看出，对于大的线性表来说，顺序查找的效率很低。虽然顺序查找的效率不高， 但在下列两种情况下也只能采用顺序查找：（ 1）如果线性表是无序表（ 即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。（ 2）即使是有序线性表，如果采用链式存储结构，也只能

45、用顺序查找。1.7.1.2二分法查找二分法查找也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足两个条件：用顺序存储结构；线性表是有序表。在本书中，为了简化问题，而更方便讨论，“ 有序” 是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。下一节排序中，有序的含义也是如此。对于长度为n的有序线性表， 利用二分法查找元素X的过程如下。将X与线性表的中间项比较：如 果 X的值与中间项的值相等，则查找成功，结束查找；如 果X小于中间项的值， 则在线性表的前半部分以二分法继续查找；如 果X大于中间项的值， 则在线性表的后半部分以二分法继续查找。例如，长度为8的线性表关键码序列

46、为： 5, 12, 26, 29, 37,45, 46, 69 ,被查元素为3 7 ,首先将与线性表的中间项比较，即与第4个数据元素29相比较,37大于中间项29的值， 则在线性表 37,45, 46, 69继续查找；接着与中间项比较，即与第2个元素45相比较，37小于4 5 ,则在线性表 37继续查找， 最后一次比较相等,查找成功。顺序查找法每一次比较，只将查找范围减少1 ,而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。可以证明，对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。1 .8排序技术排序是数据处理的重要内容。

47、所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。 排序的方法有很多， 根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法。1 .8.1 交换类排序法交换类排序法是借助数据元素的“ 交换” 来进行排序的一种方法。 本小节介绍冒泡排序法和快速排序法， 它们都使用交换排序方法。1.8.1.1 冒泡排序法冒泡排序法是最简单的一种交换类排序方法。在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。冒泡排序（BubbleSort）的基本思想就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素有序为止。冒泡排序法的基本过程如下

48、：第一遍，在线性表中，从前往后扫描，如果相邻的两个数据元素，前面的元素大于后面的元素，则将它们交换，并称为消去了一个逆序。在扫描过程中，线性表中最大的元素不断的往后移动，最后，被交换到了表的末端。此时，该元素就已经排好序了。然后对当前还未排好序的范围内的全部结点，从后往前扫描，如果相邻两个数据元素，后面的元素小于前面的元素，则将它们交换，也称为消去了一个逆序。在扫描过程中，最小的元素不断地往前移动，最后，被换到了线性表的第一个位置，则认为该元素已经排好序了。对还未排好序的范围内的全部结点，继续第二遍，第三遍的扫描，这样，未排好序的范围逐渐减小，最后为空，则线性表已经变为有序了。图1-31是一个

49、冒泡排序法的例子。图1-31 if泡排序示例原始序列4 !6-f 5-+ 2 , f 3第一遍（ 从前往后）145-f 236（ 从后往前）1245-3 6第 : 遍 （ 从前往后）124356（ 从后往前）123456最终结果123456在最坏情况下，对长度为n的线性表排序,次数为n （ n-1） /2o冒泡排序需要比较的1.8.1.2快速排序法在冒泡排序中， 一次扫描只能确保最大的元素或最小的元素移到了正确位置，而未排序序列的长度可能只减少了 1。快速排序（ Quicksort）是对冒泡排序方法的一种本质的改进。快速排序的基本思想是：在待排序的n个元素中取一个元素K（ 通常取第一个元素），

50、以元素K作为分割标准，把所有小于K元素的数据元素都移到K前面，把所有大于K元素的数据元素都移到K后面。这样，以K为分界线，把线性表分割为两个子表，这称为一趟排序。然后，对K前后的两个子表分别重复上述过程。继续下去，直到分割的子表的长度为1为止， 这时， 线性表已经是排好序的了。第一趟快速排序的具体做法是：附设两个指针low和h igh ,它们的初值分别指向线性表的第一个元素（K元素）和最后一个元素。首先从high所指的位置向前扫描，找到第一个小于K元素的元素并与K元素互相交换。 然后从low所指位置起向后扫描， 找到第一个大于K元素的数据元素并与K元素交换。重复这两步，直到low=high为止

51、。图1-32是一个快速排序法的例子。(a)第一趟扫描过程初始状态画30 6182 74122649t tlowhighhigh向左扫描网30 6182 74122649第次交换M2630 6182 7412网49t tlowhighlow向右扫描2630 6182 7412向49第次交换后2630 回82 74126149high向左扫描并交换后2630 1282 7445|6149low向右扫描并交换后2630 12园74826149low highhigh向左扫描2630 12|45 74826149(b )各趟排序之后的状态图I 3 2快速排序示例初始状态|453061827412264

52、9第一趟排序后3012 45 74|826149第. 趟排序后咽)2 6 30 45 49|6174|821第二: 超排序后1226304549网7482排序结果1226304549617482快速排序的平均时间效率最佳，为o(nlog2n ) , 最坏情况下,即每次划分，只得到一个子序列，时间效率为O (n2) o1.8.2选择类排序法选择排序的基本思想是通过每一趟从待排序序列中选出值最小的元素， 顺序放在已排好序的有序子表的后面， 直到全部序列满足排序要求为止。1.8.2.1简单选择排序法简单选择排序(Simple Selection Sort)的基本思想是：首先从所有n个待排序的数据元素

53、中选择最小的元素， 将该元素与第1个元素交换，再从剩下的n-l个元素中选出最小的元素与第2个元素交换。重复这样的操作直到所有的元素有序为止。对初始状态为(73, 26, 41, 5, 12, 34) 的序列进行简单选择排序过程如图1-33所示。图中方括号” 内为有序的子表，方括 号 ” 外为无序的子表，每次从无序子表中取出最小的一个元素加入到有序子表的末尾。步骤如下：从这6个元素中选择最小的元素5 ,将5与第1个元素交换，得到有序序列5 ；从剩下的5个元素中挑出最小的元素1 2 ,将12与第2个元素交换,得到有序列E 5, 12 ；从剩下的4个元素中挑出最小的元素2 6 ,将26与第3个元素交

54、换,得到有序序列5, 12, 26 ；依此类推，直到所以的元素都有序地排列到有序的子表中。图1 3 3简单插入排序过程 初始4837659675122649/=23748659675122649片33748659675122649/=43748659675122649/=53748657596122649/=61237486575962649i=71226374865759649/=81226374849657596简单选择排序法在最坏的情况下需要比较n (n-1) /2次。1.8.2.2堆排序法堆排序属于选择类的排序方法。( 1 )堆的定义若有n个元素的序列( % , h2, hn),将元素

55、按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆。( 1)或( 2), 儿 W % i - 1儿其中，i=l, 2, 3, ., n/2o(1 ) 情况称为小根堆，所有结点的值小于或等于左右子结点的值。(2)情况称为大根堆，所有结点的值大于或等于左右子结点的值。本节只讨论大根堆的情况。例如，序 列 (91, 85, 53, 36, 47, 30, 24, 12)是一个堆，则它对应的完全二叉树如图1-36所示。12J图1 -3 6堆顶元素为破大的堆(2)调整建堆在调整建堆的过程中，总是将根结点值与左、右子树的根结点进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换

56、， 这个调整过程从根节点开始一直延伸到所有叶子结点，直到所有子树均为堆为止。(3)堆排序首先将一个无序序列建成堆，然后将堆顶元素与堆中的最后一个元素交换。不考虑已经换到最后的那个元素，将剩下的n-l个元素重新调整为堆，重复执行此操作，直到所有元素有序为止。对于数据元素较少的线性表来说，堆排序的优越性并不明显，但对于大量的数据元素来说，堆排序是很有效的。在最坏情况下，堆排序法需要比较的次数为O (nlogzn)。1.8.3插入类排序法插入排序是每次将一个待排序元素，按其元素值的大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。1.8.3.1简单插入排序法简单插入排序是把n个待

57、排序的元素看成是一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含另外n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n ,而无序表为空，此时排序完成。简单插入排序过程如图1-33所示。 图中方括号” 呐为有序的子表，方括号” 外为无序的子表，每次从无序子表中取出第一个元素插入到有序子表中。图1 - 3 3简单插入排序过程 初始48 376596751226491=237 48659675122649六337 48659675122649i=437 4865967

58、5122649/=537 48657596122649z=612 37486575962649i=712 26374865759649z=812 26374849657596在最好情况下，即初始排序序列就是有序的情况下，简单插入排序的比较次数为n-1次，移动次数为。 次。在最坏情况下，即初始排序序列是逆序的情况下，比较次数为n(n-1) / 2 ,移动次数为n (n-1) / 2 o假设待排序的线性表中的各种排列出现的概率相同，可以证明， 其平均比较次数和平均移动次数都约为r / %因此直接插入排序算法的时间复杂度为O (n2) o在简单插入排序中，每一次比较后最多移掉一个逆序，因此,这种排序

59、方法的效率与冒泡排序法相同。1.8.3.2希尔排序法希尔排序(Shell Sort)又称为“ 缩小增量排序 ，它也是一种插入类排序的方法，但在时间效率上较简单插入排序有较大的改进。希尔排序的基本思想是：先取一个整数( 称为增量)d】V n ,把全部数据元素分成匕个组，所有距离为由倍数的元素放在一组中，组成了一个子序列， 对每个子序列分别进行简单插入排序。 然后取d2Vdi重复上述分组和排序工作；直到4 = 1 ,即所有记录在一组中为止。一方面，简单插入排序在线性表初始状态基本有序时，排序时间较少。另一方面，当n值较小时，n和n差别也较小。希尔排序开始时增量较大，分组较多，每组的数据元素数目较少

60、，故在各组内采用简单插入排序较快，后来增量d逐渐缩小，分组数减少，各组的记录数增多，但由于已经按必1分组排序，线性表比较接近有序状态，所以新的一趟排序过程也较快。可 有各种不同的取法，例如，一般取d1=n/2, cU=di/2。希尔排序的时间效率与所取的增量序列有关， 如果增量序列为:dI=n/2, di+1= d /2 (n为等待排序序列的元素个数) 。则在最坏情况下，希尔排序所需要的比较次数为0 ( r i * )。图1-34为希尔排序过程。初始状态 48 37 64 9 6 75 13 26 50 54 5. 5 L| | | L第趟排序结果 f 2, 5, 5f : 4, 3, 6：

61、空 7d=2 I- I - I -第二趟排序结果第三趟排序结果第四趟排序结果13 5 48 37 26 50 54 64 9 6 7513 5 26 37 48 50 54 64 9 6 755 13 26 37 48 50 54 64 75 9 6图卜3 4 希尔排序过程各种排序方法时间复杂度、空间复杂度对比见表1-2。表1 - 2 各种排序方法时间、空间复杂度对比排序方法时间复杂度空间双朵度度杂性平均情况最坏情况最好情况直接插入排序0( n2)0( n2)0 (n )0 (1 )筒柒宵泡排序0 ( n2)0( nJ)0 ( n)0 (1 )荷解希尔排序O(nkg：n)0( nlogjn)0

62、 (1 )较汉杂快速排序O(nlog：n)0( n2)0(nk)g2n)0(nl(f;:n)较复杂直接送畀排序0 ( n2)0( fl2)0 ( n：)0 (1 )筒笊堆排序O(nlog,n)0( nlog：n)0(nlg：n)0 (1 )较复杂第2章程序设计基础2.1 程序设计方法与风格2.1.1 程序设计经历的阶段程序是计算机的一组指令，是程序设计的最终结果。程序的功能要经过编译和执行才能最终完成。程序设计是指设计、编制、调试程序的方法和过程。与其他方法一样，程序设计也需要一定的方法来指导。需要注意的是，程序设计并不等同于通常意义上的编程。 程序设计有多个步骤组成，编程只是程序设计整个过程

63、中的一小步。程序设计方法所要做的工作是，如何对实际问题进行抽象和分解以及对程序进行组织， 才能使程序的可读性、 稳定性、 可维护性、效率等更好。 程序设计主要经历了结构化设计和面向对象的程序设计阶段。2.1.2良好的编程风格应注意的因素程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思路。良好的程序设计风格可以使程序结构清晰合理，程序代码便于维护，因此，程序设计风格深深地影响着软件的质量和维护。要形成良好的程序设计风格， 主要应注意和考虑下述一些因素。( 1 )源程序的文档化源程序文档化是指在源程序中可包含一些内部文档，以帮助阅读和理解源程序。符号名的命名规则：符号名的命名应具有一定的实

64、际含义，以便理解程序功能。程序注释：在源程序中添加正确的注释可帮助人们理解程序。程序注释可分为序言性注释和功能性注释， 以给出程序的整体说明和程序的主要功能。视觉组织：可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。( 2 )数据说明的方法为使程序中的数据说明易于理解和维护，可采用下列数据说明的风格，见表2-1。表2-1数据说明风格数据说明风格详细说明次序应规范化使数据说明次序固定， 使数据的属性容易查找， 也有利于测试、排错和维护变量安排有序化当多个变量出现在同一个说明语句中时， 变量名应按字母顺序排序， 以便于查找使用注释在定义一个复杂的数据结构时， 应通过注释来说明该数据结构的特点

65、( 3) 语句的结构为使程序更简单易懂，语句构造应该简单直接，应注意如下原则：在一行内只写一条语句；程序编写应优先考虑清晰性；程序编写要做到清晰第一，效率第二；在保证程序正确的基础上再要求提高效率；避免使用临时变量而使程序的可读性下降；避免不必要的转移；尽量使用库函数；避免采用复杂的条件语句；尽量减少使用“ 否定” 条件语句；数据结构要有利于程序的简化；要模块化，使模块功能尽可能单一化；利用信息隐蔽，确保每一个模块的独立性；从数据出发去构造程序；不要修补不好的程序，要重新编写。( 4) 输入输出输入输出方式和风格应尽可能方便用户的使用，应考虑如下原则：（ 1）对所有输入的数据都要检验数据的合法

66、性；（ 2）检查输入项的各种重要组合的合理性；（3）输入格式要简单，使得输入的步骤和操作尽可能简单；（4）输入数据时，应允许使用自由格式；（5）应允许默认值；（6）输入一批数据时，最好使用输入结束标志；（7）在以交互式输入/ 输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性。2.2结构化程序设计由于软件危机的出现，人们开始研究程序设计方法，其中最受关注的是结构化程序设计方法，它引入了工程思想和结构化思想，使大型软件的开发和编制都得到了极大的改善。2.

67、2.1 结构化程序设计的原则结构化程序设计方法的重要原则是自顶向下、逐步求精、 模块化及限制使用got。 语句。（1）自顶向下程序设计时，先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。（ 2）逐步求精对复杂问题，应设计一些子目标做过渡，逐步细化。(3)模块化模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。(4)限制使用goto语句2.2.2结构化程序的基本结构与特点1966年，Boehm和Jacopini证明了程序设计语言仅仅使用顺序、选择和重复三种基本控制结构就足以表达出各种其他形式结构的程序设计方法。 它们的共同特征是： 严格地只有

68、一个入口和一个出口。( 1 )顺序结构顺序结构是指按照程序语句行的先后顺序，自始至终一条语句一条语句地顺序执行， 它是最简单也是最常用的基本结构。 如图2-1所示，虚线框内就是一个顺序结构，在执行A中的运算后，必然执行B中的运算， 然后执行C中的运算， 没有分支， 也没有转移和重复。( 2 )选择结构选择结构又称分支结构，简单选择结构和多分支选择结构都属于这类基本结构， 这种结构可以根据设置的条件， 判断应该选择哪一枝分支来执行相应的语句序列。图2-2虚线框内是一个简单选择结构。根据条件C判断，若成立则执行A中的运算，若不成立则执行B中的运算。图2 I顺序结构(3 )重复结构图2 2筒电选择结

69、构重复结构又称为循环结构, 它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。在程序设计语言中，重复结构对应两类循环语句，对先判断后执行的循环体称为当型循环结构； 对先执行循环体后判断的称为直到型循环结构，如图2-4所示。图2 3两种重复结构总之，遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的优点：程序易于理解、使用和维护；提高了编程工作的效率，降低了软件开发成本。2.2.3结构化程序设计原则和方法的应用基于对结构化程序设计原则、方法以及结构化程序基本构成结构的掌握和了解， 在结构化程序设计的具体实施中， 要注意把握如下要素：使用程序设计语言中的顺序、选择、

70、循环等有限的控制结构表示程序的控制逻辑；选用的控制结构只准许有一个入口和一个出口；程序语句组成容易识别的块，每块只有一个入口和一个出口；复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；语言中所没有的控制结构，应该采用前后一致的方法来模拟；尽量避免GOTO语句的使用。2.3面向对象的程序设计现在，面向对象方法已经发展为主流的软件开发方法。它历经了30多年的研究和发展，已经日益成熟和完善， 应用也越来越深入和广泛。2 .3 .1 面向对象的方法客观世界中任何一个事物都可以被看成是一个对象，面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统， 提倡用人类在现实生活中常用的思维方法来认识

71、、理解和描述客观事物，强调最终建立的系统能够映射问题域，也就是说，系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。从计算机的角度来看，一个对象应该包括两个要素：一是数据;二是需要进行的操作。 对象就是一个包含数据以及与这些数据有关的操作的集合。面向对象就是运用对象、类、继承、封装、消息、结构与连接等面向对象的概念对问题进行分析、 求解的系统开发技术。面向对象有如下主要优点：与人类习惯的思维方法一致。稳定性好。可重用性好。易于开发大型软件产品。可维护性好。2 .3 .2 面向对象方法的基本概念关于面向对象方法，对其概念有许多不同的看法和定义，但是都涵盖对象及对象属性与方法、

72、类、继承、多态性几个基本要素。2.3.2.1 对象对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体，也就是说，应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象。总之， 对象是对问题域中某个实体的抽象。例如，书本、课桌、老师、电脑等都可以看做一个对象。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。客观世界中的实体通常既具有静态的属性， 又具有动态的行为，因此， 面向对象方法学中的对象是由描述该对象属性的数据以及可以对这些数据施加的操作封装在一起构成的统一

73、体。 对象可以执行的操作表示它的动态行为。属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。对象具有如下特点：标识唯一性：指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分；分类性：指可以将具有相同属性和操作的对象抽象成类；多态性：指同一个操作可以是不同对象的行为；封装性： 从外面看只能看到对象的外部特征， 而不知道也无需知道数据的具体结构以及实现操作的算法；模块独立性好： 对象是面向对象的软件的基本模块， 对象内部各种元素彼此结合得很紧密，内聚性强。23.2.2类和实例类是具有共同属

74、性、共同方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质。一个具体对象则是其对应类的一个实例。要注意的是：” 实例” 这个术语，必然是指一个具体的对象。” 对象” 这个术语，则既可以指一个具体的对象，也可以泛指一般的对象 。因此，在使用“ 实例” 这个术语的地方，都可以用“ 对象” 来代替,而使用“ 对象” 这个术语的地方，则不一定能用 实例 来代替。例如，“ 大学生” 是一个大学生类，它描述了所有大学生的性质。因此，任何大学生都是类“ 大学生” 的 一 个 对 象 （ 这里的“ 对象” 不可以用“ 实例” 来代替），而一个具体的大学生” 张三 是类 大学生” 的一个

75、实例。类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。2.3.23消息消息传递是对象间通信的手段，一个对象通过向另一对象发送消息来请求其服务。消息机制统一了数据流和控制流。消息的使用类似于函数调用 。通常一个消息由下述3部分组成：接收消息的对象名称；消 息 选 择 符 （ 也称为消息名）；零个或多个参数。消 息 只 告 诉 接 收 对 象 需 要 完 成 什 么 操 作 ，但 并 不 指 示 怎 样 完 成操 作 。消 息 完 全 由 接 收 者 解 释 ，独 立 决 定 采 用 什 么 方 法 来 完 成 所 需的 操 作 。一 个 对 象 能 够 接 收 不

76、 同 形 式 、不 同 内 容 的 多 个 消 息 ；相同形式的 消 息 可 以 送 往 不 同 的 对 象 ， 不 同 的 对 象 对 于 形 式 相 同 的 消 息 可 以有 不 同 的 解 释 ，能 够 作 出 不 同 的 反 应 。一 个 对 象 可 以 同 时 往 多 个 对象 传 递 消 息 ，两 个 对 象 也 可 以 同 时 向 某 一 个 对 象 传 递 消 息 。消息传递 如 图 2-4所 示 。图2 4消息传递示意图23.2.4继承继 承 是 面 向 对 象 的 一 个 主 要 特 征 。继 承 是 使 用 已 有 的 类 定 义 作为 基 础 建 立 新 类 的 技 术

77、 。已 有 的 类 可 当 作 基 类 来 应 用 ，则 新 类 相 应地 可 当 作 派 生 类 来 引 用 。广 义 地 说 ，继 承 是 指 能 够 直 接 获 得 已 有 的 性 质 和 特 征 ，而不必重 复 定 义 它 们 。例 如 ， 四边形” 类 是 矩 形 ” 类 的 父 类 ， 四边形” 类 可 以 有 “ 顶点坐 标 ” 等 属 性 ，有 ” 移 动 、“ 旋 转 、“ 求 周 长 ” 等 操 作 。而 “ 矩 形 ” 类除了 继 承 ” 四 边 形 ” 类 的 属 性 和 操 作 外 ，还 可 定 义 自 己 的 属 性 和 操 作 ，“ 长 “ 、“ 宽 “ 等 属

78、性 和 “ 求 面 积 ” 等 操 作 。继 承 具 有 传 递 性 ，如 果 类 Z继 承 类 Y , 类 Y继 承 类 X , 则 类 Z继承类X o 因 此 ，一 个 类 实 际 上 继 承 了 它 上 层 的 全 部 基 类 的 特 性 ，也就是说，属于某类的对象除了具有该类定义的特性外， 还具有该类上层全部基类定义的特性。继承分为单继承与多重继承。单继承是指一个类只允许有一个父类， 即类等价为树型结构。 多重继承是指一个类允许有多个父类。多重继承的类可以组合多个父类的性质构成所需要的性质。继承的优点是：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余信息， 提高软件的

79、可重用性，便于软件修改维护。另外，继承性使得用户在开发新的应用系统时不必完全从零开始， 可以继承原有的相似系统的功能或者从类库中选取需要的类，再派生出新的类以实现所需的功能。23.2.5多态性对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性。在面向对象的软件技术中，多态性是指子类对象可以像父类对象那样使用， 同样的消息既可以发送给父类对象也可以发送给子类对象。例如， 在一般类polygon （ 多边形） 中定义了一个方法Show显示自身，但并不确定执行时到底画一个什么图形。特殊类square和类rectangle都继承了polygon类的显示操

80、作，但其实现的结果却不同, 把名为Show的消息发送给一个rectangle类的对象是在屏幕上画矩形，而将同样消息名的消息发送给一个square类的对象则是在屏幕上画一个正方形。如图2-6所示，这就是多态性的表现。多态性机制不仅增强了面向对象软件系统的灵活性，进一步减少了信息冗余，而且显著提高了软件的可重用性和可扩充性。图2 - 6多态性第3章软件工程基础3.1 软件工程基本概念3.1.1 软件的定义与软件特点3.1.1.1 软件的定义计算机软件由两部分组成。一是机器可执行的程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。软件的构成见表3-1。计算机软件是由程序、数据

81、及相关文档构成的完整集合，它与计算机硬件一起组成计算机系统。表3-1计算机软件各组成部分的含义概念含 义软件程序、数据和文档程序软件开发人员依据用户需求开发的， 用某种程序设计语言描述的， 能够在计算机中执行的语句序列数据使程序能够正常操纵信息的数据结构文档与程序开发、维护和使用有关的资料我国国家标准（ 简称国标，GB）中对计算机软件（ Software）完整的定义是： 与计算机系统操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。3.1.1.2软件的特点软件具有如下特点：（ 1）软件是逻辑产品，而不是物理实体，它具有无形性，通过计算机的执行才能体现它的功能和作用；（ 2）没有明

82、显的制作过程，其成本主要体现在软件的开发和研制上，可进行大量的复制；（ 3）软件在使用期间不存在磨损和消耗问题；（4）软件的开发、运行对计算机系统具有依赖性；（5）开发和维护成本高；（6）软件开发涉及诸多社会因素。3.1.1.3软件的分类计算机软件按功能分为系统软件、应用软件、支撑软件（ 或工具软件）。系统软件是管理计算机的资源，提高计算机的使用效率，为用户提供各种服务的软件。例如，操作系统(O S )、数据库管理系统(D B M S)、编译程序、汇编程序和网络软件等。系统软件是最靠近计算机硬件的软件。应用软件为了应用于特定的领域而开发的软件。例如，我们熟悉的Word 2003、Winamp、

83、QQ和Flashget等软件属于应用软件。支撑软件是介于系统软件和应用软件之间，协助用户开发软件的工具型软件， 其中包括帮助程序人员开发和维护软件产品的工具软件，也包括帮助管理人员控制开发进程和项目管理的工具软件。例如，Dephi、PowerBuilder等。3.1.1.4软件的作用软件是用户与硬件之间的接口，是计算机系统的指挥者，是计算机系统结构设计的重要依据。3.1.2软件危机与软件工程3.1.2.1软件产生和发展软件生产的发展经历了程序设计时代、程序系统时代和软件工程时代。( 1 ) 程序设计时代从第一台计算机上的第一个程序的出现到实用的高级程序设计语言出现以前(1945年1956年 )

84、 。程序设计时代的生产方式是个体手工劳动，使用的工具是机器语言、汇编语言，主要通过编程来实现，不重视程序设计方法。(2)程序系统时代从实用的高级程序设计语言出现以后到软件工程出现以前(1956年1968 年 ) 。 程序系统时代的生产方式是作坊式小集团生产，生产工具是高级语言，开始提出结构化方法，但开发技术还没有根本性突破，开发人员素质和开发技术不适应规模大、结构复杂的软件开发，导致了软件危机的产生。(3)软件工程时代软件工程出现以后至今(1968 年一至今) 。软件工程时代的生产方式是工程化生产，使用数据库、开发工具、开发环境、网络等先进的开发技术和方法，使生产效率大大提高， 但未能完全摆脱

85、软件危机。3.1.2.2软件危机随着计算机软件规模的扩大，软件本身的复杂性不断增加，研制周期显著变长，正确性难以保证，软件开发费用上涨，生产效率急剧下降，从而出现了人们难以控制软件发展的局面，即所谓的”软件危机 。软件危机主要表现在：(1)软件需求的增长得不到满足；(2)软件开发成本和进度无法控制；(3)软件质量难以保证；( 4)软件不可维护或维护程度非常低；(5)软件成本不断提高；(6)软件开发生产效率的提高赶不上硬件的发展和应用需求的增长。总之，可以将软件危机归结为成本、质量和生产率等问题。3.1.2.3软件工程的产生为了摆脱软件危机，北大西洋公约组织成员国软件工作者于1968年和1969

86、年两次召开会议(NATO会 议 ) ，认识早期软件开发中所存在的问题和产生问题的原因，提出软件工程的概念。国 标 (GB)中指出软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。自软件工程概念的提出，该研究领域吸引了众多的学者，并开展了大量的理论和技术的研究， 形成了 软件工程学” 这一计算机科学中的分支。它所包含的内容可概括为以下两点：(1)软件开发技术：主要有软件开发方法学、软件工具、软件工程环境；(2)

87、软件工程管理：主要有软件管理、软件工程经济学。3.1.3软件工程过程IS09000定义：软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。软件工程过程包含4种基本活动：( 1 ) 软件规格说明P (P la n )：规定软件的功能及其运行机制；(2 ) 软件开发D (D o )：产生满足规格说明的软件；( 3 ) 软件确认C (Check)：确认软件能够满足客户提出的要求;(4)软件演进A (Action)：为满足客户的变更要求，软件必须在使用的过程中演进。3.1.4软件生命周期( 1 ) 软件生命周期的概念一个软件从定义、开发、使用和维护，直到最终被废弃而退役,要经历一个漫长的时期，

88、 这就如同一个人要经过胎儿、 儿童、 青年、中年和老年，直到最终死亡的漫长时期一样。通常把软件产品从提出、实现、使用、维护到停止使用、退役的过程称为软件生命周期。软件生命周期分为3个时期共8个阶段。软件定义期： 包括问题定义、 可行性研究和需求分析3个阶段;软件开发期： 包括概要设计、 详细设计、 实现和测试4个阶段;运行维护期：即运行维护阶段。软件生命周期各个阶段的活动可以有重复，执行时也可以有迭代，如图3-4所示。(2 ) 软件生命周期各阶段的主要任务在图3-1中的软件生命周期各阶段的主要任务是：问题定义。确定要求解决的问题是什么。可行性研究与计划制定。决定该问题是否存在一个可行的解决办法

89、，指定完成开发任务的实施计划。需求分析。 对待开发软件提出需求进行分析并给出详细定义。编写软件规格说明书及初步的用户手册，提交评审。软件设计。通常又分为概要设计和详细设计两个阶段，给出软件的结构、模块的划分、功能的分配以及处理流程。该阶段提交评审的文档有概要设计说明书、详细设计说明书和测试计划初稿。软件实现。在软件设计的基础上编写程序。该阶段完成的文档有用户手册、操作手册等面向用户的文档，以及为下一步作准备而编写的单元测试计划。软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。运行维护。将已交付的软件投入运行，同时不断地维护，进行必要而且可行的扩充和删改。I何义h软件

90、定义叽m型 珏 求 ? .慨. 设计h软件开发期 11 1细设ilf1q手现运行惟护期 工 叵 遹 可. . . . . . . . . . . . . . . - -: 主| 退 役 |图3 4软件生命周期3.1.5软件工程的目标与原则3.1.5.1 软件工程的目标软件工程的目标是：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程研究的内容主要包括： 软件开发技术和软件工程管理。（1）软件开发技术。软件开发技术包括：软件开发方法学、开发过程、 开发工具和软件工程环境, 其主体内容是软件开发

91、方法学。软件开发方法学是从不同的软件类型，按不同的观点和原则，对软件开发中应遵循的策略、原则、步骤和必须产生的文档资料做出规定， 从而使软件的开发能够规范化和工程化，以克服早期的手工方式生产中的随意性和非规范性。(2)软件工程管理。软件工程管理包括软件管理学、软件工程经济学、软件心理学等内容。 软件工程管理是软件按工程化生产时的重要环节，它要求按照预先制定的计划、进度和预算执行，以实现预期的经济效益和社会效益。工程管理包括人员组织、进度安排、质量保证和成本核算等；软件工程经济学是研究软件开发中对成本的估算、 成本效益分析的方法和技术。 它应用经济学的基本原理来研究软件工程开发中的经济效益问题；

92、软件心理学从个体心理、人类行为、组织行为和企业文化等角度来研究软件管理和软件工程的。3.1.5.2软件工程的原则为了达到上述的软件工程目标，在软件开发过程中，必须遵循以下软件工程的基本原则。( 1 ) 抽象。抽象事物最基本的特性和行为，忽略非本质细节，采用分层次抽象、自顶向下、逐层细化的办法控制软件开发过程的复杂性。(2)信息隐蔽。采用封装技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单。(3)模块化。模块是程序中相对独立的成分，一个独立的编程单位，应有良好的接口定义。模块的大小要适中，模块过大会使模块内部的复杂性增加，不利于模块的理解和修改，也不利于模块的调试和重用； 模块太小会导致整

93、个系统表示过于复杂， 不利于控制系统的复杂性。（ 4）局部化。要求在一个物理模块内集中逻辑上相互关联的计算资源， 保证模块间具有松散的耦合关系， 模块内部有较强的内聚性，这有助于控制系统的复杂性。（ 5）确定性。软件开发过程中所有概念的表达应是确定的、无歧义的且规范的。这有助于人与人的交互，不会产生误解和遗漏，以保证整个开发工作的协调一致。（ 6） 一致性。包括程序、数据和文档的整个软件系统的各模块应使用已知的概念、符号和术语；程序内外部接口应保持一致，系统规格说明与系统行为应保持一致。（ 7）完备性。软件系统不丢失任何重要成分，完全实现系统所需的功能。（ 8 ）可验证性。开发大型软件系统需要

94、对系统自顶向下，逐层分解。系统分解应遵循容易检查、测评、评审的原则，以确保系统的正确性。3.1.6软件开发工具与软件开发环境软件工程技术鼓励研制和采用各种先进的软件开发方法、 工具和环境。 工具和环境的使用进一步提高了软件的开发效率、维护效率和软件质量。（ 1）软件开发工具。软件开发工具是协助开发人员进行软件开发活动所使用的软件或环境，它包括需求分析工具、设计工具、编码工具、排错工具、测试工具等。（ 2）软件开发环境。软件开发环境是指支持软件产品开发的软件系统，它由软件工具集和环境集成机制构成。 工具集包括支持软件开发相关过程、活动、任务的软件工具，以便对软件开发提供全面的支持。 环境集成机制

95、为工具集成和软件开发、维护与管理提供统一的支持， 它通常包括数据集成、控制集成和界面集成3个部分。3.2结构化分析方法目前使用最广泛的软件工程方法学是结构化方法学和面向对象方法学。结构化方法学也称为传统方法学，它采用结构化方法来完成软件开发的各项任务， 并使用适当的软件工具或软件工程环境来支持结构化方法的运用。3.2.1可行性研究可行性研究的目的就是用最小的代价在尽可能短的时间内确定问题是否能够解决。（ 1）经济可行性研究分析系统的估算开发成本是否会超过项目预期的全部利润。分析系统开发对其他产品或利润的影响。（2）技术可行性研究根据客户提出的系统功能、性能及现实系统的各项约束条件，从技术角度研

96、究实现系统可行性。技术可行性研究包括：风险分析、资源分析和技术分析。风险分析的任务是在给定的约束条件下，判断能否设计并实现系统所需功能和性能。资源分析的任务是论证是否具备系统开发所需的各类人员、软件、硬件资源和工作环境等。技术分析的任务是当前的科学技术是否支持系统开发的全过程。（3）法律可行性分析研究在系统开发过程中可能涉及的各种合同、侵权、责任以及同法律相抵触的问题。（4）开发方案的选择性研究提出并评价实现系统的各种开发方案，并从中选出一种最适宜项目的开发方案。3.2.2需求分析方法3.2.2.1需求分析软件需求分析是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。需求分析的任

97、务是发现需求、求精、建模和定义需求的过程。（ 1）需求分析的定义IEEE软件工程标准词汇表对需求分析定义如下：用户解决问题或达到目标所需的条件或权能；系统或系统部件要满足合同、标准、规范或其他正式规定文档所具有的条件或权能；一种反映或所描述的条件或权能的文档说明。（ 2）需求分析阶段的工作需求分析阶段的工作可概括为4个方面：需求获取；需求分析；编写需求规格说明书；需求审评。3.222需求分析的方法( 1 ) 结构化分析方法。 主要包括面向数据流的结构化分析方法、面向数据结构的Jackson系统开发方法和面向数据结构的结构化数据系统开发方法。(2 )面向对象的分析方法。 从需求分析建立的模型的特

98、点来分,需求分析方法分为静态分析方法和动态分析方法。3.2.3结构化分析方法的概念结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用。结构化分析方法(Structure Analysis,简称S A ) 是面向数据流进行需求分析的方法，采用自顶向下、逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。结构化分析方法的步骤如下：( 1 ) 通过对用户的调查，以软件的需求为线索，获得当前系统的具体模型；(2)去掉具体模型中的非本质因素，抽象出当前系统的逻辑模型；(3)根据计算机的特点分析当前系统与目标系统的差别，建立目标系统的逻辑模型；(4)完善目标系统并补充

99、细节，写出目标系统的软件需求规格说明；(5)评审直到确认完全符合用户对软件的需求。3.2.4结构化分析常用工具结构化分析方法利用图形等半形式化的描述方式表达需求，简明易懂， 用它们形成需求说明书中的主要部分。 这种方法所用的常用工具有：数据流图、数据字典、判定树和判定表。3.2.4.1数据流图数据流图(Data Flow Diagram, D FD ), 它以图形的方式描绘数据在系统中流动和处理的过程，它只反映系统必须完成的逻辑功能，所以是一种功能模型。数据流图中的主要图形元素与说明如表3-2所示。表3-2 数据流图的元素说明名 称图 形说 明数据流(data flow )沿箭头方向传送数据的

100、通道， 一般在旁边标注数据流名加工(process )O又称转换， 输入数据经加工、变换产生输出存储文件(file) -又称数据源， 表示处理过程中存放各种数据的文件源 脾 (source/sink )ZZI表示系统和环境的接口， 雇于系统之外的实体绘制数据流图的基本原则如下:(1 )数据流图上所有的基本图形符号一般应是上述的4种基本元素；(2)数据流图的主图必须含有前面所述的4种基本元素， 缺一不可；(3)数据流图的主图上的数据流必须封闭在外部实体之间，实体可以是一个，也可以是多个；(4)变换框至少有一个输入数据流和一个输出数据流；(5)图上的每个元素都必须命名；(6 )任何一个数据流子图必

101、须与它的父图上的一个变换框对应,两者的输入数据流和输出数据流必须一致。3.2.4.2数据字典数据字典(Data Dictionary,DD)是对数据流图中所有元素的定义的集合，是结构化分析的核心。数据流图和数据字典共同构成系统的逻辑模型，没有数据字典数据流图就不严格，若没有数据流图，数据字典也难于发挥作用。数据字典中有4种类型的条目：数据流、数据项、数据存储和加工。在数据字典各条目的定义中，常使用下述符号，如表3-3所示。表3-3 数据字典定义式中出现的符号符 号含 义=表示“ 等价于“ ，定义为或“ 由什么构成“+表示“ 和“ ，与. -I-表示“ 或“ ， 即从方括号内列出的若干项中选择一

102、个， 通常用T号隔开供选择的项 )表示“ 重复即重复花括号内 的 项 ， “m表示最少重复n次 ， 星多重复m次( )表示“ 可选. ， 即圆括号里的项可有可无， 也可理解为可以重复0次或1次*表示“ 注解“表示连接符3.2.43判定树判定树又称决策树，是一种描述加工的图形工具，适合描述问题处理中具有多个判断， 而且每个决策与若干条件有关。 使用判定树进行描述时， 应先从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。3.2.4.4判定表判定表与判定树相似，也是一种描述加工的图形工具。当数据流

103、图中的加工要依赖于多个逻辑条件的取值， 即完成该加工的一组动作是由于某一组条件取值的组合引发的，使用判定表比较适宜。3.2.5结构化方法开发过程结构化方法将软件生命周期分为计划、开发、运行3个时期，每个时期又分若干阶段。( 1 ) 计划期计划期的主要任务是分析新系统应设定的目标，分析用户的基本需求，按设定目标的要求进行问题定义，并分析开发该系统的可行性，用户与分析人员的交互和配合是这一时期的重要特征和要求。问题定义确定软件系统的主要功能。 分析人员在与用户讨论的基础上提出软件系统目标、范围与功能说明。可行性研究对问题定义阶段所确定的问题实现的可能性和必要性进行研究，并讨论问题的解决办法， 对各

104、种可能方案做出必要的成本一效益分析，分析人员据此提出可行性分析报告， 作为使用部门是否继续进行该项工程的依据。(2 ) 开发期开发期包括分析、设计和实施两类任务。其中分析、设计包括需求分析、总体设计和详细设计3个阶段，实施则包括编码和测试两个阶段。需求分析。 确定用户对软件系统的功能性和非功能性的全部需求，并以需求规格说明书的形式表达；总体设计。建立软件系统的总体结构，子系统划分，并提出软件结构图；详细设计。确定软件结构图中每个模块的内部过程和结构；编码。 按照选定软件的程序语言， 将模块的过程性描述翻译成程序；测试。发现并排除上述各阶段所产生的各种错误。(3)运行期运行期的主要任务是软件维护

105、o3.2.6软件需求规格说明书软件需求规格说明书(Software Requirement Specificationy SRS)是需求分析阶段的最后成果，是软件开发的重要文档之一。(1)软件需求规格说明书的作用便于用户、开发人员进行理解和交流。反映出用户问题的结构，可以作为软件开发工作的基础和依据。作为确认测试和验收的依据。(2)软件需求规格说明书的内容软件需求规格说明书是作为需求分析的一部分而制定的可交付文档。该说明书把在软件计划中确定的软件范围加以展开， 制定出完整的信息描述、详细的功能说明、 恰当的检验标准以及其他要求有关的数据。(3)软件需求规格说明书的特点软件需求规格说明书是确保软

106、件质量的有力措施。衡量软件需求规格说明书质量好坏的标准，标准的优先级及标准的内涵如下：正确性：SRS首先要正确地反映待开发系统，体现系统的真实要求。无歧义性：对每一个需求不能有两种解释。完整性：SRS要涵盖用户对系统的所有需求，包括功能要求、性能要求、接口要求、设计约束等。可验证性： SRS描述的每一个需求都可在有限代价的有效过程中验证确认。一致性：各个需求的描述之间不能有逻辑上的冲突。可理解性：为了使用户能看懂SRS,应尽量少使用计算机的概念和术语。可修改性：SRS的结构风格在有需要时不难改变。可追踪性：每个需求的来源和流向是清晰的。作为设计的基础和验收的依据，软件需求规格说明书应该精确而无

107、二义性，并且简单易懂，这样可以方便后面的设计，以及用户看懂说明书，并且发现和指出其中的错误以保证软件系统质量。3.3结构化设计方法3.3.1软件设计的基本概念33.1.1软件设计的基础软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。 软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，也就是说，软件设计是确定系统的物理模型。软件设计的重要性和地位概括为以下几点：（ 1）软件开发阶段（ 设计、编码、测试）占软件项目开发总成本的绝大部分，是在软件开发中形成质量的关键环节；（ 2）软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途

108、径；（ 3）软件设计做出的决策，最终影响软件实现的成败；（ 4）设计是软件工程和软件维护的基础。从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。软件设计的一般过程是：软件设计是一个迭代的过程；先进行高层次的结构设计； 然后进行低层次的过程设计；穿插进行数据设计和接口设计。3.3.1.2软件设计的基本原理软件设计遵循软件工程的基本目标和原则，建立了适用于软件设计中应该遵循的基本原理和与软件设计有关的概念。（ 1）抽象。抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。（ 2）模块化。模块是指把

109、一个待开发的软件分解成若干小的简单的部分。 模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。（ 3） 信息隐蔽。 是指在一个模块内包含的信息（ 过程或数据），对于不需要这些信息的其他模块来说是不能访问的。（ 4）模块独立性。是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。内聚性是度量一个模块功能强度的一个相对指标，耦合性则用来度量模块之间的相互联系程度。耦合可以分为下列几种，它们之间的耦合度由高到低排列：内容耦合- 若一个模块直接访问另一模

110、块的内容， 则这两个模块称为内容耦合。公共耦合- 若一组模块都访问同一全局数据结构， 则称为公共耦合。外部耦合- - 若一组模块都访问同一全局数据项，则称为外部耦合。控制耦合一若一模块明显地把开关量、名字等信息送入另一模块，控制另一模块的功能，则称为控制耦合。标记耦合- 若两个以上的模块都需要其余某一数据结构的子结构时， 不使用其余全局变量的方式而是使用记录传递的方式， 这样的耦合称为标记耦合。数据耦合- 若一个模块访问另一个模块， 被访问模块的输入和输出都是数据项参数，则这两个模块为数据耦合。非直接耦合- 若两个模块没有直接关系， 它们之间的联系完全是通过程序的控制和调用来实现的，则称这两个

111、模块为非直接耦合，这样的耦合独立性最强。内聚是从功能角度来衡量模块的联系，它描述的是模块内的功能联系。内聚有如下种类，它们之间的内聚度由弱到强排列。偶然内聚- 模块中的代码无法定义其不同功能的调用。 但它使该模块能执行不同的功能，这种模块称为巧合强度模块。逻辑内聚- 这种模块把几种相关的功能组合在一起， 每次被调用时，由传送给模块的参数来确定该模块应完成哪一种功能。时间内聚- 这种模块顺序完成一类相关功能，比如初始化模块，它顺序地为变量置初值。过程内聚- - 如果一个模块内的处理元素是相关的， 而且必须以特定次序执行，则称为过程内聚。通信内聚- 这种模块除了具有过程内聚的特点外， 还有另外一种

112、关系，即它的所有功能都通过使用公用数据而发生关系。顺序内聚- 如果一个模块内各个处理元素和同一个功能密切相关， 而且这些处理必须顺序执行，一个处理元素的输出数据作为下一个处理元素的输入数据，则称为顺序内聚。功能内聚- 如果一个模块包括为完成某一具体任务所必需的所有成分， 或者说模块中所有成分结合起来是为了完成一个具体的任务，此模块则为功能内聚模块。耦合性与内聚性是模块独立性的两个定性标准，耦合与内聚是相互关联的。 在程序结构中， 各模块的内聚性越强， 则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性03.3.1.3

113、结构化设计方法的基本要求结构化设计方法的基本要求是：在详细设计阶段，为了确保模块逻辑清晰， 就应该要求所有的模块只使用单入口、单出口以及顺序、选择和循环3种基本控制结构。这样，不论一个程序包含多少个模块， 每个模块包含多少个基本的控制结构， 整个程序仍能保持一条清晰的线索。3.3.2概要设计任务概要设计又称总体设计，软件概要设计的基本任务如下所述。（1）设计软件系统结构为了实现目标系统，先进行软件结构设计，如图3-6所示。（2）数据结构及数据库设计数据设计是实现需求定义和规格说明中提出的数据对象的逻辑表示。(3)编写概要设计文档概要设计阶段的文档有概要设计说明书、数据库设计说明书和集成测试计划

114、等。(4)概要设计文档评审在文档编写完成后，要对设计部分是否完整地实现了需求中规定的功能、性能等要求，设计方案的可行性，关键的处理及内外部接口定义正确性、有效性，各部分之间的一致性等进行评审，以免在以后的设计中出现大的问题而返工。I按功能分模麻1I确 定 每 点 块 功 前I确定模，调 用 斓| 确定模玄间接T7| 评估战力构一系图3 6软件系统结构设计过程结 构 图(Stucture Chart, S C ), 也称程序结构图，是描述软件结构的图形工具，是常用的软件结构设计工具。结构图的基本图符及含义如表3-4所示。表3-4 结构图基本图符号概念 含义图 符模块 一个矩形代表一个模块， 矩形

115、内注明模块的名字或主要功能n 一般模块调用关系 矩形之间的箭头( 或直线) 表示模块的调用关系调用关系用带注释的箭头表示模块调用过程中来回传递的信息. 如果希信息 望进一步标明传递的信息是数据信息还是控制信息， 则可用带实心圆的箭头表示是控制信息， 空心圆表示数据信息0- 数据信息- - - - - - - - 控制信息软件结构图是软件系统的模块层次结构，反映了整个系统的功能实现。结构图有4中常用的模块类型：传入模块、传出模块、变换模块和协调模块，其表示图形如图3-9所示。图3 9结构图4种模块类型3.3.3面向数据流的设计方法面向数据流的结构化设计（SD）, 能够方便地将数据流图DFD转换成

116、程序结构图。DFD从系统的输入数据流到系统的输出数据流的一连串连续加工形成了 一条信息流。3.3.3.1 数据流的类型数据流图的信息流可分为两种类型：变换流和事务流。相应地,数据流图有两种典型的结构形式：变换型和事务型。变换型。 信息沿输入通路进入系统，同时由外部形式变换成内部形式，然后通过变换中心（ 也叫主加工），经加工处理以后再沿输出通路变换成外部形式离开软件系统。 当数据流图具有这些特征时，这种信息流就称为变换流，这种数据流图，称为变换型数据流图。变换型数据流图可以明显地分成输入、变换中心、输出3大部分，如图3-11所示。事务型。 信息沿着输入通路到达一个事务中心，事务中心根据输入信息（

117、 称为事务）的类型在若干个处理序列（ 称为活动流）中选择一个来执行，这种信息流称为事物流，这种数据流图，称为事务型数据流图。 事务型数据流图有明显的事务中心， 各活动流以事物中心为起点呈辐射状流出，如图3-12所示。3.33.2面向数据流设计方法的实施要点与设计过程面向数据流的结构设计过程和步骤是：( 1 ) 分析、确认数据流图的类型，区分是事务型还是变换型；(2)说明数据流的边界；(3 ) 把数据流图映射为程序结构；(4)根据设计准则把数据流转换成程序结构图。将变换型映射成结构图，又称为变换分析。其步骤如下：( 1 ) 确定数据流图是否具有变换特性；(2)确定输入流和输出流的边界，划分出输入

118、、变换和输出，独立出变换中心；(3)进行第一级分解，将变换型映射成软件结构；(4)按上述步骤如出现事务流的映射方式对各个子流进行逐级分解，直至分解到基本功能；(5)对每个模块写一个简要的说明；(6)利用软件的设计原则对软件结构进一步转化。将事务型映射成结构图，又称为事务分析。其步骤与变换分析的设计步骤大致类似， 主要差别仅在于由数据流图到软件结构的映射方法不同。 它是将事务中心映射成为软件结构中发分支的调度模块，将接收通路映射成软件结构的接收分支。3 .3 .4结构化设计的准则大量的实践表明，以下的设计准则可以借鉴为设计的指导和对软件结构图进行优化的条件。（ 1）提高模块独立性；（2）模块规模

119、适中；（ 3）深度、宽度、扇出和扇入适当；（4）使模块的作用域在该模块的控制域内；（5）应减少模块的接口和界面的复杂性；（ 6）设计成单入口、单出口的模块；（7）设计功能可预测的模块。3 .3 .5详细设计详细设计的任务，是为软件结构图中的每一个模块确定实现算法和局部数据结构， 用某种选定的表达工具表示算法和数据结构的细节。常用的过程设计工具如下所述。图形工具：程序流程图、N-S图、PAD图、HIPOo表格工具：判定表。语言工具：PDL （ 伪码）。3 3 .5 .1程序流程图程序流程图又称为程序框图， 在程序流程图中， 构成程序流程图的最基本图符及含义如下所述。方框表示一个加工步骤。菱形表示

120、一个逻辑条件。箭头表示控制流。按照结构化程序设计的要求， 程序流程图构成的所有程序描述可分解为如图3-6所示的5种控制结构，它们的含义如下所述。顺序型：几个连续的加工步骤依次排列构成。选择型：由某个逻辑判断式的取值决定选择两个加工中的一个。先判断重复型（WHILE型）：先判断循环控制条件是否成立，成立则执行循环体语句。后判断重复型（UNTIL型）：重复执行某些特定的加工，直到控制条件成立。多分支选择型：列举多种加工情况，根据控制变量的取值，选择执行其中之一。通过把图3-13中的5种基本结构相互组合或嵌套，可以构成任何复杂的程序流程图。图3 1 3程序流程图的5种相本控制结构程序流程图不易表示数

121、据结构。33.5.2 N-S图为了避免流程图在描述程序逻辑时的随意性与灵活性，1973年Nossi和Shneiderman提出了用方框图代替传统的程序流程图，引起了人们的重视，人们也把这种图称为N-S图。方框图中仅含5种基本的控制结构，即顺序型、超择型、多分支选择型、WHILE重复型和UNTIL重复型，如图3-14所示。WHILE型循环结构循环体循 环条 件UNTIL型循环结构循 环循环体顺序结构选择结构图3 14 N S图图符匕构成的5种控制结构多分支选择结构=1=2=NA.A2A”3.3.53 PAD图PAD是问题分析图(Problem Analysis Diagram )的英文缩写。它是

122、继流程图和方框图之后， 由日本的二村良彦等人在1979年提出的又一种主要用于描述软件详细设计的图形表示工具。与方框图一样，PAD也只能描述结构化程序允许使用的几种基本结构。PAD图的基本图符表示5种基本控制结构，如图3-15所示。多分支选择结构UNTIL型循环结构 WHILE型循环结构图3 15 PAD图的5种届本控制结构33.5.4 PDLPDL是过程设计语言（ Procedure Design Language）的英文缩写，也称为伪码。一般说来，PDL是一种“ 混合” 语言，它使用一种语言（ 英语）的词汇，同时却使用另一种语言（ 某种结构化的程序设计语言）的语法。用PD俄示的基本控制结构的

123、常用词汇如下：顺序：A/A END条件：IF/THEN/ELSE/ENDIF循环：DO WHILE/ENDDO循环：REPEAT UNTIL/ENDREPEAT分支：CASE_OF/WHEN/SELECT/WHEN/SELECT/ENDCASE3 .4 软件的测试软件测试就是在软件投入运行之前，尽可能多地发现软件中的错误。软件测试是保证软件质量、可靠性的关键步骤。它是对软件规格说明、设计和编码的最后复审。通常，软件测试的工作量往往占软件开发总工作量的40%以上。3.4.1 软件测试的目的和准则3.4.1.1 软件测试的目的Grenford.J.Myers给出了软件测试的目的。( 1 ) 测试是

124、为了发现程序中的错误而执行程序的过程。( 2 ) 好的测试用例(test case)很可能发现迄今为止尚未发现的错误。(3)一次成功的测试是指发现了至今为止尚未发现的错误。测试的目的是发现软件中的错误，但是，暴露错误并不是软件测试的最终目的， 测试的根本目的是尽可能多地发现并排除软件中隐藏的错误。3.4.1.2软件测试的准则根据上述软件测试的目的，为了能设计出有效的测试方案，以及好的测试用例，软件测试人员必须深入理解，并正确运用以下软件测试的基本准则。(1)所有测试都应追溯到用户需求。(2)在测试之前制定测试计划，并严格执行。(3)充分注意测试中的群集现象。(4)避免由程序的编写者测试自己的程

125、序。(5)不可能进行穷举测试。(6 ) 妥善保存测试计划、测试用例、出错统计和最终分析报告,为维护提供方便。3.4.2软件测试技术与方法软件测试具有多种方法，根据软件是否需要被执行，可以分为静态测试和动态测试。如果按照功能划分， 可以分为白盒测试和黑盒测试。3.4.2.1 静态测试与动态测试静态测试一般是指人工评审软件文档或程序，借以发现其中的错误。由于被评审的文档或程序不必运行，所以称为静态的。静态测试包括代码检查、静态结构分析、代码质量度量等。静态测试可以由人工运行，充分发挥人的逻辑思维优势，也可以借助软件工具自主运行。动态测试是指通常的上机测试，这种方法是使程序有控制地运行，并从多种角度

126、观察程序运行时的行为，以发现其中的错误。测试是否能够发现错误取决于测试实例的设计。 动态测试的设计测试实例方法一般有两类：黑盒测试方法和白盒测试方法。设计高效、 合理的测试用例是动态测试的关键。 测试用例是为测试设计的数据。 测试用例由测试输入数据和与之对应的预期输出结果两部分组成。测试用例的格式如下： （ 输入值集） ，（ 输出值集） 3.4.2.2白盒测试方法与测试用例设计白盒测试又称为结构测试或逻辑驱动测试。 它允许测试人员利用程序内部的逻辑结构及有关信息来设计或选择测试用例， 对程序所有的逻辑路径进行测试。白盒测试是在程序内部进行， 主要用于完成软件内部操作的验证。白盒测试的基本原则是

127、： 保证所测模块中每一个独立路径至少执行一次； 保证所测试模块所有判断的每一个分支至少执行一次； 保证所测模块的每一个循环都在边界条件和一般条件下至少执行一次；验证所有内部数据结构的有效性。白盒测试法主要有逻辑覆盖和基本路径测试等。（ 1）逻辑覆盖测试。泛指一系列以程序内部的逻辑结构为基础的测试用例设计技术。 通常所指的程序中的逻辑表示有判断、 分支、条件3种表示方式。语句覆盖。语句覆盖是一个比较弱的测试标准，它的含义是,选择足够的测试实例，使得程序中的每一个语句都能执行一次。路径覆盖。执行足够的测试用例，使程序中所有的可能路径都至少经历一次。判定覆盖。设计足够的测试实例，使得程序中的每个判定

128、至少都获得一次“ 真值“ 和 “ 假值” 的机会。判定覆盖要比语句覆盖严格 ，因为如果每个分支都执行过了，则每个语句也执行过了。条件覆盖。对于每个判定中所包含的若干个条件，应设计足够多的测试实例，使得判定中的每个条件都取到” 真 ” 和 “ 假 “ 两个不同的结果。条件覆盖通常比判定覆盖强，但也有的测试实例满足条件覆盖而不满足判定覆盖。判断一条件覆盖。设计足够多的测试实例，使得判定中的每个条件都能取得各种可能的“ 真” 和 “ 假 ” 值 ，并且使每个判定都能取到 慎 “ 和 “ 假 “ 两种结果。(2)基本路径测试。它的思想和步骤是，根据软件过程性描述中的控制流程确定程序的环路复杂性度量，

129、用此度量定义基本路径集合，并由此导出一组测试用例对每一条独立执行路径进行测试。3.4.23黑盒测试方法与测试用例设计黑盒测试方法又称功能测试或数据驱动测试，着重测试软件功能。白盒测试在测试过程的早期阶段进行，而黑盒测试主要用于软件的确认测试。黑盒测试完全不考虑程序内部的逻辑结构和处理过程， 黑盒测试是在软件接口处进行， 检查和验证程序的功能是否符合需求规格说明书的功能说明。常用的黑盒测试方法和技术有：等价类划分法、边界值分析法、错误推测法等。( 1 )等价类划分法等价类划分是一种常用的黑盒测试方法，这种技术的方法是先把程序的所有可能的输入划分成若干个等价类， 然后根据等价类选取相应的测试用例。

130、 每个等价类中各个输入数据度发现程序中错误的几率几乎是相同的。因此，从每个等价类中只取一组数据作为测试数据， 这样选取的测试数据最有代表性， 最可能发现程序中的错误，并且大大减少了需要的测试数据的数量。( 2 )边界值分析法边界值分析法是对各种输入、输出范围的边界情况设计测试用例的方法。大量的实践表明，程序在处理边界值时容易出错，因此设计一些测试用例， 使程序运行在边界情况附近， 这样揭露程序中错误的可能性就更大。选取的测试数据应该刚好等于、小于和大于边界值。也就是说,按照边界值分析法， 应该选取刚好等于、 稍小于和稍大于等价类边界值的数据作为测试数据， 而不是选取每个等价类内的典型值或任意值

131、作为测试数据。通常设计测试方案时总是把等价划分和边界值分析法结合使用。( 3 )错误推测法错误推测法概念。错误推测法是一种凭直觉和经验推测某些可能存在的错误， 从而针对这些可能存在的错误设计测试用例的方法。 这种方法没有机械的执行过程，主要依靠直觉和经验。错误推测法针对性强，可以直接切入可能的错误，直接定位，是一种非常实用、有效的方法，但是需要非常丰富的经验。错误推测法实施步骤。首先对被测试软件列出所有可能出现的错误和易错情况表， 然后基于该表设计测试用例。3.4.3软件测试的实施软件测试是保证软件质量的重要手段，软件测试是一个过程，其测试流程是该过程规定的程序， 目的是使软件测试工作系统化。

132、软件测试的实施过程分4个步骤，即单元测试、集成测试、确认测试和系统测试。3.4.3.1 单元测试单元测试是对软件设计的最小单位- 模块（ 程序单元）进行正确性检验测试。 单元测试的目的是发现各模块内部可能存在的各种错误 。单元测试的依据是详细的设计说明书和源程序。单元测试的技术可以采用静态分析和动态测试。对动态测试通常以白盒动态测试为主，辅之以黑盒测试。单元测试是针对单个模块，这样的模块通常不是一个独立的程序 ，需要考虑模块和其他模块的调用关系。在单元测试中，用一些辅助模块去模拟与被测模块相联系的其他模块， 即为测试模块设计驱动模块和桩模块，构成一个模拟的执行环境进行测试，如图3-21所示。驱

133、 动（Driver）模块就相当于一个“ 主程序” ，它接收测试数据，把这些数据传送给被测试的模块，输出有关的结果。桩（ Stub）模块代替被测试的模块所调用的模块。因此桩模块也可以称为“ 虚拟子程序” 。 它接受被测模块的调用， 检验调用参数,模拟被调用的子模块的功能，把结果送回被测试的模块。在软件的结构图中，顶层模块测试时不需要驱动模块，最底层的模块测试时不需要桩模块。I被 测 模 块II驱 动 模 块I机 模 面 | 桩模块2 | | 麻 块31图3 2 1单元测试的测试环境3.43.2集成测试集成测试是测试和组装软件的过程。集成测试主要发现设计阶段产生的错误，集成测试的依据是概要设计说明

134、书，通常采用黑盒测试。集成测试的内容主要有以下4个方面： 软件单元的接口测试； 全局数据结构测试； 边界条件测试； 非法输入测试。集成的方式可以分为非增量方式集成和增量方式集成两种。非增量方式是先分别测试每个模块，再把所有模块按设计要求组装一起进行整体测试，因此，非增量方式又称一次性组装方式。增量方式是把要测试的模块同已经测试好的那些模块连接起来进行测试，测试完以后再把下一个应测试的模块连接进来测试。增量方式包括自顶向下、自底向上以及自顶向下和自底向上相结合的混合增量方法。3.4.33确认测试确认测试的任务是检查软件的功能、性能及其他特征是否与用户的需求一致， 它是以需求规格说明书作为依据的测

135、试。 确认测试通常采用黑盒测试。确认测试首先测试程序是否满足规格说明书所列的各项要求，然后要进行软件配置复审。复审的目的在于保证软件配置齐全、分类有序，以及软件配置所有成分的完备性、一致性、准确性和可操作性，并且包括软件维护所必需的细节。3.43.4系统测试在确认测试完成后，把软件系统整体作为一个元素，与计算机硬件、 支持软件、 数据、 人员和其他计算机系统的元素组合在一起,在实际运行环境下对计算机系统进行一系列的集成测试和确认测试，这样的测试称为系统测试。系统测试的目的是在真实的系统工作环境下检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方。系统测试的内容包括：功能测试、操作测试

136、、配置测试、性能测试、安全性测试、外部接口测试等。3.5程序的调试在对程序进行成功测试之后将进行程序调试（ 排错）。程序调试的任务是诊断和改正程序中的错误。3.5.1 程序调试的概念调 试 （ 也称为Debug,排错） 是作为成功测试的后果出现的步骤,也就是说，调试是在测试发现错误之后排除错误的过程。 软件测试贯穿整个软件生命期，而调试主要在开发阶段。程序调试活动由两部分组成:根据错误的迹象确定程序中错误的确切性质、原因和位置。对程序进行修改，排除这个错误。3.5.1.1 程序调试的基本步骤(1)错误定位。从错误的外部表现形式入手，研究有关部分的程序，确定程序中出错的位置，找出错误的内在原因。

137、(2)修改设计和代码，以排除错误。排错是软件开发过程中一项艰苦工作， 这也决定了调试工作是一个具有很强技术性和技巧性的工作。(3)进行回归测试，防止引进新的错误。因为修改程序可能带来新的错误，重复进行暴露这个错误的原始测试或某些有关测试，以确认该错误是否被排除、是否引进了新的错误。3.5.1.2 程序调试原则调试活动由对程序中错误的定性、定位和排错两部分组成，因此调试原则也从这两个方面来考虑。(1)错误定性和定位的原则集中思考分析和错误现象有关的信息。不要钻死胡同。如果在调试中陷入困境，可以暂时放在一边,或者通过讨论寻找新的思路。不要过分信赖调试工具。调试工具只能提供一种无规律的调试方法，不能

138、代替人思考。避免用试探法。试探法其实是碰运气的盲目动作，成功率很小，是没有办法时的办法。(2)修改错误的原则在错误出现的地方，可能还有其他错误。因为经验表明，错误有群集现象。修改错误的一个常见失误是只修改了这个错误的现象，而没有修改错误本身。 如果提出的修改不能解释与这个错误有关的全部线索，这就表明只修改了错误的一部分。必须明确，修改一个错误的同时可能引入了新的错误。解决的办法是在修改了错误之后，必须进行回归测试。修改错误的过程将迫使人们暂时回到程序设计阶段。修改错误也是程序设计的一种形式， 在程序设计阶段所使用的任何方法都可以应用到错误修正的过程中来。修改源代码程序，不要改变目标代码。3.5

139、.2软件调试的方法类似于软件测试，软件调试从是否跟踪和执行程序的角度，分为静态调试和动态调试。静态调试是主要的调试手段，是指通过人的思维来分析源程序代码和排错，而动态调试是静态测试的辅助。3.5.2.1 强行排错法作为传统的调试方法，强行排错法的过程可概括为设置断点、程序暂停、观察程序状态、继续运行程序。在使用任何一种调试方法之前，必须首先进行周密的思考，必须有明确的目的，应该尽量减少无关信息的数量。3.5.2.2 回溯法回溯法适合于小规模程序的排错。即一旦发现了错误，先分析错误征兆，确定最先发现症状” 的位置。然后，从发现” 症状” 的地方开始，沿程序的控制流程，逆向跟踪源程序代码，直到找到

140、错误根源或确定出错产生的范围。3 5 2 .3 原因排除法原因排除法是通过演绎、归纳、二分法来实现的。演绎法是一种从一般原理或前提出发，经过排除和精化的过程来推导出结论的思考方法。归纳法是一种从特殊推断出一般的系统化思考方法。其基本思想是从一些线索着手, 通过分析寻找到潜在的原因， 从而找出错误。二分法实现的基本思想是，如果已知每个变量在程序中若干个关键点的正确值， 则可以使用定值语句（ 如赋值语句、 输入语句等）在程序中的某点附近给这些变量赋正确值， 然后运行程序并检查程序的输出。3 .6 软件工程管理1 . 软件工程管理的职能（ 1）组织管理。软件开发将涉及业务人员和技术人员，只有他们的共

141、同参与才能保证待开发的软件能根据用户提出的需求， 在软件技术人员配合下顺利完成。（2）人员管理。软件开发，特别是应用软件开发，需要各方面和各层次人员参加。完备的人员组织和管理，明确的任务分工，特别是开发人员和测试人员间的分工和配合， 将对软件开发的质量起到良好的保证。（ 3）资源管理。软件是特定系统的组成部分，它的开发也是系统开发的组成部分，软件开发离不开系统环境资源的支持，它们包括硬件、支撑软件、通信和辅助资源。（4）计划管理。计划管理包括对整个软件生命周期的计划安排和执行，工作量的估算和分配以及具体的进度安排。2 . 进度安排( 1 ) 进度的表示方法。明确软件开发的起始时间和交付时间是制

142、定进度的关键数据， 在总开发时间内科学地划分软件生命周期各时间段内的比例是非常关键的。( 2 ) 进度的安排方法。当前主要的进度安排方法包括：甘特图方法，即Grant方法；时间标记网络法(Time Scalar Network)、进度计划评审法(Program Evaluation and Review Technique)和关键路 径 法(Critical Path M ethod)等。3 . 标准化对于规模化的生产， 科学的管理应该是规范化的管理和标准化的管理。 对于软件生产和软件生产工程化， 当其规模达到一定程度后,其管理的规范化和标准化要求就十分迫切了。( 1 ) 软件工程标准化。软件

143、工程标准化是在大规模的软件生产活动中提出的要求，它包括：如何制定软件计划；怎样进行软件需求分析、设计；程序的编码、测试要求；维护的进行以及软件的组织管理等， 它们都需制定必要的标准并形成规范。( 2 ) 标准化的作用。软件工程标准化的作用可概括为3方面：为软件开发各层次人员提供共同遵守的规定， 把参与软件开发的各层次人员约束在一个共同的、必须遵守的标准下，以利于规范行为和有效通讯；为软件工程成果的评价和验收提供客观的、统一的标准；为软件的维护带来极大的好处。4 . 软件配置由于软件生产的复杂性，从研制、生产到使用需要经历复杂的过程，每一过程都将产生各种产品，如文档、手册和程序，它们共同构成一个

144、完 的 软 件 系统，这种构成就是软件配置。软件配置是动态的，它随软件设计、生产和使用，即按生命周期的推动而逐步增加和完善。5 .软件产权保护软件是一种不只是产品，同时又是一种易复制的产品。从长远和发展看，与保护任何一种知识产品一样， 应对软件产品的版权进行保护，会有利于软件产业的发展。第4章数据库设计基础4 .1 数据库系统的基本概念数据库技术是计算机领域的一个重要分支，数据库技术是作为一门数据处理技术发展起来的。随着计算机应用的普及和深入， 数据库技术变得越来越重要了。本节主要讲解数据库系统的基本概念、特点、内部体系结构及其发展历程。4 .1 .1 数据、数据库4.1.1.1 数据数 据

145、（Data）是数据库中存储的基本对象，是描述事物的符号记录。描述事物的符号可以是数字，也可以是文字、声音、图形、图像等，数据有多种表现形式。数据库系统中的数据有长期持久的作用，它们被称为持久性数据，而把一般存放在计算机内存中的数据称为临时性数据。数据有型(Typ e)与 值(Value)之分，数据的“ 型” 给出了数据的表示类型， 如整型、实型、字符型等； 值” 给出符合给定型的值,如整型值2 0 ,实型值2 .3 5 ,字符型值”1 ”等。4.1.1.2数据库数 据 库(DataBase, DB)是指长期储存在计算机内、有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存

146、储，具有较小的冗余度、 较高的数据独立性和易扩展性， 并可为各种用户( 应用程序) 共享。通俗的理解，数据库就是存放数据的仓库，只不过，数据库存放数据是按数据所提供的数据模式存放的。4.1.2数据库管理系统4.1.2.1数据库管理系统的概念数据库管理系统(DataBase Management System, DBM S)是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。目前流行的DBMS均为关系数据库系统，例如Oracle、PowerBuilder DB2和SQL Sever等。数据库管理系统是数据库系统的核心，它位于用户与操作系统之间，从

147、软件分类的角度来说，属于系统软件。数据库管理系统有如下功能：数据模式定义。数据库管理系统负责为数据库构建模式。数据存取的物理构建。 数据库管理系统负责为数据模式的物理存取及构建提供有效的存取方法与手段。数据操纵。数据库管理系统一般提供查询、插入、修改以及删除数据的功能。 它还具有做简单算术运算及统计的能力和强大的过程性操作能力。数据的完整性、安全性定义与检查。 数据库中的数据具有内在语义上的关联性与一致性，它们构成了数据的完整性；数据库的并发控制与故障恢复。 数据库管理系统必须对多个应用程序的并发操作做必要的控制以保证数据不受破坏， 这就是数据库的并发控制；数据库中的数据一旦遭受破坏， 数据库

148、管理系统必须有能力及时进行恢复，这就是数据库的故障恢复；数据的服务。 数据库管理系统提供对数据库中数据的多种服务功能，如数据拷贝、转储、重组、性能监测、分析等。为完成以上6个功能，数据库管理系统提供了相应的数据语言(Data Language), 它们是：数据定义语言(Data Definition Language* D D L)。该语言负责数据的模式定义与数据的物理存取构建。数据操纵语言(Data Manipulation Language, D M L)。该语言负责数据的操纵，包括查询及增加、删除、修改等操作。数据控制语言(Data Control Language, DCL)。该语言负

149、责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。上述数据语言按其使用方式具有以下两种结构形式。交互式命令语言：它的语言简单，能在终端上即时操作，它又称为自含型或自主型语言。宿主型语言：它一般可嵌入某些宿主语言中，如C、C+和COBOL等高级过程性语言中。4.1.2.2数据库管理员数据库管理员(DataBase Administrator, DBA)是指对数据库的规划、设计、维护、监视等的人员。数据库管理员的主要工作如下：数据库设计(Database Design) ： DBA的主要任务之一是数据库设计，具体地说是进行数据模式的设计；数据库维护：DBA必须对数据库中的数据安全性、完

150、整性、并发控制及系统恢复、数据定期转储等进行实施与维护；改善系统性能：提高系统效率。DBA必须随时监视数据库的运行状态，不断调整内部结构，使系统保持最佳状态与效率。4.1.3数据库系统4.1.3.1数据库系统的概念数据库系统(DataBase System, DBS)是指在计算机系统中引入数据库后的系统构成。数据库系统由数据库( 数据) 、数据库管理系统、应用系统、数据库管理员、系统平台之一- - 硬件平台( 硬件) 、系统平台之二- 软 件 平 台 ( 软 件 ) 5部分构成。硬件平台包括以下两项：计算机：它是系统中硬件的基础平台；网络：数据库系统今后将以建立在网络上为主， 而其结构形成又以

151、客户/ 服务器（C/S）方式与浏览器/ 服 务 器（B/S）方式为主。软件平台包括以下3项：操作系统：它是系统的基础软件平台；数据库系统开发工具：它包括过程性程序设计语言（ 如C, C+等），也包括可视化开发工具VB、PB、Delphi等，它还包括近期与Internet 有关的 HTML和 XML 等。接口软件： 在网络环境下数据库系统中数据库与应用程序， 数据库与网络间存在着多种接口，它们需要接口软件进行连接， 这些接口软件包括ODBC、JDBC、OLEDB、CORBA COM及DCOM等。4.1.3.2数据库应用系统在数据库系统的基础上，如果使用数据库管理系统（DBMS）软件和数据库开发工

152、具书写出应用程序， 用相关的可视化工具开发出应用界面， 则构成了数据库应用系统（Database Application System,简称DBAS） o DBAS由数据库系统、应用软件及应用界面三者组成。因此，DBAS包括数据库、数据库管理系统、人 员 （ 数据库管理员和用户）、硬件平台、软件平台、应用软件、应用界面7个部分。4.1.4数据库系统的发展数据管理技术的发展经历了3个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。文件系统是数据库系统发展的初级阶段，它具有提供简单的数据共享与数据管理的能力， 但是它缺少提供完整、统一的管理和数据共享的能力。层次数据库与网状数据库的发展为统一管理

153、与共享数据提供了有力的支撑， 但是由于它们脱胎于文件系统， 所以这两种系统也存在不足。关系数据库系统结构简单，使用方便，逻辑性强，物理性少，因此在20世纪80年代以后一直占据数据库领域的主导地位。关于数季管理3个阶段中的软硬件背景及处理特点，简单概括如表4-1所示。表4-1 数据管理3个阶段的比较人工管理阶段文件管理阶段数据库系统管理阶段背背景应用目的科学计篁科学计算、管理大规模管理硬件背景无直接存取设备磁盘、磁鼓大容量磁盘软件背景无操作系统有文件系统有数据库管理系统处理方式批处理联机实时处理、批处理分布处理、联机实时处理和批处理特点数据管理者人文件系统数据库管理系统数据面向的对象某个应用程序

154、某个应用程序现实世界数据共享程度无共享， 冗余度大共享性差， 冗余度大共享性大， 冗余度小数据的独立性不 独 立 ， 完全侬赖于程序独立性差具有高度的物理独立性和一定的逻辑独立性数据的结构化无结构记录内有结构， 整体无结构整体结构化， 用数据模型描述数据控制能力由应用程序控制由应用程序控制由DBMS提供数据安全性、完整性、并发控制和恢复4 .1 .5数据库系统的基本特点数据库系统的基本特点有数据集成性、数据的高共享性和低冗余性、数据独立性高、数据统一管理与控制。4.1.5.1数据的集成性数据库系统的数据集成性主要表现在如下几个方面:（ 1）在数据库系统中采用统一的数据结构方式。（ 2） 在数据

155、库系统中按照多个应用的需要组织全局的统一的数据 结 构 （ 即数据模式），数据模式不仅可以建立全局的数据结构，还可以建立数据间的语义联系， 从而构成一个内在紧密联系的数据整体。（3）数据库系统中的数据模式是多个应用共同的、全局的数据结构， 而每个应用的数据则是全局结构中的一部分， 称为局部结构（ 即视图），这种全局与局部的结构模式构成了数据库系统数据集成性的主要特征。4.1.5.2 数据的高共享与低冗余性由于数据的集成性使得数据可为多个应用所共享。数据的共享自身极大地减少了数据冗余性，不仅减少存储空间， 还避免数据的不一致性。所谓数据的一致性，是指在系统中同一数据在不同位置的出现应保持相同的值

156、， 而数据的不一致性指同一数据在系统的不同拷贝处有不同的值。因此，减少冗余性以避免数据的不同值出现。4.1.5.3 数据的独立性数据独立性是数据与程序间的互不依赖性，即数据库中的数据独立于应用程序而不依赖于应用程序。 数据的逻辑结构、 存储结构与存取方式的改变不会影响应用程序。数据的独立性一般分为物理独立性与逻辑独立性两种。物理独立性： 指用户的应用程序与存储在磁盘上的数据库中数据是相互独立的。 当数据的物理结构（ 包括存储结构、 存取方式等）改变时，如存储设备的更换、物理存储的更换、存取方式改变等，应用程序都不用改变。逻辑独立性： 指用户的应用程序与数据库的逻辑结构是相互独立的。数据的逻辑结

157、构改变了，如修改数据模式、增加新的数据类型、改变数据间联系等，用户程序都可以不变。4.1.5.4数据统一管理与控制数据统一管理与控制主要包括以下3个方面。数据的完整性检查： 将数据控制在有效的范围内，或保证数据之间满足一定的关系。数据的安全性保护： 每个用户只能按指定方式使用和处理指定数据，保护数据以防止不合法的使用造成的数据泄密和破坏。并发控制： 对多用户的并发操作加以控制和协调，防止相互干扰而得到错误的结果。4.1.6数据库系统的内部结构体系数据库的产品很多，它们支持不同的数据模型，使用不同的数据库语言, 建立在不同的操作系统上, 数据的存储结构也各不相同,但体系结构基本上都具有相同的特征

158、，采用” 三级模式和两级映射 , 这是数据库管理系统内部的系统结构，如图4-3所示。图4-3 : 级模式、 两级映射关系图4.1.6.1数据库系统的三级模式结构数据库系统在其内部分为三级模式，即概念模式、内模式和外模式。( 1 ) 概念模式(Cone叩tual Schem a)。概念模式也称模式，是对数据库系统中全局数据逻辑结构的描述，是全体用户( 应用) 公共数据视图。 它不涉及具体的硬件环境与平台，也与具体的软件环境无关。模式实际上是数据库数据在逻辑级上的视图。一个数据库只有一个模式。( 2 ) 外 模 式 (ExternalSchema)。外模式也称子模式，它是数据库用户( 包括应用程序

159、员和最终用户) 能够看见和使用的局部数据的逻辑结构和特征的描述， 它是由概念模式推导而出来的，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。一个概念模式可以有若干个外模式。(3) 式 (Internal Schema)。内模式又称物理模式(PhysicalSchem a), 它给出了数据库物理存储结构与物理存取方法，如数据存储的文件结构、索引、集簇及hash等存取方式与存取路径，内模式的物理性主要体现在操作系统及文件级上， 它还未深入到设备级上( 如磁盘及磁盘操作) 。模式的三个级别层次反映了模式的三个不同环境及它们的不同要求，其中内模式处于最底层，它反映了数据在计算机物理结构中的

160、实际存储形式， 概念模式处于中间层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要求。4.1.6.2数据库系统的两级映射数据库系统在三级模式之间提供了两级映射：外模式/ 概念模式的映射和概念模式/ 内模式的映射。两级映射保证了数据库中的数据具有较高的逻辑独立性和物理独立性。(1)外模式/ 概念模式的映射：对于每一个外模式，数据库系统都提供一个外模式/ 概念模式的映射，它定义了该外模式描述的数据局部逻辑结构和概念模式描述的全局逻辑结构之间的对应关系。当概念模式改变时，只需要修改外模式/ 概念模式映射即可，外模式可以保持不变。由于应用程序是根据数据的外模式编写的，因此

161、应用程序也不必修改，保证了数据的逻辑独立性。(2)概念模式/ 内模式的映射：数据库只有一个概念模式和一个内模式，所以概念模式/ 内模式的映射是唯一的，它定义了概念模式描述的全局逻辑结构和内模式描述的存储结构之间的对应关系0当内模式改变时，只需要改变概念模式/ 内模式的映射，概念模式可以保持不变，从而应用程序保持不变， 保证了数据的物理独立性。4.2数据模型现有的数据库系统都是基于某种数据模型而建立的，数据模型是数据库系统的基础， 理解数据模型的概念对于学习数据库的理论是至关重要的。所谓模型，是对现实世界特征的模拟和抽象。4.2.1 数据模型的基本概念在数据库中用数据模型这个工具来抽象、表示和处

162、理现实世界中的数据和信息。通俗地讲，数据模型就是现实世界的反映，它分为两个阶段： 把现实世界中的客观对象抽象为概念模型；把概念模型转换为某一 DBMS支持的数据模型。从事物的客观特性到计算机里的具体表示包括了现实世界、信息世界和机器世界3个数据领域。现实世界：现实世界就是客观存在的各种事物，是用户需求处理的数据来源。信息世界：通过抽象对现实世界进行数据库级上的刻画所构成的逻辑模型。计算机世界：在信息世界基础上致力于其在计算机物理结构上的描述，从而形成的物理模型。数据模型从抽象层次上描述了数据库系统的静态特征、动态行为和约束条件，因此数据模型通常由数据结构、数据操作及数据约束3部分组成。（ 1）

163、数据结构数据结构是所研究的对象类型的集合，是对系统静态特性的描述。 数据结构是数据模型的核心，不同的数据结构有不同的操作和约束，人们通常按照数据结构的类型来命名数据模型。例如，层次结构、网状结构和关系结构的数据模型分别命名为层次模型、网状模型和关系模型。(2)数据操作数据操作是相应数据结构上允许执行的操作及操作规则的集合。数据操作是对数据库系统动态特性的描述。(3)数据约束数据的约束条件是一组完整性规则的集合。也就是说，具体的应用数据必须遵循特定的语义约束条件，以保证数据的正确、有效和相容。数据模型按不同的应用层次分成3种类型，它们是概念数据模型、逻辑数据模型及物理数据模型。4.2.2 E-R

164、模型概念模型是面向现实世界的，它的出发点是有效和自然地模拟现实世界，给出数据的概念化结构。它的表示方法很多，其中最著名的是E-R模 型(EntityRelationship M o d e l)( 或实体- 联系模型)。该模型将现实世界的要求转化成实体、码、属性等几个基本概念，以及实体集间的联系，并且可以用一种图非常直观地表示出来。4.2.2.1 E-R模型的基本概念( 1 ) 实 体 ( Entity)现实世界中的事物可以抽象成为实体，实体是概念世界中的基本单位， 它们是客观存在的且又能相互区别的事物。凡是有共同属性的实体组成的一个集合称为实体集。( 2 ) 属 性 (Attribute)现

165、实世界中事物均有一些特性，这些特性可以用属性来表示。属性刻画了实体的特征。 一个实体往往可以有若干个属性。 每个属性可以有值，一个属性的取值范围称为该属性的值域或值集。（ 3）联 系 （ Relationship）实体之间的对应关系称作联系，它反映现实世界事物之间的相互关联。 实体间联系的种类是指一个实体型中可能出现的每一个实体和另一个实体型中多少个具体实体存在联系， 可归纳为3种类型。一对一联系（1： 1） o 如果对于实体集A中的每一个实体，实体集B中至多有一个（ 也可以没有）实体与之联系，反之亦然，则称实体集A与实体集B具有一对一联系，记为1： lo 例如，一个学校只有一名校长，并且校长

166、不可以在别的学校兼职， 校长与学校的关系就是一对一联系一对多联系（1： n）或多对一联系（n： 1）。如果实体集A中的每一个实体，在实体集B中都有多个实体与之对应；实体集B 中的每一个实体，在实体集A中只有一个实体与之对应，则称实体集A与实体集B是一对多联系，反之即为多对一联系。例如，公司的一个部门有多名职员， 每一个职员只能在一个部门任职，则部门与职员之间的联系就是一对多的联系多对多联系（m： n） o 如果实体集A中的每一个实体，在实体集B中都有多个实体与之对应，反之亦然，则称这种关系是多对多联系。例如，一个学生可以选多门课程，一门课程可以被多名学生选修，学生和课程的联系就是多对多联系。4

167、.2.2.2实体、联系、属性之间的联接关系E-R模型的3个基本概念是实体、联系和属性，但现实世界是有机联系的整体，为了能表示现实世界，必须把这三者结合起来。（ 1）实 体 集 （ 联系）与属性的结合实体是概念世界中的基本单位，属性附属于实体，它本身并不构成独立单位。 一个实体可以有若干个属性，实体以及它的所有属性构成了实体的一个完整描述。属性有属性域，每个属性可取属性域内的值。实体有型与值之别， 一个实体的所有属性构成了这个实体的型,相同的实体构成了实体集。(2)实体( 集) 与联系的结合实体( 集) 间可通过联系建立联接关系。一般而言，实体( 集)间无法建立直接关系，它只能通过联系才能建立起

168、联接关系。4.2.23 E-R模型的图示法E-R模型可以用图形来表示，称为E-R图。E-R图可以直观地表达出E-R模型。 在E-R图中我们分别用不同的几何图形表示E-R模型中的3个概念与两个联接关系。(1 )实体集表示法在E-R图中用矩形表示实体集，在矩形内写上该实体集的名字。例如，实体集学生(student) 课 程(course)可用如图4-4 (a)所示来表示。(2)属性表示法在E-R图中用椭圆形表示属性，在椭圆形内写上该属性的名称。例如，学生有属性：学 号(S # )、姓 名(S n )及 年 龄(S a ),它们可以用如图4-4 ( b )所示来表示。(3)联系表示法在E-R图中用菱

169、形表示联系，菱形内写上联系名。例如，学生与课程间的联系S C ,可用如图4-4 ( c )所示来表示。| s l u d c m 1 1 c o u r s e |( a )实体集表示法图4- 4（ b ）属性表示法 （ c ）联系表示法E - R模型3个 概念的示意图（4）实 体 集 （ 联系）与属性间的联接关系属性依附于实体集，因此，它们之间有联接关系。在E-R图中这种关系可用联接这两个图形间的无向线段表示（ 一般用直线）。例如，实体集student有属性S# （ 学号）、Sn （ 学生姓名）及Sa （ 学生年龄）；实体集course有属性C# （ 课程号）、Cn （ 课程名） 及P# （

170、 预修课号），此时它们可用图4-5 （ a）联接。属性也依附于联系，它们之间也有联接关系，因此也可用无向线段表示。例如，联系SC可与学生的课程成绩属性G建立联接并可用如图牛5 （ b）所示来表示。（ a ）实体集的属性间的联接 （ b ）联系。属性间的联接图4 5实体集（ 联系）。属性间的联接关系图（5）实体集与联系间的联接关系在E-R图中， 实体集与联系间的联接关系可用联接这两个图形间的无向线段表示。例如，实体集student与联系SC间有联接关系，实体集course与联系SC间也有联接关系，因此它们之间可用无向线段相联，在线段边上注明其对应函数关系，如1 ： 1, 1： n, n： m等，

171、构成一个如图牛6所示的图。s t u d e n t c o u r s e图4 -6实体集间的联系示意图4.2.3层次模型( 1 )层次模型的数据结构用树形结构表示实体及其之间联系的模型称为层次模型。在层次模型中，结点是实体，树枝是联系，从上到下是一对多的关系。支持层次模型的数据库管理系统称为层次数据库管理系统，其中的数据库称为层次数据库。层次模型的特点如下所述：有且仅有一个无父结点的根结点，它位于最高的层次，即顶端。根结点以外的子结点，向上有且仅有一个父结点，向下可以有一个或多个子结点。生活中有很多层次模型的例子，家谱就是其中很有代表性的一个。家族的祖先就是父结点，向下体现一对多的关系。除

172、祖先外的所有家庭成员都可以看作是上级父结点的子结点， 向上有且仅有一个父结点，向下有一个或多个子结点。(2)层次模型的数据操作和完整性约束层次模型的数据操作主要有查询、插入、删除和修改。进行数据操作时，应该满足的完整性约束条件如下所述。进行插入操作时，如果没有相应的双亲结点值就不能插入子女结点值。进行删除操作时，如果删除的结点有子女结点，则相应的子女结点也被同时删除。进行修改操作时，应修改所有相应的记录，以保证数据的一致性。4.2.4网状模型用网状结构表示实体及其之间联系的模型称为网状模型。可以说，网状模型是层次模型的扩展，表示多个从属关系的层次结构,呈现一种交叉关系。支持网状模型的数据库管理

173、系统称为网状数据库管理系统，其中的数据库称为网状数据库。网状模型的特点如下： 允许一个或多个结点无父结点；一个结点可以有多于一个的父结点。网状模型上的结点就像是连入到互联网上的计算机一样，可以在任意两个结点之间建立起一条通路。4.2.5关系模型4.2.5.1 关系模型的数据结构关系模型(Relation M odel)是目前最常用的数据模型之一。关系模型的数据结构非常单一， 在关系模型中， 现实世界的实体以及实体间的各种联系均用关系来表示。关系模型中常用的术语如下所示。关系：关系模型采用二维表来表示关系，简称表，由表框架及表的元组组成。一个二维表就是一个关系。例如，表4-2的二维表就是一个关系

174、。属性： 二维表中的一列称为属性。 例如， 表4-2的属性有学号、姓名、系号等，二维表中属性的个数称为属性元数(Arity) o 表4-2中的关系属性元数为“5”。值域：每个属性的取值范围。例如，表4-6的Age属性的值域不能为负数。元组：二维表中的一行称为元组。例如，表4-2的 （06001,方铭，01, 2 2 ,男）就是一个元组。一个元组由若干个元组分量组成，每个元组分量是属性的投影值。 元组分量的个数等于属性元数， 表中元组的个数称为表的基数（ Cardinality）。候选码：二维表中能唯一标识元组的最小属性集。例如，在表4-2中，如果姓名不允许重名时，学号和姓名都是候选码。主键或主

175、码：若一个二维表有多个候选码，则选定其中一个作为主键供用户使用。例如，在表4-2中，存在两个候选码：学号和姓名，若选中学号作为唯一标识，那么，学号就是学生登记表关系的主码。二维表中一定要有键，因为如果表中所有属性的子集均不是键,则表中属性的全集必为键（ 称为全键），因此也一定有主键。外键或外码：表M中的某属性集是表N的候选键或者主键，则称该属性集为表M的外键或外码。 例如， 如果表4-3系信息表关系的主码是“ 系号” ，那么，在学生登记表（ 表4-2）中的“ 系号” 就是外码。表4 ” 学生登记表学号姓名系号年龄性别06001方格0122男06003张静0222女06234白白云0321男表4

176、-3系 信息表学号系名主任06001计算机0106003物理0206234数学03关系具有以下7条性质。元组个数有限性：二维表中元组的个数是有限的。元组的唯一性：二维表中任意两个元组不能完全相同。元组的次序无关性：二维表中元组的次序，即行的次序可以任意交换。元组分量的原子性：二维表中元组的分量是不可分割的基本数据项。属性名唯一性：二维表中不同的属性要有不同的属性名。属性的次序无关性：二维表中属性的次序可以任意交换。分量值域的同一性：二维表属性的分量具有与该属性相同的值域，或者说列是同质的。满足以上7个性质的二维表称为关系，以二维表为基本结构所建立的模型称为关系模型。4.Z.5.2关系操纵关系模

177、型的数据操作是建立在关系上的数据操作， 一般有查询、增加、删除及修改4种操作。数据查询。用户可以查询关系数据库中的数据，它包括一个关系内的查询以及多个关系间的查询。数据删除。数据删除的基本单位是一个关系内的元组，它的功能是将指定关系内的元组删除。数据插入。数据插入仅对一个关系而言，在该关系内插入一个或若干个元组。数据修改。 数据修改是在一个关系中修改指定的元组与属性。4.2.53关系模型的完整性约束关系模型中可以有3类完整性约束：实体完整性约束、参照完整性约束和用户定义的完整性约束。 其中前两种完整性约束是关系模型由关系数据库系统自动支持； 用户定义的完整性约束是用户使用由关系数据库提供的完整

178、性约束语言来设定写出约束条件， 运行时由系统自动检查。在这3种完整性约束中，前两种约束是任何一个关系数据库都必须满足的，由关系数据库管理系统自动支持。( 1 ) 实体完整性约束(Entity Integrity Constraint)该约束要求关系的主键中属性值不能为空值，这是数据库完整性的最基本要求。( 2 ) 参照完整性约束(Reference Integrity Constraint)该约束是关系之间相关联的基本约束，它不允许关系引用不存在的元组；即在关系中的外键要么是所关联关系中实际存在的元组，要么就为空值。( 3 ) 用户定义的完整性约束(User defined Integrity

179、 Constraint)用户定义的完整性就是针对某一具体关系数据库的约束条件。它反映某一具体应用所涉及的数据必须满足的语义要求。 例如，某个属性的取值范围在广200之间，某个属性必须取唯一值等。4 .3 关系代数关系数据库系统的特点之一是，它是建立在数学理论基础之上的，有很多数学理论可以表示关系模型的数据操作， 其中最为著名的是关系代数与关系演算。4.3.1 关系代数的基本操作关系代数是一种抽象的查询语言， 是关系数据操作语言的一种传统表达方式，它是用对关系的运算来表达查询的。任何一种运算都是将一定的运算符作用于一定的运算对象上， 得到预期的运算结果。 所以运算对象、 运算符和运算结果是运算的

180、三大要素。关系代数的运算对象是关系， 运算结果也是关系。关系代数的运算符包括暧：集合运算符、专门的关系运算符、算术比较符和逻辑运算符，如表4-4所示。表4-4 关系代数运算符种类运算符含义种类运算符含义集合运算符U并比较运算符大于大于等于n交 -系赵刚男建筑新闻张圆女通俗建筑王晓男电子通信李健男数学电子李文男建筑数学图4 1 2投影运律示意图选择运算。从关系中找出满足给定条件的元组的操作称为选择。选择的条件以逻辑表达式给出， 使得逻辑表达式为真的元组将被选取。 选择是在二维表中选出符合条件的行，形成新的关系的过程。选择运算用公式表示为：oF (R) =t I t GR且F ( t ) 为真其中

181、，F表示选择条件，它是一个逻辑表达式，取逻辑值“ 真 或慨。逻辑表达式F由逻辑运算符、A V 连接各算术表达式组成。算术表达式的基本形式为：X0Y其中，e表示比较运算符 、 、 = 或 九 x、Y等是属性名，或为常量，或为简单函数；属性名也可以用它的序号来代替。例如， 在关系R中选择出“ 系“ 为“ 建筑 的学生， 表示为眸建筑(R),得到新的关系S , 如图4-13所示。笛卡儿积运算。设有n元关系R和m元关系S , 它们分别有p和q个元组，贝尔与S的笛卡尔积记为：RxS它是一个m+n元关系，元组个数是pxq。关系R和关系S笛卡尔积运算的结果改口图4-14所示。4 .3 .3关系代数的扩充运算

182、关系代数中除了上述几个最基本的运算外，为操纵方便还需要增添一些称为扩充运算，这些运算均可由基本运算导出。常用的扩充运算有交、除、连接及自然连接等。(1 )交运算假设有n元关系R和n元关系S ,它们的交仍然是一个n元关系，它由属于关系R且由属于关系S的元组组成， 并记为R n s。 交运算是传统的集合运算，但不是基本运算，它可由基本运算推导而得：RAS=R-(R-S)对图4-14中的R和S做交运算的结果如图4-15所示。图4-15 R ns运算示例ABcba19df22(2) 除运算除运算可以近似地看作笛卡尔积的逆运算。当SxT=R时，则必有R+S=T, T称为R除以S的商。除法运算不是基本运算

183、，它可以由基本运算推导而得。设关系R有属性M i，M2, . Mn ,关系S有属性M e i，Mn_s+2, Mn,此时有：R + S = 7 l|V ll，M2 . Mn-s(R)- nM l ，M2 . . M n -s (n M l，M2 . M n-s(R )xS )设有关系R、S ,如图4-18 ( a )、( b )所示，求丁= 酎5 ,结果见图4-18 (c) o_ _ _ _ _ _ _ _ _ _ _ _ / ? 关系_ _ _ _ _ _ _ _ _ _ _ _ s关系ABCDab19dab20fab18bbc20fbc22dcd19dcd20fCD19d20f(b)T=R

184、 + SABabcd(a) (c)图4 1 8除运tZ示例(3 )连接与自然连接运算连接运算也称e连接，是对两个关系进行的运算，其意义是从两个关系的笛卡尔积中选择满足给定属性间一定条件的那些元组。设m元关系R和n元关系S,贝R和S两个关系的连接运算用公式表示为：R8A0BS它的含义可用下式定义：RoSA0B=aAeB (RxS)其中，A和B分别为R和S上度数相等且可比的属性组。连接运算从关系R和关系S的笛卡尔积RxS中，找出关系R在属性组A上的值与关系S在属性组B上值满足0关系的所有元组。当e为” = 时，称为等值连接。当e为 时 ，称为小于连接。当e为 时，称为大于连接。需要注意的是，在。

185、连接中，属性A和属性B的属性名可以不同，但是域一定要相同，否则无法比较。设有关系R 和关系S ,如图4-16(a)、(b)所不，对图中的关系R和关系S做连接运算的结果见图4-16(c)、(d)。在实际应用中，最常用的连接是一个叫自然连接的特例。自然连接要求两个关系中进行比较的是相同的属性，并且进行等值连接，相当于e恒为” = ，在结果中还要把重复的属性列去掉。自然连接可记为：RoS设有关系R 和关系S , 如图4-17(a)、(b)所示，贝 ! jRS的结果见图4-17 (c) o_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ / ? 关系_ _ _ _ _ _ _ _ _ _

186、 _ _ _ _ _ S关系ABCDabb20bad21cdf17EF19d20f18h(a) (b)R 8s R8st* MABCDEFabb2020f(d)ABCDEFabb2019dabb2018hbad2119dbad2120fbad2118h图4 1 6 连接运舞示例4 .4 数据库的设计与管理4.4.1数据库设计概述（ 1）数据库设计的概念数据库设计是指对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能够有效地存储数据，满足各种用户的应用需求（ 信息要求和处理要求）。从数据库设计的定义可以看出，数据库设计的基本任务是根据用户对象的信息需求（ 对数据库的静态

187、要求）、处理需求（ 对数据库的动态要求） 和数据库的支持环境（ 包括硬件、 操作系统与DBMS）设计出数据模式。数据库设计的根本目标是要解决数据共享问题。（2）数据库设计方法数据库设计中有两种方法，一种是以信息需求为主，兼顾处理需求，称为面向数据的方法（data-oriented approach）；另一种方法是以处理需求为主，兼顾信息需求，称为面向过程的方法（ process-oriented a叩roach）。其中，面向数据的方法是主流的设计方法。（ 3）数据库设计的步骤数据库设计目前一般采用生命周期法，即将整个数据库应用系统的开发分解成目标独立的若干阶段。 它们是需求分析阶段、概念设计阶

188、段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。 在数据库设计中采用上面几个阶段中的前4个阶段， 并且主要以数据结构与模型的设计为主线， 如图4-19所示。图4 1 9数据库设计的4个阶段4.4.2数据库设计的需求分析需求分析简单地说就是分析用户的要求，需求分析是设计数据库的起点，需求分析的结果是否准确地反映了用户的实际要求， 将直接影响到后面各个阶段的设计，并影响到设计结果是否合理和实用。4.4.2.1 需求分析任务需求阶段的任务是通过详细调查现实世界要处理的对象（ 组织、部门、企业等），充分了解原系统（ 手工系统或计算机系统）工作概况，明确用户的各种需求。在此

189、基础上确定新系统的功能。新系统必须充分考虑今后可能的扩充和改变， 不能仅仅按当前应用需求来设计数据库。4.4.Z.2需求分析步骤进行需求分析首先是调查清楚用户的实际要求，与用户达成共识。调查用户需求的步骤：(1)调查组织机构情况。包括了解组织部门的组成情况、职责等；(2)调查各部门的业务活动情况。包括各个部门输入和使用什么数据、 如何加工处理这些数据、 输出什么信息、 输出到什么部门、输出结果的格式是什么；(3)在熟悉业务活动的基础上，协助用户明确对新系统的各种要求。包括信息要求、处理要求、完全性与完整性要求；(4)对前面调查的结果进行初步分析。确定新系统的边界；确定哪些功能由计算机完成或将来

190、准备让计算机完成、 哪些活动由人工完成。由计算机完成的功能就是新系统应该实现的功能。4.4.3数据库概念设计4.4.3.1 数据库概念设计概述数据库概念设计的目的是分析数据间内在语义的关联，在此基础上建立一个数据的抽象模型。数据库概念设计的方法有以下两种。(1)集中式模式设计法即根据需求由一个统一机构或人员设计一个综合的全局模式。它强调统一与一致， 适用于小型或并不复杂的单位或部门， 而对大型的或语义关联复杂单位则并不适合。(2)视图集成设计法即将一个单位分解成若干个部分，先对每个部分作局部模式设计，建立各个部分的视图，然后以各视图为基础进行集成。视图集成设计法是一种由分散到集中的方法，它的设

191、计过程复杂但它能较好地反映需求，适合于大型与复杂的单位。4.43.2数据库概念设计过程概念设计最常用的方法就是P.PSChen于1976年提出的实体- 联系方法，简称E-R方法。它采用E-R模型，将现实世界的信息结构统一由实体、属性以及实体之间的联系来描述。它按照” 视图集成设计法” 分为选择局部应用、视图设计和视图集成3个步骤( 1 )选择局部应用根据系统的具体情况，在多层的数据流图中选择一个适当层次的数据流图， 让这组图中每一部分对应一个局部应用，以这一层次的数据流图为出发点，设计分E-R图。(2)视图设计视图设计的策略通常有以下3种。自顶向下。即先从抽象级别高且普遍性强的对象开始逐步细化

192、、具体化与特殊化。由底向上。即先从具体的对象开始，逐步抽象，普遍化与一般化，最后形成一个完整的视图设计。由内向外。即先从最基本与最明显的对象着手，逐步扩充至非基本、不明显的其他对象。(3)视图集成视图集成的实质是将所有的局部视图统一合并成一个完整的数据模式。 在进行视图集成时， 最重要的工作便是解决局部设计中的冲突。常见的冲突有下列几种：命名冲突。命名冲突有同名异义和同义异名两种。概念冲突。同一概念在一处为实体而在另一处为属性或联系。域冲突。相同的属性在不同视图中有不同的域，有些属性采用不同度量单位也为属域冲突。约束冲突。不同的视图可能有不同的约束。视图经过合并生成的是初步E-R图，其中可能存

193、在冗余的数据和冗余的实体间联系。冗余数据和冗余联系容易破坏数据库的完整性，给数据库维护增加困难。因此，对于视图集成后所形成的整体的数据库概念结构还必须进一步验证，确保它能满足下列条件：整体概念结构内部必须具有一致性，即不能存在互相矛盾的表达；整体概念结构能准确地反映原来的每个视图结构， 包括属性、实体及实体间的联系；整体概念结构能满足需求分析阶段所确定的所有需求；整体概念结构最终还应该提交给用户，征求用户和有关人员的意见，进行评审、修改和优化，然后把它确定下来作为数据库的概念结构，作为进一步设计数据库的依据。4.4.4数据库的逻辑设计概念结构是各种数据模型的共同基础， 为了能够用某一DBMS实

194、现用户需求， 还必须将概念结构进一步转化为相应的数据模型，这正是数据库逻辑结构设计所要完成的任务。4.4.4.1 从E-R图向关系模式转换采用E-R方法得到的全局概念模型是对信息世界的描述，并不适用于计算机处理，为了适合关系数据库系统的处理，必须将E-R图转换成关系模式。这就是逻辑设计的主内容。E-R图是由实体、属性和联系组眩而关系模式中只有一种元素- 关系。通常转换的方法如表4-5所示。表4-5 E-R模型与关系间的比较表ER模型关系模型2 R模型关系模型实体元蛆属性屋性实体集关系联系关系关系关系模式中的命名可以用E-R图原有名称，也可另行命名，但是应尽量避免重名， 关系数据库管理系统一般只

195、支持有限种数据类型而E-R中的属性域则不受此限制，如出现关系数据库管理系统不支持的数据类型时就需要进行类型转换。E-R图中允许出现非原子属性，但在关系模式中一般不允许出现非原子属性，非原子属性主要有集合型和元组型。 如出现此种情况可以进行转换， 其转换方法是集合属性纵向展开而元组属性横向展开。4.4.4.2逻辑模式规范化及调整、实现在逻辑设计中还需对关系做规范化验证，规范化设计的主要步骤为：确定数据依赖；用关系来表示ER图中每一个实体，每个实体对应一个关系模式；对于实体之间的那些数据依赖进行极小化处理；对于需要进行分解的关系模式可以采用一定的算法进行分解，对产生的各种模式进行评价，选出较合适的

196、模式。此外，还需对逻辑模式做适应RDBMS限制条件的修改。调整性能以减少连接运算；调整关系大小，使每个关系数量保持在合理水平，从而可以提高存取效率；尽量使用快照（ Snapshot）4.4.43关系视图设计关系视图设计又称外模式设计，也就是用户子模式设计。关系视图是建立在关系模式基础上的直接面向用户的视图（ View）, 目前关系数据库管理系统一般都提供了视图的功能。关系视图具有以下几个优点。提供数据逻辑独立性。逻辑模式发生变化时，只需改动关系视图的定义即可，无需修改应用程序，因此，关系视图保证了数据逻辑独立性。能适应用户对数据的不同需求。关系视图可以屏蔽掉用户不需要的数据，而将用户所关心的部

197、分数据呈现出来。有一定数据保密功能。关系视图为每个用户划定了访问数据的范围，从而在应用的各用户间起了一定的保密隔离作用。4.4.5数据库的物理设计4.4.5.1数据库物理设计的内容数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。为一个给定的逻辑数据模型选取一个最适合应用环境的物理结构的过程，就是数据库的物理设计。设计物理数据库结构的准备工作：充分了解应用环境， 详细分析要运行的事务，以获得选择物理数据库设计所需参数；充分了解所用RDBMS的内部特征，特别是系统提供的存取方法和存储结构。物理设计的内容主要包括：为关系模式选择存取方法。 数据库系统是多用户共享

198、的系统,对同一个关系要建立多条存取路径才能满足多用户的多种应用要求。 物理设计的任务之一就是要确定选择哪些存取方法，即建立哪些存取路径。常用的存取方法有3类：索引方法、集簇方法和HASH方法。设计关系、索引等数据库文件的物理存储结构。 确定数据库的物理结构主要确定数据的存放位置和存储结构， 包括确定关系、索引、 集簇、日志、 备份等的存储安排和存储结构； 确定系统配置等。4.4.5.2数据库物理设计的步骤确定数据库的物理结构，确定数据的存放位置和存储结构包括关系、索引、集簇、日志、备份等的存储安排和存储结构；确定存储配置等。对物理结构进行评价，评价的重点是时间和空间效率。对数据库物理设计过程中

199、产生的多种方案进行细致的评价， 从中选择一个较优的方案作为数据库的物理结构。如果评价结果满足原设计要求则可进入到物理实施阶段， 否则,就需要重新设计或修改物理结构， 有时甚至要返回逻辑设计阶段修改数据模型。评价方法：定量估算各种方案的存储空间、存取时间、维护代价；对估算结果进行权衡、比较，选择出一个较优的合理的物理结构。4.4.6数据库管理数据库是一种共享资源，它需要维护与管理，这种工作称为数据库管理(DataBase Administration), 实施管理的人称为数据库管 理 员 ( DataBase Administrator D B A )。数据库管理一般包括：数据库的建立、数据库的

200、调整、数据库的重组、数据库的安全性控制与完整性控制、数据库的故障恢复和数据库的监控。4.4.6.1 建立数据库数据库的建立包括数据模式的建立和数据加载。DBA利用RDBMS中的DDL语言申请空间资源，定义数据库名，定义表及其属性，定义视图，定义主关键字、索引、完整性约束等。在数据模式定义后，DBA编制加载程序将外界数据加载至数据模式内，完成数据库的建立。4.4.6.2 数据库的调整在数据库的调整方面，DBA需要执行的操作有：调整关系模式与视图使之更能适应用户的需求；调整索引与集簇使数据库性能和效率更好；调整分区、数据库缓冲区大小以及并发度使数据库物理性能更好。4.4.63数据库的重组对数据库进

201、行重新整理，重新调整存储空间的工作称为数据库重组。实际中，一般是先做数据卸载，然后重新加载来达到数据重组的目的。4.4.6.4数据库的安全性控制与完整性控制数据库安全性控制需由DBA采取措施予以保证, 数据不能受到非法盗用和破坏。 数据库的完整性控制可以保证数据的正确性， 使录入库内的数据均能保持正确。4.4.6.5 数据库的故障修复如果数据库中的数据遭受破坏， RDBMS应该提供故障恢复功能,一般由DBA执行。4.4.6.6 数据库监控DBA必须严密观察数据库的动态变化， 数据库监控是进行数据库管理的基础，使得DBA在出现特殊情况（ 如发生错误和故障） 时能及时采取相应的措施。同时，DBA还需监视数据库的性能变化，在必要时对数据库作调整。