数据结构第一张幻灯片幻灯片.ppt

《数据结构第一张幻灯片幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第一张幻灯片幻灯片.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第一张幻灯片第1页，共49页，编辑于2022年，星期六先修课程先修课程nC C语言语言n高等数学高等数学n离散数学离散数学第2页，共49页，编辑于2022年，星期六学时及安排学时及安排n学时：学时：1 17474学时学时n实验：实验：6 6个实验个实验n考试类型：考试（笔试）考试类型：考试（笔试）n成绩成绩=试卷成绩试卷成绩+平时成绩平时成绩n作业：周二中午之前交到教研室作业：周二中午之前交到教研室第3页，共49页，编辑于2022年，星期六公共邮箱公共邮箱n用户名：用户名：datexinxidatexinxi n密码：密码：xinxidate xinxidate 第4页，共49页，编辑

2、于2022年，星期六第一章第一章 绪绪 论论n1.1 1.1 什么是数据结构什么是数据结构n1.2 1.2 基本概念和术语基本概念和术语n1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现n1.4 1.4 算法和算法分析算法和算法分析第5页，共49页，编辑于2022年，星期六1.1 1.1 什么是数据结构什么是数据结构Niklaus WirthNiklaus Wirth Algorithm+Date Structures=ProgramsAlgorithm+Date Structures=Programs 算算 法法 +数据结构数据结构 =程序设计程序设计程序设计程序设计程序设计

3、程序设计：为计算机处理问题编制一组指令集：为计算机处理问题编制一组指令集算法算法算法算法：处理问题的策略处理问题的策略数据结构数据结构数据结构数据结构：问题的数学模型：问题的数学模型全球气象预报全球气象预报 球面坐标系下的一般环流模式方程球面坐标系下的一般环流模式方程数值计算的程序设计问题数值计算的程序设计问题数值计算的程序设计问题数值计算的程序设计问题第6页，共49页，编辑于2022年，星期六1 1、求一组（、求一组（n n个）整数中的最大值个）整数中的最大值算法算法?基本操作是比较两个数的大小基本操作是比较两个数的大小模型？模型？整数整数2 2、计算机对弈、计算机对弈算法？算法？对弈的规则

4、和策略对弈的规则和策略模型？模型？棋盘，棋子棋盘，棋子3 3、足协的数据库、足协的数据库算法？算法？需要管理的项目？如何管理？用户界面需要管理的项目？如何管理？用户界面模型？模型？表格，数据库表格，数据库第7页，共49页，编辑于2022年，星期六概括的说概括的说 数据结构描述现实世界实体的数学模型数据结构描述现实世界实体的数学模型(非数值计算非数值计算)及其上的操作在计算机中的及其上的操作在计算机中的表示和实现。表示和实现。第8页，共49页，编辑于2022年，星期六1.2 1.2 基本概念和术语基本概念和术语一、数据与数据结构一、数据与数据结构n数据数据 所有能被输入到计算机中，并被计算机处理

5、的所所有能被输入到计算机中，并被计算机处理的所有这些符号的集合，有这些符号的集合，可见，数据是计算机操作的对象的总称，是计算机处理的可见，数据是计算机操作的对象的总称，是计算机处理的信息的载体，是信息的某一种特定的符号表示形式。信息的载体，是信息的某一种特定的符号表示形式。第9页，共49页，编辑于2022年，星期六n数据元素数据元素 数据中的一个数据中的一个“个体个体”，数据结构中讨论的基本单位。，数据结构中讨论的基本单位。n数据项数据项 数据结构中讨论的最小单位，数据元素是数据项的数据结构中讨论的最小单位，数据元素是数据项的集合集合 例如：运动员例如：运动员(数据元素数据元素)姓名姓名俱乐部

6、名称俱乐部名称出生日期出生日期参加日期参加日期职务职务业绩业绩年年 月月 日日组合项组合项第10页，共49页，编辑于2022年，星期六n数据对象数据对象 是性质相同的数据元素的集合是性质相同的数据元素的集合,是数据的一个子集是数据的一个子集 例如，整数数据对象例如，整数数据对象:N=0,1,2,:N=0,1,2,，字母字符数据对象字母字符数据对象:C=:C=A A,B B,Z Z,第11页，共49页，编辑于2022年，星期六n数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合是相互之间存在一种或多种特定关系的数据元素的集合 数据元素相互之间的关系称为数据元素相互之间的关系称为结构

