大学计算机基础课件第8章 软件技术基础

算法的定义与基本特征

算法是一组有穷指令集，是解题方案的准确而完整的描述。

基本特征：可行性:算法中的每一步操作都能够通过执行有限次的基本运算在有限时间内实现。

确定性:算法的每一步操作都必须有确切定义，不得有任何歧义性。有穷性:算法必须能在有限的时间内做完，即能在执行有限个步骤后终止。输入:一个算法有n(n≥0)个初始数据的输入。输出:一个算法有一个或多个与有效信息的输出。

算法的基本要素数据对象的运算和操作

通常，一个计算机系统包含的基本的运算和操作有如下四类：算术运算：主要包括加、减、乘、除等运算。逻辑运算：主要包括与、或、非等运算。关系运算：主要包括大于、小于、等于、不等于等运算。数据传输：主要包括输入、输出、赋值等运算。算法的控制结构一个算法通常都可以由顺序、选择、循环三种基本控制结构组合而成。

8.1.2算法评价的准则正确性可读性健壮性算法复杂度

算法复杂度

算法的时间复杂度算法的空间复杂度8.1.3数据结构的概念数据结构的定义数据的逻辑结构数据的存储结构线性结构与非线性结构

数据结构的定义

数据结构是指相互之间存在着一种或多种关系（即联系）的数据元素的集合和该集合中数据元素之间的关系组成。记为：

Data_Structure={D，R}

其中，D是数据元素的集合，R是该集合中所有数据元素之间的关系的有限集合。

数据结构包括数据的逻辑结构和数据的存储结构(或称物理结构)。

数据的逻辑结构

反映数据元素之间逻辑关系的数据结构，而与它们在计算机中的存储位置无关。

集合结构线性结构树形结构图形结构集合线性树图

数据的存储结构

数据的存储结构（又称为物理结构）是指数据的逻辑结构在计算机存储空间中的存放形式。顺序存储结构链式存储结构链式存储结构中结点由两部分组成：一部分存储结点本身的值，称为数据域；另一部分存储该结点的后继结点的存储单元地址，称为指针域。数据域指针域结点的结构

线性结构与非线性结构线性结构

非线性结构

线性结构示意图树图8.1.4线性表

线性表是具有相同数据类型的n(n≥0)个数据元素的有限集(a1，a2，…，an)，每个元素的位置是线性(一维)的。线性表(a1，a2，…，an)的逻辑特征：

有且仅有一个开始结点a1(无直接前趋)；有且仅有一个终端结点an(无直接后继)；其余的结点ai(1<i<n)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表的两种结构:

顺序存储结构(顺序表)

链式存储结构(链表)

线性表的顺序存储结构

线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的各个数据元素，使得线性表中在逻辑结构上相邻的元素存储在相邻的物理存储单元中。可见，线性表的顺序存储结构具有以下两个基本特点：（1）线性表中的所有数据元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。顺序存储结构下的线性表操作

线性表的插入线性表的删除线性表的查找线性表的复制线性表的排序线性表的分解与合并8.1.5线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，对逻辑上相邻的数据元素不要求其物理位置相邻。因此，为了表示每个数据元素ai与其直接后继ai+1之间的逻辑关系，对各个数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映象，称为存储结点。它包括两个域：其中存储数据元素本身信息的域称为数据域；存储其直接后继存储位置的域称为指针域。

8.1.6栈和队列

栈和队列是软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同，但栈必须按照“先进后出”的规则进行操作，队列必须按照“先进先出”的规则进行操作。因此，栈和队列实际上是运算受限制的特殊线性表。

栈

栈是限制在表的一端进行插入和删除运算的线性表，又称为后进先出的线性表(LIFO表)，是一种特殊的线性表。表尾称为栈顶(top)，表头叫做栈底(bottom)，表中无元素时称为空栈。进栈出栈栈顶栈底ana2a1栈示意图

栈的物理存储可以用顺序存储结构，也可以用链式存储结构。

