数据结构-第7次课第五章数组和广义表(压缩存储).ppt

第五章 数组和广义表 典型题举例 1. 将一个A[1…100, 1…100]的三对角矩阵，按行优先顺序存入一维数组B[1…298]中，A中元素a66,65（即该元素下标i = 66, j = 65）在B数组中的位置K为_______。 A. 198 B. 195 C. 197 典型题举例 2. 二维数组A的每个元素是由6个字符组成的串，其行下标i = 0、1、2、…、8，列下标j = 1、2、3、…、10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素_______的起始地址相同。设每个字符占一个字节。 A. A[8,5] B. A[3,10] C. A[5,8] D.A[0,9] 典型题举例 3. 下面________属于特殊矩阵。 A. 对角矩阵 B. 上三角矩阵 C. 下三角矩阵 D. 稀疏矩阵 E. 对称矩阵 在经典算法中，不论M(I,k)和N(k,j)的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作。 即为求Q的值，只需在M.data和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。 3 0 0 7 0 0 -1 0 -1 -2 0 0 0 0 0 2 M= 0 0 -2 0 -1 0 0 -3 0 0 -1 0 0 0 0 0 0 0 3 0 N= 1 1 3 1 4 7 2 3 -1 3 1 -1 3 2 -2 4 4 2 1 3 -2 1 5 -1 2 3 -3 3 1 -1 4 4 3 方法： 1）形成积矩阵 0 0 -6 21 -3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2）形成矩阵N的num,pot 1 2 3 4 5 num 2 1 1 1 0 pot 1 3 4 5 6 3）计算 对M三元组1第一个开始向后扫描，与第二个三元 组N处理pot[k]到pot[k+1]的一段元素相乘（k为M的列号） (-1)*(-1) 3 0 0 7 0 0 -1 0 -1 -2 0 0 0 0 0 2 M= 0 0 -2 0 -1 0 0 -3 0 0 -1 0 0 0 0 0 0 0 3 0 N= 1 1 3 1 4 7 2 3 -1 3 1 -1 3 2 -2 4 4 2 1 3 -2 1 5 -1 2 3 -3 3 1 -1 4 4 3 方法： 1）形成积矩阵 0 0 -6 21 -3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2）形成矩阵N的num,pot 1 2 3 4 5 num 2 1 1 1 0 pot 1 3 4 5 6 3）计算 对M三元组1第一个开始向后扫描，与第二个三元 组N处理pot[k]到pot[k+1]的一段元素相乘（k为M的列号） 3 0 0 7 0 0 -1 0 -1 -2 0 0 0 0 0 2 M= 0 0 -2 0 -1 0 0 -3 0 0 -1 0 0 0 0 0 0 0 3 0 N= 1 1 3 1 4 7 2 3 -1 3 1 -1 3 2 -2 4 4 2 1 3 -2 1 5 -1 2 3 -3 3 1 -1 4 4 3 方法： 1）形成积矩阵 0 0 -6 21 -3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2）形成矩阵N的num,pot 1 2 3 4 5 num 2 1 1 1 0 pot 1 3 4 5 6 3）计算 对M三元