7、结构。例如，一个含例如，一个含1212位数的十进制数可以用三个位数的十进制数可以用三个4 4位的十位的十进制数表示，进制数表示，457834292610 457834292610 a1(4578),a2(3429),a3(2610)a1(4578),a2(3429),a3(2610)在在a1,a2,a3a1,a2,a3之间存在之间存在“次序次序”关系关系 ,4578,3429,2610 a1 ,a2 ,a3 3429,4578,2610 a2 ,a1 ,a3 是带结构的数据元素的集合是带结构的数据元素的集合第12页，共49页，编辑于2022年，星期六n又例，又例，2 2行行3 3列的矩阵列的矩

8、阵 a1,a2,a3,a4,a5,a6 a1,a2,a3,a4,a5,a6 n行的次序关系行的次序关系 row=,row=,n列的次序关系列的次序关系 col=,col=,a1 a1 a2 a2 a3 a3 a4 a4 a5 a5 a6 a6 a1,a2,a3 a4,a5,a6 a1,a2,a3 a5,a4,a6 第13页，共49页，编辑于2022年，星期六n再例，一维数组再例，一维数组 a1,a2,a3,a4,a5,a6 a1,a2,a3,a4,a5,a6 中中存在次序关系存在次序关系:a|i=1,2,3,4,5|i=1,2,3,4,5第14页，共49页，编辑于2022年，星期六n数据的逻辑

9、结构可以归结为以下四类：数据的逻辑结构可以归结为以下四类：(1)(1)线性结构线性结构 (2)(2)树形结构树形结构 (3)(3)图状结构图状结构 (网状结构网状结构)(4)(4)集合结构集合结构第15页，共49页，编辑于2022年，星期六数据结构的形式定义为：数据结构的形式定义为：n数据结构是一个二元组数据结构是一个二元组 Date_Structures=(D,S)Date_Structures=(D,S)其中其中D D是数据元素的有限集，是数据元素的有限集，S S是是D D上关系的有限集。上关系的有限集。n例如：由例如：由a1,a2,a3,a4,a5,a6a1,a2,a3,a4,a5,a6

10、构成的矩阵构成的矩阵 定义矩阵是一种数据结构定义矩阵是一种数据结构 E=D,S E=D,S D=a1,a2,a3,a4,a5,a6 D=a1,a2,a3,a4,a5,a6 S=a S=|i=1,2,3,4,5|i=1,2,3,4,5第16页，共49页，编辑于2022年，星期六数据的数据的存储结构存储结构 数据结构在计算机中的表示数据结构在计算机中的表示(映像映像)数据结构的存储映像数据结构的存储映像包括数据元素的映像和关系的映像包括数据元素的映像和关系的映像数据元素的映像方法：数据元素的映像方法：用二进制位用二进制位(bit)(bit)的位串表示数据元素的位串表示数据元素 (321)(321)

11、1010=(501)=(501)8 8=(101000001)=(101000001)2 2 A=(101)A=(101)8 8=(001000001)=(001000001)2 2第17页，共49页，编辑于2022年，星期六关系的映像方法关系的映像方法：（表示：（表示的方法）的方法）顺序映像：顺序映像：以数据元素在存储器之间一个固定的相对位以数据元素在存储器之间一个固定的相对位置的关系来表示数据元素的关系置的关系来表示数据元素的关系y 的存储位置和的存储位置和x的存储位置之间差一的存储位置之间差一个常量个常量C。而而C是一个隐含值，整个存储结构中只含数据元素本身的信是一个隐含值，整个存储结构

12、中只含数据元素本身的信息。息。a1a2a3a4a5a6有序对在计算机中有两种表示方法：顺序映像和链式映像有序对在计算机中有两种表示方法：顺序映像和链式映像第18页，共49页，编辑于2022年，星期六（a1,a2,a3a1,a2,a3）a1a2a3第19页，共49页，编辑于2022年，星期六链式映像链式映像n又称非顺序映像，在整个结构中又称非顺序映像，在整个结构中x x和和y y的存储位置之的存储位置之间没有固定的关系，就是说它们的存储位置是随意间没有固定的关系，就是说它们的存储位置是随意的。的。n以附加信息以附加信息(指针指针)表示后继关系表示后继关系n需要用一个和需要用一个和x x在一起的附

