计算机基础课件ppt-计算机软件基础知识.ppt

《计算机基础课件ppt-计算机软件基础知识.ppt》由会员分享，可在线阅读，更多相关《计算机基础课件ppt-计算机软件基础知识.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机软件基础知识 软件基础软件基础算法v算法的基本概念算法的基本概念算法：算法：是一组有穷指令集，是是一组有穷指令集，是解题方案的准确而完解题方案的准确而完整的描述整的描述。通俗地说，算法就是计算机解题的过程。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。不可能优于算法的设计。算法的基本特征：算法的基本特征：是一组严谨地定义运算顺序的规则，每是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。止。算法

2、不等于程序，程序不可能优于算法。算法不等于程序，程序不可能优于算法。基本特性基本特性可行性：根据实际问题设计的算法，执行得到满意结果可行性：根据实际问题设计的算法，执行得到满意结果确定性：每一步骤必须有明确定义，不允许有多义性。确定性：每一步骤必须有明确定义，不允许有多义性。有穷性：算法必须能在有限的时间内做完。有穷性：算法必须能在有限的时间内做完。输入和输出：拥有足够的情报，方可执行。输入和输出：拥有足够的情报，方可执行。算法的基本要素1.1.对数据对象的运算和操作对数据对象的运算和操作算术运算：、算术运算：、等等逻辑运算：逻辑运算：、=、=、!=!=等等关系运算：关系运算：andand、o

3、ror、notnot等等数据传输：数据传输：w w、r r等等2.2.算法的控制结构算法的控制结构算法中各操作之间的执行顺序算法中各操作之间的执行顺序描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、N-SN-S结构化流结构化流程图、算法描述语言等程图、算法描述语言等算法可以用算法可以用顺序、选择、循环顺序、选择、循环三种基本机构组合三种基本机构组合而成。而成。算法基本设计方法（1 1）列举法：）列举法：根据问题，列举所有可能的情况，并用问题根据问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。中给定的条件检验哪些是需要的，哪些是不需要的。（2 2）

4、归纳法：）归纳法：通过列举少量的特殊情况，经过分析，最后通过列举少量的特殊情况，经过分析，最后找出一般的关系。找出一般的关系。（3 3）递推：）递推：是指从已知的初始条件出发，逐次推出所要求是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。的各中间结果和最后结果。（4 4）递归：）递归：将问题逐层分解的过程。将问题逐层分解的过程。（5 5）减半递推技术：）减半递推技术：“减半减半”，是指将问题规模减半，是指将问题规模减半，而问题性质不变；而问题性质不变；“递推递推”，是指重复，是指重复“减半减半”过程。过程。（6 6）回溯法：）回溯法：分析问题，找出一个解决总线索，然后沿着分析问

