本文主要是介绍特殊矩阵的处理 实验5:稀疏矩阵ADT的十字链表实现,矩阵乘法/加法/转置,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
稀疏矩阵ADT的实现:
在现实应用中,一些规模很大的特殊矩阵具有重要的地位。特殊矩阵可以采用二维数组存储,简单直接(顺序存储方式保持了矩阵中元素之间的二维线性关系),矩阵操作的算法都很简单,但是其空间的利用率很低(因为重复元素或零元素比较多)。 稀疏矩阵就是一种应用很广泛的特殊的矩阵,在实现稀疏矩阵ADT时通常采用“压缩”存储方案,即把只存储稀疏矩阵的非零元素,把稀疏矩阵抽象成为一个以三元组(行,列,值)为数据元素的线性表来处理,而我们知道:线性表可以采用顺序存储,也可以采用链式存储(通常用十字链表)。
现要求编程实现稀疏矩阵在“压缩”存储时的常用操作,如输出、转置、求和、乘等。(注:在代码注释中说明你采用的存储结构)
需要输入两个矩阵,完成:
(1) 转置。对第一个矩阵进行转置并输出,前面输出标题 “The transformed matrix is:”
(2) 矩阵加。如两个矩阵可以相加,进行两个矩阵加并输出,前面输出标题 “The added matrix is:”
如果不能相加输出 “Can not add!”;
(3) 矩阵乘。如果两个矩阵可以相乘,进行两个矩阵乘并输出,前面输出标题 “The product matrix is:”
如果不能相乘输出 “Can not multiply!”
矩阵的输入:有多行,第1行包括三个整数,分别是矩阵的大小m,n及非零元素的个数r。后面r行分别输入各个非零元素的 行、列、值。
矩阵的输出:有两种形式,操作时分别用符号“L”、“H”指出输出形式。
L: 以三元组的形式输出,即先输出矩阵的行数、列数和非零元素个数,再依次输出各个非零元素的行、列和值。
H: 按人们习惯的矩阵格式输出,即输出一个m*n的矩阵,是零元素的输出0,非零元素输出元素值。设定每个元素占位宽度为4。(要输出行号和列号,并对齐)
例如:输入如下:
10 8 4 //第1个矩阵 10行,8列,4个非零元素
1 8 1 //第1行第8列元素值为1
3 3 2 //第3行第3列元素值为2
3 7 3 //第3行第7列元素值为3
10 1 4 //第10行第1列元素值为4
10 8 2 //第2个矩阵 10行,8列,2个非零元素
2 6 1 //第2行第6列元素值为1
3 7 -3 //第3行第7列元素值为-3
H //输出格式类别
输出如下:
The transformed matrix is:
1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 0 0 0 0 4
2 0 0 0 0 0 0 0 0 0 0
3 0 0 2 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0
7 0 0 3 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 0 0 0
The added matrix is:
1 2 3 4 5 6 7 8
1 0 0 0 0 0 0 0 1
2 0 0 0 0 0 1 0 0
3 0 0 2 0 0 0 0 0
4 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0
10 4 0 0 0 0 0 0 0
Can not multiply!
思路:
1.使用结构体实现
(1)存储:位置(i,j),值aij
(2)输出操作:先将结构体按i排序,再按j排序,然后输出方式类似以下代码的输出
(3)转置:所有结构体的i,j互换,再次排序
(4)加法:两重循环遍历i,j,在满足:x1>=i,y1>=j的条件下更新矩阵M1的(x1,y1)值,矩阵M2同矩阵M1也更新(x2,y2),若x1=i,y2=j则将M1的aij的值放到求和后的矩阵M3中,矩阵M2同M1,若x1=x2,y1=y2,则将两元素求和后的值放到M3中。M3排序
(5)乘法:类似加法的更新操作,做矩阵的乘法操作。
2.使用十字链表,见代码
给组测试用例
Input:
3 3 7
1 1 3
1 2 2
2 1 2
2 2 3
2 3 2
3 2 2
3 3 3
3 3 7
1 1 1
1 3 3
2 2 2
2 3 4
3 1 3
3 2 4
3 3 3
L
Output:
The transformed matrix is:
Rows=3,Cols=3,r=7
1 1 3
1 2 2
2 1 2
2 2 3
2 3 2
3 2 2
3 3 3
The added matrix is:
Rows=3,Cols=3,r=9
1 1 4
1 2 2
1 3 3
2 1 2
2 2 5
2 3 6
3 1 3
3 2 6
3 3 6
The product matrix is:
Rows=3,Cols=3,r=9
1 1 3
1 2 4
1 3 17
2 1 8
2 2 14
2 3 24
3 1 9
3 2 16
3 3 17
///使用十字链表实现
#include <iostream>
#include <cstdio>using namespace std;const int maxn=10000;
typedef int etype;
struct node
{int r,c;etype val;node *right,*down,*left,*up;node(int r,int c,int val=0){this->val=val;this->r=r,this->c=c;right=down=left=up=NULL;}
};class CrossLinks
{
public:int row,col,cnt;node *h[maxn];///头节点CrossLinks(){}CrossLinks(int r,int c,int n);void push
这篇关于特殊矩阵的处理 实验5:稀疏矩阵ADT的十字链表实现,矩阵乘法/加法/转置的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!