高效简洁的三元组稀疏矩阵乘法.pdf

include#include#define max_element 4/元素加一int a,b,ic,n;/N 矩阵维数ia 变量行，ib 变量列int ln;/因子序号typedef struct int row;/行int col;/列int element;/元素数据mat;int data_234=3,0,2,5,0,1,;int data_143=3,0,1,5,1 ;int data_344=0;void mat_print(mat in_mat);void mat_trans(mat in_mat,mat out_mat);void hash_mat_multiply(mat in_mat1,mat in_mat2,mat out_mat);int main()int ia,ib,a_acc,b_acc;a_acc=0;b_acc=0;mat amax_element+1;mat bmax_element+1;mat c17=0;a0.row=max_element;a0.col=max_element-1;a0.element=0;b0.row=max_element-1;b0.col=max_element;b0.element=0;for(ia=0;ia4;ia+)for(ib=0;ib3;ib+)if(data_1iaib!=0)a0.element+;aa_acc.row=ia;aa_acc.col=ib;aa_acc.element=data_1iaib;if(data_2ibia!=0)b0.element+;b+b_acc.row=ib;bb_acc.col=ia;bb_acc.element=data_2ibia;mat_print(a);mat_print(b);hash_mat_multiply(a,b,c);/主要乘法函数mat_print(c);while(1);mat_trans(a,b);mat_print(b);return 0;void mat_print(mat in_mat)int ia;for(ia=0;ia=in_mat0.element;ia+)printf(%dt%dt%dn,in_matia.row,in_matia.col,in_matia.element);printf(n);void mat_trans(mat in_mat,mat out_mat)/转置函数，没用哈 int ia,ib,j;int row_termmax_element-1=0;int start_pmax_element-1=0;out_mat0.row=in_mat0.col;out_mat0.col=in_mat0.row;out_mat0.element=in_mat0.element;for(ia=1;iamax_element;ia+)/1.统计特定列的数量 row_termin_matia.col+;start_p0=1;/0 列开始位置为1 for(ia=1;iamax_element-1;ia+)/2.计算各定列初始位置 start_pia=start_pia-1+row_termia-1;for(ia=1;iamax_element;ia+)j=start_pin_matia.col+;/3.计算原始列的对应行out_matj.row=in_matia.col;out_matj.col=in_matia.row;out_matj.element=in_matia.element;void hash_mat_multiply(mat in_mat1,mat in_mat2,mat out_mat)int ia,ib,ib2,a,b,m1,n1,n2,p2;int out_mat_top=0;/缓存输出3 元组栈顶指向将要压入的三元组int temp4=0;/mat2列数缓存，数字4 应设为 b 组列数m1=in_mat10.row;n1=in_mat10.col;n2=in_mat20.row;p2=in_mat20.col;a=in_mat10.element;b=in_mat20.element;out_mat0.row=m1;out_mat0.col=p2;/*一种时间效率与外文数据结构教科书同速，但简洁易懂的稀疏矩阵三元组乘法方案，且不需要转置by 钟礼浩华工电信学院*两个稀疏组的元素通过变量ia ib 进行两两相乘，在a 组未变行前压入b 列数大小的*缓存组 temp 中，在变行前一一压入输出三元组out_mat 中*a 组变行后清空temp，等待下一行的数据处理。*/for(ia=1;ia=a;ia+)/进行 a 组元素扫描 for(ib=1;ib=b;ib+)/进行 b 组元素扫描 if(in_mat1ia.col=in_mat2ib.row)/若 a列=b 行则有效用，可以相乘 tempin_mat2ib.col+=in_mat1ia.element*in_mat2ib.element;/压入缓存 if(ia!=a&in_mat1ia.row!=in_mat1ia+1.row)|ia=a)/如果 a要变行或是最后一行 for(ib2=0;ib24;ib2+)/扫描缓存组 if(tempib2!=0)/如果该点不是0 out_mat+out_mat_top.row=in_mat1ia.row;/输出组栈顶自加，压入各个变量out_matout_mat_top.col=ib2;out_matout_mat_top.element=tempib2;out_mat0.element+;tempib2=0;/清空该缓存