栈的顺序存储结构又称顺序栈，栈的顺序存储结构又称顺序栈，它用一组连续的存储空间依次存放自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的当前位置，基本运算有下列三种：入栈运算出栈运算

读栈顶元素

队列

插入在表一端进行，而删除在表的另一端进行，将这种数据结构称为队或队列。

队列的物理存储可以用顺序存储结构，也可以用链式存储结构。队列的基本运算有入队、出队、取队头、判队列空、插入和删除等。a2a1a3an出队列入队列头尾队列的示意8.1.7树、二叉树及二叉树的遍历

树的定义二叉树的定义及基本性质二叉树的存储

二叉树的遍历

树的定义

树是一种简单的非线性结构，所有元素之间的关系具有明显的层次特性。下图表示了一棵一般的树。

一般的树ABEKLFCGMDHIJ层次1234

二叉树的定义

二叉树（binarytree）也是一种非线性数据结构，它类似于树结构，但在某些方面又不同于树结构。二叉树具有以下两个特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。A只有根结点的二叉树ABCDEFGH

深度为4的二叉树

二叉树的几个基本性质

性质1：在二叉树第i层上至多有2i–1个结点 (i≥1)。性质2：深度为k的二叉树中，最多有2k–1 个结点(k≥1)。性质3：具有n个结点的完全二叉树的深度 是:[log2n]+1。性质4：在任意一棵二叉树中，若其叶子 结点数为n0,度为2的结点数为 n2，则：n0=n2+1。

二叉树的存储

二叉树的存储通常采用链接方式。它是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左子树和右子树所在的链结点的存储地址。结点的存储的结构为：lchilddaterchild

二叉树的遍历

先序遍历法中序遍历法后序遍历法

二叉树的遍历是指按照一定的次序访问二叉树中的所有结点，使得每个结点被访问一次，并且只被访问一次。

二叉树的遍历举例

例：给出如下图所示的一棵二叉树，写出对应的遍历序列。按先序遍历序列：

ABDHECFGI

按中序遍历序列：DHBEAFCIG按后序遍历序列：HDEBFIGCA二叉树的示例EBADHCFGI8.1.8查找技术

查找就是在某种数据结构中找出满足条件的结点。两种基本的查找方法：

顺序查找

二分法查找

顺序查找

顺序查找一般是在线性表中查找指定的元素，其基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示查找成功；若线性表中的所有元素都与被查元素进行了比较但都不相同，则表示线性表中没有要找的元素，即查找失败。

顺序查找的优点是既适用于顺序表（即线性表的顺序存储结构），也适用于线性链表（即线性表的链式存储结构）。

顺序查找的缺点是当线性表很大时，查找效率很低。顺序查找的时间复杂度为O(n)。

二分法查找

二分法查找的方法是：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功：若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。

二分法查找的优点：平均检索长度小，即每经过一次关键码比较，则将查找范围缩小一半，经过log2n

次比较就可完成查找过程。其缺点是:只适用于顺序存储的有序表，不适用于链式存储的有序表，并且，在查找之前要为建立有序表付出代价。

8.2软件工程基础软件的定义与特点软件危机与软件工程软件工程过程与软件生命周期软件工程的基本目标与原则软件开发工具与软件开发环境

8.2.1

软件工程的基本概念

软件的定义与特点软件的定义

软件并不完全等同于程序，而是包括程序、数据及相关文档的集合，可以描述成“软件=程序+数据+文档”。

软件的特点

软件是计算机系统中的逻辑实体，具有抽象性；没有明显的制作过程，一旦开发成功，可以大量拷贝同一内容的副本；软件在运行过程中不会因为使用时间过长而出现磨损、老化以及用坏等问题；出现了软件移植的问题；软件开发复杂性较高，开发周期较长，成本较大；软件开发还涉及诸多的社会因素。

软件危机与软件工程

软件危机

随着计算机技术的发展和计算机应用规模的不断扩大，软件需求量迅速增加，软件规模也越来越大，复杂度不断增加，软件已经成为制约计算机技术发展的“瓶颈”问题。软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。

