第5章 数组和广义表.docx
11页
第五章 数组和广义表讲课提要【主要内容】1．多维数组的顺序存储结构2．特殊矩阵的压缩存储 3．广义表的定义及其与线性表的关系4．广义表的存储结构 5．广义表运算实现中递归的应用 【教学目标】1．掌握多维数组的顺序存储结构2．掌握特殊矩阵的压缩存储方法 3．掌握广义表的定义及其与线性表的关系4．掌握广义表的存储结构 5．了解广义表运算实现中递归的应用学习指导1．多维数组的顺序存储结构 对于多维数组，有两种存储方式：一是以行为主序(或先行后列)的顺序存放，如BASIC、PASCAL、C等程序设计语言 中用的是以行为主的顺序分配，即一行分配完了接着分配下一行另一种是以列为主序(先列后行)的顺序存放，如 FORTRAN 语言中，用的是以列为 主序的分配顺序，即一列一列地分配以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后， 右边第二个下标再变，„，从右向左，最后是左下标以列为主序分配的规律是：最左边的 下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，„ 从左向右，最 后是右下标不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数， 就可以将数组元素的存储地址表示为其下标的线性函数。
设有mxn二维数组A，以“以 mn 行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下设数组的基址为LOC(all)，每个数组元素占据L个地址单元，计算a”.的物理地址的函 数为：LOCO/ = LOC(a11) + ( (i-l)*n + j-1 ) * L同理，对于三维数组A，即mXnXp数组，对于数组元素a其物理地址为：mnp ijkLOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L注意：在C语言中，数组中每一维的下界定义为0贝I」：LOC(a詁=LOC(a00) + ( i*n + j ) * L【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，„，8,列 下标j=1，2,„, 10若A以行为主序存储元素，A⑻⑸的物理地址与当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]⑸是第85 个元素存储的元素而按列存储时，第85个存储的元素是A[3][10]。
即正确答案为B2．特殊矩阵压缩存储的意义 在很多科学计算与工程应用中，经常要使用矩阵的概念矩阵具有与数组相似的性质 如元素数目固定、元素按下标关系有序地排列，所以在编程时可以利用二维数组来存储矩阵， 也可以利用程序设计语言中的各种矩阵运算在某些情况下，特别是在数值分析中，经常会出现一些阶数很高的矩阵，其中含有许 多值相同的元素或零元素，如三角矩阵、对称矩阵、稀疏矩阵等，从节约存储空间的角度考 虑，此时若用二维数组存储会造成空间的极大浪费为了节省存储空间，可以对这类矩阵进 行压缩存储即为对多个相同值的元素只分配一个存储空间，而对零元素可以不分配空间3．对称矩阵压缩存储的方法对称矩阵的特点是：在一个n阶方阵中，有a..=a..,其中1Wi, jWnij ji对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可对于对称矩阵中的任意元素aj若令I=max(i,j), J=min(i,j)，则将上面两个式子综合起 来得到：k=I*(I-1)/2+J-1给出对称矩阵A中任意元素a”.，依据它的下标i和j就可由上述 对应关系式确定其在数组M中的位置K,因此a..的地址可由下式计算ijLoc(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) + jb. j*(2-1)+i2c. i*([+1) + jD.解:如果霸按行存储，那么它的前面有i-1行，其有元素个数为:i *(i -1)21+2+3+・・・+ (i-1) =i (i-1) /2同时它又是所在行的第j歹U，因此它排列的顺序还得加上j，一维数组B[n (n+1)/2]中的位置k与其下标的关系是:因此答案为A4. 三角矩阵压缩存储的方法形如图的矩阵称为三角矩阵，其中c为某个常数其中下面图(a)为下三角矩阵：主对角 线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们 的压缩存储方法r3cccc3481062cccc2946481cccc1577460cccc0882957cccc7JI.(a)下三角矩阵(b)上三角矩阵图4-1三角矩阵三角矩阵中的重复元素c可以共享一个存储空间，其余的元素有n（n+l）/2个，因此可压缩存储到向量sa[0..n（n+1）/2]中，c存放在向量的最后一个分量中，排列时以行序为主。
a和 ijsa[k啲对应关系是:下三角矩阵上三角矩阵k=k=i*(i-1)/2+j-1当i三jn*(n+1)/2-1当i
7．稀疏矩阵压缩存储的链式存储方式稀疏矩阵压缩存储的链式存储方式，即十字链表当矩阵中非零元素的个数和位置在使 用中经常发生变化时，不宜采用顺序存储结构，可采用十字链表进行存储其结点结构如图 所示rowcolvdownright图4-2十字链表的结点结构8．广义表（列表）的定义、术语及它与线性表的关系广义表（Generalized Lists）是n （n三0）个数据元素a「a2，„ a『…,an的有序序列, 一般记作：Ls=（a「a2, „ 气，…,an）其中：Ls是广义表的名称，n是它的长度，每个a. (lWiWn)是Ls的成员，它可以是i单个元素，也可以是一个广义表，分别称为广义表Ls的单元素和子表当广义表Ls非空时， 称第一个元素a1为Ls的表头(head)，称其余元素组成的表(a2，…，a.,…，a)为Ls的l 2 i n表尾( ta.l)・表的深度：表中元素的最深嵌套层数•广义表与线性表的关系：当广义表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(ta.l(ta.l(L)))B．ta.l(head(head(ta.l(L))))C．head(ta.l(ta.l(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个字节，则元素a..的地址为()ijA.p +[i*n+j-1]*k B.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k2. 已知二维数组A10x10中，元素a20的地址为560,每个元素占4个字节，则元素a10 的地址为( )A.520 B.522 C.524 D.5183. 若数组A[0„m][0„n]按列优先顺序存储，则a..地址为()A.LOC(a )+[j*m+i] B. LOC(a )+[j*n+i]C.LOC(%) + [(j-l)*n+i-l] D. LOC(ao)+ [(j-l)*m+i-l]4.若下三角矩阵A”&,按列顺序压缩存储在数组Sa[0„(n+l)n/2]中，则非零元素aij的地址为()设每个元素占d个字节) "(j - 2)( j -1)A. [(j-1)*n- +i-1]*dB.[(j-1)*n-(j - 2)( j -1)2+i]*dC．[(j-1)*n-(j- 2)( j-1)2+i+1]*d(j-2)(j-1)D. [(j-1)*n- 2 +i-2]*d5. 设有广义表D=(a,b,D),其长度为(B ),深度为(A )。
A.无穷大 B. 3 C. 2 D. 56. 广义表A= (a),则表尾为()A.a B.(( )) C.空表 D.(a)7. 广义表 A=((x,(a,。
