// SparseMatrix.cpp : Defines the entry point for the console application.
// 

#include <stdio.h>

#define MAXSIZE 8
#define MAXRC 8
#define EMPTY 0

typedef int ElemType;

typedef struct Triple{
	int i,j; //行下標(biāo)和列下標(biāo)
	ElemType e;
}Triple; //三元組

typedef struct TSMatrix{
	Triple data[MAXSIZE+1];//丟棄0號單元
	int rpos[MAXRC+1]; // 各行第一個非零元素的位置表
	int rowNum; //行數(shù)
	int colNum; //列數(shù)
	int totalNum;//非零遠(yuǎn)個數(shù)
}TSMatrix;

void CreateSMatrix(TSMatrix &TSM,char *path)
{
	int i,row;
	FILE *fp=fopen(path,"r");
	fscanf(fp,"%d",&TSM.totalNum);
	fscanf(fp,"%d %d",&TSM.rowNum,&TSM.colNum);
	for(i=1;i<=TSM.rowNum;i++)
		TSM.rpos[i]=EMPTY;

	for(i=1;i<=TSM.totalNum;i++)
	{
		fscanf(fp,"%d %d %d",&TSM.data[i].i,&TSM.data[i].j,&TSM.data[i].e);
		row=TSM.data[i].i;
		if(TSM.data[i].i!=TSM.data[i-1].i && TSM.rpos[row]==EMPTY)
			TSM.rpos[row]=i;//紀(jì)錄row行第一個元素
	}

	if(TSM.rpos[TSM.rowNum]==EMPTY) TSM.rpos[TSM.rowNum]=TSM.totalNum+1;

	for(i=TSM.rowNum-1;i>0;i--)
	{
		if(TSM.rpos[i]==EMPTY) TSM.rpos[i]=TSM.rpos[i+1];
	}
}

void Evaluate(Triple Source,Triple &Target) //一個節(jié)點(diǎn)的值賦給另一個節(jié)點(diǎn)
{
	Target.i=Source.j;
	Target.j=Source.i;
	Target.e=Source.e;
}

void DestroySMatrix(TSMatrix &TSM)
{
	TSM.rowNum=0;
	TSM.colNum=0;
	TSM.totalNum=0;
}

void PrintSMatrix(TSMatrix TSM) //這個算法有待改進(jìn)
{
	int i,j;
	ElemType a[MAXSIZE+1][MAXSIZE+1];
	for(i=1;i<=TSM.rowNum;i++)
		for(j=1;j<=TSM.colNum;j++)
			a[i][j]=0;
	for(i=1;i<=TSM.totalNum;i++)
	{
		a[TSM.data[i].i][TSM.data[i].j]=TSM.data[i].e;
	}
	for(i=1;i<=TSM.rowNum;i++)
	{
		for(j=1;j<=TSM.colNum;j++)
			printf("%2d ",a[i][j]);
		printf("\n");
	}
}

void TransposeSMatrix(TSMatrix Source,TSMatrix &Target)
{//轉(zhuǎn)置比較難的就是要把三元組的次序重排（按i從小到大，在前提上j從小到大）
 //O(colNum * rowNum)
	int i,j,k,row;
	Target.colNum=Source.rowNum;
	Target.rowNum=Source.colNum;
	Target.totalNum=Source.totalNum;

	for(i=1;i<=Target.rowNum;i++)
		Target.rpos[i]=EMPTY;

	for(i=1,k=1;i<=Target.rowNum;i++) //一行一行地搜索
	{
		for(j=1;j<=Target.totalNum;j++)
		{
			if(Source.data[j].j==i)
			{
				Evaluate(Source.data[j],Target.data[k]);
				
				row=Target.data[k].i;
				if(Target.data[k].i!=Target.data[k-1].i && Target.rpos[row]==EMPTY)
					Target.rpos[row]=k;//紀(jì)錄row行第一個元素
				k++;
			}
		}
	}

	if(Target.rpos[Target.rowNum]==EMPTY)Target.rpos[Target.rowNum]=Target.totalNum+1;

	for(i=Target.rowNum-1;i>0;i--)
	{
		if(Target.rpos[i]==EMPTY) Target.rpos[i]=Target.rpos[i+1];
	}
}

