分简少少能的少与的少简分 第三章 非线性数据结构
第三章 非线性数据结构
分简少少能的少与的少简分 目录 3.1数组 ☆3.2树 3.3图
❖ 3.1 数组 ❖ 3.2 树 ❖ 3.3 图 计 目录 算机软件基础
3.1多维数组 多维数组的定义 二维以上的数组 数组( array)在高级语言中 是作为一种数据类型介绍的,而在 本节中数组是作为一种常用数据结 构来介绍的
计 算 机 软 件 基 础 3．1 多维数组 一．多维数组的定义 二维以上的数组 。 注意：数组（array）在高级语言中 是作为一种数据类型介绍的，而在 本节中数组是作为一种常用数据结 构来介绍的 。
数组的逻辑结构(以二维数组为例) 分析:二维数组中的每一个元素既受到 行关系的制约,又受到列关系的制约。 若只考虑其中的一个关系,则对于任意 元素,直接前驱和直接后继都是唯一的, 即行、列关系都是线性的。 多维数组可看成是线性表的推广, 其逻辑关系是非线性的,实质上是多个 线性关系的组合
计 算 机 软 件 基 础 二. 数组的逻辑结构（以二维数组为例） 分析：二维数组中的每一个元素既受到 行关系的制约，又受到列关系的制约。 若只考虑其中的一个关系，则对于任意 元素，直接前驱和直接后继都是唯一的， 即行、列关系都是线性的。 结论：多维数组可看成是线性表的推广， 其逻辑关系是非线性的，实质上是多个 线性关系的组合。
多维数组的存储结构 采用顺序存储结构实现。 原因:多维数组一经定义,其元素 个数就固定不变。 顺序存储的次序: 行优先: PASCAL、C语言 列优先: FORTRAN语言
计 算 机 软 件 基 础 三．多维数组的存储结构 采用顺序存储结构实现 。 原因：多维数组一经定义，其元素 个数就固定不变。 ❖顺序存储的次序： 行优先：PASCAL、C语言 列优先：FORTRAN语言
四.矩阵的存储方法 1普通矩阵的存储方法: 采用相应的二维数组实现。 2.特殊矩阵的存储方法: 思考:两类 特殊矩阵的 今研究对象(两类特殊矩阵)}共同特点是 三角矩阵和稀疏矩阵什么? 采用压缩存储的方法实现
计 算 机 软 件 基 础 四．矩阵的存储方法 1.普通矩阵的存储方法： 采用相应的二维数组实现 。 2.特殊矩阵的存储方法： ❖ 研究对象（两类特殊矩阵） 三角矩阵和稀疏矩阵 采用压缩存储的方法实现 。 思考：两类 特殊矩阵的 共同特点是 什么？
(1)三角矩阵的压缩存储 分析:三角矩阵中非0元素的分布有规 律。 结论:可按照一定的顺序依次将三角矩 阵中所有非0元素存储在连续的存储空 间中。 非0元素在存储空间中的存放 位置k与其在原矩阵中的行、列位置间 存在着一一对应的关系
计 算 机 软 件 基 础 （1）三角矩阵的压缩存储 分析：三角矩阵中非0元素的分布有规 律。 结论：可按照一定的顺序依次将三角矩 阵中所有非0元素存储在连续的存储空 间中。 可行性：非0元素在存储空间中的存放 位置k与其在原矩阵中的行、列位置间 存在着一一对应的关系。
例如:对下三角矩阵A按行优先顺序对其 进行压缩存储 a11 a21a22 A a31a32 a33 an1 an2 an3 a l1a21a22313233|. m1 pn2 An3 nn 2345 mm+I m+2 m
计 算 机 软 件 基 础 例如：对下三角矩阵A按行优先顺序对其 进行压缩存储。 A = n 1 n 2 n 3 n n 3 1 3 2 3 3 2 1 2 2 1 1 a a a ... a ... ... ... ... a a a a a a a11 a21 a22 a31 a32 a33 …. …. aij …. …. an1 an2 an3 …. …. ann 0 1 2 3 4 5 …. …. k …. …. m m+1 m+2 …. …. m+n
矩阵中第i行第列的元素a;存放在 维数组的哪个位置? k=i×(i-1)/2+j-1
计 算 机 软 件 基 础 思考： 矩阵中第i行第j列的元素aij存放在 一维数组的哪个位置？ k=? k= i ( i - 1) / 2 + j-1
(2)稀疏矩阵的压缩存储 分析:稀疏矩阵中非0元素的分布无规律。 结论:可按照一定的顺序依次将稀疏矩阵 中所有非0元素存储在连续的存储空间中 但必须在存储非0元素值的同时设法记下其 在矩阵中的位置。 三元组法 存放每个非0元素的值及其在原矩阵中 的行、列位置三项信息
计 算 机 软 件 基 础 （2）稀疏矩阵的压缩存储 分析：稀疏矩阵中非0元素的分布无规律。 结论：可按照一定的顺序依次将稀疏矩阵 中所有非0元素存储在连续的存储空间中， 但必须在存储非0元素值的同时设法记下其 在矩阵中的位置。 可行的方法之一：三元组法 存放每个非0元素的值及其在原矩阵中 的行、列位置三项信息。