中南大学数据结构与算法第5章数组和广义表课后作业答案.doc

第5章数组与广义表习题练习答案 5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000 。?解：　　按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置)　　a0000　　a0001　　a0002?　　a0010　　a0011　　a0012?　　a0100　　a0101　　a0102?　　a0110　　a0111　　a0112?　　a0200　　a0201　　a0202?　　a0210　　a0211　　a0212?　　a1000　　a1001　　a1002?　　a1010　　a1011　　a1012?　　a1100　　a1101　　a1102?　　a1110　　a1111　　a1112?　　a1200　　a1201　　a1202?　　a1210　　a1211　 　a1212??? 按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：　　a0000 　a1000　　a0100 　a1100　　a0200 　a1200　　a0010 　a1010　　a0110 　a1110　　a0210 　a1210　　a0001 　a1001　　a0101 　a1101　　a0201 　a1201　　a0011 　a1011　　a0111 　a1111　　a0211 　a1211　　a0002 　a1002　　a0102 　a1102　　a0202 　a1202　　a0012 　a1012　　a0112 　a1112　　a0212　 a0212 5.2 给出C语言的三维数组地址计算公式。解：　　因为C语言的数组下标下界是0，所以　　　　Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d　　其中 Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。 5.3 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：　　(1)用i , j 表示k的下标变换公式。　　(2)用 k 表示 i,j 的下标变换公式。　(1) 解：?　　要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为：　　　　(i*3-1)+j-(i+1)?　　其中 (i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数　　化简可得：　　　　k=2i+j; // c下标是从0开始的。　(2) 解：　　 因为K和i,j是一一对应的关系，因此这也不难算出：　　　　i=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行号　　　　j=(k+1)%3+(k+1)/3-1 //k+1除以3的余数就是表示当前行中第几个非零元素，　　　　　　　　　　　　　　　　//加上前面的0元素所点列数就是当前列号 5.4 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?解：? (1)因含5*6=30个元素，因此A共占30*4=120个字节。? (2)a45的起始地址为：???? Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116? (3)按行优先顺序排列时，???? a25=1000+(2*6+5)*4=1068? (4)按列优先顺序排列时：(二维数组可用行列下标互换来计算)???? a25=1000+(5*5+2)*4=1108 5.5 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?答：??? 后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 5.6 简述广义表和线性表的区别与联系。答:??? 广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。 5.7 画出下列广义表的图形表示：