#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];//存放各行第一個(gè)非零元在存儲(chǔ)數(shù)組中的位置，若該行無非零元，則其rpos[]值為零
	int mu,nu,tu;
}RLSMatrix;

ScanRLSMatrix(RLSMatrix *T)
{//矩陣輸入函數(shù)，輸入各行非零元及其在矩陣中的行列數(shù)
	int k;
    printf("        ***********************************************************\n");
	printf("                  請(qǐng)輸入矩陣的行數(shù)，列數(shù)，非零元素個(gè)數(shù)             \n");
	printf("            ");
	scanf("%d,%d,%d",&(*T).mu,&(*T).nu,&(*T).tu);
	if((*T).tu>MAXSIZE){printf("非零個(gè)數(shù)超出定義范圍！");exit(0);}
	for(k=1;k<=(*T).tu;k++){
			printf("            按行存儲(chǔ)請(qǐng)輸入第%d個(gè)非零元素的行數(shù),列數(shù),其值:",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");

//計(jì)算各行第一個(gè)非零元素在存儲(chǔ)數(shù)組中的位置
//若該行無非零元，則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)
{//矩陣輸出函數(shù)，輸出矩陣形式
	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]].i&&b==(T).data[(T).rpos[a]].j){
				//(T).rpos[a]不為零時(shí)，輸出該行的非零元
				printf("%4d",(T).data[(T).rpos[a]].e);
				(T).rpos[a]++;
				}
			else
				{
			    printf("%4d",m);}
			}
		printf("\n");
		}
    printf("          ----------------------------------------\n");
}

FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q)
{//矩陣快速轉(zhuǎn)置
	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中每一行含非零元素的個(gè)數(shù)
		cpot[1]=1;
		//求第col列中第一個(gè)非零元在(*Q).data中的序號(hào)
		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];
		}
	}
