矩阵快速转置和乘法.docx
《矩阵快速转置和乘法.docx》由会员分享，可在线阅读，更多相关《矩阵快速转置和乘法.docx（18页珍藏版）》请在冰点文库上搜索。
矩阵快速转置和乘法
矩阵快速转置和乘法
1、课程设计目的及基本要求
本课程设计是为了配合《数据结构》课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用VC上机调试的基本方法。
利用三元组实现稀疏矩阵的有关算法。
基本要求：
1．功能要求--稀疏矩阵是指那些多数元素为零的矩阵，一般来说，当非零元素个数只占矩阵元素的总数的25%-30%或者低于这个百分数。
利“稀疏“特点进行存储和计算可以大大节省存储空间，提高计算效率。
实现一个能进行稀疏矩阵基本运算的运算器。
以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵的转置和两个矩阵相乘的运算。
2．首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。
可设矩阵的行数和列数均不超过20。
3.稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出；乘积矩阵也用二维数组存放。
4.程序可以对三元组的输入顺序加以限制，以行优先，以便提高计算的效率。
5.本程序中，按提示入相应的数据，由用户在键盘上输入演示程序中规定的输入数据。
这里输入的数据值为整型。
二、课程设计的主要任务
1.问题分析和任务定义
（1）稀疏矩阵采用三元组表示方法，可得一种以顺序存储结构的压缩存储结构，后得B（n×m）并对矩阵B输出。
（2）矩阵的乘法即一个矩阵与另一个的行数与前者的列数相同的矩阵相乘。
这里就用上述的矩阵A与B相乘得到C（m×m）并对矩阵C输出。
2.逻辑设计
（1）抽象数据类型稀疏矩阵的定义如下：
ADTSparseMatrix{
数据对象：
D={aij|i=1,2,3……..,m;j=1,2,3…….,n;
Aij属于Elemset,m和n分别称为矩阵的行数和列数}
数据关系：
R={Row,Col}
Row={|1<=i<=m,1<=j<=n-1}
Col={|1<=i<=m-1,1<=j<=n}
基本操作；
CreateSMatrix（&M）;
操作结果：
创建稀疏矩阵M;
PrintSMatrix（M）;
初始条件：
稀疏矩阵M存在。
操作结果：
输出稀疏矩阵M;
TransposeSmatrix（M,N） ;
初始条件：
稀疏矩阵M存在。
操作结果：
输出稀疏矩阵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）
{printf（"请输入第%d个非零元素的行,列,元素值（用空格隔开）:
",p）;
scanf（"%d%d%d",&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（"-----出错啦,请从行到列,从小到大输入!
!
\n"）;
}
elseprintf（"-----出错啦,所输入数据超出范围!
!
\n"）;
if（a==M.mu&&b==M.nu&&p<=M.tu）{printf（"-----出错啦,输入顺序有误,请认真核查,从头输入!
!
\n"）;p=1;}
}
printf（"-----输入成功!
!
\n"）;
returnOK;
}
（3）稀疏矩阵的输出算法
StatusPrintMatrix（TSMatrixM）/*输出一个矩阵*/
{inti,j,p=1;
if（M.tu==0）{printf（"-----找不到此矩阵或为空矩阵!
!
\n"）;returnERROR;}
printf（"---%d行%d列%d个非零元素---\n以阵列方式输出为:
\n",M.mu,M.nu,M.tu）;
for（i=1;i<=M.mu;i++）
{for（j=1;j{if（i==M.data[p].i&&j==M.data[p].j）
{printf（"%d",M.data[p].e）;p++;}
elseprintf（"%d",0）;
}
if（i==M.data[p].i&&j==M.data[p].j）
{printf（"%d\n",M.data[p].e）;p++;}
elseprintf（"%d\n",0）;
}
returnOK;
}
（4）稀疏矩阵的转置算法
StatusTransposeSMatrix（TSMatrixM,TSMatrix&T）/*求快速稀疏矩阵M的转置矩阵T*/
{if（M.tu==0）{printf（"-----找不到所需矩阵!
!
\n"）;returnERROR;}
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
for（p=1;p<=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<=M.nu;++p）cpot[p]=cpot[p-1]+num[p-1];
for（q=1;q<=M.tu;++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];
}
printf（"-----转置成功!
!
\n"）;
returnOK;
}
（5）两个稀疏矩阵的乘法算法
StatusMultSMatrix（TSMatrixM,TSMatrixN,TSMatrix&Q）/*求稀疏矩阵的积Q=M*N*/
{
if（M.tu==0||N.tu==0）{printf（"-----找不到所需矩阵!
!
\n"）;returnERROR;}
if（M.nu!
=N.mu）{printf（"-----此矩阵不能被运算,请核查行列数!
!
\n"）;returnERROR;}
for（p=1;p<=M.tu;p++）/*为M.rpos[]赋值*/
{if（M.data[p].i==k）
{M.rpos[k]=p;
k++;}
elseif（M.data[p].i>k）
{M.rpos[k]=p--;
k++;}
}
for（;k<=M.mu;k++）M.rpos[k]=M.tu;
k=1;
for（q=1;q<=N.tu;q++）/*为N.rpos[]赋值*/
{if（N.data[q].i==k）
{N.rpos[k]=q;k++;}
elseif（N.data[q].i>k）
{N.rpos[k]=p--;k++;}
}
for（;k<=N.mu;k++）N.rpos[k]=N.tu;
Q.mu=M.mu;/*初始化Q*/
Q.nu=N.nu;
Q.tu=0;
for（arow=1;arow<=M.mu;++arow）
{for（ccol=1;ccol<=N.nu;ccol++）
ctemp[ccol]=0;
if（arowtp=M.rpos[arow+1];
elsetp=M.tu+1;
for（p=M.rpos[arow];p{brow=M.data[p].j;
if（browt=N.rpos[brow+1];
elset=N.tu+1;
for（q=N.rpos[brow];q{ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
}
for（ccol=1;ccol<=Q.nu;++ccol）/*将数组的值压缩储存到Q*/
{if（ctemp[ccol]!
=0）
{Q.tu++;
if（Q.tu>MAXSIZE）{printf（"-----出错啦,非零元个数超出最大值!
!
\n"）;returnERROR;}
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];}
}
}
printf（"-----运算成功!
!
\n"）;
returnOK;
}
（6）函数及其函数调用关系
4.程序编码
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
/*稀疏矩阵的三元组顺序表类型TSMatrix的定义*/
#defineMAXSIZE20/*非零元个数最大值*/
#defineMAXRC10
typedefintStatus;
typedefintElemType;
typedefstruct{
inti,j;/*行下标,列下标*/
ElemTypee;/*非零元值*/
}Triple;
typedefstruct{
Tripledata[MAXSIZE+1];/*零元三元组表,data[0]未用*/
intrpos[MAXRC+1];
intmu,nu,tu;/*阵的行数、列数和非零元个数*/
}TSMatrix;
StatusCreateSMatrix（TSMatrix&M）/*创建一个稀疏矩阵*/
{intp=1,a,b,c;
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）
{printf（"请输入第%d个非零元素的行,列,元素值（用空格隔开）:
",p）;
scanf（"%d%d%d",&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（"-----出错啦,请从行到列,从小到大输入!
!
\n"）;
}
elseprintf（"-----出错啦,所输入数据超出范围!
!
\n"）;
if（a==M.mu&&b==M.nu&&p<=M.tu）{printf（"-----出错啦,输入顺序有误,请认真核查,从头输入!
!
\n"）;p=1;}
}
printf（"-----输入成功!
!
\n"）;
returnOK;
}
StatusPrintMatrix（TSMatrixM）/*输出一个矩阵*/
{inti,j,p=1;
if（M.tu==0）{printf（"-----找不到此矩阵或为空矩阵!
!
\n"）;returnERROR;}
printf（"---%d行%d列%d个非零元素---\n以阵列方式输出为:
\n",M.mu,M.nu,M.tu）;
for（i=1;i<=M.mu;i++）
{for（j=1;j{if（i==M.data[p].i&&j==M.data[p].j）
{printf（"%d",M.data[p].e）;p++;}
elseprintf（"%d",0）;
}
if（i==M.data[p].i&&j==M.data[p].j）
{printf（"%d\n",M.data[p].e）;p++;}
elseprintf（"%d\n",0）;
}
returnOK;
}
StatusMultSMatrix（TSMatrixM,TSMatrixN,TSMatrix&Q）/*求稀疏矩阵的积Q=M*N*/
{intarow,brow,p,q,ccol,ctemp[MAXRC+1],t,tp,k=1;
if（M.tu==0||N.tu==0）{printf（"-----找不到所需矩阵!
!
\n"）;returnERROR;}
if（M.nu!
=N.mu）{printf（"-----此矩阵不能被运算,请核查行列数!
!
\n"）;returnERROR;}
for（p=1;p<=M.tu;p++）/*为M.rpos[]赋值*/
{if（M.data[p].i==k）
{M.rpos[k]=p;
k++;}
elseif（M.data[p].i>k）
{M.rpos[k]=p--;
k++;}
}
for（;k<=M.mu;k++）M.rpos[k]=M.tu;
k=1;
for（q=1;q<=N.tu;q++）/*为N.rpos[]赋值*/
{if（N.data[q].i==k）
{N.rpos[k]=q;k++;}
elseif（N.data[q].i>k）
{N.rpos[k]=p--;k++;}
}
for（;k<=N.mu;k++）N.rpos[k]=N.tu;
Q.mu=M.mu;/*初始化Q*/
Q.nu=N.nu;
Q.tu=0;
for（arow=1;arow<=M.mu;++arow）
{for（ccol=1;ccol<=N.nu;ccol++）
ctemp[ccol]=0;
if（arowtp=M.rpos[arow+1];
elsetp=M.tu+1;
for（p=M.rpos[arow];p{brow=M.data[p].j;
if（browt=N.rpos[brow+1];
elset=N.tu+1;
for（q=N.rpos[brow];q{ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
}
for（ccol=1;ccol<=Q.nu;++ccol）/*将数组的值压缩储存到Q*/
{if（ctemp[ccol]!
=0）
{Q.tu++;
if（Q.tu>MAXSIZE）{printf（"-----出错啦,非零元个数超出最大值!
!
\n"）;returnERROR;}
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];}
}
}
printf（"-----运算成功!
!
\n"）;
returnOK;
}
StatusFastTransposeSMatrix（TSMatrixM,TSMatrix&T）/*求快速稀疏矩阵M的转置矩阵T*/
{intp,q,k=1;
intcpot[MAXSIZE],num[MAXSIZE];
if（M.tu==0）{printf（"-----找不到所需矩阵!
!
\n"）;returnERROR;}
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
for（p=1;p<=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<=M.nu;++p）cpot[p]=cpot[p-1]+num[p-1];
for（q=1;q<=M.tu;++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];
}
printf（"-----转置成功!
!
\n"）;
returnOK;
}
voidShow（）
{printf（"*****************************************************************\n"）;
printf（"============>>0.退出程序\n"）;
printf（"\n"）;
printf（"============>>1.创建矩阵A\n"）;
printf（"\n"）;
printf（"============>>2.输出矩阵A\n"）;
printf（"============>>3.输出矩阵B\n"）;
printf（"============>>4.输出矩阵C\n"）;
printf（"\n"）;
printf（"============>>5.转置矩阵A->B\n"）;
printf（"============>>6.矩阵相乘A*B=C\n"）;
printf（"\n"）;
printf（"*****************************************************************\n"）;
}
voidmain（）
{
intselect;
TSMatrixA,B,C;
A.tu=0;B.tu=0;C.tu=0;
Show（）;
while
（1）
{
printf（"请选择:
"）;
scanf（"%d",&select）;
if（select==0）break;
switch（select）{
case1:
CreateSMatrix（A）;
break;
case2:
PrintMatrix（A）;
break;
case3:
PrintMatrix（B）;
break;
case4:
PrintMatrix（C）;
break;
case5:
FastTransposeSMatrix（A,B）;
break;
case6:
MultSMatrix（A,B,C）;
break;
default:
printf（"输入错误,请认真核查!
!
\n"）;
break;
}
}
}
5、测试与分析
升级会员 