稀疏矩阵的建立与转置.doc

实验2 稀疏矩阵的建立与转置

一、实验目的
掌握特殊矩阵的存储和操作算法。
二、实验内容及问题描述
实现用三元组保存稀疏矩阵并实现矩阵转置的算法。
三、实验步骤
1. 定义稀疏矩阵的三元组形式的存储结构。
2. 实现三元组矩阵的传统转置算法。
3. 实现三元组矩阵的快速转置算法。
4. 输入矩阵非零元素，测试自己完成的算法。
四、程序流程图

五、概要设计
矩阵是很多的科学与工程计算中研究的数学对象。在此，我们感兴趣的是，从数学结构这门学科着眼，如何存储矩阵的元从而使矩阵的各种运算有效的进行。 本来，用二维数组存储矩阵，在逻辑上意义是很明确的，也很容易理解，操作也很容易和方便。但是在数值分析中经常出现一些阶数很高的矩阵，同时，在矩阵中又有很多值相同或者都为零的元素，可以对这种矩阵进行压缩存储：对多个值相同的元素只分配一个存储空间；对零元素不分配空间。稀疏矩阵的定义是一个模糊的定义：即非零元个数较零元个数较少的矩阵。例如下图所示的矩阵

为一个稀疏矩阵。 为了实现稀疏矩阵的这种存储结构，引入三元组这种数据结构。三元组的线性表顺存储形式如下图：

六、详细设计
sanyuanzu.h 头文件
#define max 100
typedef struct
{
int row,col;
int e;
}Triple;//定义三元组
typedef struct
{
Triple data[max];
int mu,nu,tu;
}TSMatrix;///*定义三元组的稀疏矩阵*/
void creat( TSMatrix &M) ;
void fasttrans(TSMatrix A,TSMatrix &B);
void printfx(TSMatrix x);
sanyuanzu.cpp 文件
#include<stdio.h>
#include"sanyuanzu.h"
/*建立三元组的稀疏矩阵*/
void creat( TSMatrix &M)
{
printf("请输入稀疏矩阵的行数：");
scanf("%d",&M.mu);
printf("请输入稀疏矩阵的列数：");
scanf("%d",&M.nu);
printf("请输入矩阵中非零元素的个数：");
scanf("%d",&M.tu);
int i;
printf("请输入这%d 个元素的行号和列号及其元素的值：/n",M.tu);
for(i = 1; i <= M.tu; i++)scanf("%d %d %d",&M.data[i].row,&M.data[i].col,&M.data[i].e);
}
/*实现三元组的矩阵转置的函数*/
void fasttrans(TSMatrix A,TSMatrix &B)
{
int col,cpot[max],num[max],t,p,q;
/*初始化矩阵B*/
B.mu=A.nu;
B.nu=A.mu;
B.tu=A.tu;
if(B.tu)
{
for(col=1;col<=A.nu;++col)
num[col]=0;/*初始化每一列非零元的个数*/
for(t=1;t<=A.tu;++t)
++num[A.data[t].col];/*计算每一列非零元的个数*/
cpot[1]=1;
for(col=2;col<=A.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];//计算矩阵A 每一列第一个非零元在B.data 中的位置
/*实现对A 中的每一个非零元进行转置*/
for(p=1;p<=A.tu;++p)
{
col=A.data[p].col;
q=cpot[col];
B.data[q].row=A.data[p].col;
B.data[q].col=A.data[p].row;
B.data[q].e=A.data[p].e;
++cpot[col];
}
}
}
/*稀疏矩阵的输出*/
void printfx(TSMatrix x)
{
int i,j;
for(j=1;j<=x.tu;j++)
{
for(i=1;i<=x.mu;i++)
if(x.data[j].row==i)printf("%d %d %d/n",x.data[j].row,x.data[j].col,x.data[j].e);
}
}

main.cpp 文件
#include<stdio.h>
#include'"sanyuanzu.cpp"
//主函数
int main(void)
{
TSMatrix t,s;
creat(t);
printf("你所输入的稀疏矩阵为:/n");
printfx(t);
fasttrans(t,s);
printf("转置后的稀疏矩阵为:/n");
printfx(s);
return 0;
}
}
七、调试报告

八、分析与遇到的问题
（1） 创建稀疏矩阵时，不懂如何用三元组表示元素的输出；
（2）需要注意矩阵运算中的特殊状况，
稀疏矩阵相加时，忘记对应元素相加为0时，在稀疏矩阵中不表示；
（3） 矩阵相加时，第一个矩阵的行列数要和第二个矩阵的行列数相等；
（4）输出矩阵时，输出界面不整齐。
九、 用户使用说明
（1） 运行程序，首先会看到一个提供选择的界面，输入相应的序号实现相应的功能；
（2） 在进行相应的功能之后按提示要求一三元组形式输入相应矩阵。（注意：每个数据之间用空格隔开）；
（3） 输入相应矩阵之后会输出最后的运算结果；
（4） 输出结果运算之后会可按任意键返回。

十、 心得体会
这次数据结构课程设计的制作使我对数据结构和C语言的理解加深，也使我自己认识到自己很多不足之处。我发现自己再处理稍微具体的程序时显得无从下手以前学习的知识只是理论性的知识，并没有真正实践过，当我通过网上查询、复习知识后才对编程程序有了初步思路。后来编写程序时也碰到了许多错误，我对于指针的掌握程度较差导致我再使用时产生了很多错误请教了老师和同学才逐步完成。这次实验使我认识到要想做成一个完整的程序绝对不是简单的事。我明白了无论是是做什么我们搜必须按部就班的从点滴做起，逐步完成。

5