01数据结构概述.ppt

《01数据结构概述.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章数据结构概述1.1数据的逻辑结构1.2数据的存储结构1.3算法及算法分析数据的逻辑结构；数据的存储结构；数据处理算法的描述与分析。“数据结构”是计算机专业的一门重要基础课程，它研究的问题是从实际需要中抽象出来的，是计算机科学各领域以及系统软件都会用到的知识。本章是全书的基础，主要介绍以下几个方面的内容：1.1数据的逻辑结构人们要让计算机做事情，都必须涉及三个问题：一，确定所要加工处理的数据间的关系，以便进行处理时，能够知道一个数据的后面是哪一个数据，这是数据的逻辑结构问题；二，确定要对数据做哪些处理，这是算法描述问题；三，确定以何种方式把数据存放到计算机的内存，并反映出它们间的邻接

2、关系，这是数据的存储结构问题。1.1.1数据及数据间的邻接关系“数据”是信息的载体，是人们用符号来表示客观事物的一种集合。现在把“数据”定义为：所有能够输入到计算机中被计算机加工、处理的符号的集合。通常，数据由“数据元素”（简称“元素”）集合而成的。数据元素也常被称作“结点”、“顶点”、“记录”。每个数据元素都具有完整、确定的实际意义，是数据加工处理的对象。某公司雇员的信息雇员号姓名年龄性别住址071251章三30男私立华联071252李四28女私立华联071253王五24女私立华联071254程西32男私立华联一个数据元素又可以细分成由若干个“数据项”组成。数据项也常称作“字段”、“域

3、”，它是数据元素中不可再分割的最小标识单位，通常不具备完整、确定的实际意义，只是反映数据元素某一方面的属性。数据结构关心的是从一个数据能够找到另一个数据的那种“关系”，人们根据那种关系来组织和存储数据，以便顺利、有效地实现对数据的各种处理要求。如果两个数据结点间有着某种逻辑上的联系，就称这两个结点是“邻接的”。若用圆圈代表结点，用结点间的一条连线代表它们之间存在的逻辑关系，那么，就用图1-1来表示结点A和B是“邻接的”。直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。图1-1结点的邻接常见的数据间的邻接关系有三种：线性关系、树型关系以及图状关系。数据

4、间的邻接关系，就是数据的“逻辑结构”。1.1.2数据的逻辑结构所谓数据间具有“线性”关系，是指数据一个接一个地排列成一行。如果所要处理的数据间呈线性关系，那么就说它的逻辑结构是线性的。在线性关系中，排在第1个位置的结点称为起始结点，排在最后一个位置的结点称为终端结点，其余的结点称为中间结点，如图1-2所示。1．线性关系图1-2线性关系中的各种结点线性关系的特点是：除起始结点和终端结点外，每个结点的前面和后面，都有且只有一个结点与它邻接，起始结点的前面没有邻接的结点，终端结点的后面没有邻接的结点。简单地说，线性关系的特点是：有头有尾，顺序排列。所谓数据间具有“树型”关系，是指在数据之间具有

5、分支、层次的逻辑关系。如果所要处理的数据之间呈树型关系，那么就说它的逻辑结构是树型的。文件目录间的逻辑结构就是树型的。图1-3所示为一个树型目录图例。2．树型关系图1-3文件目录间的树型关系树型关系的特点是：第1层只有一个结点，它是树型关系的起点；除第1层结点和分支末端结点外，位于中间各层的结点的前面只有一个结点与它相邻接，每个结点的后面可以有多个结点与它相邻接；第1层结点的前面没有结点与之邻接，每个分支末端结点的后面没有结点与之邻接。如果数据中的任何两个元素间都可能有邻接关系，那么就说它们之间的关系是图状的。如果所要处理的数据之间呈图状关系，那么就说它的逻辑结构是图状的。图状关系是数据

6、间最复杂的关系。图1-4所示为一张航空网络图。在图状关系中，找不到谁是起点，谁是终点，各个结点的地位可以说都是相同的。3．图状关系图1-4航空网络图状关系的特点是：每个结点都可能与多个结点有邻接关系。数据间的线性关系和树型关系，都可以视为是图状关系的一个特例。1.2数据的存储结构在计算机里存放数据时，既要存储数据本身，也要存储数据间的邻接关系。这样，在对数据进行加工处理时，才能够方便、正确地从一个数据找到与之邻接的另一个数据。数据的“存储结构”，就是研究数据在内存中的存储方式，也就是在内存中有哪些存放数据的方法。数据的存储结构也称为数据的“物理结构”。从整体上来看，数据在存储器内有两种存

7、放的方式：一种是集中地存放在内存中的一个连接的存储区；另一种是利用存储器中的零星区域，分散地存放在内存地各个地方。在把数据存储到存储器时，是以数据元素（即数据结点）为单位进行的。分配给一个数据结点的存储区域，称为一个“存储结点”。在一个存储结点里，除了要有数据本身的内容外，还要有体现数据间邻接关系的内容。所谓数据的“顺序式存储”结构，即是为一组数据分配一个连续的存储区，然后按照数据间的邻接关系，相继存放每个数据。这种存储结构，是借助