20CN网络安全小组论坛 - 编程破解 - 关于用三元组表示的稀疏矩阵相加的实现问题（数据结构）【求助】

论坛: 编程破解标题: 关于用三元组表示的稀疏矩阵相加的实现问题（数据结构）【求助】

作者: myxhyq [myxhyq]

论坛用户

各位大虾，我昨晚~上网查了一晚上的资料，可没有一个网站说了用三元组表示的稀疏矩阵的相加实现问题！
所以求各位大虾帮帮忙，教教我，知道哪个网站有相关问题的留一下网址，知道解决方法的告诉我一下，最好能结合一个实例来说明，这样容易懂一些~~~~
谢谢~~
(听朋友说这个论坛的老大什么都懂，来问就一定能解决的)

地主发表时间: 11/04 12:42

回复: jilian [jilian]

论坛用户

你吧问题再说清楚一点呀

B1层发表时间: 11/04 17:54

回复: myxhyq [myxhyq]

论坛用户

要怎么说呢？
我也不太清楚啊！
是我在做一道题时遇到的困难！就是要求稀疏矩阵用三元组表示，求两个具有相同行列的稀疏矩阵A和B的相加矩阵C并输出C，矩阵C也要用三元组表示~~~~我不知道怎么实现稀疏矩阵（用三元组表示的）的相加。
要不我把题放上来~~~

B2层发表时间: 11/04 18:39

回复: jilian [jilian]

论坛用户

我也不清楚，帮你顶上去

B3层发表时间: 11/05 09:14

回复: 286 [unique]

版主

说实在的,长期不看书,连什么是三元组都早忘十霄云外了。
所以你（包括娃哈哈）问问题之前先简单讲一个你里的的术语是什么意思，让别人回忆回忆。
如果三元组是（行，列，值）的话，我感觉这个问题应该是很容易的呀。哪还用到网上查。自己编一个不就行了。

B4层发表时间: 11/05 09:45

回复: myxhyq [myxhyq]

论坛用户

容易是相对的啊~~~~
我是真的不会~~

B5层发表时间: 11/05 12:23

回复: GNU [gnu]

论坛用户

当初每做三元组算法时，我都在纸上把对应的行列值画个表出来-_-!,不过那样看起来确实直观很多，哈哈

B6层发表时间: 11/05 19:08

回复: myxhyq [myxhyq]

论坛用户

你们好象都是高手哈~~~~
都说些搽边话，这些话我相信谁都会说吧~~~
我都说了，我刚接触数据结构，很多都搞不清楚~~~
懂的就说点实际的，教我一下，或者给我个资料看可那也行吧！！

如果后面的人还是说这个问题太简单，那请不要回帖了，因为我也会说这样的话~~~~~~

B7层发表时间: 11/05 20:36

回复: GNU [gnu]

论坛用户

引用:

你们好象都是高手哈~~~~
都说些搽边话，这些话我相信谁都会说吧~~~
我都说了，我刚接触数据结构，很多都搞不清楚~~~
懂的就说点实际的，教我一下，或者给我个资料看可那也行吧！！

如果后面的人还是说这个问题太简单，那请不要回帖了，因为我也会说这样的话~~~~~~

说实在话，很佩服你认真的学习精神，但~`你应该顾及下别人，不是每个人都在学数据结构，对我而言，我只依稀记得三元组是用来压缩稀疏距阵用的，里面三个元素用来记录原距阵的行、列、值，也只能好心提醒你用画来整理脑子里乱如麻的思维。而且相信你在问这个问题之前自己也尝试写过代码，那~`失败代码为什么不贴上来呢？起码能让没学过数据结构但精通算法的人了解你要干什么嘛。

再说一遍：很佩服你不折不扣的学习态度。

B8层发表时间: 11/05 21:10

回复: 286 [unique]

版主

其实很多情况下,大家都只愿意来这里得到什么,却不愿付出什么,得到了就说声谢谢,得不到就干什么说什么的都有。
作为一个论坛，问得多，回答得少，结果只会越来越冷清，我都说得很明白了。难道你的目的就是得到别人明确的答案？难道你对你的问题就一点想法都没有？如果没有，我也不怕得罪你：给了你你也看不懂。

互相理解是这里应有的气氛，互相帮助是这里应有的现象。

B9层发表时间: 11/06 09:35

回复: kisscjh [kisscjh]

论坛用户

我也是新手，今天我的作业也是这样的。我想我自己能解决的

B10层发表时间: 11/06 15:23

回复: jilian [jilian]

论坛用户