13、加信息指示在一起的附加信息指示y y的存储位置。的存储位置。nx x元素的存储映像是一个结点，包含两部分信息，其中元素的存储映像是一个结点，包含两部分信息，其中一部分信息是数据元素一部分信息是数据元素x x，另一部分信息是指向后继元，另一部分信息是指向后继元素的指针。素的指针。yx第20页，共49页，编辑于2022年，星期六n在不同的编程环境中，存储结构有不同的描在不同的编程环境中，存储结构有不同的描述方法。述方法。n当用高级程序设计语言进行编程时，通常可当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。用高级编程语言中提供的数据类型描述之。n例如，以三个带有次序关系

14、的整数表示一个例如，以三个带有次序关系的整数表示一个长整数时，可利用长整数时，可利用C C语言中提供的整数数组类语言中提供的整数数组类型型,定义整数为：定义整数为：typedef int Long_int3typedef int Long_int3第21页，共49页，编辑于2022年，星期六三、数据类型三、数据类型n在用高级程序语言编写的程序中在用高级程序语言编写的程序中,必须对必须对程序中出现的每个变量、常量或表达式，程序中出现的每个变量、常量或表达式，明确说明他们所属的数据类型。明确说明他们所属的数据类型。n每个类型明显或者隐含的规定了在程序制每个类型明显或者隐含的规定了在程序制定期间它的

15、变量或者表达式所明确取值的定期间它的变量或者表达式所明确取值的范围以及允许进行的操作。范围以及允许进行的操作。n数据类型是一个值的集合和定义在此集合数据类型是一个值的集合和定义在此集合上的一组操作的总称。上的一组操作的总称。第22页，共49页，编辑于2022年，星期六抽象数据类型抽象数据类型(Abstract Data Type,(Abstract Data Type,简称简称ADT)ADT)n是指一个数学模型以及定义在此数学模型上的一组操作。是指一个数学模型以及定义在此数学模型上的一组操作。nADTADT有两个重要特征：有两个重要特征：数据抽象数据抽象 用用ADTADT描述程序处理的实体时，

16、强调的是其本质的特描述程序处理的实体时，强调的是其本质的特征，其所能完成的功能以及它和外部用户的接口征，其所能完成的功能以及它和外部用户的接口(即即外界使用它的方法外界使用它的方法)数据封装数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现规范。户隐藏其内部实现规范。第23页，共49页，编辑于2022年，星期六n例如，抽象数据类型复数的定义例如，抽象数据类型复数的定义 ADT ComplexADT Complex 数据对象数据对象：D=e1,e2|e1,e2RealSetD=e1,e2|e1,e2RealSet 数据关

17、系数据关系:R1=|e1:R1=|e1是复数的实数部分，是复数的实数部分，e2e2是复数的虚数部分是复数的虚数部分 基本操作：基本操作：InitComplexInitComplex（&Z,v1,v2&Z,v1,v2）操作结果：构造复数操作结果：构造复数Z,Z,其实部和虚部分别被赋以其实部和虚部分别被赋以参数参数v1v1和和v2v2的值的值 DestroyComplexDestroyComplex（&Z&Z）操作结果：复数操作结果：复数Z Z被销毁被销毁 第24页，共49页，编辑于2022年，星期六GetRealGetReal（Z Z，&realPart&realPart）初始条件：复数已存在初

18、始条件：复数已存在操作结果：用操作结果：用realPartrealPart返回复数返回复数Z Z的实部的实部GetImageGetImage（Z,&ImagPartZ,&ImagPart）初始条件：复数已存在初始条件：复数已存在操作结果：用操作结果：用ImagPartImagPart返回复数返回复数Z Z的实部的实部Add(z1,z2,&sum)Add(z1,z2,&sum)初始条件：初始条件：z1,z2z1,z2是复数是复数操作结果：用操作结果：用sumsum返回两个复数返回两个复数z1,z2z1,z2的和值的和值ADT ComplexADT Complex假设：假设：z1,z2z1,z2是

