教材：严版数据结构

页码：P99

IDE：VS2015

代码如下：

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
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
 
#define MU 5
#define NU 6
#define Status int
#define ElemType int
 
#define ERROR 0
#define OK 1
#define MAXSIZE 12500
typedef struct {
	int i, j;//该非零元的行下标和列下标
	ElemType e;
}Triple;
 
typedef struct {
	Triple data[MAXSIZE + 1];
	int mu, nu, tu;//矩阵的行数、列数、非零元个数
}TSMatrix;
 
Status CreateMatrix(TSMatrix &M) {
	int e, i, j, k = 1;
	M.mu = MU;
	M.nu = NU;
	srand((unsigned)time(NULL));
	M.tu = rand() % 15;
	
	for(i=1;i<M.mu;i++)
		for (j = 1; j < M.nu; j++)
		{
			e = rand() % 30;
			if (e != 0) {
				M.data[k].i = i;
				M.data[k].j = j;
				M.data[k].e = e;
				k++;
				if (k == M.tu)
					break;
			}
		}
	return OK;
}
 
void print(TSMatrix M)
{
	int k;
	printf("mu=%-2d, nu=%-2d, tu=%-2d", M.mu, M.nu, M.tu);
	printf("\n");
	for (k = 1; k <= M.tu; k++)
	{
		printf("i=%-2d, j=%-2d, e=%-2d", M.data[k].i, M.data[k].j, M.data[k].e);
		printf("\n");
	}
}
 
Status TransposeSMatrix(TSMatrix M, TSMatrix &T)
{
	T.mu = M.nu;
	T.nu = M.mu;
	T.tu = M.tu;
	if (T.tu)
	{
		int q = 1;
		for(int col=1;col<=M.mu;++col)
			for (int p = 1; p <= M.tu; ++p)
			{
				if (M.data[p].j == 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;
}
 
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)
{
	T.mu = M.nu;
	T.nu = M.mu;
	T.tu = M.tu;
	int col, t, q, p;
	int num[NU];
	int cpot[NU];
	if (T.tu)
	{
		for (col = 1; col <= M.nu; ++col)
			num[col] = 0;
		for (t = 1; t <= M.tu; ++t)
			++num[M.data[t].j];
		cpot[1] = 1;
 
		for (col = 2; col <= M.nu; ++col)
			cpot[col] = cpot[col - 1] + num[col - 1];
		for (p = 1; p <= M.tu; ++p)
		{
			col = M.data[p].j;
			q = cpot[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;
			++cpot[col];
		}//for
	}//if
	return OK;
}
 
 
void main()
{
	TSMatrix M, T,R;
	CreateMatrix(M);
	TransposeSMatrix(M, T);
	printf("输出稀疏矩阵M：\n");
	print(M);
	printf("输出转置矩阵T：\n");
	print(T);
	cout << endl;
	FastTransposeSMatrix(M, R);
	printf("输出快速转置矩阵R：\n");
	print(R);
	system("pause");
}