（参考数据结构教材，严蔚敏，吴伟民版 p99，多谢阅读，望对您有帮助）
无论是几维的数组，在计算机中都是以一维数组的方式进行存储的。
矩阵：相当于二维数组，它的存储，依然是用一维数组的方式进行存储。
nxn的矩阵，在计算机空间上，需要nxn个空间。
稀疏矩阵的压缩：将矩阵中的值为零或者为常数C的某c个数，不做存储（或者共用同样的空间，本题转置对0不做存储），压缩后原本nxn的矩阵，存储只需要nxn-c的空间
下面以这样的M矩阵进行转置
1 2 3
4 0 0
0 5 1
转置后得N矩阵：
1 4 0
2 0 5
3 0 1
M矩阵的计算机三元组存储方式（此图为图1）

转置后T矩阵的计算机三元组存储方式（此图为图2）

转置过程的实现，实际上是从图一转化为图二的过程
因为图1是按照行储存（第一行储存完了，才储存第二行），转置后的T矩阵，同样是按照行进行存储。
故T矩阵再遍历矩阵M时，M的列就是T的行，把M的每列的数据，逐列，一一存到data中，完成转置运算

先给出转置代码实现：

#include "stdio.h"
#include "stdlib.h"

#define Max_size 1000

typedef struct 
{
	int i;//矩阵中数据的行号
	int j;//矩阵中数据的列号
	int e;//i行j列，数据的值
}Triple;//三元组为一个节点

typedef struct
{
	Triple data[Max_size + 1];//data[0]未用
	int mu, nu, tu;//矩阵的行数，列数，非零元个数
}Matrix;

void TransposeSMatrix(Matrix M,Matrix &T)//将矩阵M转置为T
{
	T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
	if (T.tu)//非零元不为0
	{
		int q = 1;//用于逐项记录转置后矩阵T的值
		int col, p;//矩阵M的col列号，p:指向当前值在M矩阵硬件的储存位置
		for (col = 1; col < M.nu; col++)
		{
			for (p = 1; p < M.tu; p++)
			{
				if (M.data[p].j == col)//逐列进行遍历，并插入到T.data中
				{
					T.data[q].i = M.data[p].j;
					T.data[q].j = M.data[p].i;//转置后i，j互换
					T.data[q].e = M.data[p].e;//T的值获取到
					q++;//T指针的数据后移
				}
			}
		}
	}
}

int main()
{
	Matrix M,T;
	M.mu = 3;
	M.nu = 3;
	M.tu = 6;
	M.data[1].i = 1;
	M.data[1].j = 1;
	M.data[1].e = 1;

	M.data[2].i = 1;
	M.data[2].j = 2;
	M.data[2].e = 2;

	M.data[3].i = 1;
	M.data[3].j = 3;
	M.data[3].e = 3;

	M.data[4].i = 2;
	M.data[4].j = 1;
	M.data[4].e = 4;

	M.data[5].i = 3;
	M.data[5].j = 2;
	M.data[5].e = 5;

	M.data[6].i = 3;
	M.data[6].j = 3;
	M.data[6].e = 1;

	TransposeSMatrix(M, T);
	printf("(%d,%d):%d", T.data[4].i, T.data[4].j, T.data[4].e);//求转置后T矩阵2行3列的值
	return 0;
}

运行结果
转置后T矩阵2行3列的值为5，如运行结果所示

最近有数据结构实验课了，还得学一学数据结构喽，以后就把学习经过贴上来了。

稀疏矩阵

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

稀疏数组的处理方法

1）记录数组一共有几行几列，有多少个不同的值(假设有sum个，则稀疏矩阵有sum+1行，3列)
2）把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

百度盗图（手动滑稽）

稀疏矩阵转置

题目

（不得不说这个题输入数据的确坑。。）
有两种方法转置
话不多说，上代码：

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 1000
typedef struct{
int row;//第几行
int col;//第几列
int e;//存储的值
}Triple;

typedef struct
{
    Triple data[MAXSIZE];
    int m,n,len;//稀疏矩阵的行，列，非零元素的个数
}TSMatrix;


void createTSMatrix(TSMatrix *A)//创建矩阵
{    int i=1;     //data【0】未用
    scanf("%d %d",&A->m,&A->n);
    int flag = 1;
    int a,b,c;
    char c1,c2;
    while(flag)
    {
        scanf("%d",&a);
        c1 = getchar();
         scanf("%d",&b);
         c2 = getchar();
          scanf("%d",&c);
          if(c1=='?'&&c2=='?')
            break;
          A->data[i].row=a;
          A->data[i].col=b;
          A->data[i].e=c;
          i++;

    }
    i--;
    A->len=i;
}

