|
|
Posted on 2007-11-11 14:08 山泉弯延 阅读(2723) 评论(0) 编辑 收藏 引用 所属分类: 数据结构实验集
//DEV开发环境 ，稀疏矩阵三元组表示
//作者:赵自明
//其中乘法代码参考严蔚敏数据结构
//开发完成日期：07年11月8日
//测试环境:window xp,vista
#include <cstdlib>
#include <iostream>
#define MAXSIZE 100
#define MAXRC 50
using namespace std;
typedef int ElemType;
typedef struct{
int i,j;//非零元在矩阵中的真实位置
ElemType e;//非零元
}Triple;//定义存放非零元素的结构体
typedef struct{
Triple data[MAXSIZE+1];//在使用过程有效位置也是从下标1开始
int mu,nu,tu;//行，列，非零元个数
int rpos[MAXRC+1];//从下标为1的位置开始存放每一行的第一个元素对应的在data中的位置
}TSMatrix;//定义存放稀疏矩阵的数据类型
int
CreateSMatrix(TSMatrix &M)
//创建新的稀疏矩阵
{ printf("please input m & n & tu:\n");
scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
while(M.tu>M.mu*M.nu)
{
printf("tu must <= mu*nu,input m & n & tu again: \n");
scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
}
int k;
for( k=1;k<=M.tu;k++)
{
printf("the %d number\n",k);
scanf("%d,%d,%d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
if(M.data[k].i>M.mu || M.data[k].j>M.nu )
{ printf("input error!\n");
system("PAUSE");
exit(1);
}
while(M.data[k].e==0)
{printf("elemment can not be zero!\n");
scanf("%d,%d,%d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
}
}
//以下是对寻找每行的第一个非零元在data动态数组中的位置
int num[MAXRC];
int t;
for(t=1;t<=M.mu;t++)num[t]=0;
for(t=1;t<=M.tu;++t)++num[M.data[t].i];
M.rpos[1]=1;
//求第ran行第一个非零元在Q.data中的位置
int ran=1;
// printf("第%d行的第一个元素在tu中的位置为：%d\n",ran,M.rpos[ran]);
for( ran=2;ran<=M.mu;++ran){ M.rpos[ran]=M.rpos[ran-1]+num[ran-1];
//printf("第%d行的第一个元素在tu中的位置为：%d\n",ran,M.rpos[ran]);
}
//system("PAUSE");
return 1;
}
int
PrintSMatrix(TSMatrix &M)
//以标准格式输出稀疏矩阵
{ if(!M.tu){printf("NULL to Print\n");return 0;}
int i,j,k=1;
for(i=1;i<=M.mu;i++)
{ for(j=1;j<=M.nu;j++)
{ if(i==M.data[k].i && j==M.data[k].j){printf("%d ",M.data[k].e);k++;}
else printf("# ");
}
printf("\n");
}
return 1;
}
int //此加法算法是对没有rpos算法的改进版本，时间效率更高 为 O(tu)
AddSMatrix_2(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)//由于加法结果返回给Q，建议给M,N加上const 防止在操作过程中对M,N修改
{//if(Q.data)free(Q.data);//如果data非NULL，释放内存
//printf("Go into add\n");
if(M.nu!=N.nu||M.mu!=N.mu)
{printf("M and N is not compared\n");
return 0;}
// Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));//申请的内存MAXSIZE+1表data 有效位置从1开始，MAXSIZE为最末有效下标
// if(!Q.data)exit(1);
Q.mu=M.mu;
Q.nu=M.nu;
Q.tu=0;
int ran;
int index_1_begin,index_1_end,index_2_begin,index_2_end;
int p_1,p_2;
for(ran=1;ran<=M.mu;ran++){
index_1_begin=M.rpos[ran];//当前行的第一个元素在data 中的位置
if(ran==M.mu)index_1_end=M.tu;//当前行的最后一个元素在data中的位置
else index_1_end=M.rpos[ran+1]-1;
//if(1==index_1_begin-index_1_end)if(1==inde_2_begin-index_2_end)
index_2_begin=N.rpos[ran];
if(ran==M.mu)index_2_end=N.tu;
else index_2_end=N.rpos[ran+1]-1;
// printf("go into for\n");
//printf("M当前行的第一个元素位置%d,M当前行的最后一个元素位置%d\n",index_1_begin,index_1_end);
//printf("N当前行的第一个元素位置%d,M当前行的最后一个元素位置%d\n",index_2_begin, index_2_end);
for(p_1=index_1_begin,p_2=index_2_begin;p_1<=index_1_end && p_2<=index_2_end;)//千万不要再在这里加p_1++,p_2++
if(M.data[p_1].j>N.data[p_2].j)//对M，N中当前行元素的j下标进行比较
{ // printf("小于\n");
Q.data[Q.tu+1].i=N.data[p_2].i;
Q.data[Q.tu+1].j=N.data[p_2].j;
Q.data[Q.tu+1].e=N.data[p_2].e;
p_2++;
Q.tu++;
}
else if(M.data[p_1].j<N.data[p_2].j)
{//printf("小于\n");
Q.data[Q.tu+1].i=M.data[p_1].i;
Q.data[Q.tu+1].j=M.data[p_1].j;
Q.data[Q.tu+1].e=M.data[p_1].e;
p_1++;
Q.tu++;
}
else if(M.data[p_1].j==N.data[p_2].j)
{//printf("相等的tu==%d\n",Q.tu+1);
if(M.data[p_1].e+N.data[p_2].e)
{Q.data[Q.tu+1].e=Q.data[Q.tu+1].e=M.data[p_1].e+N.data[p_2].e;
Q.data[Q.tu+1].i=M.data[p_1].i;
Q.data[Q.tu+1].j=M.data[p_1].j;
Q.tu++;
}
p_1++;
p_2++;
}//for
//当M或N当前行元素比较完的时候还需要将另一个没有比较完的非零元全部放进Q.data中
if( p_2<=index_2_end&& p_1>index_1_end )//在这里注意 比较一定使用<=和>
while(p_2<=index_2_end)
{
Q.data[Q.tu+1].i=N.data[p_2].i;
Q.data[Q.tu+1].j=N.data[p_2].j;
Q.data[Q.tu+1].e=N.data[p_2].e;
p_2++;
Q.tu++;
}//while
if(p_1<=index_1_end && p_2>index_2_end)
while(p_1<=index_1_end)
{
Q.data[Q.tu+1].i=M.data[p_1].i;
Q.data[Q.tu+1].j=M.data[p_1].j;
Q.data[Q.tu+1].e=M.data[p_1].e;
p_1++;
Q.tu++;
}//while
}//for
return 1;
}
int //减法运算与加法运算相似
SubtMatrix_2(const TSMatrix &M , TSMatrix &N,TSMatrix &Q)
{//if(Q.data)free(Q.data);//如果data非NULL，释放内存
//printf("Go into add\n");
if(M.nu!=N.nu||M.mu!=N.mu)
{printf("M and N is not compared\n");
return 0;}
// Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));//申请的内存MAXSIZE+1表data 有效位置从1开始，MAXSIZE为最末有效下标
// if(!Q.data)exit(1);
for(int i=1;i<=N.tu;++i)
N.data[i].e=-N.data[i].e;
AddSMatrix_2(M ,N,Q);
}
int //没有使用rpos的加法 时间复杂度为O(tu*tu)
AddSMatrix(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)
//两个稀疏矩阵相加，结果存放到 Q
{
// if(Q.data)free(Q.data);
if(M.nu!=N.nu||M.mu!=N.mu){printf("M and N is not compared\n");
return 0;}
//Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));
// if(!Q.data)exit(1);
Q.mu=M.mu;
Q.nu=M.nu;
Q.tu=0;
int k,k_1=1,k_2=1;
for(k=1;k_1<=M.tu && k_2<=N.tu;)
if(M.data[k_1].i<N.data[k_2].i)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e;
Q.tu++;
k_1++;
k++;
}
else if(M.data[k_1].i>N.data[k_2].i)
{Q.data[k].i=N.data[k_2].i;
Q.data[k].j=N.data[k_2].j;
Q.data[k].e=N.data[k_2].e;
Q.tu++;
k_2++;
k++;
}
else {
if(M.data[k_1].j<N.data[k_2].j)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e;
Q.tu++;
k_1++;
k++;
}
else if(M.data[k_1].j>N.data[k_2].j)
{Q.data[k].i=N.data[k_2].i;
Q.data[k].j=N.data[k_2].j;
Q.data[k].e=N.data[k_2].e;
Q.tu++;
k_2++;
k++;
}
else
{ if(M.data[k_1].e+N.data[k_2].e)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e+N.data[k_2].e;
Q.tu++;
k_1++;
k_2++;
k++;
}
else
{k_1++;
k_2++;}
}
}
if(k_1>M.tu && k_2<=N.tu)
{--k_1;
for(;k_2<=N.tu;k_2++,k++)
{Q.data[k].i=N.data[k_2].i;
Q.data[k].j=N.data[k_2].j;
Q.data[k].e=N.data[k_2].e;
Q.tu++;
}
}
if(k_1<=M.tu && k_2>N.tu)
{--k_2;
for(;k_1<=M.tu;k_1++,k++)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e;
Q.tu++;
}
}
return 1;
}
int
SubtMatrix(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)
//两个稀疏矩阵相减，结果存放到 Q
{
// if(Q.data)free(Q.data);
if(M.nu!=N.nu||M.mu!=N.mu)
{printf("M and N is not compared\n");
return 0;}
// Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));
// if(!Q.data)exit(1);
Q.mu=M.mu;
Q.nu=M.nu;
Q.tu=0;
int k,k_1=1,k_2=1;
for(k=1;k_1<=M.tu && k_2<=N.tu;)
if(M.data[k_1].i<N.data[k_2].i)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e;
Q.tu++;
k_1++;
k++;
}
else if(M.data[k_1].i>N.data[k_2].i)
{Q.data[k].i=N.data[k_2].i;
Q.data[k].j=N.data[k_2].j;
Q.data[k].e=-N.data[k_2].e;
Q.tu++;
k_2++;
k++;
}
else {
if(M.data[k_1].j<N.data[k_2].j)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e;
Q.tu++;
k_1++;
k++;
}
else if(M.data[k_1].j>N.data[k_2].j)
{Q.data[k].i=N.data[k_2].i;
Q.data[k].j=N.data[k_2].j;
Q.data[k].e=-N.data[k_2].e;
Q.tu++;
k_2++;
k++;
}
else
{ if(M.data[k_1].e-N.data[k_2].e)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e-N.data[k_2].e;
Q.tu++;
k_1++;
k_2++;
k++;
}
else
{k_1++;
k_2++;}
}
}
if(k_1>M.tu && k_2<=N.tu)
{--k_1;
for(;k_2<=N.tu;k_2++,k++)
{Q.data[k].i=N.data[k_2].i;
Q.data[k].j=N.data[k_2].j;
Q.data[k].e=-N.data[k_2].e;
Q.tu++;
}
}
if(k_1<=M.tu && k_2>N.tu)
{--k_2;
for(;k_1<=M.tu;k_1++,k++)
{Q.data[k].i=M.data[k_1].i;
Q.data[k].j=M.data[k_1].j;
Q.data[k].e=M.data[k_1].e;
Q.tu++;
}
}
return 1;
}
int
MultSMatrix(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)
//两个稀疏矩阵相乘,由于不改变M，N，结果存放到Q中，所以给M,N参数加CONST限定
{
if(M.nu!=N.mu)
{printf("M.nu!=N.mu\n");
return 0;}
//system("PAUSE");
// if(Q.data)free(Q.data);
// if( (Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple)))<0)exit(1);
Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;
if(M.tu*N.tu){
int arow;
int ctemp[N.nu+1];
for(arow=1;arow<=M.mu;++arow)
{ int i;
for(i=1;i<=N.nu;i++)ctemp[i]=0;
Q.rpos[arow]=Q.tu+1;
// printf("第%d行Q.RPOS的位置在%d\n",arow,Q.rpos[arow]);
// system("PAUSE");
int tp;
if(arow<M.mu)tp=M.rpos[arow+1];
else{tp=M.tu+1;}
//printf("该次的tp是%d\n",tp);
// system("PAUSE");
int brow,t,ccol,p;
for(p=M.rpos[arow];p<tp;++p)
{ brow=M.data[p].j;
if(brow<N.mu)t=N.rpos[brow+1];
else {t=N.tu+1;}
int q;
for(q=N.rpos[brow];q<t;++q)
{ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
// printf("now ctemp%d==%d\n", ccol,ctemp[ccol]);
}
}
// for(ccol=1;ccol<=Q.nu;++ccol)printf("ctemp[ccol]==%d\n",ctemp[ccol]);
for(ccol=1;ccol<=Q.nu;++ccol)
if(ctemp[ccol]){if(++Q.tu>MAXSIZE)return 0;
// printf("CTEMP %d\n",ctemp[ccol]);
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];
}
}
}
return 1;
}
int
main(int argc, char *argv[])
{
TSMatrix T;
TSMatrix W;
printf("================ 稀疏矩阵运算器 ===================\n");
printf(" please enter: +,-,*,q (Q,q)to exit program\n%%");
char c;
while(1)
{ scanf("%c",&c);
fflush(stdin);
switch(c){
case '+':{TSMatrix M;
TSMatrix N;
TSMatrix Q;
CreateSMatrix(M);printf("M smatrix:\n"); PrintSMatrix(M);
CreateSMatrix(N);printf("N smatrix:\n"); PrintSMatrix(N);
AddSMatrix_2(M ,N,Q) ;printf("M smatrix add N smatrix:\n"); PrintSMatrix(Q);fflush(stdin);
printf("please enter: +,-,*,q (Q,q)to exit program\n%%");break;
}
case '-':{TSMatrix M;
TSMatrix N;
TSMatrix Q;
CreateSMatrix(M);printf("M smatrix:\n"); PrintSMatrix(M);
CreateSMatrix(N);printf("N smatrix:\n"); PrintSMatrix(N);
SubtMatrix_2(M ,N,Q);printf("M smatrix sub N smatrix:\n"); PrintSMatrix(Q);fflush(stdin);
printf(" please enter: +,-,*,q (Q,q)to exit program\n%%");break;
}
case '*':{TSMatrix M;
TSMatrix N;
TSMatrix Q;
CreateSMatrix(M);printf("M smatrix:\n"); PrintSMatrix(M);
CreateSMatrix(N);printf("N smatrix:\n"); PrintSMatrix(N);
MultSMatrix(M,N,Q); printf("M smatrix mul N smatirx:\n"); PrintSMatrix(Q);fflush(stdin);
printf(" please enter: +,-,*,q (Q,q)to exit program\n%%");break;
}
case 'q':
case 'Q':return EXIT_SUCCESS;
default:{ printf("input error please enter again\n%%"); break; }
}
}
return 0;
}
 
