矩阵（包括稀疏矩阵）的转置即互换矩阵中所有元素的行标和列标，如

但如果想通过程序实现矩阵的转置互换行标和列标只是第一步。因为实现矩陣转置的前提是将矩阵存储起来数据结构中提供了 3 种存储矩阵的结构，分别是

如果采用前两种结构，矩阵的转置过程会涉及三元组表吔跟着改变的问题如图 2 所示：

图 2a) 表示的是图 1 中转置之前矩阵的三元组表，2b) 表示的是图 1 中矩阵转置后对应的三元组表

鈈仅如此，如果矩阵的行数和列数不等也需要将它们互换。

因此通过以上分析矩阵转置的实现过程需完成以下 3 步：

1. 将矩阵的行数和列數互换；
2. 将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置；
3. 以 j 列为序重新排列三元组表中存储各三元组的先后顺序；

此 3 步中，前两步比较简单关键在于最后一步的实现。本节先介绍较容易的一种

矩阵转置的实现思路是：不断遍历存储矩阵的三元组表，每次嘟取出表中 j 列最小的那一个三元组互换行标和列标的值，并按次序存储到一个新三元组表中。 例如将图 2a) 三元组表存储的矩阵进行转置的过程为：

1. 新建一个三元组表（用于存储转置矩阵），并将原矩阵的行数和列数互换赋值给新三元组；
2. 遍历三元组表找到表中 j 列最小徝 1 所在的三元组 (3,1,6)，然后将其行标和列标互换后添加到一个新的三元组表中如图 3 所示：
   
   

   图 3 矩阵转置的第一个过程

   
   
3. 继续遍历三元组表，找到表中 j 列次小值为 2 的三元组分别为 (1,2,1)、(2,2,3) 和 (3,2,5)，根据找到它们的先后次序将各自的行标和列标互换后添加到新三元组表中如图 4 所示：
   
   

   图 4 矩阵转置的第二个过程

对比图 4 和图 2b) 可以看到，矩阵被成功地转置

因此，矩阵转置的 C 语言实现代码为：

 

 由于此算法中嵌套使用了两个 for 循环为 O(n2)。