19、上述定义的复数，则是上述定义的复数，则Add(z1,z2,z3)Add(z1,z2,z3)操操作的结果将得到作的结果将得到第25页，共49页，编辑于2022年，星期六抽象数据类型的描述方法抽象数据类型的描述方法n抽象数据类型可用抽象数据类型可用(D,S,P)(D,S,P)三元组表示三元组表示n其中，其中，D D是数据对象是数据对象n S S是是D D上的关系集上的关系集n P P是对是对D D的基本操作集的基本操作集第26页，共49页，编辑于2022年，星期六1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现n抽象数据类型需要通过固有数据类型抽象数据类型需要通过固有数据类型(高高

20、级编程语言中已实现的数据类型级编程语言中已实现的数据类型)来实现。来实现。第27页，共49页，编辑于2022年，星期六1.4 1.4 算法和算法分析算法和算法分析一、算法一、算法 算法是为了解决某类问题而规定的一个算法是为了解决某类问题而规定的一个有限长的操作序列。有限长的操作序列。一个算法必须满足以下五个重要特性：一个算法必须满足以下五个重要特性：1 1、有穷性、有穷性 2 2、确定性、确定性 3 3、可行性、可行性 4 4、有输入、有输入 5 5、有输出、有输出第28页，共49页，编辑于2022年，星期六1 1、有穷性、有穷性 对于任意一组合法输入值，在执行对于任意一组合法输入值，在执行有

21、穷步骤有穷步骤之后一定能结之后一定能结束，即束，即:算法中的每个步骤都能在算法中的每个步骤都能在有限时间有限时间内完成；内完成；2 2、确定性、确定性 对于对于每种情况每种情况下所应执行的操作，在算法中都有下所应执行的操作，在算法中都有明确明确的规定，使算法的执行者或阅读者能明确其含义及的规定，使算法的执行者或阅读者能明确其含义及如何执行，并且在任何条件下，算法都只有一条执如何执行，并且在任何条件下，算法都只有一条执行路径；行路径；第29页，共49页，编辑于2022年，星期六3 3、可行性、可行性 算法中的所有操作都必须算法中的所有操作都必须足够基本足够基本，都可以通过已经实，都可以通过已经实

22、现的基本操作运算有限次实现之；现的基本操作运算有限次实现之；4 4、有输入、有输入 作为算法加工对象的量值，通常体现为算法中的一作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入而有的算法表面上可以没有输入，实际上已被嵌入算法之中；算法之中；5 5、有输出、有输出 它是一组与它是一组与“输入输入”有确定关系的量值，是算法进行有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功信息加工后得到的结果，这种确定关系即为算法的功能。能。第30页，共49页，

23、编辑于2022年，星期六作业作业n描述算法的特征。描述算法的特征。第31页，共49页，编辑于2022年，星期六课前复习课前复习n数据数据 所有能被输入到计算机中，并被计算机处理的所有这些符号的集合，所有能被输入到计算机中，并被计算机处理的所有这些符号的集合，n数据元素数据元素 数据中的一个数据中的一个“个体个体”，数据结构中讨论的基本单位。，数据结构中讨论的基本单位。n数据项数据项 数据结构中讨论的最小单位，数据元素是数据项的集合数据结构中讨论的最小单位，数据元素是数据项的集合n数据对象数据对象 是性质相同的数据元素的集合是性质相同的数据元素的集合,是数据的一个子集是数据的一个子集n数据结构数

24、据结构 是带结构的数据元素的集合是带结构的数据元素的集合n数据的逻辑结构可以归结为以下四类：数据的逻辑结构可以归结为以下四类：(1)(1)线性结构线性结构 (2)(2)树形结构树形结构 (3)(3)图状结构图状结构(网状结构网状结构)(4)(4)集合结构集合结构n数据结构是一个二元组数据结构是一个二元组 Date_Structures=(D,S)Date_Structures=(D,S)其中其中D D是数据元素的有限集，是数据元素的有限集，S S是是D D上关系的有限集。上关系的有限集。n抽象数据类型可用抽象数据类型可用(D,S,P)(D,S,P)三元组表示三元组表示n其中，其中，D D是数据

