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

实验五 数组的运算实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。实验内容与要求：设计一个稀疏矩阵计算器，要求能够：输入并建立稀疏矩阵；输出稀疏矩阵；执行两个矩阵相加；求一个矩阵的转置矩阵。程序代码：#include#define smax 20typedef int datatype; typedef struct int i,j; datatype v; node;typedef struct node datasmax; 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.data0.i,&a.data0.j,&a.data0.v); while(a.datak.v!=0)以0元素作为结束标志，因为稀疏矩阵不包含0元素 k+; scanf(%d,%d,%d,&a.datak.i,&a.datak.j,&a.datak.v); printf(输出的稀疏矩阵是：n); printf(%d,%d,%dn,a.m,a.n,a.t); for(k=0;ka.t;k+)一维数组思想，用for循环简单 printf(%d,%d,%dn,a.datak.i,a.datak.j,a.datak.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.data0.i,&a.data0.j,&a.data0.v); while(a.datak.v!=0) k+; scanf(%d,%d,%d,&a.datak.i,&a.datak.j,&a.datak.v); for(k=0;ka.t;k+)行列交换即可，但没有进行排序输出 p=a.datak.i;a.datak.i=a.datak.j;a.datak.j=p; printf(输出转置后的初步矩阵元素：n); for(k=0;ka.t;k+) printf(%d,%d,%dn,a.datak.i,a.datak.j,a.datak.v); for(p=0;pa.t;p+)冒泡排序法，对转置后的稀疏矩阵进行重新排序 for(k=0;ka.datak+1.i | (a.datak.i=a.datak+1.i & a.datak.ja.datak+1.j) q=a.datak.i;a.datak.i=a.datak+1.i;a.datak+1.i=q; q=a.datak.j;a.datak.j=a.datak+1.j;a.datak+1.j=q; q=a.datak.v;a.datak.v=a.datak+1.v;a.datak+1.v=q; printf(输出转置后的稀疏矩阵:n); printf(%d,%d,%dn,a.n,a.m,a.t); for(k=1;k(a.t+1);k+)此处下标加1是根据输出结果判定而来，不知道原因 printf(%d,%d,%dn,a.datak.i,a.datak.j,a.datak.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.data0.i,&a.data0.j,&a.data0.v); while(a.datax.v!=0) x+; scanf(%d,%d,%d,&a.datax.i,&a.datax.j,&a.datax.v); printf(请输入稀疏矩阵b:n); scanf(%d,%d,%d,&b.m,&b.n,&b.t); scanf(%d,%d,%d,&b.data0.i,&b.data0.j,&b.data0.v); while(a.datay.v!=0) y+; scanf(%d,%d,%d,&b.datay.i,&b.datay.j,&b.datay.v); 以上为重新创建两个稀疏矩阵，方便运算 if(a.m=b.m & a.n=b.n)首先行列相等的稀疏矩阵才能相加 for(x=0;xa.t;x+) c.dataz.i=a.datax.i; c.dataz.j=a.datax.j; c.dataz.v=a.datax.v; z+; for(y=0;ya.t;y+) c.dataz.i=b.datay.i; c.dataz.j=b.datay.j; c.dataz.v=b.datay.v; z+; 两个for循环先后把a,b两个稀疏矩阵元素放到一个新的稀疏矩阵c里去 printf(输出结合后的初步稀疏矩阵C的元素:n);进行一次打印 for(z=0;z(a.t+b.t);z+) printf(%d,%d,%dn,c.dataz.i,c.dataz.j,c.dataz.v); for(p=0;p(a.t+b.t);p+)冒泡排序法对新矩阵元素排序 for(z=0;zc.dataz+1.i | (c.dataz.i=c.dataz+1.i & c.dataz.jc.dataz+1.j)有这几种情况需要重新排序，首先是进行行对比（前行大于后行进行交换），然后当行相等时在进行列对比（前列大于后列时在进行交换），其他情况均不用交换 q=c.dataz.i;c.dataz.i=c.dataz+1.i;c.dataz+1.i=q; q=c.dataz.j;c.dataz.j=c.dataz+1.j;c.dataz+1.j=q; q=c.dataz.v;c.dataz.v=c.dataz+1.v;c.dataz+1.v=q; printf(输出排序后的稀疏矩阵C的元素:n);进行一次打印 for(z=1;z(a.t+b.t+1);z+) printf(%d,%d,%dn,c.dataz.i,c.dataz.j,c.dataz.v); for(z=1;z(a.t+b.t+1-r);z+)主循环，保证阅读每一个数组元素 if(c.dataz.i=c.dataz+1.i & c.dataz.j=c.dataz+1.j) 在对排好序后的矩阵进行相等行列元素的合并 c.dataz.v=c.dataz.v+c.dataz+1.v; r+;此处是关键，记录此时的步骤，如果进行一次运算后，那么后面的循环就要少一次，包括再回到主循环时也要少一次 for(z+1;(z+1)(a.t+b.t+1-r);z+)小循环是让后面的每一个数组元素向前移动一个位置，掩盖掉相等行列元素 c.dataz+1.i=c.dataz+2.i; c.dataz+1.j=c.dataz+2.j; c.dataz+1.v=c.dataz+2.j; printf(输出最终结果的稀疏矩阵C:n); printf(%d,%d,%dn,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,%dn,c.dataz.i,c.dataz.j,c.dataz.v); Else给出稀疏矩阵表开头行列总和不等时则无法计算 printf(输入的稀疏矩阵a,b不是行列相等的矩阵。n);void main()主函数spmatrix a,b; creat(a); transpose(a); add(a,b);心得体会：程序开头老