稀疏矩阵转置 c语言,【数据结构之旅】稀疏矩阵的快速转置

水深无声 2022-10-14 15:58 191阅读 0赞

说明：

稀疏矩阵的快速转置算法的核心在于，用一个数组num记录原来矩阵中的每列非零元个数，用另一个数组cpos来记录原矩阵每列第一个非零元在新矩阵中的位置，以此来达到快速转置的目的。

用这样的方法，主要是希望，矩阵转置后，存储顺序依然是按照行来存储的。

1.实现及代码注释

根据上面的核心提示，可以有如下的代码，下面的代码中的注释已经非常详细，因此这里就不把每一部分实现的功能独立开来了：\#include

\#include

\#define OVERFLOW -1

\#define OK 1

\#define ERROR 0

\#define TRUE 2

\#define FALSE -2

typedef int ElemType;

typedef int Status;

typedef struct\{ //非零元三元组类型结构体

int i, j;//非零元的行和列

ElemType e;//非零元的值

\} Triple;//非零元三元组类型结构体定义关键字

typedef struct\{//矩阵类型结构体

Triple \*data;//data域，指向非零元三元组的结构体指针

int mu, nu, tu;//矩阵的行数、列数和非零元个数

\} TSMatrix;//矩阵类型结构体定义关键字

/\*

01400-5

0-7000

3600280

mu = 3; nu = 5; tu = 5

\*/

Status CreateSMatrix(TSMatrix &M)\{//创建一个稀疏矩阵

M.tu = 5;

M.data = (Triple\*)malloc(sizeof(Triple) \* (M.tu + 1)); //data域存储元素的大小比稀疏矩阵的非零元个数大1，是因为data\[0\]不使用

if(NULL == M.data)

return OVERFLOW;

M.data\[1\].i = 1;

M.data\[1\].j = 2;

M.data\[1\].e = 14;

M.data\[2\].i = 1;

M.data\[2\].j = 5;

M.data\[2\].e = -5;

M.data\[3\].i = 2;

M.data\[3\].j = 2;

M.data\[3\].e = -7;

M.data\[4\].i = 3;

M.data\[4\].j = 1;

M.data\[4\].e = 36;

M.data\[5\].i = 3;

M.data\[5\].j = 4;

M.data\[5\].e = 28;

M.mu = 3;

M.nu = 5;

return OK;

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)\{ //采用顺序表存储表示，求稀疏矩阵M的转置矩阵T

int j, p, q, t;

/\*j记录遍历时的当前列，cops\[j\]，则表示当前列第一个非零元的位置或者该列非零元位置的其它位置(cops\[j\]++)，正式转置时用；

p记录遍历时的非零元个数，正式转置时用；

q记录cops\[j\]，简化代码的表示，正式转置时用 ；

t用在转置准备时。

\*/

int \*num;//保存每一列的非零元个数

int \*cpos;//保存转置后每列第一个非零元在T中所处的序号

//cops\[j\]++则是该列的下一个非零元，如果存在的话

T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;//初始化矩阵T

T.data = (Triple\*)malloc(sizeof(Triple)\*(T.nu + 1));

num = (int\*)malloc((M.nu + 1)\*sizeof(int));//num和cpos开辟空间比非零元个数大1，是因为不使用0号位置

cpos = (int\*)malloc((M.nu + 1)\*sizeof(int));

if(num == NULL || cpos == NULL)

return OVERFLOW;

if(T.tu != 0)\{

for(j = 1; j <= M.nu; j++)//初始化num向量

num\[j\] = 0;

for(t = 1;t <= M.tu; t++)//求M中每一列所含非零元的个数

num\[M.data\[t\].j\]++;//这里要用到num\[1\]~num\[5\]，所以上面num要全部初始化为0

cpos\[1\] = 1;//这里是一定的

for(j = 2;j <= M.nu; j++)//求每列的第一个非零元在T.data中的序号

cpos\[j\] = cpos\[j-1\] + num\[j-1\];//画表分析得出该公式并不难

for(p = 1; p <= M.tu; p++)\{//上面是准备工作，下面开始正式转置

j = M.data\[p\].j;//j的作用是记录当前遍历的列，以让cops使用

q = cpos\[j\];//是为了简化代码，因为下面都要用到cpos\[j\]

T.data\[q\].i = M.data\[p\].j;//交换行

T.data\[q\].j = M.data\[p\].i;//交换列

T.data\[q\].e = M.data\[p\].e;//赋值 ，无论如何交换，储存顺序是已经定下来的了

cpos\[j\]++;//cops\[j\]++则是该列的下一个非零元，如果存在的话，不存在的话也没有影响

\}//因为在这个for循环中，如果列变了，即j变化了，cpos\[j\]也不是原来的值了

free(num);

free(cpos);

return OK;

int main(void)\{

int i,j;

TSMatrix M;

TSMatrix T;

CreateSMatrix(M);

FastTransposeSMatrix(M, T);

printf("\\n");

return 0;

可以用C free等编译器进行编译运行，但由于时间关系，上面的代码中并没有给出转置后的矩阵打印的代码，可以自己加上去，当然也可以通过调试的方法监视新矩阵T中的data域的数值变化。

2.测试

测试就是按照上面的提示去做就可以了，时间关系，这里就先不做测试，改天有时间再补上吧。

稀疏矩阵转置 c语言,【数据结构之旅】稀疏矩阵的快速转置

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 NOJ数据结构实验003——稀疏矩阵转置

相关稀疏矩阵转置 c语言,【数据结构之旅】稀疏矩阵的快速转置

相关 C语言数据结构稀疏矩阵的转置

相关稀疏矩阵如何转置?c++版

相关 C语言：稀疏矩阵的转置

相关稀疏矩阵转置

相关 C语言数据结构——稀疏矩阵的快速转置

相关 C语言数据结构——稀疏矩阵的转置

相关【稀疏矩阵转置】线性时间复杂度实现稀疏矩阵转置

相关稀疏矩阵快速转置算法分析