#define MAX_TERMS 101	//定義最大長(zhǎng)度 
typedef struct{
	int col;
	int row;
	int xalue;
}term;
term a[MAX_TERMS];

void transpose(term a[],term b[])
//b是a的轉(zhuǎn)置 
{
	int n,i,j,currentb;
	n=a[0].value;			//元素總數(shù) 
	b[0].row=a[0].col;		//b的行數(shù)=a的列數(shù)
	b[0].co 1=a[0].row;	    //b的列數(shù)=a的行數(shù)
	b[0].value =n;
	if(n> 0) 
	{// 非零矩陣 
		currentb=1;
		for(i=0;i<a[0].col;i++)
		//按a的列轉(zhuǎn)置
			for(j=1;j<=n;j++)
			//找出當(dāng)前列的所有元素
				if(a[j].col==i)
				{//元素是當(dāng)前列的，加入b
					b[currentb]. row=a[j]. col;
					b[currentb]. col=a[j]. row;
					b[currentb]. value=a[j]. value;
					currentb++;
				}
	}
}

void fast transpose(term a[], term b[])
{
//將a的轉(zhuǎn)置矩陣存放于b中 
	int row terms[MAX_COL], starting pos[MAX_COL]; 
	int i,j, num_cols=a[0].col, num_terms=a[0].value;
	b[0].row=num_cols;b[0].col=a[0].row;
	b[0].value=num_terms;
	if(num_terms>0){//非零矩陣
		for(i=0;i<num_cols;i++)
			row_terms[i]=0;
		for(i=1;i<=num_terms;i++)
			row_terms[a[i]. co]]++;
		starting_pos[0]=1;
		for(i=1;i<num cols;i++)
			starting_pos[i]=starting_pos[i-1]+row_terms[i-l];
		for(i=1;i<=num_terms;i++){
			j=starting_pos[a[i].col]++;
			b[j].row=a[i].col;b[j].col=a[i].row;
			b[j].value=a[i].value;
		}
	}
}

void storesum(term a[],int *totald,int row,int column,int *sum)
{//如果 *sum！=0，它的行和列存儲(chǔ)位置為 d 中的 *totald+1
	if(*sum)
		if(*tptald<MAX_TERMS)
		{
			d[++*totald].row=row;
			d[*totald].col=column;
			d[*totald].value=*sum;
			*sum=0;
		}
		else{
			fprintf(stderr,"Numbers of terms in product exceeds %d\n",MAX_TERMS); 
			exit(1);
		}
}
void mmult(term a[], term b[], term d[])
//將兩個(gè)稀疏矩陣相乘 
{
	int i,j,column,totalb=b[0].value,totald=0; 
	int rows_a=a[0].row,cols_a=a[0].col;
	totala=a[0].value;int cols_b=b[0].col;
	int row_begin=1, row=a[1].row, sum=0; 
	int new_b[MAX-TERMS][3];
	if(cols_a!=b[0].row){
		fprintf(stderr,"Incompatible matrices\n"); 
		exit(1);
	}
	fast_transpose(b.new_b);
	//設(shè)置邊界條件
	a[totala+1].row=rows_a;
	new_b[totalb+1].row=cols_b; 
	new_b[totalb+1].col=0;
	for(i=1;i<=totala;){
		column=new_b[1].row; 
		for(j=1;j<=totalb+1;){
		//將a的行乘以b的列
			if(a[i].row!=row){
				storesum(d,&totald,row,column,&sum);
				i=row_begin;
				for(;new_b[j].row==column;j++)
					;
				column=new_b[j]. row;
			}
			else if(new_b[j].row!=column){
				storesum(d,&totald,row,column,&sum); 
				i=row_begin;
				column=new_b[j].row;
			}
			else switch(COMPARE(a[i].col,new_b[j].col)){
				case-1://轉(zhuǎn)到a中的下一項(xiàng)
					i++;break;
				case 0://添加項(xiàng)，轉(zhuǎn)到a和b的下一項(xiàng) 
					sum+=(a[i++].value*new_b[j++].value); break;
				case 1://來(lái)到b的下一項(xiàng)
					j++;
			}
	}// for j<=totalb+1 結(jié)束循環(huán) 
	for(;a[i].row==row;i++)
		;
	row_begin=i;row=a[i].row;
	}//for i<=totala 結(jié)束循環(huán) 
	d[0].row=rows_a;
	d[0].col=cols_b;d[0].value=totald;
}