第五章多维数组和广义表 本章学习导读 1多维数组 本章主要介绍多维数组的概念 及在计算机中的存放,特殊矩阵 2多维数组的存储结构 的压缩存储及相应运算,广义表 的概念和存储结构及其相关运算 的实现。通过本章学习,要求掌 3特殊矩阵及其压缩存储如下内容: 多维数组的定义及在计算机 4稀疏矩阵 中的存储表示; 2.对称矩阵、三角矩阵、对角 5广义表 矩阵等特殊矩阵在计算机中的压 缩存储表示及地址计算公式; 3.稀疏矩阵的三元组表示及转 本章小结 置算法实现 4.稀疏矩阵的十字链表表示及 相加算法实现; 5.广义表存储结构表示及基本 运算
第五章 多维数组和广义表 1 多维数组 2 多维数组的存储结构 3 特殊矩阵及其压缩存储 4 稀疏矩阵 5 广义表 本章小结 本章学习导读 本章主要介绍多维数组的概念 及在计算机中的存放，特殊矩阵 的压缩存储及相应运算，广义表 的概念和存储结构及其相关运算 的实现。通过本章学习，要求掌 握如下内容： 1．多维数组的定义及在计算机 中的存储表示； 2．对称矩阵、三角矩阵、对角 矩阵等特殊矩阵在计算机中的压 缩存储表示及地址计算公式； 3．稀疏矩阵的三元组表示及转 置算法实现； 4．稀疏矩阵的十字链表表示及 相加算法实现； 5．广义表存储结构表示及基本 运算
51多维数组 511多维数组的概念 数组是大家都已经很熟悉的一种数据类型,几乎所有高级语言程序设计中都设定 了数组类型。在此,我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式 1.一维数组 维数组可以看成是一个线性表或一个向量(第2章已经介绍),它在计算机内 是存放在一块连续的存储单元中,适合于随机查找。这在第2章的线性表的顺序 存储结构中已经介绍。 2.二维数组 维数组可以看成是向量的推广。例如,设A是一个有m行n列的二维数组,则A 可以表示为: aoo ao1 a10a1 ap A am-10am-11
5.1 多维数组 5.1.1 多维数组的概念 数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定 了数组类型。在此，我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式 。 1．一维数组 一维数组可以看成是一个线性表或一个向量（第2章已经介绍），它在计算机内 是存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序 存储结构中已经介绍。 2．二维数组 二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A 可以表示为： a00 a01 …… a0n-1 a10 a11 …… a1n-1 …………………………. A= am-1 0 am-1 1 …… am-1 n-1
在此,可以将二维数组A看成是由m个行向量X,X1, X1组成, 其中,X(a,a13…an),0≤≤m-1;也可以将二维数组A看成是由n 个列向量Ⅳo2y12……n组成,其中y=(aopa1p…am1),0-n-1。 由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接 后继(边界除外),故是一种典型的非线性结构 3.多维数组 同理,三维数组最多可有三个直接前驱和三个直接后继,三维以上数组 可以作类似分析。因此,可以把三维以上的数组称为多维数组,多维数 组可有多个直接前驱和多个直接后继,故多维数组是一种非线性结构。 512多维数组在计算机内的存放 怎样将多维数组中元素存入到计算机内存中呢?由于计算机内存结构是 维的(线性的),因此,用一维内存存放多维数组就必须按某种次序 将数组元素排成一个线性序列,然后将这个线性序列顺序存放在存储器 中,具体实现方法在下一节介绍
在此，可以将二维数组A看成是由m个行向量[X0，X1， …，Xm-1 ] T组成， 其中，Xi=( ai0 , ai1 , ….,ain-1 )， 0≤i≤m-1；也可以将二维数组A看成是由n 个列向量[y0 , y1 , ……,yn-1 ]组成，其中 yi=(a0i , a1i , …..,am-1i )，0≤i≤n-1。 由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接 后继（边界除外），故是一种典型的非线性结构。 3．多维数组 同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组 可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数 组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。 5.1.2 多维数组在计算机内的存放 怎样将多维数组中元素存入到计算机内存中呢？由于计算机内存结构是 一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序 将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器 中，具体实现方法在下一节介绍
52多维数组的存储结构 由于数组一般不作插入或删除操作,也就是说,一旦建立了数组, 则结构中的数组元素个数和元素之间的关系就不再发生变动,即它 们的逻辑结构就固定下来了,不再发生变化。因此,采用顺序存储 结构表示数组是顺理成章的事了。本章中,仅重点讨论二维数组的 存储,三维及三维以上的数组可以作类似分析。 多维数组的顺序存储有两种形式
5.2 多维数组的存储结构 由于数组一般不作插入或删除操作，也就是说，一旦建立了数组， 则结构中的数组元素个数和元素之间的关系就不再发生变动，即它 们的逻辑结构就固定下来了，不再发生变化。因此，采用顺序存储 结构表示数组是顺理成章的事了。本章中，仅重点讨论二维数组的 存储，三维及三维以上的数组可以作类似分析。 多维数组的顺序存储有两种形式
存放规则 行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现 时,按行号从小到大的顺序,先将第一行中元素全部存放好,再存放 第二行元素,第三行元素,依次类推 在BAS|C语言、 PASCAL语言、C/C++语言等高级语言程序设计中, 都是按行优先顺序存放的。例如,对刚才的Anxn二维数组,可用如 下形式存放到内存:a,a1am1,alo,an,…,a1n1,…,an10 11 a m-1n-1° 即二维数组按行优先存放到内存后,变成 个线性序列(线性表)。 因此,可以得出多维数组按行优先存放到内存的规律:最左边下标变 化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边 下标才变化一次。因此,在算法中,最左边下标可以看成是外循环, 最右边下标可以看成是最内循环
1．存放规则 行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现 时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放 第二行元素，第三行元素，依次类推…… 在BASIC语言、PASCAL语言、C/C++语言等高级语言程序设计中， 都是按行优先顺序存放的。例如，对刚才的Am×n二维数组，可用如 下形式存放到内存：a00，a01,…a0n-1，a10，a11，...， a1 n-1，…，am-1 0 ， am-1 1，…，am-1 n-1。即二维数组按行优先存放到内存后，变成了一 个线性序列（线性表）。 因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变 化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边 下标才变化一次。因此，在算法中，最左边下标可以看成是外循环， 最右边下标可以看成是最内循环
2.地址计算 由于多维数组在内存中排列成一个线性序列,因此,若知道第 个元素的内存地址,如何求得其他元素的内存地址?我们可 以将它们的地址排列看成是一个等差数列,假设每个元素占个 字节,元素a;的存储地址应为第一个元素的地址加上排在a;前 面的元素所占用的单元数,而an的前面有行(0-1)共i×n个元 素,而本行前面又有个元素,故a的前面一共有ixn+个元素, 设a的内存地址为LOc(a),则a的内存地址按等差数列计算 为LOc(a)=LOC(a)+ixnj)×1。同理,三维数组 Amxnx按 行优先存放的地址计算公式为 Loc(an)=LOC(a000(×n×p×p+k)×1
2．地址计算 由于多维数组在内存中排列成一个线性序列，因此，若知道第 一个元素的内存地址，如何求得其他元素的内存地址？我们可 以将它们的地址排列看成是一个等差数列，假设每个元素占l个 字节，元素aij 的存储地址应为第一个元素的地址加上排在aij 前 面的元素所占用的单元数，而aij 的前面有i行(0~i-1)共i×n个元 素，而本行前面又有j个元素，故aij的前面一共有i×n+j个元素， 设a00的内存地址为LOC(a00)，则aij的内存地址按等差数列计算 为LOC(aij)=LOC(a00)+（i×n+j）×l。同理，三维数组Am×n×p按 行优先存放的地址计算公式为： LOC(aijk)=LOC(a000)+(i×n×p+j×p+k)×l
522列优先顺序 1.存放规则 列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时, 按列号从小到大的顺序,先将第一列中元素全部存放好,再存放第二列元 素,第三列元素,依次类推 在 FORTRAN语言程序设计中,数组是按列优先顺序存放的。例如,对前 面提到的Axn二维数组,可以按如下的形式存放到内存:a0,a10 a ar m-1n-1° 即二维数 组按列优先存放到内存后,也变成了一个线性序列(线性表) 因此,可以得出多维数组按列优先存放到内存的规律:最右边下标变化最 慢,最左边下标变化最快,左边下标变化一遍,与之相邻的右边下标才变 化一次。因此,在算法中,最右边下标可以看成是外循环,最左边下标可 以看成是最内循环。 2.地址计算 同样与行优先存放类似,若知道第一个元素的内存地址,则同样可以求得 按列优存放的某一元素a的地址。 对二维数组有:LOC(an)=LOC(ao0+×m+)× 对三维数组有:LOC(an)=LOC(a0+(k×mxn+j×m+
5.2.2 列优先顺序 1．存放规则 列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时， 按列号从小到大的顺序，先将第一列中元素全部存放好，再存放第二列元 素，第三列元素，依次类推…… 在FORTRAN语言程序设计中，数组是按列优先顺序存放的。例如，对前 面提到的Am×n二维数组，可以按如下的形式存放到内存：a00， a10…， am-10， a01，a11， …， am-1 1，…， a0 m-1，a1m-1，...， am-1 n-1。 即二维数 组按列优先存放到内存后，也变成了一个线性序列（线性表）。 因此，可以得出多维数组按列优先存放到内存的规律：最右边下标变化最 慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变 化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可 以看成是最内循环。 2．地址计算 同样与行优先存放类似，若知道第一个元素的内存地址，则同样可以求得 按列优存放的某一元素aij的地址。 对二维数组有：LOC(aij)=LOC(a00)+(j×m+i)×l 对三维数组有： LOC(aijk)=LOC(a000)+(k×m×n+j×m+i)×l
5.3特殊矩阵及其压缩存储 矩阵是一个二维数组,它是很多科学与工程计算问题中研究的数学对 象。矩阵可以用行优先或列优先方法顺序存放到内存中,但是,当矩 阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种 规律时,这时,从节约存储单元出发,可考虑若干元素共用一个存储 单元,即进行压缩存储。所谓压缩存储是指:为多个值相同的元素只 分配一个存储空间,值为零的元素不分配空间。但是压缩存储时,节 约了存储单元,但怎样在压缩后找到某元素呢?因此还必须给出压缩 前的下标和压缩后下标之间变换公式,才能使压缩存储变得有意义
5.3 特殊矩阵及其压缩存储 矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对 象。矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩 阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种 规律时，这时，从节约存储单元出发，可考虑若干元素共用一个存储 单元，即进行压缩存储。所谓压缩存储是指：为多个值相同的元素只 分配一个存储空间，值为零的元素不分配空间。但是压缩存储时，节 约了存储单元，但怎样在压缩后找到某元素呢？因此还必须给出压缩 前的下标和压缩后下标之间变换公式，才能使压缩存储变得有意义
5.31特殊矩阵 对称矩阵 若一个n阶方阵A中元素满足下列条件: an=a1其中0≤,jsn-1.,则称A为对称矩阵。 例如,图5-1是一个3*3的对称矩阵。 2.三角矩阵 (1)上三角矩阵 即矩阵上三角部分元素是随机的,而下三角部分元素全部相同(为某常数C)或 全为0,具体形式见图52(a)。 图5-1一个对称矩阵
1．对称矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 ≤i, j≤n-1 ，则称A为对称矩阵。 例如，图5-1是一个3*3的对称矩阵。 5.3.1 特殊矩阵 2．三角矩阵 （1）上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或 全为0，具体形式见图5-2（a）。 图5-1 一个对称矩阵 A= 3 4 6 2 5 4 1 2 3
(2)下三角矩阵 即矩阵的下三角部分元素是随机的,而上三角部分元素全部相同(为某常数C) 或全为0,具体形式见图5-2(b)。 (a)上三角矩阵 (b)下三角矩阵 c an-In-I 图5-2三角矩阵
（2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C） 或全为0，具体形式见图5-2（b）。 （a）上三角矩阵 （b）下三角矩阵 图5-2 三角矩阵 1 0 1 1 1 1 1 0 1 1 0 0 ... ... ... ... ... ... ... n− n− n− n− a a a a a c a c c 1 1 1 1 1 1 0 0 0 1 0 1 ... ... ... ... ... ... − − − − n n n n c c c a c a a a a a