• 数组：矩阵快速转置 矩阵相加 三元组顺序表/三元矩阵 随机生成稀疏矩阵 压缩矩阵【C语言，数据结构】（内含源代码）

    目录

    题目：

    题目分析：

    概要设计：

    二维矩阵数据结构：

    三元数组\三元顺序表顺序表结构：

    详细设计：

    三元矩阵相加：

    三元矩阵快速转置：

    调试分析：

    用户手册：

    测试结果：

     源代码：

    主程序：

     头文件SparseMatrix.h：

     头文件Triple.h：

    总结：

    题目：

    稀疏矩阵A，B均采用三元组顺序表表示，验证实现矩阵A快速转置算法，并设计、验证矩阵A、B相加得到矩阵C的算法。

    题目分析：

    1.从键盘输入矩阵的行数、列数，随机生成稀疏矩阵。

    2.生成矩阵A、B后需先转换成三元顺序表，然后用三元顺序表来进行之后的操作。

    3.在三元顺序表的基础上使用快速转置（非二维矩阵）。

    4.得到三元矩阵相加的结果C。

    5.不仅需要输出三元矩阵，还需要把结果转换成二维矩阵输出，以便题目观察结果。

    6.程序执行的命令包括：(1)根据输入构造二维矩阵 (2)根据二维矩阵转换成相应的三元矩阵 (3)根据三元矩阵转换为相应的二维矩阵 (4)输出程序 (5)三元矩阵相加 (6)三元矩阵快速转置

    7.测试用例：

    1. 1
    2. (内置测试用例测试，主要包括相加为0的矩阵测试)
    3.  
    4. 2
    5. 5 5
    6. 5 5
    7. (测试5*5和5*5的矩阵)
    8.  
    9. 2
    10. 8 9
    11. 9 8
    12. (两个矩阵大小不同，不能进行相加运算，应该有相应的报错)
    13.  
    14. 2
    15. 9 8
    16. 9 8
    17. (正常的矩阵测试)

    概要设计：

    二维矩阵数据结构：

    如图，把这种数据结构可视化就是这样的，完全是按照人类习惯的一种存储方式 <(￣ˇ￣)/

    1. typedef struct {
    2. 	Elemtype **D;
    3. 	int m, n;
    4. 	int tu;
    5. } SparseMatrix, M;

    老师说：数据结构决定算法。所以在这里在二维矩阵数据结构中增加行数m、列数n，就可以在进入函数，传参的时候少传入n和m两个值。

    tu记录矩阵中非0元素的个数，可以更方便地进行三元数组的转换。

    三元数组\三元顺序表顺序表结构：

     把上面的二维矩阵转换一下，对应的三元矩阵就长这样，只存了非0元的行、列和数据￣へ￣

    三元数据结构的主要作用是将存储信息密度低的二维矩阵，以一种密度更高的方式储存在计算机中。

    1. typedef struct {
    2. 	int i, j;
    3. 	Elemtype e;
    4. } Triple;
    5.  
    6. typedef struct {
    7. 	Triple data[MAXSIZE + 1];
    8. 	int mu, nu, tu;
    9. } TSMatrix;

    首先三元数组数据结构中，三元数组的定义，首先要定义“三元”。

    三元Triple 由数据的行i，列j，数据e组成。

    三元数组数据结构中同样存储着行数mu，列数nu，非零元个数tu。

    详细设计：

    三元矩阵相加：

    首先，在矩阵相加中有许多操作相同的代码，为了降低代码复用性，所以提取代码中用图相同的代码，做成GO函数当当~ O(∩_∩)O~~

    其次，因为大小不同的矩阵不能相加，所以在函数里，可以不用判断两个矩阵的大小，就默认两个矩阵是一样大的。别问我为什么还有注释掉的判断 ╥﹏╥...

    最后是最重要的，两个数相加，如果两个答案为0，则不存入，因为他已经成为零元惹(。﹏。*)

    然后是相加部分的判断。当两个元素是相同位置的时候，两个执行相加操作，当A的元素在B的后面的时候，则执行前面的B的输入。相反也同理。注意：这里的位置并不是在三元顺序表中的位置，而是在二维数组中的位置，所以不仅可以通过我这种i和j的判断，还可以通过A.data[i][j]-A.data[0][0]得到在数组中的第几位，这种更高级的判断，为什么我没有用捏，因为老师要检查代码，为了更高的阅读性，我选择用传统的i和j的方式( *︾▽︾)

    1. Status GO(int *t, int *q, TSMatrix A, TSMatrix *C) {
    2. 	C->data[*q].i = A.data[*t].i;
    3. 	C->data[*q].j = A.data[*t].j;
    4. 	C->data[*q].e = A.data[*t].e;
    5. 	(*q)++, (*t)++;
    6. 	return OK;
    7. }
    8.  
    9. Status AddTripleSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C) {
    10. 	//add two tripleM
    11. 	int ta = 0, tb = 0, q = 0, tool;
    12. 	C->mu = A.mu;
    13. 	C->nu = A.nu;
    14. //	if(B.mu > C->mu) {
    15. //		C->mu = B.mu;
    16. //	}
    17. //	if(B.nu > C->nu) {
    18. //		C->nu = B.nu;
    19. //	}
    20. 	while(ta < A.tu && tb < B.tu) {
    21. 		if(A.data[ta].i == B.data[tb].i) {
    22. 			if(A.data[ta].j == B.data[tb].j) {
    23. 				tool = A.data[ta].e+B.data[tb].e;
    24. 				if(C->data[q].e != 0) {
    25. 					C->data[q].i = A.data[ta].i;
    26. 					C->data[q].j = A.data[ta].j;
    27. 					C->data[q].e = A.data[ta].e+B.data[tb].e;
    28. 					q++;
    29. 				}
    30. 				ta++, tb++;
    31. 			} else if(A.data[ta].j > B.data[tb].j) {
    32. 				GO(&tb, &q, B, C);
    33. 			} else if(A.data[ta].j < B.data[tb].j) {
    34. 				GO(&ta, &q, A, C);
    35. 			}
    36. 		} else if(A.data[ta].i > B.data[tb].i) {
    37. 			GO(&tb, &q, B, C);
    38. 		} else if(A.data[ta].i < B.data[tb].i) {
    39. 			GO(&ta, &q, A, C);
    40. 		}
    41. 	}
    42. 	while(ta < A.tu) {
    43. 		GO(&ta, &q, A, C);
    44. 	}
    45. 	while(tb < B.tu) {
    46. 		GO(&tb, &q, B, C);
    47. 	}
    48. 	C->tu = q;
    49. 	return OK;
    50. }

    三元矩阵快速转置：

    首先转置有个要求，三元矩阵转置后i要求从小到大排列，所以并不是简单的i = j，j = i就行了。

    快速转置前，先看普通转置，知道为什么快速

    这是普通转置，可以看到，就是简单的暴力搜索，用了双重循环，时间是N^2，n的平方。为了降低时间复杂度，所以有了快速转置：( ˇˍˇ )

    这个呢就是书上的算法，直接上书上的原图吧。

     这里讲的是什么意思呢，大致说人话就是：

    用num数组存储转置后每一行有多少个数（非零元），用num数组是为了快速求出cpot数组

    cpot数组存储转置后每一行第一个元素在三元表里的位置。( ‵▽′)ψ

    然后再根据cpot数组，把每个元素送到三元表里对应的地方。

    这样说不好理解，举个例子吧┗|*｀0′*|┛ ：

     这个矩阵二维和三元长这样，转置前。

     现在先处理num数组，我就遍历三元组j这一列，num数组一开始里面全是0，遍历的时候num[j]++，这样num[j]存的就是（转置前第j列）转置后第i行的非零元数量。

    比如第一个j = 2，那么num[2]++;就代表j = 2行多一个数。

    第二步，确定cpot数组，      

     cpot[0] = 0;
            for(col = 1; col < Mx.nu; col++) {
                cpot[col] = num[col - 1] + cpot[col - 1];
            }

    是的，简单的运算就行就这么简单。

    第三步，根据cpot数组，把对应的元素送到合适的地方，让转置后i能从小到大排列。

    具体做法是：从上到下，遍历j ，遍历到的第一个j 就是j 列的第一个数【暂停，想一下为什么就是第一个】(⊙3⊙)

    以此类推第二个j 就是 j列的第二个。

    举例，第一个j = 2是第一个，那么根据cpot数组能确定，j = 2，在转置后是三元组里的第几个元。当我扫描到下一个j = 2的时候，就是转置后j = 2 的第二个元。(⊙ω⊙)

    以下是实现

    1. Status TransposeSMatrix(TSMatrix Mx, TSMatrix *T) {
    2. 	//TransposeSM normally
    3. 	int col, num[Mx.nu], cpot[Mx.nu], t, p, q;
    4. 	T->mu = Mx.nu;
    5. 	T->nu = Mx.mu;
    6. 	T->tu = Mx.tu;
    7. 	if(T->tu) {
    8. 		for(col = 0; col < Mx.nu; col++) {
    9. 			num[col] = 0;
    10. 		}
    11. 		for(t = 0; t < Mx.tu; t++) {
    12. 			num[Mx.data[t].j]++;
    13. 		}
    14. 		cpot[0] = 0;
    15. 		for(col = 1; col < Mx.nu; col++) {
    16. 			cpot[col] = num[col - 1] + cpot[col - 1];
    17. 		}
    18. 		for(p = 0; p < Mx.tu; p++) {
    19. 			col = Mx.data[p].j;
    20. 			q = cpot[col];
    21. 			T->data[q].i = Mx.data[p].j;
    22. 			T->data[q].j = Mx.data[p].i;
    23. 			T->data[q].e = Mx.data[p].e;
    24. 			cpot[col]++;
    25. 		}
    26. 	}
    27. 	return OK;
    28. }

    调试分析：

    1.数组为了我们计算方便，我们是从0开始存的，但是为了我们看起来更符合数学逻辑，更美观，我们要输出i+1，这样输出就是从1开始的。

    2.其他就没什么嗦的了，O__O "…

    用户手册：

    dos操作系统

    先选择模式，输入1为测试模式，测试用例会包含所有特殊情况，可以看到结果都能正确处理。

    输入2为正常模式，根据提示，输入两个矩阵的长和宽。

    1和2模式都会输出原矩阵A，B和他的三元矩阵。AB相加得到的矩阵C和C的三元矩阵。A转置得到的矩阵TA和TA的三元矩阵。

    若2模式下，两矩阵A、B大小不同，则无法进行相加操作，输出数组不等大的报错。

    测试结果：

    输入：

    1

     输入：

    1. 2
    2. 8 9
    3. 9 8

     

     输入：

    1. 2
    2. 5 5 
    3. 5 5

    这里B的随机结果为0个非零元，比较特殊。

    输入：

    1. 2
    2. 8 9
    3. 8 9

     

     

     源代码：

    主程序：

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. typedef int Status;
    6. #define OK 1
    7. #define ERROR 0
    8.  
    9. typedef int Elemtype;
    10.  
    11. #include "Triple.h"
    12. #include "SparseMatrix.h"
    13.  
    14. Status RandInitSM(M *);	//scan in m & n ,and Random init a sparseMatrix
    15. Status TranslateToTM(M, TSMatrix *);	//translate M to TM;
    16. Status TranslateToM(TSMatrix, M *);	//translate TM to M;
    17. Status TransposeSMatrix(TSMatrix, TSMatrix *);	//TransposeSM normally
    18. Status AddTripleSMatrix(TSMatrix, TSMatrix, TSMatrix *);	//add two tripleM
    19. Status TestInit(M *, M *);	//test init;
    20.  
    21. int main() {
    22. 	M MB, MA, MC, TMA;
    23. 	TSMatrix A, B, C, TA;
    24. 	int chiose = 0;
    25. 	printf("Start Modle: 1-test 2-Normal running\n");
    26. 	scanf("%d", &chiose);
    27. 	if(chiose == 1) {
    28. 		TestInit(&MA, &MB);
    29. 	} else if(chiose == 2) {
    30. 		//Create a Sparsematrix;
    31. 		printf("How big the matrix will you create?(m & n):\n");
    32. 		RandInitSM(&MA);
    33. 		printf("How big the next matrix will you create?(m & n):\n");
    34. 		RandInitSM(&MB);
    35. 	} else {
    36. 		printf("\n ERROR!!\n");
    37. 		return 0;
    38. 	}
    39. 	if(MA.m != MB.m || MA.n != MB.n) {
    40. 		printf("\n Not the same size!!\n");
    41. 		return 0;
    42. 	}
    43.  
    44.  
    45. 	//Make M to TM;
    46. 	TranslateToTM(MA, &A);
    47. 	//Make M to TM;
    48. 	TranslateToTM(MB, &B);
    49.  
    50. 	//transposeSMatrix
    51. 	TransposeSMatrix(A, &TA);
    52. 	TranslateToM(TA, &TMA);
    53.  
    54. 	//C = A+B;
    55. 	AddTripleSMatrix(A, B, &C);
    56. 	//Make TM to M;
    57. 	TranslateToM(C, &MC);
    58.  
    59. 	printf("MA:");
    60. 	PrintSMatrix(MA);
    61. 	printf("MB:");
    62. 	PrintSMatrix(MB);
    63. 	printf("MC:");
    64. 	PrintSMatrix(MC);
    65.  
    66. 	printf("A:\n");
    67. 	PrintTM(A);
    68. 	printf("B:\n");
    69. 	PrintTM(B);
    70. 	printf("C:\n");
    71. 	PrintTM(C);
    72.  
    73. 	printf("\n------------------\n");
    74. 	printf("MA:");
    75. 	PrintSMatrix(MA);
    76. 	printf("TMA:");
    77. 	PrintSMatrix(TMA);
    78.  
    79. 	printf("A:\n");
    80. 	PrintTM(A);
    81. 	printf("TA:\n");
    82. 	PrintTM(TA);
    83.  
    84.  
    85. 	return 0;
    86. }
    87.  
    88. Status TestInit(M *MA, M *MB) {
    89. 	//test init;
    90. 	InitSMatrix(3, 4, MA);
    91. 	InitSMatrix(3, 4, MB);
    92.  
    93. //	A
    94. //	 1  0  0  2
    95. //	 0 -1  0  2
    96. //	 0  0  0  3
    97. //	B
    98. //	 0  1  0 -1
    99. //	 1  1  0  0
    100. //	 0  0  0  0
    101. 	MA->tu = 5;
    102. 	MA->D[0][0] = 1;
    103. 	MA->D[0][3] = 2;
    104. 	MA->D[1][1] = -1;
    105. 	MA->D[1][3] = 2;
    106. 	MA->D[2][3] = 3;
    107. 	MB->tu = 4;
    108. 	MB->D[0][1] = 1;
    109. 	MB->D[0][3] = -1;
    110. 	MB->D[1][0] = 1;
    111. 	MB->D[1][1] = 1;
    112. 	return 0;
    113. }
    114.  
    115. Status RandInitSM(M *M) {
    116. 	//scan in m & n ,and Random init a sparseMatrix
    117. 	int m, n;
    118. 	int randN;
    119. 	int i, j, k;
    120. 	srand((unsigned)time(NULL));
    121.  
    122. 	scanf("%d %d", &m, &n);
    123. 	InitSMatrix(m, n, M);
    124.  
    125. 	M->tu = rand() % (m + n) * 2;
    126. 	for(k = 0; k < M->tu; k++) {
    127. 		i = rand() % m;
    128. 		j = rand() % n;
    129. 		randN = rand() % 20;
    130. 		M->D[i][j] = randN;
    131. 	}
    132.  
    133. 	return OK;
    134. }
    135.  
    136. Status TranslateToTM(M M, TSMatrix *TM) {
    137. 	//translate M to TM;
    138. 	int i, j, cot = 0;
    139. 	TM->mu = M.m;
    140. 	TM->nu = M.n;
    141. 	for(i = 0; i < M.m; i++) {
    142. 		for(j = 0; j < M.n; j++) {
    143. 			if(M.D[i][j] != 0) {
    144. 				TM->data[cot].e = M.D[i][j];
    145. 				TM->data[cot].i = i;
    146. 				TM->data[cot].j = j;
    147. 				cot++;
    148. 			}
    149. 		}
    150. 	}
    151. 	TM->tu = cot;
    152. 	return OK;
    153. }
    154. Status TranslateToM(TSMatrix C, M *MC) {
    155. 	//translate TM to M;
    156. 	int i;
    157. 	MC->m = C.mu;
    158. 	MC->n = C.nu;
    159. 	MC->tu = C.tu;
    160. 	InitSMatrix(C.mu, C.nu, MC);
    161. 	for(i = 0; i < C.tu; i++) {
    162. 		MC->D[C.data[i].i][C.data[i].j] = C.data[i].e;
    163. 	}
    164. 	return OK;
    165. }
    166.  
    167. Status TransposeSMatrix(TSMatrix Mx, TSMatrix *T) {
    168. 	//TransposeSM normally
    169. 	int col, num[Mx.nu], cpot[Mx.nu], t, p, q;
    170. 	T->mu = Mx.nu;
    171. 	T->nu = Mx.mu;
    172. 	T->tu = Mx.tu;
    173. 	if(T->tu) {
    174. 		for(col = 0; col < Mx.nu; col++) {
    175. 			num[col] = 0;
    176. 		}
    177. 		for(t = 0; t < Mx.tu; t++) {
    178. 			num[Mx.data[t].j]++;
    179. 		}
    180. 		cpot[0] = 0;
    181. 		for(col = 1; col < Mx.nu; col++) {
    182. 			cpot[col] = num[col - 1] + cpot[col - 1];
    183. 		}
    184. 		for(p = 0; p < Mx.tu; p++) {
    185. 			col = Mx.data[p].j;
    186. 			q = cpot[col];
    187. 			T->data[q].i = Mx.data[p].j;
    188. 			T->data[q].j = Mx.data[p].i;
    189. 			T->data[q].e = Mx.data[p].e;
    190. 			cpot[col]++;
    191. 		}
    192. 	}
    193. 	return OK;
    194. }
    195.  
    196. Status GO(int *t, int *q, TSMatrix A, TSMatrix *C) {
    197. 	C->data[*q].i = A.data[*t].i;
    198. 	C->data[*q].j = A.data[*t].j;
    199. 	C->data[*q].e = A.data[*t].e;
    200. 	(*q)++, (*t)++;
    201. 	return OK;
    202. }
    203.  
    204. Status AddTripleSMatrix(TSMatrix A, TSMatrix B, TSMatrix *C) {
    205. 	//add two tripleM
    206. 	int ta = 0, tb = 0, q = 0, tool;
    207. 	C->mu = A.mu;
    208. 	C->nu = A.nu;
    209. 	if(B.mu > C->mu) {
    210. 		C->mu = B.mu;
    211. 	}
    212. 	if(B.nu > C->nu) {
    213. 		C->nu = B.nu;
    214. 	}
    215. 	while(ta < A.tu && tb < B.tu) {
    216. 		if(A.data[ta].i == B.data[tb].i) {
    217. 			if(A.data[ta].j == B.data[tb].j) {
    218. 				tool = A.data[ta].e+B.data[tb].e;
    219. 				if(C->data[q].e != 0) {
    220. 					C->data[q].i = A.data[ta].i;
    221. 					C->data[q].j = A.data[ta].j;
    222. 					C->data[q].e = A.data[ta].e+B.data[tb].e;
    223. 					q++;
    224. 				}
    225. 				ta++, tb++;
    226. 			} else if(A.data[ta].j > B.data[tb].j) {
    227. 				GO(&tb, &q, B, C);
    228. 			} else if(A.data[ta].j < B.data[tb].j) {
    229. 				GO(&ta, &q, A, C);
    230. 			}
    231. 		} else if(A.data[ta].i > B.data[tb].i) {
    232. 			GO(&tb, &q, B, C);
    233. 		} else if(A.data[ta].i < B.data[tb].i) {
    234. 			GO(&ta, &q, A, C);
    235. 		}
    236. 	}
    237. 	while(ta < A.tu) {
    238. 		GO(&ta, &q, A, C);
    239. 	}
    240. 	while(tb < B.tu) {
    241. 		GO(&tb, &q, B, C);
    242. 	}
    243. 	C->tu = q;
    244. 	return OK;
    245. }

     头文件SparseMatrix.h：

    1. #include 
    2.  
    3. typedef struct {
    4. 	Elemtype **D;
    5. 	int m, n;
    6. 	int tu;
    7. } SparseMatrix, M;
    8.  
    9. Status InitSMatrix(int, int, M *);	//Init M;
    10. Status PrintSMatrix(M);
    11.  
    12. Status InitSMatrix(int m, int n, M *M) {
    13. 	//Init M;
    14. 	M->m = m;
    15. 	M->n = n;
    16. 	M->D = (Elemtype **)malloc(m * sizeof(Elemtype *));
    17. 	for ( int i = 0; i < m; i++) {
    18. 		M->D[i] = (Elemtype *)malloc(n * sizeof(Elemtype));
    19. 	}
    20. 	for (int i = 0; i < m; i++) {
    21. 		for (int j = 0; j < n; j++) {
    22. 			M->D[i][j] = 0;
    23. 		}
    24. 	}
    25. 	if(M->D) {
    26. 		return OK;
    27. 	}
    28. 	return ERROR;
    29. }
    30.  
    31. Status PrintSMatrix(M M) {
    32. 	int i, j;
    33. 	for(i = 0; i < M.m; i++) {
    34. 		printf("\n");
    35. 		for(j = 0; j < M.n; j++) {
    36. 			printf("%2d ", M.D[i][j]);
    37. 		}
    38. 	}
    39. 	printf("\n");
    40. 	return OK;
    41. }

     头文件Triple.h：

    1. #define MAXSIZE 12500
    2. typedef struct {
    3. 	int i, j;
    4. 	Elemtype e;
    5. } Triple;
    6.  
    7. typedef struct {
    8. 	Triple data[MAXSIZE + 1];
    9. 	int mu, nu, tu;
    10. } TSMatrix;
    11.  
    12. Status PrintTM(TSMatrix);
    13.  
    14. Status PrintTM(TSMatrix TM) {
    15. 	int i;
    16. 	printf("|  i |  j |  v |\n");
    17. 	for(i = 0; i < TM.tu; i++) {
    18. 		printf("| %2d | %2d | %2d |\n", TM.data[i].i + 1, TM.data[i].j + 1, TM.data[i].e);
    19. 	}
    20. 	return OK;
    21. }

    总结：

    可以看到两个头文件里其实没什么东西，因为上机实验要展示的东西太多了，也就是说这道题其实不好╮(╯﹏╰)╭，就是要硬考你数据结构。

    o_O???

    加油↖(^ω^)↗ 一起努力。

  • 相关阅读:
    什么是跨域
    863. All Nodes Distance K in Binary Tree
    计算机系统基础知识-经典题目
    【云原生】一文讲透Kubevela addon如何添加腾讯Crane
    【数据结构】排序--选择排序(堆排序)
    HTTP 参数污染 (HPP) 和 HTTP 参数碎片 (HPF)
    分类预测 | MATLAB实现CNN-LSTM(卷积长短期记忆神经网络)多特征分类预测
    LINUX
    Android View 实现动画简单介绍
    真机测试——关于荣耀Magic UI系列HBuilder真机调试检测不到解决办法
  • 原文地址：https://blog.csdn.net/qq_62792553/article/details/127888804