软件技术基础.ppt

1、软件技术基础课程18-1软件技术基础软件技术基础课程18-2绪绪 论论 工程软件概述工程软件概述计算机三大应用领域：科学计算、信息处理、过程控制科学计算、信息处理、过程控制。随着信息技术的普及，各类计算机软硬件系统在工程应用领域的广泛应用。工程软件在实际工程应用中占有相当重要的地位。工程软件主要应用领域包括工程软件主要应用领域包括：工程辅助系统工程辅助系统：工程数值计算（Engineering Computation）、计算机辅助设计CAD、计算机辅助制造CAM、计算机辅助工程教育CAEE、计算机集成制造系统CIMS、计算机辅助测试CAT、工业控制IC、计算机仿真CS等。工程事务处理工程事务处

2、理：分为事务型系统、管理型系统、决策型系统。现代工程通信及信息交流现代工程通信及信息交流：通过支持计算机网络的工程软件不仅可以实现远程的数据传输、状态监控和现场资源配置等工作，而且还能异地共享和交流各种生产信息资源。软件技术基础课程18-3绪绪 论论 工程软件的基本元素工程软件的基本元素工程软件的三个基本要素是数据数据、数据结构数据结构和算法算法。工程数据工程数据是工程软件系统的处理对象。数据结构数据结构是对工程数据的组织。组织结构良好的数据不仅可以提高工程数据处理的效率，而且数据的可靠性也能得到有效的保障。算法算法提供处理数据的手段和方法，是提取数据内涵的一系列行为的总称。软件技术基础课程1

