第9 软件工程与数据库技术基础

第八章软件开发与信息处理技术软件工程基础数据库设计基础算法与数据结构程序设计基础8.1软件工程基础软件的非精确定义：计算机系统中与硬件相互依存的一部分，它是由程序、数据和相关文档组成的完整集合。软件生产经过了程序设计、程序系统和软件工程三个时代。8.1软件工程基础软件的规模大小、复杂程度决定了软件开发的难度，因此，必须采用科学的软件开发方法，采用抽象、分解等科学方法降低复杂度，以工程的方法管理和控制软件开发的各个阶段，以保证大型软件系统的开发具有正确性、易维护性、可读性和可重用性8.1.1软件工程基本概念软件的发展大致分为四个阶段：（如下图）阶段第一阶段第二阶段第三阶段第四阶段程序设计阶段程序系统阶段软件工程阶段(结构化方法发)软件工程阶段(面向对象方法)典型技术面向批处理有限的分布自定义软件多用户实时数据库软件产品分布式系统嵌入“智能”低成本硬件消费者的影响强大的桌面系统面向对象技术专家系统人工神经网络网络计算机软件危机和软件工程软件危机主要表现在：对软件开发成本和进度的估计常常很不准确，经费预算经常突破，完成时间一再拖延；开发的软件不能满足用户要求，用户软件不满意的现象经常发生；开发的软件可维护性差、可靠性差软件工程：运用系统的、规范的和可定量的方法开发、运行和维护软件。它包含三个要素：方法（Methodologies）工具（Tools）过程（Procedures）软件工程过程和软件生命周期软件工程过程软件生命周期软件生命周期模型软件工程的目标和原则软件开发工具与软件开发环境下图为软件生命周期各阶段的任务：时期阶段任务文档软件计划问题定义理解用户要求，划清工作范围计划说明书可行性研究可行性方案及代价需求分析软件系统的目标及应完成的工作需求规格说明书软件开发概要设计系统的逻辑设计软件概要设计说明书详细设计系统模块设计软件详细设计说明书软件编码编写程序代码程序、数据、详细注释软件测试单元测试、综合测试测试后的软件、测试大纲、测试方案与结果软件维护软件维护运行和维护维护后的软件软件开发工具与开发环境软件开发工具：是为支持软件人员开发和维护活动而使用的软件。作用：可以帮助开发人员完成一些繁琐的程序编制和调试问题，是软件开发人员将更多的精力和时间投放到最重要的软件需求和设计上，提高软件开发的速度和质量。软件开发过程问题定义可行性研究需求分析与需求分析方法结构化分析方法概述软件需求规格说明书件设计阶段分为：系统的总体设计或概要设计（确定软件系统结构）系统的详细设计（进行各模块的具体设计）8.1.4软件测试一、软件测试的目的与任务目的：确保软件的质量，尽量找出软件错误并加以纠正，而不是证明软件没有错。任务:测试任务（通过采用一定的测试策略，找出软件中的错误）调试任务或纠错任务（如果测试到错误，则定位软件中的错误，加以纠正）二、软件测试的准则三、软件测试技术与方法综述方法：静态测试法动态测试法技术：白盒测试用例设计黑盒测试用例设计8.1.4软件测试8.1.5程序的调试程序调试可以分为：静态调试（主要通过人的思维来分析源程序代码和排错，是主要的调试手段）动态调试（是静态调试的辅助）主要的调试方法有：强行排错法回溯法原因排除法8.2数据库设计基础数据库概念数据模型数据库设计与管理8.2.1数据库概念数据（Data）数据处理（DataProcessing）数据库（Database，DB）数据库管理系统（DatabaseManagementSystem，DBMS）数据库管理员（DatabaseAdministrator，DBA）数据库系统（DatabaseSystem，DBS）数据库应用系统（DatabaseApplicationSystem，DBAS）8.3数据结构与算法算法数据结构的基本概念及术语线性表栈队列树与二叉树查找与排序9.3.1算法定义：是对特定问题求解步骤的一种描述。或者说，是为求解某问题而设计的步骤序列特征：有穷性确定性有效性输入输出数据的存储结构一、顺序存储结构主要特点：结点中只有自身信息域，没有连接信息域，因此存储密度大，存储空间利用率高可以通过计算直接确定数据结构中第i个结点的存储地址Li，计算公式：L0+（i-1）m。（其中L0为第一个结点的存储地址，m为每个结点所占用的存储单元个数插入、删除运算不便，会引起大量结点的移动9.3.2数据结构的基本概念及术语二、链式存储结构主要特点：结点中除自身信息之外，还有表示连接信息的指针域，因此比顺序存储密度小，存储空间利用率低逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图等多种逻辑结构的存储表示插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可数据的运算检索：在数据结构里查找满足一定条件的结点插入：往数据结构里增加新的结点删除：把指定的结点从数据结构里去掉更新：改变指定结点的一个或多个域的值排序：保持线性结构的结点序列里结点数不变，把结点按某种指定的顺序重新排列9.3.2数据结构的基本概念及术语9.3.3线性表线性表是最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列（a1,a2,…,an）顺序表：指用顺序存储结构存储的线性表链表：用链式存储结构存储的线性表栈和队列——是对线性表的插入、删除运算可以发生的位置加以限制的两种特殊的线性表顺序表和一维数组各种高级语言里的一维数组就是用顺序方式存储的线性表，因此常用一维数组称呼顺序表若顺序表中结点个数为n，则：插入一个结点平均需要移动之结点个数为n/2，算法的时间复杂度是O(n)；删除一个结点平均需移动结点个数为（n-1）/2，算法的时间复杂度是O(n);链表线性链表（单链表）：删除算法的时间复杂度为O(n)，其主要执行时间是搜索删除位置循环链表：指链表的最后一个结点的指针值指向第一个结点，整个链表形成一个环（如下图）…结点1结点2结点n9.3.4栈栈：是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。空栈：指表中无元素栈中有元素a1,a2,…,an，如下页图所示，称a1为栈底元素。新元素进栈要置于an之上，删除或退栈先对an进行，即“后进先出”（LIFO）的操作原则栈的物理存储可以用顺序存储结构或链式存储结构栈的运算还有取栈顶元素，检查栈是否为空，清除等。栈的插入和删除ABACBABAFEBAATOPTOPTOPTOPTOPTOPan…a2a1进栈出栈栈底栈结构(3)(1)(2)(5)(4)(6)9.3.5队列队列：是限定所有的插入都在表的一端进行，所有的删除都在表的另一端进行的线性表。进行删除的一端叫队列的头，进行插入的一端叫队列的尾，如下页图所示。在队列中，新元素总是加入到队尾，每次删除的总是对头元素，即当前“最老的”元素，这就是“先进先出”（FIFO）的操作原则队列的物理存储可以用：顺序存储结构，也可用链式存储结构队列的示意（如下图）出队列a1a2a3…an入队列头尾队列的插入和删除示例初态插入A插入B删除A插入C插入D删除B插入EFRAFRRRRRRFFFFFFBABBBCCCCDDD溢出7.3.6树与二叉树树形结构是一类重要的非线性结构，树和二叉树是最常见的树形结构树（Tree）:是一个或多个结点组成的有限集合T，有一个特定的结点称为根（Root），其余的结点分为m（m≥0）个不相交的集合T1，T2，…，Tm，每个集合又是一棵树，称作这个根的子树（Subtree)树形结构的常用术语结点的度（Degree）：一个结点的子树的个数树的度：树中各结点的度的最大值树叶（Leaf）：度为0的结点分支结点：度不为0的结点双亲（Parent）、子女（Child）：结点的各子树的根称作该结点的子女；相应的该结点称作其子女的双亲兄弟（Sibling）：具有相同双亲的结点互为兄弟结点的层数（Level）树的深度（Depth）森林（Forest）二叉树二叉树（BinaryTree）:是n（n≥0)个结点的有限集合，这个集合或者为空集（n=0），或者由一个根结点及两棵不相交的、分别称作这个根的坐姿树和右子树的二叉树组成二叉树不是树的特殊情形，二者的区别：二叉树为有序树性质：1、在二叉树的i层上，最多有2i-1个结点（i≥1）2、深度为k的二叉树最多有2k-1个结点(k≥1)完全二叉树一棵深度为k且具有2k-1个结点的二叉树称为满二叉树（FullBinaryTree）深度为k，有n个结点的二叉树，当且仅当其妹一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树树的二叉树表示在树（森林）与二叉树间有一个自然的一一对应的关系，每一棵树都能唯一的转换到它所对应的二叉树把树和森林转化成对应的二叉树：凡是兄弟就用线连起来，然后去掉双亲到子女的连线，只留下道第一个子女的连线不去掉二叉树的存储二叉树的存储通常采用:链接方式。每个结点除存储结点自身的信息外再设置两个指针域IIink和rlink，分别指向结点的左子女和右子女，当结点的某个指针为空时，则相应的指针值为空（NIL）。结点的形式为：IIinkinforlink二叉树的遍历遍历一个树形结构是指：按一定次序系统的访问该结构中的所有结点，使每个结点恰好被访问一次前序遍历法（NLR次序）访问根，按前序遍历左子树，按前序遍历右子树后序遍历法（LRN次序）按后序遍历左子树，按后序遍历右子树，访问根中序遍历法（LNR次序）按中序遍历左子树，访问根，按中序遍历右子树9.3.7查找查找：是数据结构中的基本运算衡量一个查找运算法的主要标志是：查找过程中对关节码进行的平均比较次数，或称平均检索长度，以n的函数的形式表示，n是数据结构中的结点个数顺序查找顺序查找：是线性表的最简单的查找方法方法：用待查关键码与线性表中各结点的关键码值逐个比较，若找出相等的关键码值则查找成功，若找遍所有结点都不相等，则查找失败优点：对线性表的结点逻辑次序和存储结构无要求缺点：平均检索长度大假设表中各结点被查找的概率相同，即P=1/n,则顺序查找成功的平均查找长度为(n+1)/2二分法查找二分法查找：是一种效率较高的线性表查找方法。要进行二分法查找，线性表结点必须是按关键码值排号顺序的，且线性表以顺序方式存储方法：首先用要查找的关键码值与线性表中间位置结点的关键码值相比较，这个中间结点把线性表分成两个子表，比较相等则查找完成，不等则根据比较结果确定下一步的查找应在哪个子表中进行，如此下去，直到找到满足条件的结点优点：平均检索长度小，为㏒2n。每经过一次关键码比较，则将查找范围缩小一半，因此经过㏒2n次比较就可完成查找过程缺点：排序线性表花费时间，顺序方式存储插入、删除不便9.3.8排序排序：是数据处理中经常使用的一种运算分类：直接插入排序选择排序冒泡排序快速排序A.直接插入排序的基本方法：每步将一个待排序记录按其关键码值的大小插入到前面已排序的文件中适当位置上，直到全部插入为止B.选择排序的基本思想：每一趟在n-i+1(i=1,2,…,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。它为最简单且为我们最熟悉的排序C.冒泡排序的基本方法：将待排序的记录顺次两两比较，若为逆序，则进行交换D.快速排序：又称分区交换排序，是对冒泡排序的一种改进。快速排序的基本方法：在待排序序列中任取一个记录，以它为基准用交换的发方法将所有记录分成两部分，关键码比它小的在一个部分，关键码值比它大的在另一个部分。再分别对两个部分实施上述过程，一直重复到排序完成下图为四种排序方法的比较：排序方法平均时间最坏情况辅助存储直接插入排序选择排序冒泡排序快速排序O(n2)O(n2)O(n2)O(n㏒2n)O(n2)O(n2)O(n2)O(n2)O(1)O(1)O(1)O(㏒2n)9.4程序设计基础程序设计语言发展程序设计方法与风格结构化程序设计面向对象的程序设