矩阵转置的两种算法

#include <cstdio>
#include <cstdlib>
//#define _OJ_
typedef struct Triple1
{
    int i1;
    int j1;
    int data;            //用三元组表来存储稀疏矩阵
} Triple1, *Triple;

typedef struct Matrix1
{
    Triple1 elem[100];
    int row;
    int colum;
    int cnt;            //压缩矩阵行数列数及非零数的个数
} Matrix1, *Matrix;

void
TansposeMatrix(Matrix M, Matrix T)
{
    int i, j, q;
    T->cnt = M->cnt;  T->row = M->colum;  T->colum = M->row;

    if(M->cnt > 0) {
     q = 1;
     for(i = 1;i <= T->row; i++) {      //0号位不用T中的行从小到大去寻找M中的列配对
        for(j = 1;j <= T->cnt; j++) {   //和elem中的数每一个j1配对
              if(i == M->elem[j].j1) {
             T->elem[q].i1   = M->elem[j].j1;
             T->elem[q].data = M->elem[j].data;
             T->elem[q].j1 = M->elem[j].i1;               q++;
             }
         }
      }
   }

}
// 当非零个数和row * colum 相同时候 复杂度为row * colum  * colum;仅仅适于cnt<<row * colum时

void
transposematrix1(Matrix M, Matrix T)
{
    int i, j, col, p;
    int num[100], cpot[100];
    T->row = M->colum;    T->colum = M->row;  T->cnt = M->cnt;

    if(T->cnt > 0) {
     for(i = 1;i <= M->colum; i++)
     num[i] = 0;
     for(i = 1;i <= M->cnt; i++)
     ++num[M->elem[i].j1];      //计算M中每一列的非零元素个数

     cpot[0] = 1;
     for(j = 1;j <= M->colum; j++)
     cpot[j] = cpot[j - 1] + num[j - 1];   //计算每一列的第一个非零元素在elem的下标

     for(i = 1;i <= M->cnt; i++) {
     col = M->elem[i].j1;    p = cpot[col];
     T->elem[p].i1 = M->elem[i].j1;
     T->elem[p].j1 = M->elem[i].i1;
     T->elem[p].data = M->elem[i].data;    ++cpot[col];
     //计算完第一个后下标加一以便第n个非零元素计算
      }
   }

}
//复杂度为cnt + colum 当cnt = row * colum 和经典算法一样为row * colum;

int main(int argc, char const *argv[]) {
#ifndef _OJ_  //ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    int i;
    Matrix M, T;
    M = (Matrix) malloc (sizeof(Matrix1));
    T = (Matrix) malloc (sizeof(Matrix1));
    scanf("%d %d %d", &M->row, &M->colum, &M->cnt);

    printf("原矩阵如下:\n");
    for(i = 1;i <= M->cnt; i++) {
    scanf("%d  %d  %d", &M->elem[i].i1,  &M->elem[i].j1, &M->elem[i].data);
    printf("%d %d %d\n", M->elem[i].i1, M->elem[i].j1, M->elem[i].data);
    }

    TansposeMatrix(M, T);
    printf("稀疏矩阵的转置算法一如下所示:\n");
    for(i = 1;i <= T->cnt; i++)
    printf("%d %d %d\n", T->elem[i].i1, T->elem[i].j1, T->elem[i].data);

    transposematrix1(M, T);
    printf("稀疏矩阵的转置算法二如下所示:\n");
    for(i = 1;i <= T->cnt; i++)
    printf("%d %d %d\n", T->elem[i].i1, T->elem[i].j1, T->elem[i].data);

    return 0;
}
  

  

时间: 12-04

矩阵转置的两种算法的相关文章

NMath矩阵分解的两种方式

概述:本教程为您介绍.Net唯一的数学与统计学运算库NMath,实现矩阵分解的两种方法. Nmath中包括用于构造和操作矩阵QR和奇异值分解的分解类.QR分解如下表示: 1 AP=QR 其中P是一个可置换矩阵,Q是正交的,且R为上梯形.矩阵A的奇异值分解(SVD)的形式表示为: 1 A=USV* 其中U和V是正交的,S是对角的,和V *表示一个真正的矩阵V或一个复杂的矩阵V的条目沿对角线S的共轭转置的奇异值. 接下来带来一个矩阵分解类的实例,下面代码示例为从FloatMatrix创建FloatQ

