第五章 数组、特殊矩阵和广义表
本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。
5.1 多维数组
5.1.1 数组的逻辑结构
数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。图5.1是一个m行n列的二维数组。
数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：
(1) 取值操作：给定一组下标，读其对应的数据元素。
(2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。
我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。
5.1.2 数组的内存映象
现在来讨论数组在计算机中的存储表示。通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。 a11 a12 … a1n
a21 a22 … a2n
… … … …
am1 am2 … amn
图5.1 m行n列的二维数组 A= 对于一维数组按下标顺序分配即可。
对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。
第五章 数组和广义表
讲课提要
【主要内容】
1．多维数组的顺序存储结构
2．特殊矩阵的压缩存储
3．广义表的定义及其与线性表的关系
4．广义表的存储结构
5．广义表运算实现中递归的应用
【教学目标】
1．掌握多维数组的顺序存储结构
2．掌握特殊矩阵的压缩存储方法
3．掌握广义表的定义及其与线性表的关系
4．掌握广义表的存储结构
5．了解广义表运算实现中递归的应用
学习指导
1．多维数组的顺序存储结构
对于多维数组，有两种存储方式：
一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。
另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。
以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，„，从右向左，最后是左下标。以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，„，从左向右，最后是右下标。
不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有m×n二维数组Amn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。
设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算aij 的物理地址的函数为：
LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * L
同理，对于三维数组Amnp，即m×n×p数组，对于数组元素aijk其物理地址为：
LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L
注意：在C语言中，数组中每一维的下界定 义为0，则：
LOC(aij) = LOC(a00) + ( i*n + j ) * L
第五章 数组和广义表
一、选择题
1、设广义表L=((a，b，c))，则L的长度和深度分别为（ ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3
2、广义表((a),a)的表尾是（ ）。
A. a B. (a) C. () D. ((a))
3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40
4、一个非空广义表的表头（ ）。
A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子
5、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ ）。
A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j
6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ ）。
A. 3 B. 4 C. 7 D. 8
7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ ）。
A. 正确 B. 错误 C. 无法确定 D. 以上均不对
8、常对数组进行两种基本操作是（ ）。
A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 查找与索引
9、对一些特殊矩阵采用压缩存储的目的主要是为了（ ）。
A. 表达变得简单 B. 对矩阵元素的存取变得简单
C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间的开销
第五章 数组与广义表
一、 假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000。计算：
1、数组A的体积（即存储量）；
2、数组A的最后一个元素a57的第一个字节的地址；
3、按行存储时，元素a14的第一个字节的地址；
4、按列存储时，元素a47的第一个字节的地址；
答案：
1、（6*8）*6=288
2、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=1282
3、loc(a14)=1000+(1*8+4)*6=1072
4、loc(a47)=1000+(7*6+4)*6=1276
二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？
（1）a0000 (2)a1111 (3)a3125 (4)a8247
答案：（1）100
（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776
(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784
(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416
五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。
答：
K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i
=(i-1)(n+(n-i+2))/2+j-i
所以f1(i)=(n+1/2)i-1/2i2
f2(j)=j
c=-(n+1)
九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。（对角线求和）
