import java.util.*;
创新互联建站企业建站,十多年网站建设经验，专注于网站建设技术，精于网页设计，有多年建站和网站代运营经验，设计师为客户打造网络企业风格，提供周到的建站售前咨询和贴心的售后服务。对于成都网站建设、网站制作中不同领域进行深入了解和探索，创新互联在网站建设中充分了解客户行业的需求，以灵动的思维在网页中充分展现，通过对客户行业精准市场调研，为客户提供的解决方案。
//稀疏矩阵算法。
//稀疏矩阵算法是为了在大型矩阵中非零元素少时，减少存贮空间，并提高矩阵运算速度的。
//但本例中的矩阵只是为了演示算法，都比较小，时间和空间效率提升可以忽略。
public class SparseMatrix{
public static void main(String[] args){
TripleSMatrix tsm=new TripleSMatrix(7,4);
//tsm.printTriple();
tsm.printMatrix();
TripleSMatrix tsm2=new TripleSMatrix(7,4);
System.out.println("矩阵a:");
tsm.printMatrix();
System.out.println("矩阵b:");
tsm2.printMatrix();
int[][] matrixSum=addSMatrix(tsm,tsm2);
System.out.println("矩阵a+矩阵b:");
for(int i=0;i matrixSum.length;i++){
for(int j=0;j matrixSum[i].length;j++){
System.out.print(" "+matrixSum[i][j]);
}
System.out.println("");
}
}
public static int[][] addSMatrix(TripleSMatrix t1,TripleSMatrix t2){ //计算两个三元组表示的矩阵之和，返回结束数组
if(t1.rows!=t2.rows||t1.columns!=t2.columns){
System.out.println("这两个矩阵不能相加");
return null;
}
int[][] c=new int[t1.rows][t2.columns];
int i=1,j=1;
while(i =t1.nonzeroElements||j =t2.nonzeroElements){
if(t1.triple[i][0] t2.triple[j][0]i =t1.nonzeroElements){
c[t1.triple[i][0]-1][t1.triple[i][1]-1]=t1.triple[i][2];
i++;
}else if(t2.triple[j][0] t1.triple[i][0]j =t2.nonzeroElements){
c[t2.triple[j][0]-1][t2.triple[j][1]-1]=t2.triple[j][2];
j++;
}else{
if(t1.triple[i][1] t2.triple[j][1]i =t1.nonzeroElements){
c[t1.triple[i][0]-1][t1.triple[i][1]-1]=t1.triple[i][2];
i++;
}else if(t1.triple[i][1]t2.triple[j][1]j =t2.nonzeroElements){
c[t2.triple[j][0]-1][t2.triple[j][1]-1]=t2.triple[j][2];
j++;
}else{
c[t1.triple[i][0]-1][t1.triple[i][1]-1]=t1.triple[i][2]+t2.triple[j][2];
i++;j++;
}
}
}
return c;
}
}
//下面的类定义不一定是最好的，比如其中的属性大多是包访问权限，可以改进。
class TripleSMatrix{ //定义了一个三元组的类。
int[][] triple=new int[2001][3]; //三元组数组，假设稀疏矩阵的值都是整数。最多可以有2000个非零元素。第零行没有用。
int rows,columns,nonzeroElements; //稀疏矩阵的行列数和非零元素个数。
TripleSMatrix(int rows,int columns){ //构造方法，rows是稀疏矩阵的行数，columns是稀疏矩阵的列数。
Scanner input=new Scanner(System.in);
System.out.println("请输入稀疏矩阵三元组");
System.out.println("以行 列 值的形式输入，如：1 2 4表示第1行第2列元素的值为4，当输入的行为999时结束：");
int count=1;
int i=0,j,v; //i行j列,值v
while(i!=999input.hasNext()){
i=input.nextInt();
j=input.nextInt();
v=input.nextInt();
if(irows||i 1||jcolumns||j 1){
System.out.println("刚才的行，列值错，将被忽略");
continue;
}
triple[count][0]=i;
triple[count][1]=j;
triple[count][2]=v;
count++;
}
this.rows=rows;
this.columns=columns;
this.nonzeroElements=count-1;
sortTriple(triple,1,count); //对输入的三元组排序。
}
static void sortTriple(int[][] triple,int first,int end){ //对三元组排序方法，按行排，行一样按列排。
Arrays.sort(triple,first,end,new Comparator int[](){
public int compare(int[] t1,int[] t2){
if(t1[0]t2[0]) return 1;
if(t1[0] t2[0]) return -1;
if(t1[0]==t2[0]) return t1[1]-t2[1];
return 0; //没有用的一个语句，但没有它编译通不过。
}
});
}
public void printMatrix(){ //打印出当前三元组表示的稀疏矩阵。
int row=1,column=1; //row当前要打印的行，column当前要打印的列。
for(int t=1;t =nonzeroElements;t++){
while(triple[t][0]row){ //三元组中的行比当前行大
if(column!=1){ //前面打印的行没有打印完，继续打印完
for(;column =columns;column++) System.out.print(" "+0);
column=1; //新的一行列从1开始。
}else{ //当前行全为0
for(int i=1;i =columns;i++){
System.out.print(" "+0);
}
}
System.out.println(""); //换行
row++; //下一行
}
for(;column triple[t][1];column++){ //当前打印的列小于三元组中的列，前面要补零。
System.out.print(" "+0);
}
System.out.print(" ".substring(0,6-(String.valueOf(triple[t][2])).length())+triple[t][2]); //打印三元组对应的元素。
column++;
}
if(column!=1){ //前面打印的行没有打印完，继续打印完
for(;column =columns;column++) System.out.print(" "+0);
System.out.println("");
column=1;
row++ ;
}
for(;row =rows;row++){ //三元组中没有对应的值了，矩阵后面的元素全为0
for(column=1;column =columns;column++){
System.out.print(" "+0);
}
System.out.println("");
}
}
public void printTriple(){ //打印三元组
for(int i=1;i =nonzeroElements;i++){
for(int j=0;j 3;j++){
System.out.print(triple[i][j]+" ");
}
System.out.println("");
}
}
}
★稀疏矩阵运算器源代码：
#include stdio.h
#define MAXSIZE 1000
#define MAXRC 100
typedef struct
{
int i,j;
int e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int rpos[MAXRC+1];//存放各行第一个非零元在存储数组中的位置，若该行无非零元，则其rpos[]值为零
int mu,nu,tu;
}RLSMatrix;
ScanRLSMatrix(RLSMatrix *T)
{//矩阵输入函数，输入各行非零元及其在矩阵中的行列数
int k;
printf(" ***********************************************************\n");
printf(" 请输入矩阵的行数，列数，非零元素个数 \n");
printf(" ");
scanf("%d,%d,%d",(*T).mu,(*T).nu,(*T).tu);
if((*T).tuMAXSIZE){printf("非零个数超出定义范围！");exit(0);}
for(k=1;k=(*T).tu;k++){
printf(" 按行存储请输入第%d个非零元素的行数,列数,其值:",k);
scanf("%d,%d,%d",(*T).data[k].i,(*T).data[k].j,(*T).data[k].e);
if(!(*T).data[k].i||!(*T).data[k].j||(*T).data[k].i(*T).mu||(*T).data[k].j(*T).nu){
printf("输入有误！");
exit(0);
}
}
printf(" ************************************************************\n");
//计算各行第一个非零元素在存储数组中的位置
//若该行无非零元，则rpos[]值为零
int num[(*T).mu+1],row,cpot[(*T).mu+1];
cpot[1]=1;
for(k=1;k=(*T).mu;k++)
num[k]=0;
for(k=1;k=(*T).tu;k++)
++num[(*T).data[k].i];
for(row=2;row=(*T).mu;row++)
cpot[row]=cpot[row-1]+num[row-1];
for(row=1;row=(*T).mu;row++){
if(cpot[row]=(*T).tu)
if((*T).data[cpot[row]].i==row){
(*T).rpos[row]=cpot[row];
}
else
(*T).rpos[row]=0;
else
(*T).rpos[row]=0;
}
}
PrintRLSMatrix(RLSMatrix T)
{//矩阵输出函数，输出矩阵形式
int a,b,m=0;
printf(" -----------------------------------------\n");
for(a=1;a=(T).mu;a++){printf(" ");
for(b=1;b=(T).nu;b++){
if((T).rpos[a]a==(T).data[(T).rpos[a]].ib==(T).data[(T).rpos[a]].j){
//(T).rpos[a]不为零时，输出该行的非零元
printf("%4d",(T).data[(T).rpos[a]].e);
(T).rpos[a]++;
}
else
{
printf("%4d",m);}
}
printf("\n");
}
printf(" ----------------------------------------\n");
}
FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q)
{//矩阵快速转置
int col,t,p,q,num[M.nu],cpot[M.nu];
(*Q).mu=M.nu;(*Q).nu=M.mu;(*Q).tu=M.tu;
if((*Q).tu){
for(col=1;col=M.nu;++col)num[col]=0;
for(t=1;t=M.tu;++t)++num[M.data[t].j];//求M中每一行含非零元素的个数
cpot[1]=1;
//求第col列中第一个非零元在(*Q).data中的序号
for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p=M.tu;++p){
col=M.data[p].j;q=cpot[col];
(*Q).data[q].i=M.data[p].j;
(*Q).data[q].j=M.data[p].i;
(*Q).data[q].e=M.data[p].e;
++cpot[col];
}
}
//计算各行第一个非零元素在存储数组中的位置
//若该行无非零元，则rpos[]值为零
int Num[(*Q).mu+1],row,Cpot[(*Q).mu+1],k;
Cpot[1]=1;
for(k=1;k=(*Q).mu;k++)
Num[k]=0;
for(k=1;k=(*Q).tu;k++)
++Num[(*Q).data[k].i];
for(row=2;row=(*Q).mu;row++)
Cpot[row]=Cpot[row-1]+Num[row-1];
for(row=1;row=(*Q).mu;row++){
if(Cpot[row]=(*Q).tu)
if((*Q).data[Cpot[row]].i==row){
(*Q).rpos[row]=Cpot[row];
}
else
(*Q).rpos[row]=0;
else
(*Q).rpos[row]=0;
}
return 1;
}
HeRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)
{//矩阵求和函数
if((*M).mu!=(*N).mu||(*M).nu!=(*N).nu)
{printf("不满足矩阵相加的条件!");return 0;}
int k=1;
Triple *p,*q;
//设置两个指针，分别指向M，N的第一个非零元位置，移动指针进行比较，得出相加后的新矩阵非零元
p=(*M).data[1];
q=(*N).data[1];
while(p(*M).data+(*M).tu+1q(*N).data+(*N).tu+1)
if((*p).i=(*q).i)
if((*p).i(*q).i){
(*Q).data[k].i=(*p).i;
(*Q).data[k].j=(*p).j;
(*Q).data[k].e=(*p).e;
k++;p++;
}
else
if((*p).j=(*q).j)
if((*p).j(*q).j){
(*Q).data[k].i=(*p).i;
(*Q).data[k].j=(*p).j;
(*Q).data[k].e=(*p).e;
k++;p++;
}
else
{
(*Q).data[k].i=(*p).i;
(*Q).data[k].j=(*p).j;
(*Q).data[k].e=(*p).e+(*q).e;
k++;p++;q++;
}
else {
(*Q).data[k].i=(*q).i;
(*Q).data[k].j=(*q).j;
(*Q).data[k].e=(*q).e;
k++;q++;
}
else
{
(*Q).data[k].i=(*q).i;
(*Q).data[k].j=(*q).j;
(*Q).data[k].e=(*q).e;
k++;q++;
}
if(p=(*M).data+(*M).tu)
while(p=(*M).data+(*M).tu){
(*Q).data[k].i=(*p).i;
(*Q).data[k].j=(*p).j;
(*Q).data[k].e=(*p).e;
k++;p++;
}
if(q=(*N).data+(*N).tu)
while(q=(*N).data+(*N).tu){
(*Q).data[k].i=(*q).i;
(*Q).data[k].j=(*q).j;
(*Q).data[k].e=(*q).e;
k++;q++;
}
(*Q).mu=(*M).mu;(*Q).nu=(*M).nu;(*Q).tu=k-1;
//计算各行第一个非零元素在存储数组中的位置
//若该行无非零元，则rpos[]值为零
int num[(*Q).mu+1],row,cpot[(*Q).mu+1];
cpot[1]=1;
for(k=1;k=(*Q).mu;k++)
num[k]=0;
for(k=1;k=(*Q).tu;k++)
++num[(*Q).data[k].i];
for(row=2;row=(*Q).mu;row++)
cpot[row]=cpot[row-1]+num[row-1];
for(row=1;row=(*Q).mu;row++){
if(cpot[row]=(*Q).tu)
if((*Q).data[cpot[row]].i==row){
(*Q).rpos[row]=cpot[row];
}
else
(*Q).rpos[row]=0;
else
(*Q).rpos[row]=0;
}
}
ChaRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)
{//矩阵求差函数
if((*M).mu!=(*N).mu||(*M).nu!=(*N).nu)
{printf("不满足矩阵相减的条件!");return 0;}
int i;
for(i=1;i=(*N).nu;i++)
(*N).data.e*=-1;
HeRLSMatrix((*M),(*N),(*Q));
}
JiRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{//矩阵求积函数
int arow,ctemp[N.nu+1],p,tp,i=1,j=1,t,q,ccol,h=1,n=1;
if(M.nu!=N.mu){
printf("不满足矩阵相乘的条件！");exit(0);}
(*Q).mu=M.mu;(*Q).nu=N.nu;(*Q).tu=0;
if(M.tu*N.tu!=0){
for(arow=1;arow=M.mu;arow++){//处理M的每一行
for(n=0;nN.nu+1;n++)
ctemp[n]=0;//当前行累加器清零
if(M.rpos[arow]!=0){//若arow行无非零元，则计算下一个有非零元的行
p=M.rpos[arow];
if(arowM.mu){
if(M.rpos[arow+1]==0){
if(arow+1M.mu){
while(arow+iM.muM.rpos[arow+i]==0)
i++;
tp=M.rpos[arow+i];
if(tp==0)
tp=M.tu+1;
}
else tp=M.tu+1;
}
else tp=M.rpos[arow+1];
}
else tp=M.tu+1;
for(p;ptp;p++){//对当前行中的每一个非零元
if(N.rpos[M.data[p].j]!=0){
q=N.rpos[M.data[p].j];//若该行存在非零元，找到对应元在N中的行号
if(M.data[p].jN.mu){
if(N.rpos[M.data[p].j+1]==0){
if(M.data[p].j+1N.mu){
while(M.data[p].j+1N.muN.rpos[M.data[p].j+j]==0)
j++;
t=N.rpos[M.data[p].j+j];
if(t==0)
t=N.tu+1;
}
else t=N.tu+1;
}
else t=N.rpos[M.data[p].j+1];
}
else t=N.tu+1;
for(q;qt;q++){
ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
}
}//求得Q中第arow行的非零元
for(ccol=1;ccol=N.nu+1;ccol++)//存储该行的非零元到Q中
if(ctemp[ccol]){
if(hMAXSIZE){printf("非零个数超出定义范围！");exit(0);}
(*Q).data[h].i=arow;
(*Q).data[h].j=ccol;
(*Q).data[h].e=ctemp[ccol];
h++;
}
}
}
}
(*Q).tu=h-1;
//计算各行第一个非零元素在存储数组中的位置
//若该行无非零元，则rpos[]值为零
int num[(*Q).mu+1],row,cpot[(*Q).mu+1],k;
cpot[1]=1;
for(k=1;k=(*Q).mu;k++)
num[k]=0;
for(k=1;k=(*Q).tu;k++)
++num[(*Q).data[k].i];
for(row=2;row=(*Q).mu;row++)
cpot[row]=cpot[row-1]+num[row-1];
for(row=1;row=(*Q).mu;row++){
if(cpot[row]=(*Q).tu)
if((*Q).data[cpot[row]].i==row){
(*Q).rpos[row]=cpot[row];
}
else
(*Q).rpos[row]=0;
else
(*Q).rpos[row]=0;
}
}
main()
{
RLSMatrix M,N,Q;
char ch;
printf(" *************************** \n");
printf(" ** ** \n");
printf(" ** 稀疏矩阵运算器 ** \n");
printf(" ** --------------------- ** \n");
printf(" *************************** \n");
printf(" _____________________________________________________________________ \n");
printf(" | 请选择 | \n");
printf(" | A.加法 B.减法 C.乘法 D.转置 Y.继续运算 N.结束运算 | \n");
printf(" |_____________________________________________________________________| \n\n");
printf("\2 输入数字时请用逗号隔开！\n\n");
printf(" -");
scanf("%c",ch);
while(ch!='N'){//进行循环运算
switch(ch){//进行运算选择
case'A':{ printf(" 请输入要求和的两个矩阵：\n\n");
printf(" 输入第一个矩阵：\n\n");
ScanRLSMatrix(M);
printf(" 输入的第一个矩阵为：\n\n");
PrintRLSMatrix(M);
printf(" 输入第二个矩阵：\n\n");
ScanRLSMatrix(N);
printf(" 输入的第二个矩阵为：\n\n");
PrintRLSMatrix(N);
HeRLSMatrix(M,N,Q);
printf(" 两矩阵之和为：\n\n");
PrintRLSMatrix(Q);
printf(" 是否继续运算（Y/N）？\n\n");
printf(" -");
ch=getchar();
};break;
case'B':{ printf(" 请按次序输入要求差的两个矩阵：\n\n");
printf(" 输入第一个矩阵：\n\n");
ScanRLSMatrix(M);
printf(" 输入的第一个矩阵为：\n\n");
PrintRLSMatrix(M);
printf(" 输入第二个矩阵：\n\n");
ScanRLSMatrix(N);
printf(" 输入的第二个矩阵为：\n\n");
PrintRLSMatrix(N);
ChaRLSMatrix(M,N,Q);
printf(" 两矩阵之差为：\n\n");
PrintRLSMatrix(Q);
printf("是否继续运算（Y/N）？\n\n");
printf(" -");
ch=getchar();
}break;
case'C':{printf(" 请按次序输入要求积的两个矩阵：\n\n");
printf(" 输入第一个矩阵：\n\n");
ScanRLSMatrix(M);
printf(" 输入的第一个矩阵为：\n\n");
PrintRLSMatrix(M);
printf(" 输入第二个矩阵：\n\n");
ScanRLSMatrix(N);
printf(" 输入的第二个矩阵为：\n\n");
PrintRLSMatrix(N);
JiRLSMatrix(M,N,Q);
printf(" 两矩阵之积为：\n\n");
PrintRLSMatrix(Q);
printf("是否继续运算（Y/N）？\n\n");
printf(" -");
ch=getchar();
}break;
case'D':{printf("请输入要转置的矩阵：\n\n");
ScanRLSMatrix(M);
printf(" 输入的要转置的矩阵为：\n\n");
PrintRLSMatrix(M);
FasttransposeRLSMatrix(M,Q);
printf("转置矩阵为：\n\n");
PrintRLSMatrix(Q);
printf("是否继续运算（Y/N）？\n\n");
printf(" -");
ch=getchar();
}break;
case'Y':{printf("请选择运算\n");
printf(" -");
ch=getchar();
}break;
default:printf("-");ch=getchar();break;
}
}
printf(" 运算结束！\n\n");
printf(" \1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1谢谢使用!\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\n\n");
getch();
}
/*我写的一个例子，基本上将稀疏矩阵三元组存储结构的定义和其有关的算法都实现了，那java语言改变去吧！
#includestdio.h
#define MAXSIZE 1000//非零元素的个数最多为1000
typedef struct {
int row;
int col;
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE];//非零元素的三元组表
int m;//矩阵的行数
int n;//矩阵的列数
int non_zero_num;//非零元数的个数
}XSMatrix;
XSMatrix XSM_Info_Input(XSMatrix s){
int i;
printf("输入矩阵的行数：");
scanf("%d",s.m);
printf("输入矩阵的列数：");
scanf("%d",s.n);
printf("输入矩阵的非零元素的个数：");
scanf("%d",s.non_zero_num);
for(i=0;is.non_zero_num;i++){
printf("输入第%d个非零元数的信息：\n",i+1);
printf("行下标:");
scanf("%d",s.data[i].row);
printf("列下标:");
scanf("%d",s.data[i].col);
printf("元素的值");
scanf("%d",s.data[i].e);
}
return s;
}
void XSM_Info_Output(XSMatrix s){
int i;
printf("\n稀疏矩阵行数和列数：%d\t%d\n",s.m,s.n);
printf("稀疏矩阵三元组表如下：\n");
printf("行下标\t列下标\t值\n");
for(i=0;is.non_zero_num;i++){
printf("%d\t%d\t%d\n",s.data[i].row,s.data[i].col,s.data[i].e);
}
}
//列序递增转置法
XSMatrix TransXSM(XSMatrix s){
XSMatrix d;
int i,j,k=0;
d.m=s.n;
d.n=s.m;
d.non_zero_num=s.non_zero_num;
for(i=0;is.n;i++){
for(j=0;js.non_zero_num;j++){
if(s.data[j].col==i)
{
d.data[k].row=s.data[j].col;
d.data[k].col=s.data[j].row;
d.data[k].e=s.data[j].e;
k++;
}
}
}
return d;
}
main(){
XSMatrix source,dest;
source=XSM_Info_Input(source);
XSM_Info_Output(source);
dest=TransXSM(source);
XSM_Info_Output(dest);
}
此程序我做了测试没问题
编译软件（virtual c++ 6.0）望你能学习进步
#includeiostream.h
#includestdlib.h
#includeiomanip.h
#define MaxRows 100
#define MaxColumns 100
typedef int ElemType;
struct CrossNode
{
int row,col;
ElemType val;
CrossNode *down,*right;
};
struct CLMatrix
{
int m,n,t;
CrossNode *rv[MaxRows+1];
CrossNode *cv[MaxColumns+1];
};
void InitMatrix(CLMatrix M)
{
M.m=0;M.n=0;M.t=0;
for(int i=1;i=MaxRows;i++)
M.rv[i]=NULL;
for(i=1;i=MaxColumns;i++)
M.cv[i]=NULL;
}
void InputMatrix(CLMatrix M,int m,int n);
void OutputMatrix(CLMatrix M,int m,int n);
void Transpose(CLMatrix M,int m,int n);
void main()
{
CLMatrix Q,P,N;
InitMatrix(Q);
InitMatrix(P);
InitMatrix(N);
cout"请您输入矩阵的行数与列数：";
int m,n;
cinmn;
cout"请以三元组的形式进行输入:"endl;
InputMatrix(Q,m,n);
cout"您输入的稀疏矩阵为："endl;
OutputMatrix(Q,m,n);
cout"转置后的稀疏矩阵为："endl;
Transpose(Q,m,n);
}
void InputMatrix(CLMatrix M,int m,int n)
{
M.m=m;M.n=n;
int row,col,val;
int k=0;
cinrowcolval;
while(row!=0)
{
k++;
CrossNode *cp,*newptr;
newptr=new CrossNode;
newptr-row=row;
newptr-col=col;
newptr-val=val;
newptr-down=newptr-right=NULL;
cp=M.rv[row];
if(cp==NULL)
M.rv[row]=newptr;
else
{
while(cp-right!=NULL)
cp=cp-right;
cp-right=newptr;
}
cp=M.cv[col];
if(cp==NULL)
M.cv[col]=newptr;
else
{
while(cp-down!=NULL)
cp=cp-down;
cp-down=newptr;
}
cinrowcolval;
}
M.t=k;
}
void Transpose(CLMatrix M,int m,int n)
{
CLMatrix S;
InitMatrix(S);
S.m=M.m;S.n=M.n;
for(int i=1;i=S.m;i++)
{
for(int j=1;j=S.n;j++)
{
int val=0;
CrossNode *cp,*newptr;
newptr=new CrossNode;
newptr-row=i;
newptr-col=j;
newptr-val=val;
newptr-down=newptr-right=NULL;
cp=S.rv[i];
if(cp==NULL)
S.rv[i]=newptr;
else
{
while(cp-right!=NULL)
cp=cp-right;
cp-right=newptr;
}
cp=S.cv[j];
if(cp==NULL)
S.cv[j]=newptr;
else
{
while(cp-down!=NULL)
cp=cp-down;
cp-down=newptr;
}
}
}
for(i=1;i=M.m;i++)
{
CrossNode *sp1=S.rv[i];
CrossNode *mp1=M.rv[i];
while(mp1!=NULL)
{
while(sp1-colmp1-col)
sp1=sp1-right;
sp1-val=mp1-val;
mp1=mp1-right;
}
}
for(int x=1;x=S.m;x++)
{
while(S.cv[x]!=NULL)
{
coutsetw(4)S.cv[x]-val;
S.cv[x]=S.cv[x]-down;
}
coutendl;
}
}
void OutputMatrix(CLMatrix M,int m,int n)
{
CLMatrix S;
InitMatrix(S);
S.m=M.m;S.n=M.n;
for(int i=1;i=S.m;i++)
{
for(int j=1;j=S.n;j++)
{
int val=0;
CrossNode *cp,*newptr;
newptr=new CrossNode;
newptr-row=i;
newptr-col=j;
newptr-val=val;
newptr-down=newptr-right=NULL;
cp=S.rv[i];
if(cp==NULL)
S.rv[i]=newptr;
else
{
while(cp-right!=NULL)
cp=cp-right;
cp-right=newptr;
}
cp=S.cv[j];
if(cp==NULL)
S.cv[j]=newptr;
else
{
while(cp-down!=NULL)
cp=cp-down;
cp-down=newptr;
}
}
}
for(i=1;i=M.m;i++)
{
CrossNode *sp1=S.rv[i];
CrossNode *mp1=M.rv[i];
while(mp1!=NULL)
{
while(sp1-colmp1-col)
sp1=sp1-right;
sp1-val=mp1-val;
mp1=mp1-right;
}
}
for(int x=1;x=S.m;x++)
{
while(S.rv[x]!=NULL)
{
coutsetw(4)S.rv[x]-val;
S.rv[x]=S.rv[x]-right;
}
coutendl;
}
}
2 设计
2.1 用十字链表存储稀疏矩阵
为了能有效存储稀疏矩阵的元素， 本文采用十字链表对数据进行存储， 所设计的十字链表C++语言描述如下： Typedef struct OLNode{
Int i , j ;
ElemType e;
Struct OLNode * right, * down;
}OLNode; *OLink;
Typedef struct{
OLink * rhead, * chead;
Int mu,nu,tu;
}CrossList;
2.2 稀疏矩阵相乘主要算法设计
稀疏矩阵乘法运算器的设计主要设计到稀疏矩阵的创建和相乘运算， 下面给出这两个过程的C++语言描述为：
2.2.1 稀疏矩阵的创建 Statue CreateSMatrix_OL (CrossList M){
//创建稀疏矩阵M。
If (M) free(M);
Scanf (m,n,t);
M.mu:=m; M.nu:=n; M.tu:=t;
If (! ( M.rhead=(OLink * )malloc( (m+1) * sizeof(OLink) ) ) ) exit (OVERFLOW)
If (! ( M.chead=(OLink * )malloc( (n+1) * sizeof(OLink) ) ) ) exit (OVERFLOW)
M.rhead[ ]+M.chead[ ]=NULL;
For ( scanf( i, j, e); i!=0 ; scanf ( I, j, e ) ){
If(! ( p=(OLNode * )malloc( sizeof (OLNode) ) ) ) exit ( OVERFLOW )
P—i = i; p—j=j ; p—e=e;
If (M . rhead [ i ] = =NULL) M . rhead [ i ] = p;
Else{
For ( q = M . rhead [ i ]; ( q—right ) q— right— j j; q = q— right;)
p—right =q—right ; q—right=p; }
这个自己写吧，很容易的。比如稀疏矩阵里的三元组[row,col,value]，转置之后就是[col,row,value]