《数据结构 Java语言版 教学课件 ppt 王学军 第一章》由会员分享，可在线阅读，更多相关《数据结构 Java语言版 教学课件 ppt 王学军 第一章（35页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Java语言版）,人民邮电出版社,第1章 概述,主编:王学军,【知识要点】 数据结构中的常用术语； 线性结构、树形结构（层次结构）和图形结构的认识及结构特点； 算法的定义、特性以及描述规则； 时间复杂度、空间复杂度的定义以及评价规则。,第一节,1.数据结构三种基本结构引入及相关概念 例1某大学拟建立校园网络，设计了如图1.1所示的网络拓扑结构图。,图1.1 某学校校园网络结构示意图,现对该网络拓扑结构图进行分析，首先通过观察发现，该图中有若个交换机，并且要其性能参数、接口配置、相互之间联系等信息。下面通过对该校园网中交换机基本信息、交换机之间的层次关系、交换机之间的传输距离等问题着手
2、，引入数据结构三种基本结构概念。,1.1 线性结构 1通过对交换机信息分析，引入线性结构 该学校校园网的交换机信息列表如表1.1所示。通过该表可以看出，每个交换机的信息构成了一个整体，而这些交换机信息又构成了一个整体，而单纯从这些信息角度看，它构成一种顺序关系，称其为线性结构。,表1.1 某学校校园网中需要交换机信息,【例1.2】 图书管理系统。某学校图书信息包括图书编号、书名、数量和价格等方面信息，如表1.2所示，一行表示一条数据记录（简称记录），即表示某种图书的信息，一列代表一个属性，称其为字段，表示该记录中某一方面的属性。每种图书信息的位置有先后次序，他们之间形成一种线性关系，称这种数据
3、结构为线性关系。,表1.2 某学校图书信息系统,对上述具有线性结构的信息可以进行的主要操作有查找系统中某个信息、修改系统中某条记录信息、在固定的位置插入和删除相应的数据信息等,即查询、插入、删除、修改等相关操作。,2数据的相关概念 数据是数据结构的最基本概念，数据的构成及数据的性质是掌握数据结构概念的基础。数据分为数值型数据和非数值型数据，主要用于工程计算和商务处理等。数据是通过编码变成能被计算机识别、存储和处理的符号。根据数据的不同划分和分类，可以得出数据的一组相关概念。 数据（Data）是描述客观事物的数据集合。如【例1.2】中，每个描述图书的记录就是一个数据。这些数据有一个共同的特点，即
4、他们都可以被输入到计算机并能被计算机识别、存储和处理的符号。,数据元素（Data Element）是构成数据的基本单位。有些数据是由单个元素构成的，例如1，2，3，4，5，100中每个数字就是一个数据，而有些数据是由一些元素构成的。对于【例1.1】中的交换机的信息和【例1.2】中描述图书的信息都是由一组数据构成的。数据项（Data Item）是数据结构中的最小单位。当数据元素由多个项构成时，其每个分项称为数据项，例如，图书信息系统中图书编号、书名、数量、价格等都是数据项。数据对象（Data Object）是指相同性质的数据元素构成的集合。在【例1.1】中的交换机信息和【例1.2】中的图书信息，
5、都具有相同的性质和相同的数据类型，这样的数据构成的集合就是一个数据对象。,1.2 层次结构 1通过校园网交换机之间的层次关系，引入层次结构 按照交换机的之间的管理和被管理的关系，形成了一种层次结构（也称为树形结构）。每个交换机都称做该结构中的结点，结点之间形成了一对多的树形关系。 和图1.2结构类似的还有计算机目录之间关系，公司部门结构关系等等。,图1.2 某校园网交换机之间的层次关系示意图,【例1.3】计算机某磁盘（以C盘为例）目录结构如图1.3所示，该磁盘的根目录下有四个子目录（USER、WINDOWS、DOWNLOAD、WMPUB），每个子目录下面又设有两个子目录，他们之间形成了一种层次
6、关系，这就形成一种树形结构（也称为层次结构），每个目录都称作该结构中的结点，结点之间形成了一对多的关系。,图1.3 计算机某磁盘目录结构示意图 对树形结构可以进行的操作主要有：结点查找、结点信息的修改、结点的插入和删除等。,2数据结构的相关概念 数据结构（Data Structure）是指具有某种联系的数据元素以及元素之间所构成的各种关系组成的集合。包括两个方面：一方面是具有某种联系的数据元素；另一方面是数据元素之间具有的各种关系。数据元素不是孤立存在的，正因为在他们之间总存在某种相互关系，才构成了数据元素之间的各种关系，将这些关系称为结构。数据的结构可分为数据的逻辑结构和数据的物理结构。,逻
7、辑结构（Logical Structure）是指构成数据结构的数据元素相互之间本身具有的逻辑关系，如【例1.1】中交换机信息和【例1.2】中图书信息是一种线性关系，图1.2中交换机之间的层次关系和图1.3中目录之间的层次关系都属于逻辑关系。物理结构（或存储结构）是指构成数据结构的数据元素及其关系在计算机中的描述和表示。一种数据结构可对应一种或多种存储结构。,3数据结构的描述 数据结构是由两个集合构成的一个二元组。其定义如下： = di|1in, n1 /表示构成数据结构的数据元素的集合，其中di表示第i个数据元素，n为D中数据元素的个数。 rj|1jm, m1 /表示数据元素之间的各种关系，r
8、j表示数据元素之间的第j个关系， m为D上的关系个数。 ,1.3 网状结构 如图1.4所示为另一学校网络拓扑结构,图1.4 某学校校园网交换机之间位置和距离示意图,由图可看出，各结点之间形成了一种网状结构（也称图形结构），该结构的特点是每个结点之间都可以建立联系，形成了一种多对多的网状关系。与该结构类似的还有交通图、地图、通讯网络图等。,【例1.4】哥尼斯堡七桥问题。在18世纪的东普鲁士的哥尼斯堡城市，有条横贯全城的普雷格尔河和两个岛屿，在河的两岸与岛屿之间架设了7座桥，把它们连接起来（如图1.5(a)所示）。将如图1.5(a)所示的问题抽象成一个数学问题，就是一个如图1.5(b)所示的无向图
9、。,由图1.5(b)可以看出，A、B、C、D四个结点之间都可以产生联系，即多对多的关系，这就是数据结构中的网状结构（也称为图形结构）。 在网状结构中可以进行的操作有：检索顶点、查找某顶点到其他顶点之间的路径，求最短距离，求关键路径等等。 数据结构既可以描述数值型数据的特点，也可以描述非数值型数据的计算问题。数学模型包括线性表、树、图等数据结构。,2数据结构的分类 根据数据结构中相关数据元素之间不同关系，可将数据结构分为线性结构、树形结构和图形结构三类。 （1）线性结构：该结构的数据元素之间形成一对一的线性关系，【例1.2】就是线性结构。 （2）树形结构（层次结构）：该结构的数据元素之间存在着一
10、对多的关系，【例1.3】就是树形结构。 （3）图形结构（网状结构）：该结构的数据元素之间存在着多对多的关系，【例1.4】就是网状结构。 数据类型(Data Type)和数据结构之间有着密切的联系，在许多由高级语言编写的程序中，对于常量、变量或表达式都有一个所属的确定数据类型（即本身的数据特点）。根据数据特点，决定了它在程序执行期间的取值范围，以及在这些值上允许进行的操作。在数据结构中，专门提出抽象数据类型这个概念，用来描述数学模型及相关操作。,抽象数据类型（Abstract Data Type，简称ADT）是对特定数学模型的数学描述，包括操作的数据，数据之间的关系，以及在该关系上可以实现的操作
11、，即数据类型一般由元素、关系及操作三要素组成。抽象数据类型独立于各种操作的具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在Java中，可以用类的说明来表示ADT，用类的实现来实现ADT。 抽象数据类型可描述如下：,ADT 抽象数据类型名 数据对象：（数据对象的定义）； 数据关系：（数据关系的定义）； 基本操作：（基本操作的定义）； ; 【例1.5】例1.2线性结构对应的抽象数据类型定义如下： ADT book_list 数据元素：每条图书记录xi为一数据元素，i=1，2，n(n1)； 逻辑结构：所有数据元素xi存在
12、线性关系(xi，xi+1)，x1无前趋，xn无后继； 基本操作： Initbook_List(L); / 建立空线性表 Lengthbook_Llist(L); / 求线性表长度 GetElement(L,i); / 取线性表中第i个元素 Searchbook_List(L,x); / 确定元素x在线性表L中的位置 Insertbook_List(L, I,x); / 在线性表中第i个位置插入数据元素x Deletebook_List(L,i); / 删除线性表中第i个位置数据元素 ;,第二节,1.2 数据结构研究的主要问题,【学习任务】了解数据结构所研究的主要问题，为后面的学习奠定基础。 数
13、据结构是一门研究数据的各种逻辑结构和存储结构，以及对数据各种操作的学科。即研究数据的逻辑结构、数据的物理结构以及对数据的操作实现。所有的计算机系统软件和应用软件的编写都要用到各种类型的数据结构。数据结构将解决计算机中处理大量数据元素，大量的数据类型，以及越来越复杂的数据之间的关系. 例如，在【例1.2】所示的图书管理系统中，每一种类的书和其他书之间整体上构成了前后对应的线性关系，即逻辑结构，同时还要了解这样的数据如何在计算机进行存储，即存储结构，（假设使用数组进行存储），这样才可以讨论其相应操作，如插入、删除、查询、修改等。,在高级程序设计语言中，数据结构描述的是所能表示并可以存储的数据种类和
14、数据实体（即物体），数据实体是指在一种数据类型中的所有数据构成的集合；数据结构就是数据实体（即物体）中各元素之间的关系。 例如：数组A=1，2，3，4，5，6，7，8，9，10表示的小于等于10的自然数集合，其中每个数是数据实体，而各元素之间的关系就是前后元素之间的一对一关系，即1的后面是2，2的后面是3，这样就在集合A中实现数据之间的线性关系。 数据结构是计算机类专业的一门专业基础的课程，是学习操作系统、数据库原理等专业课的基础，所涉及的有数学范围的诸多知识；计算机硬件范围的编码理论、存取装置和存取方法等知识；软件范围的文件系统、数据的动态存储管理和信息管理等知识。所以说数据结构是介于数学、
15、计算机硬件及软件三者之间的一门核心课程。许多学校将数据结构课程设为计算机类专业的主干课程之一。,第三节,1.3 算法及描述 【学习任务】算法的理解及其特征，重点掌握由数学问题演变成算法的过程，以及算法的特征及评判标准。 1.3.1 算法与算法特性 根据数据结构所研究问题的性质，可以得出如下的结论： 数据结构=逻辑结构+存储结构+相应算法（或操作） 因此，算法在数据结构中起着非常重要的作用。 1.算法的概念 算法（Algorithm）是指为完成某项任务或者特定问题所设计的一种求解步骤的描述。算法可以理解成指令的有限序列，其中每一条指令可由一个或多个操作组成。 说明：算法的含义与程序十分相似，但又
16、有区别。算法是解决问题的步骤分析，而程序是具体实现算法的有效工具。,通过算法解决实际问题的过程如图1.6所示的流程图来描述。,2.基本特性 根据定义可知，算法实际上是一个问题的求解描述过程，因此它应该有很多的特性，按照算法的设计实现过程，从以下五个主要方面进行描述。 （1）算法数据的输入性：一个正确的算法必须具有零个或多个数据输入，这些输入可根据具体的算法来实现。 （2）算法步骤的确定性：构成算法的每一步必须有确切的含义，不能出现歧义，即构成算法的每个步骤必须要有确定的意义。 （3）算法步骤的可执行性：即健壮性，算法中的每个步骤都可以通过具体的操作步骤来实现，不能设计一些不能实现的操作步骤。,（4）算法步骤的有限性：即算法的完结性，一个算法必须在有限步骤之内结束或完成，或者说算法必须在有限时间内结束或完成。 （5）算法结果的输出性：一个算法至少要有一个或多个结果输出，这些结果的输出同样构成算法的某个特性。 算法还有其他一些特性