5、题，找出一个解决总线索，然后沿着这个线索逐步试探。这个线索逐步试探。算法效率度量算法的复杂度v算法的复杂度：时间复杂度、空间复杂度算法的复杂度：时间复杂度、空间复杂度算法的时间复杂度算法的时间复杂度算法时间复杂度是指执行算法所需要的算法时间复杂度是指执行算法所需要的计算工作量计算工作量。工作量用算法所执行的工作量用算法所执行的基本运算次数基本运算次数来度量，而算法所执来度量，而算法所执行的基本运算次数是问题规模的函数，即行的基本运算次数是问题规模的函数，即 算法的工作量算法的工作量=f(nf(n)算法空间复杂度算法空间复杂度算法空间复杂度是指执行这个算法所需要的算法空间复杂度是指执行这个算法所

6、需要的内存空间内存空间。存储空间包括：存储空间包括：算法程序所占的空间、算法程序所占的空间、输入数据所占输入数据所占的空间、的空间、算法执行过程中所需要的额外空间算法执行过程中所需要的额外空间数据结构基本概念能输入到计算机中能输入到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合。符号的集合。整数整数(1,2)(1,2)、实数、实数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、图形、声音。图形、声音。数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运运算算的一般方法的学科。的一般方法的学科。数据结构基本概念计算机管理图书问

7、题计算机管理图书问题计算机管理图书问题计算机管理图书问题 图书馆里有各种卡片：有按书名编排的、有按作者图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间查询时间短，又要考虑节省空间 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。数据结构基本概念 最简单的办法之一是建立一张最简单的办法之一是建立一张表表，每一本书的信息，每一本书的信息在表中占一行，如在表中占一行，如 数据结构是一门

8、研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。数据结构基本概念 如何将如何将0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9这这1010个数存放在个数存放在计算机中能最快地达到你所需要的目的？计算机中能最快地达到你所需要的目的？目的不同，目的不同，最佳最佳的存储方方法就不同。的存储方方法就不同。从大到小排列：从大到小排列：9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,0输出偶数：输出偶数：0,2,4,6,8,1,3,5,7,90,2,4,6,8,1,3,5,7,9 数据元素在数据元素在计算

9、机中的表示计算机中的表示 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。数据结构基本概念对数据结构中的对数据结构中的节点进行操作节点进行操作处理处理(插入、删除、修改、查找、排序插入、删除、修改、查找、排序)数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。数据结构研究的主要内容v 数据结构主要研究以下三个方面的问题：数据结构主要研究以下三个方面的问题：数据的逻辑结构：数据的逻辑结构：数据集合中各元素的信息，及元数据集合中各元素的信息，及元素之间所固有的逻辑关系（素之间所

10、固有的逻辑关系（前后件关系前后件关系）数据的存储结构：数据的存储结构：各数据元素在计算机中的存储关各数据元素在计算机中的存储关系系对各种数据结构进行的运算对各种数据结构进行的运算 主要目的是为了提高数据的效率。主要目的是为了提高数据的效率。所谓提高数据处理的效所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。数据处理过程中所占用的计算机存储空间。数据结构类型 1数据的逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修

11、改等。、数据的运算：检索、排序、插入、删除、修改等。A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面 线性结构和非线性结构 线性结构条件线性结构条件线性结构条件线性结构条件n（1 1）有且只有一个根结点；）有且只有一个根结点；n（2 2）每一个结点最多有一个前件，也最多有一个后件。）每一个结点最多有一个前件，也最多有一个后件。n（3 3）首节点无前件，尾节点无后件。）首节点无前件，尾节点无后件。非线性结构：非线性结构：非线性结构：非线性结构：不满足线性结构条件的数据结构

12、不满足线性结构条件的数据结构注意：注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。则，不能称为线性结构。学学学学 生生生生 成成成成 绩绩绩绩 表表表表8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成绩成绩姓名姓名学号学号树形结构全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式非线性非线性结构结构 树形结构树

13、形结构树形结构树形结构树形结构ABCDEFGH树形结构树形结构树形结构树形结构 结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系HBCDEFGA图形结构 图形结构：节点间的连接任意图形结构：节点间的连接任意图形结构：节点间的连接任意图形结构：节点间的连接任意1423 D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)无向图无向图213 D=1,2,3 R=(1,2),(2,3),(3,2),(1,3)有向图有向图顺序存储与链式存储Lo+（n-1)*m元素元素n n.元素元素i i.元素元素2 2元

14、素元素1 1LoLo+mLo+(i-1)*m存储地址存储地址存储内容存储内容Loc(a)=Lo+（i-1)*m每个元每个元素所占素所占用的存用的存储单元储单元个数个数 顺序存储顺序存储顺序存储顺序存储常用于线性数据结构，常用于线性数据结构，将逻辑上相邻的数据元将逻辑上相邻的数据元素存储在物理上相邻的素存储在物理上相邻的存储单元里。存储单元里。三个弱点三个弱点三个弱点三个弱点插入或删除操作时，需插入或删除操作时，需移动大量元数。移动大量元数。长度变化较大时，需按长度变化较大时，需按最大空间分配。最大空间分配。表的容量难以扩充表的容量难以扩充顺序存储与链式存储 1346 元素3 1536 .153