25、对象是数据对象 S S是是D D上的关系集上的关系集 P P是对是对D D的基本操作集的基本操作集算法满足五个特性：算法满足五个特性：1 1、有穷性、有穷性 2 2、确定性、确定性 3 3、可行性、可行性 4 4、有输入、有输入 5 5、有输出、有输出第32页，共49页，编辑于2022年，星期六二、算法设计的原则二、算法设计的原则设计算法时，通常应考虑达到以下目标：设计算法时，通常应考虑达到以下目标：1 1、正确性、正确性2 2、可读性、可读性3 3、健壮性、健壮性4 4、高效率与低存储量需求、高效率与低存储量需求第33页，共49页，编辑于2022年，星期六1 1、正确性、正确性n首先，算法应

26、当满足以特定的首先，算法应当满足以特定的“规格说明规格说明”方式方式给出的需求。给出的需求。n其次，对算法是否其次，对算法是否“正确正确”的理解可以有以下四个的理解可以有以下四个层次：层次：a.a.程序中不含语法错误；程序中不含语法错误；b.b.程序对于几组输入数据能够得出满足要程序对于几组输入数据能够得出满足要 求的结果；求的结果；c.c.程序对于精心选择的、典型、苛刻且带有刁难程序对于精心选择的、典型、苛刻且带有刁难 性的几组输入数据能够得出满足要求的结果。性的几组输入数据能够得出满足要求的结果。d.d.程序对于一切合法的输入数据都能得出满足要程序对于一切合法的输入数据都能得出满足要 求的

27、结果。求的结果。第34页，共49页，编辑于2022年，星期六2 2、可读性、可读性n算法主要是为了人的阅读与交流，其次才是为计算算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；机执行。因此算法应该易于人的理解；n另一方面，晦涩难懂的程序易于隐藏较多错误而难以另一方面，晦涩难懂的程序易于隐藏较多错误而难以调试。调试。第35页，共49页，编辑于2022年，星期六3 3、健壮性、健壮性n当当输入的数据非法输入的数据非法时，算法应当恰当的做出反映或时，算法应当恰当的做出反映或进行相应进行相应处理处理，而不是产生莫名其妙的输出结果。并且，处理出，而不是产生莫名其妙的输出结果

28、。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以使在更高的抽象层次上进行处错误或错误性质的值，以使在更高的抽象层次上进行处理。理。第36页，共49页，编辑于2022年，星期六4 4、高效率和低存储量需求、高效率和低存储量需求n通常算法的效率指的是算法执行的时间，通常算法的效率指的是算法执行的时间，存储量指的是算法执行过程中所需要的存储量指的是算法执行过程中所需要的最大存储空间，两者都和问题的规模有最大存储空间，两者都和问题的规模有关。关。第37页，共49页，编辑于2022年，星期六三、算法效率的衡量方法和准则三

29、、算法效率的衡量方法和准则 通常有两种衡量算法效率的方法：通常有两种衡量算法效率的方法：事后统计法事后统计法 缺点：缺点：1 1、必须执行程序、必须执行程序 2 2、其它因素掩盖算法本质、其它因素掩盖算法本质 事先分析估算法事先分析估算法 和算法执行时间有关的因素：和算法执行时间有关的因素：1 1、算法选用的策略、算法选用的策略2 2、问题的规模、问题的规模3 3、编写程序的语言、编写程序的语言4 4、编译程序产生的机器代码的质量、编译程序产生的机器代码的质量5 5、计算机执行指令的速度、计算机执行指令的速度第38页，共49页，编辑于2022年，星期六n一个特定算法的一个特定算法的“运行工作量

