数据结构答案第6章多维数组和广义表学习指导

《数据结构答案第6章多维数组和广义表学习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第6章多维数组和广义表6.1知识点分析1.多维数纽概念多维数组是向量的推广，对于二维数组A吋n既可以看成m行向量组成的向量，也可以看成n行向量组成的向量。多维数组在计算机屮有两种存储形式：按行优先顺序存储和按列优先顺序存储。2.多维数组的存储二维数组ajj的地址为：LOC（aij）=LOC（a00）+（ixn+j）xd（0下标起始的语言）三维数组的地址为:LOC（aijk）=LOC（a00o）+（（ixnxp+jxp+k）xd（0下标起始的语言）d为每个数据元索占有的字节数。3.特殊矩阵在矩阵中非零元素或零元素的分布冇一定规律

2、的矩阵称为特殊矩阵，如三角矩阵、对称矩阵、稀疏矩阵等。当矩阵的阶数很大时，川普通的二维数纽存储这些特殊矩阵将会占川很多的存储单元。从节约存储空间的角度考虑，以下特殊矩阵的存储方法。（1）对称矩阵对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：驹=却（0

3、元素，且t远小于mxn,这样的矩阵称稀疏矩阵。为了节约存储空间，稀疏矩阵中零元素无需存储，只需存储炬阵中的非零元素。稀疏矩阵常用的有:三元纟R表存储、带行指针的链表存储、I•字琏表存储等存储方法。4.广义表广义表是n（n>0）个数据元素的有序序列，广义表的元素可以是单元素，也可以是一个广义表。山于广义表的元素有两种形式，所以其结点的存储形式也有两种：（1）表结点由标,忐域、表头指针域、表尾指针域组成。（2）原了结点由标志域和值域组成。5.广义表与线性表的区别和联系线性表是具有相同类型的n个数据元素的有限序列，记为②、a2.a3

4、ano广义表也是n个数据元素的有限序列，记为a】、a2.a3ano线性表中的元素必须具有相同的类型，而广义表中的成员，既可以是单个元素（原子），也可以是一个广义表（子表）。当广义表屮的每一个％元素都是数据元素，且具有相同类型时，则它就是一个线性表，因此可以说广义表是线性表的一种推广，或者说线性表是广义表的一个特例。6.2典型习题分析【例1】设二维数组A5X6的每个元索占4个字节，存储器按字节编址。已知A的起始地址为2000,计算：（1）数组的大小？（2）A的终端结点知的存储地址？（3）按行优先顺序存储吋，迦5的存储地址？（4）

5、按列优先顺序存储时，a?5的存储地址？答：(1)数组的大小(即数组A共占多少字节):5x6x4=120Bo(2)—个结点ay的存储地址是该结点所占用的存储空间的第1个字节的地址(即起始地址),它等于：基地址+排在ay之前的结点个数x每个结点所占用的字节数。345的起始地址:LOC(a45)=2000+(4x6+5)x4=2116(3)在按行优先顺序存储吋，排在a.j之前的结点的个数为：在前i行(即0〜i・l行)上共有im个结点，在第i行上aqZ前冇j个结点(0〜j・l列)。所以按行优先存储的地址计算公式为:LOC(aij)=L

6、OC(a0o)+(ixn+j)xdLOC(a25)=2000+(2x6+5)x4=2068(4)在按列优先顺序存储时，排在a"之前的结点的个数为：在前j列(即0〜j・l列)上共有个结点，在第j列上a：」之前有i个结点(Si・l行)。所以按列优先存储的地址计算公式为：LOC(aq)=LOC(a0o)+(jxm+i)xdLOC(a25)=2000+(5x5+2)x4=2108【例2】特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存储功能？为什么？答：对于像三角矩阵等特殊矩阵由于压缩存储时将具存储在一个线性数组向量屮，矩阵元素砌的下标

7、i,j与它在向呆屮的对应元素bk下标k有一对应关系，故不会失去随机存储功能。而像稀疏矩阵，其压缩存储的方式是将其非零元索存储在一个三元组小，以三元组数组a[k]形式存储，矩阵元素％下标i,j与数组中对应元素a[k]行下标k无对应关系，故失去随机存储功能。【例3】求矩阵的转置矩阵分析：对于一个mm的矩阵Agn，其转置矩阵是一个nxm的矩阵Bm，.RB[i][j]=A[j][i]，0

8、++)B[j][i]=A[i][j];}【例4】求两个矩阵的乘分析：设两个矩阵相乘：C=AxB,其中A是一个mm的矩阵，B是一个nxk的矩阵，贝IJC为一个mxk的矩阵。其函数如卜"：voidmut(C,A,B)maxixA,B,C;{inti,j,k；for(i=0;i