15、6 元素2 1400 .元素4 1346 1400 元素1 1345 指针 存储内容存储地址1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 4head1345链式链式链式链式存储存储存储存储的地的地的地的地址映址映址映址映射表射表射表射表栈和队列 栈和队列栈和队列是两种运算时要受到某些特殊限制的线是两种运算时要受到某些特殊限制的线性表，故也称为性表，故也称为限定性的数据结构。限定性的数据结构。栈：栈：限定限定只能在表的一端进行插入和删除只能在表的一端进行插入和删除的特殊的线性表的特殊的线性表,此此种结构称为种结构称为后后进先出。进先出。n设栈设栈s=s=（a1a

16、1，a2a2，,aiai，anan）n其中其中a1a1是栈底元素，是栈底元素，anan是栈顶元素。是栈顶元素。n栈顶栈顶（top)top)：允许插入和删除的一端；：允许插入和删除的一端；n约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。n栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。a1 a2 .an进栈进栈出栈出栈栈顶栈顶栈底栈底栈和队列队列的主要运算队列的主要运算n设置一个空队列；设置一个空队列；n插入一个新的插入一个新的队尾（队尾（rearrear）元素，称元素，称为进队；为进队；n删除删除队头（队头（fr

17、ontfront）元素，称为出队；元素，称为出队；n读取队头元素；读取队头元素；a1 ,a2 ,a3 ,a4 ,an-1 ,an队队头头队队尾尾队列：队列：限定限定只能在表的一端进行插入，在表的另一端进行删除只能在表的一端进行插入，在表的另一端进行删除的线性表。的线性表。此种结构称为此种结构称为先进先出（先进先出（FIFOFIFO）表。表。栈和队列 3 2 1 0 (a)rear=front=0(队空）队空）e3 e4 (c)(c)e1,e2出队，出队，e4入队入队rear=4front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队队列的主要运算队列的主要运算n队空

18、时，令队空时，令rear=front=0;rear=front=0;元素个数元素个数rear-frontrear-frontn当有新元素当有新元素入队时，尾指针加入队时，尾指针加1 1，当有元素，当有元素出队时，头出队时，头指针加指针加1 1。故在非空队列中，头指针始终指向队头元素。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置前一个位置，而尾指针始终指向队尾元素的位置栈和队列计算循环队列长度计算循环队列长度：front=rear，队列长度，队列长度0；frontrear，队列长度，队列长度rear+size-front a1 ,a2 ,a3 ,a4 ,an-

19、1 ,an队队头头队队尾尾循环队列：循环队列：首尾相接首尾相接的队列的队列，逻辑上形成一个环状。，逻辑上形成一个环状。树与二叉树树的定义：树的定义：由一个或多个结点组成的有限集合。由一个或多个结点组成的有限集合。仅有一个根仅有一个根结点结点，结点间有明显的层次结构关系。，结点间有明显的层次结构关系。A C G T2D H I T3J M B E L KT1 F 现现实实世世界界中中，能能用用树树的的结结构构表表示示：学学校校的的行行政政关关系、书的层次结构、人类的家族血缘关系等。系、书的层次结构、人类的家族血缘关系等。树与二叉树树的基本概念：树的基本概念：树的基本概念：树的基本概念：结点（结点

20、（NodeNode）：）：树中的元素树中的元素结点的度（结点的度（DegreeDegree）：）：结点拥有的子树数。结点拥有的子树数。结点的层次：结点的层次：从根结点开始算起，根为第一层。从根结点开始算起，根为第一层。叶子（叶子（LeafLeaf）：）：度为零的结点，也称端结点。度为零的结点，也称端结点。孩子（孩子（ChildChild）：）：结点子树的根称为该结点的孩子结点。结点子树的根称为该结点的孩子结点。兄弟（兄弟（SiblingSibling）：）：同一双亲的孩子。同一双亲的孩子。双亲（双亲（ParentParent）：）：孩子结点的上层结点，称为其的双亲。孩子结点的上层结点，称为其的

21、双亲。深度（深度（Depth)Depth)：树中结点的最大层次数。树中结点的最大层次数。森林（森林（ForestForest）：）：M M棵互不相交的树的集合。棵互不相交的树的集合。A C G T2D H I T3J M B E L KT1 F树与二叉树二叉树（二叉树（Binary Tree）的定义）的定义二叉树的五种基本形态二叉树的五种基本形态二二叉叉树树一一种种特特殊殊的的树树型型结结构构，特特点点是是树树中中每每个个结结点点只只有有两两棵棵子树，且子树有左右之分，次序不能颠倒子树，且子树有左右之分，次序不能颠倒。空二叉树空二叉树 仅有仅有根结点根结点 右子树右子树为空为空 左子树左子树为

