二级教程 公共基础知识.doc

第1章 数据结构与算法第一节 算法 一、算法的基本概念 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算机方法，程序可以作为算法的一种描述。（算法也可以用流程图、专门的描述语言、自然语言来描述。） 1、算法的基本特征： （1）可行性，针对实际问题而设计的算法，执行后能够得到满意的结果。 （2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报，要使算法有效必须为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2、算法的基本要素 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 （1）算法中对数据的运算和操作： 在计算机系统中，基本运算和操作有以下4类： 算术运算：主要包括加、减、乘、除等运算； 逻辑运算：主要包括“与”、“或”、“非”等运算； 关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； 数据传输：主要包括赋值、输入、输出操作。 （2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 3、算法设计的基本方法 （1）列举法 列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 （2）归纳法 归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。 （3）递推 递推是指从已知初始条件出发，逐次推出所要求的各中间结果和最后结果。 （4）递归 人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。 递归分为直接递归与间接递归两种。 （5）减半递推技术 所谓“减半”，就是将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。 例：二分查找 （6）回溯法 在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的线路再逐步试探。二、算法的复杂度 算法复杂度：算法时间复杂度和算法空间复杂度。 1、算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，只依赖于问题的规模，它是问题的规模函数。即：算法的工作量=f(n) （1）平均性态 所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 （2）最坏情况复杂性 所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。第二节 数据结构的基本概念数据结构作为计算机的一门学科，主要研究和讨论以下三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 讨论以上问题的目的是为了提高数据处理的效率，所谓提高数据处理的效率有两个方面： （1）提高数据处理的速度； （2）尽量节省在数据处理过程中所占用的计算机存储空间。一、什么是数据结构 数据结构是指反映数据元素之间的关系的数据元素集合的表示，包括数据的逻辑结构和存储结构。1、 数据的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 一个数据的逻辑结构应包含以下两方面信息： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 一个数据的逻辑结构可以用二元关系表示为：B=（D，R），其中B表示数据结构，D表示数据元素的集合，R表示D中各数据元素之间的前后关系。 例：一年四季的数据结构可以表示为： B=（D，R） D=春，夏，秋，冬 R=(春，夏)，（夏，秋），（秋，冬） 例：家庭成员的数据结构可以表示为： B=(D,R) D=父亲，儿子，女儿 R=(父亲，儿子)，（父亲，女儿） 数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。二、数据结构的图形表示 例：一年四季数据结构的图形表示 例：家庭成员数据结构的图形表示 方框表示数据元素值，称为结点；向线从前件结点指向后件结点，表示为各数据元素之间的前后件关系。 没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）。三、线性结构与非线性结构 线性结构：有且只有一个根结点；每个结点最多一个前件，最多只有一个后件。常见的线性结构有线性表、栈、队列 非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。常见的非线性结构有树、二叉树、图等。 线性结构与非线性结构都可以使空的数据结构。对于空的数据结构，如果对该数据结构的运算时按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。第三节 线性表及顺序存储结构一、线性表的基本概念 线性表是n（n=0）个元素构成的有限序列（a1,a2,an）。表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。 非空线性表有如下一些结构特征： （1）有且只有一个根结点，它无前件； （2）有且只有一个终端结点，它无后件； （3）除了根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。二、线性表的顺序存储结构 线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储结构具备如下两个基本特征： （1）线性表中的所有元素所占用的存储空间是连续的； （2）线性表中各数据元素在存储空间中师按逻辑顺序依次存放的。 线性表第i个元素ai的存储位置为 ADR(ai)=ADR(a1)+(i-1)*k (k表示每个元素占用的字节数) 线性表的顺序存储结构是一种随机存取的存储结构。 在线性表的顺序存储结构下，可以对线性表做的运算：插入、删除、查找、排序、分解、合并、复制、逆转。三、顺序表的插入运算 线性表的插入运算是指在表的第i（1=i=n+1）个位置上，插入一个新结点x,使长度为n的线性表 （a1,a2,ai-1,ai.,an）变为长度为n+1的线性表 （a1,.,ai-1,x,ai,an）插入运算的基本步骤是：1） 将结点ai,an各后移一位以便腾出第i个位置；2） 将x置入该空位；3） 表长加1。算法分析：1） 合法的插入位置共n+1个，即第1个位置到第n+1个位置。2） 最坏情况是插入到第一个位置，共需移动n个元素。3） 最好情况是插入到第n+1个位置，不需要移动元素。4） 在插入位置等概率情况下，平均移动元素的个数为：（n+(n-1)+(n-2)+2+1+0）/ (n+1)=n / 2 5）在第i个位置上插入需要移动n-i+1次。四、顺序表的删除运算 线性表的删除运算是指将表的第i（1=i=front时，为rear-front2） 当S=0时，为零。3） 当rear=front且s=1时，为m。4） 当rear=0）个结点组成的有限集合。若n=0，称为空树；若n0，则：1） 有一个特定的称为根（root）的结点。它只有直接后件，但没有直接前件；2） 除根结点以外的其他结点可以划分为m（m=0）个互不相交的有限集合T0,T1,.,Tm-1,每个集合Ti（i=0，1，2。，m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前件，但可以有0个或多个直接后件。 树型结构具有如下特点：1） 每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根；2） 每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点；3） 一个结点所拥有的后件个数称为树的结点度；4） 树的最大层次称为树的深度。二、二叉树的定义及其基本性质 1、线性链表 二叉树（binary tree）是由n（n=0）个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。 二叉树具有如下特点：1） 非空二叉树只有一个根结点；2） 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。 在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。 2、二叉树的基本性质 性质1：在二叉树的第K层上至多有个结点（k=1）。 性质2：深度为m的二叉树至多有个结点。 性质3：对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。 如果叶子结点，度为2的结点数为，则。 证明： 设度为1的结点数目为，二叉树的结点总数为n，有 设m表示分支数，具有n个结点的二叉树的分支总数为n-1，则有 m=n-1 而所有这些分支不是来自于度为1的结点就是来自于度为2的结点，即每一个度为1的结点发出一个分支，每一个度为2的结点发出两个分支。于是有 联立上面三个等式可以得到 证毕 3、满二叉树与完全二叉树 1）满二叉树 满二叉树：若二叉树中的结点，或者度为2，或者度为0，并且度为0的结点（叶结点）都集中在最下面一层，具有这种特点的二叉树称为满二叉树。三、二叉树的存储结构四、二叉树的遍历 所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个节点仅被访问一次。 1、前序遍历（根左右） 前序遍历是首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 2、中序遍历（左根右） 中序遍历是首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 3、后序遍历（左右根） 后序遍历是首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。第七节 查找技术一、顺序查找 顺序表查找算法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素比较，若相等表示查找成功，若表中所有元素与被查元素都不相等，则查找失败。 在查找成功时，最好的情况，查找长度为1；最坏的情况，查找长度为N;平均长度为（1+2+3+.+n）/ n =(n+1) / 2 。 在两种情况下只能用顺序查找：线性表为无序表、链式存储结构的有序表二、二分查找 在长度为n的有序顺序表中查找x的过程： 将x与中间项进行比较： 若x等于中间项的值，查找成功，查找结束。 若x小于中间项的值，则在中间项以前的部分以相同的方法进行查找； 若x大于中间项的值，则在中间项以后的部分以相同的方法进行查找。 这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。 例：对有序表（18，20，25，34，48，62，74，85）用二分查找法查找74，所需要比较次数为（ ）。 A、1次B、2次C、3次D、4次【分析】 第一趟：18 20 25 34 48 62 74 85 low mid high 第二趟：18 20 25 34 48 62 74 85 low mid high第3趟：18 20 25 34 48 62 74 85 low mid high【解答】C 二分法查找只适用于顺序存储的有序表（从小到大）。 对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较次。第八节 排序技术一、交换类排序法 冒泡排序与快速排序法属于交换类的排序方法 1、冒泡排序法 冒泡排序法的基本过程： 首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两个相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。 然后，从后面道前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样又消去了一个逆序。显然，在扫描过程中，不断地将两个相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面，这也是线性表中最小元素应有的位置。 对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。 原始序列： 5 1 7 3 1 6 9 4 2 8 6 第一遍（从前往后） 1 5 3 1 6 7 4 2 8 6 9 （从后往前） 1 1 5 3 2 6 7 4 6 8 9 第二遍（从前往后） 1 1 3 2 5 6 4 6 7 8 9 （从后往前） 1 1 2 3 4 5 6 6 7 8 9 。 假设线性表的长度为N,则在最坏的情况下，冒泡排序需要经过n / 2 遍的从前往后的扫描和n / 2 遍的从后往前扫描，需要的比较次数为 n（n-1）/ 2 。 2、快速排序法 从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。 如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。 无序线性表=T 分割二、插入类排序法 1简单插入排序法 指将无序序列中的各元素依次插入到已经有序的线性表中。在最坏情况下，简单插入排序需要n(n-1)/2次比较。 2希尔排序法 将整个无序序列分割成若干小的子序列分别进行插入排序。 分割方法如下： 将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序完成。 在最坏情况下，简单插入排序需要次比较。三、选择类排序法 1简单选择排序法 扫描整个线性表，从中选出最小的元素，将它交换到表达最前面；然后对剩下的子表采用同样的方法，直到表为空为止。 在最坏情况下，简单选择排序需要n(n-1)/2次比较。 2堆排法 在最坏情况下，堆排序需要o(nlog)次比较。总结排序次数：1、插入排序 最好情况下比较次数为n-1次，最坏情况下比较次数为n(n-1)/2次。其排序方法是稳定的。2、冒泡排序 最好情况下比较次数为n-1次，最坏情况下比较次数为n(n-1)/2次。其排序方法是稳定的。3、快速排序 最好情况下比较次数为n1og2n次，最坏情况下比较次数为n(n-1)/2次。其排序方法是不稳定的。第2章 程序设计基础第一节 程序设计方法与风格一、程序设计风格程序设计的风格总体而言应该强调简单和清晰，“清晰第一，效率第二”的论点是程序设计的风格。1源程序要文档化1) 符号名的命名2) 程序注释 3) 视觉组织2数据说明的方法 1) 数据说明的次序规范化 2) 说明语句中变量安排有序化 3) 使用注释来说明复杂数据的结构3语句的结构 程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般应该注意如下： 1）在一行内只写一条语句； 2）程序编写应优先考虑清晰性； 3）除非对效率有特殊要求，程序编写要做到清晰第一，效率第二； 4）首先要保证程序正确，然后才要求提高速度； 5）避免使用临时变量而使程序的可读性下降； 6）避免不必要的转移； 7）尽可能使用库函数； 8）避免采用复杂的条件语句； 9）尽量减少使用“否定”条件的条件语句；10）数据结构要有利于程序的简化；11）要模块化，使用模块功能尽可能单一化；12）利用信息隐蔽，确保每一个模块的独立性；13）从数据出发去构造程序；14）不要修补不好的程序，要重新编写；4输入和输出 1）对所有的输入数据都要检验数据的合法性； 2）检查输入项的各种重要组合的合理性； 3）输入格式要简单，以使得输入的步骤和操作尽可能简单； 4）输入数据时，应允许使用自由格式； 5）应允许缺省值； 6）输入一批数据时，最好使用输入结束标志；7）8）二、结构化程序设计 1结构化程序设计的原则 结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。 2结构化程序的基本结构与特点 1）顺序结构 2）选择结构 3）重复结构（循环） 3结构化程序设计原则和方法的应用三、面向对象的程序设计 1关于面向对象方法面向对象方法是以客观世界中的不同对象(客观存在的实体)为基本元素，并以类和继承来表达事物之间具有的共性和它们之间存在的关系。 具备以下优点 1）与人类习惯的思维方法一致 2）稳定性好 3）可重用性好 4）易于开发大型软件产品 5）可维护性好 2面向对象方法的基本概念 1）对象：客观世界中的任何实体，每个对象都有它的属性和操作。 对象有如下一些基本特征： i) 标识唯一性 ii）分类性 iii）封装性 iv）模块独立性好 2）类（class）和实例（instance）: 是一组具有相同属性和相同操作的对象的集合。一个类中的每个对象都是这个类的一个实例。 3）消息（message）：面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。例如，一个汽车对象具有“行驶”这项操作，那么要让汽车以时速50公里行驶的话，需传递给汽车对象“行驶”及“时速50公里”的消息。通常，一个消息由下述三部分组成：i）接收消息的对象的名称；ii）消息标识符（也称为消息名）； iii）零个或多个参数。接口 接受对象发送对象 消息 操作名、参数 口 4）继承（inheritance）：使用已有的类定义为基础建立新类的定义技术。广义地说，是指能够直接获得已有的性质和特征，而不必重复定义它们。 继承具有传递性。如：类C继承类B，类B继承类A，则类C继承类A。 继承分为单继承与多重继承。 单继承：一个类只允许有一个父类。 多继承：一个类允许有多个父类。 继承的优点：相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余信息，提高软件的可重用性，便于软件修改维护。 5）多态性（polymorphism）：对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动。第3章 软件工程第一节 软件工程基本概念一、软件定义与特点 1计算机软件：包括程序、数据及相关文档的完整集合。 2软件特点 1）软是一种逻辑实体，而不是物理实体，具有抽象性。 2）软件的生产与硬件不同，它没有明显的制作过程。 3）软件在运行、使用期间不存在磨损、老化问题。 4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制。 5）软件复杂性高，成本昂贵。 6）软件开发涉及诸多的社会因素。 二、软件危机与软件工程 1软件危机：指在计算机软件的开发和维护过程中所遇到的一系列严重问题。主要表现在如下几个方面： 1）软件需求的增长得不到满足。用户对系统不满意的情况经常发生。 2）软件开发成本和进度无法控制。 3）软件质量难以保证。 4）软件不可维护或维护程度非常低。 5）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。总之，可以将软件危机归结为成本、质量、生产率等问题。 2软件工程1）定义：应用计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。 2）研究软件工程的主要目的是提高软件生产率，提高软件质量，降低软件成本等。 3）3个要素：方法、工具和过程。三、软件工程过程和软件生命周期1软件工程过程（software engineering process） 1）定义：把输入转化为输出的一组彼此相关的资源活动。 2）内涵： i）软件工程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件工程活动。 ii）从软件开发的观点看，它就是使用适当的资源（包括人员、硬件工具、时间等），为开发软件进行的一组开发活动，在过程结束是将输入（用户要求）转化为输出（软件产品）。2软件生命周期（software life cycle） 1）定义：通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为生命周期。 2）三个阶段：l 定义阶段：包括可行性研究初步项目计划、需求分析l 开发阶段：包括概要设计、详细设计、实现（编码）、测试l 维护阶段：使用（运行）、维护、退役 3）软件生命周期图可行性研究初步项目计划 定义 阶段需求分析概要设计 详细设计 开发实现（编码） 阶段 测试使用（运行） 维护维护 阶段退役四、软件工程的目标与原则 1软件工程目标：软件开发技术和软件工程管理 2软件工程原则：l 抽象l 信息隐蔽l 模块化l 局部化l 确定性l 一致性l 完备性l 可验证性五、软件开发工具与软件开发环境 1软件开发工具 2软件开发环境第二节 结构化分析方法一、需求分析与需求分析法 1需求分析：指用户对目标软件系统在功能、行为、性能、设计约束等方面 期望。 1）任务：发现需求、求精、建模和定义需求过程。需求分析将创建所需的数据模型、功能模型和控制模型。 2）需求分析阶段的工作l 需求获取l 需求分析l 编写需求规格说明书l 需求评审 2需求分析法常见的需求分析法有l 结构化分析法（SA） 如：jackson方法，主要是面向数据流的结构化分析法l 面向对象的分析法(OOA)二、结构化分析方法 1关于结构化分析方法 结构化分析法是结构话程序设计理论在软件需求分析阶段的运用，其目的是帮助弄清用户对软件的需求。 2结构化分析的常用工具 1）数据流图（DFD）：描述数据处理过程的工具，逻辑模型的图形表示法。数据流图中的主要图形元素与说明如下： 加工（转换）。输入数据经加工变换产生输出。 数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名。 存储文件（数据源）。表示处理过程中存放各种数据的文件。 源，潭。表示系统和环境的接口，属系统之外的实体。 2）数据字典（DD）：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。也可以理解为对DFD中出现的被命名的图形元素的确切解释。 3）判定树 4）判定表3软件需求规格说明书（SRS） 1）软件需求规格说明书的作用l 便于用户、开发人员进行理解和交流l 反映出用户问题的结构，可以作为软件开发工作的基础和依据l 作为确认测试和验收的依据 2）软件需求规格说明书的内容 3）软件需求规格说明书的特点l 正确性l 无歧义性l 完整性l 可验证性l 一致性l 可修改性l 可追踪性 第三节 结构化设计方法一、软件设计的基本概念 1软件设计的基础软件设计是软件工程的重要阶段，是一个把软件需求转换为软件表示的过程。基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，即确定系统的物理模型。l 软件设计重要性和地位概括如下：l 软件开发阶段（设计、编码、测试）占据软件项目开发总成本绝大部份，是在软件开发中形成质量的关键环节l 软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径l 软件设计作出的决策，最终影响软件实现的成败l 设计是软件工程和软件维护的基础 2软件设计的基本原理 1）抽象 2）模块化 3）信息屏蔽 4）模块独立性：每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。内聚性：内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。耦合性：模块间互相连接的紧密程度的度量。耦合性与内聚性是模块独立性的两个定性标准，耦合与内聚是相互关联的。在程序结构中，各模块的内聚性越强，则耦合性越弱。在软件设计过程中，应尽量做到高内聚，低耦合。即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。 3结构化设计方法二、概要设计 1概要设计的任务 1）设计软件系统结构具体过程如下：l 采用某种设计方法，将一个复杂的系统按功能划分成模块l 确定每个模块的功能l 确定模块之间的接口，即模块之间传递的信息l 评价模块结构的质量 2）数据结构及数据库设计 3）编写概要设计文档 4）概要设计文档评审 2面向数据流动设计方法 1）数据流类型：变换型和事务型 3设计的原则 1）提高模块独立性 2）模块规模适中 3）深度、宽度、扇出和扇入适当 4）使模块的作用域在该模块的控制域内 5）应减少模块的接口和界面的复杂性 6）设计成单入口、单出口的模块 7）设计功能可预测的模块三、详细设计 详细设计的任务，是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。常见的过程设计工具有：图形工具：程序流程图，N-S,PAD/HIPO表格工具：判定表语言工具：PDL(伪码) 1程序流程图 2N-S图 3PAD图 4PDL第四节 软件测试一、软件测试的目的 软件测试是为了发现错误而执行程序的过程。其目的就是尽可能多地发现软件产品中的错误和缺陷。二、软件测试的准则 1所有测试都应追溯到需求 2严格执行测试计划，排除测试的随意性 3充分注意测试中的群集现象 4程序员应避免检查自己的程序 5穷举测试不可能 6妥善保存测试计划、测试用例、出错统计和最终分析报告，为维护提供方便三、软件测试技术与方法综述 1静态测试与动态测试 2白盒测试方法与测试用例设计白盒测试方法也称为结构测试或逻辑驱动测试。其主要方法有逻辑覆盖、基本路径测试等。 3黑盒测试方法与测试用例设计黑盒测试方法也称功能测试或数据驱动测试。其主要方法有等价划分法、边界值分析法、错误推测法、因果图等。四、软件测试的实施软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）和系统测试。第五节 程序的调试一、基本概念 在对程序进行了成功的测试之后将进入程序调试。程序调试的任务是诊断和改正程序中的错误。 1程序调试的基本步骤 1）错误定位 2）修改设计和代码，以排除错误 3）进行回归测试，防止引进新的错误 2程序调试的原则二、软件调试方法 1强行排错发 2回溯法 3原因排除法第 4 章 数据库设计基础第一节 数据库系统的基本概念一、数据、数据库、数据库管理系统 1数据（DATA）：描述事物的符号记录。 2数据库（DB）：是数据的集合，它具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可以被各个应用程序所共享。 3数据库管理系统（DBMS）：是数据库的机构，它是一种系统软件，负责数据库中的