第5章信息数据的结构、组 织和管理 计算机并非天生具备这些功能,它们都是程 序员赋予的,那么程序员又是如何具备这 超凡的能力?这就是本章所要学习的。本章 首先学习现实生活中的各种信息数据之间存 在怎样的内在联系,如何在计算机中体现这 联系,从而使计算机能够进行信息处理 其次,学习在面对大量信息数据时,如何提 高人们的工作效率,即数据库技术
第5章 信息数据的结构、组 织和管理 • 计算机并非天生具备这些功能，它们都是程 序员赋予的，那么程序员又是如何具备这一 超凡的能力？这就是本章所要学习的。本章 首先学习现实生活中的各种信息数据之间存 在怎样的内在联系，如何在计算机中体现这 一联系，从而使计算机能够进行信息处理。 其次，学习在面对大量信息数据时，如何提 高人们的工作效率，即数据库技术
5.1为什么要进行数据组织? 数据组织的两层目的,一是 能够解决问题,二是方便地 解决问题
5.1 为什么要进行数据组织？ 数据组织的两层目的，一是 能够解决问题，二是方便地 解决问题
5.2数据结构 5.2.1数据结构要解决什么问题 数据结构应该包含两层含义,即数据 的逻辑结构和物理结构。数据结构是在整 个计算机科学与技术领域上广泛被使用的 术语。它用来反映一个数据的内部构成, 即一个数据由哪些成分数据构成,以什么 方式构成,呈什么结构。数据结构是信息 的一种组织方式,其目的是为了提高算法 的效率
5.2 数据结构 5.2.1 数据结构要解决什么问题 数据结构应该包含两层含义，即数据 的逻辑结构和物理结构。数据结构是在整 个计算机科学与技术领域上广泛被使用的 术语。它用来反映一个数据的内部构成， 即一个数据由哪些成分数据构成，以什么 方式构成，呈什么结构。数据结构是信息 的一种组织方式，其目的是为了提高算法 的效率
5.2数据结构 5.2.2线性表 线性表是最简单、最常用的一种数据 结构,它的逻辑结构是几个数据元素的有 限序列(a1,a,…,an)。线性表的组 成实际上包括两个要素,一是数据本身 一数据元素,它由若干个数据项组成 是数据元素间的联系—元素间的前驱 与后继关系。因此,解决线性表的存储问 题就是要解决数据元素的存储以及元素间 联系的存储
5.2 数据结构 5.2.2 线性表 线性表是最简单、最常用的一种数据 结构，它的逻辑结构是几个数据元素的有 限序列（a1，a2，…，a n）。线性表的组 成实际上包括两个要素，一是数据本身 ――数据元素，它由若干个数据项组成； 二是数据元素间的联系——元素间的前驱 与后继关系。因此，解决线性表的存储问 题就是要解决数据元素的存储以及元素间 联系的存储
5.2数据结构 5.2.3树形结构(层次结构) 树是n(n≥0)个结点的有限集合,当 其非空(n>0)时,有且只有一个特定的结 点称为根,当n1时,其余结点可分为m(m0) 个互不相交的有限集合Tm每一个集合 又是一棵树,称为这个根的子树。特殊地 若限定树的子树最多只能有两棵,且区分为 左、右子树,它就成了另一种树型结构 二叉树。树与二叉树之间有个自然的 对应关系,每一棵树都能惟一地转换到它所 对应的二叉树
5.2 数据结构 5.2.3 树形结构（层次结构） 树是n (n≥0) 个结点的有限集合，当 其非空（n>0）时，有且只有一个特定的结 点称为根，当n>1时，其余结点可分为m(m>0) 个互不相交的有限集合T1…Tm，每一个集合 又是一棵树，称为这个根的子树。特殊地， 若限定树的子树最多只能有两棵，且区分为 左、右子树，它就成了另一种树型结构―― 二叉树 。树与二叉树之间有个自然的一一 对应关系，每一棵树都能惟一地转换到它所 对应的二叉树
5.2数据结构 5.2.4图 逻辑结构 图是一种比线性表和树形结构更为 复杂的数据结构。在线性表中,每个结 点只有一个直接前驱和后继;在树形结 构中,有明显的层次关系,每一层中的 元素只和上一层中的一个元素(即双亲) 相关。而在图中,任意两个元素中均有 可能相关
5.2 数据结构 5.2.4 图 ➢逻辑结构 图是一种比线性表和树形结构更为 复杂的数据结构。在线性表中，每个结 点只有一个直接前驱和后继；在树形结 构中，有明显的层次关系，每一层中的 元素只和上一层中的一个元素（即双亲） 相关。而在图中，任意两个元素中均有 可能相关
5.2数据结构 存储结构 图的结构复杂,存储表示方法也多种 多样,但一般的存储表示法都由明显的两 部分组成,一是存储顶点信息(G),一般 用顶点数组表示(人为给顶点加上编号); 二是存储边的信息(E),当然要与相应的 结点联系在一起。常用的存储表示方法有 数组、邻接表、十字链表等。数组表示法 用两个数组分别存储数据元素(顶点)的 信息相邻矩阵 顶点数组和数据元素之 间关系(边或弧)的信息
5.2 数据结构 ➢存储结构 图的结构复杂，存储表示方法也多种 多样，但一般的存储表示法都由明显的两 部分组成，一是存储顶点信息（G），一般 用顶点数组表示（人为给顶点加上编号）； 二是存储边的信息（E），当然要与相应的 结点联系在一起。常用的存储表示方法有 数组、邻接表、十字链表等 。数组表示法 用两个数组分别存储数据元素（顶点）的 信息相邻矩阵 ——顶点数组和数据元素之 间关系（边或弧）的信息
5.2数据结构 >图的基本操作遍历 和树的遍历类似,图的遍历也是从图 中某一顶点出发,系统地访问图中所有顶 点,且使每一个顶点恰被访问一次。通常 有两种遍历方法:深度优先遍历和广度优 先遍历。 应该注意的是,图的遍历得到的次序 不仅取决于所采用的方法,还取决于从哪 个顶点以及它具体的存储结构
5.2 数据结构 ➢图的基本操作——遍历 和树的遍历类似，图的遍历也是从图 中某一顶点出发，系统地访问图中所有顶 点，且使每一个顶点恰被访问一次。通常 有两种遍历方法：深度优先遍历和广度优 先遍历 。 应该注意的是，图的遍历得到的次序 不仅取决于所采用的方法，还取决于从哪 个顶点以及它具体的存储结构
5.3关系数据库 5.3.1数据处理技术的发展 随着计算机技术的发展,在20世纪50年代 后期至60年代中期,计算机的外存已有磁盘 磁鼓等直接存取的存储设备;软件方面也有了 专门管理数据的软件文件系统,它是操作 系统的一部分。数据管理技术的这一发展阶段 被称为文件系统阶段。在这一阶段,随着数据 管理规模的扩大,数据量急剧增加,文件系统 也显露出了3个缺陷:数据冗余、数据不 致、数据联系弱
5.3 关系数据库 5.3.1 数据处理技术的发展 随着计算机技术的发展，在20世纪50年代 后期至60年代中期，计算机的外存已有磁盘、 磁鼓等直接存取的存储设备；软件方面也有了 专门管理数据的软件——文件系统，它是操作 系统的一部分。数据管理技术的这一发展阶段 被称为文件系统阶段。在这一阶段，随着数据 管理规模的扩大，数据量急剧增加，文件系统 也显露出了3个缺陷：数据冗余 、数据不一 致 、数据联系弱
5.3关系数据库 5.3.2要会使用数据库,我们应掌握些什 么 首先,一个特定的数据库管理系统是以一种 特定的方式来组织、描述和储存数据的,这种对 数据的组织、描述和存储方式,就称为数据模型。 第二,DBMS是一个专门的数据管理软件,它负责 数据的物理存储过程和各种操作的具体实现。第 ,面对一个复杂的应用环境,我们还应该知道 如何去设计好一个数据库—数据库设计理论 最后,作为一个专门管理数据的软件,它不应该 太脆弱,应具有一定的强壮性
5.3 关系数据库 5.3.2 要会使用数据库，我们应掌握些什 么 首先，一个特定的数据库管理系统是以一种 特定的方式来组织、描述和储存数据的，这种对 数据的组织、描述和存储方式，就称为数据模型。 第二，DBMS是一个专门的数据管理软件，它负责 数据的物理存储过程和各种操作的具体实现。第 三，面对一个复杂的应用环境，我们还应该知道 如何去设计好一个数据库 ——数据库设计理论 。 最后，作为一个专门管理数据的软件，它不应该 太脆弱，应具有一定的强壮性