第1章 数据结构与算法
1.1 算法
1.1.1 算法的基本概念
算法是指对解题方案的准确而完整的描述。简单地说，就是解决问题的操作步骤。
值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法，用某种表达方式（如流程图）描述，然后再用具体的程序设计语言描述此算法（即编程）。在编程时由于要受到计算机系统运行环境的限制，因此，程序的编制通常不可能优于算法的设计。 1.1.1.1 算法的基本特征
一般来说，一个算法应具有以下4个基本特征。 （1）可行性（Effectiveness）：算法在特定的执行环境中执行，应当能够得出满意的结果，即必须有一个或多个输出。 （2）确定性（Definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。
（3）有穷性（Finiteness）：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。
（4）拥有足够的情报：要使算法有效必需为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。 1.1.1.2 算法的基本要素
通常，一个算法由两种基本要素组成。 对数据对象的运算和操作；
算法的控制结构，即运算或操作时间的顺序。 （1） 算法中对数据的运算和操作
在一般的计算机系统中，基本的运算和操作有以下4类，如表1-1所示。 表1-1 4类基本的运算和操作 运算类 操作 实 例 型 算术运算 ＋、－、×、÷ a＋b、3－1 逻辑运算 与（&）、或（‖）、非（！） ！1、1‖0、1&1 关系运算 ＞＜＝≠ a>b、a=c 、b≠c 数据传输 赋值、输入、输出 a=0、b=3 （2） 算法的控制结构 一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。
算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 1.1.1.3 算法设计的基本方法
虽然设计算法是一件非常困难的工作，但是算法设计也不是无章可循，人们经过实践，总结和积累了许多行之有效的方法。常用的几种算法设计方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。 1.1.1.4 算法设计的要求
通常一个好的算法应达到如下目标： （1）正确性（Correctness）
正确性大体可以分为以下4个层次： ①程序不含语法错误；
②程序对于几组输入数据能够得出满足规格说明要求的结果；
③程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；
④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 （2）可读性（Readability）
算法主要是为了方便人的阅读与交流，其次才是其执行。可读性好有助于用户对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。 （3）健壮性（Robustness）
当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
（4）效率与低存储量需求
效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间。
1.1.2 算法的复杂度
算法的复杂度是算法效率的度量，是评价算法优劣的重要依据。 算法复杂度包括算法的时间复杂度和算法的空间复杂的。 1.1.2.1 算法的时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。
为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。
算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是问题规模（通常用整数n表示）的函数。即
算法的工作量=f（n）
例如，在N×N矩阵相乘的算法中，整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，也就是时间复杂度为n3，即
f（n）=O（n3）
在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时，基本操作的执行次数为0；当初始序列为自大至小有序时，基本操作的执行次数为n（n－1）/2。对这类算法，可以采用平均性态和最坏情况复杂性两种方法来分析。 1.1.2.2 算法的空间复杂度
算法的空间复杂度是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（in place）工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
1.2.1 数据结构的定义
数据结构是计算机科学与技术领域广泛使用的一个基本术语，用来反映数据的内部构成。在给出数据结构的定义之前，我们先弄清楚几个概念。
数据（data）：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（data element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑
和处理。
数据对象（data object）：是性质相同的数据元素的集合，是数据的一个子集。
简单地说， 数据结构是指相互关联的数据元素的集合，即数据的组织形式。所谓结构，就是指数据元素之间的前后件关系（或称直接前驱与直接后继关系）。
例如，在考虑一日三餐的时间顺序关系时，\"早餐\"是\"午餐\"的前件（或直接前驱），而\"午餐\"是\"早餐\"的后件（或直接后继）；同样，\"午餐\"是\"晚餐\"的前件，\"晚餐\"是\"午餐\"的后件。
又例如，在考虑学历的顺序关系时，\"小学\"是\"初中\"的前件，而\"初中\"是小学的后件。同样，\"初中\"是\"高中\"的前件，\"高中\"是\"初中\"的后件。
前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。
数据结构的两个要素--\"数据\"和\"结构\"是紧密联系在一起的，\"数据\"是有结构的数据，而不是无关联的、松散的；而\"结构\"就是数据元素间的关系，是由数据的特性所决定的。
数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：
（1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。
讨论以上问题的目的是为了提高数据处理的效率，即提高数据处理的速度以及尽量节省在数据处理过程中所占用的计算机存储空间。 1.2.1.1 数据的逻辑结构
由数据结构的定义可知，一个数据结构应包含以下两方面信息： （1）表示数据元素的信息；
（2）表示各数据元素之间的前后件关系。
在此定义中，并没有考虑数据元素的存储，所以上述的数据结构实际上是数据的逻辑结构。 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。
数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成
B=（D，R）
其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。 例如，如果把一日三餐看作一个数据结构，则可表示成 B=（D，R）
D={早餐，午餐，晚餐} R={（早餐，午餐），（午餐，晚餐）}
数据的逻辑结构包括线性结构、树型结构图、网状结构图和集合图4种。 1.2.1.2 数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。在进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，而且各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能不同。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。
1.2.3 线性结构与非线性结构
如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在只有一
个数据元素的数据结构中，删除该数据元素，就得到一个空的数据结构；在一个空的数据结构中插入一个新的元素后变成非空。
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。
线性结构又称为线性表。由此可见，在线性结构中，各数据元素之间的前后件关系是很简单的。
需要特别说明的是，在一个线性表中插入或删除任何一个结点后还应是线性结构。
如果一个数据结构不是线性结构，则称之为非线性结构。在非线性结构中，各数据元素之间的前后件关系要比线性结构复杂。链式结构是总常用的非线性结构。
线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。
1.3.2 线性表的顺序存储结构
通常，线性表可以采用顺序存储和链式存储，本小节主要讨论顺序存储结构。 线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构具备如下两个基本特征： （1）线性表中的所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
用顺序存储结构存储的线性表称为顺序表。在顺序表中，其前、后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
如长度为n的线性表（a1，a2，…，ai，…，an）的顺序存储如图1-6所示。
在顺序表中，如果每个元素占有K个存储单元，则下标为i+1的元素的存储位置与下标为i的元素的存储位置之间，满足下列关系：
ADR（ai+1）=ADR（ai）+K
通常把顺序表中第1个数据元素的存储地址ADR（a1）称为线性表的首地址，线性表中第i个元素ai的存储地址为：
ADR（ai）=ADR（a1）+（i-1）K
例如，在顺序表中存储数据（14，23，25，78，15，68，27），每个数据元素占有2个存储单元，第1个数据元素14的存储地址是200，则第3个数据元素25的存储地址是：
ADR（a3）=ADR（a1）+（3-1）×2=200+4=204
从这种表示方法可以看到，它是用元素在计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。
1.4.1 栈及其基本运算
1．栈的定义
栈（Stack）是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。
例如，枪械的子弹匣就可以用来形象地表示栈结构。如图1-9(a)所示，子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。
在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。当栈中没有元素时，称为空栈。例如，没有子弹的子弹匣为空栈。
通常用指针top来指示栈顶的位置，用指针bottom来指向栈底。 假设栈S=（a1，a2，…，an），则称a1 为栈底元素，an为栈顶元素。栈中元素按a1，a2，…，an的次序进栈，退栈的第一个元素应为栈顶元素an。图1-9(b)是栈的入栈、退栈示意图。
2．栈的特点
根据栈的上述定义，栈具有以下特点。
栈的修改原则是\"后进先出\"（Last In First Out，LIFO） 或\"先进后出\"（First In Last Out，FILO），因此，栈也称为\"后进先出\"表或\"先进后出\"表。
3．栈的基本运算
栈的基本运算包括入栈、退栈和读栈定元素。
（1）入栈运算
入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加1（即top加1），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈\"上溢\"错误。 （2）退栈运算
退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）
赋给一个指定的变量，然后将栈顶指针减1（即top减1）。当栈顶指针为0时，说明栈空，不可进行退栈操作。这种情况称为栈的\"下溢\"错误。 （3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。
图1-10所示是一个顺序表示的栈的动态示意图。随着元素的插入和删除，栈顶指针top反应了栈的状态不断地变化。
1.4.2 队列及其基本运算
1.4.2.1 队列的定义及运算
队列也是一种特殊的线性表。
队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许进行删除运算的一端称为队头（或排头），允许进行插入运算的一端称为队尾。若有队列：
Q=（q1，q2，…，qn）
那么，q1为队头元素（排头元素），qn为队尾元素。队列中的元素是按照q1，q2，…，qn的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在q1，q2，…，qn-1都退队之后，qn才能退出队列。因最先进入队列的元素将最先出队，所以队列具有\"先进先出\"的特性，体现\"先来先服务\"的原则。
队头元素q1是最先被插入的元素，也是最先被删除的元素。队尾元素qn是最后被插入的元素，也是最后被删除的元素。因此，与栈相反，队列又称为\"先进先出\"（First In First Out，FIFO） 或\"后进后出\"（Last In Last Out，LILO）的线性表。
例如，火车进隧道，最先进隧道的是火车头，最后进的是火车尾，而火车出隧道的时候也是火车头先出，火车尾后出。
可以用顺序存储的线性表来表示队列，为了指示当前执行退队运算的队头位置，需要一个队头指针（排头指针）front，为了指示当前执行入队运算的队尾位置，需要一个队尾指针rear。排头指针front总是指向队头元素的前一个位置，而队尾指针rear总是指向队尾元素。
往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。
1.4.2.2 循环队列及其运算
在实际应用中，队列的顺序存储结构一般采用循环队列的形式。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。
在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
一维数组（1:m），最大存储空间为m，数组（1:m）作为循环队列的存储空间时，循环队列的初始状态为空，即front=rear=m，图1-13所示是循环队列初始状态的示意图。循环队列的初始状态为空，即front=rear=m。
循环队列主要有两种基本运算：入队运算和退队运算。 （1）入队运算
入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进1（即rear=rear+1），并当rear=m+1时置rear=1；然后将新元素插入到队尾指针指向的位置。
例如，在图1-14(a)中进行入队运算，首先队尾指针进1，此时rear=m+1，置rear=1，则在第１个位置上插入数据a，见图1-14(b)；当插入第２个数据b时，队尾指针进１，rear=2，在第2个位置上插入数据b，依此类推，直到把所有的数据元素插入完成，见图1-14(c)所示。 （2）退队运算
退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进1（即front=front+1），并当front=m+1时，置front=1；然后将排头指针指向的元素赋给指定的变量。
例如，在图1-14(c)中进行退队运算时，排头指针进1（即front+1），此时front=m+1，置front=1，删除此位置的数据，即数据a。
1.5.1.1 线性链表的基本概念
在链式存储结构中。存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可以表示非线性结构。
线性表的链式存储结构称为线性链表。由于这种链表中，每个结点只有一个指针域，故又称为单链表。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。如图1-15所示。
从图1-14(a)和图1-14(c)可以看出，循环队列在队列满时，和队列空时都有front=rear，如何区分循环队列是空还是满的呢？在实际应用中，通常增加一个标志量S，S值的定义如下：
循环队列为空时S=0 循环队列为非空时S=1
由此可以判断队列空和队列满这两种情况。
当S=0时，循环队列为空，此时不能再进行退队运算，否则会发生\"下溢\"错误。
当S=1时，并且front=rear时，循环队列满。此时不能再进行入队运算，否则会发生\"上溢\"错误。
在定义了S以后，循环队列初始状态为空，表示为：S=0，且front=rear=m。
1.6.2.1 二叉树的定义
二叉树是由n（n≥0）个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。
二叉树具有以下两个特点：
（1）非空二叉树只有一个根结点；
（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有5种不同的形态，如图1-26所示。
图1-26(a)表示空二叉树；图1-26(b)是仅有根结点的二叉树，即左子树和右子树都为空二叉树；图1-26(c)是左、右子树均非空的二叉树；图1-26(d)是左子树非空，右子树为空的 二
叉树；图1-26(e)是右子树非空，左子树为空的二叉树。
在二叉树中，当一个非根结点的结点，既没有右子树，也没有左子树时，该结点即是叶子结点。
1.6.2.2 二叉树的基本性质
二叉树具有以下几个性质：
性质1：在二叉树的第k层上至多有2k-1（k≥1）个结点。 性质2：深度为m的二叉树至多有2m-1个结点。
深度为m的二叉树表示该二叉树共有m层。根据性质1，只要将第1层到第m层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，及21-1+22-1+…+2m-1=2m-1。
性质3： 对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。 证明：设一棵非空二叉树中有n个结点，叶子结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2。
所以：
n=n0＋n1＋n2 （1）
在二叉树中，除根结点外，其余每个结点都有且仅有一个前件（直接前驱）和一条从其前件结点指向它的边。假设边的总数为B，则二叉树中总的结点数为：
n＝B＋1 （2）
由于二叉树中的边都是由度为1和度为2的结点发出的。所以有：
B=n1＋n2×2 （3）
综合（1）、（2）、（3）式，可得：n0=n2 +1
性质4： 具有n个结点的完全二叉树的深度至少为［log2n］+1，其中［log2n］表示log2n的整数部分。
1.6.2.3 满二叉树与完全二叉树
满二叉树和完全二叉树是两种特殊形态的二叉树。 （1）满二叉树
满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树的第k层上有2k-1个结点。
从上面满二叉树定义可知，必须是二叉树每一层上的结点数都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。
图1-23是两棵满二叉树。图1-23(a)是深度为3的满二叉树，图1-23(b)是深度为4的满二叉树。
图1-23 满二叉树
在满二叉树中，只有度为2和度为0的结点，没有度为1的结点。所有度为0的结点即叶子结点都在同一层，即最后一层。 （2）完全二叉树
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
完全二叉树也可以这样来描述：如果对满二叉树的结点进行连续编号，从根结点开始，对二叉树的结点自上而下，自左至右用自然数进行连续编号，则深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点一一对应时，称之完全二
叉树。
由完全二叉树可知，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。 图1-28(a)是深度为3的3棵完全二叉树，图1-28(b)是深度为4的一棵完全二叉树。
完全二叉树还具有以下两个性质：
性质1：具有n个结点的完全二叉树深度为［log2n］+1。
性质2： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第［log2n］+1层，每层从左到右）,则对任一结点k（1≤k≤n），有： ①如果k＝1，则结点k父结点，是二叉树的根；如果k>1，则该结点的父结点编号为INT（k/2）； ②如果2k≤n，则结点k的左子结点编号为2k；否则该结点没有左子结点（显然也没有右子结点）；
③如果2k+1≤n，则结点k的右子结点编号为2k+1；否则该结点没有右子结点。
1.6.3 二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。
在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序不同，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。
1．前序遍历
前序遍历中\"前\"的含义是：访问根结点在访问左子树和访问右子树之前。即首先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左子树和右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
前序遍历可以描述为：若二叉树为空，则执行空操作；否则①访问根结点，②前序遍历左子树，③前序遍历右子树。
例如，对图1-30中的二叉树进行前序遍历的结果（或称为该二叉树的前序序列）为：A，B，D，H，E，I，C，F，G。
2．中序遍历
中序遍历中\"中\"的含义是：访问根结点在访问左子树和访问右子树两者之间。即首先遍历左子树，然后访问根结点，最后遍历右子树。并且在遍历左子树和右子树时，仍然首先遍历左子树，然后访问根结点，最后遍历右子树。
中序遍历可以描述为：若二叉树为空，则执行空操作；否则①中序遍历左子树，②访问根结点，③中序遍历右子树。
例如，对图1-30中的二叉树进行中序遍历的结果（或称为该二叉树的中序序列）为：H，D，B，E，I，A，C，G，F。
3．后序遍历
后序遍历中\"后\"的含义是：访问根结点在访问左子树和访问右子树之后。即首先遍历左子树，然后遍历右子树，最后访问根结点；并且在遍历左子树和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根结点。
后序遍历可以描述为：若二叉树为空，则执行空操作；否则①后序遍历左子树，②后序遍历右子树，③访问根结点。
例如，对图1-30中的二叉树进行后序遍历的结果（或称为该二叉树的后序序列）为：H，D，I，E，B，G，F，C，A。
1.7.1.1 顺序查找
顺序查找（顺序搜索）是最简单的查找方法，它的基本思想是：从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较，如果相等，则查找成功，停止查找；若整个线性表扫描完毕，仍未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败。
在进行顺序查找过程中，如果线性表中的第一个元素就是要查找的元素，则比较次数为1；如果最后一个元素才是要找的元素，或者在线性表中，没有要查找的元素，则需要与线性表中所有的元素比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。
由此可以看出，对于大的线性表来说，顺序查找的效率很低。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：
（1）如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 1.7.1.2 二分法查找
二分法查找也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足两个条件：
●用顺序存储结构； ●线性表是有序表。
在本书中，为了简化问题，而更方便讨论，\"有序\"是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。下一节排序中，有序的含义也是如此。
对于长度为n的有序线性表，利用二分法查找元素X的过程如下。 将X与线性表的中间项比较：
●如果X的值与中间项的值相等，则查找成功，结束查找；
●如果X小于中间项的值，则在线性表的前半部分以二分法继续查找； ●如果X大于中间项的值，则在线性表的后半部分以二分法继续查找。 例如，长度为8的线性表关键码序列为：［5，12，26，29，37，45，46，69］，被查元素为37，首先将与线性表的中间项比较，即与第4个数据元素29相比较，37大于中间项29的值，则在线性表［37，45，46，69］继续查找；接着与中间项比较，即与第2个元素45相比较，37小于45，则在线性表［37］继续查找，最后一次比较相等，查找成功。
顺序查找法每一次比较，只将查找范围减少1，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。
可以证明，对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。
1.8.1.1 冒泡排序法
冒泡排序法是最简单的一种交换类排序方法。在数据元素的序列中，对于某个元素，如果其后存在一个元素小于它，则称之为存在一个逆序。
冒泡排序（Bubble Sort）的基本思想就是通过两两相邻数据元素之间的比较和交换，不断地消去逆序，直到所有数据元素有序为止。
冒泡排序法的基本过程如下：
第一遍，在线性表中，从前往后扫描，如果相邻的两个数据元素，前面的元素大于后面的元素，则将它们交换，并称为消去了一个逆序。在扫描过程中，线性表中最大的元素不断的往后移动，最后，被交换到了表的末端。此时，该元素就已经排好序了。
然后对当前还未排好序的范围内的全部结点，从后往前扫描，如果相邻两个数据元素，后面的元素小于前面的元素，则将它们交换，也称为消去了一个逆序。在扫描过程中，最小的元素不断地往前移动，最后，被换到了线性表的第一个位置，则认为该元素已经排好序了。
对还未排好序的范围内的全部结点，继续第二遍，第三遍的扫描，这样，未排好序的范围逐渐减小，最后为空，则线性表已经变为有序了。
图1-31是一个冒泡排序法的例子。
在最坏情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n（n-1）/2。 1.8.1.2 快速排序法
在冒泡排序中，一次扫描只能确保最大的元素或最小的元素移到了正确位置，而未排序序列的长度可能只减少了1。快速排序（Quick Sort）是对冒泡排序方法的一种本质的改进。
快速排序的基本思想是：在待排序的n个元素中取一个元素K（通常取第一个元素），以元素K作为分割标准，把所有小于K元素的数据元素都移到K前面，把所有大于K元素的数据元素都移到K后面。这样，以K为分界线，把线性表分割为两个子表，这称为一趟排序。然后，对K前后的两个子表分别重复上述过程。继续下去，直到分割的子表的长度为1为止，这时，线性表已经是排好序的了。
第一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别指向线性表的第一个元素（K元素）和最后一个元素。首先从high所指的位置向前扫描，找到第一个小于K元素的元素并与K元素互相交换。然后从low所指位置起向后扫描，找到第一个大于K元素的数据元素并与K元素交换。重复这两步，直到low=high为止。
图1-32是一个快速排序法的例子。
快速排序的平均时间效率最佳，为O（nlog2n），最坏情况下，即每次划分，只得到一个子
2
序列，时间效率为O（n）。
1.8.2.1 简单选择排序法
简单选择排序（Simple Selection Sort）的基本思想是：首先从所有n个待排序的数据元素中选择最小的元素，将该元素与第1个元素交换，再从剩下的n-1个元素中选出最小的元素与第2个元素交换。重复这样的操作直到所有的元素有序为止。
对初始状态为（73，26，41，5，12，34）的序列进行简单选择排序过程如图1-33所示。图中方括号\"［ ］\"内为有序的子表，方括号\"［ ］\"外为无序的子表，每次从无序子表中取出最小的一个元素加入到有序子表的末尾。步骤如下：
从这6个元素中选择最小的元素5，将5与第1个元素交换，得到有序序列［ 5 ］；
从剩下的5个元素中挑出最小的元素12，将12与第2个元素交换，得到有序列［ 5，12 ］； 从剩下的4个元素中挑出最小的元素26，将26与第3个元素交换，得到有序序列［ 5，12，26 ］；
依此类推，直到所以的元素都有序地排列到有序的子表中。
简单选择排序法在最坏的情况下需要比较n（n-1）/2次。 1.8.2.2 堆排序法
堆排序属于选择类的排序方法。
（1）堆的定义
若有n个元素的序列（h1，h2，…，hn），将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时称为堆。
其中，i=1，2，3，…，n/2。
（1）情况称为小根堆，所有结点的值小于或等于左右子结点的值。（2）情况称为大根堆，所有结点的值大于或等于左右子结点的值。本节只讨论大根堆的情况。
例如，序列（91，85，53，36，47，30，24，12）是一个堆，则它对应的完全二叉树如图1-36所示。
（2）调整建堆
在调整建堆的过程中，总是将根结点值与左、右子树的根结点进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换，这个调整过程从根节点开始一直延伸到所有叶子结点，直到所有子树均为堆为止。
（3）堆排序
首先将一个无序序列建成堆，然后将堆顶元素与堆中的最后一个元素交换。不考虑已经换到最后的那个元素，将剩下的n-1个元素重新调整为堆，重复执行此操作，直到所有元素有序为止。
对于数据元素较少的线性表来说，堆排序的优越性并不明显，但对于大量的数据元素来说，堆排序是很有效的。
在最坏情况下，堆排序法需要比较的次数为O（nlog2n）。
1.8.3.1 简单插入排序法
简单插入排序是把n个待排序的元素看成是一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含另外n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n，而无序表为空，此时排序完成。
简单插入排序过程如图1-33所示。 图中方括号\"［ ］\"内为有序的子表，方括号\"［ ］\"外为无序的子表，每次从无序子表中取出第一个元素插入到有序子表中。
在最好情况下，即初始排序序列就是有序的情况下，简单插入排序的比较次数为n-1次，移动次数为0次。
在最坏情况下，即初始排序序列是逆序的情况下，比较次数为n（n-1）/2，移动次数为n（n-1）/2。假设待排序的线性表中的各种排列出现的概率相同，可以证明，其平均比较次数和平均移动次数都约为n2/4，因此直接插入排序算法的时间复杂度为O（n2）。
在简单插入排序中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。
第2章 程序设计基础
2.1程序设计方法与风格
2.1.2 良好的编程风格应注意的因素
程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思路。
良好的程序设计风格可以使程序结构清晰合理，程序代码便于维护，因此，程序设计风格深深地影响着软件的质量和维护。
要形成良好的程序设计风格，主要应注意和考虑下述一些因素。 （1）源程序的文档化
源程序文档化是指在源程序中可包含一些内部文档，以帮助阅读和理解源程序。 ①符号名的命名规则：符号名的命名应具有一定的实际含义，以便理解程序功能。
②程序注释：在源程序中添加正确的注释可帮助人们理解程序。程序注释可分为序言性注释和功能性注释，以给出程序的整体说明和程序的主要功能。
③视觉组织：可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。 （2）数据说明的方法
为使程序中的数据说明易于理解和维护，可采用下列数据说明的风格，见表2-1。 表2-1 数据说明风格 次序应规范化 变量安排有序化 使用注释 数据说明风格 使数据说明次序固定，使数据的属性容易查找，也有利于测试、排错和维护 当多个变量出现在同一个说明语句中时，变量名应按字母顺序排序，以便于查找 在定义一个复杂的数据结构时，应通过注释来说明该数据结构的特点 详细说明 （3）语句的结构
为使程序更简单易懂，语句构造应该简单直接，应注意如下原则： ①在一行内只写一条语句； ②程序编写应优先考虑清晰性；
③程序编写要做到清晰第一，效率第二； ④在保证程序正确的基础上再要求提高效率； ⑤避免使用临时变量而使程序的可读性下降； ⑥避免不必要的转移； ⑦尽量使用库函数；
⑧避免采用复杂的条件语句； ⑨尽量减少使用\"否定\"条件语句； ⑩数据结构要有利于程序的简化；
⑩要模块化，使模块功能尽可能单一化； ⑩利用信息隐蔽，确保每一个模块的独立性； ⑩从数据出发去构造程序；
⑩不要修补不好的程序，要重新编写。
（4）输入输出
输入输出方式和风格应尽可能方便用户的使用，应考虑如下原则： （1）对所有输入的数据都要检验数据的合法性； （2）检查输入项的各种重要组合的合理性；
（3）输入格式要简单，使得输入的步骤和操作尽可能简单； （4）输入数据时，应允许使用自由格式； （5）应允许默认值；
（6）输入一批数据时，最好使用输入结束标志；
（7）在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；
（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性。
2.2结构化程序
2.2.1 结构化程序设计的原则
结构化程序设计方法的重要原则是自顶向下、逐步求精、模块化及限制使用goto语句。 （1）自顶向下
程序设计时，先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。 （2）逐步求精
对复杂问题，应设计一些子目标做过渡，逐步细化。 （3）模块化
模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。
（4）限制使用goto语句
2.2.2 结构化程序的基本结构与特点
1966年，Boehm和Jacopini证明了程序设计语言仅仅使用顺序、选择和重复三种基本控制结构就足以表达出各种其他形式结构的程序设计方法。它们的共同特征是：严格地只有一个入口和一个出口。 （1）顺序结构
顺序结构是指按照程序语句行的先后顺序，自始至终一条语句一条语句地顺序执行，它是最简单也是最常用的基本结构。如图2-1所示，虚线框内就是一个顺序结构，在执行A中的运算后，必然执行B中的运算，然后执行C中的运算，没有分支，也没有转移和重复。 （2）选择结构
选择结构又称分支结构，简单选择结构和多分支选择结构都属于这类基本结构，这种结构可以根据设置的条件，判断应该选择哪一枝分支来执行相应的语句序列。图2-2虚线框内是一个简单选择结构。根据条件C判断，若成立则执行A中的运算，若不成立则执行B中的运算。
（3）重复结构
重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。
在程序设计语言中，重复结构对应两类循环语句，对先判断后执行的循环体称为当型循环结构；对先执行循环体后判断的称为直到型循环结构，如图2-4所示。
总之，遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的优点： ●程序易于理解、使用和维护；
●提高了编程工作的效率，降低了软件开发成本。
2.3面向对象的程序设计
2.3.2 面向对象方法的基本概念
关于面向对象方法，对其概念有许多不同的看法和定义，但是都涵盖对象及对象属性与方法、类、继承、多态性几个基本要素。 2.3.2.1 对象（公共基础）
对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体，也就是说，应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象。总之，对象是对问题域中某个实体的抽象。例如，书本、课桌、老师、电脑等都可以看做一个对象。
面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
客观世界中的实体通常既具有静态的属性，又具有动态的行为，因此，面向对象方法学中的对象是由描述该对象属性的数据以及可以对这些数据施加的操作封装在一起构成的统一体。对象可以执行的操作表示它的动态行为。
属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。 操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。 对象具有如下特点： ①标识唯一性：指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分； ②分类性：指可以将具有相同属性和操作的对象抽象成类； ③多态性：指同一个操作可以是不同对象的行为；
③封装性：从外面看只能看到对象的外部特征，而不知道也无需知道数据的具体结构以及实现操作的算法；
⑤模块独立性好：对象是面向对象的软件的基本模块，对象内部各种元素彼此结合得很紧密，内聚性强。
2.3.2.2 类和实例
类是具有共同属性、共同方法的对象的集合，是关于对象的抽象描述，反映属于该对象类型的所有对象的性质。一个具体对象则是其对应类的一个实例。
要注意的是：\"实例\"这个术语，必然是指一个具体的对象。\"对象\"这个术语，则既可以指一个具体的对象，也可以泛指一般的对象。因此，在使用\"实例\"这个术语的地方，都可以用\"对象\"来代替，而使用\"对象\"这个术语的地方，则不一定能用\"实例\"来代替。
例如，\"大学生\"是一个大学生类，它描述了所有大学生的性质。因此，任何大学生都是类\"大学生\"的一个对象（这里的\"对象\"不可以用\"实例\"来代替），而一个具体的大学生\"张三\"是类\"大学生\"的一个实例。
类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。 2.3.2.3 消息
消息传递是对象间通信的手段，一个对象通过向另一对象发送消息来请求其服务。
消息机制统一了数据流和控制流。消息的使用类似于函数调用。通常一个消息由下述3部
分组成：
●接收消息的对象名称；
●消息选择符（也称为消息名）； ●零个或多个参数。
消息只告诉接收对象需要完成什么操作，但并不指示怎样完成操作。消息完全由接收者解释，独立决定采用什么方法来完成所需的操作。
一个对象能够接收不同形式、不同内容的多个消息；相同形式的消息可以送往不同的对象，不同的对象对于形式相同的消息可以有不同的解释，能够作出不同的反应。一个对象可以同时往多个对象传递消息，两个对象也可以同时向某一个对象传递消息。消息传递如图2-4所示。
2.3.2.4 继承
继承是面向对象的一个主要特征。继承是使用已有的类定义作为基础建立新类的技术。已有的类可当作基类来应用，则新类相应地可当作派生类来引用。
广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。
例如，\"四边形\"类是\"矩形\"类的父类，\"四边形\"类可以有\"顶点坐标\"等属性，有\"移动\"、\"旋转\"、\"求周长\"等操作。而\"矩形\"类除了继承\"四边形\"类的属性和操作外，还可定义自己的属性和操作，\"长\"、\"宽\"等属性和\"求面积\"等操作。
继承具有传递性，如果类Z继承类Y，类Y继承类X，则类Z继承类X。因此，一个类实际上继承了它上层的全部基类的特性，也就是说，属于某类的对象除了具有该类定义的特性外，还具有该类上层全部基类定义的特性。
继承分为单继承与多重继承。单继承是指一个类只允许有一个父类，即类等价为树型结构。多重继承是指一个类允许有多个父类。多重继承的类可以组合多个父类的性质构成所需要的性质。
继承的优点是：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余信息，提高软件的可重用性，便于软件修改维护。另外，继承性使得用户在开发新的应用系统时不必完全从零开始，可以继承原有的相似系统的功能或者从类库中选取需要的类，再派生出新的类以实现所需的功能。 2.3.2.5 多态性
对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性。
在面向对象的软件技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。
例如，在一般类polygon（多边形）中定义了一个方法 \"Show\" 显示自身，但并不确定执行时到底画一个什么图形。特殊类square和类rectangle都继承了polygon类的显示操作，但其实现的结果却不同，把名为Show的消息发送给一个rectangle类的对象是在屏幕上画矩形，而将同样消息名的消息发送给一个square类的对象则是在屏幕上画一个正方形。如图2-6所示，这就是多态性的表现。
多态性机制不仅增强了面向对象软件系统的灵活性，进一步减少了信息冗余，而且显著提高了软件的可重用性和可扩充性。
第3章 软件工程基础
3.1 软件工程基本概念
3.1.1.1 软件的定义
计算机软件由两部分组成。
●一是机器可执行的程序和数据；
●二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。
软件的构成见表3-1。计算机软件是由程序、数据及相关文档构成的完整集合，它与计算机硬件一起组成计算机系统。
表3-1 计算机软件各组成部分的含义 概念 软件 程序 数据 文档 含 义 程序、数据和文档 软件开发人员依据用户需求开发的，用某种程序设计语言描述的，能够在计算机中执行的语句序列 使程序能够正常操纵信息的数据结构 与程序开发、维护和使用有关的资料 我国国家标准（简称国标，GB）中对计算机软件（Software）完整的定义是： 与计算机系统操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。 3.1.1.3 软件的分类
计算机软件按功能分为系统软件、应用软件、支撑软件（或工具软件）。
系统软件是管理计算机的资源，提高计算机的使用效率，为用户提供各种服务的软件。例如，操作系统（OS）、数据库管理系统（DBMS）、编译程序、汇编程序和网络软件等。系统软件是最靠近计算机硬件的软件。
应用软件为了应用于特定的领域而开发的软件。例如，我们熟悉的Word 2003、Winamp、QQ和Flashget等软件属于应用软件。
支撑软件是介于系统软件和应用软件之间，协助用户开发软件的工具型软件，其中包括帮助程序人员开发和维护软件产品的工具软件，也包括帮助管理人员控制开发进程和项目管理的工具软件。例如，Dephi、PowerBuilder等。 3.1.2.2 软件危机
随着计算机软件规模的扩大，软件本身的复杂性不断增加，研制周期显著变长，正确性难以保证，软件开发费用上涨，生产效率急剧下降，从而出现了人们难以控制软件发展的局面，即所谓的\"软件危机\"。软件危机主要表现在： （1）软件需求的增长得不到满足； （2）软件开发成本和进度无法控制； （3）软件质量难以保证；
（4）软件不可维护或维护程度非常低； （5）软件成本不断提高；
（6）软件开发生产效率的提高赶不上硬件的发展和应用需求的增长。 总之，可以将软件危机归结为成本、质量和生产率等问题。
3.1.2.3 软件工程的产生
为了摆脱软件危机，北大西洋公约组织成员国软件工作者于1968年和1969年两次召开会议（NATO会议），认识早期软件开发中所存在的问题和产生问题的原因，提出软件工程的概念。
国标（GB） 中指出软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。
软件工程包括3个要素，即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。
自软件工程概念的提出，该研究领域吸引了众多的学者，并开展了大量的理论和技术的研究，形成了\"软件工程学\"这一计算机科学中的分支。它所包含的内容可概括为以下两点： （1）软件开发技术：主要有软件开发方法学、软件工具、软件工程环境； （2）软件工程管理：主要有软件管理、软件工程经济学。
3.1.4 软件生命周期
（1）软件生命周期的概念
一个软件从定义、开发、使用和维护，直到最终被废弃而退役，要经历一个漫长的时期，这就如同一个人要经过胎儿、儿童、青年、中年和老年，直到最终死亡的漫长时期一样。
通常把软件产品从提出、实现、使用、维护到停止使用、退役的过程称为软件生命周期。软件生命周期分为3个时期共8个阶段。
①软件定义期：包括问题定义、可行性研究和需求分析3个阶段； ②软件开发期：包括概要设计、详细设计、实现和测试4个阶段； ③运行维护期：即运行维护阶段。
软件生命周期各个阶段的活动可以有重复，执行时也可以有迭代，如图3-4所示。 （2）软件生命周期各阶段的主要任务
在图3-1中的软件生命周期各阶段的主要任务是： ①问题定义。确定要求解决的问题是什么。
②可行性研究与计划制定。决定该问题是否存在一个可行的解决办法，指定完成开发任务的实施计划。
③需求分析。对待开发软件提出需求进行分析并给出详细定义。编写软件规格说明书及初步的用户手册，提交评审。
④软件设计。通常又分为概要设计和详细设计两个阶段，给出软件的结构、模块的划分、功能的分配以及处理流程。该阶段提交评审的文档有概要设计说明书、详细设计说明书和测试计划初稿。
⑤软件实现。在软件设计的基础上编写程序。该阶段完成的文档有用户手册、操作手册等面向用户的文档，以及为下一步作准备而编写的单元测试计划。
⑥软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。 ⑦运行维护。将已交付的软件投入运行，同时不断地维护，进行必要而且可行的扩充和删改。
3.1.5.1 软件工程的目标
软件工程的目标是：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。
软件工程研究的内容主要包括：软件开发技术和软件工程管理。
（1）软件开发技术。软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学。
软件开发方法学是从不同的软件类型，按不同的观点和原则，对软件开发中应遵循的策略、原则、步骤和必须产生的文档资料做出规定，从而使软件的开发能够规范化和工程化，以克服早期的手工方式生产中的随意性和非规范性。
（2）软件工程管理。软件工程管理包括软件管理学、软件工程经济学、软件心理学等内容。软件工程管理是软件按工程化生产时的重要环节，它要求按照预先制定的计划、进度和预算执行，以实现预期的经济效益和社会效益。
工程管理包括人员组织、进度安排、质量保证和成本核算等；软件工程经济学是研究软件开发中对成本的估算、成本效益分析的方法和技术。它应用经济学的基本原理来研究软件工程开发中的经济效益问题；软件心理学从个体心理、人类行为、组织行为和企业文化等角度来研究软件管理和软件工程的。
3.2.4.1 数据流图
数据流图（Data Flow Diagram，DFD），它以图形的方式描绘数据在系统中流动和处理的过程，它只反映系统必须完成的逻辑功能，所以是一种功能模型。
数据流图中的主要图形元素与说明如表3-2所示。 表3-2 数据流图的元素说明 名 称 图 形 数据流（data flow） 加工（process） 文件（file） 源/潭（source/sink） 说 明 沿箭头方向传送数据的通道，一般在旁边标注数据流名 又称转换，输入数据经加工、变换产生输出存储 又称数据源，表示处理过程中存放各种数据的文件 表示系统和环境的接口，属于系统之外的实体 绘制数据流图的基本原则如下： （1）数据流图上所有的基本图形符号一般应是上述的4种基本元素； （2）数据流图的主图必须含有前面所述的4种基本元素，缺一不可；
（3）数据流图的主图上的数据流必须封闭在外部实体之间，实体可以是一个，也可以是多个；
（4）变换框至少有一个输入数据流和一个输出数据流； （5）图上的每个元素都必须命名；
（6）任何一个数据流子图必须与它的父图上的一个变换框对应，两者的输入数据流和输出数据流必须一致。 3.2.4.2 数据字典
数据字典（Data Dictionary,DD）是对数据流图中所有元素的定义的集合，是结构化分析的核心。
数据流图和数据字典共同构成系统的逻辑模型，没有数据字典数据流图就不严格，若没有数据流图，数据字典也难于发挥作用。
数据字典中有4种类型的条目：数据流、数据项、数据存储和加工。 在数据字典各条目的定义中，常使用下述符号，如表3-3所示。 表3-3 数据字典定义式中出现的符号 ＝ ＋ ［…|…］ {} （） ** .. 符 号 表示\"等价于\"，\"定义为\"或\"由什么构成\" 表示\"和\"，\"与\" 表示\"或\"，即从方括号内列出的若干项中选择一个，通常用\"|\"号隔开供选择的项 表示\"重复\"，即重复花括号内的项，n{}m表示最少重复n次，最多重复m次 表示\"可选\"，即圆括号里的项可有可无，也可理解为可以重复0次或1次 表示\"注解\" 表示连接符 含 义 3.2.6 软件需求规格说明书
软件需求规格说明书（Software Requirement Specification，SRS）是需求分析阶段的最后成果，是软件开发的重要文档之一。 （1）软件需求规格说明书的作用
①便于用户、开发人员进行理解和交流。
②反映出用户问题的结构，可以作为软件开发工作的基础和依据。 ③作为确认测试和验收的依据。 （2）软件需求规格说明书的内容
软件需求规格说明书是作为需求分析的一部分而制定的可交付文档。该说明书把在软件计划中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准以及其他要求有关的数据。
（3）软件需求规格说明书的特点
软件需求规格说明书是确保软件质量的有力措施。衡量软件需求规格说明书质量好坏的标准，标准的优先级及标准的内涵如下：
①正确性：SRS首先要正确地反映待开发系统，体现系统的真实要求。 ②无歧义性：对每一个需求不能有两种解释。
③完整性：SRS要涵盖用户对系统的所有需求，包括功能要求、性能要求、接口要求、设计约束等。
④可验证性：SRS描述的每一个需求都可在有限代价的有效过程中验证确认。 ⑤一致性：各个需求的描述之间不能有逻辑上的冲突。
⑥可理解性：为了使用户能看懂SRS，应尽量少使用计算机的概念和术语。 ⑦可修改性：SRS的结构风格在有需要时不难改变。 ⑧可追踪性：每个需求的来源和流向是清晰的。 作为设计的基础和验收的依据，软件需求规格说明书应该精确而无二义性，并且简单易懂，这样可以方便后面的设计，以及用户看懂说明书，并且发现和指出其中的错误以保证软件系统质量。
3.3.1.1 软件设计的基础
软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。软件设计的
基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，也就是说，软件设计是确定系统的物理模型。
软件设计的重要性和地位概括为以下几点：
（1）软件开发阶段（设计、编码、测试）占软件项目开发总成本的绝大部分，是在软件开发中形成质量的关键环节；
（2）软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径；
（3）软件设计做出的决策，最终影响软件实现的成败； （4）设计是软件工程和软件维护的基础。
从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。
软件设计的一般过程是：软件设计是一个迭代的过程；先进行高层次的结构设计；然后进行低层次的过程设计；穿插进行数据设计和接口设计。 3.3.1.2 软件设计的基本原理
软件设计遵循软件工程的基本目标和原则，建立了适用于软件设计中应该遵循的基本原理和与软件设计有关的概念。
（1）抽象。抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。 （2）模块化。模块是指把一个待开发的软件分解成若干小的简单的部分。模块化是指解决一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。
（3）信息隐蔽。是指在一个模块内包含的信息（过程或数据），对于不需要这些信息的其他模块来说是不能访问的。
（4）模块独立性。是指每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。
模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模块独立性使用耦合性和内聚性两个定性的度量标准。
内聚性是度量一个模块功能强度的一个相对指标，耦合性则用来度量模块之间的相互联系程度。
耦合可以分为下列几种，它们之间的耦合度由高到低排列：
内容耦合--若一个模块直接访问另一模块的内容，则这两个模块称为内容耦合。 公共耦合--若一组模块都访问同一全局数据结构，则称为公共耦合。 外部耦合--若一组模块都访问同一全局数据项，则称为外部耦合。
控制耦合--若一模块明显地把开关量、名字等信息送入另一模块，控制另一模块的功能，则称为控制耦合。
标记耦合--若两个以上的模块都需要其余某一数据结构的子结构时，不使用其余全局变量的方式而是使用记录传递的方式，这样的耦合称为标记耦合。
数据耦合--若一个模块访问另一个模块，被访问模块的输入和输出都是数据项参数，则这两个模块为数据耦合。
非直接耦合--若两个模块没有直接关系，它们之间的联系完全是通过程序的控制和调用来实现的，则称这两个模块为非直接耦合，这样的耦合独立性最强。
内聚是从功能角度来衡量模块的联系，它描述的是模块内的功能联系。内聚有如下种类，它们之间的内聚度由弱到强排列。
偶然内聚--模块中的代码无法定义其不同功能的调用。但它使该模块能执行不同的功能，这种模块称为巧合强度模块。
逻辑内聚--这种模块把几种相关的功能组合在一起，每次被调用时，由传送给模块的参数来确定该模块应完成哪一种功能。
时间内聚--这种模块顺序完成一类相关功能，比如初始化模块，它顺序地为变量置初值。 过程内聚--如果一个模块内的处理元素是相关的，而且必须以特定次序执行，则称为过程
内聚。
通信内聚--这种模块除了具有过程内聚的特点外，还有另外一种关系，即它的所有功能都通过使用公用数据而发生关系。
顺序内聚--如果一个模块内各个处理元素和同一个功能密切相关，而且这些处理必须顺序执行，一个处理元素的输出数据作为下一个处理元素的输入数据，则称为顺序内聚。
功能内聚--如果一个模块包括为完成某一具体任务所必需的所有成分，或者说模块中所有成分结合起来是为了完成一个具体的任务，此模块则为功能内聚模块。
耦合性与内聚性是模块独立性的两个定性标准，耦合与内聚是相互关联的。在程序结构中，各模块的内聚性越强，则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。
3.3.2 概要设计任务
概要设计又称总体设计，软件概要设计的基本任务如下所述。 （1）设计软件系统结构
为了实现目标系统，先进行软件结构设计，如图3-6所示。 （2）数据结构及数据库设计
数据设计是实现需求定义和规格说明中提出的数据对象的逻辑表示。 （3）编写概要设计文档
概要设计阶段的文档有概要设计说明书、数据库设计说明书和集成测试计划等。 （4）概要设计文档评审
在文档编写完成后，要对设计部分是否完整地实现了需求中规定的功能、性能等要求，设计方案的可行性，关键的处理及内外部接口定义正确性、有效性，各部分之间的一致性等进行评审，以免在以后的设计中出现大的问题而返工。
结构图（Stucture Chart，SC），也称程序结构图，是描述软件结构的图形工具，是常用的软件结构设计工具。
结构图的基本图符及含义如表3-4所示。
表3-4 结构图基本图符号 概念 模块 调用关系 信息 含义 一个矩形代表一个模块，矩形内注明模块的名字或主要功能 矩形之间的箭头（或直线）表示模块的调用关系 用带注释的箭头表示模块调用过程中来回传递的信息。如果希望进一步标明传递的信息是数据信息还是控制信息，则可用带实心圆的箭头表示是控制信息，空心圆表示数据信息 图 符 一般模块 调用关系 数据信息 控制信息
软件结构图是软件系统的模块层次结构，反映了整个系统的功能实现。 结构图有4中常用的模块类型：传入模块、传出模块、变换模块和协调模块，其表示图形如图3-9所示。
3.3.5.1 程序流程图
程序流程图又称为程序框图，在程序流程图中，构成程序流程图的最基本图符及含义如下所述。
●方框表示一个加工步骤。 ●菱形表示一个逻辑条件。 ●箭头表示控制流。
按照结构化程序设计的要求，程序流程图构成的所有程序描述可分解为如图3-6所示的5种控制结构，它们的含义如下所述。
①顺序型：几个连续的加工步骤依次排列构成。
②选择型：由某个逻辑判断式的取值决定选择两个加工中的一个。 ③先判断重复型（WHILE型）：先判断循环控制条件是否成立，成立则执行循环体语句。 ④后判断重复型（UNTIL型）：重复执行某些特定的加工，直到控制条件成立。 ⑤多分支选择型：列举多种加工情况，根据控制变量的取值，选择执行其中之一。 通过把图3-13中的5种基本结构相互组合或嵌套，可以构成任何复杂的程序流程图。
图3-13 程序流程图的5种基本控制结构
程序流程图不易表示数据结构。 3.4.1.1 软件测试的目的
Grenford.J.Myers给出了软件测试的目的。
（1）测试是为了发现程序中的错误而执行程序的过程。
（2）好的测试用例（test case）很可能发现迄今为止尚未发现的错误。 （3）一次成功的测试是指发现了至今为止尚未发现的错误。
测试的目的是发现软件中的错误，但是，暴露错误并不是软件测试的最终目的，测试的根本目的是尽可能多地发现并排除软件中隐藏的错误。
3.4.1.2 软件测试的准则
根据上述软件测试的目的，为了能设计出有效的测试方案，以及好的测试用例，软件测试人员必须深入理解，并正确运用以下软件测试的基本准则。 （1）所有测试都应追溯到用户需求。
（2）在测试之前制定测试计划，并严格执行。 （3）充分注意测试中的群集现象。
（4）避免由程序的编写者测试自己的程序。 （5）不可能进行穷举测试。
（6）妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。
3.4.2 软件测试技术与方法
软件测试具有多种方法，根据软件是否需要被执行，可以分为静态测试和动态测试。如果按照功能划分，可以分为白盒测试和黑盒测试。 3.4.2.1 静态测试与动态测试
静态测试一般是指人工评审软件文档或程序，借以发现其中的错误。由于被评审的文档或程序不必运行，所以称为静态的。静态测试包括代码检查、静态结构分析、代码质量度量等。静态测试可以由人工运行，充分发挥人的逻辑思维优势，也可以借助软件工具自主运行。 动态测试是指通常的上机测试，这种方法是使程序有控制地运行，并从多种角度观察程序运行时的行为，以发现其中的错误。测试是否能够发现错误取决于测试实例的设计。动态测试的设计测试实例方法一般有两类：黑盒测试方法和白盒测试方法。
设计高效、合理的测试用例是动态测试的关键。测试用例是为测试设计的数据。测试用例由测试输入数据和与之对应的预期输出结果两部分组成。测试用例的格式如下：
[(输入值集)，(输出值集)]
3.4.2.2 白盒测试方法与测试用例设计
白盒测试又称为结构测试或逻辑驱动测试。它允许测试人员利用程序内部的逻辑结构及有关信息来设计或选择测试用例，对程序所有的逻辑路径进行测试。白盒测试是在程序内部进行，主要用于完成软件内部操作的验证。
白盒测试的基本原则是：保证所测模块中每一个独立路径至少执行一次；保证所测试模块所有判断的每一个分支至少执行一次；保证所测模块的每一个循环都在边界条件和一般条件下至少执行一次；验证所有内部数据结构的有效性。 白盒测试法主要有逻辑覆盖和基本路径测试等。
（1）逻辑覆盖测试。泛指一系列以程序内部的逻辑结构为基础的测试用例设计技术。通常所指的程序中的逻辑表示有判断、分支、条件3种表示方式。
①语句覆盖。语句覆盖是一个比较弱的测试标准，它的含义是，选择足够的测试实例，使得程序中的每一个语句都能执行一次。
②路径覆盖。执行足够的测试用例，使程序中所有的可能路径都至少经历一次。
③判定覆盖。设计足够的测试实例，使得程序中的每个判定至少都获得一次\"真值\"和\"假值\"的机会。判定覆盖要比语句覆盖严格，因为如果每个分支都执行过了，则每个语句也执行过了。
④条件覆盖。对于每个判定中所包含的若干个条件，应设计足够多的测试实例，使得判定中的每个条件都取到\"真\"和\"假\"两个不同的结果。条件覆盖通常比判定覆盖强，但也有的测试实例满足条件覆盖而不满足判定覆盖。
⑤判断－条件覆盖。设计足够多的测试实例，使得判定中的每个条件都能取得各种可能的\"真\"和\"假\"值，并且使每个判定都能取到\"真\"和\"假\"两种结果。
（2）基本路径测试。它的思想和步骤是，根据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集合，并由此导出一组测试用例对每一条独立执行路径进行测试。
3.4.2.3 黑盒测试方法与测试用例设计
黑盒测试方法又称功能测试或数据驱动测试，着重测试软件功能。白盒测试在测试过程的早期阶段进行，而黑盒测试主要用于软件的确认测试。
黑盒测试完全不考虑程序内部的逻辑结构和处理过程，黑盒测试是在软件接口处进行，检查和验证程序的功能是否符合需求规格说明书的功能说明。
常用的黑盒测试方法和技术有：等价类划分法、边界值分析法、错误推测法等。 （1）等价类划分法
等价类划分是一种常用的黑盒测试方法，这种技术的方法是先把程序的所有可能的输入划分成若干个等价类，然后根据等价类选取相应的测试用例。每个等价类中各个输入数据度发现程序中错误的几率几乎是相同的。因此，从每个等价类中只取一组数据作为测试数据，这样选取的测试数据最有代表性，最可能发现程序中的错误，并且大大减少了需要的测试数据的数量。
（2）边界值分析法
边界值分析法是对各种输入、输出范围的边界情况设计测试用例的方法。
大量的实践表明，程序在处理边界值时容易出错，因此设计一些测试用例，使程序运行在边界情况附近，这样揭露程序中错误的可能性就更大。
选取的测试数据应该刚好等于、小于和大于边界值。也就是说，按照边界值分析法，应该选取刚好等于、稍小于和稍大于等价类边界值的数据作为测试数据，而不是选取每个等价类内的典型值或任意值作为测试数据。
通常设计测试方案时总是把等价划分和边界值分析法结合使用。 （3）错误推测法 ①错误推测法概念。
错误推测法是一种凭直觉和经验推测某些可能存在的错误，从而针对这些可能存在的错误设计测试用例的方法。这种方法没有机械的执行过程，主要依靠直觉和经验。 错误推测法针对性强，可以直接切入可能的错误，直接定位，是一种非常实用、有效的方法，但是需要非常丰富的经验。 ②错误推测法实施步骤。
首先对被测试软件列出所有可能出现的错误和易错情况表，然后基于该表设计测试用例。
3.4.3 软件测试的实施
软件测试是保证软件质量的重要手段，软件测试是一个过程，其测试流程是该过程规定的程序，目的是使软件测试工作系统化。
软件测试的实施过程分4个步骤，即单元测试、集成测试、确认测试和系统测试。 3.4.3.1 单元测试
单元测试是对软件设计的最小单位--模块（程序单元）进行正确性检验测试。单元测试的目的是发现各模块内部可能存在的各种错误。
单元测试的依据是详细的设计说明书和源程序。
单元测试的技术可以采用静态分析和动态测试。对动态测试通常以白盒动态测试为主，辅之以黑盒测试。
单元测试是针对单个模块，这样的模块通常不是一个独立的程序，需要考虑模块和其他模块的调用关系。在单元测试中，用一些辅助模块去模拟与被测模块相联系的其他模块，即为测试模块设计驱动模块和桩模块，构成一个模拟的执行环境进行测试，如图3-21所示。
驱动（Driver）模块就相当于一个\"主程序\"，它接收测试数据，把这些数据传送给被测试的模块，输出有关的结果。
桩（Stub）模块代替被测试的模块所调用的模块。因此桩模块也可以称为\"虚拟子程序\"。它接受被测模块的调用，检验调用参数，模拟被调用的子模块的功能，把结果送回被测试的模块。
在软件的结构图中，顶层模块测试时不需要驱动模块，最底层的模块测试时不需要桩模块。
3.4.3.2 集成测试
集成测试是测试和组装软件的过程。
集成测试主要发现设计阶段产生的错误，集成测试的依据是概要设计说明书，通常采用黑盒测试。
集成测试的内容主要有以下4个方面： ●软件单元的接口测试； ●全局数据结构测试； ●边界条件测试； ●非法输入测试。
集成的方式可以分为非增量方式集成和增量方式集成两种。
非增量方式是先分别测试每个模块，再把所有模块按设计要求组装一起进行整体测试，因此，非增量方式又称一次性组装方式。
增量方式是把要测试的模块同已经测试好的那些模块连接起来进行测试，测试完以后再把下一个应测试的模块连接进来测试。
增量方式包括自顶向下、自底向上以及自顶向下和自底向上相结合的混合增量方法。 3.4.3.3 确认测试
确认测试的任务是检查软件的功能、性能及其他特征是否与用户的需求一致，它是以需求规格说明书作为依据的测试。确认测试通常采用黑盒测试。
确认测试首先测试程序是否满足规格说明书所列的各项要求，然后要进行软件配置复审。复审的目的在于保证软件配置齐全、分类有序，以及软件配置所有成分的完备性、一致性、准确性和可操作性，并且包括软件维护所必需的细节。 3.4.3.4 系统测试
在确认测试完成后，把软件系统整体作为一个元素，与计算机硬件、支持软件、数据、人员和其他计算机系统的元素组合在一起，在实际运行环境下对计算机系统进行一系列的集成测试和确认测试，这样的测试称为系统测试。
系统测试的目的是在真实的系统工作环境下检验软件是否能与系统正确连接，发现软件与系统需求不一致的地方。
系统测试的内容包括：功能测试、操作测试、配置测试、性能测试、安全性测试、外部接口测试等。
3.5.1 程序调试的概念
调试（也称为Debug，排错）是作为成功测试的后果出现的步骤，也就是说，调试是在测试发现错误之后排除错误的过程。软件测试贯穿整个软件生命期，而调试主要在开发阶段。
程序调试活动由两部分组成：
●根据错误的迹象确定程序中错误的确切性质、原因和位置。 ●对程序进行修改，排除这个错误。 3.5.1.1 程序调试的基本步骤
（1）错误定位。从错误的外部表现形式入手，研究有关部分的程序，确定程序中出错的位置，找出错误的内在原因。
（2）修改设计和代码，以排除错误。排错是软件开发过程中一项艰苦工作，这也决定了调
试工作是一个具有很强技术性和技巧性的工作。
（3）进行回归测试，防止引进新的错误。因为修改程序可能带来新的错误，重复进行暴露这个错误的原始测试或某些有关测试，以确认该错误是否被排除、是否引进了新的错误。 3.5.1.2 程序调试原则
调试活动由对程序中错误的定性、定位和排错两部分组成，因此调试原则也从这两个方面来考虑。
（1）错误定性和定位的原则
①集中思考分析和错误现象有关的信息。
②不要钻死胡同。如果在调试中陷入困境，可以暂时放在一边，或者通过讨论寻找新的思路。
③不要过分信赖调试工具。调试工具只能提供一种无规律的调试方法，不能代替人思考。 ④避免用试探法。试探法其实是碰运气的盲目动作，成功率很小，是没有办法时的办法。 （2）修改错误的原则
①在错误出现的地方，可能还有其他错误。因为经验表明，错误有群集现象。
②修改错误的一个常见失误是只修改了这个错误的现象，而没有修改错误本身。如果提出的修改不能解释与这个错误有关的全部线索，这就表明只修改了错误的一部分。
③必须明确，修改一个错误的同时可能引入了新的错误。解决的办法是在修改了错误之后，必须进行回归测试。
④修改错误的过程将迫使人们暂时回到程序设计阶段。修改错误也是程序设计的一种形式，在程序设计阶段所使用的任何方法都可以应用到错误修正的过程中来。
⑤修改源代码程序，不要改变目标代码。
第4章 数据库设计基础
4.1.2.1 数据库管理系统的概念
数据库管理系统（DataBase Management System，DBMS）是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等。目前流行的DBMS均为关系数据库系统，例如Oracle、PowerBuilder、DB2和SQL Sever等。
数据库管理系统是数据库系统的核心，它位于用户与操作系统之间，从软件分类的角度来说，属于系统软件。
数据库管理系统有如下功能：
①数据模式定义。数据库管理系统负责为数据库构建模式。 ②数据存取的物理构建。数据库管理系统负责为数据模式的物理存取及构建提供有效的存取方法与手段。
③数据操纵。数据库管理系统一般提供查询、插入、修改以及删除数据的功能。它还具有做简单算术运算及统计的能力和强大的过程性操作能力。
④数据的完整性、安全性定义与检查。数据库中的数据具有内在语义上的关联性与一致性，它们构成了数据的完整性；
⑤数据库的并发控制与故障恢复。数据库管理系统必须对多个应用程序的并发操作做必要的控制以保证数据不受破坏，这就是数据库的并发控制；数据库中的数据一旦遭受破坏，数据库管理系统必须有能力及时进行恢复，这就是数据库的故障恢复；
⑥数据的服务。数据库管理系统提供对数据库中数据的多种服务功能，如数据拷贝、转储、重组、性能监测、分析等。
为完成以上6个功能，数据库管理系统提供了相应的数据语言（Data Language），它们是： 数据定义语言（Data Definition Language，DDL）。该语言负责数据的模式定义与数据的物理存取构建。
数据操纵语言（Data Manipulation Language，DML）。该语言负责数据的操纵，包括查询及增加、删除、修改等操作。
数据控制语言（Data Control Language，DCL）。该语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。
上述数据语言按其使用方式具有以下两种结构形式。
●交互式命令语言：它的语言简单，能在终端上即时操作，它又称为自含型或自主型语言。 ●宿主型语言：它一般可嵌入某些宿主语言中，如C、C++和COBOL等高级过程性语言中。
4.1.3 数据库系统
4.1.3.1 数据库系统的概念
数据库系统（DataBase System，DBS）是指在计算机系统中引入数据库后的系统构成。 数据库系统由数据库（数据）、数据库管理系统、应用系统、数据库管理员、系统平台之一--硬件平台（硬件）、系统平台之二--软件平台（软件）5部分构成。
硬件平台包括以下两项：
●计算机：它是系统中硬件的基础平台；
●网络：数据库系统今后将以建立在网络上为主，而其结构形成又以客户/服务器（C/S）方式与浏览器/服务器（B/S）方式为主。
软件平台包括以下3项：
●操作系统：它是系统的基础软件平台；
●数据库系统开发工具：它包括过程性程序设计语言（如C，C++等），也包括可视化开发工具VB、PB、Delphi等，它还包括近期与Internet有关的HTML和XML等。
●接口软件：在网络环境下数据库系统中数据库与应用程序，数据库与网络间存在着多种接口，它们需要接口软件进行连接，这些接口软件包括ODBC、JDBC、OLEDB、CORBA、COM及DCOM等。
4.1.3.2 数据库应用系统
在数据库系统的基础上，如果使用数据库管理系统（DBMS）软件和数据库开发工具书写出应用程序，用相关的可视化工具开发出应用界面，则构成了数据库应用系统（Database Application System，简称DBAS）。DBAS由数据库系统、应用软件及应用界面三者组成。
因此，DBAS包括数据库、数据库管理系统、人员（数据库管理员和用户）、硬件平台、软件平台、应用软件、应用界面7个部分。
4.1.4 数据库系统的发展
数据管理技术的发展经历了3个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。 文件系统是数据库系统发展的初级阶段，它具有提供简单的数据共享与数据管理的能力，但是它缺少提供完整、统一的管理和数据共享的能力。
层次数据库与网状数据库的发展为统一管理与共享数据提供了有力的支撑，但是由于它们脱胎于文件系统，所以这两种系统也存在不足。
关系数据库系统结构简单，使用方便，逻辑性强，物理性少，因此在20世纪80年代以后一直占据数据库领域的主导地位。
关于数据管理3个阶段中的软硬件背景及处理特点，简单概括如表4-1所示。 表4-1 数据管理3个阶段的比较 背景 特点 应用目的 硬件背景 软件背景 处理方式 数据管理者 人工管理阶段 科学计算 无直接存取设备 无操作系统 批处理 人 文件管理阶段 科学计算、管理 磁盘、磁鼓 有文件系统 联机实时处理、批处理 文件系统 数据库系统管理阶段背 大规模管理 大容量磁盘 有数据库管理系统 分布处理、联机实时处理和批处理 数据库管理系统 数据面向的对象 数据共享程度 数据的独立性 据的结构化 控制能力 某个应用程序 无共享，冗余度大 不独立，完全依赖于程序 无结构 由应用程序控制 某个应用程序 共享性差，冗余度大 独立性差 记录内有结构，整体无结构 由应用程序控制 现实世界 共享性大，冗余度小 具有高度的物理独立性和一定的逻辑独立性数 整体结构化，用数据模型描述数据 由DBMS提供数据安全性、完整性、并发控制和恢复 4.1.5 数据库系统的基本特点
数据库系统的基本特点有数据集成性、数据的高共享性和低冗余性、数据独立性高、数据统一管理与控制。
4.1.5.1 数据的集成性
数据库系统的数据集成性主要表现在如下几个方面： （1）在数据库系统中采用统一的数据结构方式。
（2）在数据库系统中按照多个应用的需要组织全局的统一的数据结构（即数据模式），数据模式不仅可以建立全局的数据结构，还可以建立数据间的语义联系，从而构成一个内在紧密联系的数据整体。
（3）数据库系统中的数据模式是多个应用共同的、全局的数据结构，而每个应用的数据则是全局结构中的一部分，称为局部结构（即视图），这种全局与局部的结构模式构成了数据库系统数据集成性的主要特征。
4.1.5.2 数据的高共享与低冗余性
由于数据的集成性使得数据可为多个应用所共享。数据的共享自身极大地减少了数据冗余性，不仅减少存储空间，还避免数据的不一致性。
所谓数据的一致性，是指在系统中同一数据在不同位置的出现应保持相同的值，而数据的不一致性指同一数据在系统的不同拷贝处有不同的值。因此，减少冗余性以避免数据的不同值出现。
4.1.5.3 数据的独立性
数据独立性是数据与程序间的互不依赖性，即数据库中的数据独立于应用程序而不依赖于应用程序。数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。
数据的独立性一般分为物理独立性与逻辑独立性两种。
①物理独立性：指用户的应用程序与存储在磁盘上的数据库中数据是相互独立的。当数据的物理结构（包括存储结构、存取方式等）改变时，如存储设备的更换、物理存储的更换、存取方式改变等，应用程序都不用改变。
②逻辑独立性：指用户的应用程序与数据库的逻辑结构是相互独立的。数据的逻辑结构改变了，如修改数据模式、增加新的数据类型、改变数据间联系等，用户程序都可以不变。 4.1.5.4 数据统一管理与控制
数据统一管理与控制主要包括以下3个方面。
①数据的完整性检查：将数据控制在有效的范围内，或保证数据之间满足一定的关系。 ②数据的安全性保护：每个用户只能按指定方式使用和处理指定数据，保护数据以防止不合法的使用造成的数据泄密和破坏。
③并发控制：对多用户的并发操作加以控制和协调，防止相互干扰而得到错误的结果。
4.1.6.1 数据库系统的三级模式结构
数据库系统在其内部分为三级模式，即概念模式、内模式和外模式。 （1）概念模式（Conceptual Schema）。概念模式也称模式，是对数据库系统中全局数据逻辑结构的描述，是全体用户（应用）公共数据视图。它不涉及具体的硬件环境与平台，也与具体的软件环境无关。
模式实际上是数据库数据在逻辑级上的视图。一个数据库只有一个模式。 （2）外模式（External Schema）。外模式也称子模式，它是数据库用户（包括应用程序员和最终用户）能够看见和使用的局部数据的逻辑结构和特征的描述，它是由概念模式推导而出来
的，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。一个概念模式可以有若干个外模式。
（3）内模式（Internal Schema）。内模式又称物理模式（Physical Schema），它给出了数据库物理存储结构与物理存取方法，如数据存储的文件结构、索引、集簇及hash等存取方式与存取路径，内模式的物理性主要体现在操作系统及文件级上，它还未深入到设备级上（如磁盘及磁盘操作）。
模式的三个级别层次反映了模式的三个不同环境及它们的不同要求，其中内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式，概念模式处于中间层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要求。 4.1.6.2 数据库系统的两级映射
数据库系统在三级模式之间提供了两级映射：外模式/概念模式的映射和概念模式/内模式的映射。
两级映射保证了数据库中的数据具有较高的逻辑独立性和物理独立性。
（1）外模式/概念模式的映射：对于每一个外模式，数据库系统都提供一个外模式/概念模式的映射，它定义了该外模式描述的数据局部逻辑结构和概念模式描述的全局逻辑结构之间的对应关系。
当概念模式改变时，只需要修改外模式/概念模式映射即可，外模式可以保持不变。由于应用程序是根据数据的外模式编写的，因此应用程序也不必修改，保证了数据的逻辑独立性。 （2）概念模式/内模式的映射：数据库只有一个概念模式和一个内模式，所以概念模式/内模式的映射是唯一的，它定义了概念模式描述的全局逻辑结构和内模式描述的存储结构之间的对应关系。
当内模式改变时，只需要改变概念模式/内模式的映射，概念模式可以保持不变，从而应用程序保持不变，保证了数据的物理独立性。
4.2.1 数据模型的基本概念
在数据库中用数据模型这个工具来抽象、表示和处理现实世界中的数据和信息。通俗地讲，数据模型就是现实世界的反映，它分为两个阶段：把现实世界中的客观对象抽象为概念模型；把概念模型转换为某一DBMS支持的数据模型。
从事物的客观特性到计算机里的具体表示包括了现实世界、信息世界和机器世界3个数据领域。
①现实世界：现实世界就是客观存在的各种事物，是用户需求处理的数据来源。 ②信息世界：通过抽象对现实世界进行数据库级上的刻画所构成的逻辑模型。
③计算机世界：在信息世界基础上致力于其在计算机物理结构上的描述，从而形成的物理模型。
数据模型从抽象层次上描述了数据库系统的静态特征、动态行为和约束条件，因此数据模型通常由数据结构、数据操作及数据约束3部分组成。 （1）数据结构
数据结构是所研究的对象类型的集合，是对系统静态特性的描述。数据结构是数据模型的核心，不同的数据结构有不同的操作和约束，人们通常按照数据结构的类型来命名数据模型。例如，层次结构、网状结构和关系结构的数据模型分别命名为层次模型、网状模型和关系模型。 （2）数据操作
数据操作是相应数据结构上允许执行的操作及操作规则的集合。数据操作是对数据库系统动态特性的描述。 （3）数据约束
数据的约束条件是一组完整性规则的集合。也就是说，具体的应用数据必须遵循特定的语义约束条件，以保证数据的正确、有效和相容。
数据模型按不同的应用层次分成3种类型，它们是概念数据模型、逻辑数据模型及物理数据
模型。
4.2.2.1 E-R模型的基本概念 （1）实体（Entity）
现实世界中的事物可以抽象成为实体，实体是概念世界中的基本单位，它们是客观存在的且又能相互区别的事物。凡是有共同属性的实体组成的一个集合称为实体集。 （2）属性（Attribute）
现实世界中事物均有一些特性，这些特性可以用属性来表示。属性刻画了实体的特征。一个实体往往可以有若干个属性。每个属性可以有值，一个属性的取值范围称为该属性的值域或值集。
（3）联系（Relationship）
实体之间的对应关系称作联系，它反映现实世界事物之间的相互关联。实体间联系的种类是指一个实体型中可能出现的每一个实体和另一个实体型中多少个具体实体存在联系，可归纳为3种类型。
一对一联系（1：1）。如果对于实体集A中的每一个实体，实体集B中至多有一个（也可以没有）实体与之联系，反之亦然，则称实体集A与实体集B具有一对一联系，记为1：1。例如，一个学校只有一名校长，并且校长不可以在别的学校兼职，校长与学校的关系就是一对一联系
一对多联系（1：n）或多对一联系（n：1）。如果实体集A中的每一个实体，在实体集B中都有多个实体与之对应；实体集B 中的每一个实体，在实体集A中只有一个实体与之对应，则称实体集A与实体集B是一对多联系，反之即为多对一联系。例如，公司的一个部门有多名职员，每一个职员只能在一个部门任职，则部门与职员之间的联系就是一对多的联系
多对多联系（m：n）。如果实体集A中的每一个实体，在实体集B中都有多个实体与之对应，反之亦然，则称这种关系是多对多联系。例如，一个学生可以选多门课程，一门课程可以被多名学生选修，学生和课程的联系就是多对多联系。 4.2.2.2 实体、联系、属性之间的联接关系
E-R模型的3个基本概念是实体、联系和属性，但现实世界是有机联系的整体，为了能表示现实世界，必须把这三者结合起来。 （1）实体集（联系）与属性的结合
实体是概念世界中的基本单位，属性附属于实体，它本身并不构成独立单位。一个实体可以有若干个属性，实体以及它的所有属性构成了实体的一个完整描述。
属性有属性域，每个属性可取属性域内的值。
实体有型与值之别，一个实体的所有属性构成了这个实体的型，相同的实体构成了实体集。 （2）实体（集）与联系的结合
实体（集）间可通过联系建立联接关系。一般而言，实体（集）间无法建立直接关系，它只能通过联系才能建立起联接关系。 4.2.2.3 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#）、姓名（Sn）及年龄（Sa），它们可以用如图4-4（b）所示来表示。
（3）联系表示法
在E-R图中用菱形表示联系，菱形内写上联系名。例如，学生与课程间的联系SC，可用如图4-4（c）所示来表示。
（4）实体集（联系）与属性间的联接关系
属性依附于实体集，因此，它们之间有联接关系。在E-R图中这种关系可用联接这两个图形间的无向线段表示（一般用直线）。例如，实体集student有属性S#（学号）、Sn（学生姓名）及Sa（学生年龄）；实体集course有属性C#（课程号）、Cn（课程名）及P#（预修课号），此时它们可用图4-5（a）联接。
属性也依附于联系，它们之间也有联接关系，因此也可用无向线段表示。例如，联系SC可与学生的课程成绩属性G建立联接并可用如图4-5（b）所示来表示。
（5）实体集与联系间的联接关系
在E-R图中，实体集与联系间的联接关系可用联接这两个图形间的无向线段表示。例如，实体集student与联系SC间有联接关系，实体集course与联系SC间也有联接关系，因此它们之间可用无向线段相联，在线段边上注明其对应函数关系，如1∶1，1∶n，n∶m等，，构成一个如图4-6所示的图。
图4-6 实体集间的联系表示图
4.2.5.1 关系模型的数据结构
关系模型（Relation Model）是目前最常用的数据模型之一。关系模型的数据结构非常单一，在关系模型中，现实世界的实体以及实体间的各种联系均用关系来表示。
关系模型中常用的术语如下所示。
关系：关系模型采用二维表来表示关系，简称表，由表框架及表的元组组成。一个二维表就是一个关系。例如，表4-2的二维表就是一个关系。
属性：二维表中的一列称为属性。例如，表4-2的属性有学号、姓名、系号等，二维表中属性的个数称为属性元数（Arity）。表4-2中的关系属性元数为\"5\"。
值域：每个属性的取值范围。例如，表4-6的Age属性的值域不能为负数。
元组：二维表中的一行称为元组。例如，表4-2的（06001，方铭，01，22，男）就是一个元组。
一个元组由若干个元组分量组成，每个元组分量是属性的投影值。元组分量的个数等于属性元数，表中元组的个数称为表的基数（Cardinality）。
候选码：二维表中能唯一标识元组的最小属性集。例如，在表4-2中，如果姓名不允许重名时，学号和姓名都是候选码。
主键或主码：若一个二维表有多个候选码，则选定其中一个作为主键供用户使用。例如，在表4-2中，存在两个候选码：学号和姓名，若选中学号作为唯一标识，那么，学号就是学生登记表关系的主码。
二维表中一定要有键，因为如果表中所有属性的子集均不是键，则表中属性的全集必为键
（称为全键），因此也一定有主键。
外键或外码：表M中的某属性集是表N的候选键或者主键，则称该属性集为表M的外键或外码。例如，如果表4-3系信息表关系的主码是\"系号\"，那么，在学生登记表（表4-2）中的\"系号\"就是外码。
表4-2 学生登记表 学号 06001 06003 06234 学号 06001 06003 06234 姓名 方铭 张静 白穆云 系号 01 02 03 系名 计算机 物理 数学 年龄 22 22 21 主任 01 02 03 性别 男 女 男 表4-3 系信息表 关系具有以下7条性质。
①元组个数有限性：二维表中元组的个数是有限的。 ②元组的唯一性：二维表中任意两个元组不能完全相同。
③元组的次序无关性：二维表中元组的次序，即行的次序可以任意交换。 ④元组分量的原子性：二维表中元组的分量是不可分割的基本数据项。 ⑤属性名唯一性：二维表中不同的属性要有不同的属性名。 ⑥属性的次序无关性：二维表中属性的次序可以任意交换。
⑦分量值域的同一性：二维表属性的分量具有与该属性相同的值域，或者说列是同质的。 满足以上7个性质的二维表称为关系，以二维表为基本结构所建立的模型称为关系模型。 4.2.5.3 关系模型的完整性约束
关系模型中可以有3类完整性约束：实体完整性约束、参照完整性约束和用户定义的完整性约束。其中前两种完整性约束是关系模型由关系数据库系统自动支持；用户定义的完整性约束是用户使用由关系数据库提供的完整性约束语言来设定写出约束条件，运行时由系统自动检查。 在这3种完整性约束中，前两种约束是任何一个关系数据库都必须满足的，由关系数据库管理系统自动支持。
（1）实体完整性约束（Entity Integrity Constraint）
该约束要求关系的主键中属性值不能为空值，这是数据库完整性的最基本要求。 （2）参照完整性约束（Reference Integrity Constraint）
该约束是关系之间相关联的基本约束，它不允许关系引用不存在的元组；即在关系中的外键要么是所关联关系中实际存在的元组，要么就为空值。
（3）用户定义的完整性约束（User defined Integrity Constraint）
用户定义的完整性就是针对某一具体关系数据库的约束条件。它反映某一具体应用所涉及的数据必须满足的语义要求。例如，某个属性的取值范围在1~200之间，某个属性必须取唯一值等。
4.3.2 关系代数的基本运算
由于操作是对关系的运算，而关系是有序组的集合，因此可以将操作看成是集合的运算。 （1）插入
设有关系R需要插入若干元组，要插入的元组组成关系R′，则插入可用集合并运算表示为：
R∪R′
（2）删除
设有关系R需要删除一些元组，要删除的元组组成关系R′，则删除可用集合差运算表示为：
R-R′
（3）修改
修改关系R内的元组内容可用下面的方法实现。
①设需修改的元组构成关系R′，则先做删除得：R-R′； ②设修改后的元组构成关系R\"，此时将其插入即得到结果：（R-R′）∪ R″。 （4）查询
用于查询的3个操作无法用传统的集合运算表示，需要引入一些新的运算。 ①投影运算。
从关系模式中指定若干个属性组成新的关系称为投影。对R关系进行投影运算的结果记为πA（R），其形式定义如下：
πA（R）= { t ［ A］| t ∈ R}
其中，A为R中的属性列。
例如，对关系R中的\"系\"属性进行投影运算，记为π系（R），得到无重复元组的新关系S，如图4-12所示。
②选择运算。
从关系中找出满足给定条件的元组的操作称为选择。选择的条件以逻辑表达式给出，使得逻辑表达式为真的元组将被选取。选择是在二维表中选出符合条件的行，形成新的关系的过程。
选择运算用公式表示为：
σF（R） = { t | t ∈R且F（t）为真}
其中，F表示选择条件，它是一个逻辑表达式，取逻辑值\"真\"或\"假\"。
逻辑表达式F由逻辑运算符﹁、∧、∨连接各算术表达式组成。算术表达式的基本形式为：
XθY
其中，θ表示比较运算符>、<、≤、≥、=或≠。X、Y等是属性名，或为常量，或为简单函数；属性名也可以用它的序号来代替。
例如，在关系R中选择出\"系\"为\"建筑\"的学生，表示为σ系=建筑（R），得到新的关系S，如图4-13所示。
③笛卡儿积运算。
设有n元关系R和m元关系S，它们分别有p和q个元组，则R与S的笛卡尔积记为：
R×S
它是一个m+n元关系，元组个数是p×q。
关系R和关系S笛卡尔积运算的结果T如图4-14所示。
图4-14 笛卡尔积运算示意图
4.3.3 关系代数的扩充运算
关系代数中除了上述几个最基本的运算外，为操纵方便还需要增添一些称为扩充运算，这些运算均可由基本运算导出。常用的扩充运算有交、除、连接及自然连接等。
（1）交运算
假设有n元关系R和n元关系S，它们的交仍然是一个n元关系，它由属于关系R且由属于关系S的元组组成，并记为R∩S。交运算是传统的集合运算，但不是基本运算，它可由基本运算推导而得：
R∩S＝R- (R-S)
对图4-14中的R和S做交运算的结果如图4-15所示。 A B C b a 19 d f 22 图4-15 R∩S运算示例 （2）除运算
除运算可以近似地看作笛卡尔积的逆运算。当S×T＝R时，则必有R÷S=T，T称为R除以S的商。
除法运算不是基本运算，它可以由基本运算推导而得。设关系R有属性M1，M2，…，Mn ，关系S有属性Mn-s+1，Mn－s+2，…，Mn，此时有：
R÷S =πM1 ，M2 ，…，Mn-s(R)-πM1 ，M2 ，…，Mn-s((πM1 ，M2 ，…，Mn-s(R)×S)) 设有关系R、S，如图4-18（a）、（b）所示，求T＝R÷S，结果见图4-18（c）。
（3）连接与自然连接运算
连接运算也称θ连接，是对两个关系进行的运算，其意义是从两个关系的笛卡尔积中选择满足给定属性间一定条件的那些元组。
设m元关系R和n元关系S，则R和S两个关系的连接运算用公式表示为：
R∞AθBS
它的含义可用下式定义：
R∞SAθB=σAθB（R×S）
其中，A和B分别为R和S上度数相等且可比的属性组。连接运算从关系R和关系S的笛卡尔积R×S中，找出关系R在属性组A上的值与关系S在属性组B上值满足θ关系的所有元组。
当θ为\"＝\"时，称为等值连接。 当θ为\"<\"时，称为小于连接。 当θ为\">\"时，称为大于连接。
需要注意的是，在θ连接中，属性A和属性B的属性名可以不同，但是域一定要相同，否则无法比较。
设有关系R和关系S，如图4-16(a)、(b)所示，对图中的关系R和关系S做连接运算的结果见图4-16(c)、(d)。
在实际应用中，最常用的连接是一个叫自然连接的特例。自然连接要求两个关系中进行比较的是相同的属性，并且进行等值连接，相当于θ恒为\"＝\"，在结果中还要把重复的属性列去掉。自然连接可记为：
R∞S
设有关系R和关系S，如图4-17(a)、(b)所示，则R∞S的结果见图4-17（c）。
4.4.1 数据库设计概述
（1）数据库设计的概念
数据库设计是指对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能够有效地存储数据，满足各种用户的应用需求（信息要求和处理要求）。
从数据库设计的定义可以看出，数据库设计的基本任务是根据用户对象的信息需求（对数据库的静态要求）、处理需求（对数据库的动态要求）和数据库的支持环境（包括硬件、操作系统与DBMS）设计出数据模式。
数据库设计的根本目标是要解决数据共享问题。 （2）数据库设计方法
数据库设计中有两种方法，一种是以信息需求为主，兼顾处理需求，称为面向数据的方法（data-oriented approach）；另一种方法是以处理需求为主，兼顾信息需求，称为面向过程的方法（process-oriented approach）。其中，面向数据的方法是主流的设计方法。
（3）数据库设计的步骤
数据库设计目前一般采用生命周期法，即将整个数据库应用系统的开发分解成目标独立的若干阶段。它们是需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。在数据库设计中采用上面几个阶段中的前4个阶段，并且主要以数据结构与模型的设计为主线，如图4-19所示。
4.4.3.2 数据库概念设计过程
概念设计最常用的方法就是P.P.S.Chen于1976年提出的实体-联系方法，简称E-R方法。它采用E-R模型，将现实世界的信息结构统一由实体、属性以及实体之间的联系来描述。它按照\"视图集成设计法\"分为选择局部应用、视图设计和视图集成3个步骤 （1）选择局部应用
根据系统的具体情况，在多层的数据流图中选择一个适当层次的数据流图，让这组图中每一部分对应一个局部应用，以这一层次的数据流图为出发点，设计分E-R图。 （2）视图设计
视图设计的策略通常有以下3种。
①自顶向下。即先从抽象级别高且普遍性强的对象开始逐步细化、具体化与特殊化。 ②由底向上。即先从具体的对象开始，逐步抽象，普遍化与一般化，最后形成一个完整的视图设计。
③由内向外。即先从最基本与最明显的对象着手，逐步扩充至非基本、不明显的其他对象。 （3）视图集成
视图集成的实质是将所有的局部视图统一合并成一个完整的数据模式。在进行视图集成时，最重要的工作便是解决局部设计中的冲突。常见的冲突有下列几种：
①命名冲突。命名冲突有同名异义和同义异名两种。
②概念冲突。同一概念在一处为实体而在另一处为属性或联系。
③域冲突。相同的属性在不同视图中有不同的域，有些属性采用不同度量单位也为属域冲突。
④约束冲突。不同的视图可能有不同的约束。 视图经过合并生成的是初步E-R图，其中可能存在冗余的数据和冗余的实体间联系。冗余数据和冗余联系容易破坏数据库的完整性，给数据库维护增加困难。因此，对于视图集成后所形成的整体的数据库概念结构还必须进一步验证，确保它能满足下列条件：
①整体概念结构内部必须具有一致性，即不能存在互相矛盾的表达；
②整体概念结构能准确地反映原来的每个视图结构，包括属性、实体及实体间的联系； ③整体概念结构能满足需求分析阶段所确定的所有需求；
④整体概念结构最终还应该提交给用户，征求用户和有关人员的意见，进行评审、修改和优化，然后把它确定下来作为数据库的概念结构，作为进一步设计数据库的依据。
4.4.4.1 从E-R图向关系模式转换
采用E-R方法得到的全局概念模型是对信息世界的描述，并不适用于计算机处理，为了适合关系数据库系统的处理，必须将E-R图转换成关系模式。这就是逻辑设计的主内容。E-R图是由实体、属性和联系组成，而关系模式中只有一种元素--关系。通常转换的方法如表4-5所示。
表4-5 E-R模型与关系间的比较表 E-R模型 实体 实体集 关系模型 元组 关系 E-R模型 属性 联系 关系模型 属性 关系 关系关系模式中的命名可以用E-R图原有名称，也可另行命名，但是应尽量避免重名，关系数据库管理系统一般只支持有限种数据类型而E-R中的属性域则不受此限制，如出现关系数据库管理系统不支持的数据类型时就需要进行类型转换。
E-R图中允许出现非原子属性，但在关系模式中一般不允许出现非原子属性，非原子属性主要有集合型和元组型。如出现此种情况可以进行转换，其转换方法是集合属性纵向展开而元组属性横向展开。
因篇幅问题不能全部显示，请点此查看更多更全内容