计算机软件基础知识讲解课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机软件基础知识,软件基础,算法,算法的基本概念,算法：,是一组有穷指令集，是,解题方案的准确而完整的描述,。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。,算法的基本特征：,是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。,算法不等于程序，程序不可能优于算法。,基本特性,可行性：根据实际问题设计的算法，执行得到满意结果,确定性：每一步骤必须有明确定义，不允许有多义性。,有穷性：算法必须能在有限的时间内做完。,输入和输出：拥有足够的情报，方可执行。,算法的基本要素,1.,对数据对象的运算和操作,算术运算：、,、,等,逻辑运算：,、,=,、,=,、,!=,等,关系运算：,and,、,or,、,not,等,数据传输：,w,、,r,等,2.,算法的控制结构,算法中各操作之间的执行顺序,描述算法的工具通常有传统流程图、,N-S,结构化流程图、算法描述语言等,算法可以用,顺序、选择、循环,三种基本机构组合而成。,算法基本设计方法,（,1,）列举法：,根据问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。,（,2,）归纳法：,通过列举少量的特殊情况，经过分析，最后找出一般的关系。,（,3,）递推：,是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。,（,4,）递归：,将问题逐层分解的过程。,（,5,）减半递推技术：,“减半”，是指将问题规模减半，而问题性质不变； “递推”，是指重复“减半”过程。,（,6,）回溯法：,分析问题，找出一个解决总线索，然后沿着这个线索逐步试探。,算法效率度量,算法的复杂度,算法的复杂度：时间复杂度、空间复杂度,算法的时间复杂度,算法时间复杂度是指执行算法所需要的,计算工作量,。,工作量用算法所执行的,基本运算次数,来度量，而算法所执行的基本运算次数是问题规模的函数，即,算法的工作量,=,f(n,),算法空间复杂度,算法空间复杂度是指执行这个算法所需要的,内存空间,。,存储空间包括：,算法程序所占的空间、,输入数据所占的空间、,算法执行过程中所需要的额外空间,数据结构基本概念,能输入到计算机中,并能被计算机程序处理的,符号的集合。,整数,(1,2),、实数,(1.1,1.2),字符串,(Beijing),、,图形、声音。,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据结构基本概念,计算机管理图书问题,图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。,如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据结构基本概念,最简单的办法之一是建立一张,表,，每一本书的信息在表中占一行，如,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据结构基本概念,如何将,0,1,2,3,4,5,6,7,8,9,这,10,个数存放在,计算机中能最快地达到你所需要的目的？,目的不同，,最佳,的存储方方法就不同。,从大到小排列：,9,8,7,6,5,4,3,2,1,0,输出偶数：,0,2,4,6,8,1,3,5,7,9,数据元素在,计算机中的表示,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据结构基本概念,对数据结构中的,节点进行操作,处理,(,插入、删除、修改、查找、排序,),数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据结构研究的主要内容,数据结构主要研究以下三个方面的问题：,数据的逻辑结构：,数据集合中各元素的信息，及元素之间所固有的逻辑关系（,前后件关系,）,数据的存储结构：,各数据元素在计算机中的存储关系,对各种数据结构进行的运算,主要目的是为了提高数据的效率。,所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。,数据结构类型,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,线性结构和非线性结构,线性结构条件,（,1,）有且只有一个根结点；,（,2,）每一个结点最多有一个前件，也最多有一个后件。,（,3,）首节点无前件，尾节点无后件。,非线性结构：,不满足线性结构条件的数据结构,注意：,在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。,学 生 成 绩 表,86,胡孝臣,9861103,95,刘忠赏,9861107,100,张卓,9861109,成绩,姓名,学号,树形结构,全校学生档案管理的树形结构的组织方式,非线性结构,树形结构,树形结构,A,B,C,D,E,F,G,H,树形结构,结点间具有分层次的连接关系,H,B,C,D,E,F,G,A,图形结构,图形结构：节点间的连接任意,1,4,2,3,D= 1 , 2 , 3 , 4,R=(1,2) , (1,3) , (1,4) , (2,3),(3,4) , (2,4) ,无向图,2,1,3,D= 1 , 2 , 3 ,R= (1,2) , (2,3) , (3,2) , (1,3) ,有向图,顺序存储与链式存储,L,o,+,（,n-1)*m,元素,n,.,元素,i,.,元素,2,元素,1,L,o,L,o,+m,L,o,+(i-1)*m,存储地址,存储内容,Loc(a,)=L,o,+,（,i-1)*m,每个元素所占用的存储单元个数,顺序存储,常用于线性数据结构，,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,三个弱点,插入或删除操作时，需移动大量元数。,长度变化较大时，需按最大空间分配。,表的容量难以扩充,顺序存储与链式存储,1346,元素,3,1536,.,.,.,1536,元素,2,1400,.,.,.,元素,4,1346,1400,元素,1,1345,指针,存储内容,存储地址,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,head,1345,链式存储的地址映射表,栈和队列,栈和队列,是两种运算时要受到某些特殊限制的线性表，故也称为,限定性的数据结构。,栈：,限定,只能在表的一端进行插入和删除,的特殊的线性表,此种结构称为,后进先出。,设栈,s=,（,a1,，,a2,，,ai,，,，,an,）,其中,a1,是栈底元素，,an,是栈顶元素。,栈顶（,top),：允许插入和删除的一端；,约定,top,始终指向新数据元素将存放的位置。,栈底（,bottom):,不允许插入和删除的一端。,a,1,a,2,.,a,n,进栈,出栈,栈顶,栈底,栈和队列,队列的主要运算,设置一个空队列；,插入一个新的,队尾（,rear,）,元素，称为进队；,删除,队头（,front,）,元素，称为出队；,读取队头元素；,a,1,a,2,a,3,a,4,a,n-1,a,n,队头,队尾,队列：,限定,只能在表的一端进行插入，在表的另一端进行删除,的线性表。此种结构称为,先进先出（,FIFO,）,表。,栈和队列,3 2 1 0,(a),rear=front=0(,队空）,e,3,e,4,(c),e1,e2,出队，,e4,入队,rear =4,front,e,1,e,2,e,3,(b),rear,front,(b)e1,e2,e3,入队,队列的主要运算,队空时，令,rear=front=0;,元素个数,rear-front,当有新元素,入队时，尾指针加,1,，当有元素,出队时，头指针加,1,。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置,栈和队列,计算循环队列长度,：,front=rear,，队列长度,0,；,frontrear,，队列长度,rear+size,-front,a,1,a,2,a,3,a,4,a,n-1,a,n,队头,队尾,循环队列：,首尾相接,的队列,，逻辑上形成一个环状。,树与二叉树,树的定义：,由一个或多个结点组成的有限集合。,仅有一个根结点,，结点间有明显的层次结构关系。,A,C,G,T,2,D,H,I,T,3,J,M,B,E,L,K,T,1,F,现实世界中，能用树的结构表示：学校的行政关系、书的层次结构、人类的家族血缘关系等。,树与二叉树,树的基本概念：,结点（,Node,）：,树中的元素,结点的度（,Degree,）：,结点拥有的子树数。,结点的层次：,从根结点开始算起，根为第一层。,叶子（,Leaf,）：,度为零的结点，也称端结点。,孩子（,Child,）：,结点子树的根称为该结点的孩子结点。,兄弟（,Sibling,）：,同一双亲的孩子。,双亲（,Parent,）：,孩子结点的上层结点，称为其的双亲。,深度（,Depth),：,树中结点的最大层次数。,森林（,Forest,）：,M,棵互不相交的树的集合。,A,C,G,T,2,D,H,I,T,3,J,M,B,E,L,K,T,1,F,树与二叉树,二叉树（,Binary Tree,）的定义,二叉树的五种基本形态,二叉树一种特殊的树型结构，特点是,树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒,。,空二叉树,仅有,根结点,右子树为空,左子树为空,左右子树均非空,因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的理论。,满二叉树,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。,完全二叉树,4,2,3,1,6,7,8,9,10,11,12,5,非完全二叉树,4,2,3,1,6,7,8,9,10,11,12,5,完全二叉树,特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层,最左边,的若干位置。,二叉树的基本性质,A,、,二叉树的第,i,层上至多有,2,i-1,（,i,1,）个结点。,B,、,深度为,h,的二叉树中至多含有,2,h,-1,个结点。,C,、,若在任意一棵二叉树中，有,n0,个叶子结点（度为,0,），有,n2,个度为,2,的结点，则：,n0=n2+1,D,、,具有,n,个结点的完全二叉树的深度为,log,2,n+1,，其中,log,2,n,表示,log,2,n,的整数部分。,4,2,3,1,6,7,8,9,10,11,12,13,14,15,5,第三层,(i=3),，有,2,3-1,=4,个节点,深度,h=4,，共有,2,4,-1=15,个节点,n0=8,n2=7,n0=n2+1,15,个节点，深度,=log,2,15+1=4,二叉树的遍历,遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。,按先左后右的原则，一般使用三种遍历：,先序遍历,(D L R):,访问,根结点,，按先序遍历,左子树,，按先序遍历,右子树,。,中序遍历,(L D R):,按中序遍历,左子树,，访问,根结点,，按中序遍历,右子树,。,后序遍历,(L R D):,按后序遍历,左子树,，按后序遍历,右子树,，访问,根结点,。,二叉树为空时，执行空操作，即空二叉树已遍历完。,二叉树的遍历,先序遍历：,D L R,中序遍历：,L D R,后序遍历：,L R D,A,D,B,C,T,1,T,2,T,3,D L R,A,D L R,D L R,B,D,C,D L R,以先序遍历,D L R,为例演示遍历过程,ABDC,BDAC,DBCA,软件工程基本概念,软件的定义,软件,(software),是计算机系统中与硬件,(hardware),相互依存的另一部分。,软件包括三个部分：程序,(program),、相关数据,(data),、说明文档,(document),。,软件的特点,软件是一种逻辑实体，不是物理实体，具有抽象性。,软件没有明显的制造过程。,软件在使用过程中，没有磨损、老化问题,软件依赖与硬件和环境，导致了移植问题,软件是复杂的，而且以后会更复杂,软件的成本相当昂贵,软件工作牵涉到很多社会因素,软件工程基本概念,软件危机,早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为“软件危机”，,软件工程概念的出现源自于软件危机,。,软件工程,软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。,其目的是提高软件生产率、提高软件质量、降低软件成本。,软件工程基本目标,在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。,结构化分析方法,结构化分析方法,结构化程序设计理论在软件需求分析阶段的运用，其,目的是帮助弄清用户对软件的需求。,常用工具,数据流图、数据字典、判定树、判定表,开发策略,自顶向下，逐层分解,结构化分析方法,数据流图,(DFD),：,以图形的方式描绘数据在系统中流动和处理的过程，,它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。,加工,存储文件,源、,潭,数据流,加工（转换）：,输入数据经加工变换产生输出。,数据流：,沿箭头方向传送数据的通道，旁边标注数据流名。,存储文件（数据源）：,表示处理过程中存放各种数据的文件。,源、潭：,表示系统和环境的接口，属系统之外的实体。,结构化分析方法,数据字典,(DD),：,对所有与系统相关的数据元素的一个有组织的列表,，其,作用是对数据流图中出现的被命名的图形元素的确切解释,。,数据字典常包括,5,个部分：,数据项、数据结构、数据流、数据存储、数据处理。,数据字典是结构化分析方法的核心,判定树,：从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们构造判定树。,判定表,：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。,结构化设计方法,需求分析主要解决,“做什么”,的问题，而,软件设计,主要解决,“怎么做”,的问题。,从技术观点来看,，软件设计包括软件,结构设计,、,数据设计,、,接口设计,、,过程设计,。,结构设计：,定义软件系统各主要部件之间的关系。,数据设计：,将分析时创建的模型转化为数据结构的定义。,接口设计：,描述软件内部、软件和协作系统之间以及软件与人之间如何通信。,过程设计：,把系统结构部件转换成软件的过程性描述,结构化设计方法,软件设计基本原理：,抽象,、,模块化,、,信息隐蔽,和,模块独立性,。,抽象：,抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。,模块化：,解决一个复杂问题时自顶向下逐步把软件系统划分成较小的、相对独立但又不相互关联的模块的过程。,信息隐蔽：,模块的实施细节对于其他模块来说是隐蔽的。,模块独立性：,软件系统中每个模块只涉及软件要求的具体的子功能，和软件系统中其他模块的接口是简单的。,模块独立性指标：,耦合性,和,内聚性,模块划分原则是：,高内聚度，低耦合度,结构化设计方法,一般模块,控制信息,数据信息,总体设计（概要设计）基本任务,1,）设计软件系统结构,2,）数据结构及数据库设计,3,）编写概要设计文档,4,）概要设计文档评审,软件结构设计工具,结构图,(,程序结构图,),程序结构图的基本图符,矩形,表示模块，,箭头,表示模块间的调用关系,用带注释的箭头表示模块调用过程中来回传递的,信息,实心圆箭头,表示控制信息，,空心圆箭头,表示数据信息,软件测试,目的、意义、人员,通过合理的设计,测试用例,以最少的人力和时间发现潜在的各种错误和缺陷,保证系统质量（满足需求规格）和可靠性,由开发人员、用户一起完成,测试基本方法,人工测试（静态测试）：,评审软件文档或程序，,包括代码检查、静态结构分析、代码质量度量。,不实际运行软件,，主要通过人工进行。,机器测试（动态测试）：,通过运行软件,，来检验结果的正确性。,主要包括,白盒测试,方法和,黑盒测试,方法。,白盒测试,白盒测试（结构测试、逻辑驱动测试）,将软件看成透明的白盒，,根据程序的内部结构和逻辑结构来设计测试例子，对程序的路径和过程进行测试,，检查是否满足设计的要求,白盒测试基本原则,保证所测模块中,每一独立路径,至少执行一次；,保证所测模块,所有判断的,每一分支至少执行一次；,保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；,验证,所有内部数据结构,的有效性。,黑盒测试,黑盒测试（功能测试）,将软件看成黑盒子，,不考虑程序内部细节、结构和实现方式，仅仅测试软件的基本功能是否满足需要。,黑盒测试主要用于软件的确认测试。,根据程序的,功能说明来,设计测试用例，基本设计方法有,等价类划分法：,典型黑盒测试方法，将程序的所有可能的输入数据划分成若干部分（及若干等价类），然后从每个等价类中选取数据作为测试用例。,边界值分析法：,它是对各种输入、输出范围的边界情况设计测试用例的方法。,错误推测法：,人们可以靠经验和直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的用例。,软件的调试,基本任务,根据测试时发现的错误，找出其原因和具体的位置，进行相应地更改。,在开放阶段，由,开发人员,来进行，谁开发的程序就由谁来进行调试。,基本步骤,错误定位、,错误纠正、,回归测试,，防止引入新的错误,软件调试可分为静态调试和动态调试。,静态调试主要是指通过人的思维来分析源程序代码和排错，是,主要的调试手段,，而动态调试是辅助静态调试。,数据库设计基础,数据、信息与数据处理,数据：,存储在某种媒体上的用来,描述事物的能够识别的物理符号,。,如文字、数字、图形、声音、视频等。,信息：,一种已经,被加工为特定形式的数据,。对人们而言是可理解、可用于指导决策的数据,。,数据处理：,对数据进行收集、组织、存储、加工和传播等工作。,是将数据转换为信息的过程,，如“数据挖掘”。,三者之间的关系：,数据是信息的载体和具体表现形式,信息不随着数据形式的变化而变化,信息数据数据处理,计算机数据管理的发展,计算机数据管理,数据处理中最重要的问题就是数据管理,，包括如何对数据分类、组织、编码、存储、检索和维护。随着计算机软、硬件的不断升级，数据管理经历了以下几个阶段：,数据库管理,文件系统,人工管理,独立性越来越高，使用越来越方便，技术越来越复杂,数据库系统,DBS,：以数据库应用为基础的计算机系统,数据库,数据库管理系统,硬件系统,数据库管理员（,DBA,）,组成,用户,数据库系统,数据库相关概念,数据库（,DB,）：,指存储在计算机内、有组织、,可共享,的,数据集合,。它不仅包括数据本身，而且包括相关数据之间的联系。,数据库管理系统,(DBMS),：,一种系统软件，用于数据库的建立、使用和维护,。如,Access,、,SQL Server,、,FoxPro,、,Oracle,、,Dbase,、,DB2,、,MySQL,、,Sybase,等待,数据库应用系统：,系统开发人员利用数据库系统资源开发的面向某一类实际应用的软件系统。,由数据库系统、应用软件、应用界面组成。,数据库,数据库管理系统,数据库应用系统,1,数据库应用系统,2,数据库管理系统（,DBMS,）,数据库管理系统提供以下的数据语言：,(1),数据定义语言,(DDL),：负责数据的模式定义与数据的物理存取构建；,(2),数据操纵语言,(DML),：负责数据的操纵，如查询与增、删、改等；,(3),数据控制语言,(DCL),：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。 数据语言按其使用方式具有两种结构形式： 交互式命令,(,又称自含型或自主型语言,),；宿主型语言（一般可嵌入某些宿主语言中）。,E-R,模型,1,将人们头脑中反映出来的信息世界用文字和,符号记录下来，是构成数据模型的依据,用,E-R,图来组织数据库系统道德数据结构,2,3,是用户与数据库设计人员之间交流的工具,E-R,模型的举例,某高校教学组织管理情况为：学校有若干个系部每个系有若干学生，每个学生可选修多门课程。请设计该校的教学管理的,E-R,图。,学生,系部,隶属,选课,课程,姓名,学号,性别,系号,成绩,课程号,学分,系名,系主任,1,n,n,m,课程名,说明：,矩形表示实体型，矩形框内为实体名；, 椭圆表示属性，椭圆框内为属性名；, 菱形表示联系，菱形框内为联系名。,实体：系部、学生和课程三个,系部的属性包括：系号、系名、主任名；,学生的属性包括：学号，姓名，性别；,课程的属性包括：课程号，课程名，学分。,关系代数及关系运算,用户需要利用查询从关系数据库中找到感兴趣的数据时，需要对多个关系,(,表,),进行运算。,关系运算以关系代数为基础。,关系的基本运算分为两类：,传统集合运算：,并，交，差，笛卡尔积,专门关系运算：,选择，投影，连接,