3、8-4绪绪 论论著名计算机科学家著名计算机科学家Wirth(Wirth(沃思沃思)提出提出:数据结构数据结构+算法程序算法程序然而然而,仅有这些还不够仅有这些还不够,应是应是:数据结构算法程序设计方法语言工具和环境程序数据结构算法程序设计方法语言工具和环境程序程序设计程序设计算法设计算法设计数据结构数据结构行为特性的行为特性的设计设计结构特性的结构特性的设计设计程序中的指令必须是机器可执行的，算法中的指令则无此限制。程序中的指令必须是机器可执行的，算法中的指令则无此限制。算法的效率通常与数据的存储结构有直接关系。算法的效率通常与数据的存储结构有直接关系。软件技术基础课程18-5第1章 算法1.

4、1 算法的基本概念1.2 算法设计基本方法1.3 算法的复杂度分析软件技术基础课程18-61.1 算法的基本概念算法的基本概念n概念概念算法是为解决一个问题采取的方法和步骤。算法是为解决一个问题采取的方法和步骤。也就也就是说，算法是为实现某种计算过程而规定的基本是说，算法是为实现某种计算过程而规定的基本动作的执行序列。动作的执行序列。n算法的实现算法的实现 自动机器解自动机器解-指令的有限序列指令的有限序列。n自动机的能力：对于执行体系来说是一种制约自动机的能力：对于执行体系来说是一种制约 n描述形式的描述形式的理解能力理解能力n实现描述的实现描述的执行能力执行能力n算法的算法的有限自动机解有

5、限自动机解-在有限的存储在有限的存储空间空间和有限和有限的的时间时间内通过有限的内通过有限的步骤步骤得到预期的得到预期的结果结果。软件技术基础课程18-71.1.1 算法的基本特征算法的基本特征n1.能行性能行性(effectiveness):n每一操作都可以通过可实现的基本运算执行有限次来实每一操作都可以通过可实现的基本运算执行有限次来实现现n步骤合理性步骤合理性n步骤可操作性步骤可操作性n达到预期目的达到预期目的n与具体实现方式和环境有关。与具体实现方式和环境有关。n2.确定性确定性(definiteness):n在所指定的在所指定的范畴范畴内内无模糊性无模糊性n在所指定的在所指定的范畴范

6、畴内内无多义性无多义性。检验检验：相同输入：相同输入 相同输出。相同输出。软件技术基础课程18-8算法的基本特征算法的基本特征（续续）n3.有穷性有穷性(finiteness)n步骤有穷性步骤有穷性n时间有限性时间有限性n4.完备性完备性(self-contained)n初始条件应明确初始条件应明确n限定范围内条件应齐备限定范围内条件应齐备n结果可展现结果可展现n对异常情况的容错性对异常情况的容错性软件技术基础课程18-9算法的定义算法的定义 一组严谨定义运算一组严谨定义运算顺序顺序的的规则规则，并且，并且每一个规则都是每一个规则都是有效有效且且明确明确的，此顺的，此顺序将在序将在有限有限的次

7、数下的次数下终止终止并获得预期并获得预期的的结果结果。软件技术基础课程18-101.1.2 算法的基本要素算法的基本要素n对对数据对象的运算和操作数据对象的运算和操作n针对算法涉及的数据信息针对算法涉及的数据信息n最基本的动作和步骤单元最基本的动作和步骤单元n算法的控制结构算法的控制结构n针对算法的过程步骤针对算法的过程步骤n控制基本操作和步骤的组合顺序控制基本操作和步骤的组合顺序软件技术基础课程18-11算法要素描述系统的组成算法要素描述系统的组成n1.运算和操作的描述运算和操作的描述n标识符：用户编程时使用的名字标识符：用户编程时使用的名字n运算符运算符:n算术运算符：算术运算符：+，-，

8、*，/等等n关系运算符：关系运算符：，=，!=，=，=n逻辑运算符：逻辑运算符：&(逻辑与逻辑与)，！，！(逻辑非逻辑非)，|(逻辑或逻辑或)n位运算符：位运算符：&，|，n数据传输：数据传输：赋值赋值，输入输入，输出输出等。等。软件技术基础课程18-12算法描述方式算法描述方式n算法描述方式：算法描述方式：n框图描述法：框图描述法：用流程图的方式来描述，对输入、输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。n非形式描述法：非形式描述法：用自然语言，同时还使用一些程序设计语言中的语句来描述算法。n类高级算法语言描述法：类高级算法语言描述法：常采用类C或C+的所谓伪语言，具有容易编

9、写、阅读和格式统一的特点。n高级算法语言描述法：高级算法语言描述法：这是可以在计算机上运行并获得结果的算法描述，使给定的问题能在有限的时间内被计算机执行。通常这类算法也成为程序。软件技术基础课程18-13算法描述方式（续）算法描述方式（续）n以求两个整数以求两个整数m、n（mn）的最大公因子为例来说明不同算法描）的最大公因子为例来说明不同算法描述方法。述方法。非形式算法描述非形式算法描述该问题的非形式算法描述为：求余数以n除m，并令r为余数(0rn)；余数是否为0若r=0则结束算法，n就是最大公因子；替换并返回a若r0则mn，nr返回a。框图法框图法C语言描述语言描述int max_commo

10、n_factor(int m,int n)int r;r=m%n;while(r!=0)m=n;n=r;r=m%n;return n;软件技术基础课程18-14算法要素描述系统的组成算法要素描述系统的组成n2.控制结构控制结构控制基本运算的控制基本运算的执行顺序执行顺序n赋值赋值n选择选择-条件转移条件转移(多分枝选择多分枝选择)n循环语句循环语句以上三种动作语句的组合可以完成任何复杂的过程序列以上三种动作语句的组合可以完成任何复杂的过程序列软件技术基础课程18-15赋值语句赋值语句n赋值语句的形式为赋值语句的形式为 a=e;，其中其中a为变量名或数组为变量名或数组元素，元素，e为算术表达式或

11、逻辑表达式。为算术表达式或逻辑表达式。n如果如果a和和b都都为为变量名或数组元素，则可用记号变量名或数组元素，则可用记号ab，表示将表示将a与与b的内容进行交换。的内容进行交换。(或或c=a;a=b;b=c;)软件技术基础课程18-16控制转移语句控制转移语句 n无条件转移语句用如下形式：无条件转移语句用如下形式：goto 标号标号n条件转移语句有以下两种形式：条件转移语句有以下两种形式：IF(C)S 或或 IF(C)S1 ELSE S2软件技术基础课程18-17循环语句循环语句nWHILE语句的形式为：语句的形式为：while();do while();nFOR语句的形式为语句的形式为:fo

12、r(i=1;i=end;i+);软件技术基础课程18-18其他辅助语句：其他辅助语句：lbreak;终止整个循环终止整个循环 lcontinue；退出本次循环退出本次循环 lreturn()语句用于结束算法的执行语句用于结束算法的执行 lREAD（或（或INPUT）语句用于输入）语句用于输入lOUTPUT（或（或PRINT，或，或WRITE）语句用于输出。）语句用于输出。软件技术基础课程18-191.2 计算机算法设计的基本方法计算机算法设计的基本方法n1.列举法列举法(枚举法枚举法)首先依据问题的部分条件首先依据问题的部分条件确定确定答案的大致答案的大致范围范围，然后在此，然后在此范围内对所

13、有可能的范围内对所有可能的情况情况逐一逐一验证验证，直到全部情况验证，直到全部情况验证完。若某个情况使验证完。若某个情况使验证符合符合问题的条件，则为本题的一问题的条件，则为本题的一个个答案答案；若全部情况验证完后均不符合题目的条件，则；若全部情况验证完后均不符合题目的条件，则问题问题无解无解n确定枚举的确定枚举的集合集合(范围）范围）n确定枚举的确定枚举的条件条件和和验证验证方法（起止，顺序，相关性，方法（起止，顺序，相关性，过程）过程）n优化枚举的条件和范围。优化枚举的条件和范围。n优点：简单。优点：简单。n弱点：低效弱点：低效软件技术基础课程18-20列举法实例列举法实例n求不定方程的百

14、鸡问题：求不定方程的百鸡问题：设设x，y，z分别为母鸡、公鸡和小鸡的只数。母鸡每只三元、公分别为母鸡、公鸡和小鸡的只数。母鸡每只三元、公鸡每只二元、小鸡两只一元。问百元买百鸡有几种解法？鸡每只二元、小鸡两只一元。问百元买百鸡有几种解法？写代数方程：写代数方程：x+y+z=100 3x+2y+z/2=100软件技术基础课程18-21用列举法写算法就十分方便：用列举法写算法就十分方便：void BuyChicks()int x,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=10

15、0)&(n=100)cout x,y,z;如何优化如何优化?软件技术基础课程18-22优化后的程序：优化后的程序：void BuyChicks()int x,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 过程的递归过程的递归n需要需要机器能力机器能力的支持的支持n效率问题效率问题软件技术基础课程18-25 n直接递归直接递归:递归函数的函数体中存在显式的自我调用时，被称为直接递归。例如，函递归函数的函数体中存

16、在显式的自我调用时，被称为直接递归。例如，函数数foo中包含自我调用，因此是直接递归。中包含自我调用，因此是直接递归。int foo(int x)if(x=0)return x;return foo(x-1);n间接递归：间接递归：如果函数中包含对另一个函数的调用而该函数最终会调用函数如果函数中包含对另一个函数的调用而该函数最终会调用函数foo，则被，则被称为间接递归。称为间接递归。int foo(int x)if(x=0)return x;return bar(x);int bar(int y)return foo(y-1);软件技术基础课程18-26递归设计方法递归设计方法n把把阶数阶数较

17、高的一个过程，转化为阶数较低较高的一个过程，转化为阶数较低同类型同类型的过程。的过程。n采用递归编写程序能使程序变得非常采用递归编写程序能使程序变得非常简单简单而而清晰清晰。递归的主要思想包括三个方面：递归的主要思想包括三个方面：na)定义形式是递归的。定义形式是递归的。nb)数据之间的关系（即数据结构）按递归定义。数据之间的关系（即数据结构）按递归定义。nc)问题本身没有明显的递归结构，但用递归求解比用问题本身没有明显的递归结构，但用递归求解比用迭代求解更简单。迭代求解更简单。软件技术基础课程18-27递归设计举例递归设计举例n对于输入的参数对于输入的参数n，依次打印出自然数，依次打印出自然

