精华内容
下载资源
问答
  • 二维数组__普通矩阵转换为稀疏矩阵
    千次阅读
    2014-11-06 17:07:51
    # include<cstdio>
    # include<iostream>
    # include<iomanip>
    
    const int n = 3;
    const int m = 5;
    
    using namespace std;
    
    # define xh1 int i = 1;i <= n;i++
    # define xh2 int j = 1;j <= m;j++
    
    
    int main(void)
    {
        int a[n+1][m+1];
        int b[101][4];//行数设置这么多的原因是因为输出的需要
        int k = 0;
        for ( xh1 )
            {
                for ( xh2 )
                    {
                        cin>>a[i][j];
                    }
            }
            for ( xh1 )
                {
                    for ( xh2 )
                        {
                            if ( a[i][j]!=0 )
                                {//找到非零值然后存储,有几个非零元素的值,那么就会输出几行
                                    k++;
                                    b[k][1] = i;//稀疏矩阵某行的第一个元素
                                    b[k][2] = j;//稀疏矩阵某行的第二个元素
                                    b[k][3] = a[i][j]; //稀疏矩阵的第三个元素
                                }
                        }
                }
            for ( int i = 1;i <= k;i++ )
                {
                    for ( int j = 1;j <= 3;j++ )
                        {
                            cout<<setw(3)<<b[i][j];
                        }
                        cout<<endl;
                }
    
    
    
        return 0;
    }
    

    更多相关内容
  • PTA 5-1 稀疏矩阵的处理

    千次阅读 2021-12-15 17:37:59
    5-1 稀疏矩阵的处理 (25 分) 特殊矩阵在采用二维数组存储时,尽管矩阵操作的算法都很简单,但是其空间的利用率很低。 稀疏矩阵就是一种应用很广泛的特殊的矩阵。通常稀疏矩阵在处理时都采用“压缩”存储,即把稀疏...

    5-1 稀疏矩阵的处理 (25 分)

    特殊矩阵在采用二维数组存储时,尽管矩阵操作的算法都很简单,但是其空间的利用率很低。 稀疏矩阵就是一种应用很广泛的特殊的矩阵。通常稀疏矩阵在处理时都采用“压缩”存储,即把稀疏矩阵的非零元素抽象成为一个以三元组(行,列,值)为数据元素的线性表来处理,此线性表可以采用顺序存储,也可以采用链式存储。现要求编程实现稀疏矩阵在“压缩”存储时的常用操作,如输出、转置、求和、乘等。
    现要求编程实现稀疏矩阵在“压缩”存储时的矩阵的常用操作,如输出、转置、求和、乘等。 即输入两个矩阵,完成如下操作:
    (1) 转置。对第一个矩阵进行转置并输出,前面输出标题 “The transformed matrix is:”

    (2) 矩阵加。如两个矩阵可以相加,进行两个矩阵的加运算并输出,前面输出标题 “The added matrix is:”;如果不能相加,则输出 “Can not add!”;

    (3) 矩阵乘。如果两个矩阵可以相乘,进行两个矩阵的乘并输出,前面输出标题 “The product matrix is:”; 如果不能相乘,则输出 “Can not multiply!

    输入格式:
    输入有多行,第1行包括三个整数,分别是矩阵的大小m,n及非零元素的个数r。后面r行分别输入各个非零元素的 行、列、值。

    输出格式:
    输出有两种形式,操作时分别用符号“L”、“H”指出输出形式。 L: 以三元组的形式输出,即先输出矩阵的行数、列数和非零元素个数,再按行主序依次输出各个非零元素的行、列和值。各输出项之间空格分隔。 H: 按人们习惯的矩阵格式输出,即输出一个mn的矩阵,是零元素的输出0,非零元素输出元素值。设定每个元素占位宽度为4。(要输出矩阵的行号和列号,并对齐)

    输入样例:
    输入样例1:

    10 8 4 
    1 8 1
    3 3 2 
    3 7 3 
    10 1 4 
    10 8 2 
    2 6 1 
    3 7 -3
    H 
    结尾无空行
    

    输入样例2:

    100 90 5
    1 10 100
    50 60 200
    50 80 100
    60 60 200
    99 89 10
    100 90 4
    1 1 10
    50 60 -200
    50 80 100
    70 70 10
    L
    结尾无空行
    

    输出样例:
    输出样例1:

    The transformed matrix is:
           1   2   3   4   5   6   7   8   9  10
       1   0   0   0   0   0   0   0   0   0   4
       2   0   0   0   0   0   0   0   0   0   0
       3   0   0   2   0   0   0   0   0   0   0
       4   0   0   0   0   0   0   0   0   0   0
       5   0   0   0   0   0   0   0   0   0   0
       6   0   0   0   0   0   0   0   0   0   0
       7   0   0   3   0   0   0   0   0   0   0
       8   1   0   0   0   0   0   0   0   0   0
    The added matrix is:
           1   2   3   4   5   6   7   8
       1   0   0   0   0   0   0   0   1
       2   0   0   0   0   0   1   0   0
       3   0   0   2   0   0   0   0   0
       4   0   0   0   0   0   0   0   0
       5   0   0   0   0   0   0   0   0
       6   0   0   0   0   0   0   0   0
       7   0   0   0   0   0   0   0   0
       8   0   0   0   0   0   0   0   0
       9   0   0   0   0   0   0   0   0
      10   4   0   0   0   0   0   0   0
    Can not multiply!
    结尾无空行
    

    输出样例2:

    The transformed matrix is:
    Rows=90,Cols=100,r=5
    10 1 100
    60 50 200
    60 60 200
    80 50 100
    89 99 10
    The added matrix is:
    Rows=100,Cols=90,r=6
    1 1 10
    1 10 100
    50 80 200
    60 60 200
    70 70 10
    99 89 10
    Can not multiply!
    结尾无空行
    

    AC代码如下:

    #include <stdio.h>
    typedef struct mat{
    	int x;
    	int y;
    	int v;
    }mat;
    mat M1[10000];
    mat M2[10000];
    mat T[10000];
    mat M[10000];
    int m1=0,m2=0,n1=0,n2=0,r1=0,r2=0,r=0,rm;
    void read();
    void transform(int flag);
    void add(int flag);
    void mult(int flag);
    void sort_y(int left,int right,mat* Temp);
    void sort_x(int left,int right,mat* Temp);
    void sort_y_x(mat* Temp,int r);
    void sort_x_y(mat* Temp,int r);
    int main(){
    	read();
    	return 0;
    }
    void read(){
    	int i,j,x,y,v;
    	/* 数据读入Start */
    	scanf("%d %d %d",&m1,&n1,&r1);
    	for(i=1;i<=r1;i++)
    	scanf("%d %d %d",&M1[i].x,&M1[i].y,&M1[i].v);
    	scanf("%d %d %d",&m2,&n2,&r2);
    	for(i=1;i<=r2;i++)
    	scanf("%d %d %d",&M2[i].x,&M2[i].y,&M2[i].v);
    	/* 数据读入End */
    
    	/* Start判断打印方式,并调用转置,加法,乘法的函数 */
    	char s;
    	getchar();
    	scanf("%c",&s);
    	int flag=1;
    	if(s=='L')
    		flag=2;
    	transform(flag);
    	add(flag);
    	mult(flag);
    	/* End 判断打印方式,并调用转置,加法,乘法的函数 */
    }
    
    void transform(int flag){
    	int i,j,k=1;
    	printf("The transformed matrix is:\n");
    	sort_y_x(M1,r1);
    	if(flag==1){
    		printf("    ");
    		for(i=1;i<=m1;i++)
    			printf("%4d",i);
    		for(i=1;i<=n1;i++){
    			printf("\n%4d",i);
    			while(1){
    					if(M1[k].y<i && k<=r1)
    					k++;
    					else
    					break;
    				}
    				/*k=i k>r*/
    			for(j=1;j<=m1;j++)
    				if(k>r1||M1[k].y!=i)
    				printf("%4d",0);
    				else{
    					int temp=k;
    					int t=0;
    					while(M1[temp].y==i && temp <= r1){
    						if(M1[temp].x==j){
    							t=1;
    							break;
    						}
    						else
    						temp++;
    					}
    					if(t==1)
    					printf("%4d",M1[temp].v);
    					else
    					printf("%4d",0);
    				}
    		}
    		printf("\n");
    	}
    	else{
      		printf("Rows=%d,Cols=%d,r=%d\n",n1,m1,r1);
    		for(i=1;i<=r1;i++){
    			printf("%d %d %d\n",M1[i].y,M1[i].x,M1[i].v);
    		}
    	}
    }
    
    void add(int flag){
    	if(m1==m2&&n1==n2){
    		/* 矩阵加法 Start */
    		sort_x_y(M1,r1);
    		sort_x_y(M2,r2);
    		int book[10000]={0};
    		int k=1,i,j;
    		for(i=1;i<=r1;i++){
    			int flag_temp=0;
    			for(j=1;j<=r2;j++){
    				if(M1[i].x==M2[j].x && M1[i].y==M2[j].y ){
    					flag_temp=1;
    					book[j]=1;
    					if(M1[i].v + M2[j].v != 0){
    						T[k].v = M1[i].v + M2[j].v;
    						T[k].x = M1[i].x;
    						T[k].y = M1[i].y;
    						k++;
    					}
    					break;
    				}
    			}
    			if(flag_temp==0){
    				T[k].v = M1[i].v;
    				T[k].x = M1[i].x;
    				T[k].y = M1[i].y;
    				k++;
    			}
    		}
    		for(j=1;j<=r2;j++){
    			if(book[j]==0){
    				T[k].v = M2[j].v;
    				T[k].x = M2[j].x;
    				T[k++].y = M2[j].y;
    			}
    		}
    
    		r=k-1;
    		k=1;
    		sort_x_y(T,r);
    		/* 矩阵加法 End */
    		printf("The added matrix is:\n");
    		if(flag==1){
    			/*打印列数Start*/
    			printf("    ");
    			for(i=1;i<=n1;i++)
    				printf("%4d",i);
    			/*打印列数End*/
    
    			/*  打印矩阵  Start*/
    			for(i=1;i<=m1;i++){
    				printf("\n%4d",i);
    				while(1){
    						if(T[k].x<i && k<=r)
    						k++;
                            else
    						break;
    					}
    				/*k=i k>i*/
    				for(j=1;j<=n1;j++)
    					if(k>r||T[k].x!=i)
    					printf("%4d",0);
    					else{
    						int temp=k;
    						int t=0;
    						while(T[temp].x==i && temp <= r){
    							if(T[temp].y==j){
    								t=1;
    								break;
    							}
    							else
    							temp++;
    						}
    						if(t==1)
    						printf("%4d",T[temp].v);
    						else
    						printf("%4d",0);
    					}
    			}
    			/*  打印矩阵  End*/
    			printf("\n");
    		}
    		else{
    	  		printf("Rows=%d,Cols=%d,r=%d\n",m1,n1,r);
    			for(i=1;i<=r;i++){
    				printf("%d %d %d\n",T[i].x,T[i].y,T[i].v);
    			}
    		}
    	}
     	else
     	printf("Can not add!\n");
    }
    
    void mult(int flag){
    	/*如果可以相乘*/
    	if(n1==m2){
    		/* 计算相乘矩阵 Start 第二个矩阵转置 */
    		sort_y_x(M2,r2);
    		sort_x_y(M1,r1);
    		int i,j,k=1;
    		i=M1[1].x;
    		/*index_1用来遍历M1的*/
    		int index_1=1;
    		while(index_1<=r1){
    			/* 存储x相同的数据 */
    			int t_index1[1000]={0};/*存y*/
    			int t_matrix1[1000]={0};/*存y对应的value*/
    			int top1=0;
    			/*先把第一个放进来 后面还有相同的x的话 就放进来 */
    			t_index1[top1]=M1[index_1].y;
    			t_matrix1[top1]=M1[index_1].v;
    			top1++;
    			index_1++;
    
    			while(M1[index_1].x==i){
    				t_index1[top1]=M1[index_1].y;
    				t_matrix1[top1]=M1[index_1].v;
    				top1++;
    				index_1++;
    			}
    			i=M1[index_1].x;
    			/* 此时,x 相同的  即同一行的 已经找到了 */
    			j = M2[1].y;
    			int index_2=1;
    			while(index_2<=r2){
    				/* 重复找x的操作 ,这里找的是y*/
    				int t_matrix2[10000]={0};
    				int t_index2[10000]={0};
    				int top2=0;
    				t_index2[top2]=M2[index_2].x;
    				t_matrix2[top2]=M2[index_2].v;
    				top2++;
    				index_2++;
    				while(M2[index_2].y==j){
    				t_index2[top2]=M2[index_2].x;
    				t_matrix2[top2]=M2[index_2].v;
    				top2++;
    				index_2++;
    				}
    				j=M2[index_2].y;
    				int sum=0;
    				int temp_i;
    				int temp_k1=0;
    	   			int temp_k2=0;
    	   			/*此时,已经找到了可以相乘的行列,进行相乘*/
    	   			while(temp_k1 < top1 && temp_k2 < top2){
    					if(t_index1[temp_k1]<t_index2[temp_k2])
    					temp_k1++;
    					else if(t_index1[temp_k1]>t_index2[temp_k2])
    					temp_k2++;
    					else{
    						sum+= t_matrix2[temp_k2] * t_matrix1[temp_k1];
    						temp_k1++;
    						temp_k2++;
    					}
    				}
    				/*将乘积结果放在乘法的数组M里*/
    				if(sum!=0){
    					M[k].x = M1[index_1-1].x;
    					M[k].y = M2[index_2-1].y;
    					M[k].v = sum;
    					k++;
    				}
    			}
    
    	}
    	rm=k-1;
    	/* 计算相乘矩阵 End */
    
    		sort_x_y(M,rm);
    		printf("The product matrix is:\n");
    		if(flag==1){
    			int k=1;
    			printf("    ");
    			for(i=1;i<=n2;i++)
    				printf("%4d",i);
    			for(i=1;i<=m1;i++){
    				printf("\n%4d",i);
    				while(1){
    						if(M[k].x<i && k<=rm)
    						k++;
    						else
    						break;
    					}
    				/*k=i k>r*/
    				for(j=1;j<=n2;j++)
    					if(k>rm||M[k].x!=i)
    					printf("%4d",0);
    					else{
    						int temp=k;
    						int t=0;
    						while(M[temp].x==i && temp <= rm){
    							if(M[temp].y==j){
    								t=1;
    								break;
    							}
    							else
    							temp++;
    						}
    						if(t==1)
    						printf("%4d",M[temp].v);
    						else
    						printf("%4d",0);
    					}
    			}
    			/*  打印矩阵  End*/
    			//printf("\n");
    		}
    		else{
    	  		printf("Rows=%d,Cols=%d,r=%d\n",m1,n2,rm);
    			for(i=1;i<=rm;i++){
    				printf("%d %d %d\n",M[i].x,M[i].y,M[i].v);
    			}
    		}
    
    	}
     	else
     	printf("Can not multiply!");
    
    }
    
    
    /* 对三元组进行排序,按照y的大小进行排序*/
    void sort_y(int left,int right,mat* Temp) {
    	if(left>=right)
    		return;
    	int i,j,t,temp1,temp2,temp3;
    	temp1 = Temp[left].x;
    	temp2 = Temp[left].y;
    	temp3 = Temp[left].v;
    	i = left;
    	j = right;
    	while(i!=j) {
    		while(Temp[j].y>=temp2 && i<j)
    			j--;
    		while(Temp[i].y<=temp2 && i<j)
    			i++;
    		if(i<j) {
    			t = Temp[i].y;
    			Temp[i].y = Temp[j].y;
    			Temp[j].y = t;
    			t = Temp[i].x;
    			Temp[i].x = Temp[j].x;
    			Temp[j].x = t;
    			t = Temp[i].v;
    			Temp[i].v = Temp[j].v;
    			Temp[j].v = t;
    		}
    	}
    	Temp[left].x= Temp[i].x;
    	Temp[left].y = Temp[i].y;
    	Temp[left].v = Temp[i].v;
    	Temp[i].x=temp1;
    	Temp[i].y=temp2;
    	Temp[i].v=temp3;
    	sort_y(left,i-1,Temp);
    	sort_y(i+1,right,Temp);
    }
    /* 对三元组进行排序,按照x的大小进行排序*/
    void sort_x(int left,int right,mat* Temp) {
    	if(left>=right)
    		return;
    	int i,j,t,temp1,temp2,temp3;
    	temp1 = Temp[left].x;
    	temp2 = Temp[left].y;
    	temp3 = Temp[left].v;
    	i = left;
    	j = right;
    	while(i!=j) {
    		while(Temp[j].x>=temp1 && i<j)
    			j--;
    		while(Temp[i].x<=temp1 && i<j)
    			i++;
    		if(i<j) {
    			t = Temp[i].y;
    			Temp[i].y = Temp[j].y;
    			Temp[j].y = t;
    			t = Temp[i].x;
    			Temp[i].x = Temp[j].x;
    			Temp[j].x = t;
    			t = Temp[i].v;
    			Temp[i].v = Temp[j].v;
    			Temp[j].v = t;
    		}
    	}
    	Temp[left].x= Temp[i].x;
    	Temp[left].y = Temp[i].y;
    	Temp[left].v = Temp[i].v;
    	Temp[i].x=temp1;
    	Temp[i].y=temp2;
    	Temp[i].v=temp3;
    	sort_x(left,i-1,Temp);
    	sort_x(i+1,right,Temp);
    }
    /*  三元组排序,先对y进行排序,在不改变y的顺序的情况下对x进行排序*/
    void sort_y_x(mat* Temp,int r){
    	int i,j;
    	sort_y(1,r,Temp);
    	for(i=1;i<=r;i++){
    		int t = Temp[i].y;
    		j=i;
    		while(j<=r){
    			if(Temp[j+1].y==t) j++;
    			else break;
    		}
    		if(j>i){
    			sort_x(i,j,Temp);
    			i=j;
    		}
    	}
    }
    /*  三元组排序,先对y进行排序,在不改变x的顺序的情况下对y进行排序*/
    void sort_x_y(mat* Temp,int r){
    	int i,j;
    	sort_x(1,r,Temp);
    	for(i=1;i<=r;i++){
    		int t = Temp[i].x;
    		j=i;
    		while(j<=r){
    			if(Temp[j+1].x==t) j++;
    			else break;
    		}
    		if(j>i){
    			sort_y(i,j,Temp);
    			i=j;
    		}
    	}
    }
    
    展开全文
  • 稀疏矩阵快速转置 利用三元组顺序表存放的矩阵M,用快速转置的算法是实现转置得到矩阵T,并将T按照三元组形式输出,每行输出一个元素,注意:矩阵输出顺序按照行号升序输出。其中,行数<20、列数<20。 输入...

    稀疏矩阵快速转置 

    利用三元组顺序表存放的矩阵M,用快速转置的算法是实现转置得到矩阵T,并将T按照三元组形式输出,每行输出一个元素,注意:矩阵输出顺序按照行号升序输出。其中,行数<20、列数<20。

    输入格式:

    第一行输入M的行数mu,M的列数nu,M中非零元个数tu 从第二行开始输入tu行,每行输入一个元素的行号i、列号j和值data。

    输出格式:

    按照T的行号升序输出,每行输出一个元素的行号,列号,元素值,三个值以空格为分隔符

    输入样例:

    在这里给出一组输入。例如:

    3 4 3
    0 1 6
    1 0 -1
    2 2 4

    输出样例:

    在这里给出相应的输出。例如:

    0 1 -1
    1 0 6
    2 2 4

    代码如下: 

    #include<stdio.h>
    typedef int ElemType;
    #define MAXSIZE 12500
    typedef struct {
    	int i, j;       //该非零元的行下标和列下标
    	ElemType e;     //数据域
    }Triple;
    typedef struct {
    	Triple data[MAXSIZE]; //非零元三元组表,data[0]使用了
    	int mu, nu, tu;           //矩阵的行数,列数和非零元个数
    }TSMatrix;
    void GreateSMatrix(TSMatrix* M);
    void TransposeSMatrix(TSMatrix* M, TSMatrix* T);
    void PrintSMatrix(TSMatrix* T);
    int main() {
    	TSMatrix *M=(TSMatrix*)malloc(sizeof(TSMatrix));
    	TSMatrix *T=(TSMatrix*)malloc(sizeof(TSMatrix));
    	GreateSMatrix(M);
    	TransposeSMatrix(M, T);
    	PrintSMatrix(T);
    	return 0;
    }
    void GreateSMatrix(TSMatrix* M) //创建稀疏矩阵M
    {
    	scanf("%d %d %d", &M->mu,&M->nu,&M->tu);
    	if ((M->mu) > 0 &&(M->nu) > 0) {
    		if (M->tu < MAXSIZE)
    		{
    			for (int i = 0; i < M->tu; i++) {
    				scanf("%d %d %d", &M->data[i].i,&M->data[i].j,&M->data[i].e);
    			}
    		}
    	}
    }
    void TransposeSMatrix(TSMatrix* M, TSMatrix* T)//求稀疏矩阵M的转置矩阵T
    {
    	T->mu = M->nu, T->nu = M->mu, T->tu = M->tu;
    	if (T->tu) {
    		int q=0 , p,col;
    		for(col=0;col<M->nu;col++)
    			for(p=0;p<M->tu;p++)
    				if (M->data[p].j == 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;
    					++q;
    				}
    	}
    }
    void PrintSMatrix(TSMatrix* T) //输出矩阵
    {
    	for (int i = 0; i < T->tu; i++) {
    		printf("%d %d %d", T->data[i].i, T->data[i].j, T->data[i].e);
    		printf("\n");
    	}
    }
    

     

    展开全文
  • 完成了加减乘,绝对无误 1、 加法:可以完成加法的情况下分别对每行处理,如果非零员的列标小则在插入之,相同则完成加法运算,如果结果非零则插入。否则继续下一个飞灵员的...最后用稀疏矩阵的存储方法保存非零员。
  • PTA5-1 稀疏矩阵的处理 (25 分)

    千次阅读 2021-12-14 00:05:53
    PTA5-1 稀疏矩阵的处理 (25 分) 现要求编程实现稀疏矩阵在“压缩”存储时的矩阵的常用操作,如输出、转置、求和、乘等。 即输入两个矩阵,完成如下操作: (1) 转置。对第一个矩阵进行转置并输出,前面输出标题 “The...

    PTA5-1 稀疏矩阵的处理 (25 分)

    现要求编程实现稀疏矩阵在“压缩”存储时的矩阵的常用操作,如输出、转置、求和、乘等。 即输入两个矩阵,完成如下操作: (1) 转置。对第一个矩阵进行转置并输出,前面输出标题 “The transformed matrix is:”

    (2) 矩阵加。如两个矩阵可以相加,进行两个矩阵的加运算并输出,前面输出标题 “The added matrix is:”;如果不能相加,则输出 “Can not add!”;

    (3) 矩阵乘。如果两个矩阵可以相乘,进行两个矩阵的乘并输出,前面输出标题 “The product matrix is:”; 如果不能相乘,则输出 “Can not multiply!”

    输入格式:
    输入有多行,第1行包括三个整数,分别是矩阵的大小m,n及非零元素的个数r。后面r行分别输入各个非零元素的 行、列、值。

    输出格式:
    输出有两种形式,操作时分别用符号“L”、“H”指出输出形式。 L: 以三元组的形式输出,即先输出矩阵的行数、列数和非零元素个数,再按行主序依次输出各个非零元素的行、列和值。各输出项之间空格分隔。 H: 按人们习惯的矩阵格式输出,即输出一个mn的矩阵,是零元素的输出0,非零元素输出元素值。设定每个元素占位宽度为4。(要输出矩阵的行号和列号,并对齐)
    输入样例1:

    10 8 4 
    1 8 1
    3 3 2 
    3 7 3 
    10 1 4 
    10 8 2 
    2 6 1 
    3 7 -3
    H 
    

    输入样例2:

    100 90 5
    1 10 100
    50 60 200
    50 80 100
    60 60 200
    99 89 10
    100 90 4
    1 1 10
    50 60 -200
    50 80 100
    70 70 10
    L
    

    输出样例1:

    The transformed matrix is:
           1   2   3   4   5   6   7   8   9  10
       1   0   0   0   0   0   0   0   0   0   4
       2   0   0   0   0   0   0   0   0   0   0
       3   0   0   2   0   0   0   0   0   0   0
       4   0   0   0   0   0   0   0   0   0   0
       5   0   0   0   0   0   0   0   0   0   0
       6   0   0   0   0   0   0   0   0   0   0
       7   0   0   3   0   0   0   0   0   0   0
       8   1   0   0   0   0   0   0   0   0   0
    The added matrix is:
           1   2   3   4   5   6   7   8
       1   0   0   0   0   0   0   0   1
       2   0   0   0   0   0   1   0   0
       3   0   0   2   0   0   0   0   0
       4   0   0   0   0   0   0   0   0
       5   0   0   0   0   0   0   0   0
       6   0   0   0   0   0   0   0   0
       7   0   0   0   0   0   0   0   0
       8   0   0   0   0   0   0   0   0
       9   0   0   0   0   0   0   0   0
      10   4   0   0   0   0   0   0   0
    Can not multiply!
    

    输出样例2:

    The transformed matrix is:
    Rows=90,Cols=100,r=5
    10 1 100
    60 50 200
    60 60 200
    80 50 100
    89 99 10
    The added matrix is:
    Rows=100,Cols=90,r=6
    1 1 10
    1 10 100
    50 80 200
    60 60 200
    70 70 10
    99 89 10
    Can not multiply!
    

    代码
    可以自行优化一下,用函数包装会简洁很多。

    #include<bits/stdc++.h>
    using namespace std;
    typedef struct CrossNode* List;
    int a[10000000][3];
    struct CrossNode
    {
        int x,y,value;
        List right,down;
    };
    struct LNode
    {
        List* rhead;
        List* chead;
        int mx,my,mvalue;
    };
    typedef struct LNode* Node;
    void creatCrossNode(Node L1,int c)
    {
        int m,n,p;
        cin>>m>>n>>p;
        L1->mx=m;
        L1->my=n;
        L1->mvalue=p;
        L1->rhead=(List*)malloc(sizeof(List)*(m+1));
        L1->chead=(List*)malloc(sizeof(List)*(n+1));
        for(int i=1; i<=m; i++)
        {
            L1->rhead[i]=NULL;
        }
        for(int i=1; i<=n; i++)
        {
            L1->chead[i]=NULL;
        }
        int cnt=0;
        while(p--)
        {
            int i,j,k;
            cin>>i>>j>>k;
            if(c==1)
            {
                a[cnt][0]=i;
                a[cnt][1]=j;
                a[cnt++][2]=k;
            }
            List p=(List)malloc(sizeof(struct CrossNode));
            p->x=i;
            p->y=j;
            p->value=k;
            List q;
            if(L1->rhead[i]==NULL||L1->rhead[i]->y>j)
            {
                p->right=L1->rhead[i];
                L1->rhead[i]=p;
            }
            else
            {
                q=L1->rhead[i];
                while(q->right&&q->right->y<j)
                {
                    q=q->right;
                }
                p->right=q->right;
                q->right=p;
            }
            if(L1->chead[j]==NULL||L1->chead[j]->x>i)
            {
                p->down=L1->chead[j];
                L1->chead[j]=p;
            }
            else
            {
                q=L1->chead[j];
                while(q->down&&q->down->x<i)
                {
                    q=q->down;
                }
                p->down=q->down;
                q->down=p;
            }
        }
    }
    void createss(Node L1,Node L2)
    {
        L1->mx=L2->mx;
        L1->my=L2->my;
        L1->mvalue=L2->mvalue;
        L1->rhead=(List*)malloc(sizeof(List)*(L1->mx+1));
        L1->chead=(List*)malloc(sizeof(List)*(L1->my+1));
        for(int i=1; i<=L1->mx; i++)
        {
            L1->rhead[i]=NULL;
        }
        for(int i=1; i<=L1->my; i++)
        {
            L1->chead[i]=NULL;
        }
        int p=L1->mvalue;
        int cnt=0;
        while(p--)
        {
            int i,j,k;
            i=a[cnt][0];
            j=a[cnt][1];
            k=a[cnt++][2];
            List p=(List)malloc(sizeof(struct CrossNode));
            p->x=i;
            p->y=j;
            p->value=k;
            List q;
            if(L1->rhead[i]==NULL||L1->rhead[i]->y>j)
            {
                p->right=L1->rhead[i];
                L1->rhead[i]=p;
            }
            else
            {
                q=L1->rhead[i];
                while(q->right&&q->right->y<j)
                {
                    q=q->right;
                }
                p->right=q->right;
                q->right=p;
            }
            if(L1->chead[j]==NULL||L1->chead[j]->x>i)
            {
                p->down=L1->chead[j];
                L1->chead[j]=p;
            }
            else
            {
                q=L1->chead[j];
                while(q->down&&q->down->x<i)
                {
                    q=q->down;
                }
                p->down=q->down;
                q->down=p;
            }
        }
    
    }
    void shuchu(Node L1)
    {
        printf("    ");
        for(int i=1; i<=L1->mx; i++)
        {
            printf("%4d",i);
        }
        cout<<endl;
        int cnt=0;
        for(int i=1; i<=L1->my; i++)
        {
            cnt=0;
            List p=L1->chead[i];
            printf("%4d",i);
            while(p)
            {
                for(int x=cnt+1; x<p->x; x++)
                {
                    printf("   0");
                }
                cnt=p->x;
                printf("%4d",p->value);
                p=p->down;
            }
            for(int x=cnt+1; x<=L1->mx; x++)
            {
                printf("   0");
            }
            cout<<endl;
        }
    }
    void shuchusss(Node L1)
    {
        printf("    ");
        for(int i=1; i<=L1->my; i++)
        {
            printf("%4d",i);
        }
        cout<<endl;
        int cnt=0;
        for(int i=1; i<=L1->mx; i++)
        {
            cnt=0;
            List p=L1->rhead[i];
            printf("%4d",i);
            while(p)
            {
                for(int x=cnt+1; x<p->y; x++)
                {
                    printf("   0");
                }
                cnt=p->y;
               printf("%4d",p->value);
                p=p->right;
            }
            for(int x=cnt+1; x<=L1->my; x++)
            {
                printf("   0");
            }
            cout<<endl;
        }
    }
    int main()
    {
        Node L1=(Node)malloc(sizeof(struct LNode));
        L1->chead=NULL;
        L1->rhead=NULL;
        creatCrossNode(L1,1);
        Node L2=(Node)malloc(sizeof(struct LNode));
        L2->chead=NULL;
        L2->rhead=NULL;
        creatCrossNode(L2,0);
        Node L4=(Node)malloc(sizeof(struct LNode));
        L4->rhead=NULL;
        L4->chead=NULL;
        createss(L4,L1);
        char ch;
        cin>>ch;
        cout<<"The transformed matrix is:"<<endl;
        //shuchusss(L1);
        //shuchusss(L2);
        if(ch=='L')
        {
            cout<<"Rows="<<L1->my<<",Cols="<<L1->mx<<",r="<<L1->mvalue<<endl;
            for (int i = 1; i <= L1->my; i++)
            {
                if (L1->chead[i])
                {
                    List p = L1->chead[i];
                    while (p)
                    {
                        printf("%d %d %d\n", p->y, p->x, p->value);
                        p = p->down;
                    }
                }
            }
        }
        else
        {
            shuchu(L1);
        }
        if(L1->mx==L2->mx&&L1->my==L2->my)
        {
                for(int i=1; i<=L2->mx; i++)
            {
                List p=L2->rhead[i];
                while(p)
                {
                    List op=(List)malloc(sizeof(struct CrossNode));
                    op->x=p->x;
                    op->y=p->y;
                    op->value=p->value;
                    if(L4->rhead[i]==NULL||L4->rhead[i]->y>p->y)
                    {
                        L4->mvalue++;
                        op->right=L4->rhead[i];
                        L4->rhead[i]=op;
                    }
                    else if(L4->rhead[i]->y==p->y)
                    {
                        L4->rhead[i]->value=L4->rhead[i]->value+p->value;
                        if(L4->rhead[i]->value==0)
                        {
                            L4->mvalue--;
                        }
                    }
                    else if(L4->rhead[i]->y<p->y)
                    {
                        List q=L4->rhead[i];
                        while(q->right&&q->right->y<p->y)
                        {
                            q=q->right;
                        }
                        if(q->right&&p&&p->y==q->right->y)
                        {
                            q->right->value=q->right->value+p->value;
                            if(q->right->value==0)
                            {
                                L4->mvalue--;
                            }
                        }
                        else
                        {
                            L4->mvalue++;
                            op->right=q->right;
                            q->right=op;
                        }
                    }
                    p=p->right;
                }
            }
            cout<<"The added matrix is:"<<endl;
            if(ch=='L')
            {
                cout<<"Rows="<<L4->mx<<",Cols="<<L4->my<<",r="<<L4->mvalue<<endl;
                for(int i=1; i<=L4->mx; i++)
                {
                    if(L4->rhead[i])
                    {
                        List p=L4->rhead[i];
                        while(p)
                        {
                            if(p->value!=0)
                            {
                                printf("%d %d %d\n", p->x, p->y, p->value);
                            }
                            p=p->right;
                        }
                    }
                }
            }
            else
            {
                shuchusss(L4);
            }
    
        }
        else
        {
            cout<<"Can not add!"<<endl;
        }
        if(L1->my==L2->mx)
        {
            Node L5=(Node)malloc(sizeof(struct LNode));
            L5->chead=NULL;
            L5->rhead=NULL;
            L5->mx=L1->mx;
            L5->my=L2->my;
            L5->mvalue=0;
            L5->rhead=(List*)malloc(sizeof(List)*(L5->mx+1));
            L5->chead=(List*)malloc(sizeof(List)*(L5->my+1));
            for(int i=1; i<=L5->mx; i++)
            {
                L5->rhead[i]=NULL;
            }
            for(int i=1; i<=L5->my; i++)
            {
                L5->chead[i]=NULL;
            }
            for(int i=1; i<=L1->mx; i++)
            {
                List p,q;
                p=L1->rhead[i];
                if(p)
                {
                    for(int j=1; j<=L2->my; j++)
                    {
                        //cout<<j<<endl;
                        int sum=0;
                        q=L2->chead[j];
                        p=L1->rhead[i];
                        while(q&&p)
                        {
                            if(q->x==p->y)
                            {
                                sum=sum+q->value*p->value;
                                p=p->right;
                                q=q->down;
                            }else if(q->x>p->y)
                            {
                                p=p->right;
                            }else
                            {
                                q=q->down;
                            }
                        }
                        //cout<<"sum="<<sum<<endl;
                        if(sum!=0)
                        {
                            L5->mvalue++;
                            List op=(List)malloc(sizeof(struct CrossNode));
                            op->x=i;
                            op->y=j;
                            op->value=sum;
                            if(L5->rhead[i]==NULL||L5->rhead[i]->y>j)
                            {
                                op->right=L5->rhead[i];
                                L5->rhead[i]=op;
                                // cout<<"****"<<endl;
                            }
                            else
                            {
                                List oq=L5->rhead[i];
                                while(oq->right&&oq->right->y<j)
                                {
                                    oq=oq->right;
                                }
                                op->right=oq->right;
                                oq->right=op;
                            }
                        }
                    }
                }
    
            }
            cout<<"The product matrix is:"<<endl;
            if(ch=='L')
            {
                cout<<"Rows="<<L5->my<<",Cols="<<L5->mx<<",r="<<L5->mvalue<<endl;
                for(int i=1; i<=L5->mx; i++)
                {
                    if(L5->rhead[i])
                    {
                        List p=L5->rhead[i];
                        while(p)
                        {
                            if(p->value!=0)
                            {
                                printf("%d %d %d\n", p->x, p->y, p->value);
                            }
                            p=p->right;
                        }
                    }
                }
            }
            else
            {
                shuchusss(L5);
            }
        }
        else
        {
            cout<<"Can not multiply!";
        }
        return 0;
    }
    
    
    展开全文
  • 稀疏矩阵加法(PTA)

    千次阅读 2019-05-29 16:38:43
    稀疏矩阵加法 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​1,表示接下来要输入的A中的非零元素的个数。 接...
  • 课后作业:将二维矩阵转换成稀疏矩阵表示并存储到磁盘内,然后讲系数矩阵表示从磁盘中读取恢复为原矩阵。 Java IO流 学习产出: public class SparseArray { public static void main(String[] args) { int chess...
  • PTA7-1 稀疏矩阵加法

    2021-10-18 10:19:45
    给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数RowRowRow和ColColCol,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N1N_1N1​ ​ ,表示接下来要输入的A中的非零元素的...
  • 主题:三元组顺序表表示的稀疏矩阵转置。 问题: 输入格式: 输入第1行为矩阵行数m、列数n及非零元素个数t。 按行优先顺序依次输入t行,每行3个数,分别表示非零元素的行标、列标和值。 输出格式: 输出转置后的三元组...
  • 7-1 稀疏矩阵加法 PTA

    2022-01-07 13:44:19
    给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N1​,表示接下来要输入的A中的非零元素的个数。 接下来是N1​行...
  • 1、进行加法运算的两个矩阵由用户输入。并且用三元组顺序表表示。 2、程序首先判断两个矩阵是否能够相加。若能,在进行运算后在屏幕上现实结果,否则给出相应信息。
  • 稀疏矩阵的表示与运算一.介绍二.实现稀疏矩阵的原理1.稀疏矩阵的顺序存储2.稀疏矩阵的转置T3.求转置的方法4.快速求转置法5.稀疏矩阵加法(减法同理)6.稀疏矩阵的乘法三.稀疏矩阵的代码定义1.稀疏矩阵的元素2.稀疏...
  • 数据结构——稀疏矩阵(C语言)

    千次阅读 2021-09-03 16:17:48
    矩阵什么是矩阵代码实现三元组以及普通转置矩阵以及三元组的结构体相应功能的函数实现初始化稀疏矩阵矩阵转置链表数据的删除按位置查找数据元素合并两个链表输出链表相应功能集成调用主函数运行截图 什么是矩阵 ...
  • 稀疏矩阵加法

    千次阅读 2018-11-20 18:48:27
    PTA-7-1 稀疏矩阵加法 (20 分) 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​1​​,表示接下来要输入的...
  • PTA 7-3 稀疏矩阵加法 (20 分)

    千次阅读 2019-05-29 16:48:59
    给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​1​​,表示接下来要输入的A中的非零元素的个数。 接下来是N​...
  • PTA练习题——稀疏矩阵的加法。 题目分析:此题的核心在于找到行数和列数相等的元素进行求和,若和为零时则舍去,当行数/列数不等时分类进行讨论。 此题共分为七种情况进行讨论,分别为: 1 ai=bi;aj=bj 2 ai&...
  • 三元组顺序表表示的稀疏矩阵转置。 输入格式: 输入第1行为矩阵行数m、列数n及非零元素个数t。 按行优先顺序依次输入t行,每行3个数,分别表示非零元素的行标、列标和值。 输出格式: 输出转置后的三元组顺序表结果,...
  • 三元组顺序表表示的稀疏矩阵加法——数据结构及算法
  • (c语言)稀疏矩阵加法

    千次阅读 2020-04-17 15:01:38
    实现三元组表示的两个稀疏矩阵的加法。相关定义如下 #define MAXSIZE 100 //假设非零元个数的最大值为100 typedef struct { int i,j; //非零元的行下标和列下标,i 和 j 从 1 开始计数,与数学中矩阵元素的...
  • 6-2 三元组顺序表表示的稀疏矩阵转置 (10 分) 本题要求实现一个函数,实现三元组顺序表表示的稀疏矩阵转置。 函数接口定义: struct tripletable * trans(struct tripletable *t1); 其中 t1 是用户传入的参数。 函数...
  • C语言数据结构:稀疏矩阵的加法(三元组实现)

    万次阅读 多人点赞 2019-05-05 16:44:40
    printf("请输入稀疏矩阵的行数和列数\n"); scanf("%d %d", &T->mu, &T->nu); printf("请输入稀疏矩阵的元素\n"); for (int i = 1; i <= T->mu; i++) { for (int j = 1; j <= T->nu; j++) { scanf("%d",...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 137
精华内容 54
关键字:

pta矩阵转稀疏矩阵

友情链接: nixietube.rar