《软件技术基础》全册配套精品完整课件.ppt

1、软件技术基础全册配套精品完整课件教材习题参考第 0 章 绪论（有 * 号的标题表示最基本的内容） 0.1 课程的目的与任务课程的目的与任务0.2 课程基本要求课程基本要求0.3 学习软件的重要作用学习软件的重要作用0.4 软件课程学习方法软件课程学习方法0.5 考核方法考核方法0.1 课程的目的和任务v软件基础软件基础是是电类专业电类专业的一门专业基础课的一门专业基础课。v涉及涉及算法算法、计算机操作系统计算机操作系统、数据结构数据结构、数数据库技术和软件工程五门据库技术和软件工程五门课程的经典内容课程的经典内容。v通过该课程的学习，使学生掌握应用通过该课程的学习，使学生掌握应用软件开软件开发

2、所必需的基础知识发所必需的基础知识，为今后结合本专业开，为今后结合本专业开发应用软件打下必要的基础。发应用软件打下必要的基础。0.2 课程基本要求v了解了解常用的数据结构及相应算法，初步掌握常用的数据结构及相应算法，初步掌握对对不同类型的问题求解选择适当的数据结构。不同类型的问题求解选择适当的数据结构。v掌握掌握操作系统的操作系统的基本概念和基本功能基本概念和基本功能，了解计，了解计算机系统硬、软件资源算机系统硬、软件资源如何控制管理如何控制管理。v了解了解如何以如何以近代软件工程近代软件工程的观点开发应用软件的观点开发应用软件的基本概念和方法。的基本概念和方法。v了解了解数据库的基本概念，初

3、步掌握数据库的基本概念，初步掌握数据库系统数据库系统的开发方法的开发方法。0.3 学习软件的重要作用社会对社会对“软件软件”的需求激增。的需求激增。美国国家将软件列为六大美国国家将软件列为六大关键技术关键技术之一；之一；欧盟将欧盟将“软件和信息处理软件和信息处理”列为关列为关键技术；键技术；我国把信息产业放在优先发展的地位，看作是我国把信息产业放在优先发展的地位，看作是中国发展高新技术、赶超世界先进水平的一次中国发展高新技术、赶超世界先进水平的一次千载难逢的机遇千载难逢的机遇。0.4 课程内容 软件技术基础是一门从事软件技术基础是一门从事计算机软件开发计算机软件开发及应用程序设计的必不可少的基

4、础课。及应用程序设计的必不可少的基础课。q 算法算法q 数据结构数据结构（重点内容）（重点内容）q软件工程软件工程q操作系统操作系统q数据库系统数据库系统0.4.1 数据结构 从以下三个方面入手从以下三个方面入手 学习学习逻辑逻辑结构结构+存储存储结构结构 学习基于这种数据结构的基本操作学习基于这种数据结构的基本操作 这种数据结构的应用这种数据结构的应用0.4.2 操作系统学习方法学习操作系统从这几个方面入手学习操作系统从这几个方面入手 如何能够提高如何能够提高系统资源系统资源的的利用率利用率 更更有效有效地地组织、协调、管理组织、协调、管理计算机内部计算机内部的工作流程的工作流程 为用户为用

5、户提供更友好、便捷提供更友好、便捷的操作界面的操作界面0.4.3 数据库系统学习方法学习数据库系统从这几个方面入手学习数据库系统从这几个方面入手（1）如何设计数据表（数据依赖、规范化）如何设计数据表（数据依赖、规范化）（2）如何查找（投影、联结、并、交、补等关）如何查找（投影、联结、并、交、补等关系运算）系运算）（3）这些操作如何用数学的方法运算）这些操作如何用数学的方法运算0.4.4 软件工程学习学习学习软件工程软件工程从这几个方面入手从这几个方面入手（1）软件工程是如何解决软件开发中的）软件工程是如何解决软件开发中的管理和技术问题。管理和技术问题。（2）软件生命周期，包括阶段划分、文）软件

6、生命周期，包括阶段划分、文档、评审等概念。档、评审等概念。（3）掌握几种软件工程新方法如：原形）掌握几种软件工程新方法如：原形法、结构化、面向对象。法、结构化、面向对象。0.5考核方法（1）平时考勤）平时考勤+5次作业（次作业（20%）（2） 期末考试（期末考试（80%）。）。第一章 算法1.1 算法的基本概念算法的基本概念 1.1.1 算法的基本特征算法的基本特征 1.1.2 算法的要素算法的要素1.2 算法描述语言算法描述语言1.3 算法设计基本方法算法设计基本方法1.4 算法复杂度分析算法复杂度分析 1.4.1 时间复杂度时间复杂度 1.4.2 空间复杂度空间复杂度 教学目标教学目标 了

