《ch6程序数据的结构组织和管理课件》由会员分享，可在线阅读，更多相关《ch6程序数据的结构组织和管理课件（63页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 程序数据的结构、组织和管理程序数据的结构、组织和管理n本章要点本章要点程序设计与算法程序设计与算法程序数据的组织与结构程序数据的组织与结构1ch6程序数据的结构组织和管理4.1 程序设计与算法程序设计与算法n4.1.1 算法与程序算法与程序n什么是算法什么是算法(algorithm )算法就是求解问题的方法和步骤算法就是求解问题的方法和步骤算法的形式化定义算法的形式化定义:算法是一个四元组，即（算法是一个四元组，即（Q，I，F），其中：），其中：Q是一个包含子集是一个包含子集I和和的集合，它表示计算机的集合，它表示计算机的状态的状态I是表示计算的输入集合是表示计算的输入集合表示计
2、算的输出集合表示计算的输出集合F表示计算的规则，它是由表示计算的规则，它是由到它自身的函数，到它自身的函数，且具有自反性，即对任何一个元素且具有自反性，即对任何一个元素q Q，有，有F(q)=q2ch6程序数据的结构组织和管理算法四元组（算法四元组（Q，I，F），），n为为x I的每个的每个x定义一个计算序列定义一个计算序列x0, x1, x2, x3 . 如下：如下：x0 = x, 对于对于k = 0, x(k+1) = F(x(k)n如果，如果，k是使是使x(k) 的最小的整数，那么的最小的整数，那么就说计算序列在就说计算序列在k步终止，并且在这种情况步终止，并且在这种情况下，说从下，说从
3、x产生输出产生输出x(k).3ch6程序数据的结构组织和管理算法实例：算法实例：求两个正整数的最大公约数求两个正整数的最大公约数的的EuclideanEuclidean算法算法1.设设M=较大的数，较大的数，N=较小的数较小的数2.R=M/N的余数的余数(将整除的余数赋给将整除的余数赋给R)3.如果如果R非零，则非零，则M=N(将将N值赋给值赋给M)，N=R (将将R值赋给值赋给N),并返回并返回2；否则，；否则，最大公约数就是当前最大公约数就是当前N值值.4ch6程序数据的结构组织和管理欧几里得欧几里得(Euclidean)Euclidean)算法的四元表算法的四元表示示 n令令Q为所有单点
4、为所有单点(n)、有序偶、有序偶(m, n)、 以及所有有序四以及所有有序四元组元组(m, n, r, 1), (m, n, r, 2), (m, n, p, 3)的集的集合，其中合，其中m, n, p是正整数，是正整数，r是一个非负整数。是一个非负整数。令令I是所有有序偶是所有有序偶(m, n)的子集，并的子集，并令令是所有单点是所有单点(n)的子集。的子集。定义定义f如下如下:nf(m, n) = (m, n, 0, 1); 1nf(m, n, r, 1) = (m, n, m mod n, 2)nf(m, n, r, 2) = (n), 如果如果r = 0, 否则否则(m, n, r,
5、3)nf(m, n, p, 3) = (n, p, p, 1) 25ch6程序数据的结构组织和管理优化后的欧几里得算法。优化后的欧几里得算法。n令令Q为所有单点为所有单点(n), 有序偶有序偶(m, n), 有序三院有序三院组组(n, r, 1)的集合，其中的集合，其中m, n为正整数，为正整数， r为为非负整数。另非负整数。另I是所有有序偶是所有有序偶(m, n)的子集，并的子集，并令令是所有单点是所有单点(n)的子集。定义的子集。定义f如下：如下：nf(m, n) = (n, m mod n, 1);f(n) = (n)nf(n, r, 1) = (n), 如果如果r = 0, 否则否则(
6、r, n mod r, 1)6ch6程序数据的结构组织和管理n算法的特性：算法的特性：输入（输入（Input）输出（输出（Output）确定性（确定性（Definiteness）有穷性（有穷性（Finiteness）有效性（有效性（Effectiveness ）4.1 程序设计与算法程序设计与算法7ch6程序数据的结构组织和管理n算法的表示算法的表示自然语言自然语言流程图流程图N-S图图伪代码伪代码计算机程序设计语言计算机程序设计语言8ch6程序数据的结构组织和管理流程图流程图输入数值输入数值a、bab输出输出b的值的值输出输出a的值的值调用结束调用结束调用调用是是否否9ch6程序数据的结构组
7、织和管理N-S图图返回返回fac的值的值当当ib?a,b);12ch6程序数据的结构组织和管理n算法的设计与评价算法的设计与评价正确性正确性可读性可读性健壮性健壮性高效性高效性n常见的算法设计方法常见的算法设计方法穷举法穷举法回溯法回溯法递推法递推法递归递归分治分治13ch6程序数据的结构组织和管理n什么是程序什么是程序在低级语言中，程序表现为一组指令和有关数据在低级语言中，程序表现为一组指令和有关数据在高级语言中，程序一般表现为一组说明和语句在高级语言中，程序一般表现为一组说明和语句程序的特征：程序的特征：利用计算机解决实际问题的过程利用计算机解决实际问题的过程明确问题的要求明确问题的要求建
8、立数学模型建立数学模型算法设计算法设计编写程序编写程序调试程序调试程序运行及结果分析运行及结果分析14ch6程序数据的结构组织和管理n程序设计语言的基本功能程序设计语言的基本功能引入标识符引入标识符记住某些值记住某些值执行一些运算执行一些运算进行信息传输进行信息传输4.1.2 程序设计的语言程序设计的语言15ch6程序数据的结构组织和管理n程序设计语言的发展程序设计语言的发展面向机器的语言面向机器的语言机器语言：所有的数据、指令、符号和信息者是以二进制数机器语言：所有的数据、指令、符号和信息者是以二进制数的形式来表示的的形式来表示的如：如：11000110 表示加法运算表示加法运算汇编语言（符
9、号语言）：汇编语言（符号语言）：面向过程语言面向过程语言侧重于问题处理过程，语言与具体的机器无关，与机器的具侧重于问题处理过程，语言与具体的机器无关，与机器的具体实现无关体实现无关4.1.2 程序设计的语言程序设计的语言16ch6程序数据的结构组织和管理n典型的面向过程语言：典型的面向过程语言：4.1.2 程序设计的语言程序设计的语言FortranFortran语言（语言（IBM Mathematical Formula Translating System 19561956）：第一个被广泛使用的高级语言，主要用于科学计算）：第一个被广泛使用的高级语言，主要用于科学计算和教学科研领域和教学科研
10、领域AlgolAlgol语言（语言（ALGOrithmic Language 19581958）：第一个被广泛使）：第一个被广泛使用的结构化语言，主要用于科学计算和教学科研领域用的结构化语言，主要用于科学计算和教学科研领域CobolCobol语言（语言（COmmon Business-Oriented Language 19601960）：）：第一个被广泛用于商业、金融等行业的工具语言第一个被广泛用于商业、金融等行业的工具语言LispLisp（19601960）：第一个函数式程序设计语言，被广泛用于人）：第一个函数式程序设计语言，被广泛用于人工智能等领域工智能等领域17ch6程序数据的结构组织
11、和管理4.1.2 程序设计的语言程序设计的语言BasicBasic语言（语言（19641964）：由）：由FortranFortran语言演变而来，简单、易学、语言演变而来，简单、易学、易用，容错性能好，适合初学者使用易用，容错性能好，适合初学者使用PascalPascal语言（语言（19701970）：在）：在AlgolAlgol语言的基础上发展而来的，语言的基础上发展而来的，主要用于教学和中小型事务管理方面主要用于教学和中小型事务管理方面C C语言（语言（19721972）：是在实现）：是在实现UNIXUNIX操作系统的过程中产生的语操作系统的过程中产生的语言工具。语句简洁、控制灵活，功能
12、强大，可移植性好，运言工具。语句简洁、控制灵活，功能强大，可移植性好，运行效率高。行效率高。ADAADA语言（语言（19801980）：第一个为大型软件开发而研制的大型语）：第一个为大型软件开发而研制的大型语言工具言工具JavaJava语言（语言（19951995）：一种适合于当前高速发展的网络环境和）：一种适合于当前高速发展的网络环境和交互式多媒体的编程语言工具交互式多媒体的编程语言工具18ch6程序数据的结构组织和管理n面向对象的语言面向对象的语言C+、Delphi、Objective-C等等n可视化语言可视化语言Visual Basic、 Visual Foxpro、Visual C+、
13、Java等等4.1.2 程序设计的语言程序设计的语言19ch6程序数据的结构组织和管理n程序设计语言的分类程序设计语言的分类n按照语言的级别分：低级语言、高级语言按照语言的级别分：低级语言、高级语言n按照用途划分：通用语言、专用语言按照用途划分：通用语言、专用语言n按照语言的成分性质划分：顺序语言、按照语言的成分性质划分：顺序语言、并发并发语言、分布式语言语言、分布式语言n按照使用者的角度：面向机器的语言、面向按照使用者的角度：面向机器的语言、面向过程的语言、面向对象的语言、可视化语言过程的语言、面向对象的语言、可视化语言n按照使用方式划分：交互式语言、非交互式按照使用方式划分：交互式语言、非
14、交互式语言语言4.1.2 程序设计的语言程序设计的语言20ch6程序数据的结构组织和管理n程序设计语言提供的基本设施程序设计语言提供的基本设施n数据类型数据类型简单类型：整型、实型、布尔型、字符型、枚举型简单类型：整型、实型、布尔型、字符型、枚举型结构类型：数组、字符串、记录、结构体、文件、日结构类型：数组、字符串、记录、结构体、文件、日期期指针类型：指针类型：n各种语句各种语句基本语句：赋值语句、输入、输出语句等基本语句：赋值语句、输入、输出语句等选择结构语句：选择结构语句：ifthen、ifthenelse、switch等等循环语句循环语句: for循环、当型循环（循环、当型循环（whil
15、e循环）、直到循环）、直到型循环（型循环（dowhile循环）循环）n其他设施其他设施4.1.2 程序设计的语言程序设计的语言21ch6程序数据的结构组织和管理n语言的翻译语言的翻译n翻译程序翻译程序指的是这样一个程序，它能够把某一种语言程序(源语言程序)改造成另一种语言程序(目标语言程序)，而两者在逻辑上是等价的 编译程序:源语言是高级语言，目标语言是机器语言/汇编语言，则翻译程序称为编译程序汇编程序:源语言是汇编语言，目标语言是机器语言，则翻译程序称为汇编程序解释程序:解释程序是另一类翻译程序，它同时处理源程序和数据,对源程序解释执行而不生成目标程序4.1.2 程序设计的语言程序设计的语言
16、22ch6程序数据的结构组织和管理4.1.2 程序设计的语言程序设计的语言词法分析词法分析语法分析语法分析词义分析词义分析中间代码生成中间代码生成代码生成代码生成源程序源程序目标程序目标程序优化优化n把高级语言程序翻译成机器语言把高级语言程序翻译成机器语言程序的方法有两种：程序的方法有两种：编译方式编译方式翻译过程大体可分为如下六步：翻译过程大体可分为如下六步：编译过程如图（编译过程如图（A）所示：）所示：23ch6程序数据的结构组织和管理n词法分析：输入源程序词法分析：输入源程序,对构成源程序的字符串进行扫描和分解对构成源程序的字符串进行扫描和分解,识识别出一个个单词别出一个个单词(也称单词
17、符号也称单词符号,或简称符号或简称符号)。在词法分析阶段工。在词法分析阶段工作所依循的是语言的词法规则作所依循的是语言的词法规则.描述词法规则的有效工具是正规式描述词法规则的有效工具是正规式和有限自动机和有限自动机 n语法分析语法分析:在词法分析的基础上在词法分析的基础上,根据语言的语法规则根据语言的语法规则,把单词符号分把单词符号分解成各类语法单位解成各类语法单位(语法范畴语法范畴),如如“短语短语”,“句子句子”, “子句子句”,“程序段程序段”等等.语法规则通常用上下文无关文法描述语法规则通常用上下文无关文法描述.n语义分析与中间代码的产生：这一阶段通常包括两方面的工作首先语义分析与中间
18、代码的产生：这一阶段通常包括两方面的工作首先对各种语法范畴进行静态语义检查对各种语法范畴进行静态语义检查,如果正确则进行另一方面的工如果正确则进行另一方面的工作作,即进行中间代码的翻译即进行中间代码的翻译.通常使用属性文法描述语义规则通常使用属性文法描述语义规则所谓所谓“中间代码中间代码”是一种含义明确是一种含义明确,便于处理的记号系统便于处理的记号系统.中间代码中间代码除四元式外除四元式外,还有三元式还有三元式,间接三元式间接三元式,逆波兰记号逆波兰记号,树形表示等树形表示等 n优化：对前段产生的中间代码进行加工优化：对前段产生的中间代码进行加工,以期在最后阶段产生更为以期在最后阶段产生更为
19、高效高效(省时间和空间省时间和空间)的代码。优化所依循的原则是程序的等价变换的代码。优化所依循的原则是程序的等价变换规则，其方法有规则，其方法有:公共子表达式的提取公共子表达式的提取,循环优化循环优化,删除无用代码等删除无用代码等 n目标代码生成：把中间代码目标代码生成：把中间代码(或经优化处理后或经优化处理后)变换成特定机器上的变换成特定机器上的低级语言代码低级语言代码.它有赖于硬件系统结构和机器指令含义它有赖于硬件系统结构和机器指令含义 4.1.2 程序设计的语言程序设计的语言24ch6程序数据的结构组织和管理图（图（A）程序的编译执行方式）程序的编译执行方式4.1.2 程序设计的语言程序
20、设计的语言目标程序.obj结果编译运行编译程序高 级 语言 源 程序可执行程序.exe链接程序运行命令链接25ch6程序数据的结构组织和管理4.1.2 程序设计的语言程序设计的语言图（图（B）程序的解释执行方式）程序的解释执行方式解释方式解释方式对源程序源程序边解解释翻翻译成机器代成机器代码边执行的高行的高级语言程序。由于它的方便言程序。由于它的方便性和交互性性和交互性较好，早期一些高好，早期一些高级语言采用言采用这种方式，如种方式，如BASIC、dBASE。但它的弱点是运行效率低，程序的运行依。但它的弱点是运行效率低，程序的运行依赖于开于开发环境，不能直接在境，不能直接在操作系操作系统下运行
21、下运行 高级语言源程序结果解释并执行解释程序26ch6程序数据的结构组织和管理n程序设计方法的三个原则程序设计方法的三个原则n抽象原则抽象原则n枚举原则枚举原则n归纳原则归纳原则4.1.3 程序设计的方法程序设计的方法27ch6程序数据的结构组织和管理n结构化程序设计结构化程序设计n结构化程序设计的背景结构化程序设计的背景n结构化程序设计的内容结构化程序设计的内容 结构化程序设计的概念是结构化程序设计的概念是结构化程序设计的概念是结构化程序设计的概念是E.W.DijkstraE.W.DijkstraE.W.DijkstraE.W.Dijkstra于于于于1969196919691969年年年年
22、首先提出的，他强调了从程序结构和风格上来研首先提出的，他强调了从程序结构和风格上来研首先提出的，他强调了从程序结构和风格上来研首先提出的，他强调了从程序结构和风格上来研究程序设计问题。也将此方法称为究程序设计问题。也将此方法称为究程序设计问题。也将此方法称为究程序设计问题。也将此方法称为“自顶向下自顶向下自顶向下自顶向下”或或或或“逐步求精逐步求精逐步求精逐步求精”法。其一是法。其一是法。其一是法。其一是“自顶向下，逐步求自顶向下，逐步求自顶向下，逐步求自顶向下，逐步求精精精精”的设计思想，即整个设计应分为若干层次，的设计思想，即整个设计应分为若干层次，的设计思想，即整个设计应分为若干层次，的
23、设计思想，即整个设计应分为若干层次，逐步加以解决；而每一步实在前一步的基础上，逐步加以解决；而每一步实在前一步的基础上，逐步加以解决；而每一步实在前一步的基础上，逐步加以解决；而每一步实在前一步的基础上，对前一步设计的细化。其二是对前一步设计的细化。其二是对前一步设计的细化。其二是对前一步设计的细化。其二是“独立功能，一个独立功能，一个独立功能，一个独立功能，一个入口，一个出口入口，一个出口入口，一个出口入口，一个出口“的模块化结构，即把大而复杂的模块化结构，即把大而复杂的模块化结构，即把大而复杂的模块化结构，即把大而复杂的问题层层细化分解成若干个相对独立、功能单的问题层层细化分解成若干个相对
24、独立、功能单的问题层层细化分解成若干个相对独立、功能单的问题层层细化分解成若干个相对独立、功能单一的问题处理模块，而每个模块与外界联系只有一的问题处理模块，而每个模块与外界联系只有一的问题处理模块，而每个模块与外界联系只有一的问题处理模块，而每个模块与外界联系只有一个单入口与单出口。其三是一个单入口与单出口。其三是一个单入口与单出口。其三是一个单入口与单出口。其三是“仅用三种基本控仅用三种基本控仅用三种基本控仅用三种基本控制结构制结构制结构制结构”的设计原则，即每个模块都只用三个基的设计原则，即每个模块都只用三个基的设计原则，即每个模块都只用三个基的设计原则，即每个模块都只用三个基本结构来描述
25、本结构来描述本结构来描述本结构来描述4.1.3 程序设计的方法程序设计的方法28ch6程序数据的结构组织和管理n三种基本的程序控制结构：三种基本的程序控制结构：4.1.3 程序设计的方法程序设计的方法AB入口入口出口出口顺序结构顺序结构选择结构选择结构PAB入口入口出口出口29ch6程序数据的结构组织和管理4.1.3 程序设计的方法程序设计的方法循环结构循环结构条件条件循环体循环体入口入口出口出口成立成立不成立不成立当型循环当型循环直到型循环直到型循环条件条件循环体循环体入口入口出口出口成立成立不成立不成立30ch6程序数据的结构组织和管理三种基本结构都具有以下特点三种基本结构都具有以下特点:
26、有一个入口有一个入口有一个出口有一个出口 结构中每一部分都应当有被执行到的机会结构中每一部分都应当有被执行到的机会,也就是说也就是说,每一部分都应当有一条从入口到出每一部分都应当有一条从入口到出口的路径通过它口的路径通过它(至少通过一次至少通过一次)没有死循环没有死循环4.1.3 程序设计的方法程序设计的方法31ch6程序数据的结构组织和管理n结构化程序设计的实现结构化程序设计的实现自顶向下，逐步求精细化的分析设计方法自顶向下，逐步求精细化的分析设计方法分而治之的分割划分技术分而治之的分割划分技术模块化的组织结构形式模块化的组织结构形式4.1.3 程序设计的方法程序设计的方法32ch6程序数据
27、的结构组织和管理n软件工程方法软件工程方法n软件工程这一概念，主要是针对软件工程这一概念，主要是针对20世纪世纪60年代年代“软件危机软件危机”而提出的。它首次出现在而提出的。它首次出现在1968年年NATO（北大西洋公约组织）会议上。自这一概念（北大西洋公约组织）会议上。自这一概念提出以来，围绕软件项目，开展了有关开发模型、提出以来，围绕软件项目，开展了有关开发模型、方法以及支持工具的研究。其主要成果有：提出了方法以及支持工具的研究。其主要成果有：提出了瀑布模型，开发了一些结构化程序设计语言（例如瀑布模型，开发了一些结构化程序设计语言（例如PASCAL语言，语言，Ada语言）、结构化方法等。
28、并语言）、结构化方法等。并且，围绕项目管理提出了费用估算、文档复审等方且，围绕项目管理提出了费用估算、文档复审等方法和工具。综观法和工具。综观60年代末至年代末至80年代初，其主要特年代初，其主要特征是，前期着重研究系统实现技术，后期开始强调征是，前期着重研究系统实现技术，后期开始强调开发管理和软件质量开发管理和软件质量4.1.3 程序设计的方法程序设计的方法33ch6程序数据的结构组织和管理n软件工程开发模式软件工程开发模式瀑布式模型瀑布式模型螺旋式模型螺旋式模型面向对象生存期模型面向对象生存期模型过程开发模型过程开发模型4.1.3 程序设计的方法程序设计的方法34ch6程序数据的结构组织和
29、管理瀑布式模型瀑布式模型把软件的生命周期分为三个时期八个阶段：把软件的生命周期分为三个时期八个阶段：软件定义时期软件定义时期问题定义阶段问题定义阶段可行性研究阶段可行性研究阶段需求分析阶段需求分析阶段软件开发时期软件开发时期总体设计阶段总体设计阶段详细设计阶段详细设计阶段编码与单元测试阶段编码与单元测试阶段综合测试阶段综合测试阶段软件维护时期软件维护时期软件的运行和维护阶段软件的运行和维护阶段4.1.3 程序设计的方法程序设计的方法35ch6程序数据的结构组织和管理n面向对象的程序设计面向对象的程序设计（Object Oriented Programming，简称简称OOP）n基本概念基本概念
30、对象：可视为一个单元的代码和数据的组合。对象对象：可视为一个单元的代码和数据的组合。对象可以是一段应用程序，如控件或窗体。整个应用程可以是一段应用程序，如控件或窗体。整个应用程序也可以是一个对象序也可以是一个对象 类：从一些对象中抽象概括出此类对象所共有的静类：从一些对象中抽象概括出此类对象所共有的静态特征（属性）和动态特征（行为）而形成类。态特征（属性）和动态特征（行为）而形成类。对象是类的实例，创建了一个类后，可以创建所需对象是类的实例，创建了一个类后，可以创建所需的任何数量的对象的任何数量的对象 消息：对象之间产生相互作用所传递的信息消息：对象之间产生相互作用所传递的信息4.1.3 程序
31、设计的方法程序设计的方法36ch6程序数据的结构组织和管理n面向对象的软件开发方法面向对象的软件开发方法n面向对象的软件开发过程包括如下五个阶段：面向对象的软件开发过程包括如下五个阶段：面向对象分析：（面向对象分析：（ Object Oriented Analysis，OOA）面向对象设计：（面向对象设计：（ Object Oriented Design，OOD）面向对象编程：（面向对象编程：（ Object Oriented Programming，OOP）面向对象测试：（面向对象测试：（ Object Oriented Test，OOT）面向对象维护：面向对象维护： （ Object Or
32、iented Soft Maintenance，OOSM）4.1.3 程序设计的方法程序设计的方法37ch6程序数据的结构组织和管理面向对象程序设计的特点面向对象程序设计的特点n封装性（封装性（Encapsulation）增加了对象的独立性增加了对象的独立性增加了数据的可靠性，保护类中的数据不被类以外的程序增加了数据的可靠性，保护类中的数据不被类以外的程序随意使用随意使用n继承性（继承性（Inheritance）概念：基类、子类（派生类）概念：基类、子类（派生类）提高了程序的重用性，提高了程序修改、扩充和设计的效提高了程序的重用性，提高了程序修改、扩充和设计的效率率n多态性（多态性（Polym
33、orphism）多态性是指同一个消息被不同对象接收时产生不同的结果多态性是指同一个消息被不同对象接收时产生不同的结果4.1.3 程序设计的方法程序设计的方法38ch6程序数据的结构组织和管理类的继承关系类的继承关系RABA1A2B139ch6程序数据的结构组织和管理n其他程序设计方法概述其他程序设计方法概述n多媒体程序设计：多媒体程序设计：4.1.3 程序设计的方法程序设计的方法需求分析需求分析脚本编写脚本编写软件结构设计软件结构设计编写代码编写代码测试运行测试运行采集和制作多媒体素材采集和制作多媒体素材文文本本图图形形图图像像音音乐乐动动画画-可视化编程可视化编程创建项目创建项目创建应用程序
34、创建应用程序编译和运行项目编译和运行项目数据库应用编程数据库应用编程-文化程序设计文化程序设计40ch6程序数据的结构组织和管理n程序的调试与纠错程序的调试与纠错n编辑一个程序编辑一个程序n程序的调试程序的调试现有调试技术有三类：现有调试技术有三类：输出存储器内容输出存储器内容在程序中插入打印语句在程序中插入打印语句借助调试工具借助调试工具调试策略调试策略试探法试探法回溯法回溯法对分查找法对分查找法归纳法归纳法演译法演译法4.1.3 程序设计的方法程序设计的方法41ch6程序数据的结构组织和管理n程序的测试与纠错程序的测试与纠错黑盒子测试黑盒子测试黑盒测试又称为功能测试或数据驱动测试，把系统看
35、成黑盒测试又称为功能测试或数据驱动测试，把系统看成一个黑盒子，不考虑程序的内在逻辑，只根据需求规格一个黑盒子，不考虑程序的内在逻辑，只根据需求规格说明书的要求来检查程序的功能是否符合它的功能说明说明书的要求来检查程序的功能是否符合它的功能说明 白盒子测试白盒子测试白盒测试又称为结构测试和逻辑驱动测试，允许测试人白盒测试又称为结构测试和逻辑驱动测试，允许测试人员对程序内部逻辑结构及有关信息来设计和选择测试用员对程序内部逻辑结构及有关信息来设计和选择测试用例，对程序的逻辑路径进行测试例，对程序的逻辑路径进行测试 常用的测试用例设计技术：常用的测试用例设计技术：逻辑覆盖逻辑覆盖等价划分等价划分边界值
36、分析边界值分析图形技术图形技术4.1.3 程序设计的方法程序设计的方法42ch6程序数据的结构组织和管理n6.2.1 数据与数据类型数据与数据类型n数据概念的扩充数据概念的扩充数据：指信息的载体，是对自然界客观事物的符数据：指信息的载体，是对自然界客观事物的符号表示，即所有能有效输入到计算机中并被计算号表示，即所有能有效输入到计算机中并被计算机程序加工和处理的符号的总称。例如：文字、机程序加工和处理的符号的总称。例如：文字、表格、图象等表格、图象等数据元素（数据元素（Data element）：数据的基本单位。）：数据的基本单位。一个数据元素可以有若干个数据项组成，数据项一个数据元素可以有若干
37、个数据项组成，数据项是数据的不可再分的最小单位是数据的不可再分的最小单位6.2 程序数据的组织与结构程序数据的组织与结构43ch6程序数据的结构组织和管理数据结构的基本概念数据结构的基本概念数据结构数据结构是指计算机程序中所操作的对象是指计算机程序中所操作的对象数据以及数据之间的相互关系和运算，一般数据以及数据之间的相互关系和运算，一般包含以下三方面的内容：包含以下三方面的内容：数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构数据的运算及实现数据的运算及实现4.2 程序数据的组织与结构程序数据的组织与结构44ch6程序数据的结构组织和管理数据的逻辑结构数据的逻辑结构：是数据元素之间的逻
38、辑关系。：是数据元素之间的逻辑关系。可用一个二元组形式来定义：可用一个二元组形式来定义：Data-structure=（D，R）D：数据元素的集合：数据元素的集合R：D上关系的集合上关系的集合数据结构一般可分为线性结构和非线性结构数据结构一般可分为线性结构和非线性结构线性结构：线性表、栈、队列、串等线性结构：线性表、栈、队列、串等非线性结构：树、图等非线性结构：树、图等4.2 程序数据的组织与结构程序数据的组织与结构线性表线性表树树图图45ch6程序数据的结构组织和管理数据的存储结构数据的存储结构： 是数据及数据之间的关系在是数据及数据之间的关系在计算机内存中的表示，主要的存储方式有顺序存计算
39、机内存中的表示，主要的存储方式有顺序存储和链式存储、索引存储、散列存储等储和链式存储、索引存储、散列存储等从逻辑结构到存储结构称之为从逻辑结构到存储结构称之为“映象映象”同一逻辑结构采用不同的存储结构存储，就得到不同同一逻辑结构采用不同的存储结构存储，就得到不同的数据结构的数据结构程序中的数据运算是定义在数据的逻辑结构上的，程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。但运算的具体实现要在存储结构上进行。常用的运算有：检索、插入、删除、更新、排序等常用的运算有：检索、插入、删除、更新、排序等4.2 程序数据的组织与结构程序数据的组织与结构46ch6程序数据的结
40、构组织和管理n数据类型数据类型数据对象：性质相同的数据元素的集合，是数据数据对象：性质相同的数据元素的集合，是数据的一个子集的一个子集数据类型：是对在计算机中表示的同一数据对象数据类型：是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作表示的总称及其在该数据对象上的一组操作表示的总称数据类型有简单（原子）数据类型和结构类型数据类型有简单（原子）数据类型和结构类型数据类型概念的六大特征：数据类型概念的六大特征：n程序设计语言中提供的数据类型程序设计语言中提供的数据类型简单类型：如整型、实型、字符型等简单类型：如整型、实型、字符型等结构类型：如数组、记录、字符串等结构类型：如数组、记录、
41、字符串等指针类型：指针类型：4.2 程序数据的组织与结构程序数据的组织与结构47ch6程序数据的结构组织和管理n4.2.2 简单数据结构的应用简单数据结构的应用算法算法+数据结构数据结构=程序程序n数组数组一组具有相同属性的元素组织在一起形成数一组具有相同属性的元素组织在一起形成数在不同的程序设计语言国引入一个整型数组在不同的程序设计语言国引入一个整型数组A的方法如下：的方法如下：Ada A：array（1.8) of integer;Basic Dim a(8);C int A8;Pascal A:array1.8 of integer;PL/I Dce a(1.8)Visual Basic
42、 Dim A(8) as integer;当数组的基类型是字符类型时，就是所谓有字符串当数组的基类型是字符类型时，就是所谓有字符串二维数组、多维数组二维数组、多维数组4.2 程序数据的组织与结构程序数据的组织与结构48ch6程序数据的结构组织和管理n线线性表性表线性表是由线性表是由n（n0）个数据元素组成的有限序列）个数据元素组成的有限序列表中有且仅有一个第一个结点，它没有前驱只有一个后继表中有且仅有一个第一个结点，它没有前驱只有一个后继有且仅有一个最后一个结点，它没有后继只有一个前驱有且仅有一个最后一个结点，它没有后继只有一个前驱其余结点都有一个前驱和一个后继其余结点都有一个前驱和一个后继可
43、以写成如下序列：可以写成如下序列：（a1，a2，an）n为为0时称为空表时称为空表例如：例如：4.2 程序数据的组织与结构程序数据的组织与结构英文字母表（英文字母表（A，B，C，Z）是一个线性表，其中的每）是一个线性表，其中的每一个字母就是一个数据元素一个字母就是一个数据元素某商场某商场2004年每月的销售额（年每月的销售额（368，500，400，625，592）(单位：万元单位：万元)也是一个线性表，其中的每一个数值就是一个数据也是一个线性表，其中的每一个数值就是一个数据元素元素49ch6程序数据的结构组织和管理4.2 程序数据的组织与结构程序数据的组织与结构学生基本情况表也是一个线性表，
44、表中的数据元素是一条记录，由学学生基本情况表也是一个线性表，表中的数据元素是一条记录，由学号、姓名、性别等六个数据项组成号、姓名、性别等六个数据项组成学号学号姓名姓名性别性别年龄年龄籍贯籍贯政治面貌政治面貌张华张华男男18北京北京团员团员王丽王丽女女18广东省广东省团员团员李强李强男男19湖南省湖南省团员团员学生基本情况表学生基本情况表50ch6程序数据的结构组织和管理线性表的主要操作：线性表的主要操作：插入：在给定的线性表的第插入：在给定的线性表的第i个元素之前插入一个新数个元素之前插入一个新数据元素，线性表长度加据元素，线性表长度加1删除：删除线性表中第删除：删除线性表中第i个元素，线性表
45、的长度减个元素，线性表的长度减1查找：在线性表中查找满足某种条件的元素，需要时查找：在线性表中查找满足某种条件的元素，需要时还可对元素的值进行更新还可对元素的值进行更新线性表的存储结构可分为顺序表和链表线性表的存储结构可分为顺序表和链表4.2 程序数据的组织与结构程序数据的组织与结构51ch6程序数据的结构组织和管理n顺顺序序表表：在在计计算算机机中中用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存储线性表的各个数据元素，称作线性表的顺序存储结构。储线性表的各个数据元素，称作线性表的顺序存储结构。逻辑上相邻的元素在内存中的存储位置也相邻逻辑上相邻的元素在内存中的存储位置也相邻由于线
46、性表的所有数据元素属于同一数据类型，所由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大小相同，因此，以每个元素在存储器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。假设线要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为性表中的第一个数据元素的存储地址为b b，每一个数，每一个数据元素占据元素占L L字节，则线性表中第字节，则线性表中第i i个元素个元素a ai i在计算机存在计算机存储空间中的存储地址为：储空间中的存储地址为： Loc(aLoc(ai i)= b+)= b+（i-1i-1）* *L L线性表的顺序
47、存储结构是一种线性表的顺序存储结构是一种随机存取随机存取的存储结构的存储结构52ch6程序数据的结构组织和管理a1a2a3an-1anb+Lbb+2Lb+(n-2)Lb+(n-1)LA0A1A2An-2An-153ch6程序数据的结构组织和管理1. 顺序表的顺序表的插入插入操作操作基本思想：基本思想：在长度为在长度为n (0nMAXNUM-1)的顺序表的顺序表L的第的第i(1in+1)个个数据元素之前插入一个新的数据元素数据元素之前插入一个新的数据元素x时，需将最后一个即时，需将最后一个即第第n个至第个至第i个元素（共个元素（共n-i+1个元素）依次向后移动一个位个元素）依次向后移动一个位置，
48、空出第置，空出第i个位置，然后把个位置，然后把x插入到第插入到第i个存储位置，插入个存储位置，插入结束后顺序结束后顺序表的长度增加表的长度增加1；在顺序存储结构的线性表中插入一个元素时，平均在顺序存储结构的线性表中插入一个元素时，平均要移动表中大约一半的数据元素（要移动表中大约一半的数据元素（n/2） 。54ch6程序数据的结构组织和管理 序号 元素 序号 元素01a12a2i-1ai-1iainanMAXSiZE-1插入x01a12a2i-1ai-1ixi+1ain+1anMAXSiZE-155ch6程序数据的结构组织和管理顺序表的删除操作 在 长 度 为 n(0nMAXNUM-1)的 顺
49、序 表 L中 删 除 第i(1in)个数据元素，需将第i+1至第n个数据元素（共n-i个）的存储位置依次前移，并使顺序表的长度减1。在顺序存储结构的线性表中删除一个元素时，平均要移在顺序存储结构的线性表中删除一个元素时，平均要移动表中大约一半的数据元素（动表中大约一半的数据元素（n-1）/2）56ch6程序数据的结构组织和管理 序号 元素 序号 元素01a12a2i-1ai-1iainanMAXSiZE-1删除第i个元素01a12a2i-1ai-1iai+1i+1ai+2n-1anMAXSiZE-157ch6程序数据的结构组织和管理线线性性表表的的链链式式存存储储结结构构就就是是用用一一组组任
50、任意意的的存存储储单单元元（可可以以是是不不连连续续的的）存存储储线线性性表表的的数数据据元元素素。对对线线性性表表中中的的每每一一个个数数据据元元素素，都都需需用用两两部部分分来来存存储储：一一部部分分用用于于存存放放数数据据元元素素值值，称称为为数数据据域域；另另一一部部分分用用于于存存放放直直接接前前驱驱或或直直接接后后继继结结点点的的地地址址（指指针针），称称为为指指针针域域，我我们们把这种存储单元称为把这种存储单元称为结点结点。在在链链式式存存储储结结构构方方式式下下，存存储储数数据据元元素素的的结结点点空空间间可可以以不不连连续续，各各数数据据结结点点的的存存储储顺顺序序与与数数据
51、据元元素素之之间间的的逻逻辑辑关关系系可可以以不不一一致致，而而数数据据元元素素之之间间的的逻逻辑辑关关系系由由指指针针域域来确定。来确定。链链式式存存储储方方式式可可用用于于表表示示线线性性结结构构，也也可可用用于于表表示示非非线线性结构。性结构。58ch6程序数据的结构组织和管理线线性性表表的的链链式式存存储储结结构构，是是一一种种物物理理存存储储单单元元上上非非连连续续、非非顺顺序序的的存存储储结结构构，数数据据元元素素的的逻逻辑辑顺顺序序是是通通过过链链表表中中的的指指针针链链接接次次序序实实现现的的。此此种种形形式式的的链链表表因因只只含含有有一一个个指指针针域域，又又称为单向链表，
52、简称称为单向链表，简称单链表单链表。 heada1a2an head它的数据元素的逻辑次序靠结点的指针来指示，插入、它的数据元素的逻辑次序靠结点的指针来指示，插入、删除操作不需要移动数据元素删除操作不需要移动数据元素59ch6程序数据的结构组织和管理n循环链表循环链表n将单链表的表中最后一个结点指针指向链表的表头将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环。结点，整个链表形成一个环。n从表中任一结点出发都可找到表中其他的结点。从表中任一结点出发都可找到表中其他的结点。 head(a)循环链表的空表形式 head (b)循环链表的一般形式a0a1an-1ai双向循环链表双
53、向循环链表 headay60ch6程序数据的结构组织和管理n栈栈n栈（栈（stack）是一种只允许在一端进行插入和删除的线性表，它是）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。一种操作受限的线性表。n在表中允许进行插入和删除的一端称为栈顶（在表中允许进行插入和删除的一端称为栈顶（top），另一端称为），另一端称为栈底栈底(bottom)。栈的插入操作通常称为入栈或进栈。栈的插入操作通常称为入栈或进栈(push)，而，而栈的删除操作则称为出栈或退栈栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称。当栈中无数据元素时，称为空栈。为空栈。n根据栈的定义可知，栈
54、顶元素总是最后入栈的，因而是最先出栈；根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进后进先出（先出（LIFO，last in first out ）的原则组织数据的，因此，栈的原则组织数据的，因此，栈也被称为也被称为“后进先出后进先出”的线性表。的线性表。4.2 程序数据的组织与结构程序数据的组织与结构出栈出栈a2an入栈入栈栈顶栈顶 top栈底栈底 bottoma161ch6程序数据的结构组织和管理n队列队列n队列（队列（queue）是一种只允许在一端进行插入，而在另一
55、端进）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为许进行插入的一端称为队尾（队尾（rear），只允许进行删除的一端，只允许进行删除的一端称为称为队头队头(front)。队列的插入操作通常称为入队列或进队列，。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。元素时，称为空队列。n根据队列的定义可知，队头元素总是最先进队列的，也总是根据队列的定义可知，队头元素总是最先
56、进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照列。这种表是按照先进先出（先进先出（FIFO，first in first out ）的原则组织数据的，因此，队列也被称为的原则组织数据的，因此，队列也被称为“先进先出先进先出”表。表。n假若队列假若队列q=a0，a1，a2，an-1，进队列的顺序为，进队列的顺序为a0，a1，a2，an-1，则队头元素为，则队头元素为a0，队尾元素为，队尾元素为an-14.2 程序数据的组织与结构程序数据的组织与结构入列出列a0a1a2aian-1frontrear62ch6程序数据的结构组织和管理4.2 程序数据的组织与结构程序数据的组织与结构anan-1a1队尾队尾队头队头链队列链队列返回目录返回目录63ch6程序数据的结构组织和管理
