实验7 数据结构_数据结构实验七
实验7 数据结构由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验七”。
实验七
稀疏矩阵的实现基本操作
班级：1208341
4学号：1208141姓名：陈峰
一、实验内容
（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++也有了新的认识。
