数据结构与算法概述概要课件

第第第第2 2章章章章 数据结构与算法数据结构与算法数据结构与算法数据结构与算法一、数据结构讨论与研究的范畴一、数据结构讨论与研究的范畴二、算法二、算法第第1节节 概述概述1学习内容与要求学习内容与要求学习内容与要求学习内容与要求学习和了解数据结构所研究的内容；掌握学习和了解数据结构所研究的内容；掌握数据的逻辑结构和存储结构的定义和基本数据的逻辑结构和存储结构的定义和基本分类；分类；学习和掌握与数据结构有关的名词术语学习和掌握与数据结构有关的名词术语（如数据、数据元素、数据对象、数据类（如数据、数据元素、数据对象、数据类型、抽象数据类型型、抽象数据类型ADT等等）；等等）；学习和了解算法的概念、特点以及算法的学习和了解算法的概念、特点以及算法的评价标准。评价标准。2Data Structures+Algorithms=ProgramsNicklaus Wirth程程 序序:数据结构数据结构:算法算法:利用计算机语言编制的一组利用计算机语言编制的一组具有确定功能的指令集合。具有确定功能的指令集合。处理问题的策略。处理问题的策略。问题或对象的数学模型问题或对象的数学模型(如如何描述数据的外部表现形式何描述数据的外部表现形式和内部存储结构和内部存储结构)。3一、数据结构一、数据结构研究和讨论的范畴研究和讨论的范畴4“学生学生”数据数据1234567895“课程课程”数据数据6“选课选课”数据数据学号课程编号成绩时间981640240028206.6.10981640240169006.6.15981650240028506.6.10981650240167606.6.15981650240248906.6.139816598164024016024002024024学生学生课程课程7学生学生(学号学号,姓名姓名,性别性别,籍贯籍贯)课程课程(课程号课程号,课程名课程名,学分学分)选课选课(学号学号,课程号课程号,成绩成绩)“选课选课”数据包含如下信息数据包含如下信息:学号学号 课程编号课程编号 成绩成绩 时间时间 学生选课系统中学生选课系统中“学生学生”和和“课程课程”这两个这两个实体构成了网状（图状）关系（即实体构成了网状（图状）关系（即“选课选课”关关系）。系）。8UNIXUNIX文件系统的系统结构图文件系统的系统结构图/(root)binlibuseretcmathdsswlintaoxieStack.cppQueue.cppTree.cpp9数据结构的研究内容数据结构的研究内容 综合上述例子可见，描述这类非数综合上述例子可见，描述这类非数值计算问题的数学模型不再是数学方程，值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。而是诸如表、树和图之类的数据结构。简单地说，作为一门学科，数据结构简单地说，作为一门学科，数据结构主要研究主要研究非数值计算的程序设计问题非数值计算的程序设计问题当中当中计算机的计算机的操作对象操作对象（数据）（数据）以及它们之间以及它们之间的的关系关系（逻辑结构和物理结构）（逻辑结构和物理结构）和和操作操作（算法实现）（算法实现）。10若干名词术语若干名词术语数据（数据（data）数据元素（数据元素（data element）数据项（数据项（data item）数据对象（数据对象（data object）数据结构（数据结构（data structure）数据类型（数据类型（data type）抽象数据类型（抽象数据类型（ADT）11数据（数据（data）n数据数据是信息的载体，是描述客观是信息的载体，是描述客观事物的事物的数、字符数、字符以及所有能输入以及所有能输入到计算机中、被计算机程序识别到计算机中、被计算机程序识别和处理的和处理的符号的集合符号的集合。u 数值性数据数值性数据u 非数值性数据非数值性数据12数据元素数据元素(data element)和和数据项（数据项（data item）数据元素数据元素是数据的是数据的基本单位基本单位。在计算。在计算机程序中常作为一个整体进行考虑和机程序中常作为一个整体进行考虑和处理。数据元素又可称为处理。数据元素又可称为元素、结点、元素、结点、记录记录。有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项（data item）组成。）组成。数据项数据项是是具有具有独立含义的最小标识单位。独立含义的最小标识单位。13数据对象数据对象(data object)具有相同性质的数据成员（数据具有相同性质的数据成员（数据元素）的集合，数据的子集元素）的集合，数据的子集。例：。例：u整数数据对象整数数据对象 N=0,1,2,u学生数据对象学生数据对象有穷集和无穷集有穷集和无穷集14什么是数据结构什么是数据结构定义定义:由某一由某一数据对象数据对象及该对象中所有数据及该对象中所有数据成员之间的成员之间的关系关系组成。组成。n与与“数据对象数据对象”这一概念的区别？这一概念的区别？n作为术语名词和作为学科名词的区别？作为术语名词和作为学科名词的区别？15n数据元素间的逻辑关系，即数据元素间的逻辑关系，即数据的数据的逻辑结构逻辑结构。n数据元素及其关系在计算机存储内数据元素及其关系在计算机存储内的表示，即的表示，即数据的存储表示数据的存储表示（物理结（物理结构、物理表示）。构、物理表示）。n数据的运算，即数据的运算，即对数据元素施加的对数据元素施加的操作操作。作为学科，数据结构研究数据的组织作为学科，数据结构研究数据的组织形式，包括以下内容：形式，包括以下内容：16数据的逻辑结构数据的逻辑结构n数据的逻辑结构数据的逻辑结构从数据的逻辑关系从数据的逻辑关系上描述数据上描述数据，与数据的存储无关，与数据的存储无关，与数据元素本身的具体形式、内容与数据元素本身的具体形式、内容无关。无关。n数据的逻辑结构可以看作是从具体数据的逻辑结构可以看作是从具体问题抽象出来问题抽象出来的数据模型。的数据模型。17数据的数据的逻辑结构逻辑结构可归结为以下可归结为以下四类：四类：线性线性结构：一对一关系树形树形结构：一对多关系图状图状结构：多对多关系集合集合结构：简单隶属关系18数据逻辑结构的描述方式数据逻辑结构的描述方式 Data_Structure=D,R 其中，其中，D 是某一数据对象，是某一数据对象，R 是该对象中是该对象中所有数据成员之间的关系的有限集合。一般表所有数据成员之间的关系的有限集合。一般表现形式如下：现形式如下：D=d1,d2,dnR=r1,r2,rm关键字关键字：数据元素中可用于标识该数据元素的数据元素中可用于标识该数据元素的某个分量（数据项）。通常用关键字区别不同某个分量（数据项）。通常用关键字区别不同的数据元素。的数据元素。19D01,02,03,04,05,06,07,08,09,10R1=,R2=,R3=,20R1=,t用连线表示数据元素之间的联系用连线表示数据元素之间的联系21R2=,22R3=,23n由上述数据结构的描述可得出结论：相由上述数据结构的描述可得出结论：相同数据元素的集合（即同一数据对象），同数据元素的集合（即同一数据对象），因其关系的不同而构成不同的数据逻辑结因其关系的不同而构成不同的数据逻辑结构。构。n对一实际应用问题，合理选择数据逻辑对一实际应用问题，合理选择数据逻辑结构才能够设计出有效的算法。结构才能够设计出有效的算法。例：根据下列选课情况安排考试日程，使得在不冲突的例：根据下列选课情况安排考试日程，使得在不冲突的情况下用尽可能短的时间安排所有考试。情况下用尽可能短的时间安排所有考试。学生姓名学生姓名选修课选修课1选修课选修课2选修课选修课3甲甲ABC乙乙DE丙丙DCF丁丁EFA戊戊BF24数据的存储结构n数据的存储结构是数据在计算机内部数据的存储结构是数据在计算机内部的存储方式，依赖于计算机语言。的存储方式，依赖于计算机语言。n存储结构分类存储结构分类u 顺序存储结构顺序存储结构u 链式存储结构链式存储结构u 索引结构索引结构u 散列结构散列结构25顺序存储（矢量存储）结构顺序存储（矢量存储）结构Contiguous implementation（vector implementation）所有元素存放在一片连续的存储单元中，逻辑上所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存中其存储地址仍然相邻。相邻的元素存放到计算机内存中其存储地址仍然相邻。链式存储结构链式存储结构Linked implementation 所有元素可以存放在不连续的存储单元中，元所有元素可以存放在不连续的存储单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后其存储地址不一定是相邻的。放到计算机内存后其存储地址不一定是相邻的。26顺序和链式存储结构示意图顺序和链式存储结构示意图27数据类型数据类型n 数据类型数据类型定义：定义：一组性质相同的值的集合一组性质相同的值的集合,以及定义以及定义于这个值集合上的一组操作的总称。于这个值集合上的一组操作的总称。n C C语言中的数据类型语言中的数据类型 char int float double void char int float double void 字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 n基本数据类型（原子类型）：可以看作是计基本数据类型（原子类型）：可以看作是计算机中程序设计语言已实现的数据结构。算机中程序设计语言已实现的数据结构。n构造型数据类型：由相同或不同成分的类型构造型数据类型：由相同或不同成分的类型构成，如数组、结构体、类等。构成，如数组、结构体、类等。28抽象数据类型抽象数据类型(ADTs:Abstract Data Types)u由用户定义，用以表示实际应由用户定义，用以表示实际应用问题的用问题的数据模型。数据模型。u由由基本的数据类型基本的数据类型组成组成,并包并包括括一组相关的服务一组相关的服务（或称操作）。（或称操作）。29抽象数据类型的描述方法抽象数据类型的描述方法n抽象数据类型从形式上可用抽象数据类型从形式上可用（D，R，O）三元组表示。其中：三元组表示。其中：D是数据对象，是数据对象，R是是D上上的关系集，的关系集，O是对是对D的基本操作集的基本操作集 。一般采用如下格式描述一般采用如下格式描述ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名30ADT基本操作的定义格式基本操作的定义格式基本操作名（基本操作名（参数表参数表）初始条件初始条件：初始条件描述：初始条件描述 操作结果操作结果：操作结果描述：操作结果描述 u参数：参数：赋值参数赋值参数只为操作提供输入值只为操作提供输入值;引用参数引用参数以以&打头，除可提供输入值外，还将返回操作结果。打头，除可提供输入值外，还将返回操作结果。u初始条件：初始条件：描述操作执行之前数据结构和参数应满描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错足的条件，若不满足，则操作失败，并返回相应出错信息信息。若初始条件为空若初始条件为空,则省略之。则省略之。u操作结果操作结果：说明操作正常完成之后，数据结构的说明操作正常完成之后，数据结构的变化状况和应返回的结果。变化状况和应返回的结果。31例如，抽象数据类型例如，抽象数据类型“复数复数”的定的定义：义：数据对象：数据对象：De1,e2RealSet 数据关系：数据关系：R1|e1是复数的实数部分，是复数的实数部分，e2 是复数的虚数部分是复数的虚数部分 ADT Complex 32基本操作：基本操作：AssignComplex(&Z,v1,v2)操作结果：操作结果：构造一个复数构造一个复数 Z Z，其实部和虚，其实部和虚部分别被赋以参数部分别被赋以参数v1v1和和v2v2的值。的值。DestroyComplex(&Z)操作结果：操作结果：复数复数Z Z被销毁。被销毁。GetReal(Z,&realPart)初始条件：初始条件：复数已存在。复数已存在。操作结果：操作结果：用用realPart返回复数返回复数Z Z的实部值。的实部值。33 GetImag(Z,&ImagPart)初始条件：初始条件：复数已存在。复数已存在。操作结果：操作结果：用用ImagPart返回复数返回复数Z Z的虚部的虚部值。值。Add(z1,z2,&sum)初始条件：初始条件：z1,z2是复数。是复数。操作结果：操作结果：用用sum返回两个复数返回两个复数z1,z2的和的和值值。ADT Complex34抽象数据类型的实现抽象数据类型的实现 抽象数据类型描述的是抽象的数据模型及抽象数据类型描述的是抽象的数据模型及其操作，需要通过固有数据类型其操作，需要通过固有数据类型(高级编程语高级编程语言中已实现的数据类型言中已实现的数据类型)来实现。来实现。引入抽象数据类型的意义引入抽象数据类型的意义 通常研究一个数据结构的实现问题可以从研通常研究一个数据结构的实现问题可以从研究其抽象数据类型着手，例如通过对抽象数据究其抽象数据类型着手，例如通过对抽象数据类型的加工来用类型的加工来用C+类实现该数据结构：类的类实现该数据结构：类的数据成员对应于数据成员对应于ADT所描述的数据结构，类所描述的数据结构，类的方法对应于的方法对应于ADT所描述的操作。所描述的操作。35二、算法二、算法36关于算法关于算法 算法是为了解决某类问题而设算法是为了解决某类问题而设计的一个有限长的操作序列。计的一个有限长的操作序列。算法特性算法特性有穷性、确定性、可行性、有穷性、确定性、可行性、有输入、有输出有输入、有输出37有穷性有穷性：对于任意一组合法输入值，在执行对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即：算法中的每之后一定能结束，即：算法中的每个步骤都能在个步骤都能在有限时间有限时间内完成。内完成。确定性：确定性：对于对于每种情况每种情况下所应执行的操作，下所应执行的操作，在算法中都有在算法中都有确切确切的规定，使算法的执行者的规定，使算法的执行者或阅读者都能明确其含义及如何执行；并且或阅读者都能明确其含义及如何执行；并且在任何条件下，算法都只有一条执行路径。在任何条件下，算法都只有一条执行路径。可行性：可行性：算法中的所有操作都必须算法中的所有操作都必须足够基本足够基本，都可以通过已经实现的基本操作运算都可以通过已经实现的基本操作运算有限次有限次实现之。实现之。38有输入：有输入：作为算法加工对象的量值，通常作为算法加工对象的量值，通常体现为算法中的一组体现为算法中的一组变量变量。有些。有些输入量输入量需需要在算法执行过程中输入，而有的算法表要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上输入已被面上可以没有输入，实际上输入已被嵌入嵌入算法之中。算法之中。有输出：有输出：它是一组与它是一组与“输入输入”有确定关系有确定关系的量值，是算法进行信息加工后得到的的量值，是算法进行信息加工后得到的结结果果，这种确定关系即为算法的，这种确定关系即为算法的功能。功能。39用自然语言描述算法用自然语言描述算法：用我们日常生活中的自然语用我们日常生活中的自然语言也可以描述算法。言也可以描述算法。算法描述方法算法描述方法用流程图描述算法：用流程图描述算法：一个算法可以用流程图的方式一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。好方法，目前在一些高级语言程序设计中仍然采用。用其它方式描述算法：用其它方式描述算法：我们还可以用数学语言或约我们还可以用数学语言或约定的符号语言（如伪代码）来描述算法。定的符号语言（如伪代码）来描述算法。用用C+描述算法：描述算法：在本课程中，我们将采用在本课程中，我们将采用C+来描来描述算法，所有算法的描述都用述算法，所有算法的描述都用C+中的函数形式。中的函数形式。40算法和程序的关系算法和程序的关系l 算法算法程序！程序！算算法法着着重重体体现现思思路路和和方方法法，程程序序着着重重体体现计算机的实现。现计算机的实现。程程序序不不一一定定满满足足有有穷穷性性（例例如如死死循循环环情情形形）；另另外外，程程序序中中的的指指令令必必须须是是机机器器可可执行的，算法中的指令无此限制。执行的，算法中的指令无此限制。算法用计算机语言来书写时才是程序。算法用计算机语言来书写时才是程序。41算法设计原则算法设计原则正确性正确性可读性可读性健壮性健壮性高效率高效率低需求低需求算法评价标准算法评价标准时间特性：时间复杂度时间特性：时间复杂度T(n)空间特性：空间复杂度空间特性：空间复杂度S(n)算法设计原则与评价标准算法设计原则与评价标准42 一个特定算法的运行时间由其一个特定算法的运行时间由其“运行工作量运行工作量”决定。其运行工作量的大小，通常只依赖于决定。其运行工作量的大小，通常只依赖于问问题的规模题的规模（通常由问题涉及的数据量决定，用整（通常由问题涉及的数据量决定，用整数量数量n表示），或者说，表示），或者说，它是问题规模的函数它是问题规模的函数。算法的运行时间算法的运行时间 假如，随着假如，随着问题规模问题规模 n 的增长，算法执行时间的增长，算法执行时间的增长率和函数的增长率和函数 f(n)的增长率相同，则可记作：的增长率相同，则可记作：T(n)=O(f(n)称称T(n)为算法的为算法的时间复杂度。时间复杂度。43程序执行时间的计算程序执行时间的计算程序执行时间的计算程序执行时间的计算n事后统计法事后统计法n事前分析估算法事前分析估算法u算法策略算法策略u问题规模问题规模u程序设计语言程序设计语言u机器代码运行效率机器代码运行效率u机器执行指令的速度机器执行指令的速度44如何估算算法的时间复杂度？如何估算算法的时间复杂度？算法算法=控制结构控制结构+基本操作基本操作(基本数据类型的操作)算法的执行时间算法的执行时间=基本操作的执行次数基本操作的执行次数基本操作的执行时间基本操作的执行时间算法的执行时间算法的执行时间 与与 基本操作执行次数之和基本操作执行次数之和 成正比成正比。l 从算法中选取一种对于所研究的问题来说是从算法中选取一种对于所研究的问题来说是基本基本操作操作的操作，以该基本操作的操作，以该基本操作在算法中重复执行的次数在算法中重复执行的次数作为算法运行时间的衡量准则。作为算法运行时间的衡量准则。45例例一一两两个个矩矩阵阵相相乘乘void mult(int a,int b,int&c)/以二维数组存储矩阵元素，以二维数组存储矩阵元素，c 为为 a 和和 b 的乘积的乘积 for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=1;k=n;+k)ci,j+=ai,k*bk,j;/for/mult基本操作基本操作:乘法操作乘法操作时间复杂度时间复杂度:O(n3)46例例二二选选择择排排序序 void select_sort(int&a,int n)/将将 a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列 /select_sort基本操作基本操作:数据比较操作数据比较操作时间复杂度时间复杂度:O(n2)for(i=0;i n-1;+i)if(j!=i)aj aij=i;/选择第选择第 i 个最小元素个最小元素for(k=i+1;k n;+k)if(ak 1&change;-i)/冒泡排序冒泡排序基本操作基本操作:赋值操作赋值操作时间复杂度时间复杂度:O(n2)change=FALSE;/change 为元素进行交换标志为元素进行交换标志 for(j=0;j aj+1)aj aj+1;change=TRUE;/一趟冒泡排序一趟冒泡排序4849写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日