[理学]Data01.ppt

教材名称： 第一章 绪论 1.1 数据结构的基本概念 1.2 数据结构分类 1.3 算法及其描述 1.4 算法分析 1.5 算法设计 1.1数据结构的基本概念 1、数据（data） 数据元素（Data Element） 2、结构（Structure） 4、数据结构的形式化定义 数据元素之间关系的不同属性，数据元素之间通常有四类基本结构： 1.2 数据结构分类 1、数据结构研究的问题 2、按数据结构性质分类 3、按数据结构的存储方式分类 例：求两个正整数M与N的最大公因子。 流程框图形式： 程序语言形式： 1.4 算法分析 用计算机解决具体问题的几个基本步骤： Void 算法名(参数表) { 声明部分 语句组 } 类型 函数名(参数表) { 声明部分 语句组 } 5、算法结构 例：求1-n以内的所有素数。 i = 2 i=n j = 2 j=i-1 i mod j=0 是 否 i = i+1 j = j+1 i = i+1 打印i 结束 开始 是 是 否 否 循环条件可优化，如： j =?2/i?或? SQRT(i) ? int PRIME( int n) { for (i=2; i=n; i++) { flag = 1; for (j=2; j=i-1; j++) { if ((i%j)==0) { flag = 0; break; } } if (flag==1) pintf(“%d\n”,i) /*素数*/ }; 正确性（Correctness）：算法应当满足具体问题的需求，对问题的输入、输出和处理必须有明确而正确的描述。 设计一个“好”的算法应考虑达到以下目标： 所谓“正确”，大致包含四层意义： 一是，程序不含语法错误； 二是，程序对几组输入数据能够得出满足问题说明所要求的结果； 三是，程序对于精心选择的典型、苛刻的输入数据和边界条件数据也能够满足要求； 四是，程序对一切合法的输入数据都能产生满足规格需求说明的结果。 健壮性（robustness）：当输入数据非法时，算法也能适当地作出反应和处理，不会产生莫名其妙的错误输出，并且能控制错误的扩散。 可读性（readability）：算法主要是为人的阅读和交流而设计的，其次才是计算机执行，因此，可读性好有助于对算法的理解、修改。 执行效率与低存储量需求：执行效率一般指算法的执行时间，对于同一个问题，执行时间短的算法效率较高；存储量是指算法执行过程中所需要的存储空间。 一种是事后统计。 对依据该算法编写的不同程序通过一组或者若干组相同的数据进行统计分析。 这种方法存在两个明显的缺陷，一是必须先运行依据该算法编写的程序，二是所得时间的统计依赖于计算机的硬件和软件等环境因素，有时容易掩盖算法本身的优劣。 度量一个程序执行时间的方法通常有两种： 另一种是事前估算。 高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：（a）依据的算法选用何种策略；（b）问题的规模；（c）书写程序的语言，对于同一个算法，实现语言的级别越高，执行效率越低；（d）编译程序所产生的机器代码质量；（e）机器执行指令的速度。 如何度量？ 首先，被评价的算法应该是正确的。 当输入一组合理数据时，能够在有限的运行时间内计算出正确的结果；对于不合理的数据输入，能够给出警告信息。 算法分析的目的在于改进算法。那么，如何对一个算法进行评价呢？ 第三，依据该算法编写的程序占用计算机存储空间的度量，即所谓的空间复杂度。 其次，依据该算法编写的程序在计算机中运行时间的度量，即通常所说的时间复杂度，它是一个算法运行时间的相对度量。 其他方面。如可读性、可移植性以及易测试性等。 如何评价？ 程序运行时间的多少，主要与如下的因素有关： 问题的规模。如，计算100以内或者1000以内的所有素数。 源程序的编译功能的强弱以及产生的机器代码质量的优劣。 机器执行一条目标指令的时间长短。 程序中语句的执行次数。 时间复杂度 从算法中选取一种对于所研究问题是基本运算的元操作，以该基本操作重复执行的次数作为算法的时间度量。即频度统计法。 算法是由控制结构（顺序、分支和循环）和元操作（指固有数据类型的操作，如赋值语句、判断语句等）构成的，算法时间取决于这两者的综合效果。 例如，n×n矩阵相乘的算法中，“乘法”运算是“矩阵相乘问题”的基本操作，整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，记作T(n)=O(n3)。 一条语句的频度就是指该语句被执行的次数。而整个算法的频度是指算法中所有语句的频度之和。 for (i = 1; i= n; i++)