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