22、空为空左右子树左右子树均非空均非空因因为为树树的的每每个个结结点点的的度度不不同同，存存储储困困难难，使使对对树树的的处处理理算算法法很复杂。所以引出二叉树的理论。很复杂。所以引出二叉树的理论。满二叉树423167891011121314155 特点：所有分支结点都存在左右子树，且所有叶特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。子结点都在同一层上。完全二叉树4231678910 11125 非完全二叉树非完全二叉树4231678910 11125 完全二叉树完全二叉树 特点：除最后一层外，每一层都取最大结点数，特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该

23、层最后一层结点都集中在该层最左边最左边的若干位置。的若干位置。二叉树的基本性质A A、二叉树的第二叉树的第i i层上至多有层上至多有2 2i-1i-1（i i 1 1）个结点。）个结点。B B、深度为深度为h h的二叉树中至多含有的二叉树中至多含有2 2h h-1-1个结点。个结点。C C、若在任意一棵二叉树中，有若在任意一棵二叉树中，有n0n0个叶子结点（度为个叶子结点（度为0 0），有），有n2n2个度为个度为2 2的结点，则：的结点，则：n0=n2+1n0=n2+1D D、具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为loglog2 2n+1n+1，其中，其中 log

24、log2 2nn表示表示loglog2 2n n 的整数部分。的整数部分。423167891011121314155第三层第三层 (i=3)(i=3)，有，有2 23-13-1=4=4个节点个节点深度深度h=4h=4，共有，共有2 24 4-1=15-1=15个节点个节点n0=8,n2=7,n0=n2+1n0=8,n2=7,n0=n2+11515个节点，深度个节点，深度=log=log2 215+1=415+1=4二叉树的遍历 遍遍历历是是指指按按某某条条搜搜索索路路线线寻寻访访树树中中每每个个结结点点，且且每每个个结点只被访问一次。结点只被访问一次。按先左后右的原则，一般使用三种遍历：按先左

25、后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：先序遍历先序遍历(D L R):(D L R):访问访问根结点根结点，按先序遍历，按先序遍历左子树左子树，按先序遍历，按先序遍历右子树右子树。中序遍历中序遍历(L D R):(L D R):按中序遍历按中序遍历左子树左子树，访问，访问根结点根结点，按中序遍历，按中序遍历右子树右子树。后序遍历后序遍历(L R D):(L R D):按后序遍历按后序遍历左子树左子树，按后序遍历，按后序遍历右子树右子树，访问，访问根结点根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树为空时，执行空操作，

26、即空二叉树已遍历完。二叉树的遍历先序遍历：先序遍历：D L RD L R中序遍历：中序遍历：L D RL D R后序遍历：后序遍历：L R DL R DADBCT1T2T3D L RAD L RD L RBDCD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDAC DBCA软件工程基本概念软件的定义软件的定义软件的定义软件的定义 软件软件(software)是计算机系统中与硬件是计算机系统中与硬件(hardware)相互依存的另一相互依存的另一部分。部分。软件包括三个部分：程软件包括三个部分：程序序(program)、相关数据、相关数据(data)

27、、说明文档、说明文档(document)。软件的特点软件的特点软件的特点软件的特点n软件是软件是一种逻辑实体，不是物理实体，具有抽象性。一种逻辑实体，不是物理实体，具有抽象性。n软件没有明显的制造过程。软件没有明显的制造过程。n软件在使用过程中，没有磨损、老化问题软件在使用过程中，没有磨损、老化问题n软件依赖与硬件和环境，导致了移植问题软件依赖与硬件和环境，导致了移植问题n软件是复杂的，而且以后会更复杂软件是复杂的，而且以后会更复杂n软件的成本相当昂贵软件的成本相当昂贵n软件工作牵涉到很多社会因素软件工作牵涉到很多社会因素软件工程基本概念软件危机软件危机软件危机软件危机 早期的软件主要指程序，

