NOJ数据结构实验003——稀疏矩阵转置

冷不防 2023-01-13 10:00 178阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210417230613695.png]  
本题要求使用三元组进行矩阵转置，方法有两种，列序递增转置以及一次定位快速转置。  
第一种方法思路简单，即将行列直接交换再进行排列，但占用空间较多，时间较慢。  
第二种方法耗时较短，思路简述为记录每一列元素个数在num数组中，以及将各列元素第一次出现位置在position数组中，以此进行快速转置。  
代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 2000
    
    typedef struct
    {
        
        int row, col;//非零元行数、列数
        int data;    //非零元数据
    }Triple;
    
    typedef struct
    {
        
        Triple elem[MAXSIZE];
        int row_m, col_n, len;  //矩阵行、列、非零元个数
    }TSMatrix;
    
    TSMatrix In, Out;  //定义全局变量
    
    void InitMatrix(TSMatrix *M, int m, int n);   //初始化矩阵
    void ScanMatrix(TSMatrix *M);                  //输入矩阵非零数据
    void TransMatrix(TSMatrix *In, TSMatrix *Out); //转置矩阵
    void PrintMatrix(TSMatrix *Out);              //输出矩阵
    
    int main()
    {
        
        int m, n;
        scanf("%d%d", &m, &n);
        InitMatrix(&In, m, n);
        ScanMatrix(&In);
        TransMatrix(&In, &Out);
        PrintMatrix(&Out);
        return 0;
    }
    
    void InitMatrix(TSMatrix *M, int m, int n)
    {
           //初始化矩阵
        M->row_m = m;
        M->col_n = n;
        M->len = 0;
    }
    
    void ScanMatrix(TSMatrix *In)
    {
          //输入矩阵非零数据
        int tmp_row, tmp_col, tmp_data;
        int i = 0;
        while(1) {
        
            scanf("%d", &tmp_row);
            getchar();
            scanf("%d", &tmp_col);
            getchar();
            scanf("%d", &tmp_data);
            if (tmp_row == 0 && tmp_col == 0 && tmp_data == 0) {
        
                break;
            }
            In->len++;
            In->elem[i].row = tmp_row;
            In->elem[i].col = tmp_col;
            In->elem[i].data = tmp_data;
            i++;
        }
    }
    
    void TransMatrix(TSMatrix *In, TSMatrix *Out)
    {
          //转置矩阵
        int *num, *position, tmp_col, tmp_position;
        int tmp_col_n = In->col_n + 1;
        num = (int*) malloc (sizeof(int)*tmp_col_n);
        position = (int*) malloc (sizeof(int)*tmp_col_n);
        Out->row_m = In->col_n;
        Out->col_n = In->row_m;
        Out->len = In->len;
        for (int i = 0; i < In->col_n; i++) {
        
        	//将num元素置零
            num[i] = 0;
        }
        for (int i = 0; i < In->len; i++) {
        
        	//记录矩阵In各列元素个数
           num[In->elem[i].col]++;
        }
        position[0] = 0;
        for (int i = 1; i < In->col_n; i++) {
        
        	//记录各列元素应放置在数组的位置
            position[i] = position[i-1] + num[i-1];
        }
        for (int i = 0; i < In->len; i++) {
        
        	//开始转置
            tmp_col = In->elem[i].col;
            tmp_position = position[tmp_col];
            Out->elem[tmp_position].row = In->elem[i].col;
            Out->elem[tmp_position].col = In->elem[i].row;
            Out->elem[tmp_position].data = In->elem[i].data;
            position[tmp_col]++;
        }
    }
    
    void PrintMatrix(TSMatrix *Out)
    {
          //输出矩阵
        for (int i = 0; i < Out->len; i++) {
        
            printf("%d %d %d\n", Out->elem[i].row, Out->elem[i].col, Out->elem[i].data);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/841382196919443cb293beec57ec281f.png
[20210417230613695.png]: /images/20221022/fe64d5c4595c4fe8a25dab348295f903.png