B11层发表时间: 11/06 17:07

回复: Adinia [ayuvi]

论坛用户

我现在也正在学数据结构，看来楼顶的哥哥学的不怎么好啊，只要看书自己能看懂的
看来学数据结构没什么用呀，高手们都忘了

B12层发表时间: 11/06 20:03

回复: myxhyq [myxhyq]

论坛用户

作为一个论坛，问得多，回答得少，结果只会越来越冷清，我都说得很明白了。难道你的目的就是得到别人明确的答案？难道你对你的问题就一点想法都没有？如果没有，我也不怕得罪你：给了你你也看不懂。

我当然是在自己编写时遇到的困难啊，
你们不是说了不要帖代码吗？
你说的话可不象是个斑竹该说的啊~~~
我也知道这个问题很简单，但我确实是不懂~~
我相信接触过数据结构的都知道，（行，列，值）加上就好，但方法呢？

B13层发表时间: 11/06 20:44

回复: 286 [unique]

版主

谁什么时候说过不让贴代码了？是你段章取义，摒弃上下文理解的吧？
在你的眼中，班主就应该天天哄着你，鼓励着你，只挑好的夸，不说一句刺耳的？

B14层发表时间: 11/07 09:47

回复: 286 [unique]

版主

#define MaxSize 10000 //由用户定义
typedef int DataType； //由用户定义
typedef struct { //三元组
int i，j；//非零元的行、列号
DataType v； //非零元的值
}TriTupleNode；

typedef struct{ //三元组表
TriTupleNode data[MaxSize]； //三元组表空间
int m,n，t； //矩阵的行数、列数及非零元个数
}TriTupleTable；
/*-----------------------------------------
以上定义摘自网上,你们可以参考 http://student.zjzk.cn/course_ware/data_structure/web/duoweishuzu/duoweishuzu5.2.3.1.htm
------------------------------------------*/

TriTupleTable A,B,C;//假设下面求C=A+B,假设A,B,C中所有值都按0修理.
int pa=0,pb=0,pc=0;//三个指针,分别用来定义A,B,C三个当前值.

for (pa=0;pa<A.t;pa++)
{//注意:本段比较的是A,B中,相同数量的值.
if (pb==B.t)//如果B的数量少,先结束.
break;
if ((A.data[pa].i < B.data[pb].i) || (A.data[pa].i == B.data[pb].i && A.data[pa].j < B.data[pb].j))
{//复制A中的数据到C.
C.data[pc].i=A.data[pa].i;
C.data[pc].j=A.data[pa].j;
C.data[pc].v=A.data[pa].v;
pc++;
}
else
if (A.data[pa].i == B.data[pb].i && A.data[pa].j == B.data[pb].j)
{//相同位置
if (A.data[pa].v + B.data[pb].v !=0)
{
C.data[pc].i=A.data[pa].i;
C.data[pc].j=A.data[pa].j;
C.data[pc].v=A.data[pa].v+B.data[pb].v;
pb++;
pc++;
}
else
{//相同位置,和为0则不处理.
pb++;
}
}
else
{//复制B的数据到C
C.data[pc].i=B.data[pb].i;
C.data[pc].j=B.data[pb].j;
C.data[pc].v=B.data[pb].v;
pa--;//为什么? -----> :)
pb++;
pc++;
}
}

for (i=pa;i<A.t;i++)
{//如果B数量少,A还未处理完,则把剩下的处理掉.
C.data[pc].i=A.data[i].i;
C.data[pc].j=A.data[i].j;
C.data[pc].v=A.data[i].v;
pc++;
}

for (i=pb;i<B.t;i++)
{//如果A数量少,B还未处理完,则把剩下的处理掉.
C.data[pc].i=B.data[i].i;
C.data[pc].j=B.data[i].j;
C.data[pc].v=B.data[i].v;
pc++;
}

C.t=pc;//C的数量.

/*-----------------------------
以上程序,只一遍写完,并未验证,如有错或考虑不全,请大家指正.
-------------------------------*/

B15层发表时间: 11/07 09:53

回复: shesh [shesh]

版主

好!

B16层发表时间: 11/07 14:16

回复: myxhyq [myxhyq]

论坛用户

我是在做一道题遇到的困难，
这道题要实现两个功能1。用三元组表示稀疏矩阵A和B，且实现矩阵A和B相加后得到的矩阵C的输出2。是输出A的转置矩阵D（都要用三元组表示）
我只实现了第二个功能~~~~~~~
我的想法是，有两个矩阵都要存储值，我在这儿就有点不清楚了！
因为我已经编了下面的程序，我想就插一段程序进去，可怎么把两个矩阵的数值存进去，我就有点搞不清楚了~~~~~~~~