28、采用个体工作方式，缺少相关文档，质量低，早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为维护困难，这些问题称为“软件危机软件危机”，软件工程概念的出现源自于软件软件工程概念的出现源自于软件危机危机。软件工程软件工程软件工程软件工程 软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。原则和方法来解决软件问题的工程。其目的是提高软件生产率、提高软件其目的是提高软件生产率、提高软件质量、降低软件成本。质量、降低软件成本。软件工程基本目标软件工程基本目标软件工程基本

29、目标软件工程基本目标 在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。足用户需求的产品。结构化分析方法结构化分析方法结构化分析方法结构化分析方法结构化分析方法 结构化程序设计理论在软件需求分析阶段的运结构化程序设计理论在软件需求分析阶段的运用，其用，其目的是帮助弄清用户对软件的需求。目的是帮助弄清用户对软件的需求。常用工具常用工具常用工具常用工具n数据流图、数据字典、判定树、

30、判定表数据流图、数据字典、判定树、判定表开发策略开发策略开发策略开发策略n自顶向下，逐层分解自顶向下，逐层分解结构化分析方法数据流图数据流图数据流图数据流图(DFD)(DFD)(DFD)(DFD)：以图形的方以图形的方式描绘数据在系统中流动和处理的过程，式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。辑模型的一种工具。加工加工存储文件存储文件源、源、潭潭数据流数据流加工（转换）：加工（转换）：输入数据经加工变换产生输出。输入数据经加工变换产生输出。数据流：数据流

31、：沿箭头方向传送数据的通道，旁边标注数据流名。沿箭头方向传送数据的通道，旁边标注数据流名。存储文件（数据源）：存储文件（数据源）：表示处理过程中存放各种数据的文件。表示处理过程中存放各种数据的文件。源、潭：源、潭：表示系统和环境的接口，属系统之外的实体。表示系统和环境的接口，属系统之外的实体。结构化分析方法数据字典数据字典数据字典数据字典(DD)(DD)(DD)(DD)：对所有与对所有与系统相关的数据元素的一个有组织的系统相关的数据元素的一个有组织的列表列表，其，其作用是对数据流图中出现的被命名的图形元素的确作用是对数据流图中出现的被命名的图形元素的确切解释切解释 。n数据字典常包括数据字典常

32、包括5 5个部分：个部分：数数据项、数据结构、数据流、据项、数据结构、数据流、数据存储、数据处理。数据存储、数据处理。n数据字典是结构化分析方法的核心数据字典是结构化分析方法的核心 判定树判定树：从问题定义的文字描述中分清哪些是判定的条件，：从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定之间的从属关系、并列关系、选择关系，根据它们构造判定树。树。判定表判定表：与判定树相似，当数据流图中的加工要依赖于多个：与判定树相似，当数据流图中的加工要依赖

33、于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。件取值的组合而引发的，使用判定表描述比较适宜。结构化设计方法需求分析主要解决需求分析主要解决“做什么做什么”的问题，而的问题，而软件设计软件设计主要解决主要解决“怎么做怎么做”的的问题。问题。从技术观点来看从技术观点来看，软件设计包括软件，软件设计包括软件结构设计结构设计、数据设计数据设计、接口设计接口设计、过过程设计程设计。n结构设计：结构设计：定义软件系统各主要部件之间的关系。定义软件系统各主要部件之间的关系。n数据设计：数据设计：将分

34、析时创建的模型转化为数据结构的定义。将分析时创建的模型转化为数据结构的定义。n接口设计：接口设计：描述软件内部、软件和协作系统之间以及软描述软件内部、软件和协作系统之间以及软件与人之间如何通信。件与人之间如何通信。n过程设计：过程设计：把系统结构部件转换成软件的过程性描述把系统结构部件转换成软件的过程性描述 结构化设计方法软件设计基本原理：软件设计基本原理：抽象抽象、模块化模块化、信息隐蔽信息隐蔽和和模块独立性模块独立性。n抽象：抽象：抽象是一种思维工具，就是把事物本质的共同特抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。性提取出来而不考虑其他细节。n模块化：模块化：解

