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;
}

在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓的压缩存储是指：为多个值相同的元值分配一个存储空间；对零元不分配空间。


5.32稀疏矩阵
在m*n的矩阵中，有t个元素不为零。零α=t/m*n，称 α为矩阵的稀疏因子。通常认为α<=0.05时称为稀疏矩阵。


对于稀疏矩阵的非零元我们有下面这个表示：
如：(,(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))
如下图所示：






下面我们来看下三元组的结构体：
下面是书中代码（严蔚敏版的数据结构）
#define  MAXSIZE 12500	//非零元素个数的最大值为12500
typedef struct{
	int i, j;	//该非零元的行下标和列下标
	ElemType e;
}Triple;

typedef struct{
	Triple data[MAXSIZE + 1];	//非零元三元组表，data[0]未用
	int mu, nu, tu;	//矩阵的行数、列数和非零元个数
}TSMatrix;
分析下：


这里的思路和我们在链表上看到的有相似之处，结点变成了非零元素，线性表编程了非零元三元组的表。但多出了矩阵的行数，列数和非零元个数







学过线性代数的都知道，转置运算是一种最简单的矩阵运算。

对应一个m*n的矩阵M它的转置矩阵是T，如下图所示：


P·S:所谓的置换就是行和列进行交换，也就是关于主对角线对称（矩阵左上角到右下角的线称为主对角线）


而在程序里面，他将会是下面这张图这样：


这里的i对应行，j对应列，v表示值。


从分析a和b之间的差异可见只要做到：
1.将矩阵的行列值相互转换。
2.将每个三元组中的i和j交换。
3.重排三元组之间的次序便可实现矩阵的转置。


下面是书中给我们提供的伪代码：
Status TransposeSMatrix(TSMatrix M, TSMatrix &T) 
{ 
	// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T
	int p, q, col;
	T.mu = M.nu;  T.nu = M.mu;  T.tu = M.tu;
	if (T.tu) 
	{
		q = 1;
		for (col = 1; col <= M.nu; ++col)
		for (p = 1; p <= M.tu; ++p)
		if (M.data[p].j == col)
		{
			T.data[q].i = M.data[p].j; 
			T.data[q].j = M.data[p].i;
			T.data[q].e = M.data[p].e;  
			++q;
		}
	}
	return Ok;
} // TransposeSMatrix
下面来分析下：


col表示列，从M矩阵的第一列开始。比如col=1时，他先检索M的第一列，把非零元中第一列的换成T中的第一行，就这个思路。







下面是矩阵的快速转置方法：

原理是：如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元在b.data中(上面那图是b.data)恰当位置。那么在对a.data中的三元组一次做转置时，便可直接放到b.data中恰当的位置上去。
设两个向量：num和cpot
num[col]表示矩阵M中第col列中的非零元素个数。
cpot[col]指M中第col列的第一个非零元在b.data中的恰当位置。
有下面两个公式：
cpot[1]=1;
cpot[col]=copt[col-1]+num[col-1] 2<=col<=a.nu


图如下：


下面来分析下这个表：


cpot[1]=1.
cpot[2]=num[1]+cpot[1]=1+2=3
cpot[3]=num[2]+cpot[2]=2+3=5

cpot[4]=num[3]+cpot[3]=2+5=7

cpot[5]=num[4]+cpot[4]=1+7=8

cpot[6]=num[5]+cpot[5]=0+8=8

cpot[7]=num[6]+cpot[6]=1+8=9

这个表就是这么填的，但是在代码里面就不一样了。我这里先提一下，代码里面有覆盖和范围这种概念，这是什么意思，意思就是，大家看cpot[5]和cpot[6]都是8，那么在最后，他只会保留cpot[6],而cpot[7]他这里是9，但本身就只有8个元素，哪来第九个呢？所以这个cpot[9]在程序里面是没有用的。



下面是书中代码：

