C语言：稀疏矩阵的转置

柔情只为你懂 2022-08-03 14:42 198阅读 0赞

/*
    	稀疏矩阵的相关操作
    	1.存储：三元组结构，存储行、列、值
    	2.转置: 1)按照列数进行转置，2)按照三元组的次数进行转置,快速转置
    */
    
    # include<stdio.h>
    # include<malloc.h>
    
    //定义三元组
    typedef struct
    {
    	int x;  //横坐标
    	int y;  //纵坐标
    	int v;   //值
    }Tri;
    
    //定义稀疏矩阵的顺序存储结构
    typedef struct
    {
    	Tri * data;  //存储三元组空间的基址
    	int row;  //矩阵行数
    	int col;  //矩阵列数
    	int num;  //非0元素个数
    }Maxi;
    
    void MaxiPrint(Maxi M);  //矩阵打印
    Maxi TransportCol(Maxi M);  //1)按照列数进行转置
    Maxi TransportFast(Maxi M);  //2)快速转置
    
    int main(void)
    {
    	Maxi M;
    	int row, col, num;  //行、列、非0个数
    	int i, x, y, v;
    
    	printf("输入矩阵的大小 和 非0元素的个数：");
    	scanf("%d%d%d", &row, &col, &num);
    
    	M.row = row;
    	M.col = col;
    	M.num = num;
    	M.data = (Tri *)malloc(sizeof(Tri) * num);  //开辟三元组存储空间
    
    	//输入矩阵的三元组值
    	printf("注意：输入的三元组先按行排列，再列排列\n");
    
    	for(i = 0; i < num; i++)  //矩阵赋值
    	{
    		printf("输入矩阵的第%d个三元组值x,y,v：", i+1);
    		scanf("%d%d%d", &x, &y, &v);
    		M.data[i].x = x;
    		M.data[i].y = y;
    		M.data[i].v = v;
    	}
    
    	MaxiPrint(M);
    
    	//1)按照列数进行转置
    	Maxi T = TransportCol(M);
    	MaxiPrint(T);
    
    	//2)快速转置
    	Maxi F = TransportFast(M);
    	MaxiPrint(F);
    
    	return 0;
    }
    
    //打印矩阵M
    void MaxiPrint(Maxi M)
    {
    	int i, j, k;
    	bool flag;
    
    	for(i = 0; i < M.row; i++)
    	{
    		for(j = 0; j < M.col; j++)
    		{
    			flag = false;  //非0标记
    
    			for(k = 0; k < M.num; k++)
    			{
    				if(i == M.data[k].x && j == M.data[k].y)
    				{
    					printf("%d ", M.data[k].v);
    					flag = true;
    					break;
    				}
    			}
    			if(flag == false)
    			{
    				printf("0 ");
    			}
    		}
    		printf("\n");
    	}
    
    	printf("\n");
    }
    
    //1)按照列数进行转置
    Maxi TransportCol(Maxi M)
    {
    	Maxi T;
    	T.row = M.col;
    	T.col = M.row;
    	T.num = M.num;
    	T.data = (Tri *)malloc(sizeof(Tri) * T.num);
    
    	int i, j, k = 0;
    	for(j = 0; j < M.col; j++)  //M的列数
    	{
    		for(i = 0; i < M.num; i++)  //非0个数
    		{
    			if(M.data[i].y == j)
    			{
    				T.data[k].x = M.data[i].y;
    				T.data[k].y = M.data[i].x;
    				T.data[k].v = M.data[i].v;
    				k++;
    			}
    		}
    	}
    
    	return T;
    }
    
    //2)快速转置
    Maxi TransportFast(Maxi M)
    {
    	int i, q, col;
    	Maxi T;
    	T.row = M.col;
    	T.col = M.row;
    	T.num = M.num;
    	T.data = (Tri *)malloc(sizeof(Tri) * T.num);
    
    	//记录M中每列中非0元素的个数（即，T中每行元素的个数）
    	int * num = (int *)malloc(sizeof(int) * M.col);
    
    	for(i = 0; i < M.col; i++)  //初始化
    	{
    		num[i] = 0;
    	}
    
    	for(i = 0; i < M.num; i++)
    	{
    		num[M.data[i].y] ++;
    	}
    
    	//T中每行元素的的第一个非0元素在T.data的位置
    	int * index = (int *)malloc(sizeof(int) * T.row);
    	index[0] = 0; //T中第0行元素在T.data中的位置
    
    	for(i = 1; i < T.row; i++)
    	{
    		index[i] = index[i - 1] + num[i - 1];
    	}
    
    	//遍历M,转置矩阵T每行元素，按列的顺序出现
    	for(i = 0; i < M.num; i++)
    	{
    		 col = M.data[i].y;  //M.data元素的列号
    		 q = index[col];
    
    		 T.data[q].x = M.data[i].y;
    		 T.data[q].y = M.data[i].x;
    		 T.data[q].v = M.data[i].v;
    
    		 index[col] ++;
    	}
    
    	return T;
    }

![Center][]

[Center]: /images/20220731/13709af89ca84370891477cae80dd9e3.png