软件工程

软件工程就是采用工程化的原理、技术和方法来开发、运行和维护软件。软件工程包含三个要素：方法(Methodologies)工具(Tools)过程(Procedures)

软件工程过程与软件生命周期

软件工程过程

软件工程过程实际上就是将软件工程的方法、工具综合起来，规定方法、工具使用的顺序、要求交付的文档资料、为保证质量和适应变化所需要的管理、软件开发各个阶段的任务，最终达到合理、及时进行软件开发，获得高质量、低成本的软件产品的目的。

软件生命周期

软件生命周期大体可分为三个时期：定义阶段、开发阶段及运行和维护阶段。

软件生命周期模型

软件过程模型：瀑布模型、快速原型模型、螺旋模型、增量模型、喷泉模型、变换模型、面向对象生存期模型等。

瀑布模型瀑布模型——软件工程中应用最广泛的软件过程模型软件测试软件设计需求分析软件维护软件编码软件计划瀑布模型

软件工程的基本目标与原则软件工程的基本目标：要付出较低的开发成本，达到要求的软件功能，取得较好的软件性能，开发的软件要易于移植和维护；能按时完成开发工作，及时交付使用。软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。

结构化方法结构化分析结构化设计结构化编程软件测试问题定义和可行性分析结构化方法的软件开发过程

结构化分析方法

结构化设计方法

结构化程序设计方法

8.2.2结构化分析方法

SA（StructuredAnalysis,结构化分析）是20世纪70年代中期由E.Yourdon等人提出的一种面向数据流开展需求分析的结构化分析方法。结构化分析一般采用自顶向下，逐层分解的方法来定义系统的需求，即先把分析对象抽象成一个系统，然后采用自顶向下、逐层分解的方法，将复杂的系统分解成简单的、能够清楚地被理解和表达的若干个子系统。结构化分析方法常用的工具有数据流图（DFD）、数据字典（DD）、结构化语言、判定树、判定表等。

结构化设计方法（StructuredDesign，SD）给出一组帮助设计人员在模块层次上区分设计质量的原理与技术。它通常与结构化分析方法衔接起来使用，以数据流图为基础得到软件的模块结构。SD方法尤其适用于变换型结构和事务型结构的目标系统。在设计过程中，它从整个程序的结构出发，利用结构图（StructureChart，SC）来描述系统的模块结构。8.2.3结构化设计方法8.2.4软件测试的目的和方法

软件测试的目的

软件测试的准则

软件测试的方法

软件测试的过程

软件测试的目的测试是程序的执行过程，目的在于发现错误一个好的测试用例在于能发现至今未发现的错误一个成功的测试是发现了至今未发现的错误的测试

软件测试的准则测试应该尽早进行，最好在需求阶段就开始介入

程序员应该避免检查自己的程序，软件测试应该由第三方构造

设计测试用例时应考虑到合法的输入和不合法的输入以及各种边界条件

充分注意测试中的群集现象

对测试错误结果一定要有一个确认过程

制定严格的测试计划

妥善保存测试计划、测试用例、出错统计和最终分析报告

软件测试的方法

若从是否需要执行被测软件的角度可分为静态测试和动态测试两大类。静态测试代码检查、静态结构分析、代码质量度量等。

动态测试

动态测试是基于计算机的测试，通过执行程序来发现错误的过程。动态测试也可分为两大类：黑盒测试和白盒测试。

软件测试的过程单元测试

集成测试

确认测试

系统测试

8.2.5程序的调试

程序调试通常也称为Debug，是在进行了成功的测试之后才开始的工作。它与软件测试不同，软件测试的目的是尽可能多地发现软件中的错误，而调试的任务则是根据测试时所发现的错误，进一步诊断，找出原因和具体的位置进行改正。软件测试贯穿整个软件生命周期，调试工作主要在开发阶段。8.3程序设计基础8.3.1

程序设计方法和风格

程序设计方法程序设