void FastTransponseSMatrix(TSMatrix Source,TSMatrix &Target) //很巧妙的算法
{
	//用兩個輔助向量加速轉(zhuǎn)置
	//O(colNum + rowNum)
	int num[MAXSIZE+1];//i列元素個數(shù)
	int cpot[MAXSIZE+1];//目標(biāo)矩陣中i列第一個元素的位置
	int i,j,k;

	Target.colNum=Source.rowNum;
	Target.rowNum=Source.colNum;
	Target.totalNum=Source.totalNum;

	for(i=1;i<=Source.colNum;i++) num[i]=0;
	for(i=1;i<=Source.totalNum;i++)
	{
		k=Source.data[i].j;
		num[k]++;//第k列的元素個數(shù)增加
	}
	cpot[1]=1; //原矩陣第一列行第一個元素在 目標(biāo)矩陣中是第一行第一個元素，data[1]

	for(i=2;i<=Source.colNum;i++)
		cpot[i]=cpot[i-1]+num[i-1];
	for(i=1;i<=Source.totalNum;i++)
	{
		k=Source.data[i].j;
		j=cpot[k]++;//該列第一個元素在target中的位置
		//其實(shí)經(jīng)過++這個操作，也就可一看作是data[i]這個元素在target中的位置
		//因為每一次加一，表示這列的下個元素成為該列第一個元素，且位置要在target中推后一個
		Evaluate(Source.data[i],Target.data[j]);
	}
	for(i=1;i<=Source.colNum;i++)
	{
			Target.rpos[i]=cpot[i]; //復(fù)制紀(jì)錄位置到位
	}
}

void MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{
	int mRow,nRow,i,j,k,tp,tp2;
	int ctemp[MAXRC];//這是用來存儲當(dāng)前行的工作數(shù)據(jù)，不用二維數(shù)組的原因是沒必要浪費(fèi)空間
	Q.rowNum=M.rowNum;
	Q.colNum=N.colNum;
	Q.totalNum=0;
	for(mRow=1;mRow<=M.rowNum;mRow++) //對應(yīng)的M的每一行，從求值的角度上來講是對應(yīng)Q的每一行逐行求解
	{
		for(i=1;i<=Q.colNum;i++) ctemp[i]=0; //初始化ctemp

		Q.rpos[mRow]=Q.totalNum+1;//aRow行的當(dāng)前元素是以前的元素總數(shù)加1
		if(mRow<M.rowNum) tp=M.rpos[mRow+1]; //tp的作用是找出m行當(dāng)前的最后一個+1的元素的位置，故此種情況等于下行的起始位置
		else tp=M.totalNum+1; //這種情況就等于總數(shù)+1，因為他沒有下一行了
		//順便說一下，+1是為了統(tǒng)一tp的定義，方便下面的求解
		
		for(i=M.rpos[mRow];i<tp;i++) 
		{
			nRow=M.data[i].j; //元素對應(yīng)N中的行號
			//這樣處理是因為data[i]注定要和Nj行的每個元素都想乘一次，故這里動態(tài)規(guī)劃了下
			//經(jīng)典算法是m中的i行乘以n中的j列得到q中的ij元素
			//由于不方便找本列下1行的元素，就只能先行乘行，再綜合起來
			if(N.rpos[nRow]==EMPTY) 
				break;//這行語句也很重要的，因為我的存儲結(jié)構(gòu)中該行沒有元素就定義為EMPTY

			if(nRow<N.rowNum) tp2=N.rpos[nRow+1];
			else tp2=N.totalNum+1;

			for(j=N.rpos[nRow];j<tp2;j++) //到這里可以看出，就是逐個求i*j的
			{
				k=N.data[j].j;//乘積元素在Q中的列號
				ctemp[k]+=M.data[i].e*N.data[j].e;
			}
		}//對應(yīng)求得q的每一行，花費(fèi)時間是m*n

		//以下開始將結(jié)果轉(zhuǎn)移到q上，這里才壓縮
		for(k=1;k<=Q.colNum;k++)
		{
			if(ctemp[k]!=0)
			{
				//書上這里還有一句判斷是否超過該結(jié)構(gòu)最大容納的節(jié)點(diǎn)數(shù)的條件
				j=++Q.totalNum;
				Q.data[j].i=mRow;
				Q.data[j].j=k;
				Q.data[j].e=ctemp[k];
			}
		}
	}
}

int main()
{
	TSMatrix myMatrix,tranMatrix,resMatrix;
	CreateSMatrix(myMatrix,"data.txt");
	printf("原矩陣：\n");
	PrintSMatrix(myMatrix);

	printf("\n矩陣的轉(zhuǎn)置：\n");
	TransposeSMatrix(myMatrix,tranMatrix);
	PrintSMatrix(tranMatrix);

	printf("\n矩陣的快速轉(zhuǎn)置：\n");
	DestroySMatrix(tranMatrix);
	FastTransponseSMatrix(myMatrix,tranMatrix);
	PrintSMatrix(tranMatrix);

	printf("\n矩陣M：\n");
	CreateSMatrix(myMatrix,"M.txt");
	PrintSMatrix(myMatrix);
	printf("矩陣N：\n");
	CreateSMatrix(tranMatrix,"N.txt");
	PrintSMatrix(tranMatrix);
	printf("M與N相乘結(jié)果：\n");
	MultSMatrix(myMatrix,tranMatrix,resMatrix);
	PrintSMatrix(resMatrix);

	getchar();
	return 0;
}