18、数1至至n。非递归解：非递归解：#include Using namespace std;void write(int n)int k;for(k=1;k=n;k+)coutkendl;return;递归解：递归解：#include Using namespace std;void write1(int n)if(n!=0)/边界条件，递归入口边界条件，递归入口 write1(n-1)；/递归前进段递归前进段 coutn1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：每次只能移动一个圆盘；大盘不能叠在小盘上面。软件技术基础课程18-31n算法描述：算法描述：Hanoi

19、(n,X,Y,Z)if n=1 then move(X,1,Z)else Hanoi(n-1,X,Z,Y)move(X,n,Z)Hanoi(n-1,Y,X,Z)endifreturn前进段前进段?返回段返回段?边界条件边界条件?软件技术基础课程18-32n回溯法回溯法n试探法试探法n无法总结出求解规律。无法总结出求解规律。n无法列举可能的条件和解集。无法列举可能的条件和解集。n逐步试探逐步试探n局部成功，则继续试探。局部成功，则继续试探。n若失败，沿原路退回若干步，改变条件和方向再试，直至若失败，沿原路退回若干步，改变条件和方向再试，直至找到解。找到解。软件技术基础课程18-33皇后问题皇后问

20、题N N皇后问题自然语言描述：皇后问题自然语言描述：在在n n行行n n列的国际象棋棋盘上，列的国际象棋棋盘上，若两个皇后位于同一行、同若两个皇后位于同一行、同一列、同一对角线上，则称一列、同一对角线上，则称为它们为互相攻击。为它们为互相攻击。n n皇后问题的皇后问题的解解是指：是指：找到这找到这n n个皇后的互不攻个皇后的互不攻击的击的布局布局思考：思考：1）如何表示棋盘、棋子和布棋？）如何表示棋盘、棋子和布棋？2）如何描述布棋规则？）如何描述布棋规则？3）如何设计布棋步骤？）如何设计布棋步骤？软件技术基础课程18-34n基本思路基本思路依次为每一行确定该行皇后的合法位置依次为每一行确定该行

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

