1、数据结构2020.2第1章 数据结构与算法基础为什么要学数据结构如何学好数据结构数据结构的概念算法和算法分析习题0102030405目录目录本章要点本章要点 掌握数据结构的掌握数据结构的学习学习方法方法 掌握数据结构掌握数据结构基本概念基本概念 掌握掌握算法时间复杂度算法时间复杂度的分析方法的分析方法 基本准备，初识数据与结构基本准备，初识数据与结构1 1.1.1l 数据结构数据结构=数据数据+结构结构l 人们常说的大数据时代与信息时代，究竟什么是数据，什么是信息呢？人们常说的大数据时代与信息时代，究竟什么是数据，什么是信息呢？l 数据数据:数字、文字、图片、声音、视频数字、文字、图片、声音、
2、视频都是数据都是数据l 信息：信息：是对数据进行操作和分析之后得出的是对数据进行操作和分析之后得出的产物产物。l 数据结构数据结构 ：数据的数据的容器容器 ，装载数据达到最终的目的。，装载数据达到最终的目的。1.11.1初识数据与结构初识数据与结构数据结构的概念数据结构的概念1 1.2.21.21.2数据结构的概念数据结构的概念l 数据数据：一切可以被计算机所识别的一切可以被计算机所识别的文字符号图像音视频文字符号图像音视频等都属于等都属于数据因此数据因此数据是一个相当庞大、抽象和笼统的概念。数据是一个相当庞大、抽象和笼统的概念。l数据元素数据元素:是有一定意义数据的是有一定意义数据的基本单位
3、基本单位，作为，作为整体处理的单位。整体处理的单位。l数据项数据项:是数据的是数据的最小标识单位最小标识单位。一一个个记录记录可称为一个数据元素，一个可称为一个数据元素，一个字段字段就是就是一个数据项。一个数据项。l数据对象数据对象:是具有相同性质的是具有相同性质的数据元素数据元素的的集合集合，是数据的子集。，是数据的子集。l数据结构数据结构:相互之间存在一种或多种特定相互之间存在一种或多种特定关系关系的数据元素的的数据元素的集合集合。【例例 1-11-1】这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和C语言)组成。1.21.2数据结构的概念数据结构的概念1.21
4、.2数据结构的概念数据结构的概念数据结构的物理结构与逻辑结构数据结构的物理结构与逻辑结构物理结构物理结构:是数据元素在计算机中的表示和实现。是数据元素在计算机中的表示和实现。(实现层实现层)逻辑结构逻辑结构:是对数据元素之间的逻辑关系的描述。属于是对数据元素之间的逻辑关系的描述。属于用户用户视图视图，是是面向问题的面向问题的，反映，反映数据内部的构成方式。数据内部的构成方式。(抽象层抽象层)1.2.11.2.1数据的物理结构数据的物理结构物理结构物理结构(存储结构存储结构)是数据在计算机内部的存储实现是数据在计算机内部的存储实现，分为分为顺序存储顺序存储和和链式存储链式存储两种。两种。顺序存储
5、结构：顺序存储结构：数据元素按某种数据元素按某种顺序依此存放顺序依此存放在计算机存储在计算机存储器的连续存储单元中，器的连续存储单元中，其存储其存储的地址由起始地址和元素所占的地址由起始地址和元素所占的存储空间来决定的存储空间来决定 链式存储结构链式存储结构:把数据元素存放在把数据元素存放在任意任意的的存储单元里存储单元里，这，这组存储单元组存储单元可连续的可连续的，也，也可可不连续不连续的，的，因此需要因此需要用一个指用一个指针存放数据元素的地址，这样通过地址就针存放数据元素的地址，这样通过地址就可以找到可以找到相关联相关联数据元素的位置数据元素的位置 1.2.11.2.1数据的物理结构数据
6、的物理结构顺序存储顺序存储S 是是起始地址起始地址，H 是每个元素是每个元素所占的空间所占的空间则第则第 i 个元素的存储地址为个元素的存储地址为:Loc(i)=Loc(1)+(i-1)*H=S+(i-1)*H 1.2.11.2.1数据的物理结构数据的物理结构顺序存储顺序存储顺序存储结构的顺序存储结构的主要特点主要特点:结点中只有自身结点中只有自身数据域数据域。因此存储密度大，。因此存储密度大，利用率高。利用率高。可以通过计算确定数据结构中第可以通过计算确定数据结构中第 i i 个元素个元素的位置，可以的位置，可以(直接直接)随机存取随机存取。插入插入和和删除删除操作会引起操作会引起大量的元素
7、移动大量的元素移动 。必须存储在一片必须存储在一片地址连续地址连续的存储单元中的存储单元中 。1.2.11.2.1数据的物理结构数据的物理结构链式存储链式存储把把逻辑上逻辑上相邻相邻的元素存放的元素存放在在物理上物理上不相邻不相邻的存储单的存储单元中。元中。主要特点主要特点：有表示连接信息的有表示连接信息的指针域指针域。因此存储密度小，。因此存储密度小，利用率低利用率低。逻辑上逻辑上相邻相邻的结点在的结点在物理上物理上不一定邻接不一定邻接。插入插入和和删除删除操作操作灵活方便灵活方便;只要修改指针域只要修改指针域的值即可的值即可。可以存储在可以存储在不连续不连续的存储单元中。的存储单元中。1.
8、2.21.2.2数据的逻辑结构数据的逻辑结构数据的逻辑结构数据的逻辑结构是数据元素之间关系的描述，是数据元素之间关系的描述，可看作可看作是从具体问是从具体问题抽象出来的数学模型。题抽象出来的数学模型。与数据的存储无关与数据的存储无关，是独立于计算机的。，是独立于计算机的。通常逻辑结构有四类：通常逻辑结构有四类：集合结构集合结构:数据元素间的关系是数据元素间的关系是“属于同一个集合属于同一个集合”。集合是。集合是元素元素关系关系极为极为松散松散的一种结构。的一种结构。线性结构线性结构:该结构的数据元素之间存在着该结构的数据元素之间存在着一对一一对一的关系。的关系。1.2.21.2.2数据的逻辑结
9、构数据的逻辑结构树型结构树型结构:该结构的数据元素之间存在着该结构的数据元素之间存在着一对多一对多的关系。的关系。图形结构图形结构:该结构的数据元素之间存在着该结构的数据元素之间存在着多对多多对多的关系的关系，也也称作称作网状结构网状结构。1.2.21.2.2数据的逻辑结构数据的逻辑结构-举例说明举例说明线性数据结构树型数据结构图形数据结构1.2.31.2.3数据结构数据结构数据结构数据结构=数据数据+数据的数据的物理结构物理结构+数据的数据的逻辑结构逻辑结构 1.2.31.2.3数据类型与抽象数据类型数据类型与抽象数据类型数据类型数据类型是编程中对不同种类是编程中对不同种类 数据的一种分类与
10、定义数据的一种分类与定义。常见常见的数据类型有整型，浮点的数据类型有整型，浮点 型，字符型，布尔型等型，字符型，布尔型等 抽象数据类型抽象数据类型是用是用基本数据类型基本数据类型来描述事物的各个来描述事物的各个属性属性，再，再把把 所有所有属性当做一个属性当做一个整体整体来看待。来看待。数据结构的运算数据结构的运算插入插入、删除删除、更新更新、检索检索、排序排序加工型操作加工型操作:操作改变了存储结构的值。操作改变了存储结构的值。引用型操作引用型操作:操作只是查询或求得结点的值。操作只是查询或求得结点的值。为什么学习数据结构为什么学习数据结构1 1.3.31.31.3为什么要学习数据结构为什么
11、要学习数据结构数据结构数据结构是计算机科学与技术专业的是计算机科学与技术专业的专业基础专业基础课，是十分重要的课，是十分重要的核心核心课程。课程。所有的计算机所有的计算机系统软件系统软件和和应用软件应用软件都要用到各种类型的数据结构。都要用到各种类型的数据结构。要想要想有效地有效地使用计算机、充分发挥计算机的使用计算机、充分发挥计算机的性能性能，还必须学习和，还必须学习和掌握好数据结构的有关知识。掌握好数据结构的有关知识。如何学好数据结构如何学好数据结构1 1.4.41.41.4 如何学好数据结构如何学好数据结构(1(1)要求掌握要求掌握基本基本的的 C C 语言知识，语言知识，掌握掌握模块化
12、模块化程序设计程序设计的基本思的基本思想，能够想，能够利用利用 C C 语言熟练编写一些简单的程序。语言熟练编写一些简单的程序。(2)(2)在在学习时，首先要掌握各种学习时，首先要掌握各种基本的数据结构基本的数据结构，并对各种数据，并对各种数据结构的结构的逻辑结构逻辑结构和和物理结构物理结构有足够的认识。有足够的认识。(3)(3)对基于各种数据结构的常见的对基于各种数据结构的常见的操作及其算法操作及其算法要重点掌握，并要重点掌握，并要了解评价某个具体要了解评价某个具体算法算法优劣的方法。优劣的方法。(4)(4)多思考、多做练习题、多上机实践多思考、多做练习题、多上机实践。算法与算法分析基础算法
13、与算法分析基础1 1.5.51.51.5 算法和算法分析基础算法和算法分析基础数据结构数据结构+算法算法=编程编程 算法是描述解决问题的方法算法是描述解决问题的方法。在计算机中表现。在计算机中表现指令指令的有限序列。其的有限序列。其中每一条指令表示一个或多个操作中每一条指令表示一个或多个操作 1.5.11.5.1 算法特性算法特性(1)(1)有穷性有穷性：一个算法必须在：一个算法必须在有穷步之后结束有穷步之后结束，即有限即有限时间内完时间内完成。成。如计算机如计算机需要需要 30 30 年的时间才能结束，算法的意义就不大。年的时间才能结束，算法的意义就不大。(2)(2)确定性确定性：算法的每一
14、步必须有确切的定义，：算法的每一步必须有确切的定义，无二义性无二义性。相同。相同的输入仅有唯一的输出结果。的输入仅有唯一的输出结果。(3)(3)可行性可行性：算法中的每一步都可实现，即每一步都是：算法中的每一步都可实现，即每一步都是经过有限经过有限次数执行次数执行得以实现。得以实现。(4)(4)输入输入：一个算法具有：一个算法具有零个或多个输入零个或多个输入，可以没有输入。，可以没有输入。(5)(5)输出输出：一个算法具有：一个算法具有一个或多个输出一个或多个输出，至少有一个输出。，至少有一个输出。1.5.11.5.1 算法特性算法特性要设计一个要设计一个好好的算法通常要考虑以下的要求：的算法
15、通常要考虑以下的要求：(1)(1)正确性正确性：算法的：算法的执行结果执行结果应当应当满足满足预先规定的预先规定的功能和性能要求功能和性能要求。(2)(2)可读性可读性：一个算法应当思路清晰、层次分明、简单明了、：一个算法应当思路清晰、层次分明、简单明了、易读易懂易读易懂。(3)(3)健壮性健壮性(鲁棒性鲁棒性)：当：当输入不合法数据输入不合法数据时，应能作适当处理，不至引时，应能作适当处理，不至引起严重后果，陷入死机。起严重后果，陷入死机。(4)(4)高效率和低存储量高效率和低存储量：有效使用：有效使用存储空间存储空间和有较高的和有较高的时间效率时间效率。【例例1-5】求求n个数的最大值个数
16、的最大值。分析。分析健壮性健壮性main()int max=0,x;for(int i=1;imax)max=x;printf(“%d”,max);提示：本程序无语法错误，当输入全为正数时，结果正确；当输提示：本程序无语法错误，当输入全为正数时，结果正确；当输入全为负数时，求得的最大值为入全为负数时，求得的最大值为0，结果不正确。既要输入正确，结果不正确。既要输入正确的数据，也要输入错误的数据进行的数据，也要输入错误的数据进行健壮性健壮性测试。测试。1.5.21.5.2 算法性能分析与度量算法性能分析与度量评价一个算法主要看这个算法所评价一个算法主要看这个算法所占用机器资源占用机器资源的多少，
17、而这些的多少，而这些资源中资源中时间代价时间代价与与空间代价空间代价是两个主要的方面，通常是以算法是两个主要的方面，通常是以算法执行执行所需的机器所需的机器时间时间和所和所占用占用的的存储空间存储空间来判断一个算法的优来判断一个算法的优劣。劣。好的算法具备好的算法具备时间效率高时间效率高和和存储量低存储量低的特点。对同一问题，有的特点。对同一问题，有多个算法，多个算法，执行时间短执行时间短的效率高，存储量是指执行过程需要的的效率高，存储量是指执行过程需要的最少存储量最少存储量。1.5.21.5.2 算法性能分析与度量算法性能分析与度量（1）关于算法执行时间）关于算法执行时间一个一个算法的执行时
18、间算法的执行时间大致上等于大致上等于其所有语句执行时间的其所有语句执行时间的总和总和语句语句的执行时间的执行时间是是指指该语句该语句的的执行次数执行次数和执行和执行一次所需时间一次所需时间的的乘积乘积。两个算法的两个算法的第一条第一条、最后一条最后一条语句是语句是一样一样的，的，中间部分中间部分是要是要关注关注的，把循环当作一个整体，忽略头尾循环判断的次数，这两个算的，把循环当作一个整体，忽略头尾循环判断的次数，这两个算法的差别就是法的差别就是1与与n的区别。的区别。1.5.21.5.2 算法性能分析与度量算法性能分析与度量（2）时间复杂度）时间复杂度（Time Complexity）l 对于
19、对于算法分析，我们关心的是算法中语句算法分析，我们关心的是算法中语句总的执行总的执行次数次数T（n）是关）是关于于问题规模问题规模n的的函数函数。l T（n）随随n的的变化变化情况并确定情况并确定T（n）的）的数量级数量级。l 常用常用“大大O表示法表示法”表示：表示：T(n)=O(f(n)。l 它它表示随着表示随着问题问题的的规模规模n的的增大增大，算法执行时间算法执行时间的的增长率增长率和和f(n)的的增增长率长率相同，称作算法的相同，称作算法的渐近时间复杂度渐近时间复杂度，简称，简称时间复杂度时间复杂度。函数的渐近增长函数的渐近增长：两：两个函数个函数f(n)和和g(n)，如果存在一个整
20、数，如果存在一个整数N，使得对于所有的，使得对于所有的nN时，总有时，总有f(n)g(n)，称，称f(n)的增长渐近快于的增长渐近快于g(n)。如。如C算法、算法、D算法与算法与E算法。算法。1.5.21.5.2 算法性能分析与度量算法性能分析与度量当当n=1,2时，时，C算法不如算法不如D算法。但当算法。但当n2时时，C算法算法优于优于D算法。随算法。随n的增加，算法的增加，算法C比比D越来越好。于是我们可以说，当输入数据越来越好。于是我们可以说，当输入数据n，只要超过某一数值，只要超过某一数值N时，这个函数就总时，这个函数就总是大于另一函数，我们称是大于另一函数，我们称函数函数是是渐近增长
21、渐近增长的。的。当当n2时，即时，即N=3时，算法时，算法D与与E的渐近增长是相同的。都记为的渐近增长是相同的。都记为O（n2）。推导推导大大O阶阶的方法的方法1）程序运行时间中的）程序运行时间中的常数常数用用1代替代替。如运行。如运行3次，次，记记O(1),运行运行100次，也记次，也记为为O(1)。2）在大）在大O()函数函数中运行次数中运行次数只取最高阶项只取最高阶项，并且并且最高阶项的最高阶项的常数常数为为1。如。如5n2记记O(n2)。一般一般情况下，随情况下，随n的增大，的增大，T（n）的增长较慢的算法为最优的算法。）的增长较慢的算法为最优的算法。按大按大O阶推导方法：阶推导方法：
22、A算法算法f(n)=3,常数项常数项3次用次用1代替，记代替，记O(1)。B算法算法f(n)=2n+3，常数项，常数项3次用次用1代替，代替，2n的系数的系数2也改为也改为1，记，记O（n）C算法算法f(n)=C(3n+5)，记为，记为O（n）。）。D算法算法f(n)=(2n2)，记为，记为O(n2)。E算法算法f(n)=(2n2+3n+5),记为记为O(n2)。按最高项，其余忽略不计按最高项，其余忽略不计。1.5.21.5.2 算法性能分析与度量算法性能分析与度量【例【例1-6】在下列三段程序段中，给出原操作】在下列三段程序段中，给出原操作x=x+1的时间复杂度分析。的时间复杂度分析。（1）
23、x=x+1；程序执行程序执行1次，其时间复杂度为次，其时间复杂度为O(1)称为称为常量阶常量阶；（2）for(i=1;i=n;i+)/执行执行2n+2次次 x=x+1;/执行执行n次次程序共执行程序共执行3n+2,取最高项，去掉该项的系数，取最高项，去掉该项的系数，T(n)=O(n)，称为称为线性阶线性阶；（3）for(i=1;i=n;i+)/执行执行2n+2次次 for(j=1;j=n;j+)/执行执行n(2n+2)次次 x=x+1;/执行执行n2次次,程序共执行程序共执行3n2+4n+2,只取最高项，去掉该项的系数，只取最高项，去掉该项的系数，T(n)=O(n2),称为称为平方阶平方阶。常
24、见的时间复杂度：常见的时间复杂度：O(1)O(log2n)O(n)O(n2)O(n3)O(2n)1.5.21.5.2 算法性能分析与度量算法性能分析与度量 空间空间复杂复杂度度是是指程序运行从开始到结束所需的存储量。指程序运行从开始到结束所需的存储量。算法算法的存储空间需求，类似于算法的时间复杂度，为算法所需存储空的存储空间需求，类似于算法的时间复杂度，为算法所需存储空间的量度，记做：间的量度，记做：S(n)=O(f(n)其中其中n为问题的规模为问题的规模。一一个程序在机器上执行时，除了需要寄存本身所用的指令，常数，变个程序在机器上执行时，除了需要寄存本身所用的指令，常数，变量和输入数据以外，
25、还需要一些对量和输入数据以外，还需要一些对数据进行操作的辅助存储空间数据进行操作的辅助存储空间。其。其中对于中对于输入数据输入数据所占的具体所占的具体存储量存储量只取决于只取决于问题本身问题本身，与算法与算法无关无关。若若算法执行时所需要的算法执行时所需要的辅助空间辅助空间相对于相对于输入数据量输入数据量而言是个而言是个常数常数，则，则称这个算法为称这个算法为原地工作，辅助空间为原地工作，辅助空间为O(1)。算法的执行时间的耗费和所序的存储空间的耗费两者是矛盾的，难以算法的执行时间的耗费和所序的存储空间的耗费两者是矛盾的，难以兼得。兼得。即算法执行时间上的节省一定是以增加空间存储为代价的，反即
26、算法执行时间上的节省一定是以增加空间存储为代价的，反之亦然之亦然。常常常常以以算法执行时间算法执行时间做为做为算法优劣算法优劣的主要的主要衡量指标衡量指标。1.5.21.5.2 算法性能分析与度量算法性能分析与度量1.5.21.5.2 算法的大致分类算法的大致分类本本书涵盖的算法大致可以被分为书涵盖的算法大致可以被分为蛮力算法蛮力算法、分治算法分治算法、减治算法减治算法、变变治算法治算法以及以及动态规划算法动态规划算法等几大类。等几大类。蛮力法蛮力法(Brute Force):(Brute Force):直接解决问题直接解决问题的方法，不讲究任何策略，基于问的方法，不讲究任何策略，基于问题的描
27、述对结果题的描述对结果 进行枚举或暴力破解，因此也被称为穷举算法或枚举进行枚举或暴力破解，因此也被称为穷举算法或枚举算法。蛮力法属于最容易应用的算法，算法。蛮力法属于最容易应用的算法，因为其直接且没有策略，所以因为其直接且没有策略，所以简单，但是通常来讲简单，但是通常来讲时间复杂度较高时间复杂度较高，效率低下效率低下。蛮力法的典型算法。蛮力法的典型算法例如蛮力模式匹配算法等。例如蛮力模式匹配算法等。分分治法治法(Divide and Conquer):(Divide and Conquer):将复杂问题分解的方法，也就是俗称的将复杂问题分解的方法，也就是俗称的分而治之分而治之。将一。将一 个复
28、杂的问题分解成两个甚至更多的相同或相似的子个复杂的问题分解成两个甚至更多的相同或相似的子问题，使得解决复杂问题的目标变成问题，使得解决复杂问题的目标变成 解决多个简单的子问题。原来复解决多个简单的子问题。原来复杂问题的解就是多个子问题的解的合集。分治法是很多高效算法的基杂问题的解就是多个子问题的解的合集。分治法是很多高效算法的基础。分治法的典型算法例如快速排序算法、归并排序算法等。础。分治法的典型算法例如快速排序算法、归并排序算法等。减治法减治法(Decrease and Conquer):(Decrease and Conquer):将大问题缩小规模最终变为小问题将大问题缩小规模最终变为小问
29、题的方法。通过算法的方法。通过算法 中每一步对问题规模的缩小，使得一个较大较复中每一步对问题规模的缩小，使得一个较大较复杂的问题最终变为较小的小问题，对最后的最小问题求解，便是最杂的问题最终变为较小的小问题，对最后的最小问题求解，便是最终大问题的解。减治法的典型算法例如二分查找、插入排序、拓扑终大问题的解。减治法的典型算法例如二分查找、插入排序、拓扑排序等。排序等。变治法变治法(Transfer(Transfer andConquerandConquer):):变化问题求解的方法。基于变换的思变化问题求解的方法。基于变换的思想，把复杂问题变想，把复杂问题变 成简单的更容易求解的问题，也就是俗称的变而成简单的更容易求解的问题，也就是俗称的变而治之。典型的变治算法例如堆排序等。治之。典型的变治算法例如堆排序等。动态规划动态规划(Dynamic Programming):(Dynamic Programming):将问题分解称为不同的状态，后将问题分解称为不同的状态，后一个状态的最优解一个状态的最优解 由前一个状态的最优解得到。典型的动态规划算由前一个状态的最优解得到。典型的动态规划算法有弗洛伊德算法等。法有弗洛伊德算法等。1.5.21.5.2 算法的大致分类算法的大致分类作业作业习题习题 1.61.6
