实验七
稀疏矩阵的实现基本操作
班级:1208341
4学号:1208141
1 姓名:陈峰
一、实验内容
(1) 掌握稀疏矩阵的压缩存储; (2) 掌握稀疏矩阵的转置算法;
二、实验目的
(1) 实现上三角阵的压缩存储;
(2) 用三元组书序表存储稀疏矩阵,并实现矩阵的转置;
三、设计思想
(1) 创建一个数组; (2) 输入数据;
(3) 给定矩阵任一元素的下标; (4) 打印给定下标所对应的数据; (5) 创建三元组顺序表; (6) 输入矩阵中的数据; (7) 输出对应的矩阵;
四、程序源代码
(1) 三元组顺序表存储稀疏矩阵并实现矩阵的转置;
#include #include
# define MAXSIZE 100 # define MAXRC 10
struct Triple {
int i,j;
/*该非零元的行下标和列下标*/
int e; }; struct TSMtrix {
struct Triple data[MAXSIZE+1];
/*非零元三元组表,data[0]未用*/
int rpos[MAXRC+1];
/*各行第一个非零元的位置表*/
int cpos[MAXRC+1];
/*各列第一个非零元的位置表*/
int num[MAXRC+1];
/*各列非零元的个数*/
int mu,nu,tu;
/*矩阵的行数、列数和非零元个数*/ };
void CreateMtrix(struct TSMtrix *M) { /*创建一个稀疏矩阵*/
int i,elem,col,row,mu,nu,tu;
printf(\"please input matrix col,row,unzeroed numbers:\\n\");
scanf(\"%d%d%d\",&mu,&nu,&tu);
M->mu=mu;
M->nu=nu;
M->tu=tu;
for (i=1;i
{
printf(\"please input element col,row,value:\\n\");
scanf(\"%d%d%d\",&col,&row,&elem);
if ( muM->mu || nu>M->nu)
{
printf(\"error!\");
i--;
}
else
{
M->data[i].i=col;
M->data[i].j=row;
M->data[i].e=elem;
}
} }
void ShowMtrix(struct TSMtrix M) { /*打印出矩阵*/
int i=1,j=1,dir=1;
printf(\"The matrix is:\\n\");
for (i=1;i
{
for (j=1;j
{
if (M.data[dir].i==i && M.data[dir].j==j)
{
printf(\"%d
\",M.data[dir].e);
/*存在非零元*/
dir++;
}
else
printf(\"0
\");
}
printf(\"\\n\");
} }
void FastTransposeSMtrix(struct TSMtrix M,struct TSMtrix *T) { /*矩阵的快速转置*/
int t=1,p=1,q,col=M.nu;
T->mu=M.mu;
T->nu=M.nu;
T->tu=M.tu;
if (T->tu)
{
for (col=1;col
M.num[col]=0;
for (t=1;t
++M.num[M.data[t].j];
M.cpos[1]=1;
/*找到M中cpos的位置*/
for (col=2;col
M.cpos[col]=M.cpos[col-1]+M.num[col-1];
for (p=1;p
{
col=M.data[p].j;
q=M.cpos[col];
T->data[q].i=M.data[p].j;
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e;
++M.cpos[col];
}
} }
main() {
struct TSMtrix M;
struct TSMtrix N;
CreateMtrix(&M);
ShowMtrix(M);
printf(\"\\n\");
FastTransposeSMtrix(M,&N);
ShowMtrix(N);
getch(); }
(2) 实现矩阵的经典转置算法并测试;
#include #include #define maxsize 1200 #define Elemtype int //该结构体中存的是数组data[maxsize+1]中的元素的值和行标和列标//
typedef struct { int i,j; Elemtype e; }te;
typedef struct { te data[maxsize+1]; //存储非0元素的数组,该数组是从1开始,所以下面的p从等于1开始// int mu,nu,tu; //mu 表示行数,nu 表示列数,tu 表示该矩阵中非0的个数// }tx;
//向矩阵中输入元素 int intput(tx &a) {
int row,col,p=1; //row 表示元素的行标,col 表示元素的列标,p表示非0元素的计数器//
int temp;
printf(\"请输入矩阵行数:\");
scanf(\"%d\",&a.mu);
printf(\"请输入矩阵列数:\");
scanf(\"%d\",&a.nu);
printf(\"请输入原始矩阵的每行每列元素:\\n\");
for(row=1;row
for(col=1;col
{
scanf(\"%d\",&temp);
if(temp!=0)
{
a.data[p].i=row;
a.data[p].j=col;
a.data[p].e=temp;
p++;
}
a.tu=p;
}
printf(\"\\n\");
}
return 0; }
//输出上面的矩阵
int output(tx &a) {
int row,col;
int p=1;
printf(\"输出原始矩阵:\\n\");
for(row=1;row
{
for(col=1;col
{
if(row==a.data[p].i && col==a.data[p].j)
{
printf(\"\\t%d\",a.data[p].e);
p++;
}
else
//剩余的输出0//
printf(\"\\t%d\",0);
}
printf(\"\\n\"); //换行符的位置//
}
return 0; }
//定义了一个新的矩阵b// int transpose(tx a,tx &b)
{
int row,col;
//找出非0元素//
int p,q=1;
b.mu=a.nu; //矩阵b的行数等于矩阵a的列数//
b.nu=a.mu; //矩阵b的列数等于矩阵a的行数//
b.tu=a.tu; //非0元素的个数///
if(a.tu!=0) //判断是否有非0元素// {
//双重循环//
for(col=1;col
// 该循环是以列循环目的是:把非0元素中列标小的元素从头排列//
{
for(p=1;p
if(a.data[p].j==col)
//循环非0数组中的元素,并找出a.data[p].j等于当时的a矩阵在中的col// { //把矩阵a中非0元素的行标和列标等于矩阵b非0元素的列标和行标//
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].e=a.data[p].e;
q++;
} }
}
printf(\"\\n\");
}
return 0; }
//输出转置后的矩阵
int outputtranspose(tx &b) {
int q=1;
int row,col;
printf(\"输出转置后的矩阵:\\n\");
for(row=1;row
{
for(col=1;col
{
if(row==b.data[q].i && col==b.data[q].j) //找出b矩阵非0元素//
{
printf(\"\\t%d\",b.data[q].e);
q++;
}
else
printf(\"\\t%d\",0); //剩余的输出0//
}
printf(\"\\n\");
}
return 0; }
void main() { tx a,b; intput(a); output(a); transpose(a,b); outputtranspose(b); }
五、调试及测试数据
(1) 三元组顺序表存储稀疏矩阵并实现矩阵的转置;
(2) 实现矩阵的经典转置算法并测试;
六、实验总结
在本实验中,老师给出了“三元组顺序表存储稀疏矩阵并实现矩阵的转置”的完整实验代码供我们参考。通过对参考例子的代码的理解,看懂之后程序代码之后就能比较轻松地写出题目的代码。在本次实验中能够清楚的知道要做什么,从哪里开始做,怎么做,思路很清晰。经过编程,学会了串的操作与实现,并且对C++也有了新的认识。