软件技术基础

1、软件技术基础课程 18-1 主讲教师：朱海华 机电学院15B426 Email: 软件技术基础 软件技术基础课程 18-2 绪绪 论论 工程软件工程软件概述概述 计算机三大应用领域：科学计算、信息处理、过程控制科学计算、信息处理、过程控制。 随着信息技术的普及，各类计算机软硬件系统在工程应用领域的广泛应用。 工程软件在实际工程应用中占有相当重要的地位。 工程软件主要应用领域包括工程软件主要应用领域包括： 工程辅助系统工程辅助系统：工程数值计算（Engineering Computation）、计算机 辅助设计CAD、计算机辅助制造CAM、计算机辅助工程教育CAEE、计 算机集成制造系统CIMS

2、、计算机辅助测试CAT、工业控制IC、计算机 仿真CS等。 工程事务处理工程事务处理：分为事务型系统、管理型系统、决策型系统。 现代工程通信及信息交流现代工程通信及信息交流：通过支持计算机网络的工程软件不仅可以 实现远程的数据传输、状态监控和现场资源配置等工作，而且还能异地 共享和交流各种生产信息资源。 软件技术基础课程 18-3 绪绪 论论 工程软件工程软件的基本元素的基本元素 工程软件的三个基本要素是数据数据、数据结构数据结构和算法算法。 工程数据工程数据是工程软件系统的处理对象。 数据结构数据结构是对工程数据的组织。组织结构良好的数据不仅可以提高工程数 据处理的效率，而且数据的可靠性也能

3、得到有效的保障。 算法算法提供处理数据的手段和方法，是提取数据内涵的一系列行为的总称。 软件技术基础课程 18-4 绪绪 论论 著名计算机科学家著名计算机科学家Wirth(Wirth(沃思沃思) )提出提出: : 数据结构数据结构+ +算法程序算法程序 然而然而, , 仅有这些还不够仅有这些还不够, , 应是应是: : 数据结构算法程序设计方法语言工具和环境程序数据结构算法程序设计方法语言工具和环境程序 程序设计程序设计 算法设计算法设计 数据结构数据结构 行为特性的行为特性的 设计设计 结构特性的结构特性的 设计设计 程序中的指令必须是机器可执行的，算法中的指令则无此限制。程序中的指令必须是

4、机器可执行的，算法中的指令则无此限制。 算法的效率通常与数据的存储结构有直接关系。算法的效率通常与数据的存储结构有直接关系。 软件技术基础课程 18-5 软件技术基础课程 18-6 1.1 算法的基本概念算法的基本概念 n概念概念 算法是为解决一个问题采取的方法和步骤算法是为解决一个问题采取的方法和步骤。也就也就 是说，算法是为实现某种计算过程而规定的基本是说，算法是为实现某种计算过程而规定的基本 动作的执行序列。动作的执行序列。 n算法的实现算法的实现 自动机器解自动机器解-指令的有限序列指令的有限序列。 n自动机的能力自动机的能力：对于执行体系来说是：对于执行体系来说是一种制约一种制约 n

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

6、关。 n2. 确定性确定性(definiteness): n在所指定的在所指定的范畴范畴内内无模糊性无模糊性 n在所指定的在所指定的范畴范畴内内无多义性无多义性。 检验检验：相同输入：相同输入 相同输出。相同输出。 软件技术基础课程 18-8 算法的基本特征算法的基本特征（续续） n3. 有穷性有穷性(finiteness) n步骤有穷性步骤有穷性 n时间有限性时间有限性 n4. 完备性完备性(self-contained) n初始条件应明确初始条件应明确 n限定范围内条件应齐备限定范围内条件应齐备 n结果可展现结果可展现 n对异常情况的容错性对异常情况的容错性 软件技术基础课程 18-9 算

7、法的定义算法的定义 一组严谨定义运算一组严谨定义运算顺序顺序的的规则规则，并，并 且每一个规则都是且每一个规则都是有效有效且且明确明确的，此的，此 顺序将在顺序将在有限有限的次数下的次数下终止终止并获得预并获得预 期的期的结果结果。 软件技术基础课程 18-10 1.1.2 算法的基本要素算法的基本要素 n对对数据对象的运算和操作数据对象的运算和操作 n针对算法涉及的数据信息针对算法涉及的数据信息 n最基本的动作和步骤单元最基本的动作和步骤单元 n算法的控制结构算法的控制结构 n针对算法的过程步骤针对算法的过程步骤 n控制基本操作和步骤的组合顺序控制基本操作和步骤的组合顺序 软件技术基础课程

