1、2018/10/10,1,21世纪高等院校规划教材 数据结构（C语言版）,制作：赵坚 邵明 李兰青岛理工大学中国水利水电出版社,2018/10/10,2,本书介绍了各种常用的数据结构。共有10章第1章： 绪论 第6章： 树和二叉树第2章： 线性表 第7章： 图第3章： 栈和队列 第8章： 排序第4章： 串 第9章： 查找第5章： 数组 第10章：文件,2018/10/10,3,第1章 绪论,本章主题：数据结构的基本概念和术语 教学目的：了解数据结构的基本概念，理解常用术语 教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价 教学难点：数据元素间的 4 种结
2、构关系。 主要内容： 1.1 什么是数据结构1.2 算法描述1.3 算法分析与评价,2018/10/10,4,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构主要有三个方面的内容：数据的逻辑结构、数据的存储结构和对数据的算法。 逻辑结构：反映数据之间的逻辑关系，是对数据之间关系的描述，主要有集合、线性表、树、图等四种结构。物理结构：反映数据在计算机内部的存储安排，是数据结构在计算机中的实现方法。主要有顺序、链接、散列、索引等四种基本存储结构，并可以根据需要组合成其它更复杂的结构。算法：数据进行处理的方法。,1.1 什么是数据结构,2018/1
3、0/10,5,1.1.1 数据结构示例 【例1-1】图书目录表由于表中每条记录（表示每一本书）的登录号各不相同，所以可用登录号来唯一地标识每条记录（一本图书）。在计算机的数据管理中，能唯一地标识一条记录的数据项被称为关键字。因为每本图书的登录排列位置有先后次序，所以在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。这种关系被称为线性结构。,2018/10/10,6,返回,返回,2018/10/10,7,描述磁盘目录和文件结构时，假设每个磁盘包括一个根目录（root）和若干个一级子目录，每个一级子目录中又包含若干个二级子目录.这种关系很像自然界中的树，所以称为目录树。如左
4、图所示。,【例1-2】磁盘目录结构和文件管理系统,在这种结构中，目录和目录以及目录和文件之间呈现出一对多的非线性关系。即根root有多个下属（也称为后代），每一后代又有属于自己的后代；而任一个子目录或文件都只有一个唯一的上级（也称为双亲）。称这种数学模型为树型数据结构。,2018/10/10,8,【例1-3】教学计划编排问题,假如一个教学计划中包含许多课程。在课程之间，有些必须按规定的先后次序排课，如：学C6课程必须先学C3课，学C3课程必须先学C1课。这些课程之间存在先修和后续的关系。在这种结构中，表示课程的数据之间呈现多对多的非线性关系，称这类数学模型为图形结构。,2018/10/10,9
5、,图结构还有：多岔路口交通灯的控制和管理、煤气管道的铺设造价等。 通过以上几例可以认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。,2018/10/10,10,1.1.2 基本概念和术语1数据(Data) 数据(Data)：是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括文字、表格、图象等。例如，一个图书管理程序所要处理的数据可能是一张表格。如表1-1所示。2数据元素(Data Element)数据元素(Data Element)：是数据的
6、基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。,2018/10/10,11,例如，在表1-1所示的图书目录表中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由7个结点构成。一般情况下，一个结点中含有若干个字段（也叫数据项）。字段是构成数据的最小单位。3数据对象(Data Object) 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。4数据类型(Data Type)数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合
7、。,2018/10/10,12,例如，整型、字符型、浮点型、双精度型等数据类型，分别是一组相同结构的值以及在这些值上允许进行操作的总称。5抽象数据类型（Abstruct Data Type，简称ADT）ADT是指一个数学模型以及定义在该模型上的一组的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。,2018/10/10,13,1.1.3 数据结构(Data Structure)数据结构是研究数据元素（Data Element）之间抽象化的相互关系（逻辑结构）和这种关系在计算机中的存储表示（物理结构），
8、并对这种结构定义相适应的运算，设计出相应的算法。数据结构主要指逻辑结构和物理结构。1. 逻辑结构： 数据之间的相互关系称为逻辑结构。通常分为 4 类基本结构：集合 结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构 结构中的数据元素之间存在一对一的关系。树型结构 结构中的数据元素之间存在一对多的关系。图状结构或网状结构 结构中的数据元素之间存在多对多的关系。,2018/10/10,14,在表1-1所示的表格中，由7个结点 (数据元素)组成，每个数据元素又包括6个数据项(字段)。各结点之间在逻辑上有一种线性关系，它指出了7个结点在表中的排列顺序。这张表的逻辑结构就是数据元素(或是结点、
9、记录)之间的关系。对于表中的任一个结点(记录)，都只有一个前驱结点，也只有一个后继结点，整个表只有一个开始结点和一个终端结点。此表的逻辑结构是线性的。,2018/10/10,15,四类数据基本结构的示意图：,(a)集合结构 (b)线性结构 (c)树型结构 (d)图形结构,由以上例子可见，描述这类非数值计算问题的数学模型和方法不再是数学方程，而是诸如线性表、树和图之类的数据结构。,2018/10/10,16,数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,2018/10/10,17,2. 存
10、储结构：数据结构在计算机中的存储表示称为数据的存储结构。它包括数据元素的表示和关系的表示。表1-1所示的表格数据在计算机中可以有多种存储表示： 数据既可以存放在一块连续的内存单元中，通过元素在存储器中的位置来表示它们之间的逻辑关系（顺序）；也可以随机分布在内存中的不同位置，通过指针元素表示数据元素之间的逻辑关系（链式）。这两种不同的表示方法对应有四种不同的存储结构（亦称方式）：顺序存储结构、链式存储结构、索引存储结构和散列存储结构。,2018/10/10,18,(1)顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 优点：占用较少
11、的存储空间； 缺点：由于只能使用相邻的一整块存储单元，因此可能产生较多的碎片现象。 顺序存储结构通常借助程序语言中的数组来描述。顺序存储结构主要应用于线性的数据结构。,2018/10/10,19,(2) 链式存储结构将结点所占的存储单元分为两部分，一部分存放结点本身的信息，另一部分存放结点的后继结点地址，结点间的逻辑关系由附加的指针字段表示。链式存储结构常借助于程序语言的指针类型描述。优点：不会出现碎片现象，充分利用所有的存储单元；缺点：每个结点占用较多的存储空间。(3)索引存储方式是用结点的索引号来确定结点的存储地址。在储存结点信息的同时，要建立附加的索引表。优点：检索速度快。缺点：增加了附
12、加的索引表，占用较多的存储空间；在增加和删除数据时需要修改索引表而花费较多时间。,2018/10/10,20,(4) 散列存储方式是根据结点的关键字值直接计算出该结点的存储地址。通过散列函数把结点间的逻辑关系对应到不同的物理空间。优点:检索、增加和删除结点的操作都很快；缺点:当采用不好的散列函数时可能出现结点存储单元的冲突，为解决冲突需要附加时间和空间的开销。,2018/10/10,21,3数据的运算 数据运算定义在数据的逻辑结构上，即施加于数据的操作。例如对一张表的记录进行查找、增加、删除、修改，这就是对数据的运算。4数据结构三方面的关系数据的逻辑结构、数据的存储结构及数据的运算三方面构成一
13、个数据结构的整体。 存储结构是对数据项的存储。同一逻辑结构可用不同存储结构就对应不同的存储标识。 例如，线性表若采用顺序存储方式，称为顺序表；若采用链式存储方式，称为链表；若采用散列存储方式，可称为散列表。,2018/10/10,22,1.2.1 算法（Algorithm）1、算法：简单地说就是解决特定问题的方法。是对问题求解过程的一种描述。特定的问题可以是数值的，也可以是非数值的。 一个算法可以用自然语言、计算机程序设计语言或其它语言（比如类C语言）来说明。一般而言，描述算法最合适的语言是介于自然语言和程序设计语言之间的类语言。如：类C，类pascal等。,1.2 算法描述,2018/10/
14、10,23,2、算法的特点算法是执行特定计算的有穷过程。这个过程有5个特点：1) 动态有穷：当执行一个算法时，不论是何种情况，在经过了有限步骤后，这个算法一定要终止。2) 确定性：算法中的每条指令都必须是清楚的，指令无二义性。3) 输入：具有0个或多个由外界提供的量(输入)。4) 输出：产生1个或多个结果。5) 可行性：每条指令都充分基本，即：序列中的每个操作都是可以简单完成的，都可以通过已经实现的基本操作运算的有限次来实现。 注意：算法和程序是有区别的，即程序未必能满足动态有穷。在本书中只讨论满足动态有穷的程序，因此“算法”和“程序” 是通用的。,2018/10/10,24,1.2.2 算法
15、描述一个算法可以用自然语言、数字语言或流程图等来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等，本书选用C语言作为描述算法的工具。1用自然语言描述算法 用日常的自然语言来描述算法(可以是英文,也可以是其它文字语言)。优点：简单，便于人们对算法的阅读。缺点：不够严谨。,2018/10/10,25,2用流程图描述算法使用程序流程图，N-S图等描述算法。特点是描述过程简洁、明了。目前在一些高级语言程序设计中仍然被采用。但用这两种方法描述的算法不能直接在计算机上执行，必须通过编程将它转换成可执行程序。3用程序设计（C或C+）语言描述算法可以直接使用程序设计语言（如C或C+
16、）描述算法，但直接使用程序设计语言不太容易且不直观，且需要借助于注释才能看明白。,2018/10/10,26,为解决理解与执行的矛盾，常使用一种称为伪码（类）语言的描述方法来进行算法描述。类语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而且比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。,2018/10/10,27,1.3.1 算法设计的要求 要设计一个好的算法通常要考虑以下要求。 正确性(Correctness)：算法的执行结果应当满足预先规定的功能和性能要求。 可读性(Rea
17、dability)：算法应当思路清晰、层次分明、简单明了、易读易懂。以有利于阅读者对程序的理解。 健壮性(Robustness)：算法应具有容错处理。当输入非法数据时，算法应对其作出反应并适当处理，不至引起严重后果。高效性和存储量需求：效率指算法执行的时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。,1.3 算法分析与评价,2018/10/10,28,1.3.2 算法效率的度量 1时间复杂度（Time complexity）一个算法的时间复杂度是指算法运行从开始到结束所需要的时间。通常是所处理问题规模的一个函数T(n) ，常采用数量级的
18、形式表示。记作：T(n)=O(f(n)称T(n)为算法的(渐近)时间复杂度。,2018/10/10,29,2空间复杂度（Space complexity）一个算法的空间复杂度是指算法运行从开始到结束所需的存储量。算法的存储量指的是算法执行过程中所需的最大存储空间。 算法执行期间所需要的存储量应该包括以下三部分：(1) 输入数据所占空间；(2) 程序本身所占空间；(3) 辅助变量所占空间。 类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义：S(n)=O(g(n) 称S(n)为算法的空间复杂度。,2018/10/10,30,1数据结构研究的是数据的表示和数据之间的关系
19、。从逻辑上讲，数据有集合、线性、树和图四种结构。从存储结构上讲，数据有顺序结构、链接结构、索引结构和散列结构四种。理论上，任一种数据逻辑结构都可以用任一种存储结构来实现。 2在集合结构中，数据处于无序的、各自独立的状态；在线性结构中，数据之间是1对1的关系；在树结构中，数据之间是1对多的关系；在图结构中，数据之间是多对多的关系。 3就存储结构而言，一个数组占有一片连续的存储空间，每个元素的物理存储单元是按下标位置从0开始连续编号的，相邻元素之间其存储位置也相邻。对于任一种数据的逻辑结构，若能够把元素之间的逻辑关系对应地转换为数组下标位置之间的物理关系，则就能够利用数组来实现其顺序存储结构。,本章小结,2018/10/10,31,4抽象数据类型是数据和对数据进行各种操作的集合体。这里所说的数据是广义的，是带有结构的数据，它可以具有任何逻辑结构和存储结构。 5算法的评价指标主要为正确性、健壮性、可读性和有效性四个方面。有效性又包括时间复杂度(性)和空间复杂度(性)两个方面。一个算法的时间和空间复杂度越好，就越节省时间和空间，则表明该算法越有效。 6算法的时间复杂度和空间复杂度通常用数量级的形式表示出来。数量级的形式可分为常量级，对数级、线性级、平方级、立方级等多个级别。当数据处理量较大时，处于前面级别的算法比处于后面级别的算法更有效。,