Status  FastTransposeSMatrix(TSMatrix M, TSMatrix &T) 
{ 
	// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T
	int col, t, p, q;
	int num[20], cpot[20];
	T.mu = M.nu;  T.nu = M.mu;  T.tu = M.tu;
	if (T.tu) {
		for (col = 1; col <= M.nu; ++col)	//对列数进行初始化
			num[col] = 0;
		for (t = 1; t <= M.tu; ++t) // 求 M 中每一列所含非零元的个数
			++num[M.data[t].j];
		cpot[1] = 1;
		// 求 M 中每一列的第一个非零元在 b.data 中的序号
		for (col = 2; col <= M.nu; ++col) 
			cpot[col] = cpot[col - 1] + num[col - 1];
		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;
			T.data[q].e = M.data[p].e;  
			++cpot[col];
		} // for
	} // if
	return OK;
} // FastTransposeSMatrix
分析如下：


这个程序的关键就是他只用了一个for循环，而上面那个程序用了两个for循环，这使得时间复杂度降低了。这个for(p=1;p<M.tu;++p).这个就是我刚刚在上表说的那个意思。这里有个++cpot[col]这是个关键
现在来解释下++cpot[col]:
我们可以看到上表中cpot[col]只有1,3,5,7,8而2,4,5没有，所以用了这个++cpot[col]后他就把每一列的第一个元素移到了第二个。








如果还有同学不懂，下面我给出全部的代码。
不懂的同学单步调试下。
#include <stdio.h>
#include <windows.h>
#define MAXSIZE 1250  

#define    OK      1  
#define    ERROR   0  
#define    TRUE    1  
#define    FLASE   0  

typedef    int     Status;
typedef    int     ElemType;

typedef struct{
	int   i, j;       //该非零元的行下标和列下标  
	ElemType e;       //非零元对应的值  
}Triple;

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

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)              //快速转置  
{                                                      //采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T  
	T.mu = M.nu;
	T.nu = M.mu;
	T.tu = M.tu;
	if (T.tu)
	{
		int col;
		int num[100], cpot[100];
		for (col = 1; col <= M.nu; ++col)
			num[col] = 0;                 //num数组的初始化  
		for (int t = 1; t <= M.tu; ++t)
			++num[M.data[t].j];         //求M中每一列含有的非零元个数  
		cpot[1] = 1;
		for (col = 2; col <= M.nu; ++col)
			cpot[col] = cpot[col - 1] + num[col - 1];         //求cpot向量  
		int q;
		for (int 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;
			T.data[q].e = M.data[p].e;
			++cpot[col];
		}//for  
	}//if  
	return OK;
}//FastTransposeSMatrix  

Status main()
{
	TSMatrix M;
	TSMatrix T;
	printf("请输入原矩阵：\n");
	printf("行数、列数： ");
	scanf_s("%d%d", &M.mu, &M.nu);
	printf("元素总数： ");
	scanf_s("%d", &M.tu);
	printf("输入各个对应压缩值：\n");
	for (int i = 1; i <= M.tu; ++i)
		scanf_s("%d%d%d", &M.data[i].i, &M.data[i].j, &M.data[i].e);

	FastTransposeSMatrix(M, T);

	printf("转置后行数、列数、元素总数非别为：\n%d     %d     %d\n\n", T.mu, T.nu, T.tu);
	printf("值为：\n");
	for (int t = 1; t <= T.tu; ++t)
		printf("%d     %d     %d\n", T.data[t].i, T.data[t].j, T.data[t].e);
	system("pause");
	return OK;
}


运行结果如下：


和下面这图是不是一模一样

稀疏矩阵转置以及输出
代码实现：

1.稀疏矩阵的输入

2.稀疏矩阵转三元组

3.转置

