稀疏矩阵基本操作 实验报告.docx
《稀疏矩阵基本操作 实验报告.docx》由会员分享，可在线阅读，更多相关《稀疏矩阵基本操作 实验报告.docx（25页珍藏版）》请在冰点文库上搜索。
稀疏矩阵基本操作实验报告
稀疏矩阵基本操作实验报告
一、实验内容
稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表示方法下的转置、相加、相乘等算法
二、实验目的
1.熟悉数组、矩阵的定义和基本操作
2.熟悉稀疏矩阵的储存方式和基本运算
3.理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法
三、实验原理
1.使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和元素值）。
除了三元组表本身，储存一个稀疏矩阵还需要额外的三个变量，分别储存矩阵的非零元个数，矩阵的行数和矩阵的列数。
2.稀疏矩阵的创建算法：
第一步：
根据矩阵创建一个二维数组，表示原始矩阵
第二步：
取出二维数组中的元素（从第一个元素开始取），判断取出元素是否为非零元素，如果为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数组表里，否则取出下一个元素，重复该步骤。
第三步：
重复第二步，知道二维数组中所有的元素已经取出。
3.稀疏矩阵倒置算法：
第一步：
判断进行倒置的矩阵是否为空矩阵，如果是，则直接返回错误信息。
第二步：
计算要倒置的矩阵每列非零元素的数量，存入到num数组（其中num[i]代表矩阵中第i列非零元素的个数）。
以及倒置后矩阵每行首非零元的位置，存入cpot数组中（其中cpot表示倒置后矩阵每行非零元的位置，对应表示原矩阵每列中第一个非零元的位置）。
第三步：
确定倒置后矩阵的行数和列数。
第四步：
取出表示要导致矩阵中三元组表元素{e,I,j}（第一次取出第一个，依次取出下一个元素），从第二步cpot数组中确定该元素倒置后存放的位置（cpot[j]），把该元素的行下标和列下标倒置以后放入新表的指定位置中。
cpot[j]变量加一。
第五步：
重复第四步，直到三元组表中所有的元素都完成倒置。
第六步：
把完成倒置运算的三元组表输出。
4.稀疏矩阵加法算法：
第一步：
检查相加两个矩阵的行数和列数是否相同，如果相同，则进入第二步，否则输出错误信息。
第二步：
定义变量i和j，用于控制三元组表的遍历。
第三步：
比较变量矩阵M中第i个元素和矩阵N中第j个元素，如果两个元素是同一行元素，如果不是则进入第四步，如果是，再继续比较两个元素是否为同一列元素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放到三元组表中。
进入第五步
第四步：
如果矩阵M中第i个元素的行下标大于矩阵N中第j个元素的行下标，则把矩阵N中第j个元素所在行的所有非零元素添加到三元组表中；如果矩阵M中第i个元素的行下标小于矩阵N中第j个元素的下标，则把M中第i个元素所在行的所有非零元素依次添加到三元组表中。
第五步：
重复第三步，直到矩阵M和矩阵N中所有元素都非零元素添加到三元组表中。
第六步：
输出运算结果
5.稀疏矩阵乘法算法：
第一步：
检查矩阵M和矩阵N能否参与乘法运算（即矩阵M的列数等于矩阵N的行数），如果两个矩阵可以参与乘法运算，进入下一步，否则输出错误信息
第二步：
检查两个矩阵相乘以后是否为零矩阵，如果相乘结果是零矩阵，直接返回一个零矩阵。
第三步：
分别计算矩阵M和矩阵N中每行非零元的个数（分别存放到num_m和num_n数组中），并计算出每行首非零元的位置（分别存放到cpot_m和cpot_n中）。
第四步：
依次取矩阵M中的非零元（第一次取出矩阵M中的第一个非零元），求出该非零元所在行和所在列乘积的和，然后把值放到结果三元组表的特定位置。
第五步：
重复第四步，直到矩阵M中所有非零元都已经参与运算。
第六步：
输出结果
四、
程序流程图
五、实验结果
5.1
程序主菜单
5.2
稀疏矩阵三元组的创建和倒置
5.3
稀疏矩阵的加法运算并以三元组输出结果
5.4
稀疏矩阵的乘法运算并以矩阵方式输出结果
六、操作说明
1.在创建稀疏矩阵的时候，可以每次输入一个数据，也可以一次输入多个数据，程序会自动根据输入元素的个数对矩阵数据进行填充
2.每次矩阵运算失败时（无论是输入的矩阵不符合矩阵运算的条件，参与运算其中一个矩阵为空矩阵，或者分配不到临时空间），程序都会返回到主菜单。
输入的数据都会被清空。
七、附录：
代码
#include
#include
#include
#defineMAXSIZE1000
#defineOK0
#defineMALLOC_FAIL-1//表示分配空间时发生错误
#defineEMPTY_MATRIX-2//表示正尝试对一个空矩阵进行运算操作
#defineMATRIX_NOT_MATCH-3//表示尝试对不符合运算条件的矩阵进行运算操作（例如非相同行数列数矩阵相加）
/*-----------结构体声明部分----------------*/
typedefstruct
{
introw;//非零元的行下标
intcol;//非零元的列下标
inte;//非零元的值
}Triple;
typedefstruct
{
Triple*data;//非零元素的元素表
intrownum;//矩阵的行数
intcolnum;//矩阵的列数
intnum;//矩阵非零元的个数
}TSMatrix,*PTSMatrix;
/*-----------函数声明部分------------------*/
//初始化稀疏矩阵结构
intTSMatrix_Init（TSMatrix*M）;
//以三元组的方式输出稀疏矩阵
voidTSMatrix_PrintTriple（TSMatrix*M）;
//以矩阵的方式输出稀疏矩阵
voidTSMartix_PrintMatrix（TSMatrix*M）;
//从一个二维数组（普通矩阵）创建一个稀疏矩阵
TSMatrix*TSMatrix_Create（int*a,introw,intcol）;
//从键盘录入数据创建一个稀疏矩阵
TSMatrix*TSMatrix_CreateFromInput（）;
//求稀疏矩阵M的转置矩阵T
intTSMatrix_FastTranspose（TSMatrixM,TSMatrix*T）;
//如果稀疏矩阵M和N的行数的列数相同，计算Q=M+N
intTSMatrix_Add（TSMatrixM,TSMatrixN,TSMatrix*Q）;
//如果稀疏矩阵M的列数等于N的行数，计算Q=MxN;
intTSMatrix_Multply（TSMatrixM,TSMatrixN,TSMatrix*Q）;
//把光标位置移动到该行行首
voidResetCursor（）;
/*-----------程序主函数--------------------*/
intmain（void）
{
intinfo;
charch;
//从一个二维数组创建一个系数矩阵
TSMatrix*M;
TSMatrix*N;
//用来接收运算结果的空间
TSMatrix*T=（TSMatrix*）malloc（sizeof（TSMatrix））;
while
（1）
{
fflush（stdin）;
system（"cls"）;
printf（"稀疏矩阵基本操作演示\n"）;
printf（"1.矩阵的创建和转置\n"）;
printf（"2.矩阵的加法运算并以三元组输出结果\n"）;
printf（"3.矩阵的乘法运算并以矩阵输出结果\n"）;
printf（"\n"）;
printf（"Q.退出程序\n"）;
printf（"\n"）;
printf（"请输入选项：
"）;
scanf（"%c",&ch）;
switch（ch）
{
case'1':
system（"cls"）;
M=TSMatrix_CreateFromInput（）;
if（M!
=NULL）
{
printf（"\n\n以三元组输出稀疏矩阵：
\n"）;
TSMatrix_PrintTriple（M）;
printf（"\n倒置后稀疏矩阵的三元组输出：
\n"）;
TSMatrix_FastTranspose（*M,T）;
TSMatrix_PrintTriple（T）;
system（"pause"）;
}
else
{
printf（"创建矩阵过程发生错误"）;
system（"pause"）;
}
break;
case'2':
system（"cls"）;
M=TSMatrix_CreateFromInput（）;
N=TSMatrix_CreateFromInput（）;
if（M==NULL||N==NULL）
{
printf（"创建矩阵过程中发生错误！
\n"）;
system（"pause"）;
break;
}
info=TSMatrix_Add（*M,*N,T）;
if（info==MATRIX_NOT_MATCH）
{
printf（"这两个矩阵不能运算呢！
！
⊙﹏⊙\n"）;
}
elseif（info==OK）
{
printf（"\n运算结果：
\n"）;
TSMatrix_PrintTriple（T）;
}
system（"pause"）;
break;
case'3':
system（"cls"）;
M=TSMatrix_CreateFromInput（）;
N=TSMatrix_CreateFromInput（）;
if（M==NULL||N==NULL）
{
printf（"创建矩阵过程中发生错误！
\n"）;
system（"pause"）;
break;
}
info=TSMatrix_Multply（*M,*N,T）;
if（info==MATRIX_NOT_MATCH）
{
printf（"这两个矩阵不能运算呢！
！
⊙﹏⊙\n"）;
}
elseif（info==OK）
{
printf（"\n运算结果：
\n"）;
TSMartix_PrintMatrix（T）;
}
system（"pause"）;
break;
case'q':
case'Q':
exit（0）;
}
}
return0;
}
//初始化稀疏矩阵结构
intTSMatrix_Init（TSMatrix*M）
{
M->data=（Triple*）malloc（MAXSIZE*sizeof（Triple））;
if（!
M->data）
returnMALLOC_FAIL;
M->num=0;
M->colnum=0;
M->rownum=0;
returnOK;
}
//从一个二维数组创建一个稀疏矩阵
TSMatrix*TSMatrix_Create（int*a,introw,intcol）
{
inti,j;
TSMatrix*P=（TSMatrix*）malloc（sizeof（TSMatrix））;
TSMatrix_Init（P）;
//设置稀疏矩阵的行数和列数
P->rownum=row;
P->colnum=col;
for（i=0;i{
for（j=0;j{
//如果第i+1行第i+1列元素是非零元素
if（0!
=*（a+i*col+j））
{
//把非零元的元素和位置信息保存到稀疏矩阵中
P->data[P->num].e=*（a+i*col+j）;
P->data[P->num].row=i+1;
P->data[P->num].col=j+1;
//把稀疏矩阵中的非零元个数加一
P->num++;
}
}
}
returnP;
}
//以三元组的方式输出稀疏矩阵
voidTSMatrix_PrintTriple（TSMatrix*M）
{
inti;
if（0==M->num）
{
printf（"稀疏矩阵为空！
\n"）;
return;
}
printf（"ijv\n"）;
printf（"===============\n"）;
for（i=0;inum;i++）
{
printf（"%3d%3d%3d\n",M->data[i].row,M->data[i].col,M->data[i].e）;
}
printf（"===============\n"）;
}
//求稀疏矩阵M的转置矩阵T
intTSMatrix_FastTranspose（TSMatrixM,TSMatrix*T）
{
int*num,*cpot,i,t;
//如果矩阵M为空矩阵，返回错误信息
if（M.num==0）
returnEMPTY_MATRIX;
//分配临时的工作空间
num=（int*）malloc（（M.colnum+1）*sizeof（int））;
cpot=（int*）malloc（（M.colnum+1）*sizeof（int））;
//如果临时的工作空间分配不成功
if（num==NULL||cpot==NULL）
returnMALLOC_FAIL;
//初始化临时工作空间（把num数组用0填充）
for（i=1;i<=M.rownum;i++）
num[i]=0;
//统计倒置后每行的元素数量（即统计倒置前矩阵每列元素的数量）
for（i=1;i<=M.num;i++）
num[M.data[i-1].col]++;
//设置T矩阵每行首个非零元的位置
cpot[1]=0;
for（i=2;i<=M.colnum;i++）
cpot[i]=cpot[i-1]+num[i-1];
//把T矩阵的信息清空
TSMatrix_Init（T）;
//把矩阵M的信息填充到T中。
//矩阵倒置以后，T的行数等于M的列数，T的列数等于M的行数
T->num=M.num;
T->colnum=M.rownum;
T->rownum=M.colnum;
//对M矩阵中每个非零元素进行转置操作
for（i=0;i{
t=cpot[M.data[i].col];
T->data[t].col=M.data[i].row;
T->data[t].row=M.data[i].col;
T->data[t].e=M.data[i].e;
++cpot[M.data[i].col];
}
//转置完成后释放临时工作空间
free（num）;
free（cpot）;
returnOK;
}
//如果稀疏矩阵M和N的行数的列数相同，计算Q=M+N
intTSMatrix_Add（TSMatrixM,TSMatrixN,TSMatrix*Q）
{
inti=0,j=0,k=0;
if（M.colnum!
=N.colnum||M.rownum!
=N.rownum）
returnMATRIX_NOT_MATCH;
//填充结果矩阵信息
TSMatrix_Init（Q）;
Q->colnum=M.colnum;
Q->rownum=M.rownum;
Q->num=0;
while（i{
//如果ij指向元素是同一行的元素
if（M.data[i].row==N.data[j].row）
{
//如果i和j指向的元素指向的是同一个元素
if（M.data[i].col==N.data[j].col）
{
Q->data[k].row=M.data[i].row;
Q->data[k].col=M.data[i].col;
Q->data[k].e=M.data[i].e+N.data[j].e;
Q->num++;
i++;
j++;
k++;
}
//如果i指向元素的列下标大于j指向元素的列下标
//把下标小（j指向的元素）的放入到Q矩阵中
elseif（M.data[i].col>N.data[j].col）
{
Q->data[k].row=N.data[j].row;
Q->data[k].col=N.data[j].col;
Q->data[k].e=N.data[j].e;
Q->num++;
j++;
k++;
}
//如果i指向元素的列下标小于j指向元素的列下标
//把下标小（i指向的元素）的放入到Q矩阵中
elseif（M.data[i].col{
Q->data[k].row=M.data[i].row;
Q->data[k].col=M.data[i].col;
Q->data[k].e=M.data[i].e;
Q->num++;
i++;
k++;
}
}
//如果i指向的元素行下标大于j指向元素的行下标
elseif（M.data[i].row>N.data[j].row）
{
Q->data[k].row=N.data[j].row;
Q->data[k].col=N.data[j].col;
Q->data[k].e=N.data[j].e;
Q->num++;
k++;
j++;
}
//如果i指向元素行下标小于j指向元素的行下标
elseif（M.data[i].row{
Q->data[k].row=M.data[i].row;
Q->data[k].col=M.data[i].col;
Q->data[k].e=M.data[i].e;
Q->num++;
i++;
k++;
}
}
//如果还有剩余元素，按顺序把元素添加到结果矩阵中
while（i{
Q->data[k].row=M.data[i].row;
Q->data[k].col=M.data[i].col;
Q->data[k].e=M.data[i].e;
Q->num++;
i++;
k++;
}
while（j{
Q->data[k].row=N.data[j].row;
Q->data[k].col=N.data[j].col;
Q->data[k].e=N.data[j].e;
Q->num++;
j++;
k++;
}
returnOK;
}
//如果稀疏矩阵M的列数等于N的行数，计算Q=MxN;
intTSMatrix_Multply（TSMatrixM,TSMatrixN,TSMatrix*Q）
{
int*num_m,*cpot_m,*num_n,*cpot_n,i,j,k,s,col;
inta,ri,rj;
//如果两个矩阵不满足矩阵相乘的条件，返回错误信息
if（M.colnum!
=N.rownum）
returnMATRIX_NOT_MATCH;
//分配临时空间
num_m=（int*）malloc（（M.rownum+1）*sizeof（int））;
cpot_m=（int*）malloc（（M.rownum+1）*sizeof（int））;
num_n=（int*）malloc（（N.rownum+1）*sizeof（int））;
cpot_n=（int*）malloc（（N.rownum+1）*sizeof（int））;
//填充结果矩阵的信息
TSMatrix_Init（Q）;
Q->rownum=M.rownum;
Q->colnum=N.colnum;
Q->num=0;
//如果相乘为零矩阵，直接返回
if（0==M.num*N.num）
returnOK;
//初始化临时空间
for（i=1;i<=M.colnum;i++）
num_m[i]=0;
for（i=1;i<=N.colnum;i++）
num_n[i]=0;
//计算矩阵每行非零元元素的数量
for（i=0;inum_m[M.data[i].row]++;
for（i=0;inum_n[N.data[i].row]++;
cpot_m[1]=cpot_n[1]=0;
for（i
升级会员 