《数据结构概述》PPT课件.ppt

第二章 常用数据结构及其运算1计算机软件计算机软件技术基础技术基础上海大学上海大学 通信与信息工程学院通信与信息工程学院安安 平平计算机基础教学课件计算机基础教学课件第二章 常用数据结构及其运算2学时数：学时数：4040，其中习题课，其中习题课2 2学时。学时。讲授主要内容：第讲授主要内容：第2 2、3 3、4 4章章自学内容：自学内容：其余各章其余各章 课程的主要内容及安排课程的主要内容及安排第二章 常用数据结构及其运算3常用数据结构及其运算常用数据结构及其运算第二章第二章第二章 常用数据结构及其运算42 21 1 概概 述述2 22 2 线性表线性表2 23 3 栈与队栈与队2 25 5 树与二叉树树与二叉树2 26 6 图图2 27 7 查查 找找2 28 8 排排 序序第二章 常用数据结构及其运算52.1 2.1 概概 述述2.1.1 2.1.1 数据结构的概念数据结构的概念1. 数值型与非数值型数据数值型与非数值型数据数值型：数值型：整型、实型、布尔型等整型、实型、布尔型等非数值型：非数值型：文献检索、金融管理、商业系统文献检索、金融管理、商业系统 等数据处理等数据处理2. 数据结构数据结构研究非数值运算的程序设计问题。研究非数值运算的程序设计问题。数据结构就是相互之间存在一种或多种特定数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。关系的数据元素的集合。如如线性关系、层次关系、网状关系线性关系、层次关系、网状关系等。等。第二章 常用数据结构及其运算62.1 2.1 概概 述述数据数据(data)是信息的载体，指所有能输入到计是信息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数、字符、符号等的集合。分为数值型数值型和和非数非数值型值型数据两类。数据两类。数据元素数据元素(data element)是数据的基本单位。是数据的基本单位。如数据集合如数据集合N= 1N= 1，2 2，3 3，4 4，5 5 中整数中整数1 1至至5 5均为数据元素。均为数据元素。 数据元素不一定是单个的数字或字符，也可数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。能是若干个数据项的组合，如学生信息。 数据元素有时也称结点或记录。数据元素有时也称结点或记录。3. 基本概念和术语基本概念和术语第二章 常用数据结构及其运算72.1 2.1 概概 述述数据类型数据类型程序设计语言中允许的变量类型程序设计语言中允许的变量类型 基本数据类型（原子类型）：变量值不可分，基本数据类型（原子类型）：变量值不可分，如整型、实型、字符型等如整型、实型、字符型等 结构类型：变量值可分，如数组、结构体等结构类型：变量值可分，如数组、结构体等数据对象数据对象(data object)性质相同的数据元素的性质相同的数据元素的集合集合。如大写字母字符的数据对象是集合：如大写字母字符的数据对象是集合：C= AC= A，BB，.，Z Z 。第二章 常用数据结构及其运算82.1 2.1 概概 述述数据结构数据结构(data structure)是指同一数据对象中各是指同一数据对象中各数据元素间存在的关系。数据元素间存在的关系。 数据结构与算法数据结构与算法 程序程序算法算法数据结构数据结构算法算法指解决特定问题的有限运算序列指解决特定问题的有限运算序列第二章 常用数据结构及其运算92.1 2.1 概概 述述1.1.逻辑结构逻辑结构：研究数据元素及其关系的数学特性，：研究数据元素及其关系的数学特性， 即数据元素间的逻辑关系。即数据元素间的逻辑关系。二元组二元组 S =S =（D D，R R） D D数据元素的非空有限集合数据元素的非空有限集合R RD D上关系的非空有限集合。上关系的非空有限集合。2.1.2 2.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构第二章 常用数据结构及其运算102.1 2.1 概概 述述四类基本结构：四类基本结构：线性结构（一对一）线性结构（一对一） 树形结构（一对多）树形结构（一对多） 图形结构（多对多）图形结构（多对多）2.1.2 2.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构集合集合第二章 常用数据结构及其运算11例1：linearity = (D, R)，其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , 例2：Tree= (D, R)，其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , 第二章 常用数据结构及其运算12例4：S = (D, R)，其中D 1,2,3,4,5,6R = r1, r2r 1= , , , , r2=,例3：Graph= (D, R)，其中D 1,2,3,4,5; R = rr = , , , , 第二章 常用数据结构及其运算132.1 2.1 概概 述述2.2.物理结构物理结构( (存储结构存储结构) )：是逻辑结构在计算是逻辑结构在计算机中的映象，即具体实现。机中的映象，即具体实现。四种基本存储结构：顺序存储结构 链式存储结构 索引存储结构 散列存储结构3.3.逻辑结构与存储结构的关系逻辑结构与存储结构的关系算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。同一种逻辑结构可采用不同的存储结构。2.1.2 2.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构第二章 常用数据结构及其运算142.1 2.1 概概 述述2.1.3 2.1.3 算法与算法分析算法与算法分析一、什么是算法一、什么是算法 算法是对特定问题求解步骤的一种描述，是指算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个令的有限序列，其中每条指令表示一个或多个操作。操作。 算法的五个特征：算法的五个特征：有穷性、确定性、可行性、有穷性、确定性、可行性、 输入、输出输入、输出 算法描述：算法描述：采用采用类类C C语言语言的形式，有时也用自然的形式，有时也用自然语言。注释部分用语言。注释部分用/或或/ /* *.* */ /表示。表示。第二章 常用数据结构及其运算152.1 2.1 概概 述述2.1.3 2.1.3 算法与算法分析算法与算法分析二、算法设计的要求：二、算法设计的要求：正确性、健壮性、效率与低存储正确性、健壮性、效率与低存储三、算法评价标准：三、算法评价标准：时间复杂度、空间复杂度时间复杂度、空间复杂度一般时间复杂度考虑的较多。一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法，算法的分析一个可执行的算法不一定是一个好算法，算法的分析 通常用计算机执行时在通常用计算机执行时在时间时间和和空间空间两方面的消耗多少两方面的消耗多少作为评价该算法优劣的标准。作为评价该算法优劣的标准。 度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常有两种方法： 事后统计事后统计和和事前分析估算事前分析估算着重介绍方法。（算法、问题规模、语言、机器代码质量、机器执行指令的速度）第二章 常用数据结构及其运算162.1 2.1 概概 述述一、时间复杂度一、时间复杂度1.1. 频度：频度：指一条语句重复执行的次数。记作：指一条语句重复执行的次数。记作：F(n)F(n)2.2. 算法的时间度量算法的时间度量：T(n)=O(F(n)T(n)=O(F(n)是问题规模是问题规模 n n 的某个函数的某个函数F(n),F(n),称为算法称为算法的渐进时间复杂度或时间复杂度。的渐进时间复杂度或时间复杂度。例：例：T(n)=3nT(n)=3n2 2 + 2n, + 2n, 则则 T(n)=O(nT(n)=O(n2 2) ) T(n)=3 T(n)=3n n + 2+ 2n n, ,则则 T(n)=O(3T(n)=O(3n n) )2.1.4 2.1.4 算法分析技术初步算法分析技术初步第二章 常用数据结构及其运算172.1 2.1 概概 述述“+x”“+x”的语句频度及三段程序的时间复杂度：的语句频度及三段程序的时间复杂度：(a)(a) (b) (b) (c) (c)F(n):F(n): 1 1 n n n n2 2T(n):T(n): O(1) O(1) O(n) O(n) O(n O(n2 2) )2.1.4 2.1.4 算法分析技术初步算法分析技术初步例例: : ( (a) +x;s=0a) +x;s=0 (b) for (i=1;i=n;+i) +x;s+=x; (b) for (i=1;i=n;+i) +x;s+=x; (c) for (j=1;j=n;+j) (c) for (j=1;j=n;+j)for (k=1;k=n;+k) +x;s+=x;for (k=1;k=n;+k) +x;s+=x;第二章 常用数据结构及其运算18问题问题 ？有A、B两段程序同时运行，在某时刻A的运行速度是B的2倍，因此，A的算法复杂度比B低（即效率高）。2.1 2.1 概概 述述第二章 常用数据结构及其运算192.1 2.1 概概 述述 常见的时间复杂度常见的时间复杂度 1 1）O(1)O(1)：常量型常量型 2 2）O(n)O(n)、O(nO(n2 2) )、.、O(O(n nk k) )：多项式型多项式型 3 3）O(logO(log2 2n)n)、O(2logO(2log2 2n)n)：对数型对数型 4 4）O(2O(2n n) )、O(eO(en n) )：指数型指数型按增长率排序，一般有：按增长率排序，一般有：1) 1) 3) 2) 4)3) 2) 4)2.1.4 2.1.4 算法分析技术初步算法分析技术初步T(n)n510 15 202n(n/2)35n2100n200log2n2000第二章 常用数据结构及其运算202.1 2.1 概概 述述 当难以精确计算基本操作执行次数（或语句频当难以精确计算基本操作执行次数（或语句频度）情况下，只需求出关于度）情况下，只需求出关于 n n 的增长率或阶的增长率或阶即可。即可。 当难以确定各种输入数据集出现的概率时，平当难以确定各种输入数据集出现的概率时，平均时间复杂度也难以确定时，可用最坏的情均时间复杂度也难以确定时，可用最坏的情况作为分析依据况作为分析依据 2.1.4 2.1.4 算法分析技术初步算法分析技术初步第二章 常用数据结构及其运算212.1 2.1 概概 述述例：例：求下列程序段的时间复杂度求下列程序段的时间复杂度1.1. for (i=0; in; i+)for (i=0; in; i+)2.2. for (j=0; jn; j+)for (j=0; jn; j+)3.3. bij=0;bij=0;4.4. for (k=0; kn; k+)for (k=0; k 外层逐层分析外层逐层分析第二章 常用数据结构及其运算262.1 2.1 概概 述述 2.1.4 2.1.4 算法分析技术初步算法分析技术初步 5)5) 过程调用语句：过程调用语句：a.a.非递归过程：根据过程调用的层次，由内而外分非递归过程：根据过程调用的层次，由内而外分 析程序的运行时间。析程序的运行时间。b.b.递归调用：可先对递归过程设一特定的运行时间递归调用：可先对递归过程设一特定的运行时间 函数函数T(n)T(n)，根据过程递归调用的情况，得到根据过程递归调用的情况，得到T(n)T(n) 的一个递推关系。的一个递推关系。 6)6) go to go to 语句：语句：可以最坏情况进行计算，即在遇到向可以最坏情况进行计算，即在遇到向下转移的下转移的go to go to 语句时，可认为语句时，可认为go to go to 语句所引起语句所引起的控制转移根本没有发生；当遇到向上转移的的控制转移根本没有发生；当遇到向上转移的go go to to 语句时，则必须考虑它对程序运行时间的影响。语句时，则必须考虑它对程序运行时间的影响。第二章 常用数据结构及其运算272.1 2.1 概概 述述4.4. 时间复杂度计算举例时间复杂度计算举例 2.1.4 2.1.4 算法分析技术初步算法分析技术初步例1： (1) for ( i=1; i=i+1; -j ) (3) if ( Aj-1Aj ) (4)temp = Aj-1;(5)Aj-1=Aj;(6)Aj=temp; 分析：(4)(6): O(1)(3)(6): O(1)(2)(6): O(1(n-i) = O(n-i)(1)(6): T(n)=O(n2)()(211nOinOni第二章 常用数据结构及其运算282.1 2.1 概概 述述2.1.4 2.1.4 算法分析技术初步算法分析技术初步例2：for ( i=2 ; i= i ; -j) S ;求“S”语句的频度及整个程序段的算法复杂度分析：i=2：执行 n-1 次i=3：执行 n-2 次i=n-2；执行 3 次则：F(n) = 3+4+5+n-1 = (n-3)(n+2)/2 T(n) = O(n2)第二章 常用数据结构及其运算292.1 2.1 概概 述述2.1.4 2.1.4 算法分析技术初步算法分析技术初步例3： i=1; While ( i=n) i=i*3 ;求语句的频度及整个程序段的算法复杂度分析：设句的频度为F(n)则：1log)( 33)(nnFnnFT(n) = O(log3n)第二章 常用数据结构及其运算302.1 2.1 概概 述述2.1.4 2.1.4 算法分析技术初步算法分析技术初步例4： prime( int n ) / n为一正整数 int i=2 ; while ( n%i)!=0 & i*1.0 sqrt(n)printf(“%d是一素数n”, n); elseprintf(“%d不是一素数n”, n);求算法的复杂度分析：设嵌套最深层语句“ i+”的频度为F(n),有：F(n)1.0= (y+1)(y+1) do y = y+1 ;求语句的频度和整个程序段的算法复杂度分析：F(n)F(n) 10 ) do if w 20 then w=w-10 ; k-elsew=w+10;求语句的频度分析：对每一合法k值，句执行2次则，句频度F(n)= (21-10)222第二章 常用数据结构及其运算332.1 2.1 概概 述述2.1.4 2.1.4 算法分析技术初步算法分析技术初步例7： x = 87 ; y = 10 ; while ( y 0 ) if ( x 100 ) x - = 10 ; y - - ; else x + + ; 求语句的频度和整个算法的复杂度。分析：句频度F(n)= 15119114T(n)=O(1)第二章 常用数据结构及其运算342.1 2.1 概概 述述2.1.4 2.1.4 算法分析技术初步算法分析技术初步例8： int fact ( int n)/ 计算n! (1)if ( n=1)(2)fact=1;else(3)fact=n*fact(n-1) ; 计算程序段的时间复杂度1 , 1n ),1()(ndnTCnT第二章 常用数据结构及其运算352.1 2.1 概概 述述2.1.4 2.1.4 算法分析技术初步算法分析技术初步例9： float p (n) int n; (1) if (n0) if (x100) x - = 10 ; y-elsex+ ; 本节结束，返回目录