数组和广义表

1、目录5.1多维数组多维数组 5.1.1多维数组的概念多维数组的概念 1一维数组一维数组一维数组可以看成是一个线性表或一个向一维数组可以看成是一个线性表或一个向量（第二章已经介绍），它在计算机内是量（第二章已经介绍），它在计算机内是存放在一块连续的存储单元中，适合于随存放在一块连续的存储单元中，适合于随机查找。这在第二章的线性表的顺序存储机查找。这在第二章的线性表的顺序存储结构中已经介绍。结构中已经介绍。2二维数组二维数组二维数组可以看成是向量的推广。二维数组可以看成是向量的推广。 a00 a01 a0n-1 a10 a11 a1n-1 . am-1 0 am-1 1 am-1 n-1 A= 例

2、如，设例如，设A是一个有是一个有m行行n列的二维数组，列的二维数组，则则A可以表示为：可以表示为：在此，可以将二维数组在此，可以将二维数组A看成是由看成是由m个行向量个行向量X0，X1， ，Xm-1T组成，其中，组成，其中，Xi=( ai0, ai1, .,ain-1)， 0im-1；也可以将二维数组也可以将二维数组A看成是由看成是由n个列向量个列向量Y0, Y1, ,Yn-1组成，其中组成，其中 Yi=(a0i, a1i, .,am-1i)， 0in-1。 由此可知由此可知二维数组二维数组中的每一个元素最多可有中的每一个元素最多可有二个直接前驱和两个直接后继（边界除外），二个直接前驱和两个直

3、接后继（边界除外），故是一种典型的非线性结构。故是一种典型的非线性结构。3多维数组多维数组同理，三维数组最多可有三个直接前驱和三个直同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。是一种非线性结构。5.1.2 多维数组在计算机内的存放多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢？怎样将多维数组中元素存入到计算机内存

4、中呢？由于计算机内存结构是一维的（线性的），因由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中线性序列顺序存放在存储器中 5.2多维数组的存储结构多维数组的存储结构由于数组由于数组一般不作插入或删除操作一般不作插入或删除操作，也就是说，也就是说，一旦建立了数组，则结构中的数组元素个数和元一旦建立了数组，则结构中的数组元素个数和元素之间的关系就不再发生变动，即它们的逻辑结素之间的关系就不再发生变动，即它们的逻辑结构就固定

5、下来了，不再发生变化。因此，采用构就固定下来了，不再发生变化。因此，采用顺顺序存储序存储结构表示数组是顺理成章的事了。本章中，结构表示数组是顺理成章的事了。本章中，仅重点讨论二维数组的存储，三维及三维以上的仅重点讨论二维数组的存储，三维及三维以上的数组可以作类似分析。数组可以作类似分析。多维数组的顺序存储有两种形式：多维数组的顺序存储有两种形式：5.2.1 行优先顺序行优先顺序1存放规则存放规则 行优先顺序也称为低下标优先。具体实现时，行优先顺序也称为低下标优先。具体实现时，按行号从小到大的顺序，先将第一行中元素全按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，

6、部存放好，再存放第二行元素，第三行元素，依次类推依次类推 在在BASIC语言、语言、 PASCAL语言、语言、 C/C+语言等语言等高级语言程序设计中，都是按行优先顺序存放高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的的。例如，对刚才的Amn二维数组，可用如下二维数组，可用如下形式存放到内存：形式存放到内存：a00， a01, a0n-1，a10，a11，.， a1 n-1，am-1 0 ， am-1 1，am-1 n-1。即二维数组按行优先存放到内存后，变成了一即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。个线性序列（线性表）。因此，可以得出多维数组按行优先存放到

7、内存因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是标可以看成是外循环，最右边下标可以看成是最内循环。最内循环。 2地址计算地址计算 由于多维数组在内存中排列成一个线性序列，由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求因此，若知道第一个元素的内存地址，如何求得其它元素的内存地址？得其它元素的

8、内存地址？ 我们可以将它们的地址排列看成是一个等差数列，假我们可以将它们的地址排列看成是一个等差数列，假设每个元素占设每个元素占L个字节，元素个字节，元素aij 的存储地址应为第一的存储地址应为第一个元素的地址加上排在个元素的地址加上排在aij 前面的元素所占用的单元数，前面的元素所占用的单元数，而而aij 的前面有的前面有i行行(0i-1)共共in个元素，而本行前面又个元素，而本行前面又有有j个个(0j-1)元素，故元素，故aij的前面一共有的前面一共有in+j个元素，设个元素，设a00的内存地址为的内存地址为LOC(a00)，则，则aij的内存地址按等差数的内存地址按等差数列计为列计为:L

