《java版数据结构 第1章 绪论课件》由会员分享，可在线阅读，更多相关《java版数据结构 第1章 绪论课件（43页珍藏版）》请在金锄头文库上搜索。
1、数据结构 第一章 概述,第一章 概 述,教学目标： 了解数据结构的相关概念和掌握 算法的基本概念和性质 算法的性能分析和评价 重点：算法的概念、描述方法、评价标准和分析 难点：算法分析,为什么要学习数据结构,软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件系统设计的核心。,数据结构十算法=程序,例1-1 学生信息检索系统,学生文件,例1 学生信息检索系统,按姓名,索引表,例1 学生信息检索系统,按专业,索引表,例1 学生信息检索系统,按年级,索引表,例1-2 人机对奕问题,例1-3 教学计划编排问题,数据结构课程主要是研究
2、非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。 学习数据结构的目的就是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。,数据结构的学科地位,.综合性的专业基础课 .介于数学、计算机硬件和计算机软件之间的核心课程 .不仅仅是程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的基础,1.1.2 有关概念和术语,数据（data)所有能输入到计算机中去的描述客观事物的符号。 数据元素（data element）数据的基本单位，也称节点（node）或记录（record）。 数据对象（d
3、ata Object）具有共同特性的元素集合，是数据的一个子集。 数据结构（data structure)数据元素和数据元素关系的集合。,一个数据结构有两个要素： 数据元素的集合； 关系的集合。,Data_Structure=(D，R) 其中D是数据元素的有限集，R是D上的关系的有限集。,数据的逻辑结构,数据的逻辑结构指数据结构中元素之间的逻辑关系。它是从具体问题中抽象出来的数学模型。是独立于计算机存储器（与具体的计算机无关）。可分为如下几种基本类型： 集合结构： 线性结构： 树型结构： 图形结构：,数据的存储结构,数据的存储结构数据的逻辑结构在计算机存储器中的存储方式，又称物理结构。可分为如
4、下两种类型。 顺序存储结构： 链式存储结构：,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,1.2 算法的概念及其特征,算法（algorithm）：是在解决问题时，按照某种机械的步骤一定可以得到问题的结果的处理过程；是计算机解决问题的过程，是解决某一特定问题的具体步骤的描述，是指令的有限序列。,1.2.2 算法的三要素,操作： 算术运算：加、减、乘、除。 关系比较：大于、小于、等于、不等于 逻辑运算：与、或、非 数据传送：输入、输出（计算）、赋值（计算）。 控制结构： 顺序结构：选择结构：循环结构： 数据结构：,1.2.3 算法的基本性质,目的性 分
5、步性 有序性 有限性 操作性,1.2.4 算法的基本特征,有穷性 确定性 可行性 算法有零个或多个的输入 算法有一个或多个的输出,1.2.5 算法设计的要求,正确性 可读性 稳健性 高效率与低存储量的要求,1.3 算法分析和评价,对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的3条主要标准是： （1）算法实现所耗费的时间（时间复杂度）。 （2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间（空间复杂度）。 （3）算法应易于理解、易于编码、易于调试等。,1.3.1 算法的时间复杂度,1。 和算法执行时间相关的因素 问题中数据存储的数据结构
6、； 算法采用的数据模型； 算法设计的策略； 问题的规模； 实现算法的程序语言； 编译算法产生的机器代码的质量； 计算机执行指令的速度。,算法时间效率的衡量方法,算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量，评价的方法有： 事后分析法 事前分析估算法,事后分析法,将算法用程序设计语言实现，然后度量程序的运行时间。 缺点：必须先运行依据算法编制的程序； 不同的算法在相同环境下运行分析，工作效率太低； 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。,事前分析估算法,同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算
7、法效率不合适。 渐进时间复杂度：随着问题规模n的增长，算法执行时间增长率和函数f(n)的增长率相同，可记作：T(n)=o(f(n)，称T(n)为算法的渐进时间复杂度，简称时间复杂度，o是数量级的符号。,时间复杂度估算,从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。 一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。,时间复杂度定义,如果存在两个正常数c和n0，使得对所有的n，n n0 ，有： f(n) cg(n) 则有： f(n)=O(g(n),1.每个赋值语句或读/写语句的运行时间通常是O(1）。但有一些例外情况,如赋值语
8、句的右部表达式可能出现函数调用,这时就要考虑计算函数值所耗费的时间。 2.顺序语句的运行时间由线性规则决定，即为该序列中耗费时间最多的语句的运行时间。,3.语句if的运行时间为条件语句测试时间（通常取0(1)）加上分支语句的运行时间，语句if-else-if的运行时间为条件测试时间加上分支语句的运行时间。 4.循环语句的运行时间是n次重复执行循环体所耗费时间的总和。,5. 常见的渐进时间复杂度有： O(1) ：常量时间阶 O (n)：线性时间阶 O(n) ：对数时间阶 O(nn) ：线性对数时间阶 O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n),例如：一个程序
9、的实际执行时间为 T(n)=2.7n3+3.8n2+5.3 则T(n)=O(n3),1.3.2 算法的空间复杂度,空间复杂度 ：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作： S(n)=O(f(n) 其中： n为问题的规模(或大小),1.3.2 算法的空间复杂度,该存储空间一般包括三个方面： 输入数据所占的空间; 算法（程序）本身所占的空间; 辅助变量所占的空间。 一般地，算法的空间复杂度指的是辅助空间。,1.3.2 算法的空间复杂度,一维数组an： 空间复杂度 O(n) 二维数组anm： 空间复杂度 O(n*m),例1 +x; s=0 ; 将x自增看成是基本操作，则语句
10、频度为，即时间复杂度为(1) 。 如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。,例2 for(i=1; i=n; +i) +x; s+=x ; 语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。,例3 for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x ; 语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。,例4 两个n阶方阵的乘法 for(i=1，i=n; +i) for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik*bkj ; 由于是一个三重循环
11、，每个循环从1到n，则总次数为： nnn=n3时间复杂度为T(n)=O(n3) 一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。,例5 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai,j=x; 语句频度为： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。,定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则A(n)=O(n m),一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。,
