数组存储结构 |
您所在的位置：网站首页 › 数组转置和矩阵转置一样吗 › 数组存储结构 |
数组存储结构
|
一、普通转置算法
矩阵（包括稀疏矩阵）的转置，就是将矩阵中的所有元素的行标和列标进行互换。
因为实现矩阵转置的前提是将矩阵存储起来，数据结构中提供了 3 种存储矩阵的结构，分别是三元组顺序表、行逻辑链接的顺序表和十字链表。如果采用前两种结构，矩阵的转置过程会涉及三元组表也跟着改变：
不仅如此，如果矩阵的行数和列数不等，也需要将它们互换。 因此通过以上分析，矩阵转置的实现过程需完成以下 3 步： 将矩阵的行数和列数互换；将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置；以 j 列为序，重新排列三元组表中存储各三元组的先后顺序；前两步比较简单，关键在于最后一步的实现。下面先介绍较容易的一种。 矩阵转置的实现思路是：不断遍历存储矩阵的三元组表，每次都取出表中 j 列最小的那一个三元组，互换行标和列标的值，并按次序存储到一个新三元组表中。 例如，将图 2a) 三元组表存储的矩阵进行转置的过程为： 新建一个三元组表（用于存储转置矩阵），并将原矩阵的行数和列数互换赋值给新三元组； 遍历三元组表，找到表中 j 列最小值 1 所在的三元组 (3,1,6)，然后将其行标和列标互换后添加到一个新的三元组表中，如图 3 所示：
图 3 矩阵转置的第一个过程 继续遍历三元组表，找到表中 j 列次小值为 2 的三元组，分别为 (1,2,1)、(2,2,3) 和 (3,2,5)，根据找到它们的先后次序将各自的行标和列标互换后添加到新三元组表中，如图 4 所示：
图 4 矩阵转置的第二个过程 对比图 4 和图 2b) 可以看到，矩阵被成功地转置。 矩阵转置的 C 语言实现代码： #include #define number 10 //三元组的结构体 typedef struct{ int i,j;//行标列标 int data;//数据 }triple; //整个矩阵的结构体 typedef struct{ triple data[10]; int n,m,num;//行数，列数，非零元素个数 }TSMatrix; TSMatrix transposeMatrix(TSMatrix M,TSMatrix T){ T.m=M.n;//行变列 T.n=M.m;//列变行 T.num=M.num;//非零元素个数 if(T.num){ int q=0; for(int col=1;col |
【本文地址】
今日新闻 |
推荐新闻 |