(Java版)数据结构与算法第1章.pptVIP

第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 什么是数据结构 数据结构的定义可以记作： Data-Structure=（D，R） 其中D是数据元素的有限集合，R是D上的关系。 一般情况下，“关系”是指数据元素之间存在的逻辑关系，也称为数据的逻辑结构。数据在计算机内的存储表示（或映象）称为数据的存储结构或物理结构。 1.1 什么是数据结构 逻辑结构体现的是数据元素之间的逻辑关系，换句话说就是从操作对象中抽象出来的数学模型，因此又称为抽象结构，通常习惯说的数据结构一般就是指的逻辑结构。然而讨论数据结构的目的是为了在计算机中实现对数据的操作，因此还需要研究数据的存储结构。 存储结构是数据在计算机内的表示（映象），又称物理结构。它包括数据元素的表示和关系的表示。 1.1 什么是数据结构 由于映象的方法不同，所以同一种的逻辑结构可以映象成两种不同的存储结构：顺序映象（顺序存储结构）和非顺序映象（非顺序存储结构）。 顺序映象的特点是在顺序存储结构（一般用一维数组）中体现数据之间的关系；而非顺序存储结构则一般采用指针实现数据之间的关系，包括链式存储结构（链表）和散列结构等。 数据的存储结构要能够正确反映数据元素之间的逻辑关系。也就是说数据的逻辑结构和数据的存储结构是密不可分的两个方面，任何一个算法的设计取决于选定的逻辑结构，而算法的实现则依赖于采用的存储结构。 1.1 什么是数据结构 顺序映象（顺序存储结构）是借助元素在存储器中位置表示数据元素之间的逻辑关系，或逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点的逻辑关系由存储单元的邻接关系来体现；而非顺序映象（链式存储结构）是借助元素存储地址的指针表示元素之间的逻辑关系，或逻辑上相邻的结点在物理位置上可相邻，可不相邻，逻辑关系由附加的指针段表示。 1.1 什么是数据结构 数据的非顺序存储结构除包括链式存储结构（简称链表）以外，还有散列存储结构、索引存储结构等。 链式存储结构是利用指针直接表示数据元素之间的关系。 散列结构的基本思想是根据结点的关键字，利用散列函数直接计算出该结点的存储地址。 索引存储结构是指在存储结点信息的同时，还建立附加的索引表。索引表的每一项称为索引项，索引项的一般形式是：（关键字，地址）。关键字：能够惟一标识一个结点的那些数据项集合；索引存储结构分为稠密索引和稀疏索引，其中稠密索引是指每个结点在索引表中都有一个索引项的索引表；而稀疏索引是指一组结点在索引表中对应一个索引项的索引表。 1.1 什么是数据结构 针对存储结构，数据元素存储在计算机中，应对每个数据元素确定其取值范围属性就是数据类型。数据类型是和数据结构密切相关的一个概念，用以刻画（程序）操作对象的特征。 数据类型根据是否允许分解分为原子类型和结构类型，其中原子类型是指其值不可再分的数据类型，例如整型、字符型等；而结构类型是指其值可以再分解为若干成分（分量）的数据类型，例如数组的值由若干分量组成。 根据数据的结构（逻辑结构和存储结构）特性在数据的生存期间的变动情况，将数据结构分为静态结构和动态结构。静态结构是指在数据存在期不发生任何变动，例如高级语言中的静态数组；而动态结构是指在一定范围内结构的大小可以发生变动，如使用的堆栈。 1.1 什么是数据结构 总之，数据结构所要研究的主要内容简单归纳为以下三个方面： ⑴ 研究数据元素之间的客观联系（逻辑结构）； ⑵ 研究数据在计算机内部的存储方法（存储结构）； ⑶ 研究如何在数据的各种结构（逻辑的和物理的）上实施有效的操作或处理（算法）。 所以数据结构是一门抽象地研究数据之间的关系的学科。 1.2 基本概念和术语 1.2.1 数据结构的发展 数据结构作为一门