第5章 数组和广义表

第五章 数组和广义表

讲课提要

【主要内容】

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

【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，?，8，列下标j=1，2，?，10。若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存

储时的元素（ ）的物理地址相同。设每个字符占一个字节。

A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]

解： 二维数A是一个9行10列的矩阵，即A[9][10]。按行存储时，A[8][5]是第85个元素存储的元素。而按列存储时，第85个存储的元素是A[3][10]。即正确答案为B。

2．特殊矩阵压缩存储的意义

在很多科学计算与工程应用中，经常要使用矩阵的概念。矩阵具有与数组相似的性质，如元素数目固定、元素按下标关系有序地排列，所以在编程时可以利用二维数组来存储矩阵，也可以利用程序设计语言中的各种矩阵运算。

在某些情况下，特别是在数值分析中，经常会出现一些阶数很高的矩阵，其中含有许多值相同的元素或零元素，如三角矩阵、对称矩阵、稀疏矩阵等，从节约存储空间的角度考虑，此时若用二维数组存储会造成空间的极大浪费。为了节省存储空间，可以对这类矩阵进行压缩存储。即为对多个相同值的元素只分配一个存储空间，而对零元素可以不分配空间。

3．对称矩阵压缩存储的方法

对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中1≤i , j≤n。 对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。

对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：k=I*(I-1)/2+J-1。给出对称矩阵A中任意元素aij，依据它的下标i和j就可由上述对应关系式确定其在数组M中的位置K，因此aij的地址可由下式计算。

Loc(aij)=Loc(M[K])=Loc(M[0])+K*L=Loc(M[0])+[I*(I+1)/2+J]*L 其中：L为每个数据元素所占的存储单元长度。 I=max(i,j)。 J=min(i,j)。 K=I*(I+1)/2+J。

【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（ ）。

A．

i*(i?1)j*(j?1)i*(i?1)j*(j?1)?j B．?i C．?j D．?i 2222解： 如果aij按行存储，那么它的前面有i-1行，其有元素个数为：

1+2+3+…+（i-1）=i（i-1）/2。同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：

i*(i?1)?j。 2因此答案为A。

4．三角矩阵压缩存储的方法

形如图的矩阵称为三角矩阵，其中c为某个常数。其中下面图(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。

3 c c c c 3 4 8 1 0

6 2 c c c c 2 9 4 6

4 8 1 c c c c 1 5 7

7 4 6 0 c c c c 0 8

c c c c 7 8 2 9 5 7

(a) 下三角矩阵 (b) 上三角矩阵 图4-1 三角矩阵

三角矩阵中的重复元素c可以共享一个存储空间，其余的元素有n(n+1)/2个，因此可压缩存储到向量sa[0..n(n+1)/2]中，c存放在向量的最后一个分量中，排列时以行序为主。aij和sa[k]的对应关系是： 下三角矩阵：

i*(i-1)/2+j-1 当i≥j k= n*(n+1)/2-1 当i

(i-1)*(2n-i+2)/2+j-i 当i≤j k= n*(n+1)/2 当i>j

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。请写出从第一列开始以列序为主序分配方式时在B中确定元素aij的存放位置的公式。

解： 如果aij按列存储，那么它的前面有j-1列，共有元素： n+(n-1)+(n-2)+ ?+[n-(j-2)] =(j-1)*n-

(j?2)(j?1)

2而它又是所在列的第i行，因此在它前的元素个数还得加上i。因此它在一维数组B中的存储顺序为：

(j-1)*n-

(j?2)(j?1)+i

25．稀疏矩阵及其压缩存储的特点

设m*n矩阵中有t个非零元素且t<

6．稀疏矩阵压缩存储的顺序存储方式

以顺序方式组织存储时常用的方法是三元组顺序表，方法是：将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，采用顺序存储方法存储该表。

7．稀疏矩阵压缩存储的链式存储方式 稀疏矩阵压缩存储的链式存储方式，即十字链表。当矩阵中非零元素的个数和位置在使用中经常发生变化时，不宜采用顺序存储结构，可采用十字链表进行存储。其结点结构如图所示。

row down

col v right 图4-2 十字链表的结点结构

8．广义表（列表）的定义、术语及它与线性表的关系 ? 广义表（Generalized Lists）是n（n≥0）个数据元素a1, a2, ? ai, ? , an的有序序列，一般记作：Ls＝（a1, a2, ? ai, ? , an）。

其中：Ls是广义表的名称，n是它的长度，每个ai（1≤i≤n）是Ls的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表Ls的单元素和子表。当广义表Ls非空时，称第一个元素a1为Ls的表头（head），称其余元素组成的表（a2，?，ai，?，an）为Ls的表尾（tail）。

? 表的深度：表中元素的最深嵌套层数。

? 广义表与线性表的关系：当广义表Ls中的元素全部是原子时，广义表即为线性表。因此，可认为线性表是广义表的特例，广义表是线性表的推广。

9．广义表的三个重要性质 （1）广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，? 。

（2）广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。

（3）广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。

10．广义表的存储结构 按结点形式的不同，广义表的链式存储结构可分为两种不同的存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。

11．广义表的基本运算

广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。

此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。

【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（ ）。

A．head(tail(tail(L)))

B．tail(head(head(tail(L)))) C．head(tail(tail(head(L)))) D．head(tail(tail(tail(L))))

解：选项A的结果是字符串“u”；选项B的结果是空表，无字符；选项C的结果是字符“z”；选项D的结果是字符“t”。从所有选项的结果可以看出，ASCII码最大的是字符“z”。因此正确答案是C。

习题4

一、单项选择题

1. 设二维数组A[0?m-1][0?n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ ）。

A.p +[i*n+j-1]*k B.p+[(i-1)*n+j-1]*k C.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k

2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10

的地址为（ ）。

A.520 B.522 C.524 D.518 3. 若数组A[0?m][0?n]按列优先顺序存储，则aij地址为（ ）。 A.LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i]

C.LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1]

