文档介绍：第5章多维数组和广义表
数据结构(C++描述)
广义表
特殊矩阵及其压缩存储
稀疏矩阵
退出
目录
一维数组可以看成是一个线性表或一个向量(第二章已经介绍),它在计算机内是存放在一块连续的存储单元中,适合于随机查找。这在第二章的线性表的顺序存储结构中已经介绍。
二维数组可以看成是向量的推广。
例如,设A是一个有m行n列的二维数组,则A可以表示为:
在此,可以将二维数组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。
由此可知二维数组中的每一个元素最多可有二个直接前驱和两个直接后继(边界除外),故是一种典型的非线性结构。
同理,三维数组最多可有三个直接前驱和三个直接后继,三维以上数组可以作类似分析。因此,可以把三维以上的数组称为多维数组,多维数组可有多个直接前驱和多个直接后继,故多维数组是一种非线性结构。
多维数组在计算机内的存放
怎样将多维数组中元素存入到计算机内存中呢?由于计算机内存结构是一维的(线性的),因此,用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列,然后将这个线性序列顺序存放在存储器中
由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,则结构中的数组元素个数和元素之间的关系就不再发生变动,即它们的逻辑结构就固定下来了,不再发生变化。因此,采用顺序存储结构表示数组是顺理成章的事了。本章中,仅重点讨论二维数组的存储,三维及三维以上的数组可以作类似分析。
多维数组的顺序存储有两种形式:
行优先顺序
行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时,按行号从小到大的顺序,先将第一行中元素全部存放好,再存放第二行元素,第三行元素,依次类推……
在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。即二维数组按行优先存放到内存后,变成了一个线性序列(线性表)。
因此,可以得出多维数组按行优先存放到内存的规律:最左边下标变化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次。因此,在算法中,最左边下标可以看成是外循环,最右边下标可以看成是最内循环。
由于多维数组在内存中排列成一个线性序列,因此,若知道第一个元素的内存地址,如何求得其它元素的内存地址?我们可以将它们的地址排列看成是一个等差数列,假设每个元素占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。
列优先顺序
列优先顺序也称为高下标优先或右边下标优先于左边下标。具体实现时,按列号从小到大的顺序,先将第一列中元素全部存放好,再存放第二列元素,第三列元素,依次类推……
在FORTRAN语言程序设计中,数组是按列优先顺序存放的。例如,对前面提到的Am×n二维数组,可以按如下的形式存放到内存:a00, a10…, am-10, a01,a11, …, am-1 1,…, a0 m-1,a1m-1,..., am-1 n-1。即二维数组按列优先存放到内存后,也变成了一个线性序列(线性表)。
因此,可以得出多维数组按列优先存放到内存的规律:最右边下标变化最慢,最左边下标变化最快,左边下标变化一遍,与之相邻的右边下标才变化一次。因此,在算法中,最右边下标可以看成是外循环,最左边下标可以看成是最内循环。
同样与行优先存放类似,若知道第一个元素的内存地址,则同样可以求得按列优存放的某一元素aij的地址。
对二维数组有:LOC(