sparsematrix.cpp

实验1：链表的应用--求多项式之和 1、实验目的：掌握单链表的各种基本操作

// 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; //行下标和列下标
	ElemType e;
}Triple; //三元组

typedef struct TSMatrix{
	Triple data[MAXSIZE+1];//丢弃0号单元
	int rpos[MAXRC+1]; // 各行第一个非零元素的位置表
	int rowNum; //行数
	int colNum; //列数
	int totalNum;//非零远个数
}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;//纪录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) //一个节点的值赋给另一个节点
{
	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) //这个算法有待改进
{
	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)
{//转置比较难的就是要把三元组的次序重排（按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;//纪录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) //很巧妙的算法
{
	//用两个辅助向量加速转置
	//O(colNum + rowNum)
	int num[MAXSIZE+1];//i列元素个数
	int cpot[MAXSIZE+1];//目标矩阵中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列的元素个数增加
	}
	cpot[1]=1; //原矩阵第一列行第一个元素在 目标矩阵中是第一行第一个元素，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中的位置
		//其实经过++这个操作，也就可一看作是data[i]这个元素在target中的位置
		//因为每一次加一，表示这列的下个元素成为该列第一个元素，且位置要在target中推后一个
		Evaluate(Source.data[i],Target.data[j]);
	}
	for(i=1;i<=Source.colNum;i++)
	{
			Target.rpos[i]=cpot[i]; //复制纪录位置到位
	}
}

void MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{
	int mRow,nRow,i,j,k,tp,tp2;
	int ctemp[MAXRC];//这是用来存储当前行的工作数据，不用二维数组的原因是没必要浪费空间
	Q.rowNum=M.rowNum;
	Q.colNum=N.colNum;
	Q.totalNum=0;
	for(mRow=1;mRow<=M.rowNum;mRow++) //对应的M的每一行，从求值的角度上来讲是对应Q的每一行逐行求解
	{
		for(i=1;i<=Q.colNum;i++) ctemp[i]=0; //初始化ctemp

		Q.rpos[mRow]=Q.totalNum+1;//aRow行的当前元素是以前的元素总数加1
		if(mRow<M.rowNum) tp=M.rpos[mRow+1]; //tp的作用是找出m行当前的最后一个+1的元素的位置，故此种情况等于下行的起始位置
		else tp=M.totalNum+1; //这种情况就等于总数+1，因为他没有下一行了
		//顺便说一下，+1是为了统一tp的定义，方便下面的求解
		
		for(i=M.rpos[mRow];i<tp;i++) 
		{
			nRow=M.data[i].j; //元素对应N中的行号
			//这样处理是因为data[i]注定要和Nj行的每个元素都想乘一次，故这里动态规划了下
			//经典算法是m中的i行乘以n中的j列得到q中的ij元素
			//由于不方便找本列下1行的元素，就只能先行乘行，再综合起来
			if(N.rpos[nRow]==EMPTY) 
				break;//这行语句也很重要的，因为我的存储结构中该行没有元素就定义为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;
			}
		}//对应求得q的每一行，花费时间是m*n

		//以下开始将结果转移到q上，这里才压缩
		for(k=1;k<=Q.colNum;k++)
		{
			if(ctemp[k]!=0)
			{
				//书上这里还有一句判断是否超过该结构最大容纳的节点数的条件
				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矩阵的转置：\n");
	TransposeSMatrix(myMatrix,tranMatrix);
	PrintSMatrix(tranMatrix);

	printf("\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相乘结果：\n");
	MultSMatrix(myMatrix,tranMatrix,resMatrix);
	PrintSMatrix(resMatrix);

	getchar();
	return 0;
}