实验报告 矩阵快速转置
- 格式：doc
- 大小：91.50 KB
- 文档页数：6
实验报告
实验项目名称：实现矩阵的快速
转置的操作
所属课题名称：数据结构
实验类型：验证实验
实验日期：2010/12/20
学院：数学与信息科学学院
专业: 信息与计算科学
班级: 082班
姓名：李晓璐
学号：0801214037
实验稀疏矩阵的快速转置操作
一、实验目的
1、了解稀疏矩阵的三元组存储形式。
2、熟悉掌握三元表存储矩阵的转置算法。
二、实验环境
硬件：PC 微型计算机、256M以上内存，40G以上硬盘。
软件：Windows XP，Turbo C/C++
三、实验内容
转置运算是一种最简单的矩阵运算。
对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵。
假设a和b是TSMatrix型的变量，分别表示矩阵M和T。
按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。
实现由a得到b的方式如下。
在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。
在此，设num和cpot两个向量，num[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中应有的位置。
显然有：
cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]
四、实验步骤
1、本实验的程序清单如下。
“TSMatrix.h”
#define MAXSIZE 12500
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW 0
typedef int Status;
typedef int ElemType;
struct Triple
{
int i,j;
ElemType e;
};
class TSMatrix
{
public:
TSMatrix(){mu=0;nu=0;tu=0;};
TSMatrix(int,int,int);
~TSMatrix(){};
void setTSMatrix();
Status PrintSMatrix();
Status TransposeSMatrix(TSMatrix &T);
Status FastTransposeSMatrix(TSMatrix &T);
private:
Triple data[MAXSIZE+1];
int mu,nu,tu;
};
TSMatrix::TSMatrix(int a,int b,int c)
{
mu=a;nu=b;tu=c;
for(int p=1;p<=tu;p++)
{
printf("依次输入稀疏矩阵第%d个非零元的行号,列号,元素:",p);
scanf("%d,%d,%d",&data[p].i,&data[p].j,&data[p].e);
}
}
void TSMatrix::setTSMatrix()
{
cout<<"输入矩阵的行数:";
cin>>mu;
cout<<"输入矩阵的列数:";
cin>>nu;
cout<<"输入矩阵的非零元个数:";
cin>>tu;
for(int p=1;p<=tu;p++)
{
printf("依次输入稀疏矩阵第%d个非零元的行号,列号,元素:",p);
scanf("%d,%d,%d",&data[p].i,&data[p].j,&data[p].e);
}
}
Status TSMatrix::PrintSMatrix()
{
int k=1,t=0;
for(int p=1;p<=mu;p++)
{
for(int q=1;q<=nu;q++)
{
if(p==data[k].i&&q==data[k].j&&k<=tu)
{
cout.width(3);
cout.setf(ios::left);
cout<<data[k].e;
cout.unsetf(ios::left);
k++;
}
else
{
cout.width(3);
cout.setf(ios::left);
cout<<t;
cout.unsetf(ios::left);
}
}
cout<<endl;
}
return OK;
}
Status TSMatrix::TransposeSMatrix(TSMatrix &T)
{
int col,p,q;
T.mu=nu;
T.nu=mu;
T.tu=tu;
if(T.tu)
{
q=1;
for(col=1;col<=nu;++col)
for(p=1;p<=tu;++p)
if(data[p].j==col)
{
T.data[q].i=data[p].j;
T.data[q].j=data[p].i;
T.data[q].e=data[p].e;
++q;
}
}
return OK;
}
Status TSMatrix::FastTransposeSMatrix(TSMatrix &T)
int col,p,q,t;
int *num=new int[10],*cpot=new int[10];
num=(int*)malloc(tu*sizeof(int));
cpot=(int*)malloc(tu*sizeof(int));
T.mu=nu;
T.nu=mu;
T.tu=tu;
if(T.tu)
{
for(col=1;col<=nu;++col) num[col]=0;
for(t=1;t<=tu;++t) ++num[data[t].j];
cpot[1]=1;
for(col=2;col<=nu;++col)cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=tu;++p)
{
col=data[p].j;
q=cpot[col];
T.data[q].i=data[p].j;
T.data[q].j=data[p].i;
T.data[q].e=data[p].e;
++cpot[col];
}
}
return OK;
}
“TSMstrixMain.cpp”
#include"iostream"
using namespace std;
#include"TSMatrix.h"
int main()
{
TSMatrix M,T;
cout<<"输出稀疏矩阵:"<<endl;
M.setTSMatrix();
M.PrintSMatrix();
M.TransposeSMatrix(T);
cout<<"输出经过转置后的稀疏矩阵:"<<endl;
T.PrintSMatrix();
M.FastTransposeSMatrix(T);
cout<<"输出经过快速转置后的稀疏矩阵:"<<endl;
T.PrintSMatrix();
return 0;
2、本程序运行的结果如下
五、实验小结
这次数据结构课程设计的制作使我对数据结构和C语言的理解更加深刻，也使我认识到了自己很多不足之处。
我发现自己在处理稍微具体的程序时显得无从下手，以前学习的知识只是理论性的知识，并没有真正实践过，当我通过网上查询、请教学生老师、复习知识后才对编写程序有了初步的思路。
后来编写程序时也碰到了许多错误，我对于指针的掌握程度较差导致了我在使用的时候产生了很多错误，请教了学习较好的同学后才逐步完成。
最后还有很多细节方面难以修改，于是就改进算法，使自己的程序有了雏形。
这次程序设计使我认识到，要做成编写一个完整的程序绝对不是一件简单的事情，不单要掌握基础知识更要勇于实践，不单要舍得花费时间更要用心去完成它。
无论是编写程序还是完成现实生活中的其他事情，我们都必须按部就班地从点滴做起，逐步完成。
不但要完成更要做到尽善尽美。
学习数据结构的历程不会因为完成本次课程设计而停止，我是为了用知识武装大脑而学习，通过学习充实自己的生活，我一定会努力学习，争取以后能够完成规模更大的程序。
