数据结构与算法分析 第1章.ppt

第第1 1章章 数据结构概论数据结构概论1.1 什么是数据结构 1.2 基本概念和术语 1.2.1 数据结构的发展数据结构的发展 1.2.2 数据结构的基本概念和术语数据结构的基本概念和术语 1.3 抽象数据类型和数据结构 1.4 学习数据结构的意义 1.5 算法算法1.5.1 算法及其性质1.5.2 算法描述的分析算法描述的分析 1.1 1.1 什么是数据结构什么是数据结构 信息中的各个数据元素并不是孤立存在的，它们之间存在着一定的结构关系。一般说来，使用计算机解决具体问题时，通常需要几个步骤：分析具体问题得到数学模型，设计解决数学模型的算法，编制程序并调试，最后得到最终答案。在数据结构中数据之间的关系主要有两种，它们分别是线性关系和非线性关系，其中非线性关系又可以分为树型关系和图关系。数据的逻辑结构和存储结构是密不可分的两个方面，在实现算法时，首先应解决数据的存储问题。1.1 1.1 什么是数据结构什么是数据结构数据之间既要考虑存储，又要考虑数据单位之间的关系，在确定了存储结构后，根据存储的结构再来确定相应操作的实现方法。简单说数据结构是研究数据的存储、数据之间的关系和对数据实现各种操作的一门学科。1.1 1.1 什么是数据结构什么是数据结构数据结构的定义可以记作：Data-Structure=（D，R）其中D是数据元素的有限集合，R是D上的关系。一般情况下，“关系”是指数据元素之间存在的逻辑关系，也称为数据的逻辑结构。数据在计算机内的存储表示（或映象）称为数据的存储结构或物理结构。1.1 1.1 什么是数据结构什么是数据结构逻辑结构体现的是数据元素之间的逻辑关系，换句话说就是从操作对象中抽象出来的数学模型，因此又称为抽象结构，通常习惯说的数据结构一般就是指的逻辑结构。然而讨论数据结构的目的是为了在计算机中实现对数据的操作，因此还需要研究数据的存储结构。存储结构是数据在计算机内的表示（映象），又称物理结构。它包括数据元素的表示和关系的表示。1.1 1.1 什么是数据结构什么是数据结构由于映象的方法不同，所以同一种的逻辑结构可以映象成两种不同的存储结构：顺序映象（顺序存储结构）和非顺序映象（非顺序存储结构）。顺序映象的特点是在顺序存储结构（一般用一维数组）中体现数据之间的关系；而非顺序存储结构则一般采用指针实现数据之间的关系，包括链式存储结构（链表）和散列结构等。数据的存储结构要能够正确反映数据元素之间的逻辑关系。也就是说数据的逻辑结构和数据的存储结构是密不可分的两个方面，任何一个算法的设计取决于选定的逻辑结构，而算法的实现则依赖于采用的存储结构。1.1 1.1 什么是数据结构什么是数据结构顺序映象（顺序存储结构）是借助元素在存储器中位置表示数据元素之间的逻辑关系，或逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点的逻辑关系由存储单元的邻接关系来体现；而非顺序映象（链式存储结构）是借助元素存储地址的指针表示元素之间的逻辑关系，或逻辑上相邻的结点在物理位置上可相邻，可不相邻，逻辑关系由附加的指针段表示。1.1 1.1 什么是数据结构什么是数据结构数据的非顺序存储结构除包括链式存储结构（简称链表）以外，还有散列存储结构、索引存储结构等。链式存储结构是利用指针直接表示数据元素之间的关系。散列结构的基本思想是根据结点的关键字，利用散列函数直接计算出该结点的存储地址。索引存储结构是指在存储结点信息的同时，还建立附加的索引表。索引表的每一项称为索引项，索引项的一般形式是：（关键字，地址）。关键字：能够惟一标识一个结点的那些数据项集合；索引存储结构分为稠密索引和稀疏索引，其中稠密索引是指每个结点在索引表中都有一个索引项的索引表；而稀疏索引是指一组结点在索引表中对应一个索引项的索引表。1.1 1.1 什么是数据结构什么是数据结构针对存储结构，数据元素存储在计算机中，应对每个数据元素确定其取值范围属性就是数据类型。数据类型是和数据结构密切相关的一个概念，用以刻画（程序）操作对象的特征。数据类型根据是否允许分解分为原子类型和结构类型，其中原子类型是指其值不可再分的数据类型，例如整型、字符型等；而结构类型是指其值可以再分解为若干成分（分量）的数据类型，例如数组的值由若干分量组成。根据数据的结构（逻辑结构和存储结构）特性在数据的生存期间的变动情况，将数据结构分为静态结构和动态结构。静态结构是指在数据存在期不发生任何变动，例如高级语言中的静态数组；而动态结构是指在一定范围内结构的大小可以发生变动，如使用的堆栈。1.1 1.1 什么是数据结构什么是数据结构总之，数据结构所要研究的主要内容简单归纳为以下三个方面：研究数据元素之间的客观联系（逻辑结构）；研究数据在计算机内部的存储方法（存储结构）；研究如何在数据的各种结构（逻辑的和物理的）上实施有效的操作或处理（算法）。所以数据结构是一门抽象地研究数据之间的关系的学科。1.2 1.2 基本概念和术语基本概念和术语 1.2.1 数据结构的发展数据结构的发展数据结构作为一门独立的课程始于1968年，在我国数据结构作为一门独立课程在80年代初，早期的数据结构对课程的范围没有明确的规定，数据结构的内容几乎和图论、树的理论是相同的，在60到70年代随着大型程序的出现，软件也相对独立，结构程序设计逐步成为程序设计方法学的主要内容，人们已经认识到程序设计的实质就是对所确定的问题选择一种好的结构，从而设计一种好的算法。1.2 1.2 基本概念和术语基本概念和术语1.2.2 数据结构的基本概念和术语数据结构的基本概念和术语 数据结构是指数据之间的相互形式，即数据的组织形式。数据结构分为逻辑结构和存储结构。逻辑结构是指数据元素之间的逻辑关系；存储结构是指数据元素及其关系在计算机内的表示。数据是对客观事物的符号表示，在计算机科学中是指输入到计算机中并能够被计算机识别、存储和加工处理的符号的总称。数据由数据项组成。数据项（数据元素）是指具有独立含义的最小识别单位（数据中不可分割的最小单位）。数据项又称项或字段。1.2 1.2 基本概念和术语基本概念和术语1.2.2 数据结构的基本概念和术语数据结构的基本概念和术语数据项有逻辑形式（logical form）和物理形式（physical form）两个方面。用ADT给出的数据项的定义是它的逻辑形式，数据结构中对数据项的实现是它的物理形式。在存储结构中包括了数据元素的表示和数据元素之间的关系表示。数据元素存储在计算机中，计算机中表示信息的最小单位是二进制数的一位，称为位（bit），由若干位组成一个位串表示一个数据元素，称为元素或结点，也可以描述为结点是数据处理的数据单位，它可能是一条记录或一个数据项或组合数据项。对应结点定义根据结点所处位置的不同可以将表中的结点分为前趋和后继结点，对表中任意结点，处于该结点之前的所有结点称为该结点的前趋结点，处于该结点之后的所有结点称为该结点的后继结点，与之相邻的前趋结点称为直接前趋结点，与之相邻的后继结点称为直接后继结点；表中的第一个结点称为开始结点，表中最后一个没有后继的结点称为终端结点。1.3 1.3 抽象数据类型和数据结构抽象数据类型和数据结构 数据类型是指一个值的集合以及在这些值上定义的一组操作的总称。抽象数据类型（Abstract Data Type 简称ADT）是指抽象数据组织和与之相关的操作。每一个操作由它的输入和输出定义。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内的表示和实现无关。抽象数据类型可以定义为：（D，S，P）其中D表示数据对象，S是D上的关系集，P是对D的基本操作集。1.3 1.3 抽象数据类型和数据结构抽象数据类型和数据结构ADT使用伪码描述为：ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名 1.4 1.4 学习数据结构的意义学习数据结构的意义 算法+数据结构=程序。其中数据结构是指数据逻辑结构和物理结构，算法是对数据运算的描述。由此可见程序设计的实质是对具体问题选择一种好的数据结构，再设计一个好的算法，而好的算法通常取决于实际问题的数据结构。1.5 1.5 算法算法 1.5.1 算法及其性质算法及其性质算法是指解决问题的一种方法或者一个过程。一个问题可以用多种算法来解决，一个给定的算法解决一个特定的问题。数据结构与算法之间存在着密切的关系。可以说不了解施加于数据上的算法需求就无法决定数据结构；反之算法的结构设计和选择又依赖于作为其基础的数据结构。即数据结构为算法提供了工具。算法是利用这些工具来实施解决问题的最优方案。1.5 1.5 算法算法1.5.1 算法及其性质算法及其性质算法就是解决问题的方法。算法是解决某个特定问题的一些指令的集合；由人们组织起来加以准备加以实施的有限的基本步骤。流程图是图形化的算法，程序是用计算机语言描述的算法。在计算机领域内，一个算法实质上是根据处理问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算。1.5 1.5 算法算法1.5.1 算法及其性质算法及其性质一个完整的算法应该满足以下几条性质：正确性。算法必须完成所期望的功能，得到的结果必须是正确的。确定性。组成算法的指令必须是清晰的、无二义性。也就是说算法的每一个步骤都必须准确定义。准确定义是指所描述的行为必须是对人或机器而言是可读的、可执行的。每一步必须在有限的时间内执行完毕，同时必须是我们所力所能及的，能够依赖于具体的工具来执行的工序。有穷性。算法必须在有限的步骤内结束。如果一个算法由无限的步骤组成，该算法不可能有计算机程序实现。有效性。算法的指令必须具有可执行性。可终止性。算法必须可以终止，即不能进入死循环。一个算法可以没有输入，但是至少应该有一个输出。1.5 1.5 算法算法1.5.2 算法描述的分析算法描述的分析 一、算法设计要求 正确性。算法设计应满足具体问题的需求。它至少应该包括对输入、输出及加工过程等的明确的无歧义性的描述。“正确”涵义通常包含程序无语法错误、程序能够得到正确的结果、程序对不合法的数据的输入应有满足要求的结果。一般对程序的测试时，以录入不合法数据得到满足要求的结果作为衡量程序是否合格的标准。可读性。算法主要是为了人的阅读与交流，算法可读性好有助于人对算法的理解。健壮性。当输入非法的数据时，算法能够适当地作出反应或进行处理，不会产生莫名其妙的输出结果。效率与低存储量需求。效率是指算法的执行时间，一般对问题的求解方法很多，执行时间短的算法效率高。存储量的需求是指算法执行过程所需要的最大的存储容量，存储空间越小，则算法越好。1.5 1.5 算法算法1.5.2 算法描述的分析算法描述的分析 二、算法分析 算法的分析主要是指判断算法的优劣，判断一个算法的好坏一般从两个方面考虑，即从时间角度和从空间角度上衡量算法。一般算法分析从时间角度考虑的比较多。当然判断一个算法的好与坏，不能以时间或空间衡量简单化，而是根据实际情况综合考虑。度量一个程序的执行时间通常有两种方法：事后统计方法。事前分析估算的方法。1.5 1.5 算法算法1.5.2 算法描述的分析算法描述的分析将算法的求解问题的输入称为问题的规模，并用一个整数n表示。在算法的每个步骤中，可能有若干条语句，而频度就是指每条语句的执行次数。一个算法的时间复杂度是指算法的时间耗费。简单说，就是以一条基本语句的执行时间为基本单位，该算法所有语句中总的基本语句的执行次数，就是该算法的时间耗费，它是该算法所求解的问题规模n的函数。当问题的规模n趋向无穷大时，我们把时间复杂度的数量阶称为算法的渐进时间复杂度。一般我们把渐进时间复杂度称为算法的时间复杂度，记做“O”（Order）。1.5 1.5 算法算法1.5.2 算法描述的分析算法描述的分析算法的时间复杂度，记做“O”（Order），它有严格的数学定义：若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）O（f（n）表示存在正的常数C和n0，使得当nn0时都满足0T（n）C*f（n）。空间复杂度（Space Complexity）类似于时间复杂度，是指该算法所耗费的存储空间，也是问题规模n的函数。一般是指渐进空间复杂度。记作：S（n）=O（f（n）其中n是问题的规模（大小）。