7、解算法的了解算法的基本概念、算法描述语言基本概念、算法描述语言 ， 掌掌握几种常见算法的基本实现，并能分析算法的握几种常见算法的基本实现，并能分析算法的时间和空间复杂度时间和空间复杂度。 学习要点学习要点 掌握算法的掌握算法的基本概念和基本特征基本概念和基本特征 理解常用的几种算法的思想例如：理解常用的几种算法的思想例如：列举法，列举法， 递推法，递归法和减半递推递推法，递归法和减半递推。 算法复杂度算法复杂度的概念和意义（时间复杂度与空的概念和意义（时间复杂度与空间复杂度）。间复杂度）。引出算法 行为特性的设计行为特性的设计- 将解决实际问题的每个细将解决实际问题的每个细节准确地加以定义，并

8、且还应当将全部解题节准确地加以定义，并且还应当将全部解题过程完整地描述出来。这就是过程完整地描述出来。这就是算法算法的设计。的设计。 结构特性的设计结构特性的设计- 确定合适的确定合适的数据结构数据结构。 1.1 算法基本概念算法（算法（Algorithm） 是对特定问题求解步骤的一种描述；是对特定问题求解步骤的一种描述； 是一组指令的有限集合。是一组指令的有限集合。算法的基本特征算法的基本特征 能行性能行性：算法中描述的操作都是可通过已经实现的：算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的；基本运算、执行有限次实现的； 确定性确定性：算法中的每一条指令必须有明确的含义，：算

9、法中的每一条指令必须有明确的含义，不能有二义性；不能有二义性； 有穷性有穷性：一个算法必须总是在执行有穷步后结束，：一个算法必须总是在执行有穷步后结束，且每一步都可在合理的执行时间内完成；且每一步都可在合理的执行时间内完成； 拥有足够情报拥有足够情报：一个算法应有：一个算法应有0个或多个输入；个或多个输入；结论： 所谓算法，是一组严谨地定义运算顺序的所谓算法，是一组严谨地定义运算顺序的规则规则，并且每一个规则都是有效的、明确，并且每一个规则都是有效的、明确的，此顺序将在的，此顺序将在有限的次数下终止。有限的次数下终止。 1.1.2 算法的基本要素算法中对数据的运算和操作算法中对数据的运算和操作

10、 （1）算术运算：）算术运算：主要包括加、减、乘、除等运算。主要包括加、减、乘、除等运算。（2）逻辑运算：）逻辑运算：主要包括主要包括“与与”、“或或”、“非非”等运算。等运算。（3）关系运算：）关系运算：主要包括主要包括“大于大于”、“小于小于”、“等于等于”、“不等不等于于”等运算。等运算。（4）数据传输：）数据传输：主要包括赋值、输入、输出等操作主要包括赋值、输入、输出等操作。 算法的控制结构算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，算法的控制结构给出了算法的基本框架，算法一般都可以用顺序

11、、选择、循环三种基本控制结构算法一般都可以用顺序、选择、循环三种基本控制结构组合而成组合而成 1.2 算法的描述 算法的描述方式（常用的）：算法的描述方式（常用的）：算法描述算法描述自然语言自然语言 流程图流程图 特定的表示算法的图形符号特定的表示算法的图形符号伪语言伪语言 包括程序设计语言的三大基本包括程序设计语言的三大基本 结构及自然语言的一种语言结构及自然语言的一种语言 类语言类语言 类似高级语言的语言，类似高级语言的语言， 例如，类例如，类PASCAL，类，类c语言语言本课程采用的算法描述语言1. 符号与表达式符号与表达式 2. 赋值语句赋值语句 3. 控制转移语句控制转移语句4. 循