4.三元组转稀疏矩阵
#include<iostream.h>
#include<stdio.h>
#define MAXSIZE 10000
typedef int ElemType;
typedef int Status;
#define M1 4
#define N1 4
typedef struct{  //三元组
	int row;     //行
	int line;	 //列
	ElemType elem;   //元素大小
}triple;
typedef struct{  //矩阵
	triple data[MAXSIZE];
	int rownum;    //行数
	int linenum;    //列数
	int elemnum;    //元素总数
}Trix;
void createTrix(Trix &M,ElemType a[M1][N1]){   //创建稀疏矩阵
	M.linenum=N1;
	M.rownum=M1;
	M.elemnum=0;
	for(int i=0;i<M1;i++)
		for(int j=0;j<N1;j++)
			if(a[i][j]!=0)
			{
				M.data[M.elemnum].row=i;
				M.data[M.elemnum].line=j;
				M.data[M.elemnum].elem=a[i][j];
				M.elemnum++;
			}
		cout<<"已将稀疏矩阵转化为三元组"<<endl;
}

void coutTrix(Trix N){      //输出稀疏矩阵
	int k=0;
	if(N.elemnum!=0){
		for(int i=0;i<N.rownum;i++){			//行数
		   for(int j=0;j<N.linenum;j++){		//列数
			   if(N.data[k].line==j&&N.data[k].row==i){   //比较，如果行列相等就输出，没有就输出零
				   cout<<N.data[k].elem<<"  ";
				   k++;
			   }
			   else cout<<0<<"  ";
			}
		   cout<<endl;
		}
	}
	cout<<"稀疏矩阵转化完毕！"<<endl;
}
void coutTriple(Trix M){	//输出三元组
	int num=0;
	cout<<"三元组输出如下"<<endl;
	cout<<"num  row  line  value"<<endl;
	cout<<"---------------------"<<endl;

	for(int i=0;i<M.elemnum;i++){
		cout<<num<<"     "<<M.data[i].row<<"     "<<M.data[i].line<<"     "<<M.data[i].elem<<endl;
		num++;
		}
	cout<<"输出完毕"<<endl;
}
void transTriple(Trix &M,Trix &N){//转置三元组
	int k;
	N.rownum=M.linenum;				//行列互换
	N.linenum=M.rownum;
	N.elemnum=M.elemnum;			//元素个数一样
	if(M.elemnum!=0)
	{
		k=0;
		for(int i=0;i<M.linenum;i++)//N的行数
			for(int j=0;j<M.elemnum;j++)
				if(M.data[j].line==i)
				{
					N.data[k].line=M.data[j].row;
					N.data[k].row=M.data[j].line;
					N.data[k].elem=M.data[j].elem;
					k++;
				}
	}
	cout<<"三元组转置成功"<<endl;
}
void main(){
	Trix M,N;
	int i=0,j=0;
	int row,line;
	cout<<"请输入稀疏矩阵的行数和列数"<<endl;
	cin>>row>>line;
	int a[M1][N1]={0};
	cout<<"请输入稀疏矩阵的元素"<<endl;
	for(i=0;i<row;i++)
		for(j=0;j<line;j++)
			cin>>a[i][j];
	createTrix(M,a);
	coutTriple(M);      //三元组输出方式
	transTriple(M,N);
	coutTriple(N);      //三元组输出方式
	coutTrix(N);        //稀疏矩阵输出方式
}

问题描述

问题描述：稀疏矩阵转置

设计思路

设计思路：稀疏矩阵中存在大量非零元素，直接转置执行时间较高。因而采用三元组表示。按照压缩的概念，只存储稀疏矩阵中的非零元素，除了存储非零元素的值之外，还必须同时记下它所在的行列位置。三元组表示法是用一个具有三个数据域的一维数组表示稀疏矩阵，每一行有三个字段，分别该元素的行下表、列下表和值。设A，B分别为某稀疏矩阵转置前后的三元组表，i为行下标，j为列下标，v味元素值。变量m为稀疏矩阵行数，n为稀疏矩阵列数，tu为非零元素个数。本算法要求把A中行下标、列下标交换后送到B中，并且使B中行下表仍按递增顺序存放。

数据结构：

i：行下标

j：列下标

v：元素值

tu：非零元素个数

A：转置前矩阵

B：转置后矩阵

Ai：转置前三元组

Bi：转置后三元组

t[0]：工作数组

算法描述：

TRANSMAT ( A , B)

If( tu!=0) then
	
