【文档说明】计算机软件基础知识概要课件.ppt，共(50)页，1.070 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2508.html

以下为本文档部分文字说明：

1计算机软件基础知识软件基础第1页，共50页。算法❖算法的基本概念٭算法：是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。٭算法的基本特征：是一组严谨地定义运算顺序的

规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。٭基本特性▪可行性：根据实际问题设计的算法，执行得到满意结果▪确定性：每一步骤必须有明确定义，不允许有多义性。▪有穷性：算法必须能在有限的时间内做完。▪输入和输出

：拥有足够的情报，方可执行。第2页，共50页。算法的基本要素٭1.对数据对象的运算和操作▪算术运算：＋、－、×、÷等▪逻辑运算：>、<、＝、>=、<=、!=等▪关系运算：and、or、not等▪数据传输：w、r等٭2.算法的控制结构▪算法中各操作之间的执行顺序▪描述

算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等▪算法可以用顺序、选择、循环三种基本机构组合而成。第3页，共50页。算法基本设计方法（1）列举法：根据问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

（2）归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。（3）递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（4）递归：将问题逐层分解的过程。（5）减半递推技术：“减半”，是指

将问题规模减半，而问题性质不变；“递推”，是指重复“减半”过程。（6）回溯法：分析问题，找出一个解决总线索，然后沿着这个线索逐步试探。第4页，共50页。算法效率度量——算法的复杂度❖算法的复杂度：时间复杂度、空间复

杂度٭算法的时间复杂度▪算法时间复杂度是指执行算法所需要的计算工作量。▪工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)٭算法空间复杂度▪算法空间复杂度是指执行这个算法所需要的内存空间。▪存储空间包括：①算法程序所占的空间、②输入数据

所占的空间、③算法执行过程中所需要的额外空间第5页，共50页。数据结构基本概念能输入到计算机中并能被计算机程序处理的符号的集合。整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。数

据结构是一门研究数据组织、存储和运算的一般方法的学科。第6页，共50页。数据结构基本概念计算机管理图书问题图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间数据结构是

一门研究数据组织、存储和运算的一般方法的学科。第7页，共50页。数据结构基本概念最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如数据结构是一门研究数据组织、存储和运算的一般方法的学科。第8页，共50页。数据结

构基本概念如何将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数据元素在计算机中的表示数据结构是一门研究数据组织、存储和运算的一般方法的学科。第9页，共50页。数据结构基本概念对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序)数据结构是一门研究数据组织、存储和运算的

一般方法的学科。第10页，共50页。数据结构研究的主要内容❖数据结构主要研究以下三个方面的问题：٭数据的逻辑结构：数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系）٭数据的存储结构：各数据元

素在计算机中的存储关系٭对各种数据结构进行的运算主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。第11页，共50页。数据结构类型1．数据的逻辑结构2、数据的存储结构3、数据

的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面第12页，共50页。线性结构和非线性结构线性结构条件◼（1）有且只有一个根结点；◼（2）每一个结点最多有一个前件，也最多

有一个后件。◼（3）首节点无前件，尾节点无后件。非线性结构：不满足线性结构条件的数据结构注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。学生成绩表86胡孝臣9861

10395刘忠赏9861107100张卓9861109成绩姓名学号第13页，共50页。树形结构全校学生档案管理的树形结构的组织方式非线性结构树形结构第14页，共50页。树形结构ABCDEFGH树形结构—结点间具有分层

次的连接关系HBCDEFGA第15页，共50页。图形结构图形结构：节点间的连接任意1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}无向图213D={1,2,3}R={(

1,2),(2,3),(3,2),(1,3)}有向图第16页，共50页。顺序存储与链式存储Lo+（n-1)*m元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m每个元素所占用的存储单元个数顺序存储٭常用于线性数

据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。三个弱点٭插入或删除操作时，需移动大量元数。٭长度变化较大时，需按最大空间分配。٭表的容量难以扩充第17页，共50页。顺序存储与链式存储1346元素31536…….……..…….1536元素21400…….……