22、的皇后，并从其所在的下一个列并从其所在的下一个列(j+1j+1)继续试探。继续试探。程序实现的要素？程序实现的要素？软件技术基础课程18-35皇后问题皇后问题对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。软件技术基础课程18-

23、36思考题思考题解的唯一性解的唯一性?1 12 23 3n n12in解的完备性解的完备性-全部解集全部解集?无解的证明无解的证明?ENDEND软件技术基础课程18-37软件技术基础课程18-381.3 算法的复杂度分析算法的复杂度分析n算法的评价算法的评价n算法的复杂度算法的复杂度n算法的最优性算法的最优性n快速算法的设计快速算法的设计n制约算法效率的要素制约算法效率的要素n时间时间n空间空间软件技术基础课程18-39算法评价标准算法评价标准n算法评价标准算法评价标准n正确性正确性n程序不含语法错误程序不含语法错误n对于几组输入数据能够得出满足要求的结果对于几组输入数据能够得出满足要求的结果

24、n对于精心挑选的典型、苛刻的几组输入数据能够得出满足要求对于精心挑选的典型、苛刻的几组输入数据能够得出满足要求的结果的结果-一般作为衡量标准一般作为衡量标准n对于一切合法的输入数据对于一切合法的输入数据都能产生满足规格说明要求的结果都能产生满足规格说明要求的结果 -很难满足很难满足(无法枚举无法枚举)n可读性可读性:容易阅读理解，模块化，可以牺牲效率容易阅读理解，模块化，可以牺牲效率n健壮性健壮性：异常处理机制：异常处理机制n高效率高效率与与低存储量低存储量需求需求软件技术基础课程18-401.3.1 算法的时间复杂度算法的时间复杂度n1.时间复杂度时间复杂度-一个算法运行时间的相对度量。一个