//計(jì)算各行第一個(gè)非零元素在存儲(chǔ)數(shù)組中的位置
//若該行無非零元，則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)
{//矩陣求和函數(shù)
    if((*M).mu!=(*N).mu||(*M).nu!=(*N).nu)
		{printf("不滿足矩陣相加的條件!");return 0;}
	int k=1;
	Triple *p,*q;
	//設(shè)置兩個(gè)指針，分別指向M，N的第一個(gè)非零元位置，移動(dòng)指針進(jìn)行比較，得出相加后的新矩陣非零元
	p=&(*M).data[1];
	q=&(*N).data[1];
	while(p<(*M).data+(*M).tu+1&&q<(*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;

//計(jì)算各行第一個(gè)非零元素在存儲(chǔ)數(shù)組中的位置
//若該行無非零元，則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)
{//矩陣求差函數(shù)
    if((*M).mu!=(*N).mu||(*M).nu!=(*N).nu)
		{printf("不滿足矩陣相減的條件!");return 0;}
	int i;
	for(i=1;i<=(*N).nu;i++)
		(*N).data[i].e*=-1;
	HeRLSMatrix(&(*M),&(*N),&(*Q));

}

JiRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{//矩陣求積函數(shù)
	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;n<N.nu+1;n++)
			ctemp[n]=0;//當(dāng)前行累加器清零
            if(M.rpos[arow]!=0){//若arow行無非零元，則計(jì)算下一個(gè)有非零元的行
				p=M.rpos[arow];
			    if(arow<M.mu){
				   if(M.rpos[arow+1]==0){
					  if(arow+1<M.mu){
						 while(arow+i<M.mu&&M.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;p<tp;p++){//對(duì)當(dāng)前行中的每一個(gè)非零元
			        if(N.rpos[M.data[p].j]!=0){
				       q=N.rpos[M.data[p].j];//若該行存在非零元，找到對(duì)應(yīng)元在N中的行號(hào)
				       if(M.data[p].j<N.mu){
				          if(N.rpos[M.data[p].j+1]==0){
					         if(M.data[p].j+1<N.mu){
						        while(M.data[p].j+1<N.mu&&N.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;q<t;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++)//存儲(chǔ)該行的非零元到Q中
			    if(ctemp[ccol]){
					if(h>MAXSIZE){printf("非零個(gè)數(shù)超出定義范圍！");exit(0);}
				   (*Q).data[h].i=arow;
				   (*Q).data[h].j=ccol;
				   (*Q).data[h].e=ctemp[ccol];
				   h++;
				}
		    }
	    }
    }
    (*Q).tu=h-1;

//計(jì)算各行第一個(gè)非零元素在存儲(chǔ)數(shù)組中的位置
//若該行無非零元，則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("                         **     稀疏矩陣運(yùn)算器    **                        \n");
	printf("                         ** --------------------- **                        \n");
	printf("                         ***************************                        \n");
	printf("    _____________________________________________________________________     \n");
	printf("   |                               請(qǐng)選擇                                |    \n");
	printf("   |   A.加法    B.減法     C.乘法    D.轉(zhuǎn)置  Y.繼續(xù)運(yùn)算     N.結(jié)束運(yùn)算  |    \n");
    printf("   |_____________________________________________________________________|    \n\n");
	printf("\2 輸入數(shù)字時(shí)請(qǐng)用逗號(hào)隔開！\n\n");
	printf("     ->");
	scanf("%c",&ch);
	while(ch!='N'){//進(jìn)行循環(huán)運(yùn)算
		switch(ch){//進(jìn)行運(yùn)算選擇
			case'A':{ printf("       請(qǐng)輸入要求和的兩個(gè)矩陣：\n\n");
			          printf("       輸入第一個(gè)矩陣：\n\n");
					  ScanRLSMatrix(&M);
					  printf("       輸入的第一個(gè)矩陣為：\n\n");
					  PrintRLSMatrix(M);
					  printf("       輸入第二個(gè)矩陣：\n\n");
					  ScanRLSMatrix(&N);
					  printf("       輸入的第二個(gè)矩陣為：\n\n");
					  PrintRLSMatrix(N);
					  HeRLSMatrix(&M,&N,&Q);
					  printf("       兩矩陣之和為：\n\n");
					  PrintRLSMatrix(Q);
					  printf("      是否繼續(xù)運(yùn)算（Y/N）？\n\n");
					  printf("     ->");
					  ch=getchar();
					};break;
			case'B':{ printf("        請(qǐng)按次序輸入要求差的兩個(gè)矩陣：\n\n");
			          printf("        輸入第一個(gè)矩陣：\n\n");
					  ScanRLSMatrix(&M);
					  printf("        輸入的第一個(gè)矩陣為：\n\n");
					  PrintRLSMatrix(M);
					  printf("        輸入第二個(gè)矩陣：\n\n");
					  ScanRLSMatrix(&N);
					  printf("        輸入的第二個(gè)矩陣為：\n\n");
					  PrintRLSMatrix(N);
					  ChaRLSMatrix(&M,&N,&Q);
					  printf("        兩矩陣之差為：\n\n");
					  PrintRLSMatrix(Q);
					  printf("是否繼續(xù)運(yùn)算（Y/N）？\n\n");
					  printf("     ->");
					  ch=getchar();
					}break;
			case'C':{printf("         請(qǐng)按次序輸入要求積的兩個(gè)矩陣：\n\n");
			          printf("        輸入第一個(gè)矩陣：\n\n");
					  ScanRLSMatrix(&M);
					  printf("        輸入的第一個(gè)矩陣為：\n\n");
					  PrintRLSMatrix(M);
					  printf("        輸入第二個(gè)矩陣：\n\n");
					  ScanRLSMatrix(&N);
					  printf("        輸入的第二個(gè)矩陣為：\n\n");
					  PrintRLSMatrix(N);
					  JiRLSMatrix(M,N,&Q);
					  printf("        兩矩陣之積為：\n\n");
					  PrintRLSMatrix(Q);
					  printf("是否繼續(xù)運(yùn)算（Y/N）？\n\n");
					  printf("     ->");
					  ch=getchar();
					}break;

			case'D':{printf("請(qǐng)輸入要轉(zhuǎn)置的矩陣：\n\n");
			         ScanRLSMatrix(&M);
					 printf("        輸入的要轉(zhuǎn)置的矩陣為：\n\n");
					 PrintRLSMatrix(M);
					 FasttransposeRLSMatrix(M,&Q);
					 printf("轉(zhuǎn)置矩陣為：\n\n");
					 PrintRLSMatrix(Q);
					 printf("是否繼續(xù)運(yùn)算（Y/N）？\n\n");
					 printf("     ->");
					 ch=getchar();
				    }break;

			case'Y':{printf("請(qǐng)選擇運(yùn)算\n");
			         printf("     ->");
					 ch=getchar();
					}break;
			default:printf("->");ch=getchar();break;
			}
	}
printf("                                   運(yùn)算結(jié)束！\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();
}