第5次作业题目

问题 A : 算法5-1：稀疏矩阵转置

时间限制：1 秒 内存限制：32 兆 特殊判题： 否 提交：101 解决： 47

题目描述

稀疏矩阵的存储不宜用二维数组存储每个元素，那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零元素。这个一维数组的元素类型是一个三元组，由非零元素在该稀疏矩阵中的位置（行号和列号对）以及该元组的值构成。

矩阵转置就是将矩阵行和列上的元素对换。

现在就请你对一个稀疏矩阵进行转置。以下是稀疏矩阵转置的算法描述：

图：稀疏矩阵转置的算法描述

输入格式

输入的第一行是两个整数r和c（r*c <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行，每行有c个整数，表示这个稀疏矩阵的各个元素。

输出

输出c行，每行有r个整数，每个整数后跟一个空格。该结果为输入稀疏矩阵的转置矩阵。

样例输入

6 7

0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0

0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0

样例输出

0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0

问题 B : 算法5-2：稀疏矩阵快速转置

题目描述

稀疏矩阵的存储不宜用二维数组存储每个元素，那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零元素。这个一维数组的元素类型是一个三元组，由非零元素在该稀疏矩阵中的位置（行号和列号对）以及该元组的值构成。

而矩阵转置就是将矩阵行和列上的元素对换。参考算法5.1中的具体做法，令mu和nu分别代表稀疏矩阵的行数和列数，不难发现其时间复杂度为O(mu×nu)。而当非零元的个数tu与mu×nu同数量级时，算法5.1的时间复杂度将上升至O(mu×nu2)。因此，需要采用快速的稀疏矩阵转置算法。

现在就请你实现一个快速的对稀疏矩阵进行转置的算法。以下是稀疏矩阵快速转置的算法描述：

输入格式

输入的第一行是两个整数r和c（r<200, c<200, r*c <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行，每行有c个整数，用空格隔开，表示这个稀疏矩阵的各个元素。

输出

输出为读入的稀疏矩阵的转置矩阵。输出共有c行，每行有r个整数，每个整数后输出一个空格。请注意行尾输出换行。

样例输入

6 7

0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0

样例输出

0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0

0 0 14 0 0 0 0 0 0 0 0 0

问题 C : 算法5-3：行逻辑链接的矩阵乘法

时间限制：1 秒 内存限制：32 兆 特殊判题： 否 提交：35 解决： 12

题目描述

对于一个稀疏矩阵，当需要频繁的随机存取任意一行的非零元时，则需要知道每一行的第一个非零元在三元组表中的位置。为此，可以将算法5.2中用来指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。这种“带行链接信息”的三元组表即为行逻辑链接的顺序表。其类型描述如下：

针对存储于行逻辑链接顺序表的稀疏矩阵，其矩阵相乘的算法与经典算法有所不同。因此，对于两个稀疏矩阵相乘(Q=M×N)的过程可以大致描述如下：

请使用行逻辑链接的顺序表实现两个稀疏矩阵的乘法。

输入格式

输入的第一行是两个整数r1和c1（r1<200, c1<200, r1*c1 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r1行，每行有c1个整数，用空格隔开，表示第一个稀疏矩阵的各个元素。

之后的一行有两个整数r2和c2（c1=r2<200, c2<200, r2*c2 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r2行，每行有c2个整数，用空格隔开，表示第二个稀疏矩阵的各个元素。

输出

输出两个矩阵的乘积。输出共有r1行，每行有c2个整数，每个整数后输出一个空格。请注意行尾输出换行。

样例输入

4 5

0 0 0 69 78 0 0 5 0 0 0 0 0 0 0

0 91 2 0 82 5 6

0 18 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 41 0 0 47 62 0 0 0 0 0 0 0 35

样例输出

0 0 3243 4278 0 2730 0 0 0 0 0 205 0 0 0 0 0 0 0 0 6097 0 0 2952

提示[+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

问题 D : 算法5-4：采用十字链表存储的稀疏矩阵

时间限制：1 秒 内存限制：32 兆 特殊判题： 否 提交：18

解决： 17

题目描述

当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储的结构来表示三元组的线性表了。因此，在这种情况下，采用链式存储结构表示三元组更为恰当。十字链表就是能够实现这样功能的一种数据结构。

在十字链表中，每个非零元可以用一个包含5个域的结点表示。其中i、j和e这3个域分别表示该非零元所在的行、列和非零元的值，向右域right用来链接同一行中下一个非零元，而向下域down用来链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表。每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵通过这样的结构形成了一个十字交叉的链表。

稀疏矩阵的十字链表类型可以描述如下：

下面是建立稀疏矩阵十字链表的算法描述：

给出一个稀疏矩阵，请将其存储到一个十字链表中，并将存储完毕的矩阵输出。

输入格式

输入的第一行是两个整数r和c（r<200, c<200, r*c <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行，每行有c个整数，用空格隔开，表示稀疏矩阵的各个元素。

输出

输出读入的矩阵。输出共有r行，每行有c个整数，每个整数后输出一个空格。请注意行尾输出换行。

样例输入

5 6

0 18 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 41 0 0 47 62 0 0 0 0 0 0 0 35

样例输出

0 18 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 41 0 0 47 62 0 0 0 0 0 0 0 35

提示[+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

输出读入的矩阵。输出共有r行，每行有c个整数，每个整数后输出一个空格。请注意行尾输出换行。

样例输入

5 6

0 18 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 41 0 0 47 62 0 0 0 0 0 0 0 35

样例输出

0 18 0 0 0 0 0 0 67 0 0 0 0 0 0 0 0 41 0 0 47 62 0 0 0 0 0 0 0 35

提示[+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

本文来源：https://www.bwwdw.com/article/lhcd.html