我的程序~~~~~~~~~~~~~~~~~~~~~~~~
我建立的是一个工程：
（SeqSpaMat.h中的内容：）
#include <iostream.h>
#include <stdlib.h>
template<class T> struct Term
{int row;
int col;
T value;
};
template<class T>class SeqSpaMat
{
　　　　friend ostream&operator<<(ostream&out,const SeqSpaMat<T>&a);
　　　　friend istream&operator>>(istream&in,SeqSpaMat<T>&a);
　　　　private:
　　　　　　　　int rows;
　　　　　　　　int cols;
　　　　　　　　Term<T>*arr;
　　　　　　　　int size;
　　　　　　　　int MaxSize;
　　　　public:
　　　　　　　　SeqSpaMat(int maxTerm=100);
　　　　　　　　~SeqSpaMat(void)
　　　　　　　　{delete []arr;};
　　　　　　　　void Transpose(SeqSpaMat<T>&a);
};
template<class T>
SeqSpaMat<T>::SeqSpaMat(int maxTerm)
{if(maxTerm<1)
{
　　　　cout<<"初始化值错！"<<endl;
　　　　exit(1);
}
MaxSize=maxTerm;
arr=new Term<T>[MaxSize];
size=rows=cols=0;
}
template<class T>void SeqSpaMat<T>::Transpose(SeqSpaMat<T>&a)
{int j;
if (size>a.MaxSize)
{
　　　　cout<<"空间不够无法转置"<<endl;
　　　　exit(1);
}
a.cols=rows;
a.rows=cols;
a.size=size;

int *colSize,*rowNext;
colSize=new int[cols];
rowNext=new int[rows];

for(int i=0;i<cols;i++)colSize[i]=0;
for(i=0;i<size;i++)colSize[arr[i].col]++;

rowNext[0]=0;
for(i=1;i<cols;i++)
rowNext[i]=rowNext[i-1]+colSize[i-1];
for(i=0;i<size;i++)
{j=rowNext[arr[i].col]++;
a.arr[j].row=arr[i].col;
a.arr[j].col=arr[i].row;
a.arr[j].value=arr[i].value;
}
delete[]colSize;
delete[]rowNext;
}
template<class T>
ostream&operator<<(ostream&out,const SeqSpaMat<T>&a)
{
　　　　cout<<"矩阵行数为："<<a.rows<<endl;
　　　　cout<<"矩阵列数为："<<a.cols<<endl;
　　　　cout<<"矩阵非零元个数为："<<a.size<<endl;

　　　　cout<<"矩阵非零三元组为："<<endl;
for (int i=0;i<a.size;i++)
cout<<"a("<<a.arr[i].row<<","<<a.arr[i].col<<")="<<a.arr[i].value<<endl;
return out;
}
template<class T>
istream&operator>>(istream&in,SeqSpaMat<T>&a)
{
　　　　cout<<"输入行数、列数和非零元个数：";
　　　　in>>a.rows>>a.cols>>a.size;

　　　　if(a.size>a.MaxSize)
　　　　{cout<<"非零元个数超过了定义的最大值："<<endl;
　　　　exit(1);
　　　　}
for(int i=0;i<a.size;i++)
　　　　{
　　　　　　　　cout<<"输入行号、列号和元素值：";
　　　　　　　　in>>a.arr[i].row>>a.arr[i].col>>a.arr[i].value;
　　　　}
　　　　
return in;
}

原文件中的内容：
#include"SeqSpaMat.h"

void main(void)
{
　　　　SeqSpaMat<int>matricA;
　　　　SeqSpaMat<int>matricB;
　　　　SeqSpaMat<int>matricC;
　　　　SeqSpaMat<int>matricD;

　　　　cin>>matricA;
　　　　cout<<"矩阵A为："<<endl;
　　　　cout<<matricA;

cin>>matricB;
　　　　cout<<"矩阵B为："<<endl;
　　　　cout<<matricB;

　　　　//cout<<"矩阵A与矩阵B相加后得到的矩阵C为"<<endl;
　　　　//cout<<c<<endl;

matricA.Transpose(matricD);
　　　　cout<<"矩阵A转置后的矩阵D为："<<endl;
　　　　cout<<matricD;

}

B17层发表时间: 11/07 15:02

回复: myxhyq [myxhyq]

论坛用户

没有人提意见了吗？

B18层发表时间: 11/08 22:44

论坛: 编程破解