数据结构ppt课件.ppt

《数据结构ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构ppt课件.ppt（22页珍藏版）》请在三一文库上搜索。

1、Tel:0571-88394222 QQ;106159278,数据结构,Tel:0571-88394222 QQ;106159278,数据结构概述,数据结构主要解决怎样合理地组织数据,建立合适的数据结构,提高计算机执行程序所用的时间效率和空间使用效率的学科。 新提法：真实模拟世界。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。,

2、Tel:0571-88394222 QQ;106159278,数据结构涉及的知识,计算机硬件范围的存贮装置和存取方法 在计算机软件范围中的文件系统数据的动态存贮与管理,信息检索 数学范围的许多算法知识 还有一些综合性的知识,如编码理论,算子关系、数据类型、数据表示、数据运算,数据存取等各方面的知识,Tel:0571-88394222 QQ;106159278,理论基础是程序设计和离散数学 在分析和处理数据结构和算法时也用到概率、图论、集合等方面的知识 各种算法都是以实际问题的数学模型给出的。 所以,数据结构是一门理论性很强,实践性很强的一门专业基础课。,Tel:0571-88394222 QQ

3、;106159278,数据结构基础,数据（data）是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据的含义非常广泛，除了通常的数值数据、字符、字符串是数据以外，声音、图像等一切可以输入计算机并能被处理的都是数据。例如除了表示人的姓名、身高、体重等的字符、数字是数据，人的照片、指纹、三维模型、语音指令等也都是数据。 数据元素（data element）是数据的基本单位，是数据集合的个体，在计算机程序中通常作为一个整体来进行处理。例如一条描述一位学生的完整信息的数据记录就是一个数据元素；空间中一点的三维坐标也可以是一个数据元素。数据元素通常由若干个数据项组成，例如描述学生相关

4、信息的姓名、性别、学号等都是数据项；三维坐标中的每一维坐标值也是数据项。数据项具有原子性，是不可分割的最小单位。,Tel:0571-88394222 QQ;106159278,数据对象（data object）是性质相同的数据元素的集合，是数据的子集。例如一个学校的所有学生的集合就是数据对象，空间中所有点的集合也是数据对象。 数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素的集合。是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。由于信息可以存在于逻辑思维领域，也可以存在于

5、计算机世界，因此作为信息载体的数据同样存在于两个世界中。表示一组数据元素及其相互关系的数据结构同样也有两种不同的表现形式，一种是数据结构的逻辑层面，即数据的逻辑结构；一种是存在于计算机世界的物理层面，即数据的存储结构。,Tel:0571-88394222 QQ;106159278,数据的逻辑结构按照数据元素之间相互关系的特性来分，可以分为以下四种结构：集合、线性结构、树形结构和图状结构。我们讨论的数据结构主要有线性表、栈、队列、树和图， 其中线性表、栈、队列属于线性结构，树和图属于非线性结构 数据的逻辑结构可以采用两种方法来描述：二元组、图形。,Tel:0571-88394222 QQ;106

6、159278,二元组表示形式,数据结构 = D , S 其中 D 是数据元素的集合；S 是 D 中数据元素之间的关系集合，并且数据元素之间的 关系是使用序偶来表示的。序偶是由两个元素 x 和 y 按一定顺序排列而成的二元组，记作 ，x 是它的第一元素，y 是它的第二元素。 当使用图形来表示数据结构时，是用图形中的点来表示数据元素，用图形中的弧来表示数据元素之间的关系。如果数据元素 x 与 y 之间有关系，则在图形中有从表示 x 的点 出发到达表示 y 的点的一条弧。,Tel:0571-88394222 QQ;106159278,一种数据结构的二元组表示为 set = (K,R)，其中K = 0

7、1, 02, 03, 04, 05 R = 可以看到在数据结构 set 中，只有数据元素的集合非空，而数据元素之间除了同属一个集合之外不存在任何关系（关系集合为空）。这表明该结构只考虑数据元素而不考虑它们之 间的关系。我们把具有这种特点的数据结构称为集合结构。,Tel:0571-88394222 QQ;106159278,一种数据结构的二元组表示为 linearity = (K,R)，其中 K = 01, 02, 03, 04, 05 R = , , , 可以看到在数据结构 linearity 中，数据元素之间是有序的。在这些数据元素中有一个可 以被称为“第一个”（元素 01）的数据元素；还有

8、一个可以被称为“最后一个”（元素 04） 的数据元素；除第一个元素以外每个数据元素有且仅有一个直接前驱元素，除最后一个元素 以外每个数据元素有且仅有一个直接后续元素。这种数据结构的特点是数据元素之间是 1对 1 的联系，即线性关系，我们把具有此种特点的数据结构称为线性结构,Tel:0571-88394222 QQ;106159278,一种数据结构的二元组表示为 tree = (K,R)，其中 K = 01, 02, 03, 04, 05, 06 R = , , , , 可以看到在数据结构 tree 中，除了一个数据元素（元素 01）以外每个数据元素有且仅 有一个直接前驱元素，但是可以有多个直接