35、决一个复杂问题时自顶向下逐步把软件系统解决一个复杂问题时自顶向下逐步把软件系统划分成较小的、相对独立但又不相互关联的模块的过程。划分成较小的、相对独立但又不相互关联的模块的过程。n信息隐蔽：信息隐蔽：模块的实施细节对于其他模块来说是隐蔽的。模块的实施细节对于其他模块来说是隐蔽的。n模块独立性：模块独立性：软件系统中每个模块只涉及软件要求的具软件系统中每个模块只涉及软件要求的具体的子功能，和软件系统中其他模块的接口是简单的。体的子功能，和软件系统中其他模块的接口是简单的。模块独立性指标：模块独立性指标：耦合性耦合性和和内聚性内聚性模块划分原则是：模块划分原则是：高内聚度，低耦合度高内聚度，低耦合

36、度结构化设计方法一般模块一般模块控制信息控制信息数据信息数据信息总体设计（概要设计）基本任务总体设计（概要设计）基本任务n1 1）设计软件系统结构）设计软件系统结构n2 2）数据结构及数据库设计）数据结构及数据库设计n3 3）编写概要设计文档）编写概要设计文档n4 4）概要设计文档评审）概要设计文档评审软软件结构设计工具件结构设计工具结构图结构图(程序结构图程序结构图)程序结构图的基本图符程序结构图的基本图符程序结构图的基本图符程序结构图的基本图符矩形矩形表示模块，表示模块，箭头箭头表示模块间的调用关系表示模块间的调用关系用带注释的箭头表示模块调用过程中来回传递的用带注释的箭头表示模块调用过程

37、中来回传递的信息信息 n实心圆箭头实心圆箭头表示控制信息，表示控制信息，空心圆箭头空心圆箭头表示数据信息表示数据信息 软件测试目的、意义、人员目的、意义、人员目的、意义、人员目的、意义、人员n通过合理的设计通过合理的设计测试用例测试用例以最少的人力和时间发现潜在以最少的人力和时间发现潜在的各种错误和缺陷的各种错误和缺陷n保证系统质量（满足需求规格）和可靠性保证系统质量（满足需求规格）和可靠性n由开发人员、用户一起完成由开发人员、用户一起完成 测试基本方法测试基本方法测试基本方法测试基本方法n人工测试（静态测试）：人工测试（静态测试）：评审软件文档或程序，评审软件文档或程序，包括代包括代码检查、

38、静态结构分析、代码质量度量。码检查、静态结构分析、代码质量度量。不实际运行软不实际运行软件件，主要通过人工进行。，主要通过人工进行。n机器测试（动态测试）：机器测试（动态测试）：通过运行软件通过运行软件，来检验结果的，来检验结果的正确性。正确性。主要包括主要包括白盒测试白盒测试方法和方法和黑盒测试黑盒测试方法。方法。白盒测试白盒测试（结构测试、逻辑驱动测试）白盒测试（结构测试、逻辑驱动测试）白盒测试（结构测试、逻辑驱动测试）白盒测试（结构测试、逻辑驱动测试）n将软件看成透明的白盒，将软件看成透明的白盒，根据程序的内部结构和逻辑结根据程序的内部结构和逻辑结构来设计测试例子，对程序的路径和过程进行

39、测试构来设计测试例子，对程序的路径和过程进行测试，检，检查是否满足设计的要求查是否满足设计的要求白盒测试基本原则白盒测试基本原则白盒测试基本原则白盒测试基本原则n保证所测模块中保证所测模块中每一独立路径每一独立路径至少执行一次；至少执行一次；n保证所测模块保证所测模块所有判断的所有判断的每一分支至少执行一次；每一分支至少执行一次；n保证所测模块每一循环都在边界条件和一般条件下至少保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；各执行一次；n验证验证所有内部数据结构所有内部数据结构的有效性。的有效性。黑盒测试黑盒测试（功能测试）黑盒测试（功能测试）黑盒测试（功能测试）黑盒测试（功能测

