数据结构课程设计

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 12500
#define range 81
#define MAXMN  500 
#define error  0
#define ok  1

typedef struct{
	int i,j;//该非零元素的行下标和列下标
	int e;
}Triple; 
typedef struct{
	Triple data[MAXSIZE+1]; 
    int rpos[MAXMN+1]; 
    int mu,nu,tu;//矩阵的行数、列数和非零元个数              
}RLSMatrix; // 行逻辑链接顺序表类型
typedef struct{
	int m,n;
	int arr[range][range];
}Matrix;

void CreateMatrix(Matrix *M){//创建稀疏矩阵
	int i,j;
	printf("请输入稀疏矩阵的行数m和列数n:");
	scanf("%d %d",&M->m,&M->n);
	printf("请输入稀疏矩阵:\n");
	for(i=1;i<=M->m;i++){
		for(j=1;j<=M->n;j++){
			scanf("%d",&M->arr[i][j]);
		}
	}
}
void InitTSMatrix(Matrix M,RLSMatrix *T){//将矩阵转化为三元组输出
	int i,j,k;
	T->mu=M.m;
	T->nu=M.n;
	T->tu=0;
	T->rpos[1]=1;
	k=1;
	for(i=1;i<=M.m;i++){
		T->rpos[i+1]=i;
		for(j=1;j<=M.n;j++){
			if(M.arr[i][j]==0) continue;
			else{
				T->data[k].e=M.arr[i][j];
				T->data[k].i=i;
				T->data[k].j=j;
                T->rpos[i+1]++;
				printf("(%3d,%3d,%3d)\n",T->data[k].i,T->data[k].j,T->data[k].e);
				k++;
				T->tu++;
			}
		}
		T->rpos[i+1]+=T->rpos[i];
	}
}
void printMatrix(Matrix M){//输出矩阵
	int i,j;
	for(i=1;i<=M.m;i++){
		for(j=1;j<=M.n;j++){
			printf("%5d",M.arr[i][j]);
		}
		printf("\n");
	}
}
void printTriple(RLSMatrix T){
	int i,j,p;
    p=1;
	for(i=1;i<=T.mu;i++){
		for(j=1;j<=T.nu;j++){
			if(i==T.data[p].i&&j==T.data[p].j){
				printf("%5d",T.data[p].e);
				p++;
			}
			else
				printf("    0");
		}
		printf("\n");
	}
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T){//求转置矩阵
  int col,p,q,t;
  int num[100];
  T->mu=M.nu;  
  T->nu=M.mu;  
  T->tu=M.tu;
  if (T->tu) {
    for (col=1; col<=M.nu; ++col)  
		num[col] = 0;
    for (t=1; t<=M.tu; ++t) 
		++num[M.data[t].j];//求m中每一列含非零元个数
    M.rpos[1]=1;
    for (col=2; col<=M.nu; ++col)
       M.rpos[col] = M.rpos[col-1] + num[col-1];
    for (p=1; p<=M.tu; ++p){
		col=M.data[p].j;
		q=M.rpos[col];
		T->data[q].i=M.data[p].j;
		T->data[q].j=M.data[p].i;
		T->data[q].e=M.data[p].e;
		++M.rpos[col];
	}//for
  } // if
} // FastTransposeSMatrix
int MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix *Q) {
	int ctemp[MAXSIZE+1];
	int p,q,t,brow,arow,ccol;
    if (M.nu != N.mu) 
		return error;
    Q->mu = M.mu; 
	Q->nu = N.nu; 
	Q->tu = 0; 
    if (M.tu*N.tu != 0) {   // M,N是非零矩阵
        for (arow=1; arow<=M.mu; ++arow) { // 处理M的每一行
	    for(ccol=1;ccol<=Q->nu;++ccol)
		    ctemp[ccol]=0;
	Q->rpos[arow] = Q->tu+1;      
    for (p=M.rpos[arow]; p<M.rpos[arow+1];++p) {//对当前行中每一个非零元
        brow=M.data[p].j;          
        if (brow < N.nu ) 
			t = N.rpos[brow+1];
        else 
			t = N.tu+1;
        for (q=N.rpos[brow];  q< t;  ++q) {
            ccol = N.data[q].j;            // 乘积元素在Q中列号
            ctemp[ccol] += M.data[p].e * N.data[q].e;
		} // for q
	} // 求得Q中第crow( =arow)行的非零元
    for (ccol=1; ccol<=Q->nu; ++ccol) 
		if (ctemp[ccol]) {
            if (++Q->tu > MAXSIZE) 
			    return error;
        Q->data[Q->tu].i = arow;
		Q->data[Q->tu].j = ccol;
		Q->data[Q->tu].e = ctemp[ccol];
		} // if
		} // for arow
   } // if    
   return ok;
  } // MultSMatrix

     
  
