软件技术基础

主讲教师：朱海华机电学院15B426Email:zhuhh@软件技术基础1绪

论工程软件概述计算机三大应用领域：科学计算、信息处理、过程控制。随着信息技术的普及，各类计算机软硬件系统在工程应用领域的广泛应用。工程软件在实际工程应用中占有相当重要的地位。工程软件主要应用领域包括：

工程辅助系统：工程数值计算（EngineeringComputation）、计算机辅助设计CAD、计算机辅助制造CAM、计算机辅助工程教育CAEE、计算机集成制造系统CIMS、计算机辅助测试CAT、工业控制IC、计算机仿真CS等。

工程事务处理：分为事务型系统、管理型系统、决策型系统。

现代工程通信及信息交流：通过支持计算机网络的工程软件不仅可以实现远程的数据传输、状态监控和现场资源配置等工作，而且还能异地共享和交流各种生产信息资源。2绪

论工程软件的基本元素工程软件的三个基本要素是数据、数据结构和算法。

工程数据是工程软件系统的处理对象。

数据结构是对工程数据的组织。组织结构良好的数据不仅可以提高工程数据处理的效率，而且数据的可靠性也能得到有效的保障。

算法提供处理数据的手段和方法，是提取数据内涵的一系列行为的总称。3绪论著名计算机科学家Wirth(沃思)提出:

数据结构+算法＝程序然而,仅有这些还不够,应是:

数据结构＋算法＋程序设计方法＋语言工具和环境＝程序程序设计算法设计数据结构行为特性的设计结构特性的设计算法的效率通常与数据的存储结构有直接关系4第1章算法1.1算法的基本概念1.2算法设计基本方法1.3算法的复杂度分析51.1算法的基本概念概念

算法是为解决一个问题采取的方法和步骤。也就是说，算法是为实现某种计算过程而规定的基本动作的执行序列。算法的实现–自动机器解--指令的有限序列。自动机的能力：对于执行体系来说是一种制约描述形式的理解能力实现描述的执行能力算法的有限自动机解--在有限的存储空间和有限的时间内通过有限的步骤得到预期的结果。61.1.1算法的基本特征1.能行性(effectiveness):

每一操作都可以通过可实现的基本运算执行有限次来实现步骤合理性步骤可操作性达到预期目的与具体实现方式和环境有关。2.确定性(definiteness):在所指定的范畴内无模糊性在所指定的范畴内无多义性。检验：相同输入相同输出。7算法的基本特征（续）3.有穷性(finiteness)步骤有穷性时间有限性4.完备性(self-contained)初始条件应明确限定范围内条件应齐备结果可展现对异常情况的容错性8算法的定义

一组严谨定义运算顺序的规则，并且每一个规则都是有效且明确的，此顺序将在有限的次数下终止并获得预期的结果。91.1.2算法的基本要素对数据对象的运算和操作针对算法涉及的数据信息最基本的动作和步骤单元算法的控制结构针对算法的过程步骤控制基本操作和步骤的组合顺序10算法要素描述系统的组成1.运算和操作的描述标识符运算符:算术运算符：+，-，*，/等关系运算符：>，<，==，!=，＞=。＜=逻辑运算符：&&(逻辑与)，！(逻辑非)，||(逻辑或)

位运算符：&，|，~，…数据传输：赋值，输入，输出等。11算法描述方式算法描述方式：框图描述法：用流程图的方式来描述、输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。非形式描述法：用自然语言，同时还使用一些程序设计语言中的语句来描述算法。类高级算法语言描述法：常采用类C或C++的所谓伪语言，具有容易编写、阅读和格式统一的特点。高级算法语言描述法：这是可以在计算机上运行并获得结果的算法描述，使给定的问题能在有限的时间内被计算机执行。12算法描述方式（续）以求两个整数m、n（m≥n）的最大公因子为例来说明不同算法描述方法。非形式算法描述该问题的非形式算法描述为：①[求余数]以n除m，并令r为余数(0≤r＜n)；②[余数是否为0]若r=0则结束算法，n就是最大公因子；③[替换并返回a]若r≠0则m←n，n←r返回a。框图法C语言描述intmax_common_factor(intm,intn){intr;r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}13算法要素描述系统的组成2.控制结构—控制基本运算的执行顺序赋值选择--条件转移(多分枝选择)循环语句以上三种动作语句的组合可以完成任何复杂的过程序列14赋值语句赋值语句的形式为