12、环语句循环语句 5. 其他语句其他语句 1.符号与表达式符号符号 是以字母开头的字母和数字的有限串，主要用以表示变量是以字母开头的字母和数字的有限串，主要用以表示变量名、数组名等，必要时也用来表示语句标号。名、数组名等，必要时也用来表示语句标号。 在语句标号后应跟随一个冒号，然后是语句。在语句标号后应跟随一个冒号，然后是语句。 例如例如 loop：ii1 算法中一般对变量或数组的数据类型不作说明算法中一般对变量或数组的数据类型不作说明 算术运算符沿用数学中的表示法算术运算符沿用数学中的表示法 （1）关系运算符用：）关系运算符用：=、等表示。等表示。 （2）逻辑运算符用）逻辑运算符用and(与与

13、)、or(或或)、not（非）等表示。（非）等表示。 2.赋值语句 普通赋值普通赋值 例如：例如：a=e 内容交换内容交换 例如：例如：a b 多个变量同时赋值多个变量同时赋值 例如：例如：a=b=e表示将表达式表示将表达式e的计算结果同时赋给的计算结果同时赋给a与与b。 3.控制转移语句 无条件转移语句无条件转移语句 GOTO 标号标号 条件转移语句有以下两种形式条件转移语句有以下两种形式 IF C THEN S或或 IF C THEN S1 ELSE S2 C是一个逻辑表达式，是一个逻辑表达式，S、S1和和S2是单一的语句或是单一的语句或者是用一对括号者是用一对括号括起来的语句组。括起来的

14、语句组。4.循环语句 WHILE语句的形式为语句的形式为 形式：形式：WHILE C DO S FOR语句的形式为语句的形式为 FOR iinit TO limit BY step DO S5.其他语句 EXIT语句主要用于退出某个循环。语句主要用于退出某个循环。 RETURN语句用于结束算法的执行。语句用于结束算法的执行。 READ（或（或INPUT）和）和WRITE（或（或PRINT，或，或OUTPUT）语句分别用于输）语句分别用于输入和输出。入和输出。1.3 算法设计基本方法 列举法列举法 归纳法归纳法 递推递推 递归递归 减半递推技术减半递推技术 回溯法回溯法 1.列举法 基本思想基本

15、思想 根据提出的问题，列举所有可能的情况，并用问根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需题中给定的条件检验哪些是需要的，哪些是不需要的。因此，要的。因此，列举法常用于解决列举法常用于解决“是否存在是否存在”或或“有多少种可能有多少种可能”等类型的问题，等类型的问题，例如求解不定例如求解不定方程的问题。方程的问题。 例题：例题：设每只母鸡值设每只母鸡值3元，每只公鸡值元，每只公鸡值2元，每只元，每只小鸡值小鸡值0.5元。现要用元。现要用100元钱买元钱买100只鸡，设计买只鸡，设计买鸡方案，这就是经典的求解百鸡问题。鸡方案，这就是经典的求解百鸡问题。P

16、ROCEDURE BAIJIFOR I=0 TO 100 DOFOR J=0 TO 100 DOFOR K=0 TO 100 DO MI+J+K N3I十十2J+0.5K IF（M100）and（N100）THEN OUTPUT I，J，K RETURN总循环次数为总循环次数为10131030301 首先，考虑到母鸡为首先，考虑到母鸡为3元一只，因此，母鸡最多只能买元一只，因此，母鸡最多只能买33以，以，即算法中的外循环没有必要从即算法中的外循环没有必要从0到到100而只需要从而只需要从0到到33就就可以了。可以了。 其次，考虑到公鸡为其次，考虑到公鸡为2元一只，因此，公鸡最多只能头元一只，因

17、此，公鸡最多只能头50只。只。又考虑到对公鸡的列举是在算法的第二层循环中，此时已经又考虑到对公鸡的列举是在算法的第二层循环中，此时已经买了买了I只母鸡，且买一只母鸡的价钱相当于买只母鸡，且买一只母鸡的价钱相当于买1.5只公鸡。因只公鸡。因此，由第一层循环已经确定买此，由第一层循环已经确定买I只母鸡的前提下，公鸡最多只只母鸡的前提下，公鸡最多只能买能买50-1.5I只，即第二层对只，即第二层对J的循环只需从的循环只需从0到到50-1.5I就可以就可以了。了。 最后，考虑到买的总鸡数为最后，考虑到买的总鸡数为100，而由第一层循环已确定买，而由第一层循环已确定买I只母鸡，由第二层循环已确定买只母鸡