void TransMatrix(TSMatrix A,TSMatrix *B)//序列递增转置法
{
    int i,j,k;
    B->n=A.m;
    B->m=A.n;
    B->len=A.len;
    if(B->len)
    {
        j=1;//辅助计数器，记录转置后的三元组元素下标值
        for(k=1;k<=A.n;k++)//扫描矩阵A的列次或B的行次

            for(i=1;i<=A.len;i++)  //扫描A找列为k的元素
        {
            if(A.data[i].col==k)
            {
                B->data[j].row=A.data[i].col;
                B->data[j].col=A.data[i].row;
                B->data[j].e=A.data[i].e;
                j++;
            }
        }
    }
}

void FastTransMatrix(TSMatrix A,TSMatrix *B)//快速转置法
{
    int col,t,p,q;
    int num[MAXSIZE],position[MAXSIZE];
    B->n=A.m;
    B->m=A.n;
    B->len=A.len;
    if(B->len)
    {
        for(col=1;col<=A.n;col++)
            num[col]=0;
        for(t=1;t<=A.len;t++)
            num[A.data[t].col]++;
        position[1]=1;
        for(col=2;col<=A.n;col++)
        {
            position[col]=position[col-1]+num[col-1];
        }
        for(p=1;p<=A.len;p++)
        {
            col=A.data[p].col;
            q=position[col];
            B->data[q].row=A.data[p].col;
            B->data[q].col=A.data[p].row;
            B->data[q].e=A.data[p].e;
            position[col]++;
        }
    }
}

void printMatrix(TSMatrix *B)//输出矩阵
{
    for(int i=1;i<=B->len;i++)
    {
        printf("%d %d %d\n",B->data[i].row,B->data[i].col,B->data[i].e);
    }
}

int main()
{
    TSMatrix A,B;//A为初始矩阵，B为转置后的矩阵
    createTSMatrix(&A);
    FastTransMatrix(A,&B);
    printMatrix(&B);
    return 0;
}

Think:
1知识点：线性时间复杂度实现稀疏矩阵转置
2方法：
（１）：通过三元组记录初始输入信息
（２）：记录每一列的元素个数
（３）：求得记录每一列的第一个元素应放置的转置三元组的位置
（４）：通过（３）所得到的记录数组和初始输入时记录的三元组遍历转置稀疏矩阵即可

3反思：
（１）：求解记录的是每一列的第一个元素应放置的转置三元组的位置，故遍历范围为[1, nu]而不是[1, tu]

例题：
SDUT——数据结构实验之数组三：快速转置

Problem Description
转置运算是一种最简单的矩阵运算，对于一个m*n的矩阵M( 1 = < m < = 10000,1 = < n < = 10000 )，它的转置矩阵T是一个n*m的矩阵，且T( i , j )=M( j , i )。显然，一个稀疏矩阵的转置仍然是稀疏矩阵。你的任务是对给定一个m*n的稀疏矩阵( m , n < = 10000 )，求该矩阵的转置矩阵并输出。矩阵M和转置后的矩阵T如下图示例所示。

稀疏矩阵M

稀疏矩阵T

Input
连续输入多组数据，每组数据的第一行是三个整数mu, nu, tu(tu <= 50)，分别表示稀疏矩阵的行数、列数和矩阵中非零元素的个数，随后tu行输入稀疏矩阵的非零元素所在的行、列值和非零元素的值，同一行数据之间用空格间隔。(矩阵以行序为主序)

Output
输出转置后的稀疏矩阵的三元组顺序表表示。

Example Input
3 5 5
1 2 14
1 5 -5
2 2 -7
3 1 36
3 4 28

Example Output
1 3 36
2 1 14
2 2 -7
4 3 28
5 1 -5

Hint

Author
xam

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct Node{
    int x, y, num;
}node1[104], node2[104];

int book[14014], cpot[14014];

int main(){
    int mu, nu, tu;
    while(~scanf("%d %d %d", &mu, &nu, &tu)){
        memset(book, 0, sizeof(book));
        for(int i = 1; i <= tu; i++){
            scanf("%d %d %d", &node1[i].x, &node1[i].y, &node1[i].num);
            book[node1[i].y]++;
        }
        cpot[1] = 1;
        for(int i = 2; i <= nu; i++){
            cpot[i] = cpot[i-1] + book[i-1];
        }
        for(int i = 1; i <= tu; i++){
            int id = cpot[node1[i].y];
            node2[id].x = node1[i].y;
            node2[id].y = node1[i].x;
            node2[id].num = node1[i].num;
            cpot[node1[i].y]++;
        }
        for(int i = 1; i <= tu; i++){
            printf("%d %d %d\n", node2[i].x, node2[i].y, node2[i].num);
        }
    }
    return 0;
}