试验7数据结构

1、实验七稀疏矩阵的实现基本操作班级：1 2083414 学号：12081411姓名：陈峰一、实验内容（1）掌握稀疏矩阵的压缩存储；（2）掌握稀疏矩阵的转置算法；二、实验目的（1）实现上三角阵的压缩存储；（2）用三元组书序表存储稀疏矩阵，并实现矩阵的转置;三、设计思想（1）创建一个数组；（2）输入数据；（3）给定矩阵任一元素的下标；（4）打印给定下标所对应的数据；（5）创建三元组顺序表；（6）输入矩阵中的数据；（7）输出对应的矩阵；四、程序源代码（1）三元组顺序表存储稀疏矩阵并实现矩阵的转置;#in elude <stdio.h>#in elude vconi o.h># def

2、ine MAXSIZE 100# define MAXRC 10 struct Tripleint i,j;/*该非零元的行下标和列下标*/int e;struct TSMtrixstruct Triple dataMAXSIZE+1;/* 非零元三元组表，data0未用*/int rposMAXRC+1;/*各行第一个非零元的位置表*/int cposMAXRC+1;/*各列第一个非零元的位置表*/int numMAXRC+1;/*各列非零元的个数*/int mu, nu,tu;/*矩阵的行数、列数和非零元个数*/;void CreateMtrix(struct TSMtrix *M)/*创

3、建一个稀疏矩阵*/int i,elem,col,row,mu, nu,tu;prin tf("please in put matrix col,row, un zeroed nu mbers:n"); scan f("%d%d%d",&mu,&nu,& tu);M->mu=mu;M->nu=nu;M->tu=tu;for (i=1;i<=tu;i+)prin tf("please in put eleme nt col,row,value:n");scan f("%d%d%d&

4、quot;,&col,&row,&elem);if ( mu<0 | n u<0 | mu>M->mu | nu>M-> nu)prin tf("error!");i-;elseM->datai.i=col;M->datai.j=row; M->datai.e=elem;void ShowMtrix(struct TSMtrix M)/*打印出矩阵*/int i=1,j=1,dir=1;prin tf("The matrix is:n");for (i=1;i<=M.mu

5、;i+)for (j=1;j<=M. nu;j+)if (M.datadir.i=i && M.datadir.j=j) /* 存在非零元 */ prin tf("%d ",M.datadir.e);dir+;elseprin tf("O");prin tf("n");void FastTra nsposeSMtrix(struct TSMtrix M,struct TSMtrix *T)/*矩阵的快速转置*/int t=1,p=1,q,col=M.nu;T->mu=M.mu;T->nu=M.nu;T

6、->tu=M.tu;if (T->tu)for (col=1;col<=M.nu ;col+)M.n umcol=0;for (t=1;t<=M. nu;t+)+M. nu mM.datat.j;M.cpos1=1;/*找到 M 中 cpos的位置 */for (col=2;col<=M.nu ;col+)M.cposcol=M.cposcol-1+M. numcol-1;for (p=1;p<=M.tu;p+)col=M.datap.j; q=M.cposcol;T->dataq.i=M.datap.j;T->dataq.j=M.datap.i

7、;T->dataq.e=M.datap.e;+M.cposcol;mai n()struct TSMtrix M;struct TSMtrix N;CreateMtrix(&M);ShowMtrix(M);prin tf("n");FastTra nsposeSMtrix(M,&N);ShowMtrix(N); getch();(2)实现矩阵的经典转置算法并测试；#in elude <stdio.h>#i nclude <stdlib.h>#defi ne maxsize 1200#define Elemtype int该结构体

8、中存的是数组 datamaxsize+1中的元素的值和行标和列标/typedef structint i,j;Elemtype e;te;typedef structte datamaxsize+1; 存储非0元素的数组，该数组是从1开始，所以 下面的p从等于1开始/int mu,nu,tu; /mu表示行数，nu表示列数，tu表示该矩阵中非0的个 数/tx;/向矩阵中输入元素int in tput(tx &a)int row,col,p=1; /row 表示元素的行标，col表示元素的列标， p 表示非0元素的计数器/int temp;printf("请输入矩阵行数：&qu

9、ot;);sca nf("%d",&a.mu);printf("请输入矩阵列数：");sca nf("%d",&a.nu);printf("请输入原始矩阵的每行每列元素：n"); for(row=1;row<=a.mu;row+) / 双重循环 /for(col=1;col<=a .nu ;col+)scan f("%d", &temp); if(temp!=O)a.datap.i=row;a.datap.j=col;a.datap.e=temp;p+;a.t

10、u=p;prin tf("n");return 0;输出上面的矩阵int output(tx &a)int row,col;int p=1;prin tf("输出原始矩阵：n");for(row=1;row<=a.mu;row+)for(col=1;col<=a .nu ;col+)if(row=a.datap.i && col=a.datap.j)找出非 0 元素/prin tf("t%d",a.datap.e);p+;else/剩余的输出0prin tf("t%d",0);p

11、rintf("n"); /换行符的位置/return 0;定义了一个新的矩阵b/int tran spose(tx a,tx &b)int row,col;in t p,q=1;b.mu=a.nu; /矩阵b的行数等于矩阵a的列数/b.nu=a.mu; /矩阵b的列数等于矩阵a的行数/b.tu=a.tu; 非0元素的个数/if(a.tu!=O) /判断是否有非0元素/双重循环/for(col=1;col<=a .nu ;col+)该循环是以列循环目的是：把非0元素中列标小的元素从头排列/for(p=1;p<=a.tu;p+)if(a.datap.j=co

12、l)循环非0数组中的元素，并找出a.datap.j等于当时的a矩阵在中的col/把矩阵a中非0元素的行标和列标等于矩阵b非0元素的列标和行标/b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.e=a.datap.e;q+;prin tf("n");return 0;输出转置后的矩阵int outputtra nspose(tx &b)int q=1;int row,col;printf("输出转置后的矩阵：n");for(row=1;row<=b.mu;row+)for(col=1;col<

13、;=b .nu ;col+)if(row=b.dataq.i && col=b.dataq.j)/ 找出 b 矩阵非 0 元素/ prin tf("t%d",b.dataq.e);q+;elseprintf("t%d",0); / 剩余的输出 0prin tf("n");return 0;void mai n()tx a,b;in tput(a);output(a);tran spose(a,b); outputtra nspose(b);五、调试及测试数据(1)三元组顺序表存储稀疏矩阵并实现矩阵的转置；(2)实现矩阵的经典转置算法并测试;请瓠入矩昨行数：3蘸入原乍矩阵禹每行每列元素12 34 5 67 8 9输岀原始矩阵：1 2345&