第三章 数据结构与算法概述

null上章回顾上章回顾数据指针、函数指针和数组间的运算操作 注意讲述const 、define、enum、static等C关键词特点和区别 static几个重要的用法和特性 讲述C语言编程常见的几个错误 重点提示C语言编程的调试 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 数据结构与算法概述 数据结构与算法概述 第三章本章结构本章结构抽象数据类型的表示与实现数据结构与算法算法和算法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 基本概念和术语什么是数据结构预习检查预习检查什么是数据结构 常见的数据结构的形式有哪些 算法的时间复杂度是什么 算法的空间复杂度是什么 null**课程目标 了解数据结构的基本概念 理解常用术语 了解算法时间复杂度的分析与评价 了解算空间复杂度的分析与评价3.1 什么是数据结构** 数据结构是一门研究非数值计算的程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构主要有三个方面的内容： 数据的逻辑结构、数据的存储结构和对数据的算法。 逻辑结构：反映数据之间的逻辑关系，是对数据之间关系的描述，主要有集合、线性表、树、图等四种结构。 物理结构：反映数据在计算机内部的存储安排，是数据结构在计算机中的实现方法。 主要有顺序、链接、散列、索引等四种基本存储结构，并可以根据需要组合成其它更复杂的结构。 算法：数据进行处理的方法。 3.1 什么是数据结构null** 3.1.1 数据结构示例 【例3-1】图书目录表 由于表中每条记录（表示每一本书）的登录号各不相同，所以可用登录号来唯一地标识每条记录（一本图书）。在计算机的数据管理中，能唯一地标识一条记录的数据项被称为关键字。因为每本图书的登录排列位置有先后次序，所以在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。这种关系被称为线性结构。 null** 返回返回 3.1.1 数据结构示例图表 null** 描述磁盘目录和文件结构时，假设每个磁盘包括一个根目录（root）和若干个一级子目录，每个一级子目录中又包含若干个二级子目录…. 这种关系很像自然界中的树，所以称为目录树。如左图所示。 3.1.1 磁盘目录结构和文件管理系统 在这种结构中，目录和目录以及目录和文件之间呈现出一对多的非线性关系。即根root有多个下属（也称为后代），每一后代又有属于自己的后代；而任一个子目录或文件都只有一个唯一的上级（也称为双亲）。称这种数学模型为树型数据结构。null** 3.1.1 教学 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 编排问题 假如一个教学计划中包含许多课程。在课程之间，有些必须按规定的先后次序排课，如：学C6课程必须先学C3课，学C3课程必须先学C1课。这些课程之间存在先修和后续的关系。 在这种结构中，表示课程的数据之间呈现多对多的非线性关系，称这类数学模型为图形结构。null** 图结构还有：多岔路口交通灯的控制和管理、煤气管道的铺设造价等。 通过以上几例可以认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 3.1.1 图案例总结null** 1．数据(Data) 数据(Data)：是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括文字、表格、图象等。 例如，一个图书管理程序所要处理的数据可能是一张表格。如表1-1所示。 2．数据元素(Data Element) 数据元素(Data Element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 3.1.2 基本概念和术语 null** 例如，在表3-1所示的图书目录表中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由7个结点构成。 一般情况下，一个结点中含有若干个字段（也叫数据项）。字段是构成数据的最小单位。 3．数据对象(Data Object) 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 4．数据类型(Data Type) 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 3.1.2 基本概念和术语 null** 例如，整型、字符型、浮点型、双精度型等数据类型，分别是一组相同结构的值以及在这些值上允许进行操作的总称。 5．抽象数据类型（Abstruct Data Type，简称ADT） ADT是指一个数学模型以及定义在该模型上的一组的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 3.1.2 基本概念和术语 null** 数据结构是研究数据元素（Data Element）之间抽象化的相互关系（逻辑结构）和这种关系在计算机中的存储表示（物理结构），并对这种结构定义相适应的运算，设计出相应的算法。 数据结构主要指逻辑结构和物理结构。 1. 逻辑结构： 数据之间的相互关系称为逻辑结构。通常分为 4 类基本结构： 集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 线性结构 结构中的数据元素之间存在一对一的关系。 树型结构 结构中的数据元素之间存在一对多的关系。 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 3.1.3 数据结构null** 在表3-1所示的表格中，由7个结点 (数据元素)组成，每个数据元素又包括6个数据项(字段)。各结点之间在逻辑上有一种线性关系，它指出了7个结点在表中的排列顺序。 这张表的逻辑结构就是数据元素(或是结点、记录)之间的关系。对于表中的任一个结点(记录)，都只有一个前驱结点，也只有一个后继结点，整个表只有一个开始结点和一个终端结点。 此表的逻辑结构是线性的。3.1.3 数据结构null** 四类数据基本结构的示意图：(a)集合结构(b)线性结构(c)树型结构(d)图形结构 由以上例子可见，描述这类非数值计算问题的数学模型和方法不再是数学方程，而是诸如线性表、树和图之类的数据结构。 3.1.3 数据结构null** 数据对象可以是有限的，也可以是无限的。 　 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。3.1.3 数据结构null** 2. 存储结构： 数据结构在计算机中的存储表示称为数据的存储结构。它包括数据元素的表示和关系的表示。 表3-1所示的表格数据在计算机中可以有多种存储表示： 数据既可以存放在一块连续的内存 单元 初级会计实务单元训练题天津单元检测卷六年级下册数学单元教学设计框架单元教学设计的基本步骤主题单元教学设计 中，通过元素在存储器中的位置来表示它们之间的逻辑关系（顺序）； 也可以随机分布在内存中的不同位置，通过指针元素表示数据元素之间的逻辑关系（链式）。这两种不同的表示方法对应有四种不同的存储结构（亦称方式）： 顺序存储结构、链式存储结构、索引存储结构和散列存储结构。3.1.3 存储结构null** (1)顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 优点：占用较少的存储空间； 缺点：由于只能使用相邻的一整块存储单元，因此可能产生较多的碎片现象。 顺序存储结构通常借助程序语言中的数组来描述。 顺序存储结构主要应用于线性的数据结构。3.1.3 存储结构null** (2) 链式存储结构将结点所占的存储单元分为两部分，一部分存放结点本身的信息，另一部分存放结点的后继结点地址，结点间的逻辑关系由附加的指针字段表示。 链式存储结构常借助于程序语言的指针类型描述。 优点：不会出现碎片现象，充分利用所有的存储单元； 缺点：每个结点占用较多的存储空间。 (3)索引存储方式是用结点的索引号来确定结点的存储地址。 在储存结点信息的同时，要建立附加的索引表。 优点：检索速度快。 缺点：增加了附加的索引表，占用较多的存储空间；在增加和删除数据时需要修改索引表而花费较多时间。 3.1.3 存储结构null** (4) 散列存储方式是根据结点的关键字值直接计算出该结点的存储地址。通过散列函数把结点间的逻辑关系对应到不同的物理空间。 优点:检索、增加和删除结点的操作都很快； 缺点:当采用不好的散列函数时可能出现结点存储单元的冲突，为解决冲突需要附加时间和空间的开销。 3.1.3 存储结构null** 3．数据的运算 数据运算定义在数据的逻辑结构上，即施加于数据的操作。 例如对一张表的记录进行查找、增加、删除、修改，这就是对数据的运算。 4．数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。 存储结构是对数据项的存储。同一逻辑结构可用不同存储结构就对应不同的存储标识。 例如，线性表若采用顺序存储方式，称为顺序表；若采用链式存储方式，称为链表；若采用散列存储方式，可称为散列表。 3.1.3 存储结构3.2 算法描述 ** 3.2.1 算法（Algorithm） 1、算法：简单地说就是解决特定问题的方法。是对问题求解过程的一种描述。 特定的问题可以是数值的，也可以是非数值的。 一个算法可以用自然语言、计算机程序设计语言或其它语言（比如类C语言）来说明。 一般而言，描述算法最合适的语言是介于自然语言和程序设计语言之间的类语言。如：类C，类pascal等。3.2 算法描述 null** 2、算法的特点 算法是执行特定计算的有穷过程。这个过程有5个特点： 1) 动态有穷; 2) 确定性; 3) 输入：具有0个或多个由外界提供的量(输入)。 4) 输出：产生1个或多个结果。 5) 可行性： 3.2 算法特点 null** 一个算法可以用自然语言、数字语言或流程图等来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等，本书选用C语言作为描述算法的工具。 1．用自然语言描述算法 用日常的自然语言来描述算法(可以是英文,也可以是其它文字语言)。 优点：简单，便于人们对算法的阅读。 缺点：不够严谨。 3.2.2 算法描述 null** 2．用流程图描述算法 使用程序流程图，N-S图等描述算法。特点是描述过程简洁、明了。目前在一些高级语言程序设计中仍然被采用。 但用这两种方法描述的算法不能直接在计算机上执行，必须通过编程将它转换成可执行程序。 3．用程序设计（C或C++）语言描述算法 可以直接使用程序设计语言（如C或C++）描述算法，但直接使用程序设计语言不太容易且不直观，且需要借助于注释才能看明白。 3.2.2 算法描述 null** 为解决理解与执行的矛盾，常使用一种称为伪码（类）语言的描述方法来进行算法描述。 类语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而且比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。 3.2.2 算法描述3.3 算法分析与评价 **3.3.1 算法设计的要求 要设计一个好的算法通常要考虑以下要求。 ⑴正确性(Correctness)：算法的执行结果应当满足预先规定的功能和性能要求。 ⑵可读性(Readability)：算法应当思路清晰、层次分明、简单明了、易读易懂。以有利于阅读者对程序的理解。  ⑶健壮性(Robustness)：算法应具有容错处理。当输入非法数据时，算法应对其作出反应并适当处理，不至引起严重后果。 ⑷高效性和存储量需求：效率指算法执行的时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。 3.3 算法分析与评价 null** 1．时间复杂度（Time complexity） 一个算法的时间复杂度是指算法运行从开始到结束所需要的时间。 通常是所处理问题规模的一个函数T(n) ，常采用数量级的形式表示。记作： T(n)=O(f(n)) 称T(n)为算法的(渐近)时间复杂度。 3.3.2 算法效率的度量null** 2．空间复杂度（Space complexity） 一个算法的空间复杂度是指算法运行从开始到结束所需的存储量。 算法的存储量指的是算法执行过程中所需的最大存储空间。 算法执行期间所需要的存储量应该包括以下三部分： (1) 输入数据所占空间； (2) 程序本身所占空间； (3) 辅助变量所占空间。 类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义：S(n)=O(g(n)) 称S(n)为算法的空间复杂度。 3.3.2 算法的空间复杂度阶段小节阶段小节链式存储的四种结构是什么 算法的空间复杂度是指什么 本章总结本章总结主要讲述数据结构的基本概念和术语抽象数据类型的表示和实现重点讲述算法的时间复杂度和空间复杂度的分析了解数据结构的定义抽象数据类型的表示与实现数据结构与算法算法和算法分析基本概念和术语什么是数据结构实验1实验1实验内容 题目：对冒泡排序算法进行时间复杂度和空间复杂度的分析 实验目的 理解算法分析的原理，掌握算法分析的操作 实验分析 时间复杂度根据循环的嵌套层次和隔层循环的次数 空间复杂度根据算法使用的资源的空间