4. 若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0?(n+1)n/2]中，则非零元素aij的地址为（ ）。（设每个元素占d个字节）

(j?2)(j?1)+i-1]*d

2(j?2)(j?1)B. [(j-1)*n-+i]*d

2(j?2)(j?1)C．[(j-1)*n-+i+1]*d

2(j?2)(j?1)D．[(j-1)*n-+i-2]*d

2A. [(j-1)*n-5. 设有广义表D=(a,b,D)，其长度为（B ），深度为（ A ）。 A.无穷大 B.3 C.2 D.5 6. 广义表A=（a），则表尾为（ ）。

A.a B.(( )) C.空表 D.(a)

7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（ ）。 A.x B.(a,B) C.(x,(a,B)) D.A 8. 下列广义表用图来表示时，分支结点最多的是（ ）。 A.L=((x,(a,B)),(x,(a,B),y)) B.A=(s,(a,B))

C.B=((x,(a,B),y)) D.D=((a,B),(c,(a,B),D) 9. 通常对数组进行的两种基本操作是（ ）。

A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引

10. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。

A.80 B.100 C.240 D.270

11. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。

A.SA+141 B.SA+144 C.SA+222 D.SA+225 12. 稀疏矩阵一般的压缩存储方法有两种，即（ ）。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表

13. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。

A.正确 B.不正确 14. 一个广义表的表头总是一个（ ）。

A.广义表 B.元素 C.空表 D.元素或广义表 15. 一个广义表的表尾总是一个（ ）。

A.广义表 B.元素 C.空表 D.元素或广义表 16. 数组就是矩阵，矩阵就是数组，这种说法（ ）。 A.正确 B.错误 C.前句对，后句错 D.后句对 二、填空题

1. 一维数组的逻辑结构是_线性结构_，存储结构是_顺序结构_；对于二维或多维数组，分

为_以行为主序_和__以列为主序___两种不同的存储方式。 2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为__ i×n+j个元素位置__。

3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_ 5___，深度为__3__。 4. 一个稀疏矩阵为 ? 0 0 2 0 ? ，则对应的三元组线性表为_（（0，2，2），（1，0，3），

?3000?

?? ?00?15? ??0000??

(2，2，-1），（2，3，5））

5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为___ n×(n+1)/2___。

6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____ e__。

7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为___41____。

8. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是__ head(head(tail(Ls)))__。

9. 三维数组R[c1?d1,c2?d2,c3?d3]共含有__（d1-c1+1）×（d2-c2+1）×（d3-c3+1） __个元素。（其中：c1≤d1,c2≤d2,c3≤d3）

10. 数组A[1?10，-2?6，2?8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为___913__。 三、判断题

1. 数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（× ）数组是查找和修改

2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（√ ） 3. 以行为主序或以列为主序对于多维数组的存储没有影响。（√ ） 4. 对于不同的特殊矩阵应该采用不同的存储方式。（√ ） 5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（× ）

6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（×）

7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（√ ） 8. 距阵中的数据元素可以是不同的数据类型。（× ） 9. 矩阵中的行列数往往是不相等的。（× ）

10. 广义表的表头可以是广义表，也可以是单个元素。（√ ） 11. 广义表的表尾一定是一个广义表。（√ ） 12. 广义表的元素可以是子表，也可以是单元素。（√ ） 13. 广义表不能递归定义。（× ）广义表可以递归遍历 14. 广义表实际上是基本线性表的推广。（√ ） 15. 广义表的组成元素可以是不同形式的元素。（√ ）

1、设广义表L=((a，b，c))，则L的长度和深度分别为（ C ）。

A. 1和1 B. 1和3 C. 1和2 D. 2和3 2、广义表((a),a)的表尾是（ B ）。

A. a B. (a) C. () D. ((a)) 3、稀疏矩阵的常见压缩存储方法有（ C ）两种。

A. 二维数组和三维数组 B. 三元组和散列表 C. 三元组和十字链表 D. 散列表和十字链表 4、一个非空广义表的表头（ D ）。

A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子 5、数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（A ）。

A. 1175 B. 1180 C. 1205 D. 1210 6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ A ）。

A. 3 B. 4 C. 7 D. 8 7、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ B ）。

A. 正确 B. 错误 C. 无法确定 D. 以上均不对

8、广义表(a,b,c)的表尾是（ B ）。

A. b,c B. (b,c) C. c D. (c) 9、常对数组进行两种基本操作是（ C ）。

A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 查找与索引

10、对一些特殊矩阵采用压缩存储的目的主要是为了（ D ）。

A. 表达变得简单 B. 对矩阵元素的存取变得简单

C. 去掉矩阵中的多余元素 D. 减少不必要的存储空间的开销

11、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A. 13 B. 33 C. 18 D. 40

12、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B的下标位置k的值是（ B ）。

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 13、广义表A=((a),a)的表头是（ B ）。

A. a B. (a) C. b D. ((a)) 14、稀疏矩阵一般的压缩存储方法有两种，即（ C ）。

A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表

15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ B ）。

?0?8?0?7A. ?00???50??0?8?0?0C. ?70???50?060??000?

000??400??060??003?

000??400???0?8?0?7B. ??50??00?060??003?

400??000??060??000?

403??000??

?0?8?0?7 D. ??50??00?16、以下有关广义表的表述中，正确的是（ A ）。

A. 由0个或多个原子或子表构成的有限序列 B. 至少有一个元素是子表

C. 不能递归定义 D. 不能为空表 17、对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（D ）。

A. 的 B. e C. (e) D. （e,f） 二、判断题

（× ）1、广义表中原子个数即为广义表的长度。

（ ×）2、一个稀疏矩阵采用三元组表示，若把三元组中有关行下标与列下标的值互换，并把mu和nu的值进行互换，则完成了矩阵转置。 （√ ）3、稀疏矩阵压缩存储后，必会失去随机存取功能。 （× ）4、广义表的长度是指广义表中括号嵌套的层数。 （√ ）5、广义表是一种多层次的数据结构，其元素可以是单原子也可以是子表。 三、填空题

1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是___ Loc(A[0][0])+(i*N+j)*k ____。

2、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是： (x,y,z) 。 3、二维数组，可以按照 列序为主和行序为主 两种不同的存储方式。

4、稀疏矩阵的压缩存储方式有： 三元组 和 十字链表 。 四、综合题

1、现有一个稀疏矩阵，请给出它的三元组表。

?0?1??0??03100210?20?0?? 0??0?答案：

i112334j231233v31121-2

一、基本概念

1、数组地址的计算（一维数组，二维数组）

2、稀疏矩阵的压缩存储方法：三元组表和十字链表（要求会稀疏矩阵的三元组表示） 3、广义表的概念

4、求广义表的深度和长度、求广义表的表头和表尾 二、练习题

3. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。

4. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。 6．求下列广义表操作的结果： (1) GetTail[GetHead[((a,b),(c,d))]];

(2) GetTail[GetHead[GetTail[((a,b),(c,d))]]]

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第5章 数组和广义表在线全文阅读。