9、OC(aij)=LOC(a00)+（in+j）L。同理，三维数组同理，三维数组Amnp按行优先存放的地址计算公式按行优先存放的地址计算公式为：为：LOC(aijk)=LOC(a000)+(inp+jp+k)L。5.2.2 列优先顺序列优先顺序1存放规则存放规则列优先顺序也称为高下标优先。具体实现时，列优先顺序也称为高下标优先。具体实现时，按列号从小到大的顺序，先将第一列中元素全按列号从小到大的顺序，先将第一列中元素全部存放好，再存放第二列元素，第三列元素，部存放好，再存放第二列元素，第三列元素，依次类推依次类推 在在FORTRAN语言程序设计中，数组是按列优先语言程序设计中，数组是按列优先顺序

10、存放的。例如，对前面提到的顺序存放的。例如，对前面提到的Amn二维数组，二维数组，可以按如下的形式存放到内存：可以按如下的形式存放到内存：a00， a10， am-10， a01，a11， ， am-1 1， a0 m-1，a1m-1，.， am-1 n-1。 即二维数组按列优先存放到内存后，也变成即二维数组按列优先存放到内存后，也变成了一个线性序列（线性表）。了一个线性序列（线性表）。因此，可以得出多维数组按列优先存放到内存的因此，可以得出多维数组按列优先存放到内存的规律：最右边下标变化最慢，最左边下标变化最规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才

11、快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，最右边下标可以看变化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。成是外循环，最左边下标可以看成是最内循环。2地址计算地址计算 同样与行优先存放类似，若知道第一个元素的内同样与行优先存放类似，若知道第一个元素的内存地址，则同样可以求得按列优存放的某一元素存地址，则同样可以求得按列优存放的某一元素aij的地址。的地址。对二维数组有：对二维数组有：LOC(aij)=LOC(a00)+(jm+i)L对三维数组有：对三维数组有： LOC(aijk)=LOC(a000)+(kmn+jm+i)L题目题目1

12、: 1: 假设有二维数组假设有二维数组A A6x86x8，每个元素用相邻的，每个元素用相邻的6 6 个字节存储，存储器按字节编址。已知个字节存储，存储器按字节编址。已知A A 的起始存储地址（基地址）为的起始存储地址（基地址）为10001000，计算：，计算：数组数组A A的存储量；的存储量；数组数组A A的最后一个元素的最后一个元素a a5757的第一个字节的地址；的第一个字节的地址；按行存储时，元素按行存储时，元素a a1414的第一个字节的地址；的第一个字节的地址；按列存储时，元素按列存储时，元素a a4747的第一个字节的地址；的第一个字节的地址；二维数组二维数组M M 的成员是的成员

13、是6 6个字符（每个字符占一个存储个字符（每个字符占一个存储单元）单元） 组成的串，行下标的范围从组成的串，行下标的范围从0 0到到8 8，列下标的，列下标的范围从范围从1 1到到1010，则，则M M至少需要至少需要_ _ _个字节，个字节，M M 的第的第8 8列列和第和第5 5行共占行共占_个字节，若个字节，若M M 按行优先方式存储，按行优先方式存储，M M 8585的起始地址与的起始地址与M M 按列优先方式存储时的按列优先方式存储时的_元元素的起使地址一致。素的起使地址一致。 A A、 90 ; 114; M5890 ; 114; M58 B B、 180; 54; M89180;

14、 54; M89 C C、 240; 60; M09240; 60; M09 D D、 540; 108; M310540; 108; M310数组数组A A中，每个元素中，每个元素A A 的长度为的长度为3 3个字节，行下标个字节，行下标i i从从1 1到到8 8，列下标，列下标j j从从1 1到到1010 ，从首地址，从首地址SASA开始连开始连续存放在存储器内，该数组按行存放时，元素续存放在存储器内，该数组按行存放时，元素A85A85的起始地址为的起始地址为_。 A A、 SA+141SA+141 B B、 SA+180SA+180 C C、 SA+222SA+222 D D、 SA+2

15、25SA+225二维二维A1020A1020采用列序为主方式存储，每个元素占一采用列序为主方式存储，每个元素占一个存储单元，并且个存储单元，并且A00A00的存储地址是的存储地址是200200，则，则A612A612的地址是的地址是_。二维数组二维数组A10.205.10A10.205.10采用行序为主方式存储，采用行序为主方式存储，每个元素占每个元素占4 4个存储单元，并且个存储单元，并且A105A105的存储地址是的存储地址是10001000，则，则A189A189的地址是的地址是_。 1. 设二维数组设二维数组a610，每个数组元素占用，每个数组元素占用4个存储单元，若按行个存储单元，若

