|
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
|