8、18-11 算法要素描述系统的组成算法要素描述系统的组成 n1. 运算和操作的描述运算和操作的描述 n标识符标识符：用户编程时使用的名字：用户编程时使用的名字 n运算符运算符: n算术运算算术运算符符：+，-，*，/ 等等 n关系运算符：关系运算符：，=， !=，=，= n逻辑逻辑运算符运算符： r=m%n; while(r!=0) m=n; n=r; r=m%n; return n; 软件技术基础课程 18-14 算法要素描述系统的组成算法要素描述系统的组成 n2. 控制结构控制结构控制基本运算的控制基本运算的执行顺序执行顺序 n赋值赋值 n选择选择-条件转移条件转移 (多分枝选择多分枝选择

9、) n循环语句循环语句 以上三种动作语句的组合可以完成任何复杂的过程序列以上三种动作语句的组合可以完成任何复杂的过程序列 软件技术基础课程 18-15 赋值赋值语句语句 n赋值语句的形式为赋值语句的形式为 a= =e; ，其中其中a为变量名或数组为变量名或数组 元素，元素，e为算术表达式或逻辑表达式。为算术表达式或逻辑表达式。 n如果如果a和和b都都为为变量名或数组元素，则可用记号变量名或数组元素，则可用记号 ab，表示将表示将a与与b的内容进行交换。的内容进行交换。(或或 c=a;a=b;b=c;) 软件技术基础课程 18-16 控制转移控制转移语句语句 n无条件转移语句用如下形式：无条件转

10、移语句用如下形式： goto 标号标号 n条件转移语句有以下两种形式：条件转移语句有以下两种形式： IF ( C ) S 或或 IF ( C) S1 ELSE S2 软件技术基础课程 18-17 循环循环语句语句 nWHILE语句的形式为：语句的形式为： while() ; do while(); nFOR语句的形式为语句的形式为: for (i=1;i=end;i+) ; 软件技术基础课程 18-18 其他辅助语句：其他辅助语句： lbreak; 终止整个循环终止整个循环 lcontinue；退出本次循环退出本次循环 lreturn()语句用于结束算法的执行语句用于结束算法的执行 lREAD

11、（或（或INPUT）语句用于输入）语句用于输入 lOUTPUT（或（或PRINT，或，或WRITE）语句用于输出。）语句用于输出。 软件技术基础课程 18-19 1.2 计算机算法设计的基本方法计算机算法设计的基本方法 n1. 列举法列举法 (枚举法枚举法) 首先依据问题的部分条件首先依据问题的部分条件确定确定答案的大致答案的大致范围范围，然后在，然后在 此范围内对所有可能的此范围内对所有可能的情况情况逐一逐一验证验证，直到全部情况，直到全部情况 验证完。若某个情况使验证验证完。若某个情况使验证符合符合问题的条件，则为本问题的条件，则为本 题的一个题的一个答案答案；若全部情况验证完后均不符合题

12、目的；若全部情况验证完后均不符合题目的 条件，则问题条件，则问题无解无解 n确定枚举的确定枚举的集合集合(范围）范围） n确定枚举的确定枚举的条件条件和和验证验证方法（起止，顺序，相关性，方法（起止，顺序，相关性， 过程）过程） n优化枚举的条件和范围。优化枚举的条件和范围。 n优点：简单。优点：简单。 n弱点：低效弱点：低效 软件技术基础课程 18-20 列举法实例列举法实例 n求不定方程的百鸡问题：求不定方程的百鸡问题： 设设x ，y，z分别为母鸡、公鸡和小鸡的只数。母鸡每只三元、公分别为母鸡、公鸡和小鸡的只数。母鸡每只三元、公 鸡每只二元、小鸡两只一元。问百元买百鸡有几种解法？鸡每只二元

13、、小鸡两只一元。问百元买百鸡有几种解法？ 写代数方程：写代数方程： 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=100) ; 如何优化如何优化? 软件技术基础课程 18-22 优化后的程序：优化后的程序： void BuyChicks() int x,y,z

