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

《数据结构与算法分析 第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什么是数据结构信息中的各个数据元素并不是孤立存在的，它们之间存在着一定的结构关系。一般说来，使用计算机解决具体问题时，通常需要几个步骤：分析具体问题得到数学模型，设计解决数学模型的算法，编制程序并调试，最后得到最终答案。在数据结构中数据之间的关系主要有两种，它们分别是线性关

2、系和非线性关系，其中非线性关系又可以分为树型关系和图关系。数据的逻辑结构和存储结构是密不可分的两个方面，在实现算法时，首先应解决数据的存储问题。1.1什么是数据结构数据之间既要考虑存储，又要考虑数据单位之间的关系，在确定了存储结构后，根据存储的结构再来确定相应操作的实现方法。简单说数据结构是研究数据的存储、数据之间的关系和对数据实现各种操作的一门学科。1.1什么是数据结构数据结构的定义可以记作：Data-Structure=（D，R）其中D是数据元素的有限集合，R是D上的关系。一般情况下，“关系”是

3、指数据元素之间存在的逻辑关系，也称为数据的逻辑结构。数据在计算机内的存储表示（或映象）称为数据的存储结构或物理结构。1.1什么是数据结构逻辑结构体现的是数据元素之间的逻辑关系，换句话说就是从操作对象中抽象出来的数学模型，因此又称为抽象结构，通常习惯说的数据结构一般就是指的逻辑结构。然而讨论数据结构的目的是为了在计算机中实现对数据的操作，因此还需要研究数据的存储结构。存储结构是数据在计算机内的表示（映象），又称物理结构。它包括数据元素的表示和关系的表示。1.1什么是数据结构由于映象的方法不同，所以同一

4、种的逻辑结构可以映象成两种不同的存储结构：顺序映象（顺序存储结构）和非顺序映象（非顺序存储结构）。顺序映象的特点是在顺序存储结构（一般用一维数组）中体现数据之间的关系；而非顺序存储结构则一般采用指针实现数据之间的关系，包括链式存储结构（链表）和散列结构等。数据的存储结构要能够正确反映数据元素之间的逻辑关系。也就是说数据的逻辑结构和数据的存储结构是密不可分的两个方面，任何一个算法的设计取决于选定的逻辑结构，而算法的实现则依赖于采用的存储结构。1.1什么是数据结构顺序映象（顺序存储结构）是借助元素在存储

5、器中位置表示数据元素之间的逻辑关系，或逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点的逻辑关系由存储单元的邻接关系来体现；而非顺序映象（链式存储结构）是借助元素存储地址的指针表示元素之间的逻辑关系，或逻辑上相邻的结点在物理位置上可相邻，可不相邻，逻辑关系由附加的指针段表示。1.1什么是数据结构数据的非顺序存储结构除包括链式存储结构（简称链表）以外，还有散列存储结构、索引存储结构等。链式存储结构是利用指针直接表示数据元素之间的关系。散列结构的基本思想是根据结点的关键字，利用散列函数直接计算出该

6、结点的存储地址。索引存储结构是指在存储结点信息的同时，还建立附加的索引表。索引表的每一项称为索引项，索引项的一般形式是：（关键字，地址）。关键字：能够惟一标识一个结点的那些数据项集合；索引存储结构分为稠密索引和稀疏索引，其中稠密索引是指每个结点在索引表中都有一个索引项的索引表；而稀疏索引是指一组结点在索引表中对应一个索引项的索引表。1.1什么是数据结构针对存储结构，数据元素存储在计算机中，应对每个数据元素确定其取值范围属性就是数据类型。数据类型是和数据结构密切相关的一个概念，用以刻画（程序）操作对象

7、的特征。数据类型根据是否允许分解分为原子类型和结构类型，其中原子类型是指其值不可再分的数据类型，例如整型、字符型等；而结构类型是指其值可以再分解为若干成分（分量）的数据类型，例如数组的值由若干分量组成。根据数据的结构（逻辑结构和存储结构）特性在数据的生存期间的变动情况，将数据结构分为静态结构和动态结构。静态结构是指在数据存在期不发生任何变动，例如高级语言中的静态数组；而动态结构是指在一定范围内结构的大小可以发生变动，如使用的堆栈。1.1什么是数据结构总之，数据结构所要研究的主要内容简单归纳为以下三个

8、方面：⑴研究数据元素之间的客观联系（逻辑结构）；⑵研究数据在计算机内部的存储方法（存储结构）；⑶研究如何在数据的各种结构（逻辑的和物理的）上实施有效的操作或处理（算法）。所以数据结构是一门抽象地研究数据之间的关系的学科。1.2基本概念和术语1.2.1数据结构的发展数据结构作为一门独立的课程始于1968年，在我国数据结构作为一门独立课程在80年代初，早期的数据结构对课程的范围没有明确的规定，数据结构的内容几乎和图论、树的理论是相同的，在60到70年代随着大型程序的出现，