..…….∧元素413461400元素11345指针存储内容存储地址1536元素21400元素11346元素3∧元素4head1345链式存储的地址映射表第18页，共50页。栈和队列栈和队列是两种运算时要受到某些特殊限制的线性表，故也称为限定性的

数据结构。栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。◼设栈s=（a1，a2，…,ai，…，an）◼其中a1是栈底元素，an是栈顶元素。◼栈顶（top)：允许插入和删除的一端；◼约定top始终指向新数据元素将存放的位置。◼栈底（bot

tom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底第19页，共50页。栈和队列队列的主要运算◼设置一个空队列；◼插入一个新的队尾（rear）元素，称为进队；◼删除队头（front）元素，称为出队；◼读取队头元素；a1,a2,a3,a4,…………a

n-1,an队头队尾队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。第20页，共50页。栈和队列3210(a)rear=front=0(队空）e3e4(c)(c)e1,e2出队，e4入队rear=4

fronte1e2e3(b)rearfront(b)e1,e2,e3入队队列的主要运算◼队空时，令rear=front=0;元素个数＝rear-front◼当有新元素入队时，尾指针加1，当有元素出队时，

头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置第21页，共50页。栈和队列计算循环队列长度：①front=rear，队列长度＝0；②front<rear，队列长度＝rear-front；③front>rear，队列长度＝rear+size-fron

ta1,a2,a3,a4,…………an-1,an队头队尾循环队列：首尾相接的队列，逻辑上形成一个环状。第22页，共50页。树与二叉树树的定义：由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关

系。ACGT2DHIT3JMBELKT1F现实世界中，能用树的结构表示：学校的行政关系、书的层次结构、人类的家族血缘关系等。第23页，共50页。树与二叉树树的基本概念：结点（Node）：树中的元素结点的度（Degree）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第一

层。叶子（Leaf）：度为零的结点，也称端结点。孩子（Child）：结点子树的根称为该结点的孩子结点。兄弟（Sibling）：同一双亲的孩子。双亲（Parent）：孩子结点的上层结点，称为其的双亲。深度（Depth)：树中结点的最大层次数。

森林（Forest）：M棵互不相交的树的集合。ACGT2DHIT3JMBELKT1F第24页，共50页。树与二叉树二叉树（BinaryTree）的定义二叉树的五种基本形态二叉树一种特殊的树型结构，特点是树中

每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。空二叉树仅有根结点右子树为空左子树为空左右子树均非空因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的理论。第25页，共50页。满二叉树423167891

011121314155特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。第26页，共50页。完全二叉树423167891011125非完全二叉树423167891011125完全二叉树特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层

最左边的若干位置。第27页，共50页。二叉树的基本性质A、二叉树的第i层上至多有2i-1（i1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点（度为0），有n2个度为2的结点，则：n

0=n2+1D、具有n个结点的完全二叉树的深度为[log2n]+1，其中[log2n]表示log2n的整数部分。423167891011121314155第三层(i=3)，有23-1=4个节点深度h=4，共有24-1=15个节点n0=8,n2=7,n0

=n2+115个节点，深度=[log215]+1=4第28页，共50页。二叉树的遍历遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍历：先序遍历(DLR):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(LDR):按中序遍历左

子树，访问根结点，按中序遍历右子树。后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。第29页，共50页。二叉树的遍历先序遍历：DLR中序遍历：LDR后序遍历：LRDADBCT1T2T3DLRADLR

DLRBDCDLR以先序遍历DLR为例演示遍历过程ABDCBDACDBCA第30页，共50页。软件工程基本概念软件的定义软件(software)是计算机系统中与硬件(hardware)相互依存的另一部分。软件包括三个部分：程

序(program)、相关数据(data)、说明文档(document)。软件的特点◼软件是一种逻辑实体，不是物理实体，具有抽象性。◼软件没有明显的制造过程。◼软件在使用过程中，没有磨损、老化问题◼软

