数据结构稀疏矩阵应用.doc

实验五 数组的运算
实验目的：
掌握稀疏矩阵的压缩存储方法及主要运算的实现。
实验内容与要求：
设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷求一个矩阵的转置矩阵。
程序代码：
#include<stdio.h>
#define smax 20
typedef int datatype;
typedef struct
{ int i,j;
datatype v;
}node;
typedef struct
{ node data[smax];
int m,n,t;
}spmatrix;

void creat(spmatrix a)\\创建输出稀疏矩阵
{ int k=0;
printf("请输入稀疏矩阵：\n");
scanf("%d,%d,%d",&a.m,&a.n,&a.t);
scanf("%d,%d,%d",&a.data[0].i,&a.data[0].j,&a.data[0].v);
while(a.data[k].v!=0)\\以0元素作为结束标志，因为稀疏矩阵不包含0元素
{k++;
scanf("%d,%d,%d",&a.data[k].i,&a.data[k].j,&a.data[k].v);
}
printf("输出的稀疏矩阵是：\n");
printf("%d,%d,%d\n",a.m,a.n,a.t);
for(k=0;k<a.t;k++)\\一维数组思想，用for循环简单
printf("%d,%d,%d\n",a.data[k].i,a.data[k].j,a.data[k].v);
printf("\n");
}

void transpose(spmatrix a)\\转置函数
{ int p,q,k=0;
printf("请输入稀疏矩阵：\n");
scanf("%d,%d,%d",&a.m,&a.n,&a.t);
scanf("%d,%d,%d",&a.data[0].i,&a.data[0].j,&a.data[0].v);
while(a.data[k].v!=0)
{k++;
scanf("%d,%d,%d",&a.data[k].i,&a.data[k].j,&a.data[k].v);
}
for(k=0;k<a.t;k++)\\行列交换即可，但没有进行排序输出
{p=a.data[k].i;a.data[k].i=a.data[k].j;a.data[k].j=p;}
printf("输出转置后的初步矩阵元素：\n");
for(k=0;k<a.t;k++)
printf("%d,%d,%d\n",a.data[k].i,a.data[k].j,a.data[k].v);
for(p=0;p<a.t;p++)\\冒泡排序法，对转置后的稀疏矩阵进行重新排序
for(k=0;k<(a.t-p);k++)
{if(a.data[k].i>a.data[k+1].i || (a.data[k].i==a.data[k+1].i && a.data[k].j>a.data[k+1].j))
{q=a.data[k].i;a.data[k].i=a.data[k+1].i;a.data[k+1].i=q;
q=a.data[k].j;a.data[k].j=a.data[k+1].j;a.data[k+1].j=q;
q=a.data[k].v;a.data[k].v=a.data[k+1].v;a.data[k+1].v=q;
}
}
printf("输出转置后的稀疏矩阵:\n");
printf("%d,%d,%d\n",a.n,a.m,a.t);
for(k=1;k<(a.t+1);k++)\\此处下标加1是根据输出结果判定而来，不知道原因
printf("%d,%d,%d\n",a.data[k].i,a.data[k].j,a.data[k].v);
printf("\n");
}