40、试）将软件看成黑盒子，将软件看成黑盒子，不考虑程序内部细节、结构和实现不考虑程序内部细节、结构和实现方式，仅仅测试软件的基本功能是否满足需要。方式，仅仅测试软件的基本功能是否满足需要。黑盒测试主要用于软件的确认测试。黑盒测试主要用于软件的确认测试。根据程序的根据程序的功能说明来功能说明来设计测试用例，基本设计方法有设计测试用例，基本设计方法有等价类划分法：等价类划分法：典型黑盒测试方法，将程序的所有可能的输入数典型黑盒测试方法，将程序的所有可能的输入数据划分成若干部分（及若干等价类），然后从每个等价类中选取据划分成若干部分（及若干等价类），然后从每个等价类中选取数据作为测试用例。数据作为测试用

41、例。边界值分析法：边界值分析法：它是对各种输入、输出范围的边界情况设计测试它是对各种输入、输出范围的边界情况设计测试用例的方法。用例的方法。错误推测法：错误推测法：人们可以靠经验和直觉推测程序中可能存在的各种人们可以靠经验和直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的用例。错误，从而有针对性地编写检查这些错误的用例。软件的调试基本任务基本任务基本任务基本任务根据测试时发现的错误，找出其原因和具体的位置，进根据测试时发现的错误，找出其原因和具体的位置，进行相应地更改。行相应地更改。在开放阶段，由在开放阶段，由开发人员开发人员来进行，谁开发的程序就由谁来进行，谁开发的程序就由

42、谁来进行调试。来进行调试。基本步骤基本步骤基本步骤基本步骤n错误定位、错误定位、错误纠正、错误纠正、回归测试回归测试，防止引入新，防止引入新的错误的错误软件调试可分为静态调试和动态调试。软件调试可分为静态调试和动态调试。静态调试主要是指通过人的静态调试主要是指通过人的思维来分析源程序代码和排错，是思维来分析源程序代码和排错，是主要的调试手段主要的调试手段，而动态调试是辅助，而动态调试是辅助静态调试。静态调试。数据库设计基础 数据、信息与数据处理数据、信息与数据处理n数据：数据：存储在某种媒体上的用来存储在某种媒体上的用来描述事物的能够识别的物理符号描述事物的能够识别的物理符号。如如文字、数字、

43、图形、声音、视频等。文字、数字、图形、声音、视频等。信息：信息：一种已经一种已经被加工为特定形式的数据被加工为特定形式的数据。对人们而言是可理解、可。对人们而言是可理解、可用于指导决策的数据用于指导决策的数据。数据处理：数据处理：对数据进行收集、组织、存储、加工和传播等工作。对数据进行收集、组织、存储、加工和传播等工作。是是将数据转换为信息的过程将数据转换为信息的过程，如，如“数据挖掘数据挖掘”。n n三者之间的关系：三者之间的关系：三者之间的关系：三者之间的关系：n数据是信息的载体和具体表现形式数据是信息的载体和具体表现形式n信息不随着数据形式的变化而变化信息不随着数据形式的变化而变化 n信

44、息数据数据处理信息数据数据处理计算机数据管理的发展 计算机数据管理计算机数据管理n数据处理中最重要的问题就是数据管理数据处理中最重要的问题就是数据管理，包括如何对数据，包括如何对数据分类、组织、编码、存储、检索和维护。随着计算机软、分类、组织、编码、存储、检索和维护。随着计算机软、硬件的不断升级，数据管理经历了以下几个阶段：硬件的不断升级，数据管理经历了以下几个阶段：数据库管理数据库管理文件系统文件系统人工管理人工管理独立性越来越高，独立性越来越高，使用越来越方便，使用越来越方便，技术越来越复杂技术越来越复杂数据库系统DBSDBS：以数据库应用为基础的计算机系统：以数据库应用为基础的计算机系统

45、数据库数据库数据库管理系统数据库管理系统硬件系统硬件系统数据库管理员（数据库管理员（DBADBA）组成组成用户用户数据库系统 数据库相关概念数据库相关概念n数据库（数据库（DBDB）：）：指存指存储在计算机内、有组织、储在计算机内、有组织、可共享可共享的的数据集合数据集合。它不仅包括数据本身，而且包括相关数据之间的联系。它不仅包括数据本身，而且包括相关数据之间的联系。数据库管理系统数据库管理系统(DBMS)：一种系统软件一种系统软件，用于数据库的建立、，用于数据库的建立、使用和维护使用和维护。如。如AccessAccess、SQL ServerSQL Server、FoxProFoxPro、O