16、按行 优先顺序存放数组元素，优先顺序存放数组元素，a00的存储的地址为的存储的地址为860，则，则a35 的存储地址是（的存储地址是（ ） A. 1000 B. 860 C. 1140 D. 1200AC2. 一个矩阵从一个矩阵从a00开始存放，每个元素占用开始存放，每个元素占用4个存储单元，若个存储单元，若 a78的存储地址为的存储地址为2732，a1316的存储地址为的存储地址为3364，则此，则此 矩阵的存储方式是（矩阵的存储方式是（ ） A. 只能按行优先存储只能按行优先存储 B. 只能按列优先存储只能按列优先存储 C. 按行优先存储或按列优先存储均可按行优先存储或按列优先存储均可 D

17、. 以上都不对以上都不对D3. 在一个二维数组在一个二维数组A中，假设每个数组元素长度为中，假设每个数组元素长度为3个存储单元，个存储单元， 行下标行下标i为为08，列下标，列下标j为为09，从首地址，从首地址SA开始连续存放，此开始连续存放，此 时时A85起始地址为（起始地址为（ ） A. SA+141 B. SA+144 C. SA+222 D. SA+2555.3 特殊矩阵及其压缩存储特殊矩阵及其压缩存储 5.3.1 特殊矩阵特殊矩阵 若一个若一个n阶方阵阶方阵A中元素满足下列条件：中元素满足下列条件： aij=aji 其中其中 0 i, jn-1 ，则称，则称A为对称为对称矩阵。矩阵。

18、1对称矩阵对称矩阵 例如，图例如，图5-1是一个是一个3*3的对称矩阵。的对称矩阵。 A= 643452321 图 5-1 一个对称矩阵 2三角矩阵三角矩阵 （1）上三角矩阵）上三角矩阵即矩阵上三角部分元素是随机的，而下三即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数角部分元素全部相同（为某常数C）或全为）或全为0，具体形式见图，具体形式见图5-2(a)。 图图5-2(a) 上三角矩阵上三角矩阵 11,11,1110,0100.- - - - - - n n n n acccaacaaa （2）下三角矩阵）下三角矩阵即矩阵的下三角部分元素是随机的，而上即矩阵的下三角部分元素是

19、随机的，而上三角部分元素全部相同（为某常数三角部分元素全部相同（为某常数C）或）或全为全为0，具体形式见图，具体形式见图5-2(b)。 111,11,0111000.- - - - -,nnnnaaacaacca 图图5-2(b) 下三角矩阵下三角矩阵 3对角矩阵对角矩阵 若矩阵中所有非零元素都集中在以主对角若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。五对角矩阵、七对角矩阵等。例如，图例如，图5-3为为7 7的三对角矩阵（即有三的

20、三对角矩阵（即有三条对角线上元素非条对角线上元素非0）。）。 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa 图图 5-3 一个一个 7X77X7的三对角矩阵的三对角矩阵 5.3.2 压缩存储压缩存储1对称矩阵对称矩阵 若矩阵若矩阵An n是对称的，对称的两个元素可以共用一个是对称的，对称的两个元素可以共用一个存储单元，这样，原来存储单元，这样，原来n 阶方阵需阶方阵需 n2个存储单元，若个存储单元，若采用压缩存储，仅需采用压缩存储，仅需 n(n+1)/2个存贮单元，

