数据结构+课程设计+稀疏矩阵的操作

1、攀枝花学院学生课程设计（论文）题 目：学生姓名： 学 号： 所在院(系)： 专 业： 班 级： 指 导 教 师： 职称：年 月 日攀枝花学院教务处制攀枝花学院本科学生课程设计任务书注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表稀疏矩阵的操作1.课程设计的目的本课程设计是为了配合数据结构课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。利用三元组实现稀疏矩阵的有关算法。2问题描述2.1稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。2.2求出A的转置矩阵D，输出D。3.

2、基本要求稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。4.结构设计4.1.以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。4.2.稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则通常以阵列形式列出。4.3.首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的

3、行数和列数均不超过20。4.4.程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教材的算法，以便提高计算效率。5.在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放5.算法思想5.1主函数设置循环和选择语句进行运算循环和选择，进行稀疏矩阵的加法，减法，乘法，转置和是否继续运算5个分支开关进行运算选择。5.2设置函数分别实现稀疏矩阵的输入，输出，加法，减法，乘法。5.3在数组结构体中设置存放每行第一个非零元在其数组存储结构单元的位置的存储单元，若该行无非零元，则存为06.模块划分6.1typedef struct存放各行第一个非零元在存储数组中的位

4、置，若该行无非零元，则其rpos值为零6.2 createsmatrix(rlsmatrix *M) 矩阵输入函数，输入各行非零元及其在矩阵中的行列数6.3 FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q) 矩阵快速转置6.4 HeRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) 矩阵求和6.5 ChaRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) 矩阵求差6.6 JiRLSMatrix(RLSMatrix M,RLSMatrix N,RLSMa

5、trix *Q) 矩阵求积7.算法实现7.1首先定义非零元个数的最大值和存放各行第一个非零元在存储数组中的位置 #include<stdio.h>#define MAXSIZE 100 /* 非零元个数的最大值 */typedef struct tripleint i,j; /* 行下标,列下标 */int e; /* 非零元素值 */triple;typedef struct tsmatrixtriple dataMAXSIZE+1; /* 非零元三元组表,data0未用 */int mu,nu,tu; /* 矩阵的行数、列数和非零元个数 */* 各列第一个非零元的位置表rpos

6、0未用 */rlsmatrix;7.2创建稀疏矩阵矩阵的行数，列数，和非零元素的个数并按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值。createsmatrix(rlsmatrix *M) /* 创建稀疏矩阵M */int e,i,m,n;M->data0.i=0; /* 为以下比较顺序做准备 */printf("请输入矩阵的行数，列数，和非零元素的个数:");scanf("%d",&M->mu);scanf("%d",&M->nu);scanf("%d",

7、&M->tu);for(i=1;i<=M->tu;i+)printf("请按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值：",i,M->mu,M->nu); scanf("%d",&m);scanf("%d",&n);scanf("%d",&e);if(m<1|m>M->mu|n<1|n>M->nu) /*行或列超出范围 */printf("行或列超出范围");getch()

