2019秋《数据结构课程设计》——课程设计报告模板

中国石油大学（北京）远程教育学院数据结构课程设计报告课程设计题目学生姓名学号专业班级2019 年 月题目要求：设计一个稀疏矩阵计算器，实现两个稀疏矩阵的加法、减法、乘法以及矩阵的转置运算。采用菜单为应用程序的界面，用户通过对菜单进行选择，分别实现矩阵的相加、相减、相乘以及矩阵转速运算。1需求分析1. 稀疏矩阵是指稀疏因子小于等于0.5的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。2. 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，以及两个矩阵的加、减、乘的运算。稀疏矩阵的输入形式采用三元组表示，运算结果以阵列形式列出。3. 演示程序以用户和计算机的对话方式进行，数组的建立方式为边输入边建立。首先输入矩阵的行数和列数，并判别给出的两个矩阵的行列数是否与所要求的运算相匹配。4. 程序可以对三元组的输入属性不加以限制；根据对矩阵的行列，三元组作之间插入排序，从而进行运算时，不会产生错误。5. 在用三元组表示稀疏矩阵时，相加、相减和相乘所产生的结果矩阵另外生成。6. 运行环境：VC6.0+。2概要设计稀疏矩阵元素用三元组表示：typedef structint i;/非零元的行下标int j;/非零元的列下标int e;/矩阵非零元Triple;稀疏矩阵采用三元组顺序表存储：#define MSXSIZE 12500/假设非零元个数的最大值为200#define MAXRC 10 /假定矩阵的最大行数为10typedef struct int mu ; /矩阵的行数 int nu ; /矩阵的列数 int tu ; /矩阵的非零元素个数 Triple dataMAXSIZE+1; /非零元三元组表，data0没有用int rposMAXRC+1; /各行第一个非零元素的位置表Tabletype;系统主要函数及功能如下：Menu( )：主控菜单，接收用户的选项；Input_Matrix( )：输入矩阵；Print_matrix( )：输出矩阵；Cal_matrix( )：计算矩阵每行第一个非零元在三元组中的位序号；TransposeMatrix( )：矩阵转置；Add_Matrix( )：矩阵加法运算；Sub_Matrix( )：矩阵减法运算；Multi_Matrix( )：矩阵乘法运算。模块的调用关系如图1所示。Multi_MatrixmainAdd_MatrixSub_MatrixTransposeMatrixCal_MatrixInput_MatrixPrint_Matrix图1 程序调用模块示意图3详细设计1. 主函数设计/*/* 矩阵运算主函数 */*主函数中，实现用户菜单菜单的打印，并根据用户的选项执行相应的功能，主函数力求简洁、清晰。void main( ) num=Menu();/打印主菜单while(num)switch(num)case 1:Multi_Matrix();/矩阵相乘break;case 2:TransposeMatrix();/矩阵转置break;case 3:Add_Matrix();/矩阵加法break;case 4:Sub_Matrix();/矩阵减法case 0:break;/switchnum=Menu();/while2. 主菜单设计主控菜单是用来输出提示信息和处理输入，此函数返回用户的选项，提供给main函数中的switch语句。对于不符合要求的选项，提示输入错误并要求用户重新输入。将此函数与main函数合在一起，编译运行程序，即可检查并验证菜单选项是否正确。主菜单如下：/*/* 打印主控菜单函数 */*int menu( )printf("n 主菜单");printf("n*");printf("n1. 矩阵乘法");printf("n2. 矩阵转置");printf("n3. 矩阵加法");printf("n4. 矩阵减法");printf("n0. 退出");printf("n*");scanf("%d",&num);while(num<0|num>4)/输入非法，重新输入scanf("%d",&num);return num;3. 矩阵乘法运算函数/*/* 矩阵乘法运算算法 */*Status Multi_Matrix() Input_Matrix(&a);/输入矩阵a Input_Matrix(&b); /输入矩阵b Cal_matrix(&a);/计算矩阵a每行第一个非零元的位序号 Cal_matrix(&b);/计算矩阵b每行第一个非零元的位序号 if (a.nu!=b.mu)/不符合矩阵乘法条件，不能相乘 return ERROR; c.mu=a.mu; /对矩阵c初始化 c.nu=b.nu; c.tu=0; if(a.tu*b.tu!=0) for(arow=1;arow<=a.mu;arow+) /*处理矩阵a的每一行*/ for (p=1;p< MAXRC+1;p+) /*当前行各元素累加器清零*/ ctempp=0; c.rposarow=c.tu+1; if(arow<a.mu ) tp=a.rpos arow+1; else tp=a.tu +1; for(p=a.rposarow; p<tp;p+) /求得c中第crow行的非零元 brow=a.datap.j; if(brow<b.nu) t=b.rposbrow+1; else t=b.tu+1; for (q=b.rposbrow;q<t;q+) ccol=b.dataq.j; /*乘积元素在矩阵c中的列号*/ ctempccol+=a.datap.e*b.dataq.e; /*for q*/ /for p for(ccol=1;ccol<=c.nu;ccol+) if(ctempccol)/*压缩存储该行非零元*/ if(c.tu)>MAXSIZE) exit(1); c.tu+; c.datac.tu.i=arow; c.datac.tu.j=ccol; c.datac.tu.e=ctempccol; /*end if*/ /*for arrow*/ /*if*/ Print_matrix(a); Print_matrix(b); Print_matrix(c);4. 矩阵转置算法/*/* 矩阵转置算法 */*void TransposeMatrix()Input_Matrix(&a);/输入矩阵ab.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if(b.tu) q=1; /*b.data的下标*/ for(col=1;col<=a.nu;col+) /对a的每一列 for(p=1;p<=a.tu;p+) /*p为a的下标*/ if( a.datap.j=col) /寻找矩阵a中列为col的非零元 b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.e=a.datap.e; q+; /if(p)/if(b.tu)Print_matrix(b); /输出a的转置矩阵5. 矩阵加法算法/*/* 矩阵加法运算函数 */* c=a+b */*Status Add_Matrix()Input_Matrix(&a); /输入矩阵aInput_Matrix(&b); /输入矩阵bif(a.mu !=b.mu |a.nu !=b.nu ) /不满足矩阵加法条件return ERROR;c.mu =a.mu ;c.nu =a.nu ;ta=1;tb=1;tc=1;if(a.tu *b.tu !=0)while(ta<=a.tu) && (tb<=b.tu)if(a.datata.i=b.datatb.i)if(a.datata.j=b.datatb.j)temp=a.dat