件依赖与硬件和环境，导致了移植问题◼软件是复杂的，而且以后会更复杂◼软件的成本相当昂贵◼软件工作牵涉到很多社会因素第31页，共50页。软件工程基本概念软件危机早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为“软件

危机”，软件工程概念的出现源自于软件危机。软件工程软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。其目的是提高软件生产率、提高软件质量、降低软件成本。软件工程基本目标在给定成本、进度的前提下，开发出具有有效

性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。第32页，共50页。结构化分析方法结构化分析方法结构化程序设计理论在软件需求分析阶段的运用，其目的是帮助弄清用户对软件的需求。常用工具◼数

据流图、数据字典、判定树、判定表开发策略◼自顶向下，逐层分解第33页，共50页。结构化分析方法数据流图(DFD)：以图形的方式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工

具。加工存储文件源、潭数据流٭加工（转换）：输入数据经加工变换产生输出。٭数据流：沿箭头方向传送数据的通道，旁边标注数据流名。٭存储文件（数据源）：表示处理过程中存放各种数据的文件。٭源、潭：表示系统和环境的接口，属系统之外的实体。第34页，共50页。结构化

分析方法数据字典(DD)：对所有与系统相关的数据元素的一个有组织的列表，其作用是对数据流图中出现的被命名的图形元素的确切解释。◼数据字典常包括5个部分：数据项、数据结构、数据流、数据存储、数据处理。◼数据字典是结构化

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

逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。第35页，共50页。结构化设计方法需求分析主要解决“做什么”的问题，而软件设计主要解决“怎么做”的问题。从技术观点来看，软件设计包括

软件结构设计、数据设计、接口设计、过程设计。◼结构设计：定义软件系统各主要部件之间的关系。◼数据设计：将分析时创建的模型转化为数据结构的定义。◼接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。◼过程设计：把系统结

构部件转换成软件的过程性描述第36页，共50页。结构化设计方法软件设计基本原理：抽象、模块化、信息隐蔽和模块独立性。◼抽象：抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。◼模块化：解决一个复杂问题时自顶向下逐步把软件系统划分成较小的、相对独立但又

不相互关联的模块的过程。◼信息隐蔽：模块的实施细节对于其他模块来说是隐蔽的。◼模块独立性：软件系统中每个模块只涉及软件要求的具体的子功能，和软件系统中其他模块的接口是简单的。▪模块独立性指标：耦合性和内聚性▪模块划分原则是：高内聚度，低耦合度第37页，共50页。结构化设计方法一般

模块控制信息数据信息总体设计（概要设计）基本任务◼1）设计软件系统结构◼2）数据结构及数据库设计◼3）编写概要设计文档◼4）概要设计文档评审软件结构设计工具—结构图(程序结构图)٭程序结构图的基本图符▪矩形表示模块，箭头表示模块间的调用关系▪用带注释的箭头表

示模块调用过程中来回传递的信息◼实心圆箭头表示控制信息，空心圆箭头表示数据信息第38页，共50页。软件测试目的、意义、人员◼通过合理的设计测试用例以最少的人力和时间发现潜在的各种错误和缺陷◼保证系统质量（满足需求规格）和可靠性◼由开发人员、用户一起完成测

试基本方法◼人工测试（静态测试）：评审软件文档或程序，包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。◼机器测试（动态测试）：通过运行软件，来检验结果的正确性。主要包括白盒测试方法和黑盒测试方法。第39页，共50页。白盒测试白盒测试（结构测试

、逻辑驱动测试）◼将软件看成透明的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对程序的路径和过程进行测试，检查是否满足设计的要求白盒测试基本原则◼保证所测模块中每一独立路径至少执行一次；◼保证所测模块所有判断的每一分支至少执

行一次；◼保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；◼验证所有内部数据结构的有效性。第40页，共50页。黑盒测试黑盒测试（功能测试）٭将软件看成黑盒子，不考虑程序内部细节、结构和实现方式，仅仅测试软件的基本功能是否满足需要。٭黑盒测试主要用于软件的确认测试。٭根据程序的