30、运行工作量”的大小，的大小，只依赖于问题的规模只依赖于问题的规模(通常用整数通常用整数n n表示表示)，或者说，它是问题规模的函数。，或者说，它是问题规模的函数。第39页，共49页，编辑于2022年，星期六n假如，随着问题规模假如，随着问题规模n n的增长，算法执行的增长，算法执行时间时间T(n)T(n)的增长率和的增长率和f(n)f(n)的增长率相同，的增长率相同，则可记为：则可记为：T(n)=O(f(n)T(n)=O(f(n)称称T(n)T(n)为算法的为算法的(渐进渐进)时间复杂度时间复杂度。第40页，共49页，编辑于2022年，星期六n算法算法=控制结构控制结构+原操作原操作 （固有数

31、据类型的操作）（固有数据类型的操作）n算法的执行时间算法的执行时间=原操作原操作(i)(i)的执行次数的执行次数每个原操作每个原操作(i)(i)的执行时间的执行时间 算法的执行时间与原操作的执行次数之和成正比算法的执行时间与原操作的执行次数之和成正比 从算法中选取一种对于所研究的问题来说是从算法中选取一种对于所研究的问题来说是基本操作基本操作的原操作，以该基本操作的原操作，以该基本操作在算法中重复执行的次数在算法中重复执行的次数作作为算法运行时间的衡量准则。为算法运行时间的衡量准则。第41页，共49页，编辑于2022年，星期六例一 for(i=1;i=n;+i)for(i=1;i=n;+i)f

32、or(j=1;j=n;+j)for(j=1;j=n;+j)ci,j=0;ci,j=0;for(k=1;k=n;+k)for(k=1;k=n;+k)ci,j+=ai,k*bk,j;ci,j+=ai,k*bk,j;基本操作：乘法操作基本操作：乘法操作基本操作：乘法操作基本操作：乘法操作 时间复杂度：时间复杂度：O O（n n3 3）第42页，共49页，编辑于2022年，星期六例二例二 void select_sort(int a,int n)void select_sort(int a,int n)/将将a a中整数序列重新排列成自小到大有序的整数序列中整数序列重新排列成自小到大有序的整数序列 f

33、or(i=0;in-1;+i)for(i=0;in-1;+i)j=i;j=i;for(k=i+1;kn;+k)for(k=i+1;kn;+k)if(akaj)j=k;if(ak1&change;-i)for(i=n-1,change=TRUE;i1&change;-i)change=FALSE;change=FALSE;for(j=0;j=i;+j)for(j=0;jaj+1)if(ajaj+1)ajaj+1;ajaj+1;change=TRUE;change=TRUE;/bubble_sort/bubble_sort基本操作：赋值操作基本操作：赋值操作基本操作：赋值操作基本操作：赋值操作时间

34、复杂度：时间复杂度：O O（n n2 2）第44页，共49页，编辑于2022年，星期六四、算法的存储空间需求四、算法的存储空间需求算法的空间复杂度算法的空间复杂度 S(n)=O(g(n)S(n)=O(g(n)表示随着问题规模表示随着问题规模n n的增大，算法运行所需的增大，算法运行所需存储量的增长率与存储量的增长率与g(n)g(n)的增长率相同。的增长率相同。第45页，共49页，编辑于2022年，星期六算法的存储量包括：算法的存储量包括：1 1、输入数据所占空间、输入数据所占空间 2 2、程序本身所占空间、程序本身所占空间 3 3、辅助变量所占空间、辅助变量所占空间 若输入数据所占空间只取决于

35、问题本若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。和程序之外的辅助变量所占额外空间。第46页，共49页，编辑于2022年，星期六例三例三void bubble_sort(int a,int n)void bubble_sort(int a,int n)/将将a a中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列 for(i=n-1,change=TRUE;i1&change;-i)for(i=n-1,change=TRUE;i1&change;-i)change=FAL

36、SE;change=FALSE;for(j=0;j=i;+j)for(j=0;jaj+1)ajaj+1;if(ajaj+1)ajaj+1;change=TRUE;change=TRUE;/bubble_sort/bubble_sort 空间复杂度：空间复杂度：空间复杂度：空间复杂度：O O O O（1 1 1 1）第47页，共49页，编辑于2022年，星期六n若所需额外空间相对于输入数据量来说是若所需额外空间相对于输入数据量来说是常数的话，则称此算法为原地工作。常数的话，则称此算法为原地工作。n 若所需存储量依赖于特定的输入，则通若所需存储量依赖于特定的输入，则通常按最坏情况考虑。常按最坏情况考虑。第48页，共49页，编辑于2022年，星期六本章学习要点n熟悉各名词、术语的含义，掌握基本概熟悉各名词、术语的含义，掌握基本概念。念。n理解算法五个要素的确切含义理解算法五个要素的确切含义n掌握计算语句频度和估算算法时间复杂掌握计算语句频度和估算算法时间复杂度的方法度的方法第49页，共49页，编辑于2022年，星期六