a=e;，其中a为变量名或数组元素，e为算术表达式或逻辑表达式。如果a和b都为变量名或数组元素，则可用记号a≒b，表示将a与b的内容进行交换。(或c=a;a=b;b=c;)15控制转移语句

无条件转移语句用如下形式：

goto标号条件转移语句有以下两种形式：

IF(C){S}

或

IF(C){S1}ELSE{S2}16循环语句WHILE语句的形式为：

while(){};do{}while();FOR语句的形式为:for(i=1;i<=end;i++){};17其他辅助语句：

break;终止整个循环continue；退出本次循环

return()语句用于结束算法的执行

READ（或INPUT）语句用于输入OUTPUT（或PRINT，或WRITE）语句用于输出。

181.2计算机算法设计的基本方法1.列举法(枚举法)首先依据问题的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到全部情况验证完。若某个情况使验证符合问题的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解确定枚举的集合(范围）确定枚举的条件和验证方法（起止，顺序，相关性，过程）优化枚举的条件和范围。优点：简单。弱点：低效19列举法实例求不定方程的百鸡问题：设x

，y，z分别为母鸡、公鸡和小鸡的只数。母鸡每只三元、公鸡每只二元、小鸡两只一元。问百元买百鸡有几种解法？写代数方程：

x+y+z=1003x+2y+z/2=10020用列举法写算法就十分方便：voidBuyChicks(){intx,y,z;for(x=0,x<=100,x++)for(y=0,y<=100,y++) for(z=0,z<=100,z++){ m=x+y+z; n=3*x+2*y+0.5*z;if((m==100)&(n==100))cout<<x,y,z;};}如何优化?21优化后的程序：voidBuyChicks(){intx,y,z;for(x=0;x<=33;x++) //最多可以买33只母鸡

for(y=0;y<=50-1.5*x;y++) //最多可买50只公鸡

{ z=100-x-y; if((3*x+2*y+0.5*z)==100)cout<<x,y,z;};}222.归纳法列举少量特殊情况，从而找出一般规律。适用于存在某种假设规律并可验证的模型必须验证：数学归纳法3.递推法求解过程中的中间结果存在有规律的顺序依赖关系.直至最后结果。稳定性问题。234.递归--算法的自包含性自己调用自己的算法过程。将问题按规律逐层分解，直至含有解的最简形式。按逆过程综合出终解。直接递归P(P(P(……)))间接递归P(Q(P(……)))定义的递归-->过程的递归需要机器能力的支持效率问题24递归设计方法把阶数较高的一个过程，转化为阶数较低同类型的过程。采用递归编写程序能使程序变得非常简单而清晰。递归的主要思想包括三个方面：a)定义形式是递归的。b)数据之间的关系（即数据结构）按递归定义。c)问题本身没有明显的递归结构，但用递归求解比用迭代求解更简单。25递归设计举例对于输入的参数n，依次打印出自然数1至n。非递归解：#include<iostream>Usingnamespacestd;voidwrite(intn){intk;for(k=1;k<=n;k++)cout<<k<<endl;return;}递归解：#include<iostream>Usingnamespacestd;voidwrite1(intn){if(n!=0) //边界条件，递归入口{write1(n-1)；//递归前进段cout<<n<<endl;}return; //递归返回段

}26递归设计方法一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件满足时，递归前进；当边界条件不满足时，递归返回。考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。递归的能力在于用有限的语句来定义对象的未知集合。27Hanoi塔问题XYZXYZXYZ123原始问题：Hanoi(n,X,Y,Z)Hanoi(n-1,Y,X,Z)Hanoi(n-1,X,Z,Y)nmove(X,n,Z)有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。28算法描述：Hanoi(n,X,Y,Z)ifn=1thenmove(X,1,Z)elseHanoi(n-1,X,Z,Y)move(X,n,Z)Hanoi(n-1,Y,X,Z)endifreturn前进段?返回段?边界条件?29递推与递归的区别递推：基于数据的递归：基于方法的一个递推算法总可以转换为一个递归算法。递归算法往往比非递归算法要付出更多的计算机资源。306.回溯法试探法无法总结出求解规律。无法列举可能的条件和解集。逐步试探局部成功，则继续试探。若失败，沿原路退回若干步，改变条件和方向再试，直至找到解。八后问题31皇后问题N皇后问题自然语言描述：在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。