21、将近节约个存贮单元，将近节约一半存贮单元，这就是实现压缩的好处。但是，将一半存贮单元，这就是实现压缩的好处。但是，将n阶阶对称方阵存放到一个向量空间对称方阵存放到一个向量空间s0到到s -1中，我们中，我们怎样找到怎样找到sk与与aij的一一对称应关系呢？使我们在的一一对称应关系呢？使我们在sk中直接找到中直接找到aij。2) 1( + +nn我们仅以行优先存放分两种方式讨论：我们仅以行优先存放分两种方式讨论：例如，图例如，图5-1是一个是一个3*3的对称矩阵。的对称矩阵。 A= 643452321 图 5-1 一个对称矩阵 （1）只存放下三角部分）只存放下三角部分由于对称矩阵关于主对角线对称

22、，故我们只需存放主对由于对称矩阵关于主对角线对称，故我们只需存放主对角线及主对角线以下的元素。这时，角线及主对角线以下的元素。这时，a00存入存入s0，a10 存入存入s1，a11存入存入 s2，具体参见下图。，具体参见下图。aij这时这时sk与与aij的对应关系为的对应关系为: i(i+1)/2+j 当当 ij k= j(j+1)/2+i 当当 ij aijaji下面的对应关系容易推出：当下面的对应关系容易推出：当ij 时，时，aij在下三角部分在下三角部分中，中，aij前面有前面有i行，共有行，共有1+2+3+i个元素，而个元素，而aij是第是第i+1行的第行的第j个元素，即有个元素，即有

23、k=1+2+3+-+i+j=i(i+1)/2+j；当当ij时，交换时，交换i与与j即可。即可。ajiaij(1)2iinjiki- -+-(1)2iin i- - 11122211121110020100.- - - - - -nnnnnaaaaaaaaaa a00 a01 a02 a03 a04 a05 a06 a07 an-2n-2 an-2n-1 an-1n-1 0 1 2 3 4 5 6 7 2) 1( +nn -3 2) 1( +nn -2 2) 1( +nn -1 对称矩阵及用上三角压缩存储 i*n- +j-i 当当ij k= j*n- +i-j 当当ij2) 1( - -ii2)

24、1( - -jj故sk与aij的对应关系为：设有一个设有一个n n n n的对称矩阵的对称矩阵A A，将其上三角部分，将其上三角部分按行存放在一个一维数组按行存放在一个一维数组B B中，中，A00A00存放存放于于B0B0中，那么第中，那么第i+1i+1行的对角元素行的对角元素AiiAii存放于存放于B B中（中（ ）处。）处。 A. (i+3)A. (i+3)* *i/2 i/2 B. (i+1) B. (i+1)* *i/2i/2 C. (2n-i+1) C. (2n-i+1)* *i/2i/2 D. (2n-i-1) D. (2n-i-1)* *i/2i/2C C2三角矩阵三角矩阵 （1

25、）下三角矩阵）下三角矩阵下三角矩阵的压缩存放与对称矩阵用下三角形式存放类下三角矩阵的压缩存放与对称矩阵用下三角形式存放类似，但必须多一个存储单元存放上三角部分元素，使用似，但必须多一个存储单元存放上三角部分元素，使用的存储单元数目为的存储单元数目为n(n+1)/2+1。故可以将。故可以将n n的下三角矩的下三角矩阵压缩存放到只有阵压缩存放到只有n(n+1)/2+1个存储单元的向量中，假个存储单元的向量中，假设仍按行优先存放，这时设仍按行优先存放，这时sk与与aij的对应关系为：的对应关系为： i(i+1)/2+j ij k= n(n+1)/2 ij) 5.4 稀疏矩阵稀疏矩阵按照压缩存储的概念

26、，要存放稀疏矩阵的元素，由于没按照压缩存储的概念，要存放稀疏矩阵的元素，由于没有某种规律，除存放非零元的值外，还必须存贮适当的有某种规律，除存放非零元的值外，还必须存贮适当的辅助信息，才能迅速确定一个非零元是矩阵中的哪一个辅助信息，才能迅速确定一个非零元是矩阵中的哪一个位置上的元素。下面将介绍稀疏矩阵的几种存储方法及位置上的元素。下面将介绍稀疏矩阵的几种存储方法及一些算法的实现。一些算法的实现。 5.4.1 稀疏矩阵的存储稀疏矩阵的存储 1三元组表三元组表在压缩存放稀疏矩阵的在压缩存放稀疏矩阵的非零元非零元同时，若还存放此同时，若还存放此非零元所在的非零元所在的行号行号和和列号列号，则称为，则

27、称为三元组表法三元组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它即称稀疏矩阵可用三元组表进行压缩存储，但它是一种顺序存贮（按行优先顺序存放）。一个非是一种顺序存贮（按行优先顺序存放）。一个非零元有零元有行号、列号、值行号、列号、值，为一个，为一个三元组三元组，整个稀整个稀疏矩阵中非零元的三元组合起来称为三元组表疏矩阵中非零元的三元组合起来称为三元组表。 00070015000001800000240001400003000000000009120- 稀疏矩阵M 2带行指针的链表带行指针的链表 把具有相同行号的非零元用一个单链表连接起把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若

28、干行组成若干个单链表，来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。例如，稀疏矩阵合起来称为带行指针的链表。例如，稀疏矩阵M的带行指针的链表描述形式见下图。的带行指针的链表描述形式见下图。 5.5 广义表广义表 5.5.1基本概念基本概念广义表是第二章提到的线性表的推广。线性表广义表是第二章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是义表中的元素既可以是原子项原子项，也可以是，也可以是子表子表(另一个线性表另一个线性表)。 1广义表的定义广义表的定义广义表是广义表是n0个元素个元素a1，a2，

