数据结构与算法第1节概述.ppt

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