矩阵快速转置和乘法Word下载.docx
《矩阵快速转置和乘法Word下载.docx》由会员分享，可在线阅读，更多相关《矩阵快速转置和乘法Word下载.docx（18页珍藏版）》请在冰点文库上搜索。
|1<
=i<
=m,1<
=j<
=n-1}
Col={<
ai,j,ai+1,j>
=m-1,1<
=n}
基本操作；
CreateSMatrix（&
M）;
操作结果：
创建稀疏矩阵M;
PrintSMatrix（M）;
初始条件：
稀疏矩阵M存在。
输出稀疏矩阵M;
TransposeSmatrix（M,N）
;
输出稀疏矩阵N
MultSMatrix（M,N,&
Q）;
稀疏矩阵M的行数等于N的列数。
求稀疏矩阵的和Q=M*N.
}ADTSparseMatrix
（2）数据结构：
row
col
value
三元组的结构
（3）程序模块：
1）主程序模块：
Intmain（）
{
初始化；
While
（1）
接受命令；
处理命令；
}
}
2）创建稀疏矩阵模块；
3）对已创建好的稀疏矩阵进行快速矩阵转置；
4）求稀疏矩阵的乘积Q=M*N模块；
5）输出稀疏矩阵模块；
（4）各模块的调用关系及算法设计如下流程图所示
四、详细设计
（1）三元组数据结构算法
typedefstruct{
inti,j;
/*行下标,列下标*/
ElemTypee;
/*非零元值*/
}Triple;
typedefstruct{
Tripledata[MAXSIZE+1];
/*零元三元组表,data[0]未用*/
intrpos[MAXRC+1];
intmu,nu,tu;
/*阵的行数、列数和非零元个数*/
}TSMatrix;
（2）稀疏矩阵的创建算法
StatusCreateSMatrix（TSMatrix&
M）/*创建一个稀疏矩阵*/
printf（"
请输入稀疏矩阵的行数,列数,非零元数（请小于20个,用空格隔开各数据）:
"
）;
scanf（"
%d%d%d"
&
M.mu,&
M.nu,&
M.tu）;
if（M.tu>
MAXSIZE||M.tu<
=0||M.tu>
M.mu*M.nu）
{printf（"
-----出错啦,非零元个数超过最大值!
!
\n"
returnERROR;
while（p<
=M.tu）
请输入第%d个非零元素的行,列,元素值（用空格隔开）:
p）;
scanf（"
a,&
b,&
c）;
M.data[0].i=0;
M.data[0].j=0;
if（a<
=M.mu&
&
b<
=M.nu&
c!
=0）
{if（a>
M.data[p-1].i||（a==M.data[p-1].i&
b>
M.data[p-1].j））
{M.data[p].i=a;
M.data[p].j=b;
M.data[p].e=c;
p++;
elseprintf（"
-----出错啦,请从行到列,从小到大输入!
elseprintf（"
-----出错啦,所输入数据超出范围!
if（a==M.mu&
b==M.nu&
p<
=M.tu）{printf（"
-----出错啦,输入顺序有误,请认真核查,从头输入!
p=1;
-----输入成功!
returnOK;
（3）稀疏矩阵的输出算法
StatusPrintMatrix（TSMatrixM）/*输出一个矩阵*/
{inti,j,p=1;
if（M.tu==0）{printf（"
-----找不到此矩阵或为空矩阵!
）;
---%d行%d列%d个非零元素---\n以阵列方式输出为:
M.mu,M.nu,M.tu）;
for（i=1;
i<
=M.mu;
i++）
{for（j=1;
j<
M.nu;
j++）
{if（i==M.data[p].i&
j==M.data[p].j）
%d"
M.data[p].e）;
0）;
if（i==M.data[p].i&
%d\n"
}
（4）稀疏矩阵的转置算法
StatusTransposeSMatrix（TSMatrixM,TSMatrix&
T）/*求快速稀疏矩阵M的转置矩阵T*/
{if（M.tu==0）{printf（"
-----找不到所需矩阵!
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
for（p=1;
=M.nu;
++p）num[p]=0;
for（q=1;
q<
=M.tu;
++q）++num[M.data[q].j];
cpot[1]=1;
for（p=2;
++p）cpot[p]=cpot[p-1]+num[p-1];
++q）
{p=M.data[q].j;
k=cpot[p];
T.data[k].i=M.data[q].j;
T.data[k].j=M.data[q].i;
T.data[k].e=M.data[q].e;
++cpot[p];
-----转置成功!
（5）两个稀疏矩阵的乘法算法
StatusMultSMatrix（TSMatrixM,TSMatrixN,TSMatrix&
Q）/*求稀疏矩阵的积Q=M*N*/
if（M.tu==0||N.tu==0）{printf（"
if（M.nu!
=N.mu）{printf（"
-----此矩阵不能被运算,请核查行列数!
p++）/*为M.rpos[]赋值*/
{if（M.data[p].i==k）
{M.rpos[k]=p;
k++;
elseif（M.data[p].i>
k）
{M.rpos[k]=p--;
for（;
k<
k++）M.rpos[k]=M.tu;
k=1;
=N.tu;
q++）/*为N.rpos[]赋值*/
{if（N.data[q].i==k）
{N.rpos[k]=q;
k++;
elseif（N.data[q].i>
{N.rpos[k]=p--;
=N.mu;
k++）N.rpos[k]=N.tu;
Q.mu=M.mu;
/*初始化Q*/
Q.nu=N.nu;
Q.tu=0;
for（arow=1;
arow<
++arow）
{for（ccol=1;
ccol<
=N.nu;
ccol++）
ctemp[ccol]=0;
if（arow<
M.mu）
tp=M.rpos[arow+1];
elsetp=M.tu+1;
for（p=M.rpos[arow];
tp;
++p）
{brow=M.data[p].j;
if（brow<
N.mu）
t=N.rpos[brow+1];
elset=N.tu+1;
for（q=N.rpos[brow];
t;
{ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
for（ccol=1;
=Q.nu;
++ccol）/*将数组的值压缩储存到Q*/
{if（ctemp[ccol]!
=0）
{Q.tu++;
if（Q.tu>
MAXSIZE）{printf（"
-----出错啦,非零元个数超出最大值!
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];
printf（"
-----运算成功!
returnOK;
（6）函数及其函数调用关系
4.程序编码
#include<
stdio.h>
stdlib.h>
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
/*稀疏矩阵的三元组顺序表类型TSMatrix的定义*/
#defineMAXSIZE20/*非零元个数最大值*/
#defineMAXRC10
typedefintStatus;
typedefintElemType;
{intp=1,a,b,c;
StatusMultSMatrix（TSMatrixM,TSMatrixN,TSMatrix&
{intarow,brow,p,q,ccol,ctemp[MAXRC+1],t,tp,k=1;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
StatusFastTransposeSMatrix（TSMatrixM,TSMatrix&
{intp,q,k=1;
intcpot[MAXSIZE],num[MAXSIZE];
voidShow（）
{printf（"
*****************************************************************\n"
============>
>
0.退出程序\n"
1.创建矩阵A\n"
2.输出矩阵A\n"
3.输出矩阵B\n"
4.输出矩阵C\n"
5.转置矩阵A->
B\n"
6.矩阵相乘A*B=C\n"
voidmain（）
intselect;
TSMatrixA,B,C;
A.tu=0;
B.tu=0;
C.tu=0;
Show（）;
while
（1）
请选择:
"
%d"
select）;
if（select==0）break;
switch（select）{
case1:
CreateSMatrix（A）;
break;
case2:
PrintMatrix（A）;
case3:
PrintMatrix（B）;
case4:
PrintMatrix（C）;
case5:
FastTransposeSMatrix（A,B）;
case6:
MultSMatrix（A,B,C）;
default:
输入错误,请认真核查!
5、测试与分析
升级会员 