数据结构----稀疏矩阵运算器课程设计
目 录
稀疏矩阵运算器设计 ............................................................................................ I 摘 要 ................................................................................................................... II
第一章 需求分析 .......................................................................................... 1 第二章 概要设计 .......................................................................................... 2 第三章 设计步骤 .......................................................................................... 6 3.1 函数说明 ....................................................................................... 6 3.2 设计步骤 ....................................................................................... 7 第四章 设计理论分析方法 ........................................................................ 20 4.1 算法一：矩阵转置 ..................................................................... 20 4.2 算法二：矩阵加法 ..................................................................... 20 4.3 算法三：矩阵乘法 ..................................................................... 21 第五章 程序调试 ........................................................................................ 23 第六章 心得体会 ........................................................................................ 25 参考文献 .................................................................................................... 26
第一章 需求分析
1． 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。
2． 以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，求逆，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 3． 演示程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。
4． 由题目要求可知：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。
5． 程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。
6． 在用三元组表示稀疏矩阵时，相加、乘积和相减所得结果矩阵应该另生成；矩阵求逆时，为了算法方便，使用二维数组存放。 7． 程序在VC6.0环境下设计。
程序执行的命令为：1.稀疏矩阵转置; 2.稀疏矩阵加法; ;3. 稀疏矩阵乘法; 4.退出 的工作。
第二章 概要设计
1． 抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{
数据对象：D={aij|i=1,2,…,m; j=1,2,…,n;
aij∈ElemSet, m和n分别为矩阵的行数和列数}
数据关系：R={Row,Col }
Row={﹤ai,j, ai,j+1﹥| 1≤i≤m, 1≤j≤n-1} Col = {﹤ai,j, ai+1,j﹥| 1≤i≤m-1, 1≤j≤n} 基本操作：
create(TSMatrix &TM)
操作结果：创建稀疏矩阵矩阵TM
LocateELem(TSMatrix M,int i,int j,int e)
初始条件：稀疏矩阵M存在
操作结果：稀疏矩阵中是否存在非零元素A[i][j]，若存在返回e
disp(TSMatrix TM)
初始条件：稀疏矩阵TM存在 操作结果：通常形式输出稀疏矩阵 InsertSortMatrix(TSMatrix &TM)
初始条件：稀疏矩阵TM存在
操作结果：根据对矩阵的行列，三元组TM作直接插入排序 TransposeSMatrix(TSMatrix M,TSMatrix &T) 初始条件：稀疏矩阵M和T存在
操作结果：求稀疏矩阵M转置的稀疏矩阵T AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C) 初始条件：稀疏矩阵A，B和C存在
操作结果：稀疏矩阵的加法运算:C=A+B
SubTSM(TSMatrix A,TSMatrix B,TSMatrix &C) 初始条件：稀疏矩阵A，B和C存在 操作结果：稀疏矩阵的减法运算:C=A-B MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C) 初始条件：稀疏矩阵A，B和C存在 操作结果：稀疏矩阵的乘法运算:C=A×B NiMatrix(TSMatrix &TM) 初始条件：稀疏矩阵TM存在 操作结果：稀疏矩阵求逆 }ADT SparseMatrix;
2. 主程序： void main( ) {初始化；
do {
接受命令；
选择处理命令； }while(命令！=“退出”) }
3. 本程序有四个模块，调用关系如下：
4 本程序的流程图
主程序模块 矩阵输入模块 矩阵运算模块 矩阵输出模块 图2.1
开始 选择1，选择2，进行矩阵加法运算 选择要执行的操作 选择3，进行矩阵乘法运算 选择4，退出程序 进行矩阵 转置运算 输出结果 输入n个矩阵A的行数、列数、非零元个数
图2.2
结束 第三章 设计步骤
3.1函数说明
稀疏矩阵的三元组顺序表存储表示： typedef struct // 定义三元组的元素 { int i,j; int v; }Triple; class tripletable
{ //设计类来描述稀疏矩阵及其操作 public:
aaa *pdata;
triple data[maxsize]; int rpos[maxsize]; tripletable(); ~tripletable(); void convert() ; void add( );
void multi ( ); private: int m ; int n ; int t ; int a ; };
主要函数： tripletable(); ~tripletable(); void convert( ) ; void add( ); void multi ( ); void main( ); 3.2设计步骤：
设计一个矩阵类实现矩阵的运算：class tripletable(包含矩阵的各种运算函数)。
输入矩阵（以三元组形式输入非零元） { int k;
tripletable A,B;
cout<<\"输入稀疏矩阵A的行数，列数和非零元个数：\";
cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) {
printf(\"输入第%d个非0元素的行数，列数和值:\ cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; } 输出矩阵： int c[100][100]={0};
for(k=1;k<=B.t;k++) {
c[B.data[k].i][B.data[k].j]=B.data[k].v; }
cout<<\"转置（加法，乘法）结果为：\"< void tripletable::convert( ) //矩阵的转置 { int k; tripletable A,B; cout<<\"输入稀疏矩阵A的行数，列数和非零元个数：\"; cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) { printf(\"输入第%d个非0元素的行数，列数和值:\ cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; } B.m=A.m;B.n=A.n;B.t=A.t; if(B.t) { int q=1,col; for(col=1;col<=A.n;++col) for(int p=1;p<=A.t;++p) if(A.data[p].j==col) { B.data[q].i=A.data[p].j; B.data[q].j=A.data[p].i; B.data[q].v=A.data[p].v; ++q; } } int shuru[100][100]={0}; for(k=1;k<=B.t;k++) { shuru[B.data[k].j][B.data[k].i]=B.data[k].v; } cout<<\"输入为：\"< for(k=1;k<=B.t;k++) { result[B.data[k].i][B.data[k].j]=B.data[k].v; } cout<<\"结果为：\"< cout< 加法矩阵： void tripletable::add( ) //矩阵的加法 { int k; tripletable A,B; cout<<\"输入稀疏矩阵A的行数，列数和非零元个数：\"; cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) { printf(\"输入第%d个非0元素的行数，列数和值:\ cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; } cout<<\"输入稀疏矩阵B的行数，列数和非零元个数：\"; cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k++) { printf(\"输入第%d个非0元素的行数，列数和值:\ cin>>B.data[k].i>>B.data[k].j>>B.data[k].v; } if(A.m!=B.m||A.n!=B.n) { cout<<\"输入错误：A与B的行数或列数不相同，请重新输入\"< a[A.data[k].i][A.data[k].j]=A.data[k].v; } cout<<\"A输入为：\"< b[B.data[k].i][B.data[k].j]=B.data[k].v; } cout<<\"B输入为：\"< for(int l=1;l<=A.n;l++) { c[k][l]=a[k][l]+b[k][l]; } } cout<<\"加法结果C为：\"< void tripletable::multi() //矩阵的乘法 { int k; tripletable A,B,C; cout<<\"输入稀疏矩阵A的行数，列数和非零元个数：\"; cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) { printf(\"输入第%d个非0元素的行数，列数和值:\ cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; } int row=1; for(k=1;k<=A.t;k++) { while(row<=A.data[k].i) { A.rpos[row++]=k; } } while(row<=A.m)A.rpos[row++]=A.t+1; cout<<\"输入稀疏矩阵B的行数，列数和非零元个数：\"; cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k++) { printf(\"输入第%d个非0元素的行数，列数和值:\ cin>>B.data[k].i>>B.data[k].j>>B.data[k].v; } row=1; for(k=1;k<=B.t;k++) { while(row<=B.data[k].i) { B.rpos[row++]=k; } } while(row<=B.m)B.rpos[row++]=B.t+1; if(A.n!=B.m) { cout<<\"输入错误：A的列数不等于B的行数，请重新输入\"< for(arow=1;arow<=A.m;++arow) { int ctemp[maxsize]={0}; C.rpos[arow]=C.t+1; if(arow if(brow ctemp[ccol]+=A.data[p].v*B.data[q].v; } } for(ccol=1;ccol<=C.n;++ccol) { if(ctemp[ccol]) { if(++C.t>maxsize)return; C.data[C.t].i=arow; C.data[C.t].j=ccol; C.data[C.t].v=ctemp[ccol]; } } } } int a[100][100]={0}; for(k=1;k<=A.t;k++) { a[A.data[k].i][A.data[k].j]=A.data[k].v; } cout<<\"A输入为：\"; cout< for(int l=1;l<=A.n;l++) cout< b[B.data[k].i][B.data[k].j]=B.data[k].v; } cout<<\"B输入为：\"< c[C.data[k].i][C.data[k].j]=C.data[k].v; } cout<<\"乘法结果C为：\"< 第四章 设计理论分析方法 4.1 算法一：矩阵转置 转置运算时一种最简单的矩阵运算，对于一个m*n的矩阵M，他的转置矩阵T是一个n*m的矩阵，且T（i，j）=M（j，i），1<=i<=n,1<=j<=m。 显然，一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。(1)将矩阵的行列值相互交换;(2)将每个三元组中的i和j相互调换；（3）重排三元组之间的次序便可实现矩阵的转置。 一般矩阵转置算法为 for(col=1;col<=nu;++col) for(row=1;row<=mu;++row) T[col][row]=M[row][col]; 按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。在此，需要附设num和cpot两个向量。Num[col]表示矩阵M中 第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。 cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2<=col<=a.nu 这就是快速转置。 4.2 算法二：矩阵加法 稀疏矩阵使用三元组存储，则运算时只需考虑非零元的值即可。两个矩阵相加 首先必须保证M.mu=N.mu&&M.nu=N.nu即同行同列的矩阵才能相加。 for(k=1;k<=M.tu;k++) for(i=1;i<=N.tu;i++) if(M.data[k].i == N.data[i].i && M.data[k].j == N.data[i].j) Q.data[count].e = M.data[k].e + N.data[i].e; flag[i] = true; 如果非零元位置一样就直接相加 if(i>N.tu) Q.data[count].e = M.data[k].e; 如果没有找到与M非零元位置一样的元素就直接把M中的非零元赋值给矩阵Q。 for(k=1;k<=N.tu;k++) if(!flag[k]) Q.data[count].e = N.data[k].e; 如果N中的元素没有被查找，则直接把N中的非零元赋值给矩阵Q。 4.3 算法三：矩阵乘法 矩阵乘法采用“带行链接信息”的三元组存储。经典算法如下： for(i=1;i<=m1;++i) for(j=1;j<=n2;++j) {Q[i][j]=0; for（k=1;k<=n1;++k） Q[i][j]+=M[j][k]*N[k][j]; } 稀疏矩阵相乘前提：M.nu=N.mu 大致步骤描述如下： Q初始化； If(Q是非零矩阵) {//逐行求积 for(arow=1;arrow<=M.mu;++arow) {//处理M的每一行 ctemp[ ]=0;//累加器清零 计算Q中第arow行的积并存入ctemp[ ]中； 将ctemp[ ]中非零元压缩存储到Q.data; } } 第五章 程序调试 整个程序主要运用了矩阵运算的规则，利用创建三元组表，分析数据，行列是否匹配，稀疏矩阵的转置，稀疏矩阵的相加，稀疏矩阵的相乘。 （1）稀疏矩阵的转置 图 5.1 （2）稀疏矩阵的加法 图 5.2 （3）稀疏矩阵的乘法： 图 5.3 第六章 心得体会 通过此次课程设计，使我更加扎实的掌握了有关稀疏矩阵方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。 过而能改，善莫大焉。在课程设计过程中，不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师和同学的指导下，终于游逆而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！ 参考文献 [1]谭浩强著.C程序设计（第三版）[M].北京：清华大学出版社，2009.5 [2]严蔚敏、吴伟民 主编《数据结构 （C语言版）》[M]. 清华大学出版社 2004.11 [3]．李建学 等 编著《数据结构课程设计案例精编（用C/C++描述）》[M]，清华大学出版社 2007.2 [4].殷人昆 主编《数据结构:用面向对象方法与C++语言描述》[M]， 清华大学出版社 2007.6 因篇幅问题不能全部显示，请点此查看更多更全内容