void RLSMatrix_Add(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q){//三元组表示的稀疏矩阵加法
    int m,n,q,qe;
	int t;
	if(M->mu!=N->mu||M->nu!=N->nu){
		printf("输入错误，矩阵无法相加！\n");
		exit(error);
	}
    Q->mu=M->mu;
    Q->nu=M->nu;
    Q->tu=0;
    m=1;n=1;q=1;
    for(t=1;t<=M->mu+1;t++){ //对矩阵的每一行进行加法  
        while(M->data[m].i<t) 
			m++;
        while(N->data[n].i<t) 
			n++;
        while(M->data[m].i==t&&N->data[n].i==t){//行列值都相等的元素   
            if(M->data[m].j==N->data[n].j){
                qe=M->data[m].e+N->data[n].e;
                if(qe){//和不为0
                    Q->data[q].i=t;
                    Q->data[q].j=M->data[m].j;
                    Q->data[q].e=qe;
                    m++;n++;q++;
				}
			}//if
                else if(M->data[m].j>N->data[n].j) {
                    Q->data[q].i=t;
                    Q->data[q].j=N->data[n].j;
                    Q->data[q].e=N->data[n].e;
                    n++;q++;
				}
            else{
                Q->data[q].i=t;
                Q->data[q].j=M->data[m].j;
                Q->data[q].e=M->data[m].e;
                m++;q++;
			}
		}//while
        while(M->data[m].i==t){//插入M中剩余的元素(第t行)
            Q->data[q].i=t;
            Q->data[q].j=M->data[m].j;
            Q->data[q].e=M->data[m].e;
            m++;q++;
		}
        while(N->data[n].i==t){ //插入N中剩余的元素(第t行)
            Q->data[q].i=t;
            Q->data[q].j=N->data[n].j;
            Q->data[q].e=N->data[n].e;
            n++;q++;
		}
	}//for
    Q->tu=q;
}//RLSMatrix_Add 
void main(){
	Matrix M,N;
	int num;
	RLSMatrix P,Q,R,S,T;
	printf("创建矩阵M\n");
	CreateMatrix(&M);//创建矩阵
	printf("您输入的矩阵为：\n");
	printMatrix(M);//输出矩阵
	printf("该矩阵转换成三元组类型为：\n");
	InitTSMatrix(M,&T);//将矩阵转化为三元组T输出
	while(1){
		printf("请选择要执行的操作：\n1、转置\n2、相加\n3、相乘\n");
		scanf("%d",&num);
		if(num==1||num==2||num==3)
			break;
		printf("输入有误！\n");
	}
	switch(num){
	case 1:
        FastTransposeSMatrix(T,&P);//求矩阵M(T)的转置矩阵P
		printTriple(P);//将P以矩阵形式输出
		break;
	case 2:
		printf("请输入要与矩阵M相加的矩阵N(行列数要与矩阵M的相等)\n");
        CreateMatrix(&N);//创建矩阵
	    printf("该矩阵转换成三元组类型为：\n");
	    InitTSMatrix(N,&Q);//将矩阵转化为三元组Q输出
		RLSMatrix_Add(&T,&Q,&S);
        printTriple(S);
		break;
	case 3:
        printf("请输入要与矩阵M相乘的矩阵N\n");
		CreateMatrix(&N);//创建矩阵
	    printf("该矩阵转换成三元组类型为：\n");
	    InitTSMatrix(N,&Q);//将矩阵转化为三元组Q输出
        MultSMatrix(T,Q,&R);
		printTriple(R);
		break;
	}
}