{ q<-1 //q为转置以后B的行号//
	
  for col=1 to n
	
    For p=1 to tu //p为转置前A的行号//
	
      If A[p].j=col then
	
        {B[q].i<-a[p].j; B[q].j<A[p].i;
	
          B[q].v<-A[p].v; q<-q+1}
	
      End(p)
	
   End(col)}
	
return
测试用例及结果说明

测试用例：稀疏矩阵元素为

A[0][0]=3;

A[0][4]=7;

A[1][2]=-1;

A[2][0]=-1;

A[2][1]=-2;

A[4][3]=2;

测试结果：

转置前矩阵A：

3       0       0       0       7

0       0       -1      0       0

-1      -2      0       0       0

0       0       0       0       0

0       0       0       2       0

工作三元组Ai：

1       1       3

1       5       7

2       3       -1

3       1       -1

3       2       -2

5       4       2

工作三元组Bi：

1       1       3

1       3       -1

2       3       -2

3       2       -1

4       5       2

5       1       7

转置后矩阵：

3       0       -1      0       0

0       0       -2      0       0

0       -1      0       0       0

0       0       0       0       2

7       0       0       0       0

设计及测试过程

第一步：提出问题；

第二步：问题转换；

第三步：算法构思；

第四步：伪码描述；

第五步：代码编写；

第六步：代码测试；

第七步：代码修正；

参考书籍：

《计算机软件技术基础》 清华大学出版社 第三版

#include<iostream>
using namespace std;
#define N 5
struct node
{
	int i;
	int j;
	int v;
}Ai[N*N],Bi[N*N],t[1];
int main()
{
	int A[N][N],B[N][N],a,b,tu=0,i,j=0;
	node *q;
	for(a=0;a<N;a++)
		for(b=0;b<N;b++)
		{
			A[a][b]=0;
			B[a][b]=0;
		}
	A[0][0]=3;
	A[0][4]=7;
	A[1][2]=-1;
	A[2][0]=-1;
	A[2][1]=-2;
	A[4][3]=2;
	cout<<"转置前矩阵为"<<endl;
	for(a=0;a<N;a++)
	{
		for(b=0;b<N;b++)
			cout<<A[a][b]<<'\t';
		cout<<endl;
	}
	for(a=0;a<N;a++)
		for(b=0;b<N;b++)
			if(A[a][b]!=0)
			{
				Ai[tu].i=a+1;
				Ai[tu].j=b+1;
				Ai[tu].v=A[a][b];
				tu++;
			}
	cout<<"转置前矩阵等效三元组为"<<endl;
	for(i=0;i<tu;i++)
		cout<<Ai[i].i<<'\t'<<Ai[i].j<<'\t'<<Ai[i].v<<endl;
	for(i=0;i<tu-1;i++)
	{
		int min=i;
		for(j=i+1;j<tu;j++)
			if(Ai[j].j<Ai[min].j)
				min=j;
		t[0].i=Ai[i].i;
		t[0].j=Ai[i].j;
		t[0].v=Ai[i].v;
		Ai[i].i=Ai[min].i;
		Ai[i].j=Ai[min].j;
		Ai[i].v=Ai[min].v;
		Ai[min].i=t[0].i;
		Ai[min].j=t[0].j;
		Ai[min].v=t[0].v;
	}
	for(i=0;i<tu;i++)
	{
		Bi[i].i=Ai[i].j;
		Bi[i].j=Ai[i].i;
		Bi[i].v=Ai[i].v;
	}
	cout<<"转置后矩阵等效三元组为"<<endl;
	for(i=0;i<tu;i++)
		cout<<Bi[i].i<<'\t'<<Bi[i].j<<'\t'<<Bi[i].v<<endl;
	for(i=0;i<tu;i++)
	{
		a=Bi[i].i-1;
		b=Bi[i].j-1;
		B[a][b]=Bi[i].v;
	}
	cout<<"转置后矩阵为"<<endl;
	for(a=0;a<N;a++)
	{
		for(b=0;b<N;b++)
			cout<<B[a][b]<<'\t';
		cout<<endl;
	}
	system("pause");
	return 0;
}