n皇后问题的解是指：

找到这n个皇后的互不攻击的布局思考：1）如何表示棋盘、棋子和布棋？2）如何描述布棋规则？3）如何设计布棋步骤？♛♛♛♛♛32基本思路

依次为每一行确定该行皇后的合法位置安放第i行皇后时，需要在列的方向从0到n-1试探(j=0,…,n-1)在第j列安放一个皇后如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第j列安放的皇后：如果没有出现攻击，在第j列安放的皇后不动

递归安放第i+1行皇后如果第i行不能安放皇后，则回溯到第i-1行，撤销该行的皇后，并从其所在的下一个列(j+1)继续试探。程序实现的要素？33皇后问题对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。34思考题解的唯一性?123n12in♛♛♛♛♛解的完备性--全部解集?无解的证明?END35361.3算法的复杂度分析算法的评价算法的复杂度算法的最优性快速算法的设计制约算法效率的要素时间空间37算法评价标准算法评价标准正确性程序不含语法错误对于几组输入数据能够得出满足要求的结果对于精心挑选的典型、苛刻的几组输入数据能够得出满足要求的结果----一般作为衡量标准对于一切合法的输入数据都能产生满足规格说明要求的结果---------很难满足(无法枚举)可读性:

容易阅读理解，模块化，可以牺牲效率健壮性：异常处理机制高效率与低存储量需求381.3.1算法的时间复杂度1.时间复杂度--一个算法运行时间的相对度量。一个程序的时间复杂度是指程序从开始到结束运行所需要的时间。算法执行时间:算法执行时间=原操作的执行次数之和*原操作的执行时间算法执行所需考虑因素:与非关键性细节无关与执行算法的机器速度无关与辅助环境无关时间复杂度度量方法:算法基本操作重复执行的次数是模块n的某一个函数f(n)。

工作量=f(n)

n：问题的规模时间复杂度表示方法：T(n)=O(f(n))39随着模块n的增大，算法执行时间的增长率和f(n)增长率成正比。在计算时间复杂度时，先找出算法的基本操作，然后根据对应的各语句确定它的执行次数，再找出T(n)的同数量级（它的同数量级有以下：1，log(2)n，n，nlog(2)n，n的平方，n的三次方，2的n次方，n!），找出后，令f(n)=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n)=O(f(n))时间复杂度分析40乘法运算是基本操作，因为：①核心操作，处于最深层循环；②花费时间（相对于加法）。例n阶矩阵相乘的算法for(i=1;i<=n;++i)

for(j=1;j<=n;++j){

c[i][j]=0;

for(k=1;k<=n;++k)

c[i][j]+=a[i][k]*b[k][j]}乘法、加法执行次数均为n3

时间复杂度分析举例41按数量级递增排列，常见的时间复杂度有：

常量阶：O(1)

对数阶：O(logn)

线性阶：O(n)

线性对数阶：

O(nlogn)

平方阶：O(n2)

立方阶：O(n3)

K次方阶：O(nk)

指数阶：O(2n)

T(n)=O(f(n))时间复杂度的表示基本操作执行次数为n3，与整个运行时间成正比因此以n的函数作为效率衡量标准。记作：

T(n)=O(n3)

