|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#
include
<stdio.h>
#
include
<stdlib.h>
#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;
//矩阵类型结构体定义关键字
/*
0 14 0 0 -5
0 -7 0 0 0
36 0 0 28 0
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
;
}
|
【数据结构之旅】稀疏矩阵的快速转置
2016-05-10
2543
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《
阿里云开发者社区用户服务协议》和
《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写
侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：
目录
相关文章
|
5月前
|
算法
|
6月前
|
存储
机器学习/深度学习
算法
|
6月前
|
存储
算法
NoSQL
|
存储
Java
Python
|
6月前
|
存储
人工智能
算法
|
6月前
|
存储
机器学习/深度学习
人工智能
|
存储
算法
Java
|
存储
机器学习/深度学习
人工智能
|
存储
人工智能
|
存储
算法
一篇文章让你彻底理解数组及其扩展的数据结构，快速转置算法等，千字超详细总结！
数组
本章主要介绍数组基本概念及其扩展，二维数组的特殊矩阵：对称矩阵、三角矩阵、稀疏矩阵、十字链表等存储解耦；然后介绍并实现了稀疏矩阵的快速转置算法。
可以转载，但请声明源链接：文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
125
0
0