18、，由第二层循环已确定买J只公鸡，因此，买小鸡的只公鸡，因此，买小鸡的数量只能是数量只能是K=100-I-J，即第三层循环已经没有必要了。，即第三层循环已经没有必要了。改进后的算法算法描述语言算法描述语言PROCEDURE BAIJIFOR I0 TO 33 DOFOR J=0 TO 50-1.5I DO K=100-I-J IF（3I+2J+0.5K=100）THENOUTPUT I，J，K RETURN总循环次数为总循环次数为C语言算法：语言算法：#include “stdio.h”main（）（）int i,j,k;for (i=0;i=33;i+)for (j=0;j=50-1.5*i;

19、j+) k=100-i-j; if (3*i+2*j+0.5*k=100.0) printf（”%5d %5d %5dn”,i,j,k）;列举法-改进后的算法（C语言）2.归纳法 归纳法的基本思想归纳法的基本思想 通过列举少量的特殊情况，经过分析，最后找出一般的通过列举少量的特殊情况，经过分析，最后找出一般的关系关系。 归纳是一种抽象归纳是一种抽象 即从特殊现象中找出一般关系。但由于在归纳的过程中即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到不可能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的的结论还

20、只是一种猜测，还需要对这种猜测加以必要的证明证明。3.递推法 基本思想基本思想 从已知的初始条件出发，逐次推出所要求的各从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对本身已经给定，或是通过对问题的分析与化简问题的分析与化简而得到确定而得到确定。 例题例题1020, 2 , 1 , 0,5ndxxxInn递推法例题分析发现相邻两个积分之间存在以下关系发现相邻两个积分之间存在以下关系:nIInn151151nnInI 只要知道只要知道In-1 就可以算出就可以算出In ，也就是说，只要知，也就是说，只