46、racleOracle、DbaseDbase、DB2DB2、MySQLMySQL、SybaseSybase等待等待数据库应用系数据库应用系统：统：系统开发人员利用数据库系统资源开发的面向某系统开发人员利用数据库系统资源开发的面向某一类实际应用的软件系统。一类实际应用的软件系统。由数据库系统、应用软件、应用界面组成。由数据库系统、应用软件、应用界面组成。数据库数据库数据数据库管库管理系理系统统数据库应用系统数据库应用系统1数据库应用系统数据库应用系统2数据库管理系统（DBMS）数据库管理系统提供以下的数据语言：数据库管理系统提供以下的数据语言：(1)数据定义语言数据定义语言(DDL)：负责数据的

47、模式定义：负责数据的模式定义与数据的物理存取构建；与数据的物理存取构建；(2)数据操纵语言数据操纵语言(DML)：负责数据的操纵，如：负责数据的操纵，如查询与增、删、改等；查询与增、删、改等；(3)数据控制语言数据控制语言(DCL)：负责数据完整性、安全：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。性的定义与检查以及并发控制、故障恢复等。数数据语言按其使用方式具有两种结构形式：据语言按其使用方式具有两种结构形式：交互式交互式命令命令(又称自含型或自主型语言又称自含型或自主型语言)；宿主型语言；宿主型语言（一般可嵌入某些宿主语言中）。（一般可嵌入某些宿主语言中）。E-R模型1将人

48、们头脑中反映出来的信息世界用文字和将人们头脑中反映出来的信息世界用文字和符号记录下来，是构成数据模型的依据符号记录下来，是构成数据模型的依据用用E-RE-R图来组织数据库系统道德数据结构图来组织数据库系统道德数据结构23是用户与数据库设计人员之间交流的工具是用户与数据库设计人员之间交流的工具E-RE-R模型的举例模型的举例某高校教学组织管理情况为：某高校教学组织管理情况为：学校有若干个系部每个系有学校有若干个系部每个系有若干学生，每个学生可选修若干学生，每个学生可选修多门课程。请设计该校的教多门课程。请设计该校的教学管理的学管理的E-RE-R图。图。学生学生系部系部隶属隶属选课选课课程课程姓名

49、姓名学号学号性别性别系号系号成绩成绩课程号课程号学分学分系名系名系主任系主任1 1n nn nm课程名课程名说明：说明：矩形表示实体型，矩形框内为实体名；矩形表示实体型，矩形框内为实体名；椭圆表示属性，椭圆框内为属性名；椭圆表示属性，椭圆框内为属性名；菱形表示联系，菱形框内为联系名。菱形表示联系，菱形框内为联系名。实体：系部、学生和课程三个实体：系部、学生和课程三个 系部的属性包括：系号、系名、主任名；系部的属性包括：系号、系名、主任名；学生的属性包括：学号，姓名，性别；学生的属性包括：学号，姓名，性别；课程的属性包括：课程号，课程名，学分。课程的属性包括：课程号，课程名，学分。关系代数及关系

50、运算 用户需要利用查询从关系数据库中找到感兴趣的用户需要利用查询从关系数据库中找到感兴趣的用户需要利用查询从关系数据库中找到感兴趣的用户需要利用查询从关系数据库中找到感兴趣的数据时，需要对多个关系数据时，需要对多个关系数据时，需要对多个关系数据时，需要对多个关系(表表表表)进行运算。进行运算。进行运算。进行运算。关关关关系运算以系运算以系运算以系运算以关系代数为基础。关系代数为基础。关系代数为基础。关系代数为基础。关系的基本运算分为两类：关系的基本运算分为两类：关系的基本运算分为两类：关系的基本运算分为两类：传统集合运算：传统集合运算：传统集合运算：传统集合运算：并，交，差，笛卡尔积并，交，差