14、; 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直接递归直接递归: 递归函数的函数体中存在显式的自我调用时，被称为直接递归。例如，函递归函数的函数体中存在显式的自我调用时，被称为直接递归。例如，函 数数foo中包含自我调用，因此是直接递归。中包含自我调用，因此是直接

15、递归。 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把把阶数阶数较高的一个过程，转化为阶数较低较高的一个过程，转化为阶数较低同类

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

17、 #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-31 n算法描述：算法描

18、述： Hanoi(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) endif return 前进段前进段? 返回段返回段? 边界条件边界条件? 软件技术基础课程 18-32 n回溯法回溯法 n试探法试探法 n无法总结出求解规律。无法总结出求解规律。 n无法列举可能的条件和解集。无法列举可能的条件和解集。 n逐步试探逐步试探 n局部成功，则继续试探。局部成功，则继续试探。 n若失败，沿原路退回若干步，改变条件和方向再试，直至若失败，沿原路退回若干步，改变条

19、件和方向再试，直至 找到解。找到解。 软件技术基础课程 18-33 皇后问题皇后问题 N N皇后问题自然语言描述：皇后问题自然语言描述： 在在n n行行n n列的国际象棋棋盘上，列的国际象棋棋盘上， 若两个皇后位于同一行、同若两个皇后位于同一行、同 一列、同一对角线上，则称一列、同一对角线上，则称 为它们为互相攻击。为它们为互相攻击。 n n皇后问题的皇后问题的解解是指：是指： 找到这找到这n n个皇后的互不攻个皇后的互不攻 击的击的布局布局 思考思考：1）如何表示棋盘、棋子和布棋？）如何表示棋盘、棋子和布棋？ 2）如何描述布棋规则？）如何描述布棋规则？ 3）如何设计布棋步骤？）如何设计布棋步

20、骤？ 软件技术基础课程 18-34 n基本思路基本思路 依次为每一行确定该行皇后的合法位置依次为每一行确定该行皇后的合法位置 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列列安放的皇后不动安放的皇后不动 递归安放递归

21、安放第第i+1i+1行行皇后皇后 n如果如果第第i i行行不能安放皇后，则不能安放皇后，则回溯回溯到到第第i-1i-1行行，撤销该行的皇后，撤销该行的皇后， 并从其所在的下一个列并从其所在的下一个列( (j+1j+1) )继续试探。继续试探。 程序实现的要素？程序实现的要素？ 软件技术基础课程 18-35 皇后问题皇后问题 对于皇后问题来说，由于每 一行、每一列和每一个对角 线，都只能放一个皇后，当 一个皇后放到棋盘上后，不 管它放在棋盘的什么位置， 它所影响的行和列方向上的 棋盘位置是固定的，因此在 行、列方面没有什么信息可 以利用。但在不同的位置， 在对角线方向所影响的棋盘 位置数则是不同

22、的。可以想 象，如果把一个皇后放在棋 盘的某个位置后，它所影响 的棋盘位置数少，那么给以 后放皇后留下的余地就太大， 找到解的可能性也大；反之 留有余地就小，找到解的可 能性也小。 软件技术基础课程 18-36 思考题思考题 解的唯一性解的唯一性? 1 12 23 3n n 1 2 i n 解的完备性解的完备性 -全部解集全部解集? 无解的证明无解的证明? 软件技术基础课程 18-37 软件技术基础课程 18-38 1.3 算法的复杂度分析算法的复杂度分析 n算法的评价算法的评价 n算法的复杂度算法的复杂度 n算法的最优性算法的最优性 n快速算法的设计快速算法的设计 n制约算法效率的要素制约算

23、法效率的要素 n时间时间 n空间空间 软件技术基础课程 18-39 算法评价标准算法评价标准 n算法评价标准算法评价标准 n正确性正确性 n程序不含语法错误程序不含语法错误 n对于几组输入数据能够得出满足要求的结果对于几组输入数据能够得出满足要求的结果 n对于精心挑选的典型、苛刻的几组输入数据能够得出满足要求对于精心挑选的典型、苛刻的几组输入数据能够得出满足要求 的结果的结果-一般作为衡量标准一般作为衡量标准 n对于一切合法的输入数据对于一切合法的输入数据都能产生满足规格说明要求的结果都能产生满足规格说明要求的结果 - - 很难满足很难满足(无法枚举无法枚举) n可读性可读性: 容易阅读理解，

