sparsematrix.cpp

数据结构课程设计题目

//稀疏矩阵

#include<iostream>
using namespace std;
#define maxsize 200

typedef struct
{
 int row,col;
 int elem;
}Triple;

typedef struct
{
 Triple data[maxsize+1];
 int m,n,len;
}TSMatrix;


TSMatrix M,N;





//一次定位快速转置法
void change(TSMatrix A,TSMatrix *B)
{
 int col,t,p,q;
 int num[maxsize];
 int position[maxsize];
 B->len=A.len;B->n=A.m;B->m=A.n;

 if(B->len)
 {
  for(col=1;col<=A.n;col++)
   num[col]=0;
  for(t=1;t<=A.len;t++)
   num[A.data[t].col]++;//扫描一遍三元组，计算每一列非零元素的个数

  position[1]=1;
  for(col=2;col<=A.n;col++)
   position[col]=position[col-1]+num[col-1];//求col列中第一个非零元素在B.data[]的正确位置

  for(p=1;p<=A.len;p++)
  {
   col=A.data[p].col;
   q=position[col];
   B->data[q].row=A.data[p].col;
   B->data[q].col=A.data[p].row;
   B->data[q].elem=A.data[p].elem;
   position[col]++;//指向下一个列号为col的非令元素在转置三元组中的位置
  }
 }
}
 




//矩阵加法函数
bool add(TSMatrix M,TSMatrix N,TSMatrix &S)
{
	if(M.m!=N.m||M.n!=N.n)
	{
		cout<<"两个矩阵不可加！"<<endl;
		return false;
	}
	S.m=M.m;
	S.n=M.n;

	int i=1,j=1,k=1;
	//M.len表示矩阵M中非零元的个数，N.len同
	while(i<=M.len&&j<=N.len)      //此处需同时进行
	{
		if(M.data[i].row<N.data[j].row) 
          //{S.data[k].row=M.data[i].row;
          //S.data[k].col=M.data[i].col;
          //S.data[k].elem=M.data[i].elem;
	      //i++; k++;}
			S.data[k++]=M.data[i++];     
		if(M.data[i].row>N.data[j].row) //此句原为if(N.data[i].row>N.data[j].row)
			S.data[k++]=N.data[j++];         
		if(M.data[i].row==N.data[j].row) 
		{
			if(M.data[i].col<N.data[j].col)
				S.data[k++]=M.data[i++];
			if(M.data[i].col>N.data[j].col)
				S.data[k++]=N.data[j++];
			if(M.data[i].col==N.data[j].col)
			{
				if(M.data[i].elem+N.data[j].elem) 
				{
					S.data[k]=M.data[i];
					S.data[k++].elem=M.data[i].elem+N.data[j].elem;
				}
				i++;j++;
			}
		}
	}

	while(i<=M.len)  //将M中的剩余元素拷到S中
		S.data[k++]=M.data[i++];
	while(j<=N.len)  //将N中的剩余元素拷到S中
		S.data[k++]=N.data[j++];

	S.len=--k;  
	if(k>=maxsize)
	{
		cout<<"错误，数据溢出 ！"<<endl;
		return false;
	}

	return true;
}





//输出矩阵函数(成功)
void print(TSMatrix S)
{
	
	
	int array[20][20];
	for(int i=0;i<20;i++)
		for(int j=0;j<20;j++)
			array[i][j]=0;
		//初始化数组

	for(int k=1;k<=S.len;k++)
		array[S.data[k].row][S.data[k].col]=S.data[k].elem;
	//三元组转化成矩阵



	for(int h1=1;h1<=S.m;h1++)
	{
		for(int h2=1;h2<=S.n;h2++)
			cout<<array[h1][h2]<<" ";
		cout<<endl;
	}
}




//主函数体
void main()
{
 
 cout<<"请输入M矩阵的行数，列数和非零元素的个数："<<endl;
 cin>>M.m>>M.n>>M.len;
 for(int i=1;i<=M.len;i++)
 {
  cout<<"请输入元素的行号，列号和元素值："<<endl;
  cin>>M.data[i].row>>M.data[i].col>>M.data[i].elem;
 }//定义且初始化第一个距阵


cout<<"输出矩阵M："<<endl;
print(M);

 
 cout<<"请输入N矩阵的行数，列数和非零元素的个数："<<endl;
 cin>>N.m>>N.n>>N.len;
 for(int j=1;j<=N.len;j++)
 {
  cout<<"请输入元素的行号，列号和元素值："<<endl;
  cin>>N.data[j].row>>N.data[j].col>>N.data[j].elem;
 }//定义且初始化第二个距阵


cout<<"输出矩阵N："<<endl;
 print(N);
 


TSMatrix S,D;
add(M,N,S);


cout<<"输出矩阵S："<<endl;
print(S);


change(S,&D);
cout<<"输出S的转置矩阵D："<<endl;
print(D);


}