清华大学VB经典教案第十三节——软件技术基础.ppt

第13章 软件技术基础 13.1 算法与数据结构 13.1.1 算法 算法是解题方案的准确而完整的描述。算法可以用程序实现，但算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 算法具有五个基本特征：可行性、确定性、有穷性、输入、输出。 算法由两个基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。算法的基本运算和操作包括四类：算术运算、逻辑运算、关系运算、数据传输；算法的基本控制结构有三种：顺序结构、选择结构、循环结构。 描述算法的工具有：传统的流程图、N-S结构化流程图、算法描述语言等。 算法设计的基本方法有：列举法、归纳法、递推法、递归法、减半递推技术、回溯法。,评价一个算法的主要标准是：算法的效率和存储需求。算法的效率指的是时间复杂度，存储需求指的是空间复杂度。,1算法的时间复杂度 算法的效率用算法在执行过程中的基本运算次数来度量，而算法所执行的基本运算次数是问题规模（通常用n表示）的函数，即 算法的工作量=f(n) 算法的时间量度记作 T(n)=O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 在实际分析中，要精确计算T(n)是困难的，只要大致计算出算法时间复杂度的数量级，即按重复执行次数最多的语句（基本运算或原操作）的次数，来确定算法的时间复杂度。,在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用如下两种方法来分析算法的工作量: （1）平均性态分析 所谓平均性态分析是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。 （2）最坏情况复杂性分析 所谓最坏情况复杂性分析是指在规模为n时，算法所执行的基本运算的最大次数。,2算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的存储空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外存储空间。其中，额外存储空间包括算法程序执行过程中的工作单元以及某些数据结构所需要的附加存储空间，如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。,13.1.2 数据结构的基本概念 数据结构是指相互有关联的数据元素的集合。结构是指数据元素之间的前后件关系，前后件关系是数据元素之间的一个基本关系。数据结构主要研究和讨论如下三个方面的问题： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 研究和讨论以上问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度；二是尽量节省在数据处理过程中所占用的计算机存储空间。,1数据的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构，其中数据元素之间的前后件关系是指它们的逻辑关系，而与它们在计算机中的存储位置无关。 2数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。 3数据结构的图形表示 数据集合中的每一个数据元素称为数据结点，简称结点，用中间标有元素值的方框表示，用一条有向线段表示前件结点指向后件结点，如图13-1所示。,4线性结构与非线性结构 根据数据结构中数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。 如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件； 则称该数据结构为线性结构，线性结构又称线性表。 需要特别说明的是：在一个线性结构中插入或删除任何一个结点后仍然是线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。 注意：线性结构与非线性结构是在数据的逻辑结构概念下的一种划分方法，与数据的存储结构无关。,13.1.3 线性表及其顺序存储结构 1线性表的基本概念,非空线性表有如下一些结构特征： （1）有且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，有且只有一个后件。线性表中结点的个数n称为线性表的长度，当n=0时，称为空表。 2线性表的顺序存储结构 线性表的顺序存储结构也称为顺序表。具有如下两个基本特点： （1）在顺序表中，所有元素所占的存储空间是连续的； （2）各数据元素在存储空间中是按逻辑顺序依次存放的，其前后件的两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。 在程序设计语言中，通常用一维数组来表示线性表的顺序存储空间，因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的。一般来说，长度为n的线性表 （a1,a2,ai,an）,在顺序表中，如果要在第i（1in）个元素之前插入一个新元素，则原来第i个元素之后(包括第i个元素)的所有元素都必须往后移动一个位置。平均情况下，要在顺序表中插入一个新元素，需要移动表中一半的元素。 在顺序表中，如果要删除第i（1in）个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。平均情况下，要在线性表中删除一个元素，需要移动表中一半的元素。,13.1.4 栈和队列 1栈 栈是特殊的线性表，属于线性结构。栈允许插入与删除的一端称为栈顶，用Top指针指示，而不允许插入与删除的另一端称为栈底，用Bottom指针指示。 栈按照“先进后出”(First In Last Out，FILO)或“后进先出”(Last In First Out，LIFO)的原则组织数据，因此，栈也被称为“先进后出”表或“后进先出”表。栈具有记忆作用（栈顶指针以下的元素被记忆），在顺序存储结构下，栈的插入与删除运算都不需要移动表中其他数据元素，仅移动Top指针即可，栈顶指针动态反映了栈中元素的变化情况，如图13-3所示。与一般的线性表一样，在程序设计语言中，用一维数组作为栈的顺序存储空间。 在顺序存储结构下，栈的运算有如下三种： （1）入栈运算：在栈顶位置插入一个新元素； （2）退栈运算：取出栈顶元素并赋给一个指定的变量； （3）读栈顶元素：将栈顶元素赋给一个指定的变量。,2队列 队列也是特殊的线性表，允许在一端进行插入，而在另一端进行删除，允许插入的一端称为队尾，用rear指针指示，rear指针总是指向最后被插入的元素，允许删除的一端称为队头，用front指针指示，front指针指向队头元素的前一个位置。 队列又称为“先进先出”(First In First Out，FIFO)或“后进后出”(Last In Last Out，LILO)的线性表，它体现了“先到先服务”的原则。在顺序存储结构下，队列的插入与删除运算都不需要移动表中其他数据元素，仅移动rear和front指针即可，如图13-4所示。与栈一样，在程序设计语言中，用一维数组作为队列的顺序存储空间。 在实际应用中，队列的顺序存储结构一般采用循环队列的形式。循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图13-5所示。,循环队列的运算有如下两个： （1）入队运算：在循环队列的队尾加入一个新元素； （2）退队运算：在循环队列的队头位置退出一个元素并赋给指定的变量。 设循环队列的容量为m，循环队列中元素个数的计算方法如下： （1）如果rearfront，则循环队列中的元素个数为rear-front； （2）如果rearfront，则循环队列中的元素个数为m+(rear-front)。,13.1.5 线性链表 线性链表是线性表的链式存储结构。栈的链式存储结构，简称为链栈；队列的链式存储结构，简称为链队列。 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分，用于存放指针，称为指针域，其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。 线性链表可以分为三大类： （1）单链表：一个结点只有一个指针域指向后件结点，从任何一个结点开始只能扫描到其后的所有结点，如图13-6所示，其中，head表示头指针，“”表示空指针，以下同；,（2）双向链表：一个结点有两个指针域，分别指向前件结点和后件结点，从任何一个结点开始可以扫描到其后或其前的所有结点，如图13-7所示； （3）循环链表：所有结点的指针构成了一个环状链。循环链表的表头结点的指针域指向线性表的第一个元素的结点，循环链表中最后一个结点的指针域指向表头结点，从任何一个结点开始可以扫描到链表中的所有结点，如图13-8所示。,线性链表的主要运算有如下三种： （1）在线性链表中查找指定元素，主要目的是为线性链表的读写、插入和删除做准备； （2）在链式存储结构下的线性表中插入一个新元素； （3）在链式存储结构下的线性表中删除包含指定元素的结点。 线性链表在插入与删除过程中均不发生数据元素移动的现象，只需改变相关结点的指针即可，线性链表的物理存储结构可以不连续存放。,13.1.6 树与二叉树 树是一种简单的非线性结构，在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。 1树的基本概念 （1）父结点：每一个结点的前件称为该结点的父结点； （2）子结点：每一个结点的后件称为该结点的子结点； （3）树根结点：树中没有前件的结点； （4）叶子结点：树中没有后件的结点；,（5）结点的度：一个结点所拥有的后件个数称为该结点的度； （6）树的度：树中所有结点中的最大度称为树的度； （7）树的深度：树的最大层次称为树的深度，根结点在第一层； （8）子树：以某结点的一个子结点为根所构成的树称为该结点的一棵子树，叶子结点没有子树。,2二叉树及其基本性质 二叉树具有两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，称为该结点的左子树和右子树。 （1）二叉树的基本性质 性质1 在二叉树的第k层上最多有2k-1 (k1)个结点。 性质2 深度为m的二叉树最多有2m-1个结点。 性质3 在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。 性质4 具有n个结点的二叉树，其深度至少为log2n+1。 其中，log2n表示取log2n的整数部分，以下同。,（2）满二叉树与完全二叉树 满二叉树是这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点；每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点，如图13-10所示。 完全二叉树是这样的一种二叉树：除最后一层外，每一层上的结点数均达到最大值；如果从根结点开始，对二叉树的结点自上而下、自左至右用自然数（从1开始）进行连续编号，则深度为m，且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应。 完全二叉树的叶子结点只可能出现在层次最大的两层上；对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1，如图13-11所示。,根据完全二叉树的上述特点以及在任意一棵二叉树中，度为0的结点总是比度为2的结点多一个，可以看出：在一棵完全二叉树中最多有1个度为1的结点，而且 当完全二叉树的总结点数为偶数，设为2n时，则有n-1个度为2的结点，有1个度为1的结点，有n个叶子结点； 当完全二叉树的总结点数为奇数，设为2n+1时，则有n个度为2的结点，没有度为1的结点，有n+1个叶子结点。 完全二叉树的两个性质： 性质1 具有n个结点的完全二叉树的深度为log2n+1。,性质2 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点进行编号，则对于编号为k（k=1,2,n）的结点有如下结论： 若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为k/2； 若2kn，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点，显然也没有右子结点； 若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。 结论可以确定根结点及编号为k的结点的父结点的位置；结论可以确定编号为k的结点的左子结点的位置；结论可以确定编号为k的结点的右子结点的位置，同时也确定了它的左子结点的位置。 最后需要指出的是：满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树。,（3）二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构，二叉树的链式存储结构也称为二叉链表。根据完全二叉树的性质2，对于完全二叉树可以按层序进行顺序存储,但顺序存储结构对于一般的二叉树不适用。 （4）二叉树的遍历 二叉树的遍历是根据一定的规律访问二叉树中的每一个结点，并且每个结点只能访问一次。二叉树遍历有如下三种形式： 前序遍历 首先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树； 中序遍历 首先遍历左子树，然后访问根结点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树；,后序遍历 首先遍历左子树，然后遍历右子树，最后访问根结点，并且在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。 对于二叉树遍历有如下三个结论: 已知一棵二叉树的前序遍历序列与中序遍历序列，能惟一确定这棵二叉树； 已知一棵二叉树的前序遍历序列与后序遍历序列，不能惟一确定这棵二叉树； 已知一棵二叉树的中序遍历序列与后序遍历序列，能惟一确定这棵二叉树。,13.1.7 查找技术 查找是指在一个给定的数据结构中，查找某个指定的元素。这里仅介绍顺序查找和二分（对分、折半）查找。,1顺序查找 平均情况下，用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。对于大的线性表来说，顺序查找的效率是很低的，虽然顺序查找的效率不高，但在下列两种情况下，只能采用顺序查找： （1）如果线性表为无序表，即表中元素的排列是无序的，则不管是顺序存储结构还是链式存储结构，都只能采用顺序查找； （2）即使是有序线性表，如果采用链式存储结构，也只能采用顺序查找。 在长度为n的线性表中进行顺序查找，最坏情况下需要比较n次。 2二分（对分、折半）查找 二分查找只适用于顺序存储的有序线性表。 设长度为n的有序线性表（假设从小到大排列）所在区域的下界为low，上界为high，则中间位置mid=(low+high)/2，若此元素等于给定值（要查找的数据），则查找成功；若此元素大于给定值，则在区域mid+1high内进行二分查找；若此元素小于给定值，则在区域lowmid-1内进行二分查找。,在长度为n的有序线性表中进行二分（对分、折半）查找，最坏情况下需要比较log2n+1次。,【例13-1】长度为8的有序线性表（12,17,21,35,46,50,83,95），用二分查找法查找元素83，查找过程如图13-12所示。,13.1.8 排序技术 排序是指将一个无序序列整理成递增或递减的有序序列的过程。这里仅介绍交换类排序、插入类排序和选择类排序。 1交换类排序 （1）冒泡排序 冒泡（起泡）排序的基本思想是通过相邻数据元素的比较和位置交换，逐步将无序序列变成有序序列的过程。 最坏情况下，冒泡排序需要的比较次数为n(n-1)/2。,【例13-2】对无序序列（50,95,35,12,83,21,46,17）进行冒泡排序（从小到大排列），排序过程如图13-13所示。,（2）快速排序 快速排序的基本思想是从线性表中选取一个元素放入变量T中，对线性表从右边扫描直到某个小于T的元素，将该元素移到前面，对线性表从左边扫描直到某个大于T的元素，将该元素移到后面，反复不断地从右、左两个方向扫描，结果就将线性表分成了两个子表，T插入到其分界线的位置处，这个过程称为线性表的划分，通过对线性表的一次划分，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，后面子表中的所有元素均不小于T；继续对划分后的两个子表按上述原则进行划分，并且，这种划分过程一直做下去，直到所有子表为空，此时的线性表就变成了有序表，如图13-14所示。 最坏情况下，快速排序需要的比较次数为n(n-1)/2。,【例13-3】对无序序列（50,95,35,12,83,21,46,17）进行快速排序（从小到大排列），排序过程如图13-15所示。,2插入类排序 插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。 （1）简单插入排序 简单插入排序的基本思想是将线性表中的第一个元素看成是一个有序的子序列，从第二个元素开始，首先将第k（k从2开始）个元素放到一个变量T 中，然后从有序子表的最后一个元素（即线性表中第k-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第k个元素）插入到刚移出的空位置上，。 最坏情况下，简单插入排序需要的比较次数为n(n-1)/2。,【例13-4】对无序序列（50,95,35,12,83,21,46,17）进行简单插入排序（从小到大排列），排序过程如图13-16所示。,（2）希尔排序 希尔排序的基本思想是将整个无序序列划分成若干小的子序列分别进行简单插入排序。 子序列的划分方法为：将相隔某个增量h的元素构成一个子序列，在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次简单插入排序，排序完成。 增量序列一般取ht=n/2k（k=1,2,log2n），其中n为无序序列的长度。 希尔排序的效率与所选取的增量序列有关，如果选取上述增量序列，则最坏情况下，希尔排序所需要的比较次数为O(n1.5)。,【例13-5】对无序序列（50,95,35,12,83,21,46,17）进行希尔排序（从小到大排列），排序过程如图13-17所示。,3选择类排序 （1）简单选择排序 简单选择排序的基本思想是：假设第一个位置放最小的元素，最后一个位置放最大的元素，扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表为空。 最坏情况下，简单选择排序需要的比较次数为n(n-1)/2。,【例13-6】对无序序列（50,95,35,12,83,21,46,17）进行简单选择排序（从小到大排列），排序过程如图13-18所示。,（2）堆排序 具有n个元素的序列(h1,h2,hn)，当且仅当满足,或,i=1,2,n/2时，称为堆。由堆的定义可以看出，堆顶元素即第一个元素必为最大或最小的元素。,堆排序的基本思想是：首先将一个无序序列建成堆；将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后），不考虑已经交换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆；反复做第步，直到剩下的子序列为空。 调整建堆的过程为：将无序的初始序列看成一棵完全二叉树，从第n/2个元素（最后一个非叶子结点）开始，按照堆的定义调整建堆，直到根结点为止。 堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。最坏情况下，堆排序需要比较的次数为O(nlog2n)。,【例13-7】对无序序列（50,95,35,12,83,21,46,17）进行初始建堆的过程如图13-19所示。,13.2 程序设计基础 13.2.1 程序设计方法与风格 1程序设计的风格 程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思路。程序设计的风格强调简单和清晰，即“清晰第一，效率第二”。,要形成良好的程序设计风格，主要应注重和考虑的因素如下： （1）源程序文档化 符号名的命名； 程序注释：注释一般分为序言性注释和功能性注释。序言性注释通常位于每个程序的开头部分；功能性注释的位置一般嵌在源程序体中，主要描述相应的语句或程序做什么； 视觉组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进等技巧使程序层次清晰。 （2）数据说明的方法 包括数据说明的次序规范化、说明语句中变量安排有序化、使用注释来说明复杂数据的结构。,（3）语句的结构 程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。 （4）输入和输出 输入和输出信息是用户直接关心的，输入和输出方式和格式应尽可能方便用户的使用，因为系统能否被用户接受，往往取决于输入和输出的风格。,13.2.2 结构化程序设计 1结构化程序设计的原则 （1）自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标；先从最上层总目标开始设计，逐步使问题具体化； （2）逐步求精：对复杂问题，应设计一些子目标作过渡，逐步细化； （3）模块化：模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，每个小目标称为一个模块； （4）限制使用goto语句。,2结构化程序的基本结构 结构化程序设计的三种基本结构是：顺序结构、选择结构和循环结构。 3结构化程序的优点 程序易于理解、使用和维护；提高了编程工作的效率，降低了软件开发成本。,13.2.3 面向对象程序设计 1面向对象方法 面向对象方法的主要优点：与人类习惯的思维方法一致，以对象为中心；稳定性好；可重用性好；易于开发大型软件产品；可维护性好。 2面向对象的基本概念 （1）对象：客观世界中的实体称为问题域的对象； （2）类：类是具有相似性质的一组对象的抽象； （3）类的实例：一个具体的对象称为类的实例； （4）消息：用于请求对象执行某一处理或回答某些要求的信息；,（5）封装：是一种信息隐蔽技术，目的在于将对象的使用者和对象的设计者分开； （6）继承：表示类之间相似性的机制； （7）多态：同样的消息被不同的对象接受时，可导致不同的行为。,13.3 软件工程基础 13.3.1 软件工程的概念 1软件的定义与特点 （1）软件是程序、数据及相关文档的完整集合。文档是与程序开发、维护和使用有关的图文资料。 （2）软件的特点 软件是一种逻辑实体，而不是物理实体，具有抽象性； 软件的生产与硬件不同，一旦开发成功，可以大量拷贝； 软件在运行、使用期间不存在磨损、老化问题； 软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制；,软件复杂性高，成本昂贵； 软件开发涉及诸多的社会因素。 根据应用目标的不同，软件可以分为应用软件、系统软件和支撑软件（或工具软件）。 2软件工程 软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护。软件工程包括三个要素：方法、工具和过程。 软件工程的核心思想是把软件产品看作工程产品来处理，把需求计划、可行性研究、工程审核、质量监督等工程化的概念引入到软件生产中，以期达到工程项目的三个基本要素：进度、经费和质量的目标。,3软件工程过程与软件生命周期 （1）软件工程过程 软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。定义了两个方面的内涵：,软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件工程活动。基于这个方面，软件工程过程通常包含四种基本活动：P(Plan)软件规格说明；D(Do)软件开发；C(Check)软件确认；A(Action)软件演进； 从软件开发的观点来看，是使用适当的资源（包括人员、软硬件工具、时间等）为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化为输出（软件产品）。 （2）软件生命周期 软件产品从提出、实现、使用、维护到退役的过程称为软件生命周期。软件生命周期分为三个时期： 软件定义期：包括问题定义、可行性研究和需求分析三个阶段； 软件开发期：包括系统设计、详细设计、编码和测试四个阶段； 软件运行维护期：即运行维护阶段。,4软件工程的目标与原则 软件工程的目标是：在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。 基于软件工程的目标，软件工程的理论和技术研究的内容主要包括软件开发技术和软件工程管理。软件开发技术包括软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学；软件工程管理包括软件管理学、软件工程经济学、软件心理学等内容。 为了达到软件工程的目标，在软件开发过程中，必须遵循软件工程的基本原则，包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。,13.3.2 结构化分析方法 软件开发方法包括分析方法、设计方法和程序设计方法。 1需求分析与需求分析方法 软件需求是指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。,常见的需求分析方法： 结构化分析方法； 结构化分析方法是着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。 面向对象的分析方法。,2结构化分析的常用工具 （1）数据流（程）图：用于刻画数据流和转换的信息系统建模技术，数据流图由四种基本成分构成：数据流、数据处理、数据存储、外部实体，它们的符号如图13-20所示。,数据流程图有两种典型的结构形式：变换型（数据变换）和事务型（功能实现）。,（2）数据字典：是对数据流图中所有元素的定义的集合，是结构化分析的核心。数据流图和数据字典共同构成系统的逻辑模型，没有数据字典数据流图就不严格，没有数据流图，数据字典也难于发挥作用。 数据字典中有四种类型的条目：数据流、数据项、数据存储和数据加工。 （3）判定树：用图形方式描述数据流图中的处理或加工逻辑，如图13-21所示。,（4）判定表：能将所有条件组合充分表示出来，但建立过程较为繁杂。一张判定表由四个部分组成：左上部列出所有条件、左下部是所有可能的动作、右上部是表示各种条件组合的一个矩阵、右下部是与每种条件组合相对应的动作，见表13-1。,3.2.3 软件需求规格说明书 软件需求规格说明书（Software Requirement Specification，SRS）是需求分析阶段的最后成果，是软件开发中的重要文档之一，是作为需求分析的一部分而制定的可交付文档。,13.3.3 结构化设计方法 1软件设计的基本概念 软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。,结构化设计方法的基本思想是将软件设计成相对独立、单一功能的模块组成的结构。 评价模块独立性的主要标准有两个：一是模块之间的耦合，它表明两个模块之间互相独立的程度；二是模块内部的关系是否紧密，称为内聚。 一般来说，要求模块之间的耦合尽可能地弱，即模块尽可能独立，而要求模块的内聚程度尽量地高，即高内聚，低耦合。 耦合和内聚是一个问题的两个方面，耦合程度弱的模块，其内聚程度一定高。 软件设计分两步：概要设计和详细设计。 软件设计是一个迭代的过程，先进行高层次的结构设计，后进行低层次的过程设计，穿插进行数据设计和接口设计。,2概要设计 （1）概要设计的基本任务 概要设计的基本任务是：设计软件系统结构；数据结构及数据库设计；编写概要设计文档；概要设计文档评审。 常用的软件结构设计工具是结构图（Structure Chart，SC），也称程序结构图。使用结构图描述软件系统的层次和分块结构关系，它反映了整个系统的功能实现以及模块与模块之间的联系与通信，是未来程序中的控制层次体系。 结构图是描述软件结构的图形工具，结构图的基本图符如图13-22所示。,（2）由数据流程图导出结构图 结构化设计方法实际上是面向数据流程图的，即它的工作对象是在结构化分析方法中形成的数据流程图，因此，可以由数据流程图导出结构图。 3详细设计 详细设计的任务是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。 常见的过程设计工具有： 图形工具：程序流程图、N-S图、PAD图、HIPO图； 表格工具：判定表； 语言工具：PDL（过程设计语言）。,（1）程序流程图,（2）N-S图,（3）问题分析图PAD,（4）过程设计语言PDL,13.3.4 软件测试 1软件测试的目的 软件测试是在设想程序有错误的前提下进行的，其目的是设法暴露程序中的错误和缺陷，一个好的测试在于能发现至今未发现的错误，一个成功的测试是发现了至今未发现的错误，但测试只能说明程序有错，而不能证明程序无错，如果希望通过有限次的测试就能发现程序中的所有错误是不可能的，因此，程序不可能具有百分之百的可靠性。 2软件测试的准则 （1）所有测试都应追溯到用户需求； （2）严格执行测试计划，排除测试的随意性； （3）充分注意测试中的群集现象； （4）程序员应避免检查自己的程序； （5）穷举测试不可能； （6）妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便。,3软件测试方法 软件测试具有多种方法，依据软件是否需要被执行，可以分为静态分析和动态测试；依照功能划分，可以分为白盒测试和黑盒测试。 （1）静态分析； （2）动态测试； （3）白盒测试：是根据对程序内部逻辑结构的分析来选取测试用例。白盒测试的主要方法有：逻辑覆盖测试（语句覆盖、路径覆盖、判定覆盖、条件覆盖、判断条件覆盖）、基本路径测试等； （4）黑盒测试：也称功能测试或数据驱动测试，黑盒测试完全不考虑程序的内部结构和内部特征。黑盒测试的主要方法有:等价类划分法、边界值分析法、错误推测法。 4软件测试的实施 软件测试过程分为四个步骤：第步单元测试；第步集成测试；第步验收测试（确认测试）；第步系统测试。,13.3.5 程序调试 程序调试的任务是诊断和改正程序中的错误，调试主要在开发阶段进行。 1程序调试的基本步骤 （1）错误定位； （2）修改设计和代码，以排除错误； （3）进行回归测试，防止引进新的错误。 2软件调试方法 软件调试可分为静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试的，静态调试的主要方法有：强行排错法、回溯法、原因排除法。 3.软件测试与调试的关系 （1）测试的目的是暴露错误，评价程序的可靠性；而调试的目的是发现错误的位置，并改正错误；,（2）测试是揭示设计人员的过失，通常应由非设计人员来承担；而调试是帮助设计人员纠正错误，可以由设计人员自己承担； （3）测试是机械的、强制的、严格的，也是可预测的；而调试要求随机应变、联想、经验、智力，并要求自主地去完成； （4）经测试发现错误后，可以立即进行调试并改正错误；经过调试后的程序还需进行回归测试，以检查调试的效果，同时也可防止在调试过程中引进新的错误； （5）测试用例与调试用例可以一致，也可以不一致。,13.4 数据库设计基础 13.4.1 数据库系统的基本概念 1数据是描述事物的符号记录。 2数据库(Database，DB)是数据的集合，具有统一的结构形式并存放于统一的存贮介质内，是多种应用数据的集成，并可被多个应用所共享。,3数据库管理系统(Database Management System，DBMS)是数据库的管理机构，它是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护、数据服务等，是数据库系统的核心。 数据库管理系统的功能包括：数据模式定义；数据存取的物理构建；数据操纵；数据的完整性、安全性定义与检查；数据库的并发控制与故障恢复；数据服务等。 数据库管理系统提供的数据语言有三类： 数据定义语言(Data Definition Language，DDL)负责数据的模式定义与数据的物理存取构建； 数据操纵语言(Data Manipulation Language，DML)负责数据的操纵，包括查询、添加、删除、修改等操作； 数据控制语言(Data Control Language，DCL)负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能，包括系统初启程序、文件读写与维护程序、存取路径管理程序、缓冲区管理程序、安全性控制程序、完整性检查程序、并发控制程序、事务管理程序、运行日志管理程序和数据库恢复程序等。,4数据库管理员（Database Administrator，DBA） 主要工作有：数据库设计、数据库维护、改善数据库系统性能，提高系统效率。 5数据库系统 数据库系统（Database System，DBS）由数据库、数据库管理系统、数据库管理员、硬件、系统软件五个部分构成了一个以数据库为核心的完整的运行实体，称为数据库系统。 6数据库应用系统 数据库应用系统（Database Application System，DBAS）由数据库系统、应用软件及应用界面三个部分组成。,13.4.2 数据管理技术的发展与数据库系统的基本特点 数据管理技术的发展过程分为三个阶段：人工管理阶段、文件管理阶段以及数据库管理阶段。 数据库系统的基本特点是：数据的集成性；数据的高共享性与低冗余性；数据独立性；数据的统一管理与控制，包括数据的完整性检查、数据的安全性保护、并发控制。数据库技术的根本目标是要解决数据的共享问题。,数据的独立性一般分为两种： 物理独立性：当数据的物理结构包括存储结构、存取方式等改变时，应用程序不用改变； 逻辑独立性：当数据的逻辑结构改变时，应用程序不用改变。,13.4.3 数据库系统的内部体系结构 数据库系统的内部体系结构包括三级模式和两级映射，如图13-26所示。,13.4.4 数据模型 数据模型通常由数据结构、数据操作及数据约束三部分组成。 1三种不同应用层次的数据模型 （1）概念数据模型简称概念模型，是一种面向客观世界、面向用户的模型，与具体的数据库管理系统无关，与具体的计算机平台无关。概念模型着重于对客观世界复杂事物的结构描述以及它们内在联系的刻画。概念模型是整个数据模型的基础，较为有名的概念模型有E-R模型、扩充的E-R模型、谓词模型等。 （2）逻辑数据模型又称数据模型，是一种面向数据库系统的模型，该模型着重于数据库系统一级的实现，概念模型只有转换成数据模型后才能在数据库中得以表示。常见的逻辑数据模型有：层次模型、网状模型、关系模型、面向对象模型等。 （3）物理数据模型又称物理模型，是一种面向计算机物理表示的模型，此模型给出了数据模型在计算机中物理结构的表示。,2E-R模型 （1）E-R模型的基本概念 实体：现实世界中的事物可以抽象成为实体，实体是概念世界中的基本单位，它们是客观存在但又能相互区别的事物；具有共性的实体组成的集合称为实体集； 属性：现实世界中事物均有一些特性，这些特性可以用属性来表示； 联系：在现实世界中事物间的关联称为联系。 （2）实体集之间的联系 一对一的联系，简记为1:1； 一对多或多对一的联系，简记为1:M（1:m）或M:1（m:1）； 多对多的联系：简记为M:N或m:n。 （3）E-R模型中三个基本概念之间的联接关系 （4）E-R模型的图示法 E-R模型的图形表示称为E-R图。E-R图的基本图形表示如下：,实体集表示：在E-R图中，用矩形表示实体集，在矩形内写上实体集名； 属性表示：在E-R图中，用椭圆形表示属性，在椭圆形内写上属性名； 联系表示：在E-R图中，用菱形表示联系，在菱形内写上联系名。,3层次模型 层次模型的基本结构是树形结构。层次模型最明显的特点是层次清楚，构造简单，易于实现，它可以很方便地表示出一对一和一对多这两种实体集之间的联系，但不能直接表示多对多的联系，因此，对于复杂的数据关系，用层次模型表示比较麻烦。 4网状模型 网状模型是一个不加任何条件限制的无向图，它可以有一个以上的结点无父结点，但至少有一个结点有多于一个的父结点。 网状模型不仅具有层次模型的一些特点，而且能方便地描述较为复杂的数据关系，可以直接描述实体集之间多对多的联系。网状模型是层次模型的一般形式，层次模型则是网状模型的特殊情况。 网状模型和层次模型都属于格式化模型。,5关系模型 关系模型采用二维表来表示，简称表，每一个二维表称为一个关系；二维表由表框架（或表结构）及表元组（或表记录）组成；表框架由n个命名的属性组成，对属性的命名称为属性名，n称为属性元数，每个属性有一个取值范围称为值域，每个属性对应表中的一个列，称为元或字段；表中的每一行称为元组或记录，一个表框架可以包含m个元组，m称为表的基数。 表框架对应关系的模式，关系模式是对关系的描述，其格式如下： 关系名（属性名1,属性名2,属性名n）,（1）关系的性质 关系模型采用二维表来表示，二维表一般满足下面七个性质： 元组个数的有限性：二维表中元组个数是有限的； 元组的惟一性：二维表中元组均不相同； 元组的次序无关性：二维表中元组的次序可以任意交换； 元组分量的原子性：二维表中元组的分量是不可分割的基本数据项； 属性名惟一性：二维表中属性名互不相同； 属性的次序无关性：二维表中属性与次序无关，可任意交换； 分量值域的统一性：二维表属性的分量具有与该属性相同的值域。 （2）键 关系模型中的键或码具有标识元组、建立元组间联系等重要作用。在二维表中凡是能惟一标识元组的最小属性集称为该表的键或码，一个二维表可能有若干个键，它们称为该表的候选键或候选码，从二维表的所有候选键中选取一个作为用户使用的键称为主键或主码，一般主键也简称键或码。,如果一个关系中的属性或属性组合不是该关系的主键，但它们是另外一个关联关系的主键，则称其为该关系的外键或外码。,（3）关系操作 关系模型中对数据的操作有四种：查询、添加、删除、修改。这四种操作的对象都是关系，而且操作的结果也是关系，因此都是建立在关系上的操作。 （4）关系中的数据约束 关系模型允许定义三类数据约束：实体完整性约束（该约束要求关系的主键中属性值不能为空值，这是数据库完整性的最基本要求）、参照完整性约束（该约束是关系之间相关联的基本约束，它不允许关系引用不存在的元组，即在关