功能说明来设计测试用例，基本设计方法有▪等价类划分法：典型黑盒测试方法，将程序的所有可能的输入数据划分成若干部分（及若干等价类），然后从每个等价类中选取数据作为测试用例。▪边界值分析法：它是对各种输入、输出范围的边界情况设计测试用例的方法。▪错误推测法：人们可

以靠经验和直觉推测程序中可能存在的各种错误，从而有针对性地编写检查这些错误的用例。第41页，共50页。软件的调试基本任务٭根据测试时发现的错误，找出其原因和具体的位置，进行相应地更改。٭在开放阶段，由开发人员来进行，谁开发的程序就由谁来进行调试。基本步骤◼①错误定位、②错误纠

正、③回归测试，防止引入新的错误软件调试可分为静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试。第42页，共50页。数据库设计基础数据、信息与数据处理◼数据：存储在某种媒体上的用来描述事物的能够识别的物

理符号。如文字、数字、图形、声音、视频等。n信息：一种已经被加工为特定形式的数据。对人们而言是可理解、可用于指导决策的数据。n数据处理：对数据进行收集、组织、存储、加工和传播等工作。是将数据转换为信息的过程

，如“数据挖掘”。◼三者之间的关系：◼数据是信息的载体和具体表现形式◼信息不随着数据形式的变化而变化◼信息＝数据＋数据处理第43页，共50页。计算机数据管理的发展计算机数据管理◼数据处理中最重要的问题就是数据管理

，包括如何对数据分类、组织、编码、存储、检索和维护。随着计算机软、硬件的不断升级，数据管理经历了以下几个阶段：数据库管理文件系统人工管理独立性越来越高，使用越来越方便，技术越来越复杂第44页，共50页。数据库系统DBS：以数据库应用为基础的计算机系统数据库

数据库管理系统硬件系统数据库管理员（DBA）组成用户第45页，共50页。数据库系统数据库相关概念◼数据库（DB）：指存储在计算机内、有组织、可共享的数据集合。它不仅包括数据本身，而且包括相关数据之间的联系

。n数据库管理系统(DBMS)：一种系统软件，用于数据库的建立、使用和维护。如Access、SQLServer、FoxPro、Oracle、Dbase、DB2、MySQL、Sybase等待n数据库应用系统：系统开发人员利用数据库系统资源开发的面向某一类实际应用的软件系统。由数

据库系统、应用软件、应用界面组成。数据库数据库管理系统数据库应用系统1数据库应用系统2…第46页，共50页。数据库管理系统（DBMS）数据库管理系统提供以下的数据语言：(1)数据定义语言(DDL)：负责数

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

可嵌入某些宿主语言中）。第47页，共50页。E-R模型1将人们头脑中反映出来的信息世界用文字和符号记录下来，是构成数据模型的依据用E-R图来组织数据库系统道德数据结构23是用户与数据库设计人员之间交流的工具第48页，共50页。49E-R模型的举例某高校教学组织管理情况为：学校有若干个系部

每个系有若干学生，每个学生可选修多门课程。请设计该校的教学管理的E-R图。学生系部隶属选课课程姓名学号性别系号成绩课程号学分系名系主任1nnm课程名说明：①矩形表示实体型，矩形框内为实体名；②椭圆表示属性，椭圆框内为属性名；③菱形表示联系，菱形框内为联系名。实体：系部、学生和课程三个系部的属

性包括：系号、系名、主任名；学生的属性包括：学号，姓名，性别；课程的属性包括：课程号，课程名，学分。第49页，共50页。关系代数及关系运算用户需要利用查询从关系数据库中找到感兴趣的数据时，需要对多个关系(表)进行运算。关系运算以关系代数为基础。关系的基本运算分为两类

：传统集合运算：并，交，差，笛卡尔积专门关系运算：选择，投影，连接第50页，共50页。