代码： 全选
// Array Structure | Transpose Sparse Matrix
// Last Modified: 2008-06-12
// Last Modified: 2008-06-14
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
typedef struct
{
int row;
int col;
int value;
} tt_node;
typedef struct
{
tt_node data[MAX_SIZE];
int cols;
int rows;
int nzs; // none zero
} tri_tuple_table;
void print_table(tri_tuple_table *table)
{
int i;
printf("\n row ");
printf("\n column ");
printf("\n value ");
for (i = 0; i < table->nzs; i++)
printf("\n %d. %d %d %d ", i + 1, table->data[i].row, table->data[i].col, table->data[i].value);
printf("\n");
}
void trans_table(tri_tuple_table *ta, tri_tuple_table *tb)
{
/*
*
* 按行序转置，按列索引存放
* 1. 求 矩阵 A 每一列非零元素个数
* 2. 确定 矩阵 A 每一行第一个非零元素在 表 B 中起始序号
* 3. 设置相应行列号，将 表 A 中元素依次复制到 表 B
*
*/
int *ma_nzs; // 矩阵 A 每列非零元素个数
int *col_order; // 列索引，即矩阵 A 中每列第一个非零元素在表 B 中起始序号
int i, j, k;
tb->rows = ta->cols;
tb->cols = ta->rows;
tb->nzs = ta->nzs;
if (ta->nzs <= 0)
{
printf("\n\n there's not none zero elements ");
return;
}
ma_nzs = malloc(sizeof(int)*(ta->cols));
col_order = malloc(sizeof(int)*(ta->cols));
/*
* 1. 求 矩阵 A 每一列非零元素个数
*/
// 初始化 每列非零元素个数
for (i = 0; i < ta->cols; i++)
ma_nzs[i] = 0;
// 累计 非零元素个数
for (i = 0; i < ta->nzs; i++) // ta->nzs = 4
{
j = ta->data[i].col;
ma_nzs[j]++;
/*
* A -> B
*
* 024 -> 06
* 608 20
* 48
*
* 012 -> 016
* 024 102
* 106 204
* 128 218
*
* ma_nzs[0] = 1
* ma_nzs[1] = 1
* ma_nzs[2] = 2
*
*/
}
/*
* 2. 确定 矩阵 A 每一行第一个非零元素在 表 B 中起始序号
*/
// 初始化 列索引
for (i = 0; i < ta->nzs; i++)
col_order[i] = 0;
// 求 矩阵 A 每列第个非零元素在表 B 中的位置
// 行序范围 1 ~ ta->nzs（非零元素个数）
for (i = 1; i < ta->nzs; i++)
{
col_order[i] = col_order[i - 1] + ma_nzs[i - 1];
/*
* A -> B
*
* 024 -> 06
* 608 20
* 48
*
* 012 -> 016
* 024 102
* 106 204
* 128 218
*
* col_order[1] = 1
* col_order[2] = 2
* col_order[3] = 4
*
*/
}
printf("\n\n");
for (i = 0; i < ta->cols; i++)
printf("\n ma_nzs[%d] = %d ", i, ma_nzs[i]);
printf("\n");
for (i = 1; i < ta->nzs; i++)
printf("\n col_order[%d] = %d ", i, col_order[i]);
printf("\n");
/*
* 3. 设置相应行列号，将 表 A 中元素依次复制到 表 B
*/
// 将 表 A 中各个元素依次复制到 表 B 中的相应位置
for (i = 0; i < ta->nzs; i++)
{
/*
* A -> B
*
* 024 -> 06
* 608 20
* 48
*
* 012 -> 016
* 024 102
* 106 204
* 128 218
*
*/
j = ta->data[i].col;
k = col_order[j]; // 矩阵 A 中该列在表 B 中的起始位置
tb->data[k].col = ta->data[i].row;
tb->data[k].row = ta->data[i].col;
tb->data[k].value = ta->data[i].value;
col_order[j]++; // 矩阵 A 中该列下一个元素在表 B 中的位置
printf("\n %d. %d %d %d ", i + 1, tb->data[i].row, tb->data[i].col, tb->data[i].value);
printf("\n | col_order[%d]++ = %d | ", j, col_order[j]);
printf("\n");
}
// free(col_order);
}
void table_to_matrix(tri_tuple_table *ta)
{
int row, col;
int line;
int matrix[ta->rows][ta->cols];
int matrixb[ta->cols][ta->rows];
for (row = 0; row < ta->rows; row++)
for (col = 0; col < ta->cols; col++)
matrix[row][col] = 0;
for (line = 0; line < ta->nzs; line++)
matrix[ta->data[line].row][ta->data[line].col] = ta->data[line].value;
printf("\n");
printf("\n Matrix A ");
printf("\n");
for (row = 0; row < ta->rows; row++)
{
for (col = 0; col < ta->cols; col++)
printf(" %d ", matrix[row][col]);
printf("\n");
}
for (row = 0; row < ta->rows; row++)
for (col = 0; col < ta->cols; col++)
matrixb[col][row] = matrix[row][col];
printf("\n Matrix B ");
printf("\n");
for (row = 0; row < ta->cols; row++)
{
for (col = 0; col < ta->rows; col++)
printf(" %d ", matrixb[row][col]);
printf("\n");
}
}
int main()
{
void trans(tri_tuple_table *ta, tri_tuple_table *tb);
void print_table(tri_tuple_table *ta);
void table_to_matrix(tri_tuple_table *ta);
tri_tuple_table *ta; // table A
tri_tuple_table *tb; // table B
int i;
ta = malloc(sizeof(tri_tuple_table));
tb = malloc(sizeof(tri_tuple_table));
printf("\n\n Array Structure | Transpose Sparse Matrix \n");
/*
* matrix
*
* A B
*
* 0 2 4 0 6
* 6 0 8 2 0
* 4 8
*
*
* tri tuple table
*
* A B
*
* 0 1 2 0 1 6
* 0 2 4 1 0 2
* 1 0 6 2 0 4
* 1 2 8 2 1 8
*
*/
ta->data[0].row = 0;
ta->data[0].col = 1;
ta->data[0].value = 2;
ta->data[1].row = 0;
ta->data[1].col = 2;
ta->data[1].value = 4;
ta->data[2].row = 1;
ta->data[2].col = 0;
ta->data[2].value = 6;
ta->data[3].row = 1;
ta->data[3].col = 2;
ta->data[3].value = 8;
ta->rows = 0;
ta->cols = 0;
ta->nzs = 0; // none zero
i = 0;
while (ta->data[i].value)
{
if (ta->data[i].row > ta->rows - 1)
ta->rows = ta->data[i].row + 1;
if (ta->data[i].col > ta->cols - 1)
ta->cols = ta->data[i].col + 1;
ta->nzs++;
i++;
}
printf("\n");
printf("\n Table A Stat ");
printf("\n rows : ta->rows = %d ", ta->rows);
printf("\n cols : ta->cols = %d ", ta->cols);
printf("\n ta->nzs = %d ", ta->nzs);
table_to_matrix(ta);
printf("\n Table A ");
print_table(ta);
trans_table(ta, tb);
printf("\n Table B ");
print_table(tb);
return 0;
}