hdu 1162 Eddy&#39;s picture 最小生成树入门题 Prim+Kruskal两种算法AC

Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7428    Accepted Submission(s): 3770 Problem Description Eddy begins to like painting pictures recently ,he is sure of himself to

次小生成树的两种算法

一."换边"算法 用Kruskal求最小生成树,标记用过的边.求次小生成树时,依次枚举用过的边,将其去除后再求最小生成树,得出所有情况下的最小的生成树就是次小的生成树.可以证明:最小生成树与次小生成树之间仅有一条边不同. 这样相当于运行m次Kruskal算法. 复杂度O(m^2) 示例代码: int Kruskal_MinTree() { int u,v; init(); int i,flag,cnt; minedge = 0; flag = cnt = 0; int tmp = 0;

最小生成树的两种算法:Prim和Kruskal算法

越来越明白了一个道理:你写不出代码的原因只有一个,那就是你没有彻底理解这个算法的思想!! 以前写过最小生成树,但是,水了几道题后,过了一段时间,就会忘却,一点也写不出来了.也许原因只有一个,那就是我没有彻底理解这两种算法. 主题: 其实,求最小生成树有两个要点,一个是权值最小,还有一个就是这个图必须是树.而Prim和Kruskal的不同之处在于两者选择的变量不同,Prim选择的是始终保持权值最小,然后逐个加点构建一棵树.而Kruskal则是始终保证是一棵树(虽然构建过程中不一定是真正的树,但并查

树:最小生成树-两种算法

先来说说什么是树. 树实际上是图的一种,当一个有N个点的无向连通图,只有N-1条边时,就是一棵树,即树中不会有环出现:所以对于一个图,删除某些环中的某条边,使得该图成为一棵树,那么这棵树就称为生成树. 而最小生成树的意思就是,给定有n个顶点的带权图G(E,V),找到一棵生成树,求该生成树的边权和. Kruskal算法: 算法步骤: 1.构造一个有n个顶点的无边子图: 2.从原图选择边权最小的边加入该子图,直至子图成为一棵树: 3.边能加入子图的条件是,边的两个端点u,v还未连通,Kruskal算

求最大公约数(GCD)的两种算法

之前一直只知道欧几里得辗转相除法,今天学习了一下另外一种.在处理大数时更优秀的算法--Stein 特此记载 1.欧几里得(Euclid)算法 又称辗转相除法,依据定理gcd(a,b)=gcd(b,a%b) 实现过程演示: sample:gcd(15,10)=gcd(10,5)=gcd(5,0)=5 C语言实现: 1 int Euclid_GCD(int a, int b) 2 { 3 return b?Euclid_GCD(b, a%b):a; 4 } 2.Stein 算法 一般实际应用中的整数

hdu 1874 畅通工程续 两种算法AC Floyd+Bellman-Ford算法 又是一波水题~~

畅通工程续 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 31655    Accepted Submission(s): 11564 Problem Description 某省自从实行了很多年的畅通工程计划后,终于修建了很多路.不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行

hdu 3371 Connect the Cities Prim + Kruskal两种算法分别AC 水过~~~~

Connect the Cities Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11727    Accepted Submission(s): 3278 Problem Description In 2100, since the sea level rise, most of the cities disappear. Tho

hdu 1217 Arbitrage 两种算法AC代码,Floyd+Bellman-Ford 大水题一枚 注意是有向图~~

Arbitrage Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4998    Accepted Submission(s): 2286 Problem Description Arbitrage is the use of discrepancies in currency exchange rates to transform

hdu 1863 畅通工程 最小生成树模板入门题 prim+kruskal两种算法AC。

畅通工程 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 18866    Accepted Submission(s): 8012 Problem Description 省政府"畅通工程"的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可).经过调查评估,得到的统计表中列出