void add(spmatrix a,spmatrix b)\\求和函数
{spmatrix c;
int x=0,y=0,z=0;
int p,q,r=0;
printf("请输入稀疏矩阵a:\n");
scanf("%d,%d,%d",&a.m,&a.n,&a.t);
scanf("%d,%d,%d",&a.data[0].i,&a.data[0].j,&a.data[0].v);
while(a.data[x].v!=0)
{x++;
scanf("%d,%d,%d",&a.data[x].i,&a.data[x].j,&a.data[x].v);
}
printf("请输入稀疏矩阵b:\n");
scanf("%d,%d,%d",&b.m,&b.n,&b.t);
scanf("%d,%d,%d",&b.data[0].i,&b.data[0].j,&b.data[0].v);
while(a.data[y].v!=0)
{y++;
scanf("%d,%d,%d",&b.data[y].i,&b.data[y].j,&b.data[y].v);
}\\以上为重新创建两个稀疏矩阵，方便运算
if(a.m==b.m && a.n==b.n)\\首先行列相等的稀疏矩阵才能相加
{for(x=0;x<a.t;x++)
{c.data[z].i=a.data[x].i;
c.data[z].j=a.data[x].j;
c.data[z].v=a.data[x].v;
z++;
}
for(y=0;y<a.t;y++)
{c.data[z].i=b.data[y].i;
c.data[z].j=b.data[y].j;
c.data[z].v=b.data[y].v;
z++;
}\\两个for循环先后把a,b两个稀疏矩阵元素放到一个新的稀疏矩阵c里去
printf("输出结合后的初步稀疏矩阵C的元素:\n");\\进行一次打印
for(z=0;z<(a.t+b.t);z++)
printf("%d,%d,%d\n",c.data[z].i,c.data[z].j,c.data[z].v);

for(p=0;p<(a.t+b.t);p++)\\冒泡排序法对新矩阵元素排序
for(z=0;z<(a.t+b.t-p);z++)
{if(c.data[z].i>c.data[z+1].i || (c.data[z].i==c.data[z+1].i && c.data[z].j>c.data[z+1].j))\\有这几种情况需要重新排序，首先是进行行对比（前行大于后行进行交换），然后当行相等时在进行列对比（前列大于后列时在进行交换），其他情况均不用交换
{q=c.data[z].i;c.data[z].i=c.data[z+1].i;c.data[z+1].i=q;
q=c.data[z].j;c.data[z].j=c.data[z+1].j;c.data[z+1].j=q;
q=c.data[z].v;c.data[z].v=c.data[z+1].v;c.data[z+1].v=q;
}
}
printf("输出排序后的稀疏矩阵C的元素:\n");\\进行一次打印
for(z=1;z<(a.t+b.t+1);z++)
printf("%d,%d,%d\n",c.data[z].i,c.data[z].j,c.data[z].v);

for(z=1;z<(a.t+b.t+1-r);z++)\\主循环，保证阅读每一个数组元素
if(c.data[z].i==c.data[z+1].i && c.data[z].j==c.data[z+1].j) \\在对排好序后的矩阵进行相等行列元素的合并
{c.data[z].v=c.data[z].v+c.data[z+1].v;
r++;\\此处是关键，记录此时的步骤，如果进行一次运算后，那么后面的循环就要少一次，包括再回到主循环时也要少一次
for(z+1;(z+1)<(a.t+b.t+1-r);z++)\\小循环是让后面的每一个数组元素向前移动一个位置，掩盖掉相等行列元素
{c.data[z+1].i=c.data[z+2].i;
c.data[z+1].j=c.data[z+2].j;
c.data[z+1].v=c.data[z+2].j;
}
}
printf("输出最终结果的稀疏矩阵C:\n");
printf("%d,%d,%d\n",a.m,a.n,(a.t+b.t-r));\\输出稀疏矩阵表头时只需将行列元素交换输出即可，元素个数输出时要注意相等行列元素合并进行了几次操作，即用r记录操作步骤的次数，每进行一次操作那么最终稀疏矩阵就少一个数组元素，同时r又是伴随步骤增加的
for(z=1;z<(a.t+b.t+1-r);z++)\\原理同上
printf("%d,%d,%d\n",c.data[z].i,c.data[z].j,c.data[z].v);
}
Else\\给出稀疏矩阵表开头行列总和不等时则无法计算
printf("输入的稀疏矩阵a,b不是行列相等的矩阵。\n");
}

void main()\\主函数
{spmatrix a,b;
creat(a);
transpose(a);
add(a,b);
}

心得体会：程序开头老师指点了一下，后面的算法以及函数全为自己长时间编写，全用一维数组包含多个数据的思想去操作，抓住主的数组元素值的变化，步步为营，一个目标一个目标的实现，在操作时最好对这次操作结果做一次打印，就像程序中进行前后元素交换的时候主数组下标加1是为什么没有研究透，不过通过每步打印发现了这个规律，要不然找死都找不出结果为何少一个元素，开头元素为何是一串数字乱码。