24、模块化，可以牺牲效率容易阅读理解，模块化，可以牺牲效率 n健壮性健壮性：异常处理机制：异常处理机制 n高效率高效率与与低存储量低存储量需求需求 软件技术基础课程 18-40 1.3.1 算法的时间复杂度算法的时间复杂度 n1. 时间复杂度时间复杂度 - 一个算法运行时间的相对度量。一 个程序的时间复杂度是指程序从开始到结束运行所需要 的时间。 n算法执行时间算法执行时间: n算法算法执行时间执行时间= =原操作的执行次数之和原操作的执行次数之和* *原操作的执行时间原操作的执行时间 n算法执行所需考虑因素算法执行所需考虑因素: n与非关键性细节无关与非关键性细节无关 n与执行算法的机器速度无关

25、与执行算法的机器速度无关 n与辅助环境无关与辅助环境无关 n时间复杂度时间复杂度度量方法度量方法: 算法基本操作算法基本操作重复执行的次数重复执行的次数 是模块是模块n的某一个函数的某一个函数f(n)。 工作量工作量 = f(n) n：问题的规模：问题的规模 n时间复杂度表示方法时间复杂度表示方法： T(n) = O(f(n) 软件技术基础课程 18-41 n随着模块n的增大，算法执行时间的增长率和f(n)增长率成 正比。 n在计算时间复杂度时，先找出算法的基本操作先找出算法的基本操作，然后根据 对应的各语句确定它的执行次数确定它的执行次数，再找出T(n)的同数量级 （它的同数量级有以下：1，

26、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 乘法运算是乘法运算是基本操作基本操作，因为：，因为： 核心操作，处于最深层循环；核心操作，处于最深层循环； 花费时间（相对于加法）。花费时间（相对于加法）。 例例 n 阶矩阶矩 阵相乘的算法阵相乘的算法 for ( i = 1; i=n; +i ) for (j = 1; j=n; +j ) c i j = 0 ; for (k

27、= 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( n3 ) K次方阶：次方阶：O( nk ) 指数阶：指数阶：O( 2n ) T(n)=O(f(n) 时间复杂度的表示时间复杂度的表示 基本

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

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

30、括： 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-67 n顺序结构数据的存取顺序结构数据的存取 软件技术基础课程 18-68 顺序存储结构顺序存储结构分析分析 线性结构线性结构 B B（D

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

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

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

35、.常用数据结构的分类可以常用数据结构的分类可以定义在逻辑结构上定义在逻辑结构上， 也可以也可以定义在存储结构上定义在存储结构上，还可以，还可以定义在存储定义在存储 方法上。方法上。 软件技术基础课程 18-72 2.1.3 数据结构的图形表示 n逻辑结构的表示逻辑结构的表示 n符号的表示符号的表示 B = ( D, R) B - 数据结构数据结构, D - 数据元素的集合数据元素的集合, R - D上的一个关系上的一个关系 n图形的表示图形的表示 d2d3d1d4 d5 根节点根节点 内部节点内部节点 终节点终节点 关系描述关系描述 软件技术基础课程 18-73 例、家族的族谱例、家族的族谱

36、家族的族谱反映的是家族成员之间的血缘关系，假设家族的族谱反映的是家族成员之间的血缘关系，假设 某家族有某家族有1010个成员：个成员：A A、B B、C C、D D、E E、F F、G G、H H、I I、J J，他，他 们之间的血缘关系可以用如下图表示。们之间的血缘关系可以用如下图表示。 这种分支结构关系被称为树结构，它很象一棵倒置的这种分支结构关系被称为树结构，它很象一棵倒置的 树，树，A A 是树的根。是树的根。 非线性结构的图形表示 J J I I A A C C H HG GF FE E 家族树的图示表示家族树的图示表示 血缘关系是血缘关系是 一种非线性结构关系一种非线性结构关系 B

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