一般而言，基本操作重复执行的次数是问题规模n的函数T(n)，当n趋于无穷大时，T(n)的数量级（价）称为算法的渐近时间复杂度，记作：42算法的最优性最优性定义:执行的基本运算相对最少。寻优过程设计算法A，确定响应的上界W(n)[最坏]改进算法,确定响应的下界F(n)[至少]若W(n)=F(n),则已获得最优算法,否则继续改进.即F(n)同时具备必要性和充分性,则算法为最优.快速算法时间复杂度最小431.3.2算法的空间复杂度空间复杂度：是指程序运行从开始到结束所需的存储空间。执行算法所需要的存储空间包括：算法程序所占空间输入数据所占空间执行过程所需的额外空间通常以算法的空间复杂度作为算法所需存储空间的量度。空间复杂度的表示：

S(n)=O(g(n))

空间复杂度也是问题规模n的函数。表示随问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。44算法分析举例求和的例子，intn=100;intsum=0;for(inti=1;i<=n;i++){ sum=sum+i;}时间复杂度T(n)=O(n)空间复杂度S(n)=O(1)使用函数迭代intsum(intn){ if(n==1)returnn; returnn+sum(n-1);}main(){ intn=100; intS=sum(n);}时间复杂度T(n)=O(n)空间复杂度S(n)=O(n)END45第2章基本数据结构2.1数据结构的基本概念1.什么是数据结构2.数据结构的表示46数据、数据元素、数据项和数据结构1.基本术语数据(data)--反映客观事物的信息的集合，是信息的载体，它能够被计算机识别、存储和加工处理。例如数、字符。数据元素(dataelement)--集合中的个体，数据的基本单位，例如数据集合中的某个特定的数值。一个数据元素可以由多个数据项组成（字段、域、属性）数据项—是具有独立含义的最小数据单位。数据＞数据元素＞数据项（班级通讯录＞个人记录＞姓名，年龄，联系地址）数据对象(dataobject)相同特性的数据元素的集合--数据的子集。例如，整数的数据对象是N＝{0，士1，士2，…}2.1数据结构的基本概念47数据、数据元素、数据项和数据结构数据结构(datastructure)—互相关联的数据元素的集合，例如，向量和矩阵，图书卡片。

数据元素的集合，记为D；在D上的一个关系，记为R。

数据结构＝（D，R）48数据类型定义：数据类型是指为一种数据结构和能够对该数据结构进行的操作的集合

例如:整型（int）

、浮点型（float，double）、字符型（char）、指针型、空类型（void）。intj;-32768~+32767unsignedintj;

0~+65535longintj;-232~

+232-1unsignedlongintj;49C语言的数据类型

┌基本型(int)┌整型│短整型(shortint)││长整型(longint)│└无符号型(unsignedint)│┌基本类型│实型(浮点型)┌单精度(float)││

└双精度(double)数据类型││字符型(char)│└枚举型(enum)││┌数组类型(inta[])│构造类型│结构体类型(struct)│└共用体类型(union)│指针类型(int*pa)└空类型50数据举例：身份证数据的管理在身份证管理应用层次的视图数据元素：每个身份证信息是一个数据元素，包括姓名、性别、身份证号和相片等数据项数据项：姓名、性别、身份证号和相片都是数据项数据结构：身份证信息之间的关系：逻辑结构：（线性）表结构物理结构：数组操作：增加、删除、查找数据结构的嵌套：例如：相片是一个图象数据，具有图象数据结构，它可以作为一个数据项嵌套在每个人的数据项中。51数据结构与算法一个算法的效率往往与数据的表示形式有着直接的关系。数据结构的选择，对程序质量的影响极大。学习数据结构的目的也就是为了更好地进行程序设计。521.3.2

数据结构的表示