25、程序的时间复杂度是指程序从开始到结束运行所需要的时间。n算法执行时间算法执行时间:n算法算法执行时间执行时间=原操作的执行次数之和原操作的执行次数之和*原操作的执行时间原操作的执行时间n算法执行所需考虑因素算法执行所需考虑因素:n与非关键性细节无关与非关键性细节无关n与执行算法的机器速度无关与执行算法的机器速度无关n与辅助环境无关与辅助环境无关n时间复杂度时间复杂度度量方法度量方法:算法基本操作算法基本操作重复执行的次数重复执行的次数是模块是模块n的某一个函数的某一个函数f(n)。工作量工作量=f(n)n：问题的规模：问题的规模n时间复杂度表示方法时间复杂度表示方法：T(n)=O(f(n)软件

26、技术基础课程18-41n随着模块n的增大，算法执行时间的增长率和f(n)增长率成正比。n在计算时间复杂度时，先找出算法的基本操作先找出算法的基本操作，然后根据对应的各语句确定它的执行次数确定它的执行次数，再找出T(n)的同数量级（它的同数量级有以下：1，log(2)n，n，n log(2)n，n的平方，n的三次方，2的n次方，n!），找出后，令f(n)=该数量级，若 T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n)=O(f(n)时间复杂度分析时间复杂度分析软件技术基础课程18-42乘法运算是乘法运算是基本操作基本操作，因为：，因为：核心操作，处于最深层循环；核心操作，处于最深层循环

27、；花费时间（相对于加法）。花费时间（相对于加法）。例例 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 时间复杂度分析举例时间复杂度分析举例软件技术基础课程18-43按数量级递增排列，常见的时间复杂度有：按数量级递增排列，常见的时间复杂度有：常量阶：常量阶：O(1)对数阶：对数阶：O(logn)线性阶：线性阶：O(n)线性对数阶：线性对数阶：O(nlog n)平方阶：平方阶：O(n2)立方阶：立方阶：O(

28、n3)K次方阶：次方阶：O(nk)指数阶：指数阶：O(2n)T(n)=O(f(n)时间复杂度的表示时间复杂度的表示基本操作执行次数为基本操作执行次数为n n3 3，与整个运行时间成正比因此以，与整个运行时间成正比因此以n n的函数作为效率衡量标准。记作：的函数作为效率衡量标准。记作：T(n)=O(n3)一般而言，基本操作重复执行的一般而言，基本操作重复执行的次数次数是问题规模是问题规模n n的函数的函数T(n)T(n)，当，当n n趋于无穷大时，趋于无穷大时，T(n)T(n)的数量级（价）称为算法的数量级（价）称为算法的渐近时间复杂度，记作：的渐近时间复杂度，记作：软件技术基础课程18-44算

29、法的最优性算法的最优性n最优性定义最优性定义:n执行的基本运算执行的基本运算相对相对最少。最少。n寻优过程寻优过程n设计算法设计算法A，确定响应的上界，确定响应的上界W(n)最坏最坏n改进算法改进算法,确定响应的下界确定响应的下界F(n)至少至少n若若W(n)=F(n),则已获得最优算法则已获得最优算法,否则继续改进否则继续改进.n即即F(n)同时具备必要性和充分性同时具备必要性和充分性,则算法为最优则算法为最优.n快速算法快速算法 n时间复杂度最小时间复杂度最小软件技术基础课程18-451.3.2 算法的空间复杂度算法的空间复杂度n空间复杂度：空间复杂度：是指程序运行从开始到结束所需的存储空

30、间。n执行算法所需要的存储空间包括：执行算法所需要的存储空间包括：n算法程序所占空间算法程序所占空间n输入数据所占空间输入数据所占空间n执行过程所需的额外空间执行过程所需的额外空间通常以算法的空间复杂度作为算法所需存储空间的量度。空间复杂度的表示：空间复杂度的表示：S(n)=O(g(n)空间复杂度也是问题规模n的函数。表示随问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。软件技术基础课程18-46算法分析举例算法分析举例n求和的例子，求和的例子，int n=100;int sum=0;for(int i=1;i物理上相邻物理上相邻,关系自然确定关系自然确定n易于易于描述线性

31、结构描述线性结构，也可，也可存储经过线性化处理的非线性结存储经过线性化处理的非线性结构构n主要数据类型主要数据类型:向量（表格存储结构）向量（表格存储结构）,数组数组n高级计算机语言以高级计算机语言以数据类型数据类型的方式提供了一个基本数据结的方式提供了一个基本数据结构集的存储和操作。构集的存储和操作。n影响选择的因素：数据的影响选择的因素：数据的访问效率访问效率和存储和存储空间占用空间占用的权衡。的权衡。软件技术基础课程18-66软件技术基础课程18-67n顺序结构数据的存取顺序结构数据的存取软件技术基础课程18-68顺序存储结构顺序存储结构分析分析线性结构线性结构 B B（D D，R R）

32、D Daa，b b，c c，d d，e e，ffR R(b(b，c)c),(c(c，d),(dd),(d，a),(aa),(a，f),f),（f f，e e）顺顺序序存存储储的的示示意意图图（假假设设每每一一个个数数据据元元素素占占一一个个存存储储单单元元），数数据据元元素的存储空间是连续的。素的存储空间是连续的。1005b1006c1007d1008a1009f1010e软件技术基础课程18-69n 2.链式存储结构链式存储结构n每个节点由两部分组成每个节点由两部分组成:数据域数据域,位置指示域位置指示域(指针域指针域)n即可实现线性结构即可实现线性结构,又可表示非线性结构又可表示非线性结构

33、n特点特点:n可以表示可以表示任意复杂任意复杂的结构的结构n存储空间存储空间不连续不连续n存储顺序与结构存储顺序与结构顺序不一致顺序不一致n不能随机访问不能随机访问n访问访问效率不均等效率不均等n主要形式主要形式:单链表、双链表、多重链表、循环链表单链表、双链表、多重链表、循环链表data 单元节点P软件技术基础课程18-70链式存储链式存储示例示例每个结点设一指针，用以指出每个结点设一指针，用以指出其后件的存储序号。最后一个其后件的存储序号。最后一个结点的指针为空，用结点的指针为空，用“0 0”表表示。示。第一个结点专门用一个指第一个结点专门用一个指针（称为头指针，用针（称为头指针，用HEA

34、DHEAD表示）表示）指向它。指向它。线性结构线性结构 B B（D D，R R）D Daa，b b，c c，d d，e e，ffR R(b(b，c)c),(c(c，d),(dd),(d，a),(aa),(a，f),f),（f f，e e）data 单元节点单元节点PHEAD指针所指存储地址是？软件技术基础课程18-71数据的逻辑结构与存储结构的关系数据的逻辑结构与存储结构的关系1.1.数据的逻辑结构必定要有某种存储结构实现数据的逻辑结构必定要有某种存储结构实现2.2.两种结构的关联既不固定，也不唯一。两种结构的关联既不固定，也不唯一。3.3.常用数据结构的分类可以常用数据结构的分类可以定义在逻

35、辑结构上定义在逻辑结构上，也可以也可以定义在存储结构上定义在存储结构上，还可以，还可以定义在存储定义在存储方法上。方法上。软件技术基础课程18-722.1.3 数据结构的图形表示n逻辑结构的表示逻辑结构的表示n符号的表示符号的表示 B=(D,R)B-数据结构数据结构,D-数据元素的集合数据元素的集合,R-D上的一个关系上的一个关系n图形的表示图形的表示d2d3d1d4d5根节点根节点内部节点内部节点终节点终节点关系描述关系描述软件技术基础课程18-73例、家族的族谱例、家族的族谱 家族的族谱反映的是家族成员之间的血缘关系，假设家族的族谱反映的是家族成员之间的血缘关系，假设某家族有某家族有101

36、0个成员：个成员：A A、B B、C C、D D、E E、F F、G G、H H、I I、J J，他，他们之间的血缘关系可以用如下图表示。们之间的血缘关系可以用如下图表示。这种分支结构关系被称为树结构，它很象一棵倒置的这种分支结构关系被称为树结构，它很象一棵倒置的树，树，A A 是树的根。是树的根。非线性结构的图形表示J JI IA AC CH HG GF FE E家族树的图示表示家族树的图示表示血缘关系是血缘关系是一种非线性结构关系一种非线性结构关系B BD D软件技术基础课程18-74数据结构数据结构的研究对象及的研究对象及本课程讨论的问题本课程讨论的问题数据结构数据结构的研究对象：的研究

37、对象：n非数值数据之间的结构关系，不一定能在分非数值数据之间的结构关系，不一定能在分析数学范畴内建立解析模型析数学范畴内建立解析模型n运算操作以插入、删除、查找、更改为主。运算操作以插入、删除、查找、更改为主。本课程讨论的问题本课程讨论的问题：应用中常用的几种数据结构，以及如何存应用中常用的几种数据结构，以及如何存储储,如何处理它们。如何处理它们。软件技术基础课程18-75 操作与数据结构的定义密切相关。主要算法涉及到以下操作：操作与数据结构的定义密切相关。主要算法涉及到以下操作：插入插入：在数据结构中的指定位置插入新的数据元素。：在数据结构中的指定位置插入新的数据元素。删除删除：删去数据结构

38、中的指定的数据元素。：删去数据结构中的指定的数据元素。更新更新：改变数据结构中某个数据元素的值。：改变数据结构中某个数据元素的值。查找查找：在数据结构中寻找满足某个特定要求的数据元素。：在数据结构中寻找满足某个特定要求的数据元素。（返回位置或值）（返回位置或值）排序排序：在线性数据结构中重新安排数据元素之间的逻辑顺：在线性数据结构中重新安排数据元素之间的逻辑顺序关系。序关系。数据结构的基本操作软件技术基础课程18-76算法与数据结构的对应性1.行为特性设计行为特性设计-算法设计算法设计 信息结构特性设计信息结构特性设计-数据结构设计数据结构设计2.不能离开数据结构去抽象地分析程序的算法；也不能

39、脱离算法不能离开数据结构去抽象地分析程序的算法；也不能脱离算法去孤立地研究程序的数据结构，而只能从算法与数据结构的统一去孤立地研究程序的数据结构，而只能从算法与数据结构的统一上去认识程序。上去认识程序。软件技术基础课程18-77数据结构对算法影响数据结构对算法影响n一个算法的效率与数据的表示形式直一个算法的效率与数据的表示形式直接有关，对程序质量的影响极大。接有关，对程序质量的影响极大。n数据的构成和表示方式数据的构成和表示方式n数据的存储方式数据的存储方式n数据的类型选择数据的类型选择软件技术基础课程18-78离散问题中的算法与数据结构离散问题中的算法与数据结构软件技术基础课程18-79离散

40、问题中的算法与数据结构离散问题中的算法与数据结构软件技术基础课程18-80n算法与程序设计的关系。算法与程序设计的关系。n程序就是在数据的某些特定的表示方式和结构基程序就是在数据的某些特定的表示方式和结构基础上对抽象算法的计算机语言具体表述。础上对抽象算法的计算机语言具体表述。n数据结构是对数据的抽象，独立于具体数据数据结构是对数据的抽象，独立于具体数据n算法是对处理过程的抽象，独立于具体处理算法是对处理过程的抽象，独立于具体处理程序设计程序设计=算法算法+数据结构数据结构程序的基本概念程序的基本概念软件技术基础课程18-81本阶段小结本阶段小结数据数据数据抽象模型数据抽象模型数据元素数据元素

41、数据项数据项数据结构数据结构逻辑结构逻辑结构存储结构存储结构运算运算线性结构线性结构非线性结构非线性结构顺序存储结构顺序存储结构链式存储结构链式存储结构算法算法时间复杂度时间复杂度空间复杂度空间复杂度软件技术基础课程18-82本阶段重点本阶段重点n算法的概念算法的概念(算法是为实现某种计算过程而规定的基本动作的算法是为实现某种计算过程而规定的基本动作的执行序列。执行序列。)n算法的算法的4个基本属性个基本属性（能行性，确定性，有穷性，完备性）（能行性，确定性，有穷性，完备性）n数据结构的特征数据结构的特征（顺序存储，链式存储）（顺序存储，链式存储）n数据结构的描述数据结构的描述（D+R）END