数组与广义表的压缩存储练习解析

"本资源为第5章关于数组和广义表的练习题，涵盖了特殊矩阵、稀疏矩阵、二维数组存储方式、对称矩阵压缩存储、数组元素位置计算以及广义表操作等内容。" 在计算机科学中，数组和广义表是两种重要的数据结构，它们在处理大量数据时扮演着关键角色。以下是对这些练习题中涉及知识点的详细解释： 1. **特殊矩阵和稀疏矩阵**： - 特殊矩阵如对角矩阵、单位矩阵等，其中大部分元素为0，少数元素为非零。这些矩阵通常可以高效地存储和处理。 - **稀疏矩阵**是指非零元素数量远小于总元素数量的矩阵。为了节省存储空间，稀疏矩阵通常采用压缩存储，如三元组表或压缩链接列表。在压缩存储后，由于元素的存储位置不再与原始坐标对应，因此失去了随机存取的功能。 2. **二维数组存储**： - 二维数组的存储方式有两种：按行存储和按列存储。在按行存储时，元素M[3][5]的起始地址与按列存储时的某个元素相同。由于题目没有给出具体的列存储顺序，答案可能是根据元素位置计算得出的。题目中提到的选项可能需要根据具体的存储方式来确定。 3. **对称矩阵的压缩存储**： - 对于对称矩阵，只需要存储上三角或下三角部分即可，因为其余部分是对称的。假设矩阵的下三角元素按行存储，a11为第一个元素，存储地址为1，那么a85的位置可以通过计算得出。对于10阶矩阵，a85在下三角的第8行第5列，其位置可以通过公式计算：`(i-1)*i/2 + j`，这里的i和j分别是行和列的索引。 4. **对称矩阵下三角元素的位置计算**： - 对于下三角元素aij (i < j)，在数组B中的位置k可以通过公式 `j*(j-1)/2 + i` 计算得出。这是因为元素是按照列优先的顺序存储的。 5. **对称矩阵上方元素的存储位置**： - 当矩阵A的对角线上方的元素以列为主的次序存储时，元素aij (1 ≤ i, j ≤ n, 且 i ≤ j) 的位置可以用公式 `j(j-l)/2 + i - 1` 来计算。 6. **二维数组到一维数组的映射**： - 二维数组A[i, j]转换为一维数组B中的下标通常是 `(i-1)*n + j`，这是行优先的存储方式。 7. **稀疏矩阵的三元组表示**： - 一个100*90的稀疏矩阵，如果有10个非0元素，用三元组表示时，每个三元组需要存储行索引、列索引和值，一共3个整数。每个整数占2字节，所以10个元素需要10 * 3 * 2 = 60字节，加上可能存在的结束标记，总字节数可能是66字节。 8. **广义表的操作**： - 广义表是一种可以包含其他表的数据结构，类似于链表的递归形式。要从广义表L中取出原子项t，需要先取L的第二个元素（也就是tail(L)），然后取这个元素的第一个元素（即head(tail(L))），最后再取这个元素的第一个元素（head(head(tail(L)))）。 这些练习题涵盖了数组和广义表的基本概念和操作，对于理解这两种数据结构及其在存储和运算中的优化方法至关重要。在实际编程中，理解和掌握这些知识可以帮助我们更有效地处理数据，提高算法的效率。