29、an的有限序列，的有限序列，其中每一个其中每一个ai或者是或者是原子原子，或者是一个，或者是一个子表子表。广义表通常记为广义表通常记为LS=(a1,a2,an)，其中，其中LS为广为广义表的名字，义表的名字，n为广义表的长度，为广义表的长度， 每一个每一个ai为广为广义表的元素。但在习惯中，一般用大写字母表义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。示广义表，小写字母表示原子。2广义表举例广义表举例 (1) A=( ), A为空表，长度为为空表，长度为0。B=(a,（b,c） ), B是长度为是长度为2的广义表，第一项的广义表，第一项 为原子，第二项为子表。为原子，第二

30、项为子表。C=(x,y,z) C是长度为是长度为3的广义表，每一项都是的广义表，每一项都是 原子。原子。(4) D=(B,C) ， D是长度为是长度为2的广义表，每一项都是上的广义表，每一项都是上 面提到的子表。面提到的子表。(5) E=(a,E) 是长度为是长度为2的广义表，第一项为原子，第的广义表，第一项为原子，第 二项为它本身。二项为它本身。 3广义表的表示方法广义表的表示方法 (1) 用用LS=(a1，a2，an)形式，其中每一个形式，其中每一个ai为原子为原子 或广义表或广义表例如：例如： A=(b,c) B=(a,A) E=(a,E) 都是广义表。都是广义表。（2）将广义表中所有子

31、表写到）将广义表中所有子表写到原子形式原子形式，并利用圆括号，并利用圆括号 嵌套嵌套 例如，上面提到的广义表例如，上面提到的广义表A、B、C可以描述为：可以描述为： A (b,c) B (a,(b,c) E (a, (a,（a,）)(3) 将广义表用树和图来描述将广义表用树和图来描述 上面提到的广义表上面提到的广义表A、B、C的描述见下图。的描述见下图。 B A C b a c A b c B a A b c (a) A=(b,c) (b) B=(a,A) (c) C=(A,B) 广义表用广义表用树树或或图图来表示来表示 4广义表的广义表的深度深度 一个广义表的深度是指该广义表展开后所含括号的

32、一个广义表的深度是指该广义表展开后所含括号的层数。层数。例如，例如，A=(b,c)的深度为的深度为1，B=(A,d)的深度为的深度为2，C=(f,B,h)的深度为的深度为3。设有广义表设有广义表D(a,b,D)D(a,b,D)，其长度为，其长度为-，深度为，深度为-.-.广义表广义表(a,(a,b),d,e,(i,j),k)的长度是的长度是_，深度是，深度是_5广义表的广义表的表头、表尾表头、表尾若广义表若广义表LSLS（n=1)n=1)非空，则非空，则a1a1是是LSLS的表头，其余的表头，其余元素组成的表元素组成的表(a(a1 1,a,a2 2, ,a an n) )称为称为LSLS的表尾

33、。的表尾。任何一个非空广义表其任何一个非空广义表其表头可能是原子表表头可能是原子表，也可能，也可能是是广义表广义表，而其，而其表尾必定是广义表表尾必定是广义表。广义表广义表(a),a)的表头是的表头是_，表尾是，表尾是_广义表广义表(a,b),c,d)的表头是的表头是_，表尾是，表尾是_ 广义表广义表(a,b,c,d)的表头是的表头是_，表尾是，表尾是_问：一个广义表由其表头和表尾唯一确定？问：一个广义表由其表头和表尾唯一确定？设设HAEDpHAEDp为求广义表为求广义表p p的表头函数，的表头函数，TAILpTAILp为求广义表为求广义表p p的表尾函数，其中的表尾函数，其中是函数的符是函数的符号，给出下列广义表的运算结果：号，给出下列广义表的运算结果：HEADHEAD（a a，b b，c c） 的结果是的结果是_。TAILTAIL（a,b,ca,b,c） 的结果是的结果是_。HEAD(a),(b)HEAD(a),(b)的结果是的结果是_。TAIL(a),(b)TAIL(a),(b)的结果是的结果是_。HEADTAIL(a,b,c)HEADTAIL(a,b,c)的结果是的结果是_。TAILHEAD(a,b),(c,d)TAILHEAD(a,b),(c,d)的结果是的结果是_。HEADHEAD(a,b),(c,d)HEADHEAD(a,b),(c,d)的结