21、要知道了道了I0，就可以通过这个递推公式计算出所有的，就可以通过这个递推公式计算出所有的积分值积分值In（n=1，2，20）。）。 这个关系就可以得到如下递推公式这个关系就可以得到如下递推公式 递推法例题分析100182322. 0)5/6ln(5ln6ln51dxxI20,2,1,51182322.010nInIInn 相邻两个积分之间除了具有递推关系式相邻两个积分之间除了具有递推关系式: nIInn15110nnII以外，还满足下列不等式以外，还满足下列不等式因而，因而，I20 应比应比I0小。且所有的积分值都不可能为负。因小。且所有的积分值都不可能为负。因此，由递推算法此，由递推算法(1

22、.3)得到的结果（表得到的结果（表1.1）是不可靠的。）是不可靠的。 递推法例题分析-改进方法根据递推关系式可以根据递推关系式可以改进改进成另一个递推公式：成另一个递推公式： nnInI515111 ,29,30,51511130nInIInn递推关系如下：递推关系如下：递推法总结:例题分析-改进前后 在老递推算法中，初值是近似的，即在老递推算法中，初值是近似的，即实际上存在一个误差；实际上存在一个误差；老递推算法递推过程中，当计算到老递推算法递推过程中，当计算到I20时，其误差是初值误时，其误差是初值误差的差的 520倍。倍。 在新递推算法中，虽然初值在新递推算法中，虽然初值 I30是近似的

23、，而且误差可能很是近似的，而且误差可能很大。但在用新递推算法递推过程中，每递推计算一次，大。但在用新递推算法递推过程中，每递推计算一次，后后一个计算值的误差是前一个计算值误差的一个计算值的误差是前一个计算值误差的1/5，因此，当计，因此，当计算到算到I20时，其误差是初值时，其误差是初值I30误差的误差的1/510 。4.递归法基本思想基本思想（1）为了降低问题的复杂程度，总是将问题）为了降低问题的复杂程度，总是将问题逐层逐层分解分解，最后归结为一些最简单的问题。，最后归结为一些最简单的问题。（2）这种将问题逐层分解的过程，实际上）这种将问题逐层分解的过程，实际上并没有并没有对问题进行求解对问

24、题进行求解，而只是当解决了最后那些，而只是当解决了最后那些最简单的问题后，再沿着原来分解的最简单的问题后，再沿着原来分解的逆过程逆过程逐步进行综合逐步进行综合，这就是，这就是递归的基本思想。递归的基本思想。（3）因此，递归的基础也是归纳。）因此，递归的基础也是归纳。递归法举例说明例：例：编写一个过程，对于输入的参数编写一个过程，对于输入的参数n，依次打印输，依次打印输 出自然数出自然数1到到n。非递归算法。非递归算法。PROCEDURE WRT(n)FOR k=1 TO n DO OUTPUT kRETURN 递归算法。递归算法。PROCEDURE WRT1（n）IF（n0）THENWRT1（

25、n-1） OUTPUT nRETURN 总结：n 递归是构造计算机算法的一种基本方法。如果一个过程直接或间接地调递归是构造计算机算法的一种基本方法。如果一个过程直接或间接地调用它自身，则称该过程是递归的，递归过程必须有一个递归终止条件，用它自身，则称该过程是递归的，递归过程必须有一个递归终止条件，即存在即存在“递归出口递归出口”。无条件的递归是毫无意义的。无条件的递归是毫无意义的。 n 递归分为直接递归与间接递归两种。如果一个算法递归分为直接递归与间接递归两种。如果一个算法P显式地调用自己则显式地调用自己则称为直接递归，例如算法称为直接递归，例如算法1.4是一个直接递归的算法。如果算法是一个直

26、接递归的算法。如果算法P调用另调用另一个算法一个算法Q，而算法，而算法Q又调用算法又调用算法P，则称为间接递归调用。，则称为间接递归调用。n 递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。直到最简单的问题为止。n 递归与递推是既有区别又有联系的两个概念。递推是从已知的初始条件递归与递推是既有区别又有联系的两个概念。递推是从已知的初始条件出发，逐次递推出最后所求的值。递归

27、则是从需求的函数本身出发，逐出发，逐次递推出最后所求的值。递归则是从需求的函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值。一般说来，一个递推算法总可以转换为一个递归算来，得到最终的值。一般说来，一个递推算法总可以转换为一个递归算法。法。 5.减半递推技术 举例说明：举例说明：两个两个n阶矩阵相乘，通常需要作阶矩阵相乘，通常需要作n3次乘法。那次乘法。那么两个二阶矩阵相乘需要作么两个二阶矩阵相乘需要作8次乘法。次乘法。2221121122211211bbbbBaaaaA222212212

28、1221121221212112112111122211211babababababababaccccC其乘积矩阵其乘积矩阵CAB为：为：)()()()()()()(2221221271211112162212115112122422121131122212221122111bbaaxbbaaxbaaxbbaxbbaxbaaxbbaax对于低阶的矩阵相乘问题，如二阶矩阵相乘，减对于低阶的矩阵相乘问题，如二阶矩阵相乘，减少乘法次数是有可能的。令：少乘法次数是有可能的。令： 减半递推技术举例乘积矩阵乘积矩阵C C中的各元素可用以上中的各元素可用以上7 7个量的线性组合个量的线性组合来表示：来表示：

29、上述方法计算两个上述方法计算两个二阶矩阵相乘只需要二阶矩阵相乘只需要7 7次乘法就够次乘法就够了，了，比通常的方法减少了比通常的方法减少了1 1次乘法。以此类推，最后可以归次乘法。以此类推，最后可以归结为计算一阶矩阵相乘的问题，而一阶矩阵相乘只需结为计算一阶矩阵相乘的问题，而一阶矩阵相乘只需要一次乘法。要一次乘法。62312242215312754111xxxxcxxcxxcxxxxc减半递推技术举例根据以上分析，假设根据以上分析，假设 ，且，且 阶矩阵相乘所需阶矩阵相乘所需要的乘法次数为要的乘法次数为M（k），则有），则有kn2kn2)0(7)2(7) 1(7)(2MkMkMkMk减半递推技

30、术例题分析81. 27loglog2277)(nnkMnk因此有因此有减半递推技术总结： 对问题分而治之。工程上常用的分治法是减半对问题分而治之。工程上常用的分治法是减半递推技术。这个技术在快速算法的研究中有很递推技术。这个技术在快速算法的研究中有很重要的实用价值。所谓重要的实用价值。所谓“减半减半”，是指将问题，是指将问题的的规模减半规模减半，而问题的性质不变，所谓，而问题的性质不变，所谓“递递推推”，是指，是指重复重复“减半减半”的过程的过程。例题设方程设方程f(x)=0在区间在区间a,b上有实根，且上有实根，且f(a)与与f(b)异号。利用二分异号。利用二分法求该方程在区间法求该方程在区

31、间a,b上的一个实根。上的一个实根。分析：分析： 首先取给定区间的中点首先取给定区间的中点c=(a+b)/2。 然后判断然后判断f(c)是否为是否为0。若。若f(c)=0，则说明，则说明c即为所求的根，求即为所求的根，求解过程结束；如果解过程结束；如果f(c) 0 ，则根据以下原则将原区间减半：，则根据以下原则将原区间减半： 若若f(a)f(c)0，则取原区间的前半部分；，则取原区间的前半部分； 若若f(b)f(c)0 ，则取原区间的后半部分。，则取原区间的后半部分。 最后判断减半后的区间长度是否已经很小。最后判断减半后的区间长度是否已经很小。 若若|a-b|，则过程结束，取（，则过程结束，取

32、（a+b）/2为根的近似值；否则，为根的近似值；否则，则重复上述的减半过程。则重复上述的减半过程。double root(a，b，eps，f)double a,b ,exp,(*f)() f0f(a) while(|ab|eps) DO c(ab)/2； f1(*f)(c) if (f1=0) return c if (f0*f10) ac else bc; c(ab)/2； return(c)6.回溯法 基本思想基本思想1.在工程上，有些实际问题却在工程上，有些实际问题却很难归纳很难归纳出一组简单出一组简单的递推公式或直观的求解步骤，并且也不能进行的递推公式或直观的求解步骤，并且也不能进行无

33、限的列举。无限的列举。2.一种有效的方法是一种有效的方法是“试试”。通过对问题的分析，。通过对问题的分析，找出一个解决问题的线索；然后沿着这个线索逐找出一个解决问题的线索；然后沿着这个线索逐步试探。步试探。3.对于每一步试探，若试探成功，就得到问题的解；对于每一步试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。探。这种方法称为回溯法。 例：例：n皇后问题（皇后问题（n=4）1.4 算法的复杂度分析算法评价的标准：算法评价的标准：时间复杂度时间复杂度和和空间复杂度空间复杂度。时间复杂度时间复杂度 指在计

34、算机上运行该算法所花费的时间。常以基本运算指在计算机上运行该算法所花费的时间。常以基本运算的重复次数来衡量。用的重复次数来衡量。用“O（数量级）（数量级）”来表示，称为来表示，称为“阶阶”。常见的时间复杂度有：。常见的时间复杂度有： O(1)， O(logn)， O(n)， O(n2 )， O(2n ) 常数阶常数阶 对数阶对数阶 线性阶线性阶 平方阶平方阶 指数阶指数阶空间复杂度空间复杂度 指算法在计算机上运行所占用的存储空间的大小。指算法在计算机上运行所占用的存储空间的大小。 （程序、输入、额外辅助）（程序、输入、额外辅助） 平均性态 所谓平均性态分析，是指用各种特定输入下的基所谓平均性态

35、分析，是指用各种特定输入下的基本运算次数的本运算次数的带权平均值带权平均值来度量算法的工作量。来度量算法的工作量。 设设x是所有可能输入中的某个特定输入，是所有可能输入中的某个特定输入，p(x)是是x出现的概率（即输入为出现的概率（即输入为x的概率），的概率），t(x)是算法在是算法在输入为输入为x时所执行的基本运算次数时所执行的基本运算次数，则算法的平，则算法的平均性态定义为：均性态定义为：nDxxtxpnA)()()(最坏情况复杂性 所谓所谓最坏情况分析最坏情况分析，是指在规模为，是指在规模为n时，算法时，算法所执行的基本运算的最大次数。所执行的基本运算的最大次数。 它定义为：它定义为：

36、)(max)(xtnWnDx例题例：采用顺序搜索法，在长度为例：采用顺序搜索法，在长度为n的一维数组中查的一维数组中查找值为找值为x的元素。即从数组的第一个元素开始，的元素。即从数组的第一个元素开始，逐个与被查值逐个与被查值x进行比较。基本运算为进行比较。基本运算为x与数组与数组元素的比较。元素的比较。 平均性态分析 设被查项设被查项x在数组中的概率为在数组中的概率为q ) 1()1 (ninniiti 如果已知需要查找的如果已知需要查找的x一定在数组中，此时一定在数组中，此时q1，则则A(n)=（nl）2。 如果已知需要查找的如果已知需要查找的x有一半的机会在数组中，有一半的机会在数组中，此

37、时此时q12；则；则A(n)=(n+1)/4+n/23n/4) 1(1)1 (/niqninqpinqqnnqinqtpnAniniii)1 (2/) 1()1 ()/()(111最坏情况分析 在这个例子中，最坏情况发生在需要查找的在这个例子中，最坏情况发生在需要查找的x是数组中的最后一个元素，或是数组中的最后一个元素，或x不在数组中的不在数组中的时候，此时显然有：时候，此时显然有：nnitnWi11 |max)(算法的最优性算法的最优性1.1. 衡量算法的好坏主要依据算法的复杂度，特衡量算法的好坏主要依据算法的复杂度，特别是别是时间复杂度。时间复杂度。通常总是在最坏的情况下通常总是在最坏的情

38、况下分析算法的工作量。分析算法的工作量。2.2. 最优算法是指在解决一个问题时，如果在被最优算法是指在解决一个问题时，如果在被研究的算法类中，没有一个算法比现有算法研究的算法类中，没有一个算法比现有算法执行更少的基本运算，则称此算法是最优的。执行更少的基本运算，则称此算法是最优的。 总结：算法的基本概念算法的基本概念算法的基本特征算法的基本特征算法的要素算法的要素算法描述语言算法描述语言算法设计基本方法算法设计基本方法算法复杂度分析算法复杂度分析第二章 基本数据结构及其运算第 2 章 基本数据结构及其运算（有 * 号的标题表示最基本的内容） 2.1数据结构的基本概念 * 2.1.1 什么是数据

39、结构2.2 线性表 2.2.1 线性表的基本概念 2.2.2 线性顺序表及其运算 2.2.3 线性链表及其运算 2.2.4 栈及其应用 2.2.5 队列及其应用教学内容一、数据结构概述 数据、数据元素、数据结构、逻辑结构、 物理结构、 算法、特征、评价二、顺序表 线性表、顺序表、描述、 创建、插入、删除等算法三、链表 单链表、循环链表、双向链表、双向循环链表 判空、插入、删除、定位等操作 指针域、数据域、头节点、头指针2.1.1 什么是数据结构 数据（Data） 能存于计算机、并被计算机处理的符号的集合。 它是客观事物的符号表示。 数据元素（Element） 是数据的基本单位、数据集合中的个体

40、。 数据结构（Data Structure） 是带有结构特征的数据元素的集合；它有三个要素： DS=数据的逻辑结构+存储结构+数据的运算一.基本概念二. 数据的逻辑结构概念：客观事物本身存在的结构形式及关系。特点：描述数据间的顺序（逻辑）关系，抽象地反映数据元素的结构，而不管它们在计算机中如何存放。 与物理存放位置无关描述方法：用二元组来描述： DS=（D，R）其中： D：是数据元素的有限集合； R：是数据元素之间关系的集合。成员：由1名教师、13名研究生、16名本科生组成； 成员关系是：教师指导研究生、研究生指导12名本科生。 数据结构的形式化描述：定义DS如下： Group=（D，R） 其

41、中： D=T，G1，,Gn,S11,Snm 1 n 3 , 1 m 2 R=R1,R2 R1=|1 i n , 1 n 3 R2=|1 i n ,1 j m , 1 n 3 , 1 m 2 1.数据的逻辑结构-举例 （1）线性结构：一对一次序关系 （2）树形结构：一对多层次关系 （3）图或网状结构：多对多关系 （4）集合：属性相同，元素间没有关系2.数据逻辑结构的类别三、数据的存储结构 是指数据结构在计算机中的表示(又称映象)，即数据在计算机中的存放形式。 逻辑结构在存储器中的映射。又称物理结构数据存储结构分类1. 顺序存储结构2. 链式存储结构3. 索引存储结构 （略）4. 散列存储结构 （

42、略）1. 顺序存储结构概念：把数据元素按某种顺序存放在一块连续的存 储单元中的存储形式。数据结点结构: d1 d2 dn数据域特点: 连续存放;逻辑上相邻,物理上也相邻。 结构简单，易实现。 插入、删除操作不便（需大量移动元素）。2. 链式存储结构概念：以链表形式将数据元素存放于任意存储单元 中，可连续存放，也可以不连续存放，以指 针实现链表间的联系。数据结点结构: d1. d2dn 特点: 非连续存放,借助指针来表示元素间的关系; 插入、删除操作简单，只要修改指针即可； 结构较复杂，需要额外存储空间。数据域 指针域 总结： （1）逻辑结构和物理结构的关系 数据的逻辑结构是从逻辑关系（某种顺序

43、）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。 数据的存储结构是逻辑结构在计算机中的实现，是依 赖于计算机的；离开了机器，则无法进行任何操作。 任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。逻辑结构：独立于计算机。存储结构：依赖于计算机算法设计考虑逻辑结构，算法实现依赖存储结构。总结： （2）数据结构分类线性表堆栈队列串数组树二叉树图线性结构非线性结构数据结构DS2.2 线性表2.2.1 线性表基本概念 线性表是指数据元素之间的关系为一一对应的线性关系的数据结构。 例如，一星期七天的英文缩写表示： （Sun，Mon，Tue

44、，Wed，Thu，Fri，Sat） 是一个线性表，其中的元素是字符串，表的长度为7。 线性表虽然简单，但是应用范围非常广泛。非空线性表的结构特征 有且只有一个根结点a1，它无前件； 有且只有一个终端结点an，它无后件； 除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。一、线性表的逻辑结构定义： 线性表是n（n0）个元素a1,a2,an 的有限序列；表中每个数据元素，除第一个外，有且只有一个前件；除最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为 ),.,.,(21niaaaa例如：一星期七天的英文缩写表示： （Sun，Mon，Tue，Wed，Thu，Fr

45、i，Sat） 是一个线性表，其中的元素是字符串，表的长度为7。二、元素关系描述1）L的长度为n（n 0），当n为0时，表示是空表； 2）每个元素（除了第1个和最后一个元素外），有唯一的前件和后件；3）线性表中各元素间存在着线性关系；4）均匀性；各元素数据类型必须相同；5）有序性；各元素是有序的，不可交换次序。2.2.2 线性顺序表存储结构线性表的顺序存储结构 将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。顺序表 采用顺序存储结构的线性表简称为“顺序表”。顺序表的存储特点： 只要确定了起始位置，表中任一元素的地址都通过下列公式得到： LOC（ai）=LOC（a1）+（i

46、-1）*L 1i n 其中，L是每个元素占用存储单元的长度。一、定义二、线性表元素存储示意图 a1a2.ai.元素序号 内存状态 存储地址2 i1.LOC(a1)LOC(a1)+1L.LOC(a1)+(i-1)L.三、 线性表的基本操作Setnull（L） 置空表Length（L） 求表长度；求表中元素个数Get（L，i） 取表中第i个元素（1i n）Prior（L，i） 取i的前件元素Next（L，i） 取i的后件元素Locate（L，x） 返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x） 删除元素Empty（L） 判别表是否为空template class

47、SqList Type *v; /顺序表存储数组 int mm; /最大允许长度 int nn; /当前线性表的长度public: Sq_LList () mm=0 ;nn=0; Sq_LList ( int); int Prt_sq_list ( Type & x ) ; /前驱 int flag_sq_LList(); void ins_sq_LList(int ,T); void del_sq_LLIst() 1. 插入算法线性表的存放形式：采用一维数组存放。操作要求：将X插入线性表（a1,a2,an）中 的第i个位置算法步骤: step1 将第n至第i个元素后移一个存储位置; step

48、2 将x插入到ai-1之后; step3 表的长度加1。表项的插入25 34 57 16 48 09 63 0 1 2 3 4 5 6 7data50插入 x25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data50i长度为长度为n n的线性表中的第的线性表中的第i i个元素之前插入新元素个元素之前插入新元素b b。PROCEDURE INSL（V，m，n，i，b）IF（n=m）THENOVERFLOW；RETURNIF(in) THEN in1IF（i1)THEN i1FOR j=n TO i BY 1 DO V（j+1）=V（j）V(i)=bnn1RETUR

49、Ntemplate int Sq_LList : Ins_sq_LList (T* v, int*n ;int i; T b ) /在表中第 i 个位置插入新元素 b int k; if( *n = m) cout “overflow”*n) i = *n+1; if(i = i ; k -) vk = vk-1; v i -1 =b; *n=*n +1; return;2. 删除算法线性表的存放形式：采用一维数组存放。操作要求：删除线性表(a1,a2,an)中的第i个元素算法步骤: step1 判别指定的位置是否合法； step2 若合法，则将位置i+1至n上的元素前移一个存储位置; ste

50、p3 表的长度减 1。表项的删除25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data16删除 x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7data在长度为在长度为n的线性表中删除第的线性表中删除第i个元素个元素PROCEDUREINSL（V，m，n，i）IF（n=0）THENUNDERFLOW；RETURNIF(in) THEN “Not this element in the list”;RETURNFOR j=i TO n-1 DO V（j）=V（j+1）nn-1RETURN template void del_sq_LLis