数据结构稀疏矩阵运算器课程设计.docx
- 文档编号:16316036
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:27
- 大小:133.06KB
数据结构稀疏矩阵运算器课程设计.docx
《数据结构稀疏矩阵运算器课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构稀疏矩阵运算器课程设计.docx(27页珍藏版)》请在冰点文库上搜索。
数据结构稀疏矩阵运算器课程设计
数据结构----稀疏矩阵运算器课程设计
稀疏矩阵运算器设计............................................................................................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.抽象数据类型稀疏矩阵的定义如下:
ADTSparseMatrix{
数据对象:
D={a|i=1,2,…,m;j=1,2,…,n;
ija∈ElemSet,m和n分别为矩阵的行数和列ij数}
数据关系:
R={Row,Col}
Row={﹤a,a﹥|1≤i≤m,1≤j≤n-1}i,j+1i,jCol={﹤a,a﹥|1≤i≤m-1,1≤j≤n}i+1,ji,j基本操作:
create(TSMatrix&TM)
操作结果:
创建稀疏矩阵矩阵TM
LocateELem(TSMatrixM,inti,intj,inte)
初始条件:
稀疏矩阵M存在
操作结果:
稀疏矩阵中是否存在非零元素A[i][j],若存在返回e
disp(TSMatrixTM)
初始条件:
稀疏矩阵TM存在
操作结果:
通常形式输出稀疏矩阵
InsertSortMatrix(TSMatrix&TM)
存在TM初始条件:
稀疏矩阵
操作结果:
根据对矩阵的行列,三元组TM作直接插入排序
TransposeSMatrix(TSMatrixM,TSMatrix&T)
初始条件:
稀疏矩阵M和T存在
操作结果:
求稀疏矩阵M转置的稀疏矩阵T
AddTSM(TSMatrixA,TSMatrixB,TSMatrix&C)
初始条件:
稀疏矩阵A,B和C存在
操作结果:
稀疏矩阵的加法运算:
C=A+B
SubTSM(TSMatrixA,TSMatrixB,TSMatrix&C)
初始条件:
稀疏矩阵A,B和C存在
操作结果:
稀疏矩阵的减法运算:
C=A-B
MultSMatrix(TSMatrixA,TSMatrixB,TSMatrix&C)
初始条件:
稀疏矩阵A,B和C存在
操作结果:
稀疏矩阵的乘法运算:
C=A×B
NiMatrix(TSMatrix&TM)
初始条件:
稀疏矩阵TM存在
操作结果:
稀疏矩阵求逆
}ADTSparseMatrix;
2.主程序:
voidmain()
{初始化;
do{
接受命令;
选择处理命令;
}while(命令!
=“退出”)
}
3.本程序有四个模块,调用关系如下:
主程序模块
矩阵输入模块
矩阵运算模块
矩阵输出模块
图2.1
本程序的流程图4
开始
选择要执行的操作
,1选择进行矩阵转置运算
,选择2进行矩阵加法运算
,选择3进行矩阵乘法运算
选择4,退出程序
的行数、列数、非零元个数A个矩阵n输入
输出结果
结束
2.2
图
设计步骤第三章
函数说明3.1稀疏矩阵的三元组顺序表存储表示:
定义三元组的元素typedefstruct//
{
inti,j;
intv;
}Triple;
classtripletable
设计类来描述稀疏矩阵及其操作//{
public:
aaa*pdata;
tripledata[maxsize];
tripletable();intrpos[maxsize];
~tripletable();
voidconvert();
voidadd();
voidmulti();
private:
intm;
intn;
intt;
inta;
};
主要函数:
tripletable();
~tripletable();
voidconvert();
voidadd();
voidmulti();
voidmain();
3.2设计步骤:
设计一个矩阵类实现矩阵的运算:
classtripletable(包含矩阵的各种运算函数)。
输入矩阵(以三元组形式输入非零元)
{
intk;
tripletableA,B;
;
的行数,列数和非零元个数:
A输入稀疏矩阵潣瑵?
cin>>A.m>>A.n>>A.t;
for(k=1;k<=A.t;k++)
{
牰湩晴尨输入第%d个非0元素的行数,列数和值:
k);
cin>>A.data[k].i>>A.data[k].j>>A.data[k].v;
}
输出矩阵:
intc[100][100]={0};
for(k=1;k<=B.t;k++)
{
c[B.data[k].i][B.data[k].j]=B.data[k].v;
}
潣瑵?
转置(加法,乘法)结果为:
< for(k=1;k<=B.n;k++) { for(intl=1;l<=B.m;l++) cout< cout< } } 转置矩阵: 矩阵的转置//voidtripletable: : convert() { intk; tripletableA,B; 潣瑵? 输入稀疏矩阵A的行数,列数和非零元个数: ; cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) { 牰湩晴尨输入第%d个非0元素的行数,列数和值: k); 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) { intq=1,col; for(col=1;col<=A.n;++col) for(intp=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; } } intshuru[100][100]={0}; for(k=1;k<=B.t;k++) { shuru[B.data[k].j][B.data[k].i]=B.data[k].v; } 潣瑵? 输入为: < for(k=1;k<=B.m;k++) { for(intl=1;l<=B.n;l++) cout< cout< } intresult[100][100]={0}; for(k=1;k<=B.t;k++) { result[B.data[k].i][B.data[k].j]=B.data[k].v; } 潣瑵? 结果为: < for(k=1;k<=B.n;k++) { for(intl=1;l<=B.m;l++) cout< cout< } } 以上主要设计思想: 通过三元组输入一个矩阵A,为了找到A的每一列中所有非零元素,需要对其三元组表A.data从第一行起整个扫描一遍,由于A.data是以A的行序为主序来存放每个非零元的,由此得到的恰是B.data的应有的顺序。 加法矩阵: voidtripletable: : add()//矩阵的加法 { intk; tripletableA,B; 潣瑵? 输入稀疏矩阵A的行数,列数和非零元个数: ; cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) { 牰湩晴尨输入第%d个非0元素的行数,列数和值: k); cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; } 潣瑵? 输入稀疏矩阵B的行数,列数和非零元个数: ; cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k++) { 牰湩晴尨输入第%d个非0元素的行数,列数和值: k); cin>>B.data[k].i>>B.data[k].j>>B.data[k].v; } if(A.m! =B.m||A.n! =B.n) { 潣瑵? 输入错误: A与B的行数或列数不相同,请重新输入< return; } inta[100][100]={0}; for(k=1;k<=A.t;k++) { a[A.data[k].i][A.data[k].j]=A.data[k].v; } cout< < for(k=1;k<=A.m;k++) { for(intl=1;l<=A.n;l++) cout< cout< } intb[100][100]={0}; for(k=1;k<=B.t;k++) { b[B.data[k].i][B.data[k].j]=B.data[k].v; } cout< < for(k=1;k<=B.m;k++) { for(intl=1;l<=B.n;l++) cout< cout< } intc[100][100]={0}; for(k=1;k<=A.m;k++) { for(intl=1;l<=A.n;l++) { c[k][l]=a[k][l]+b[k][l]; } } 潣瑵? 加法结果C为: < for(k=1;k<=A.m;k++) { for(intl=1;l<=A.n;l++) cout< cout< } } 以上主要设计思想: 此功能由函数add()实现,当用户选择该功能时系统即提示用户初始化要进行加法的两个矩阵的信息。 然后检测这两个矩阵是否符合矩阵相加的规则,如果符合,进行加法。 否则重新输入第二个矩阵来保证两个矩阵可以相加。 最后输出结果。 乘法矩阵: voidtripletable: : multi()//矩阵的乘法 { intk; tripletableA,B,C; 潣瑵? 输入稀疏矩阵A的行数,列数和非零元个数: ; cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k++) { 牰湩晴尨输入第%d个非0元素的行数,列数和值: k); cin>>A.data[k].i>>A.data[k].j>>A.data[k].v; } introw=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; 潣瑵? 输入稀疏矩阵B的行数,列数和非零元个数: ; cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k++) { 牰湩晴尨输入第%d个非0元素的行数,列数和值: k); 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) { 潣瑵? 输入错误: A的列数不等于B的行数,请重新输入< return; } C.m=A.m;C.n=B.n;C.t=0; intarow,p,q,ccol,t,tp; if(A.t*B.t! =0) { for(arow=1;arow<=A.m;++arow) { intctemp[maxsize]={0}; C.rpos[arow]=C.t+1; if(arow else{tp=A.t+1;} for(p=A.rpos[arow];p { intbrow=A.data[p].j; if(brow else{t=B.t+1;} for(q=B.rpos[brow];q { ccol=B.data[q].j; 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]; } } } } inta[100][100]={0}; for(k=1;k<=A.t;k++) { a[A.data[k].i][A.data[k].j]=A.data[k].v; } cout< ;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 稀疏矩阵运算器课程设计 稀疏 矩阵 运算器 课程设计