稀疏矩阵乘法操作

稀疏矩阵乘法操作稀疏矩阵乘法操作 01.# include 02.# include 03.# define NULL 0 04.# define OK 1 05.# define ERROR 0 06.# define MAXSIZE 100 /* 矩阵中非零元的最大值 */ 07.# define MAXRC 10 /* 矩阵的最大行值 */ 08. 09.typedef int status ; 10. 11. /********** 稀疏矩阵的行逻辑链接的顺序表存储表示 **********/ 12...

稀疏矩阵乘法操作 01.# include 02.# include 03.# define NULL 0 04.# define OK 1 05.# define ERROR 0 06.# define MAXSIZE 100 /* 矩阵中非零元的最大值 */ 07.# define MAXRC 10 /* 矩阵的最大行值 */ 08. 09.typedef int status ; 10. 11. /********** 稀疏矩阵的行逻辑链接的顺序表存储表示 **********/ 12. 13.typedef struct /* 非零元的三元组 */ 14.{ 15. int i, j ; /* 非零元的行下标和列下标 */ 16. int e ; 17.}Triple; 18. 19.typedef struct /* 稀疏矩阵的行逻辑链接的顺序表 */ 20.{ 21. Triple data[MAXSIZE+1]; /* 非零三元组表，data[0]未用，以下定义的数组都是从1开始 */ 22. int rpos[MAXRC+1]; /* 代表各行第一个非零元的序号表，其值为data的下标 */ 23. int mu,nu,tu; /* 矩阵的行数、列数、非零元的个数 */ 24.}RLSMatrix; /* R:row L:logic S:sequence */ 25. 26. 27. /********* 基本操作的函数原型的声明 *********/ 28. 29.status CreateSMatrix_RL(RLSMatrix * matrix); 30.// 创建一个稀疏矩阵; 31.// 输入行数、列数，支持乱序输入三元组，并计数; 32.// 以行为主序进行重新排列，并记录每行起始位置于matrix->rpos[row]; 33.// 若非零元超过 MAXSIZE或行数超过MAXRC，则返回ERROR，否则OK; 34. 35.void PrintSMatrix_RL(RLSMatrix * matrix); 36.// 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩阵; 37. 38.status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q); 39.// 输入两个稀疏矩阵M和N，并初始化Q，然后计算M*N的值赋给Q; 40.// 如果M->mu!=N->nu或列数大于MAXRC或者计算出的非零元个数大于MAXSIZE，都返回ERROR,否则OK; 41.// 计算过程如下: 42.// 1. 由于矩阵M和Q的行数相等并且C语言以行为主序进行存储，所以以M进行逐行的扫描。 43.// 2. 使Q的此行逻辑表的序号等于其非零元个数Q.tu+1，以表示其行的首个元素的序号。 44.// 3. 从行中找到M的非零元，并以它的列值为N的行号，对N进行行的扫描，若存在，则依次计算它们，并把其值累加到一个以N中这个对应非零元的列值为序号的临时数组ctemp[ccol]中。 45.// 4. 在M的当前行完成扫描后，将ctemp[ccol]不为0的值，压入到Q矩阵的三元组，累加++Q.tu，若Q.tu大于了MAXSIZE，这返回ERROR。 46. 47./************ main( ) 函数对矩阵乘法的实现 ************/ 48. 49.void main() 50.{ 51. RLSMatrix * M,* N,* Q; 52. if(!(M=(RLSMatrix *)malloc(sizeof(RLSMatrix)))) 53. exit(ERROR); 54. if(!(N=(RLSMatrix *)malloc(sizeof(RLSMatrix)))) 55. exit(ERROR); 56. if(!(Q=(RLSMatrix *)malloc(sizeof(RLSMatrix)))) 57. exit(ERROR); 58. if(CreateSMatrix_RL(M)&&CreateSMatrix_RL(N)) 59. { 60. printf("/nput out M:/n"); 61. PrintSMatrix_RL(M); /* 打印出M */ 62. printf("/nput out N:/n"); 63. PrintSMatrix_RL(N); /* 打印出N */ 64. if(MultSMatrix_RL(M,N,Q)) 65. { 66. printf("/n/n/n M * N :/n"); 67. PrintSMatrix_RL(Q); /* 计算结果 */ 68. } 69. else 70. printf("M.mu and N.nu are not mathing/n"); 71. } 72. else 73. printf("input error./n"); 74.} 75. 76. 77./*********** 基本操作的算法描述 ****************/ 78. 79.status CreateSMatrix_RL(RLSMatrix * matrix) 80.// 创建一个稀疏矩阵; 81.// 输入行数、列数，支持乱序输入三元组，并计数; 82.{ 83. int num=0,p,q,min,temp; // 中间变量; 84. int row; 85. printf("input the total row and col:/n"); 86. scanf("%d%d",&matrix->mu,&matrix->nu); // 输入行数、列数; 87. if(matrix->mu>MAXRC) 88. return ERROR; 89. printf("row col val/n"); 90. scanf("%d%d%d",&matrix->data[num+1].i,&matrix->data[num+1].j,&matrix->data[num+1 ].e); 91. while(matrix->data[num+1].i) // 乱序输入三元组; 92. { 93. if(++num>MAXSIZE) 94. return ERROR; 95. scanf("%d%d%d",&matrix->data[num+1].i,&matrix->data[num+1].j,&matrix->data[num+1 ].e); 96. } 97. matrix->tu=num; // num的值即为此矩阵的非零元个数; 98. for(p=1;p<=matrix->tu-1;++p) // 按行为主序依次重新排列非零元 99. { 100. min=p; // 使较小的行数、列数的元的序号min为当前值p; 101. for(q=p+1;q<=matrix->tu;++q) // 开始依次比较; 102. { 103. if(matrix->data[min].i>matrix->data[q].i||(matrix->data[min].i==matrix->data[q]. i&&matrix->data[min].j>matrix->data[q].j)) 104. min=q; // 在乱序的三元表中，始终保证min是较小的行列数的序号; 105. } 106. temp=matrix->data[min].i; // 交换行值; 107.matrix->data[min].i=matrix->data[p].i; 108. matrix->data[p].i=temp; 109. temp=matrix->data[min].j; // 交换列值; 110. matrix->data[min].j=matrix->data[p].j; 111. matrix->data[p].j=temp; 112. temp=matrix->data[min].e; // 交换元素值; 113. matrix->data[min].e=matrix->data[p].e; 114. matrix->data[p].e=temp; 115. } 116. for(row=1,num=0;row<=matrix->mu;++row) // 记录 matrix->rpos[row]; 117. { 118. matrix->rpos[row]=num+1; 119. while(matrix->data[num+1].i==row) 120. ++num; 121. } 122. return OK; 123.} 124.// 时间复杂度分析: 125.// 1. 输入非零元:O(tu); 2. 重新排列(最坏情况下);O(tu*(tu-1)) ; 3. 记录行逻辑表:O(mu) 126.void PrintSMatrix_RL(RLSMatrix * matrix) 127.// 输入矩阵，打印出矩阵的行数、列数、非零元个数，以及整个矩阵; 128.{ 129. int row,col; 130. int num=0; 131. printf("/nrow:%d col:%d number:%d/n",matrix->mu,matrix->nu,matrix->tu); 132. for(row=1;row<=matrix->mu;++row) 133. { 134. for(col=1;col<=matrix->nu;++col) 135. { 136. if(num+1<=matrix->tu&&matrix->data[num+1].i==row&&matrix->data[num+1].j==col) 137. { 138. ++num; 139. printf("%4d",matrix->data[num].e); /* 当扫描到非零元的行列值与之相等时，输出其值 */ 140. } 141. else 142. printf("%4d",NULL); /* 没有非零元的地方补0 */ 143. } 144. printf("/n"); /* 每行输入完毕后，换行 */ 145. } 146.} 147. 148.// 时间复杂度:O(mu*nu). 149. 150. 151. 152.status MultSMatrix_RL(RLSMatrix * M,RLSMatrix * N,RLSMatrix * Q) 153.// 输入两个稀疏矩阵M和N，并初始化Q，然后计算M*N的值赋给Q 154.{ 155. int arow,brow,ccol; 156. int * ctemp; /* 以N的列值为序号的临时数组 */ 157. int tp,p,tq,q; /* 中间变量 */ 158. if(M->nu!=N->mu) 159. return ERROR; 160. Q->mu=M->mu; /* 初始化Q */ 161. Q->nu=N->nu; 162. Q->tu=0; 163. if(!(ctemp=(int *)malloc((N->nu+1)*sizeof(int)))) /* 动态建立累加器 */ 164. exit(ERROR); 165. if(M->tu*N->tu!=0) /* Q是非零矩阵 */ 166. { 167. for(arow=1;arow<=M->mu;++arow) /* 逐行扫描 */ 168. { 169. for(ccol=1;ccol<=N->nu;++ccol) 170. ctemp[ccol]=0; /* 初始化累加器 */ 171. Q->rpos[arow]=Q->tu+1; 172. if(arowmu) 173. tp=M->rpos[arow+1]; /* tp是M下一行的序号 */ 174. else 175. tp=M->tu+1; 176. for(p=M->rpos[arow];pdata[p].j; /* 对应元在N中的行号 */ 179. if(browmu) 180. tq=N->rpos[brow+1]; /* tq是N下一行的行号 */ 181. else 182. tq=N->tu+1; 183. for(q=N->rpos[brow];qdata[q].j; /* 提取对应元的列号 */ 186. ctemp[ccol]+=M->data[p].e*N->data[q].e; 187. /* 两个对应元的值相乘并累加到以列号为序号的累加器中 */ 188. } 189. } 190. for(ccol=1;ccol<=Q->nu;++ccol) /* 将此行非零元压缩入Q中 */ 191. { 192. if(ctemp[ccol]) 193. { 194. if(++Q->tu>MAXSIZE) 195. return ERROR; 196. Q->data[Q->tu].i=arow; 197. Q->data[Q->tu].j=ccol; 198. Q->data[Q->tu].e=ctemp[ccol]; 199. } 200. } 201. } 202. } 203. return OK; 204.} 205.// 时间复杂度:O(M->mu*(N->nu+M->nu*N->nu+N->nu));

                    本文档为【稀疏矩阵乘法操作】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

稀疏矩阵乘法操作

你可能还喜欢