首页 » Program » C/C++ » 正文

稀疏矩阵快速转置

问: 1.什么是稀疏矩阵?
答: 假设在m*n的矩阵中,有t个元素不为0,令&=t/(m*n),&就是矩阵的稀疏因子,通常认为&<=0.05时称为稀疏矩阵。——–摘自《数据结构(C语言版)》
2.什么是转置?
答:在矩阵M中,每个元素的行和列互换,构成新的矩阵T,T即M的转置矩阵,行列互换就是转置(Mij = Tji)。
3.什么是三元组?
答:稀疏矩阵中每个非0元的行标,列标和数值构成一个三元组。
4.什么是三元组表?
答:稀疏矩阵中的每个非0元构成的三元组放在一起,加上稀疏矩阵的总行数,总列数和非0元总数构成三元组表。
5.为什么我看不懂fastt函数的最后一个for循环啊?(哈哈别问我为什么知道,因为我也想了很久才懂)
答:自己模拟一遍,看看注释。

公式:计算M中第col列的第一个非0元素在T三元组表中的位置
cpot[1] = 1;
cpot[col] = cpot[col-1] + num[col-1];

#include <stdio.h>

typedef struct
{
    int i,j;
    int e;
} triple;   //存行标,列标,数值

typedef struct       //三元组表
{
    triple data[1000+1];     //非0元的信息
    int numh,numl,tu;
} ts;       //存三元组,总行数,总列数,非零元素总数

int fastt(ts M,ts &T)
{
    int col,p,q,t;
    int num[1000],cpot[1000];   //num存M中第col列中非0元素个数,cpot存M中第col列的第一个非0元素在T中的位置
    T.numh = M.numl;
    T.numl = M.numh;
    T.tu = M.tu;
    if (T.tu)
        {
            for (col=1; col<=M.numl; col++)
                {
                    num[col] = 0;      //初始化全部0
                }
            for (t=1; t<=M.tu; t++)
                {
                    num[M.data[t].j]++;    //计算每一列非零元素个数
                }

            cpot[1] = 1;      //固定的
            for (col=2; col<=M.numl; col++)
                {
                    cpot[col] = cpot[col-1] + num[col-1];   //公式,计算M每列第一个非零元素转置后在T三元组表的位置
                }

            for (p=1; p<=M.tu; p++)
                {
                    col = M.data[p].j;
                    q = cpot[col];  //如果一列中不止一个元素,后面的++就有用了
                    T.data[q].i = M.data[p].j;
                    T.data[q].j = M.data[p].i;     //Tij = Mji
                    T.data[q].e = M.data[p].e;
                    cpot[col]++;                 //加1为这一列的下一个非0元素做准备
                }
        }
    return 1;
}

void creatzz(ts &M)
{
    printf("请输入稀疏矩阵非零元素个数\n");
    scanf("%d",&M.tu);
    printf("请输入稀疏矩阵行数\n");
    scanf("%d",&M.numh);
    printf("请输入稀疏矩阵列数\n");
    scanf("%d",&M.numl);
    printf("输入稀疏矩阵非零元素三元组信息\n");
    for (int k=1; k<=M.tu; k++)
        {
            printf("第%d个元素的行标:",k);
            scanf("%d",&M.data[k].i);
            printf("第%d个元素的列标:",k);
            scanf("%d",&M.data[k].j);
            printf("此元素值:");
            scanf("%d",&M.data[k].e);
        }
}

void printM(ts &M)
{
    int p,q,t = 1,e = 0,flag = 0;
    for (p=1; p<=M.numh; p++) //有数值打印数值没数值打印0
        {
            for (q=1; q<=M.numl; q++)
                {
                    for (t=1; t<=M.tu; t++)
                        {
                            if (M.data[t].i==p&&M.data[t].j==q) //搜索这一坐标有无非0元
                                {
                                    printf("%5d",M.data[t].e);   //遇到非0元就打印其数值
                                    flag = 1;
                                }
                        }
                    if (flag==0)
                        printf("%5d",e);   //没有非0元打印0
                    flag = 0;  //如果打印了非0元,flag重新变回0
                }
            printf("\n");
        }
    printf("\n");
}

void printT(ts M)   //打印三元组表(行,列,值)
{
    printf("i  j   v\n");
    for (int i=1; i<=M.tu; i++)
        {
            printf("%d  %d   %d\n",M.data[i].i,M.data[i].j,M.data[i].e);
        }
}

int main()
{

    ts M,T;
    creatzz(M);   //建立三元组表
    printf("原稀疏矩阵:\n");
    printM(M);    //打印没转置的稀疏矩阵
    printf("原稀疏矩阵三元组顺序表:\n");
    printT(M);    //打印三元组顺序表
    fastt(M,T);                   //转置!
    printf("转置后的稀疏矩阵:\n");
    printM(T);
    printf("转置后的稀疏矩阵三元组顺序表:\n");
    printT(T);
    return 0;
}

赞 (0)

Comment