8、;exit();if(m<M->datai-1.i|m=M->datai-1.i&&n<=M->datai-1.j) /*行或列的顺序有错*/printf("行或列的顺序有错");getch();exit();M->datai.i=m;M->datai.j=n;M->datai.e=e;7.3求矩阵的快速转置cpos为存放每列的第一个非零元素的地址，temp为中间变量对cpos对初始化，判断初值为0则为cpos赋值，然后进行转置。void transposesmatrix(rlsmatrix M,rlsmatr

9、ix *T) /* cpos存放每列的第一个非零元素的地址，temp中间变量 */int i,m,*cpos,*temp,k=0;T->mu=M.nu;T->nu=M.mu;T->tu=M.tu;cpos=(int *)malloc(M.mu*sizeof(int);if(cpos=NULL)exit();temp=(int *)malloc(M.mu*sizeof(int);if(temp=NULL)exit();/* 对cpos对初始化，初值为0 */*(cpos+1)=0;for(i=1;i<=M.nu;i+)for(m=1;m<=M.tu;m+)if(M.

10、datam.j=i)k+;tempi=k;if(i=1&&k!=0)*(cpos+i)=1;/* 为cpos赋值 */if(i>1)*(cpos+i)=*(temp+i-1)+1;free(temp);for(i=1;i<=M.tu;i+)/* 进行转置 */T->data*(cpos+M.datai.j).i=M.datai.j;T->data*(cpos+M.datai.j).j=M.datai.i;T->data*(cpos+M.datai.j).e=M.datai.e;(*(cpos+M.datai.j)+;free(cpos);7.3矩阵

11、的相乘设置两个指针，分别指向M，N的第一个非零元位置，移动指针进行比较，得出相加后的新矩阵非零元。定义Qe为矩阵Q的临时数组，矩阵Q的第i行j列的元素值存于*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)中，初值为0，结果累加到Qe，*Qe矩阵中，因为M的每一行和N的每一列相乘都是T的一个元素，不管它是零或非零，当M的第一行和N的第一列相乘则得T的第一个元素；当M的第一行和N的第二列相乘则得T的第二个元素，M的第i行和N的第j列相乘则得T的第p个元素；根据归纳法得p=(i-1)*N的列数+j。multsmatrix(rlsmatrix M,rlsmatrix N,rlsma

12、trix *T)int i,j,Qn=0;int *Qe;if(M.nu!=N.mu)printf("两矩阵无法相乘");getch();exit();T->mu=M.mu;T->nu=N.nu;Qe=(int *)malloc(M.mu*N.nu*sizeof(int); /* Qe为矩阵Q的临时数组*/for(i=1;i<=M.mu*N.nu;i+)*(Qe+i)=0;/* 矩阵Q的第i行j列的元素值存于*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)中，初值为0 */ for(i=1;i<=M.tu;i+) /* 结果累加到

13、Qe */for(j=1;j<=N.tu;j+)if(M.datai.j=N.dataj.i)*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)+=M.datai.e*N.dataj.e;for(i=1;i<=M.mu;i+) /*Qe矩阵中，因为M的每一行和N的每一列相乘都是T的一个元素，不管它是零或非零 */for(j=1;j<=N.nu;j+) /*当M的第一行和N的第一列相乘则得T的第一个元素；当M的第一行和N的第二列相乘则得T的第二个元素； */if(*(Qe+(i-1)*N.nu+j)!=0) /*当M的第i行和N的第j列相乘则得T的第p个元素；

14、根据归纳法得p=(i-1)*N的列数+j */Qn+;/非零元个数加一T->dataQn.e=*(Qe+(i-1)*N.nu+j);T->dataQn.i=i;T->dataQn.j=j;free(Qe);T->tu=Qn;return ;7.4矩阵的相加编写一个求两个对称矩阵相加运算的函数。设对称矩阵的数据元素为整数类型，对称矩阵采用压缩存储方法存储，要求和矩阵采用非压缩方法存储。设置两个指针，分别指向M，N的第一个非零元位置，移动指针进行比较，得出相加后的新矩阵非零元计算各行第一个非零元素在存储数组中的位置，若该行无非零元，则rpos值为零。HeRLSMatrix(

15、RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q)/矩阵求和函数if(*M).mu!=(*N).mu|(*M).nu!=(*N).nu)printf("不满足矩阵相加的条件!");return 0;int k=1;Triple *p,*q;/设置两个指针，分别指向M，N的第一个非零元位置，移动指针进行比较，得出相加后的新矩阵非零元p=&(*M).data1; q=&(*N).data1; while(p<(*M).data+(*M).tu+1&&q<(*N).data+(*N).tu+1) if(*p)

16、.i<=(*q).i) if(*p).i<(*q).i) (*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e; k+;p+; else if(*p).j<=(*q).j) if(*p).j<(*q).j) (*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e; k+;p+; else (*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e+(*q).e; k+;p

17、+;q+; else (*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; else (*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; if(p<=(*M).data+(*M).tu)while(p<=(*M).data+(*M).tu)(*Q).datak.i=(*p).i;(*Q).datak.j=(*p).j;(*Q).datak.e=(*p).e;k+;p+;if(q<=(*N).data+(*

18、N).tu)while(q<=(*N).data+(*N).tu)(*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; (*Q).mu=(*M).mu;(*Q).nu=(*M).nu;(*Q).tu=k-1;/计算各行第一个非零元素在存储数组中的位置 /若该行无非零元，则rpos值为零 int num(*Q).mu+1,row,cpot(*Q).mu+1; cpot1=1; for(k=1;k<=(*Q).mu;k+) numk=0; for(k=1;k<=(*Q).tu;k+) +num(

19、*Q).datak.i; for(row=2;row<=(*Q).mu;row+) cpotrow=cpotrow-1+numrow-1; for(row=1;row<=(*Q).mu;row+) if(cpotrow<=(*Q).tu) if(*Q).datacpotrow.i=row) (*Q).rposrow=cpotrow; else (*Q).rposrow=0; else (*Q).rposrow=0;8.系统运行结果图1输入第一个矩阵A图2输入第二个矩阵B 两个矩阵的和图3矩阵A的转置矩阵D9.心得体会通过一周的课程设计使我对数据结构有了更深的理解，对以前学习中

20、不明白的，不理解的都有了进一步的理解。在实际操作中遇到了很多困难，但通过找资料，请教同学和老师，使我的动手能力和沟通能力都有了提高。在整个课程设计中总是在编写程序中发生错误，有时会很没耐性，但都被我一一克服了，编程一定要有耐心，同时还有认真仔细，尽量保证不出现错误。编程要有条理，不仅使自己要看懂 ，别人也能看懂，这样有利于程序的改正。在做完这个课程设计时，心里有种说不出来的高兴，自己动手完成的设计有一种成就感，增强了自己的自信心，我相信在今后的学习中，我会保持这种良好的心情投入到各科的学习中，使我的成绩不断提高。10.参考文献1 严蔚敏 吴伟名 编著，数据结构M.， 清华大学出版社， 2001

21、年1月20-252 张颖江 胡燕 主编，C语言程序设计M.， 科学出版社 ，1998年7月46-803 殷人昆， 数据结构M.，清华大学出版社， 2001年3月 120-1694 徐孝凯 ，数据结构实用教程M.，清华大学出版社，1999年12月 47-805 Adam Drozdek（美），数据结构与算法M.， 机械工业出版社 ，2003年7月 69-8911.附录源程序清单#include<stdio.h>#define MAXSIZE 100 /* 非零元个数的最大值 */typedef struct tripleint i,j; /* 行下标,列下标 */int e; /*

22、非零元素值 */triple;typedef struct tsmatrixtriple dataMAXSIZE+1; /* 非零元三元组表,data0未用 */int mu,nu,tu; /* 矩阵的行数、列数和非零元个数 */* 各列第一个非零元的位置表rpos0未用 */rlsmatrix;createsmatrix(rlsmatrix *M) /* 创建稀疏矩阵M */int e,i,m,n;M->data0.i=0; /* 为以下比较顺序做准备 */printf("请输入矩阵的行数，列数，和非零元素的个数:");scanf("%d",&a

23、mp;M->mu);scanf("%d",&M->nu);scanf("%d",&M->tu);for(i=1;i<=M->tu;i+)printf("请按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值：",i,M->mu,M->nu); scanf("%d",&m);scanf("%d",&n);scanf("%d",&e);if(m<1|m>M->mu

24、|n<1|n>M->nu) /*行或列超出范围 */printf("行或列超出范围");getch();exit();if(m<M->datai-1.i|m=M->datai-1.i&&n<=M->datai-1.j) /*行或列的顺序有错*/printf("行或列的顺序有错");getch();exit();M->datai.i=m;M->datai.j=n;M->datai.e=e;void transposesmatrix(rlsmatrix M,rlsmatrix

25、*T) /* cpos存放每列的第一个非零元素的地址，temp中间变量 */int i,m,*cpos,*temp,k=0;T->mu=M.nu;T->nu=M.mu;T->tu=M.tu;cpos=(int *)malloc(M.mu*sizeof(int);if(cpos=NULL)exit();temp=(int *)malloc(M.mu*sizeof(int);if(temp=NULL)exit();/* 对cpos对初始化，初值为0 */*(cpos+1)=0;for(i=1;i<=M.nu;i+)for(m=1;m<=M.tu;m+)if(M.dat

26、am.j=i)k+;tempi=k;if(i=1&&k!=0)*(cpos+i)=1;/* 为cpos赋值 */if(i>1)*(cpos+i)=*(temp+i-1)+1;free(temp);for(i=1;i<=M.tu;i+)/* 进行转置 */T->data*(cpos+M.datai.j).i=M.datai.j;T->data*(cpos+M.datai.j).j=M.datai.i;T->data*(cpos+M.datai.j).e=M.datai.e;(*(cpos+M.datai.j)+;free(cpos);HeRLSMat

27、rix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) /矩阵求和函数if(*M).mu!=(*N).mu|(*M).nu!=(*N).nu)printf("不满足矩阵相加的条件!");return 0;元p=&(*M).data1; q=&(*N).data1; while(p<(*M).data+(*M).tu+1&&q<(*N).data+(*N).tu+1) if(*p).i<=(*q).i) if(*p).i<(*q).i) (*Q).datak.i=(*p).i; (*Q).

28、datak.j=(*p).j; (*Q).datak.e=(*p).e; k+;p+; int k=1; Triple *p,*q; /设置两个指针，分别指向M，N的第一个非零元位置，移动指针进行比较，得出相加后的新矩阵非零else if(*p).j<=(*q).j) if(*p).j<(*q).j)(*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e; k+;p+; (*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e+(*q).e; k+;

29、p+;q+; else else (*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; else (*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; if(p<=(*M).data+(*M).tu)while(p<=(*M).data+(*M).tu)(*Q).datak.i=(*p).i; (*Q).datak.j=(*p).j; (*Q).datak.e=(*p).e; k+;p+; if(q<=(*

30、N).data+(*N).tu)while(q<=(*N).data+(*N).tu)(*Q).mu=(*M).mu;(*Q).nu=(*M).nu;(*Q).tu=k-1;/计算各行第一个非零元素在存储数组中的位置 /若该行无非零元，则rpos值为零 (*Q).datak.i=(*q).i; (*Q).datak.j=(*q).j; (*Q).datak.e=(*q).e; k+;q+; for(k=1;k<=(*Q).tu;k+) +num(*Q).datak.i; for(row=2;row<=(*Q).mu;row+) cpotrow=cpotrow-1+numrow

31、-1; int num(*Q).mu+1,row,cpot(*Q).mu+1; cpot1=1; for(k=1;k<=(*Q).mu;k+) numk=0; for(row=1;row<=(*Q).mu;row+) if(cpotrow<=(*Q).tu) if(*Q).datacpotrow.i=row) (*Q).rposrow=cpotrow; else (*Q).rposrow=0; else (*Q).rposrow=0;ChaRLSMatrix(RLSMatrix *M,RLSMatrix *N,RLSMatrix *Q) /矩阵求差函数if(*M).mu!=(

32、*N).mu|(*M).nu!=(*N).nu)printf("不满足矩阵相减的条件!");return 0;multsmatrix(rlsmatrix M,rlsmatrix N,rlsmatrix *T) int i,j,Qn=0;int *Qe;if(M.nu!=N.mu)printf("两矩阵无法相乘");getch();exit();T->mu=M.mu;T->nu=N.nu;Qe=(int *)malloc(M.mu*N.nu*sizeof(int); /* Qe为矩阵Q的临时数组*/ int i; for(i=1;i<=(

33、*N).nu;i+) (*N).datai.e*=-1; HeRLSMatrix(&(*M),&(*N),&(*Q);for(i=1;i<=M.mu*N.nu;i+)*(Qe+i)=0;/* 矩阵Q的第i行j列的元素值存于*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)中，初值为0 */ for(i=1;i<=M.tu;i+) /* 结果累加到Qe */for(j=1;j<=N.tu;j+)if(M.datai.j=N.dataj.i)*(Qe+(M.datai.i-1)*N.nu+N.dataj.j)+=M.datai.e*N.d

34、ataj.e;for(i=1;i<=M.mu;i+) /*Qe矩阵中，因为M的每一行和N的每一列相乘都是T的一个元素，不管它是零或非零 */for(j=1;j<=N.nu;j+) /*当M的第一行和N的第一列相乘则得T的第一个元素；当M的第一行和N的第二列相乘则得T的第二个元素； */if(*(Qe+(i-1)*N.nu+j)!=0) /*当M的第i行和N的第j列相乘则得T的第p个元素；根据归纳法得p=(i-1)*N的列数+j */Qn+;/非零元个数加一T->dataQn.e=*(Qe+(i-1)*N.nu+j);T->dataQn.i=i;T->dataQn.

35、j=j;free(Qe);T->tu=Qn;return ;main()RLSMatrix M,N,Q;char ch;printf(" * n");printf(" * * n"); printf(" * 稀疏矩阵运算器 * n"); printf(" * - * n"); printf(" printf(" printf(" printf(" * n"); _ n"); | 请选择 | n"); | A.加法 B.减法 C.乘法 D.转

36、置 Y.继续运算 N.结束运算 | n"); printf(" |_| nn"); printf("2 输入数字时请用逗号隔开！nn");printf(" ->"); scanf("%c",&ch); while(ch!='N')/进行循环运算 switch(ch)/进行运算选择 case'A': printf(" 请输入要求和的两个矩阵：nn"); printf(" 输入第一个矩阵：nn"); ScanRLSMatri

37、x(&M); printf(" 输入的第一个矩阵为：nn");PrintRLSMatrix(M); printf(" 输入第二个矩阵：nn"); ScanRLSMatrix(&N); printf(" 输入的第二个矩阵为：nn"); PrintRLSMatrix(N); HeRLSMatrix(&M,&N,&Q); printf(" 两矩阵之和为：nn"); PrintRLSMatrix(Q); printf(" 是否继续运算（Y/N）？nn"); printf(" ->"); ch=getchar(); ;break; case'B': printf(" 请按次序输入要求差的两个矩阵：nn"); printf(" 输入第一个矩阵：nn"); ScanRLSMatrix(&M); printf(" 输入的第一个矩阵为：nn"); PrintRLSMatrix(M);