java版数据结构第1章绪论.ppt

数据结构数据结构第一章第一章 概述概述第一章第一章 概概 述述教学目标：教学目标：l了解数据结构的相关概念和掌握了解数据结构的相关概念和掌握 l 算法的基本概念和性质算法的基本概念和性质l算法的性能分析和评价算法的性能分析和评价重点：算法的概念、描述方法、评价标准和重点：算法的概念、描述方法、评价标准和分析分析难点：算法分析难点：算法分析为什么要学习数据结构为什么要学习数据结构 软件设计是计算机学科各个领域的核心。软件设计是计算机学科各个领域的核心。软件设计时要考虑的首要问题是数据的表示、组软件设计时要考虑的首要问题是数据的表示、组织和处理方法。数据结构设计和算法设计是软件织和处理方法。数据结构设计和算法设计是软件系统设计的核心。系统设计的核心。数据结构十算法数据结构十算法=程序程序例例1-1 学生信息检索系统学生信息检索系统学生文件线性表学号学号姓名姓名性别性别专业专业年级年级980001吴承志吴承志男男计算机科学与技术计算机科学与技术98级级980002李淑芳李淑芳女女信息与计算科学信息与计算科学98级级990301刘丽刘丽女女数学与应用数学数学与应用数学99级级990302张会友张会友男男信息与计算科学信息与计算科学99级级990303石宝国石宝国男男计算机科学与技术计算机科学与技术99级级000801何文颖何文颖女女计算机科学与技术计算机科学与技术2000级级000802赵胜利赵胜利男男数学与应用数学数学与应用数学2000级级000803崔文靖崔文靖男男信息与计算科学信息与计算科学2000级级010601刘丽刘丽女女计算机科学与技术计算机科学与技术2001级级010602魏永鸣魏永鸣男男数学与应用数学数学与应用数学2001级级l例例1 学生信息检索系统学生信息检索系统按姓名线性表崔文靖崔文靖8何文颖何文颖6李淑芳李淑芳2刘丽刘丽3,9石宝国石宝国5魏永鸣魏永鸣10吴承志吴承志1赵胜利赵胜利7张会友张会友4索引表l例例1 学生信息检索系统学生信息检索系统按专业索引表线性表l例例1 学生信息检索系统学生信息检索系统按年级索引表线性表2000级6,7,82001级9,1098级1,299级3,4,5例例1-2 人机对奕问题人机对奕问题树.图课程编号课程名称先修课程C1计算机导论无C2数据结构C1，C4C3汇编语言C1C4C程序设计语言C1C5计算机图形学C2，C3，C4C6接口技术C3C7数据库原理C2，C9C8编译原理C4例例1-3 教学计划编排教学计划编排问题问题数据结构课程主要是研究非数值计算的程序数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。们之间的关系和操作的学科。学习数据结构的目的就是为了了解计算机处学习数据结构的目的就是为了了解计算机处理对象的特性，将实际问题中所涉及的处理理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。对象在计算机中表示出来并对它们进行处理。数据结构的学科地位数据结构的学科地位.综合性的专业基础课综合性的专业基础课.介于数学、计算机硬件和计算机软件之间的介于数学、计算机硬件和计算机软件之间的核心课程核心课程.不仅仅是程序设计的基础，而且是设计和实不仅仅是程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的基础系统程序和大型应用程序的基础1.1.2 有关概念和术语有关概念和术语l数据（数据（data)所有能输入到计算机中去的所有能输入到计算机中去的描述描述客观事物的符号。客观事物的符号。l数据元素（数据元素（data element）数据的数据的基本单位基本单位，也称节点（也称节点（node）或记录（或记录（record）。）。l数据数据对象对象（data Object）具有共同特性的元具有共同特性的元素集合，是数据的一个子集。素集合，是数据的一个子集。l数据结构（数据结构（data structure)数据元素和数据数据元素和数据元素关系的集合元素关系的集合。根据数据元素间关系的基本特性，有四种基本数据结构（集合）数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图一个数据结构有两个要素：一个数据结构有两个要素：l数据元素的集合；数据元素的集合；l关系的集合。关系的集合。Data_Structure=(D，R)其中其中D是数据元素的有限集，是数据元素的有限集，R是是D上的上的关系的有限集。关系的有限集。数据的逻辑结构数据的逻辑结构l数据的逻辑结构数据的逻辑结构指数据结构中元素之间的指数据结构中元素之间的逻辑关系。逻辑关系。它是从具体问题中抽象出来的数它是从具体问题中抽象出来的数学模型。是独立于计算机存储器（与具体的学模型。是独立于计算机存储器（与具体的计算机无关）。计算机无关）。可分为如下几种基本类型：可分为如下几种基本类型：集合结构：集合结构：线性结构：线性结构：树型结构：树型结构：图形结构：图形结构：数据的存储结构数据的存储结构l数据的存储结构数据的存储结构数据的逻辑结构在计数据的逻辑结构在计算机算机存储器中的存储方式，又称物理结存储器中的存储方式，又称物理结构。可分为如下两种类型。构。可分为如下两种类型。顺序存储结构：顺序存储结构：链式存储结构：链式存储结构：元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 .1400 元素2 1536 .1536 元素3 1346 链式存储链式存储 h 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：1.2 算法的概念及其特征算法的概念及其特征 算法（算法（algorithm）：是在解决问：是在解决问题时，按照某种机械的步骤一定可以得题时，按照某种机械的步骤一定可以得到问题的结果的处理过程；是计算机解到问题的结果的处理过程；是计算机解决问题的过程，是决问题的过程，是解决某一特定问题的解决某一特定问题的具体步骤的描述，是具体步骤的描述，是指令的有限序列。指令的有限序列。1.2.2 算法的三要素算法的三要素操作：操作：l算术运算：加、减、乘、除。算术运算：加、减、乘、除。l关系比较：大于、小于、等于、不等于关系比较：大于、小于、等于、不等于l逻辑运算：与、或、非逻辑运算：与、或、非l数据传送：输入、输出（计算）、赋值（计算）。数据传送：输入、输出（计算）、赋值（计算）。控制结构：控制结构：l顺序结构：选择结构：循环结构：顺序结构：选择结构：循环结构：数据结构：数据结构：1.2.3 算法的基本性质算法的基本性质目的性目的性分步性分步性有序性有序性有限性有限性操作性操作性1.2.4 算法的基本特征算法的基本特征有穷性有穷性确定性确定性可行性可行性算法有零个或多个的输入算法有零个或多个的输入算法有一个或多个的输出算法有一个或多个的输出1.2.5 算法设计的要求算法设计的要求正确性正确性可读性可读性稳健性稳健性高效率与低存储量的要求高效率与低存储量的要求1.3 算法分析和评价算法分析和评价对算法的分析和评价，一般应考虑正确性、可维护对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的其中评价算法的3条主要标准是：条主要标准是：（1）算法实现所耗费的时间（时间复杂度）。）算法实现所耗费的时间（时间复杂度）。（2）算法实现所耗费的存储空间，其中主要考）算法实现所耗费的存储空间，其中主要考虑辅助存储空间（空间复杂度）。虑辅助存储空间（空间复杂度）。（3）算法应易于理解、易于编码、易于调试等。）算法应易于理解、易于编码、易于调试等。1.3.1 算法的时间复杂度算法的时间复杂度1。和算法执行时间相关的因素和算法执行时间相关的因素l问题中数据存储的数据结构；问题中数据存储的数据结构；l算法采用的数据模型；算法采用的数据模型；l算法设计的策略；算法设计的策略；l问题的规模；问题的规模；l实现算法的程序语言；实现算法的程序语言；l编译算法产生的机器代码的质量；编译算法产生的机器代码的质量；l计算机执行指令的速度。计算机执行指令的速度。算法时间效率的衡量方法算法时间效率的衡量方法 算法效率算法效率：用依据该算法编制的程用依据该算法编制的程序在计算机上执行所序在计算机上执行所消耗的时间消耗的时间来度量，来度量，评价的方法有：评价的方法有：l事后分析法事后分析法l事前分析估算法事前分析估算法事后分析法事后分析法 将算法用程序设计语言实现，然后度量程将算法用程序设计语言实现，然后度量程序的运行时间。序的运行时间。缺点：缺点：必须先运行依据算法编制的程序；必须先运行依据算法编制的程序；不同的算法在相同环境下运行分析，不同的算法在相同环境下运行分析，工作效率太低；工作效率太低；所得时间统计量依赖于硬件、软件等所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣。环境因素，掩盖算法本身的优劣。事前分析估算法事前分析估算法同一个算法用不同的语言、不同的编译程序、在同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，不同的计算机上运行，效率均不同，所以所以使用使用绝对时间单位绝对时间单位衡量算法效率衡量算法效率不合适。不合适。渐进时间复杂度：随着问题规模渐进时间复杂度：随着问题规模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）。但有一些例外情况）。但有一些例外情况,如赋值语句的右如赋值语句的右部表达式可能出现函数调用部表达式可能出现函数调用,这时就要考虑计这时就要考虑计算函数值所耗费的时间。算函数值所耗费的时间。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)例如：一个程序的实际执行时间为例如：一个程序的实际执行时间为T(n)=2.7n3+3.8n2+5.3则则T(n)=O(n3)1.3.2 算法的空间复杂度算法的空间复杂度空间复杂度空间复杂度：是指算法编写成程序后，在计算：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：机中运行时所需存储空间大小的度量。记作：S(n)=O(f(n)其中：其中：n为问题的规模为问题的规模(或大小或大小)1.3.2 算法的空间复杂度算法的空间复杂度该存储空间一般包括三个方面：该存储空间一般包括三个方面：l 输入数据所占的空间输入数据所占的空间;l 算法（程序）本身所占的空间算法（程序）本身所占的空间;l 辅助变量所占的空间。辅助变量所占的空间。一般地，算法的空间复杂度指的是一般地，算法的空间复杂度指的是辅助空辅助空间间。1.3.2 算法的空间复杂度算法的空间复杂度l 一维数组一维数组an：空间复杂度空间复杂度 O(n)l 二维数组二维数组anm：空间复杂度空间复杂度 O(n*m)例例1 +x;s=0;将将x自增看成是基本操作，则语句频度为，自增看成是基本操作，则语句频度为，即时间复杂度为即时间复杂度为(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;由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1到到n，则总次数为：，则总次数为：nnn=n3时间复杂度为时间复杂度为T(n)=O(n3)一般地，常用最深层循环内的语句中的原操作的执行频一般地，常用最深层循环内的语句中的原操作的执行频度度(重复执行的次数重复执行的次数)来表示。来表示。例例5 5 for(ifor(i=2;i=2;i=n;+in;+i)for(jfor(j=2;j=i-1;+j)=2;j=i-1;+j)+x;+x;ai,jai,j=x;=x;语句频度为：语句频度为：1+2+3+1+2+3+n-2=(1+n-2)+n-2=(1+n-2)(n-2)/2(n-2)/2 =(n-1)(n-2)/2=n =(n-1)(n-2)/2=n2 2-3n+2-3n+2 时间复杂度为时间复杂度为O(nO(n2 2)，即此算法的时间复杂度为，即此算法的时间复杂度为平方阶。平方阶。定理定理：若：若A(nA(n)=a)=a m m n n m m+a+a m-1m-1 n n m-1m-1+a+a1 1n+an+a0 0是一是一个个m m次多项式，则次多项式，则A(nA(n)=)=O(nO(n m m)一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为（即零次多项式）来限界。而一个时间为O(nO(n2 2)的算的算法则由一个二次多项式来限界。法则由一个二次多项式来限界。