中国石油大学（北京）远程教育学院《数据结构》课程设计报告课程设计题目学生姓名学号专业班级2019 年月题目要求：设计一个稀疏矩阵计算器，实现两个稀疏矩阵的加法、减法、乘法以及矩阵的转置运算。

采用菜单为应用程序的界面，用户通过对菜单进行选择，分别实现矩阵的相加、相减、相乘以及矩阵转速运算。

1需求分析1. 稀疏矩阵是指稀疏因子小于等于0.5的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

2. 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，以及两个矩阵的加、减、乘的运算。

稀疏矩阵的输入形式采用三元组表示，运算结果以阵列形式列出。

3. 演示程序以用户和计算机的对话方式进行，数组的建立方式为边输入边建立。

首先输入矩阵的行数和列数，并判别给出的两个矩阵的行列数是否与所要求的运算相匹配。

4. 程序可以对三元组的输入属性不加以限制；根据对矩阵的行列，三元组作之间插入排序，从而进行运算时，不会产生错误。

5. 在用三元组表示稀疏矩阵时，相加、相减和相乘所产生的结果矩阵另外生成。

6. 运行环境：VC6.0++。

2概要设计稀疏矩阵元素用三元组表示：typedef struct{int i; //非零元的行下标int j; //非零元的列下标int e; //矩阵非零元}Triple;稀疏矩阵采用三元组顺序表存储：#define MSXSIZE 12500 //假设非零元个数的最大值为200#define MAXRC 10 //假定矩阵的最大行数为10typedef struct{int mu ; //矩阵的行数int nu ; //矩阵的列数int tu ; //矩阵的非零元素个数Triple data[MAXSIZE+1]; //非零元三元组表，data[0]没有用int rpos[MAXRC+1]; //各行第一个非零元素的位置表}Tabletype;系统主要函数及功能如下：Menu( )：主控菜单，接收用户的选项；Input_Matrix( )：输入矩阵；Print_matrix( )：输出矩阵；Cal_matrix( )：计算矩阵每行第一个非零元在三元组中的位序号；TransposeMatrix( )：矩阵转置；Add_Matrix( )：矩阵加法运算；Sub_Matrix( )：矩阵减法运算；Multi_Matrix( )：矩阵乘法运算。

模块的调用关系如图1所示。

图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();}//while}2. 主菜单设计主控菜单是用来输出提示信息和处理输入，此函数返回用户的选项，提供给main函数中的switch语句。

对于不符合要求的选项，提示输入错误并要求用户重新输入。

将此函数与main函数合在一起，编译运行程序，即可检查并验证菜单选项是否正确。

主菜单如下：//*****************************************//* 打印主控菜单函数*//*****************************************int menu( ){printf("\n 主菜单");printf("\n*********************");printf("\n 1. 矩阵乘法");printf("\n 2. 矩阵转置");printf("\n 3. 矩阵加法");printf("\n 4. 矩阵减法");printf("\n 0. 退出");printf("\n*********************");scanf("%d",&num);while(num<0||num>4) //输入非法，重新输入scanf("%d",&num);return num;}3. 矩阵乘法运算函数//*****************************************//* 矩阵乘法运算算法*//*****************************************Status Multi_Matrix(){Input_Matrix(&a); //输入矩阵aInput_Matrix(&b); //输入矩阵bCal_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++) /*当前行各元素累加器清零*/ctemp[p]=0;c.rpos[arow]=c.tu+1;if(arow<a.mu )tp=a.rpos [arow+1];elsetp=a.tu +1;for(p=a.rpos[arow]; p<tp;p++){ //求得c中第crow行的非零元brow=a.data[p].j;if(brow<b.nu)t=b.rpos[brow+1];elset=b.tu+1;for (q=b.rpos[brow];q<t;q++){ccol=b.data[q].j; /*乘积元素在矩阵c中的列号*/ctemp[ccol]+=a.data[p].e*b.data[q].e;} /*for q*/}//for pfor(ccol=1;ccol<=c.nu;ccol++)if(ctemp[ccol]) /*压缩存储该行非零元*/{if((c.tu)>MAXSIZE)exit(1);c.tu++;c.data[c.tu].i=arow;c.data[c.tu].j=ccol;c.data[c.tu].e=ctemp[ccol];}/*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.data[p].j==col){ //寻找矩阵a中列为col的非零元b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].e=a.data[p].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.data[ta].i==b.data[tb].i){if(a.data[ta].j==b.data[tb].j){temp=a.data[ta].e+b.data[tb].e;if(temp!=0){c.data[tc].i=a.data[ta].i;c.data[tc].j=a.data[ta].j;c.data[tc].e=temp;tc++;}//end if (temp)ta++; tb++;}//end ifelse{if(a.data[ta].j<b.data[tb].j){c.data[tc].i=a.data[ta].i;c.data[tc].j=a.data[ta].j;c.data[tc].e=a.data[ta].e;ta++; tc++;}//end of else ifelse{c.data[tc].i=b.data[tb].i;c.data[tc].j=b.data[tb].j;c.data[tc].e=b.data[tb].e;tb++; tc++;}//}}//end ifelse{if(a.data[ta].i<b.data[tb].i){c.data[tc].i=a.data[ta].i;c.data[tc].j=a.data[ta].j;c.data[tc].e=a.data[ta].e;tc++; ta++;}else{c.data[tc].i=b.data[tb].i;c.data[tc].j=b.data[tb].j;c.data[tc].e=b.data[tb].e;tc++; tb++;}}}//whilewhile(ta<=a.tu){ //处理a中剩余非零元c.data[tc].i=a.data[ta].i;c.data[tc].j=a.data[ta].j;c.data[tc].e=a.data[ta].e;tc++; ta++;}while(tb<=b.tu){ //处理b中剩余非零元c.data[tc].i=b.data[tb].i;c.data[tc].j=b.data[tb].j;c.data[tc].e=b.data[tb].e;tc++; tb++;}}//c.tu=tc;Print_matrix(c);}6. 矩阵输入算法用于输入矩阵的行数、列数、非零元个数，以及每个非零元素。