例11设数据元素的集合为D＝｛di|1＜i＜7的整数}，画出对应于下列关系所构成的数据结构的图形：R1＝{(d1，d3)，（d1，d7），（d4，d5），（d3，d6），（d2，d4）}R2＝{(di，dj)|i十j＝5}R3＝｛（d2，d3），（d3，d1），（d1，d4），（d4，d6），（d6，d5），（d5，d7）｝三个数据结构的图形如下图所示。53R1＝{(d1，d3)，（d1，d7），（d4，d5），（d3，d6），（d2，d4）}R2＝{(di，dj)|i十j＝5}R3＝｛（d2，d3），（d3，d1），（d1，d4），（d4，d6），（d6，d5），（d5，d7）｝54在数据结构的图形表示中，没有前件的结点称为根结点，如图（a）中的结点d1、d2，图（b）中的结点d5、d6、d7，图（C）中的结点d2；没有后件的结点称为终结点，如图（a）中的d5、d6、d7，图（b）中的d5、d6、d7，图（c）中的d7。除了根结点与终结点以外，其余结点均称为内部结点。图中数据结构的图形表示说明55数据结构四个基本的数据结构集合结构：关系集合是空集

顶点元素间无任何关系，R={}空集56线性结构和非线性结构线性结构：元素间的关系是1对1

1)有且只有一个初始节点2)最多有一个前区驱,最多有一个后继(也可以无)3)插入或删除一个节点后仍满足1),2)非线性结构:元素间的关系是1对多不满足线性结构特点的通称为非线性结构树型结构：一般树、二叉树、森林

一个结点可以有多个直接后继（除叶子结点外），

但只有一个直接前驱（除根结点外）57图状结构图状结构：元素间的关系是多对多

一个结点可以有多个直接后继，也可以有多个直接前驱581.数据的逻辑结构数据结构的表示包括两个方面：一是逻辑结构的表示：二是存储结构的表示：数据的逻辑结构：数据元素之间的逻辑关系特征从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型与数据元素本身的形式、内容无关分类线性结构：线性表非线性结构：树、图59逻辑结构举例以班级数据为例，数据元素是学生，学生有学号、姓名和性别等数据项。学生同属于一个班级的关系构成集合结构按学号排列的学生关系构成线性结构如果学生分组管理，班长-组长-普通学生，那么学生的上下级关系则构成层次结构学生之间的朋友关系构成一个网状结构60例1、学生基本情况登记表。学号姓名 专业政治面藐

001 王洪 计算机党员002孙文计算机团员003 谢军 计算机团员004 李辉 计算机团员005 沈祥福计算机党员006 余斌 计算机团员007 巩力计算机团员008 孔令辉计算机团员

00100300200400600500007学号关系是一种线性结构关系逻辑结构举例612.数据的存储结构数据存储结构——数据元素极其关系在计算机存储器内的表示数据结构在计算机中的表示—为数据元素分配存储单元将数据元素间的逻辑关系映射到存储位置关系上依赖于程序设计语言所提供的数据类型和存储形式1.顺序存储结构等长；等间隔逻辑上相邻-->物理上相邻,关系自然确定易于描述线性结构，也可存储经过线性化处理的非线性结构主要数据类型:向量（表格存储结构）,数组高级计算机语言以数据类型的方式提供了一个基本数据结构集的存储和操作。影响选择的因素：数据的访问效率和存储空间占用的权衡。6263顺序结构数据的存取64顺序存储结构分析线性结构B＝（D，R）

D＝{a，b，c，d，e，f}R＝{(b，c),(c，d),(d，a),(a，f),（f，e）}顺序存储的示意图（假设每一个数据元素占一个存储单元），数据元素的存储空间是连续的。1005b1006c1007d1008a1009f1010e65

2.链式存储结构每个节点由两部分组成:数据域,位置指示域(指针域)即可实现线性结构,又可表示非线性结构特点:可以表示任意复杂的结构存储空间不连续存储顺序与结构顺序不一致不能随机访问访问效率不均等主要形式:

单链表、双链表、多重链表、循环链表data

单元节点P66链式存储示例每个结点设一指针，用以指出其后件的存储序号。最后一个结点的指针为空，用“0”表示。第一个结点专门用一个指针（称为头指针，用HEAD表示）指向它。线性结构B＝（D，R）

D＝{a，b，c，d，e，f}R＝{(b，c),(c，d),(d，a),(a，f),（f，e）}data

单元节点P67数据的逻辑结构与存储结构的关系1.数据的逻辑结构必定要有某种存储