稀疏矩阵的转置算法 |
您所在的位置：网站首页 › 3个矩阵的转置 › 稀疏矩阵的转置算法 |
稀疏矩阵的转置算法
|
关于数组，大家并不陌生，几乎所有的程序设计语言都把数组类型设为了固有类型。 数组是n(n>1)个相同类型数据元素构成的有限序列，它是下标-值偶对的集合，即集合中的每一个元素都是由一个值和一组下标组成的。 数组一般分为一维、二维、三维数组，其中二维数组也称为矩阵，本文主要讲解对于矩阵中稀疏矩阵的相关操作算法。 稀疏矩阵在矩阵中，当数值为0的元素远远多于非0元素的个数，且非0元素的分布并没有规律时，称该矩阵为稀疏矩阵。 例如： 上图的稀疏矩阵的三元组表示为： 假设以顺序存储结构来存储三元组表，则可以得到稀疏矩阵的一种压缩方式——三元组顺序表。 三元组顺序表 三元组顺序表的相关定义 #include using namespace std; #define maxsize 1000 //最大存储容量 #define OK 1 #define FALSE 0 typedef int ElemType; typedef int status; typedef struct { int i, j; //行列号 ElemType e; //值 }Triple; //三元组(行号，列号，值） typedef struct { Triple data[maxsize + 1]; int mu, nu, tu; //稀疏矩阵的行数，列数，非零元个数 }TSMatrix; //稀疏矩阵故此时稀疏矩阵的图示为： 首先输入一个稀疏矩阵，然后将其压缩成三元组表。 void CreateMatrix(TSMatrix &M) { int A[100][100]; int a, b; //a，b用来存储矩阵的行号列号 int h, l; int m=0; //m为非零元个数计数器 cout a >> b; for (h = 1; h for (l = 1; l m++; M.data[m].i = h; M.data[m].j = l; M.data[m].e = A[h][l]; } } M.tu = m; M.mu = a; M.nu = b; } } 稀疏矩阵的输出 以三元组表的形式输出非零元素 void PrintTriple(TSMatrix M) { // 输出稀疏矩阵M的三元组表示 int i; cout for (b = 1; b A[a][b] = M.data[k].e; k++; } else { A[a][b] = 0; } } } cout //稀疏矩阵的转置 int p, q,col; ElemType e; //q代表转置后矩阵的元素计数器，p代表原矩阵中元素的计数器，e代表元素值，col代表行号顺序 T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { q = 1; for (col = 1; 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; } 快速转置由于上面算法的时间复杂度太高，为O(M.nu*M.mu)，故将算法改进，降低时间复杂度。 思路如下： 求原矩阵中每一行的三元组个数求原矩阵中的每一行中第一个三元组在转置后矩阵中的序号讲原矩阵中每个三元组根据序号依次转换到转置后矩阵的相应位置故在原矩阵中增加了 数组num来记录原矩阵中每列的非零元素个数(即转置后矩阵中每行的非零元个数）数组pos来记录转置后矩阵中每行第一个元素的位置 status TransposeMatrix_plus(TSMatrix M, TSMatrix& T) { //稀疏矩阵转置的改进版，快速转置 //在原矩阵中增加了num[j]来记录原矩阵M中每列的非零元素个数，即转置后T中每行的非零元个数 //增加了pos[j]来记录转置后矩阵T中每行第一个元素的位置 int i, j, k; int* num = (int*)malloc(M.nu * sizeof(int)); int* pos = (int*)malloc(M.nu * sizeof(int)); T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (M.tu) { //第一步：确定M中每一列的num值 for (j = 1; j num[M.data[k].j]++; //遍历整个M矩阵，统计M中每一列（T中的每一行）元素个数num } //第二步：确定T中各行元素的起始位置pos值 for (j = 2; j j = M.data[k].j; T.data[pos[j]].j = M.data[k].i; T.data[pos[j]].i = M.data[k].j; T.data[pos[j]].e = M.data[k].e; pos[j]++; } } return OK; }随意编写了个主函数来进行测试，转置用的是快速转置算法 void main() { TSMatrix A, B; CreateMatrix(A); PrintTriple(A); TransposeMatrix_plus(A, B); cout |
对于稀疏矩阵，我们通常采用三元组的形式来进行压缩，不考虑0元素的个数和位置，只记录非0元素的行列位置和数据值。 三元组：（行号，列号，值）
【本文地址】