数据结构课程设计
- 格式：doc
- 大小：267.50 KB
- 文档页数：17
附件1：课程设计题目稀疏矩阵相乘学院计算机科学与技术学院专业********班级********姓名张权指导教师林泓2011 年06 月30 日系主任（或责任教师）签名： 2011年06月30日课程设计任务书学生姓名：********专业班级：********指导教师：林泓工作单位：计算机科学系题目: 稀疏矩阵相乘初始条件：稀疏矩阵是指那些多数元素为零的矩阵。
利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。
实现一个能进行稀疏矩阵基本运算的运算器。
（1）以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵（2）实现两个矩阵相乘的运算。
（3）稀疏矩阵采用十字链表表示，而运算结果的矩阵则以通常的阵列形式列出。
（4）测试用例见严蔚敏《数据结构习题集(C语言版)》p136。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1. 问题描述简述题目要解决的问题是什么。
2. 设计存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4. 经验和体会（包括对算法改进的设想）5. 附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。
说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。
时间安排：1、第19周完成。
2、6月30日下午-7月1日在实验中心检查程序、交课程设计报告、源程序（U盘）。
指导教师签名： 2011年6月22日稀疏矩阵相乘1.1问题描述稀疏矩阵是指那些多数元素为零的矩阵。
利用“稀疏”特点进行存储和计算可以大大节存储空间，提高计算效率。
实现一个能进行稀疏矩阵基本运算的运算器。
（1）以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵（2）实现两个矩阵相乘的运算。
（3）稀疏矩阵采用十字链表表示，而运算结果的矩阵则以通常的阵列形式列出。
（4）测试用例见严蔚敏《数据结构习题集(C语言版)》p136。
2.1设计2.1.1存储结构设计为了便于随机存取任意一行的非零元，则需知道每行的第一个非零元在三元组表中的位置。
一般则将指示“行”信息的辅助数组固定在稀疏矩阵的存储结构中。
称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。
其基类型描述如下：#define MAXSIZE 400#define MAXRCtypedef struct{int i,j;ElemType e;}Triple;typedef struct{Triple data[MAXSIZE+1];int rpos[MAXRC+1];int mu,nu,tu;}RLSMatrix;由于非零元素的插入或删除将会引起矩阵中元素的移动。
所以对于这种类型的矩阵，我们采用链式存储结构表示三元组的线性表更为恰当。
稀疏矩阵十字链表存储表示描述如下：typedef struct OLNode{int i,j;ElemType e;struct OLNode *right,*dowm;}OLNode;*OLink;typedef struct{OLink *rhead,*chead;int mu,nu,tu;}CrossList;本实验主要利用矩阵的三元组表为行逻辑链接的顺序表。
2.1.2主要算法设计2.1.2.1设定矩阵的抽象数据类型定义：ADT SparseMatrix{数据对象：D={ m和n分别称为矩阵的行数和列数}数据关系：R={Row，Col}Row={<ai,j，ai,j+1 >|1<=i<=m，a<=j<=n-1 }Col={<ai,j，ai+1,j>|1<=i<=m-1，a<=j<=n }基本操作：CreateSMatrix(&M);操作结果：创建稀疏矩阵M。
DestorySMatrix(&M);初始条件：稀疏矩阵M存在。
操作结果：销毁稀疏矩阵M。
PrintSMatrix(M)；初始条件：稀疏矩阵M存在。
操作结果: 输出稀疏矩阵M。
CopySMatrix(M,&T)；初始条件：稀疏矩阵M存在。
操作结果：由稀疏矩阵M复制得到T。
AddSMatrix(M,N,&Q)；初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的和Q=M+N。
SubtSMatrix(M,N,&Q);初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的差Q=M-N。
MultSMatrix(M,N,&Q);初始条件：稀疏矩阵M的列数等于N的行数。
操作结果：求稀疏矩阵乘积Q=M*N。
TransposeSMatrix(M,&T);初始条件：稀疏矩阵M 存在。
操作结果：求稀疏矩阵M的转置矩阵T。
}ADT SparseMatrix本实验主要用到矩阵抽象类型中的创建函数，输出函数，两稀疏矩阵相乘函数。
2.1.2.2本程序包含的模块（1）void main(){初始化；do{ 接收命令；处理命令；}while(命令！=退出)；}（2）稀疏矩阵模块——实现相关的稀疏矩阵抽象数据类型。
主要为创建稀疏矩阵函与矩阵输出函数。
（3）稀疏矩阵求值模块——实现稀疏矩阵求值抽象数据类型。
稀疏矩阵求值模块即为相乘模块MulTSMatrix()；2.1.2.3详细设计算法（C++语言描述）1.首先设计矩阵的存储结构。
为了便于计算两稀疏矩阵相乘，提高计算效率，我选择了矩阵的三元组表为行逻辑链接的顺序表。
具体内容如下：struct Triple{ //稀疏矩阵的三元组表存储表示int i,j; //该非零元的行下标和列下标int e;};struct RLSMatrix{Triple data[MAXSIZE+1]; //非零元三元组表，data[0]未用int rpos[MAXRC+1]; //各行第一个非零元的位置表int mu,nu,tu; //矩阵的行数列数和非零元的个数};2.输入创建稀疏矩阵的算法void CreateSMatrix(RLSMatrix &T){int k;cout<<"\n请输入矩阵行数、列数及非零元个数: ";cin>>T.mu;cin>>T.nu;cin>>T.tu;cout<<"\n";if(T.tu>MAXSIZE||T.mu>21){cout<<"非零个数超出定义范围！出错！";exit(1);}for(k=1;k<=T.tu;k++){cout<<"请输入第"<<k<<"个非零元素的行数,列数及其值: ";cin>>T.data[k].i;cin>>T.data[k].j;cin>>T.data[k].e;}T.rpos[1]=1;for(int a=1;a<=T.mu;a++){ int size=0;for(k=1;k<=T.tu;k++) if(T.data[k].i==a)size++;T.rpos[a+1]=size+T.rpos[a];}}3.稀疏矩阵相乘的算法int MulTSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)// 求稀疏矩阵相乘采用行逻辑链接存储表示{int ccol=0,brow,t,arow,p,q;if(M.nu!=N.mu){cout<<"你的输入不满足矩阵相乘的条件!\n";return 0;}Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//初始化Qif(M.tu*N.tu!=0)//Q是非零矩阵{for(arow=1;arow<=M.mu;++arow)//处理每一行{int ctemp[MAXSIZE+1]={0};//当前行元素累加器清零Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p)//对当前行中每一个非零元{brow=M.data[p].j;//找对应元在N中的行号if(brow<N.mu) t=N.rpos[brow+1];else t=N.tu+1;for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;//乘积元素在Q中的列号ctemp[ccol]+=M.data[p].e*N.data[q].e;}//forq}//求的Q中第crow行的非零元for(ccol=1;ccol<=Q.nu;++ccol)//压缩存储该行非零元if(ctemp[ccol]){if(++Q.tu >MAXSIZE) return 0;Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].e=ctemp[ccol];}//if}//for arow}//ifreturn 1;}4.输出矩阵算法void PrintSMatrix(RLSMatrix &Q) //输出稀疏矩阵{int k=1,row,line;if(Q.tu==0)cout<<"0";else{for(row=1;row<=Q.mu;row++){for(line=1;line<=Q.nu;line++){if(Q.data[k].i==row&&Q.data[k].j==line){cout.width(4);cout<<Q.data[k++].e;cout.width(4);}else {cout.width(4);cout<<"0";cout.width(4);}}cout<<endl;}}}6.主函数的设计算法：void main(){RLSMatrix M,N,Q;int i;do{cout<<"\t\t***************************\n";cout<<"\t\t 稀疏矩阵运算器\n";cout<<"\t\t***************************\n\n";cout<<"\t\t 1.矩阵相乘\n\n";cout<<"\t\t 0.退出\n\n";cout<<"\t\t 请选择: ";cin>>i;if(i==0) goto end;else{cout<<"\n请输入第一个矩阵M:\n";CreateSMatrix(M);cout<<"\n 请输入第二个矩阵N:\n"; CreateSMatrix(N); switch(i) {case 1:MulTSMatrix(M,N,Q);break; default:break ； }}cout<<"M 矩阵="<<endl; PrintSMatrix(M);cout<<"N 矩阵="<<endl; PrintSMatrix(N);cout<<"结果为"<<endl; PrintSMatrix(Q); cout<<endl; getchar(); getchar(); end: ;}while(i!=0); }2.1.3测试用例设计本实验所用测试用例为任务书所要求的严蔚敏《数据结构习题集(C 语言版)》p136。