1 //DEV开发环境 ，稀疏矩阵三元组表示
2 //作者:赵自明
3 //其中乘法代码参考严蔚敏数据结构
4 //开发完成日期：07年11月8日
5 //测试环境:window xp,vista
6 #include <cstdlib>
7 #include <iostream>
8 #define MAXSIZE 100
9 #define MAXRC 50
10 using namespace std;
11 typedef int ElemType;
12 typedef struct{
13 int i,j;//非零元在矩阵中的真实位置
14 ElemType e;//非零元
15 }Triple;//定义存放非零元素的结构体
16
17 typedef struct{
18 Triple data[MAXSIZE+1];//在使用过程有效位置也是从下标1开始
19 int mu,nu,tu;//行，列，非零元个数
20 int rpos[MAXRC+1];//从下标为1的位置开始存放每一行的第一个元素对应的在data中的位置
21 }TSMatrix;//定义存放稀疏矩阵的数据类型
22 int
23 CreateSMatrix(TSMatrix &M)
24 //创建新的稀疏矩阵
25 { printf("please input m & n & tu:\n");
26 scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
27 while(M.tu>M.mu*M.nu)
28 {
29 printf("tu must <= mu*nu,input m & n & tu again: \n");
30 scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
31 }
32
33 int k;
34 for( k=1;k<=M.tu;k++)
35 {
36 printf("the %d number\n",k);
37 scanf("%d,%d,%d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
38 if(M.data[k].i>M.mu || M.data[k].j>M.nu )
39 { printf("input error!\n");
40 system("PAUSE");
41 exit(1);
42 }
43 while(M.data[k].e==0)
44 {printf("elemment can not be zero!\n");
45 scanf("%d,%d,%d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
46 }
47 }
48 //以下是对寻找每行的第一个非零元在data动态数组中的位置
49 int num[MAXRC];
50 int t;
51 for(t=1;t<=M.mu;t++)num[t]=0;
52 for(t=1;t<=M.tu;++t)++num[M.data[t].i];
53 M.rpos[1]=1;
54 //求第ran行第一个非零元在Q.data中的位置
55 int ran=1;
56 // printf("第%d行的第一个元素在tu中的位置为：%d\n",ran,M.rpos[ran]);
57 for( ran=2;ran<=M.mu;++ran){ M.rpos[ran]=M.rpos[ran-1]+num[ran-1];
58 //printf("第%d行的第一个元素在tu中的位置为：%d\n",ran,M.rpos[ran]);
59 }
60 //system("PAUSE");
61 return 1;
62 }
63 int
64 PrintSMatrix(TSMatrix &M)
65 //以标准格式输出稀疏矩阵
66 { if(!M.tu){printf("NULL to Print\n");return 0;}
67 int i,j,k=1;
68 for(i=1;i<=M.mu;i++)
69 { for(j=1;j<=M.nu;j++)
70 { if(i==M.data[k].i && j==M.data[k].j){printf("%d ",M.data[k].e);k++;}
71 else printf("# ");
72
73 }
74 printf("\n");
75 }
76 return 1;
77 }
78 int //此加法算法是对没有rpos算法的改进版本，时间效率更高 为 O(tu)
79 AddSMatrix_2(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)//由于加法结果返回给Q，建议给M,N加上const 防止在操作过程中对M,N修改
80 {//if(Q.data)free(Q.data);//如果data非NULL，释放内存
81 //printf("Go into add\n");
82 if(M.nu!=N.nu||M.mu!=N.mu)
83 {printf("M and N is not compared\n");
84 return 0;}
85 // Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));//申请的内存MAXSIZE+1表data 有效位置从1开始，MAXSIZE为最末有效下标
86 // if(!Q.data)exit(1);
87 Q.mu=M.mu;
88 Q.nu=M.nu;
89 Q.tu=0;
90 int ran;
91 int index_1_begin,index_1_end,index_2_begin,index_2_end;
92 int p_1,p_2;
93 for(ran=1;ran<=M.mu;ran++){
94 index_1_begin=M.rpos[ran];//当前行的第一个元素在data 中的位置
95 if(ran==M.mu)index_1_end=M.tu;//当前行的最后一个元素在data中的位置
96 else index_1_end=M.rpos[ran+1]-1;
97 //if(1==index_1_begin-index_1_end)if(1==inde_2_begin-index_2_end)
98 index_2_begin=N.rpos[ran];
99 if(ran==M.mu)index_2_end=N.tu;
100 else index_2_end=N.rpos[ran+1]-1;
101 // printf("go into for\n");
102 //printf("M当前行的第一个元素位置%d,M当前行的最后一个元素位置%d\n",index_1_begin,index_1_end);
103 //printf("N当前行的第一个元素位置%d,M当前行的最后一个元素位置%d\n",index_2_begin, index_2_end);
104
105 for(p_1=index_1_begin,p_2=index_2_begin;p_1<=index_1_end && p_2<=index_2_end;)//千万不要再在这里加p_1++,p_2++
106 if(M.data[p_1].j>N.data[p_2].j)//对M，N中当前行元素的j下标进行比较
107 { // printf("小于\n");
108 Q.data[Q.tu+1].i=N.data[p_2].i;
109 Q.data[Q.tu+1].j=N.data[p_2].j;
110 Q.data[Q.tu+1].e=N.data[p_2].e;
111 p_2++;
112 Q.tu++;
113 }
114 else if(M.data[p_1].j<N.data[p_2].j)
115 {//printf("小于\n");
116 Q.data[Q.tu+1].i=M.data[p_1].i;
117 Q.data[Q.tu+1].j=M.data[p_1].j;
118 Q.data[Q.tu+1].e=M.data[p_1].e;
119 p_1++;
120 Q.tu++;
121 }
122 else if(M.data[p_1].j==N.data[p_2].j)
123 {//printf("相等的tu==%d\n",Q.tu+1);
124 if(M.data[p_1].e+N.data[p_2].e)
125 {Q.data[Q.tu+1].e=Q.data[Q.tu+1].e=M.data[p_1].e+N.data[p_2].e;
126 Q.data[Q.tu+1].i=M.data[p_1].i;
127 Q.data[Q.tu+1].j=M.data[p_1].j;
128 Q.tu++;
129 }
130 p_1++;
131 p_2++;
132 }//for
133 //当M或N当前行元素比较完的时候还需要将另一个没有比较完的非零元全部放进Q.data中
134 if( p_2<=index_2_end&& p_1>index_1_end )//在这里注意 比较一定使用<=和>
135
136 while(p_2<=index_2_end)
137 {
138 Q.data[Q.tu+1].i=N.data[p_2].i;
139 Q.data[Q.tu+1].j=N.data[p_2].j;
140 Q.data[Q.tu+1].e=N.data[p_2].e;
141 p_2++;
142 Q.tu++;
143 }//while
144
145 if(p_1<=index_1_end && p_2>index_2_end)
146 while(p_1<=index_1_end)
147 {
148 Q.data[Q.tu+1].i=M.data[p_1].i;
149 Q.data[Q.tu+1].j=M.data[p_1].j;
150 Q.data[Q.tu+1].e=M.data[p_1].e;
151 p_1++;
152 Q.tu++;
153 }//while
154 }//for
155 return 1;
156 }
157 int //减法运算与加法运算相似
158 SubtMatrix_2(const TSMatrix &M , TSMatrix &N,TSMatrix &Q)
159 {//if(Q.data)free(Q.data);//如果data非NULL，释放内存
160 //printf("Go into add\n");
161 if(M.nu!=N.nu||M.mu!=N.mu)
162 {printf("M and N is not compared\n");
163 return 0;}
164 // Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));//申请的内存MAXSIZE+1表data 有效位置从1开始，MAXSIZE为最末有效下标
165 // if(!Q.data)exit(1);
166 for(int i=1;i<=N.tu;++i)
167 N.data[i].e=-N.data[i].e;
168 AddSMatrix_2(M ,N,Q);
169
170 }
171 int //没有使用rpos的加法 时间复杂度为O(tu*tu)
172 AddSMatrix(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)
173 //两个稀疏矩阵相加，结果存放到 Q
174 {
175 // if(Q.data)free(Q.data);
176 if(M.nu!=N.nu||M.mu!=N.mu){printf("M and N is not compared\n");
177 return 0;}
178 //Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));
179 // if(!Q.data)exit(1);
180 Q.mu=M.mu;
181 Q.nu=M.nu;
182 Q.tu=0;
183 int k,k_1=1,k_2=1;
184 for(k=1;k_1<=M.tu && k_2<=N.tu;)
185 if(M.data[k_1].i<N.data[k_2].i)
186 {Q.data[k].i=M.data[k_1].i;
187 Q.data[k].j=M.data[k_1].j;
188 Q.data[k].e=M.data[k_1].e;
189 Q.tu++;
190 k_1++;
191 k++;
192 }
193 else if(M.data[k_1].i>N.data[k_2].i)
194 {Q.data[k].i=N.data[k_2].i;
195 Q.data[k].j=N.data[k_2].j;
196 Q.data[k].e=N.data[k_2].e;
197 Q.tu++;
198 k_2++;
199 k++;
200 }
201 else {
202 if(M.data[k_1].j<N.data[k_2].j)
203 {Q.data[k].i=M.data[k_1].i;
204 Q.data[k].j=M.data[k_1].j;
205 Q.data[k].e=M.data[k_1].e;
206 Q.tu++;
207 k_1++;
208 k++;
209 }
210 else if(M.data[k_1].j>N.data[k_2].j)
211 {Q.data[k].i=N.data[k_2].i;
212 Q.data[k].j=N.data[k_2].j;
213 Q.data[k].e=N.data[k_2].e;
214 Q.tu++;
215 k_2++;
216 k++;
217 }
218 else
219 { if(M.data[k_1].e+N.data[k_2].e)
220 {Q.data[k].i=M.data[k_1].i;
221 Q.data[k].j=M.data[k_1].j;
222 Q.data[k].e=M.data[k_1].e+N.data[k_2].e;
223 Q.tu++;
224 k_1++;
225 k_2++;
226 k++;
227 }
228 else
229 {k_1++;
230 k_2++;}
231 }
232 }
233 if(k_1>M.tu && k_2<=N.tu)
234 {--k_1;
235 for(;k_2<=N.tu;k_2++,k++)
236 {Q.data[k].i=N.data[k_2].i;
237 Q.data[k].j=N.data[k_2].j;
238 Q.data[k].e=N.data[k_2].e;
239 Q.tu++;
240 }
241 }
242 if(k_1<=M.tu && k_2>N.tu)
243 {--k_2;
244 for(;k_1<=M.tu;k_1++,k++)
245 {Q.data[k].i=M.data[k_1].i;
246 Q.data[k].j=M.data[k_1].j;
247 Q.data[k].e=M.data[k_1].e;
248 Q.tu++;
249 }
250 }
251 return 1;
252 }
253 int
254 SubtMatrix(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)
255 //两个稀疏矩阵相减，结果存放到 Q
256 {
257 // if(Q.data)free(Q.data);
258 if(M.nu!=N.nu||M.mu!=N.mu)
259 {printf("M and N is not compared\n");
260 return 0;}
261 // Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple));
262 // if(!Q.data)exit(1);
263 Q.mu=M.mu;
264 Q.nu=M.nu;
265 Q.tu=0;
266 int k,k_1=1,k_2=1;
267 for(k=1;k_1<=M.tu && k_2<=N.tu;)
268 if(M.data[k_1].i<N.data[k_2].i)
269 {Q.data[k].i=M.data[k_1].i;
270 Q.data[k].j=M.data[k_1].j;
271 Q.data[k].e=M.data[k_1].e;
272 Q.tu++;
273 k_1++;
274 k++;
275 }
276 else if(M.data[k_1].i>N.data[k_2].i)
277 {Q.data[k].i=N.data[k_2].i;
278 Q.data[k].j=N.data[k_2].j;
279 Q.data[k].e=-N.data[k_2].e;
280 Q.tu++;
281 k_2++;
282 k++;
283 }
284 else {
285 if(M.data[k_1].j<N.data[k_2].j)
286 {Q.data[k].i=M.data[k_1].i;
287 Q.data[k].j=M.data[k_1].j;
288 Q.data[k].e=M.data[k_1].e;
289 Q.tu++;
290 k_1++;
291 k++;
292 }
293 else if(M.data[k_1].j>N.data[k_2].j)
294 {Q.data[k].i=N.data[k_2].i;
295 Q.data[k].j=N.data[k_2].j;
296 Q.data[k].e=-N.data[k_2].e;
297 Q.tu++;
298 k_2++;
299 k++;
300 }
301 else
302 { if(M.data[k_1].e-N.data[k_2].e)
303 {Q.data[k].i=M.data[k_1].i;
304 Q.data[k].j=M.data[k_1].j;
305 Q.data[k].e=M.data[k_1].e-N.data[k_2].e;
306 Q.tu++;
307 k_1++;
308 k_2++;
309 k++;
310 }
311 else
312 {k_1++;
313 k_2++;}
314 }
315 }
316 if(k_1>M.tu && k_2<=N.tu)
317 {--k_1;
318 for(;k_2<=N.tu;k_2++,k++)
319 {Q.data[k].i=N.data[k_2].i;
320 Q.data[k].j=N.data[k_2].j;
321 Q.data[k].e=-N.data[k_2].e;
322 Q.tu++;
323 }
324 }
325 if(k_1<=M.tu && k_2>N.tu)
326 {--k_2;
327 for(;k_1<=M.tu;k_1++,k++)
328 {Q.data[k].i=M.data[k_1].i;
329 Q.data[k].j=M.data[k_1].j;
330 Q.data[k].e=M.data[k_1].e;
331 Q.tu++;
332 }
333 }
334 return 1;
335 }
336 int
337 MultSMatrix(const TSMatrix &M ,const TSMatrix &N,TSMatrix &Q)
338 //两个稀疏矩阵相乘,由于不改变M，N，结果存放到Q中，所以给M,N参数加CONST限定
339 {
340 if(M.nu!=N.mu)
341 {printf("M.nu!=N.mu\n");
342 return 0;}
343 //system("PAUSE");
344 // if(Q.data)free(Q.data);
345 // if( (Q.data=(Triple*)malloc((MAXSIZE+1)*sizeof(Triple)))<0)exit(1);
346 Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;
347 if(M.tu*N.tu){
348 int arow;
349 int ctemp[N.nu+1];
350 for(arow=1;arow<=M.mu;++arow)
351 { int i;
352 for(i=1;i<=N.nu;i++)ctemp[i]=0;
353 Q.rpos[arow]=Q.tu+1;
354 // printf("第%d行Q.RPOS的位置在%d\n",arow,Q.rpos[arow]);
355 // system("PAUSE");
356 int tp;
357 if(arow<M.mu)tp=M.rpos[arow+1];
358 else{tp=M.tu+1;}
359 //printf("该次的tp是%d\n",tp);
360 // system("PAUSE");
361 int brow,t,ccol,p;
362 for(p=M.rpos[arow];p<tp;++p)
363 { brow=M.data[p].j;
364 if(brow<N.mu)t=N.rpos[brow+1];
365 else {t=N.tu+1;}
366 int q;
367 for(q=N.rpos[brow];q<t;++q)
368 {ccol=N.data[q].j;
369 ctemp[ccol]+=M.data[p].e*N.data[q].e;
370 // printf("now ctemp%d==%d\n", ccol,ctemp[ccol]);
371 }
372 }
373 // for(ccol=1;ccol<=Q.nu;++ccol)printf("ctemp[ccol]==%d\n",ctemp[ccol]);
374 for(ccol=1;ccol<=Q.nu;++ccol)
375 if(ctemp[ccol]){if(++Q.tu>MAXSIZE)return 0;
376 // printf("CTEMP %d\n",ctemp[ccol]);
377 Q.data[Q.tu].i=arow;
378 Q.data[Q.tu].j=ccol;
379 Q.data[Q.tu].e=ctemp[ccol];
380 }
381 }
382
383 }
384 return 1;
385 }
386
387 int
388 main(int argc, char *argv[])
389 {
390
391
392 TSMatrix T;
393 TSMatrix W;
394 printf("================ 稀疏矩阵运算器 ===================\n");
395 printf(" please enter: +,-,*,q (Q,q)to exit program\n%%");
396 char c;
397 while(1)
398 { scanf("%c",&c);
399 fflush(stdin);
400 switch(c){
401 case '+':{TSMatrix M;
402 TSMatrix N;
403 TSMatrix Q;
404 CreateSMatrix(M);printf("M smatrix:\n"); PrintSMatrix(M);
405 CreateSMatrix(N);printf("N smatrix:\n"); PrintSMatrix(N);
406 AddSMatrix_2(M ,N,Q) ;printf("M smatrix add N smatrix:\n"); PrintSMatrix(Q);fflush(stdin);
407 printf("please enter: +,-,*,q (Q,q)to exit program\n%%");break;
408 }
409 case '-':{TSMatrix M;
410 TSMatrix N;
411 TSMatrix Q;
412 CreateSMatrix(M);printf("M smatrix:\n"); PrintSMatrix(M);
413 CreateSMatrix(N);printf("N smatrix:\n"); PrintSMatrix(N);
414 SubtMatrix_2(M ,N,Q);printf("M smatrix sub N smatrix:\n"); PrintSMatrix(Q);fflush(stdin);
415 printf(" please enter: +,-,*,q (Q,q)to exit program\n%%");break;
416 }
417 case '*':{TSMatrix M;
418 TSMatrix N;
419 TSMatrix Q;
420 CreateSMatrix(M);printf("M smatrix:\n"); PrintSMatrix(M);
421 CreateSMatrix(N);printf("N smatrix:\n"); PrintSMatrix(N);
422 MultSMatrix(M,N,Q); printf("M smatrix mul N smatirx:\n"); PrintSMatrix(Q);fflush(stdin);
423 printf(" please enter: +,-,*,q (Q,q)to exit program\n%%");break;
424 }
425 case 'q':
426 case 'Q':return EXIT_SUCCESS;
427 default:{ printf("input error please enter again\n%%"); break; }
428 }
429 }
430 return 0;
431 }
432
|