数据结构稀疏矩阵应用

实验五 数组的运算

实验目的：

掌握稀疏矩阵的压缩存储方法及主要运算的实现。

实验内容与要求：

设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷求一个矩阵的转置矩阵。

程序代码：

#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);