9、后续元素。这种数据结构的特点是数据元素之间是 1 对 N 的联系，我们把具有此种特点的数据结构称为树结构,Tel:0571-88394222 QQ;106159278,一种数据结构的二元组表示为 graph = (K,R)，其中 K = 01, 02, 03, 04, 05 R = , , , , , , , , 可以看到在数据结构 graph 中，每个数据元素可以有多个直接前驱元素，也可以有多个 直接后续元素。这种数据结构的特点是数据元素之间是 M 对 N 的联系，我们把具有此种特 点的数据结构称为图结构。,Tel:0571-88394222 QQ;106159278,图形表示方法,Tel:

10、0571-88394222 QQ;106159278,数据的存储结构,数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示。通过数据元素的定义可以看出，我们可以很容易的使用 Java 中的一个类来实现它，数据元素的数据项 就是类的成员变量。 数据元素之间的关系在计算机中主要有两种不同的表示方法：顺序映像和非顺序映像， 并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构的特点是： 数据元素的存储对应于一块连续的存储空间，数据元素之间的前驱和后续关系通过数据元素 在存储器中的相对位置来反映。链式存储结构的特点是：数据元素的存储对应的是不连续的 存储空间，每个存储节点

11、对应一个需要存储的数据元素。元素之间的逻辑关系通过存储节点 之间的链接关系反映出来。,Tel:0571-88394222 QQ;106159278,抽象数据类型,抽象数据类型是描述数据结构的一种理论工具。在介绍抽象数据类型之前我们先介绍一 下数据类型的基本概念。 数据类型（data type）是一组性质相同的数据元素的集合以及加在这个集合上的一组操 作。例如 Java 语言中就有许多不同的数据类型，包括数值型的数据类型、字符串、布尔型 等数据类型。以 Java 中的 int 型为例，int 型的数据元素的集合是-2147483648,2147483647 间的整数，定义在其上的操作有加、减、乘

12、、除四则运算，还有模运算等。,Tel:0571-88394222 QQ;106159278,定义数据类型的作用一个是隐藏计算机硬件及其特性和差别，使硬件对于用户而言是透明的，即用户可以不关心数据类型是怎么实现的而可以使用它。定义数据类型的另一个作用 是，用户能够使用数据类型定义的操作，方便的实现问题的求解。例如，用户可以使用 Java 定义在 int 型的加法操作完成两个整数的加法运算，而不用关心两个整数的加法在计算机中 到底是如何实现的。这样不但加快了用户解决问题的速度，也使得用户可以在更高的层面上 考虑问题。,Tel:0571-88394222 QQ;106159278,抽象数据类型可以使

13、用一个三元组来表示： ADT = (D, S, P) 其中 D 是数据对象，S 是 D 上的关系集，P 是加在 D 上的一组操作。 在定义抽象数据类型时，我们使用以下格式： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作：,Tel:0571-88394222 QQ;106159278,数据结构的操作,1,结构的生成； 2.结构的销毁； 3,在结构中查找满足规定条件的数据元素； 4,在结构中插入新的数据元素； 5,删除结构中已经存在的数据元素； 6,遍历。,Tel:0571-88394222 QQ;106159278,Java 集合架构,Java 2软件开发包（SDK）提供了一些新类来

14、支持大多数常用的ADT。这些类被称为Java集合类（类似于MFC中的集合类），它们协同工作从而形成Java 集合架构。这个集合架构提供了一套将数据表示成所谓的集合抽象数据的接口和类。 java.util.Collection接口被用来表示任意的成组的对象，也就是元素。这个接口提供基本的诸如添加，删除，和查询这样的操作。Collection接口还提供了一个iterator方法。iterator方法返回java.util.Iterator接口的一个实例。而Iterator接口又提供了hasNext, next, 和 remove方法。使用Iterator接口提供的方法，你可以从头到尾循环遍历一个C

15、ollection对象中的实例并能够安全的删除iterator(游标)所表示的元素。 java.util.AbstractCollection 是所有集合架构类的基础。AbstractCollection 类提供了对java.util.Collection 接口中除iterator和size方法以外的所有方法的实现。这两个例外的方法由所有继承java.util.AbstractCollection的子类实现。,Tel:0571-88394222 QQ;106159278,练习,设计一个抽象数据类型：Class 数据成员为 Student。 数据操作：为基本方法。 要求：能通过自己写的run方法测试基本方法。,Tel:0571-88394222 QQ;106159278,计算 1 * 2 * 3 + 10 / 5,Tel:0571-88394222 QQ;106159278,联系方式,杭州和盈科技公司 Address:潮王路238号银地大厦2F ,