数据结构 课程设计.docx
- 文档编号:2804118
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:17
- 大小:51.06KB
数据结构 课程设计.docx
《数据结构 课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构 课程设计.docx(17页珍藏版)》请在冰点文库上搜索。
数据结构课程设计
设计性综合性实验
实验课题名称:
稀疏矩阵运算器
院系:
计算机科学与技术学院专业:
计算机科学与技术
课程:
数据结构教师:
学号:
姓名:
学号:
姓名:
学号:
姓名:
学号:
姓名:
学号:
姓名:
2010至2011学年度上学期
实验名称:
稀疏矩阵运算器
实验性质:
设计性
实验器材:
PC机并装有VC++6.0环境
实验目的:
深入研究数组的存储表示和实现技术,熟悉广义表存储结构的特性
实验任务:
实现一个能进行稀疏矩阵基本运算的运算器,要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵,实现两矩阵的相加、相减、相乘等运算。
输入以三元组表示,输出以通常的阵列形式列出。
实验内容、过程及结果:
一.问题描述
稀疏矩阵是指那些多数元素为零的矩阵。
利用稀疏特点进行储存和计算可以大大节省储存空间,提高计算效率。
实现能进行称稀疏矩阵基本运算的运算器。
基本要求:
以带逻辑链接信息的三元组顺序表表示稀疏矩阵,实现矩阵相加,相减,相乘的运算。
稀疏矩阵的输入形式采用三元组表示。
而运算结果的矩阵则用通常的阵列形式列出。
测试数据:
+
=
+
=
*
=
二.设计思路
A.行逻辑链接的顺序表为了便于随机存取任意一行的非零元,则需知道每一行的第一个非零元在三元组表中的位置。
为此,可将指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中
B.数据结构的选用为了实现稀疏矩阵的各种运算,采用三元组的方式储存矩阵
C.矩阵的各种运算为了求2和矩阵的各类运算,只需要在相乘2个矩阵中相对应的各个元素的j值和i值相运算即可
三.解决问题
【主程序模块】:
voidmain()
{
初始化;
do{
接受命令;
处理命令;
}while(命令!
=“退出”);
}
【功能模块调用关系图】
主程序模块
创建稀疏矩阵模块
运算稀疏矩阵模块
打印稀疏矩阵模块
【详细设计】
稀疏矩阵运算器
矩阵相乘
矩阵相加
矩阵相减
退出本系统
输入矩阵1
输入矩阵1
输入矩阵1
输入矩阵2
输入矩阵2
输入矩阵2
计算结果
计算结果
计算结果
typedefstruct{
introw;//行数
intcol;//列数
intv;//非零元素值
}triplenode;
typedefstruct{
triplenodedata[maxsize+1];//非零元三元组
introwtab[maxrow+1];//各行第一个非零元的位置表
intmu,nu,tu;//矩阵的行数、列数和非零元个数
}rtripletable;
voidcreat(rtripletable&A)//创建稀疏矩阵
voidprint(rtripletableA)//输出稀疏矩阵
intaddsmatrix(rtripletableM,rtripletableN)//矩阵相加
intsubsmatrix(rtripletableM,rtripletableN)//稀疏矩阵相减
voidmultsmatrix(rtripletableM,rtripletableN,rtripletable&Q)//稀疏矩阵相乘
四.实现
1.功能函数设计
ADTArray{
数据对象:
D={aij|0≤i≤b1-1,0≤j≤b2-1}
数据关系:
R={ROW,COL}
ROW={
COL={
基本操作:
CreateSMatrix(&M);//操作结果:
创建稀疏矩阵M.
PrintSMatrix(M);
//初始化条件:
稀疏矩阵M存在.
//操作结果:
输出稀疏矩阵M.
AddSMatrix(M,N,&Q);
//初始化条件:
稀疏矩阵M与N的行数和列数对应相等.
//操作结果:
求稀疏矩阵的和Q=M+N.
SubSMatrix(M,N,&Q);
//初始化条件:
稀疏矩阵M与N的行数和列数对应相等.
//操作结果:
求稀疏矩阵的差Q=M-N.
MultSMatrix(M,N,&Q);
//初始化条件:
稀疏矩阵M的列数等于N的行数.
//操作结果:
求稀疏矩阵的乘积Q=M*N.
}ADTArray
【源程序】
#include
#include
#include
#definemaxsize100
#definemaxrow100
#defineOK1
#defineERROR-1
typedefstruct
{
introw;//行数
intcol;//列数
intv;//非零元素值
}triplenode;
typedefstruct
{
triplenodedata[maxsize+1];//非零元三元组
introwtab[maxrow+1];//各行第一个非零元的位置表
intmu,nu,tu;//矩阵的行数、列数和非零元个数
}rtripletable;
voidcreat(rtripletable&A)//创建稀疏矩阵
{
intk=1,sum=1,loop,p,t;
intnum[maxrow+1];
cout<<"请输入矩阵的行数和列数:
"< cout<<"行数: "; cin>>A.mu; cout<<"列数: "; cin>>A.nu; cout<<"非零元素个数: "; cin>>A.tu; cout<<"请以空格隔开的形式输入非零元的行、列、值."< for(loop=1;loop<=A.tu;loop++) { cin>>A.data[loop].row>>A.data[loop].col>>A.data[loop].v; } for(p=1;p<=A.mu;p++)num[p]=0; //A三元组每一列的非零元素个数 for(t=1;t<=A.tu;t++)++num[A.data[t].row]; //求A中每一列含非零元个数 A.rowtab[1]=1; //求第p列中第一个非零元在A.data中的序号 for(t=2;t<=A.mu;t++)A.rowtab[t]=A.rowtab[t-1]+num[t-1]; return; } voidprint(rtripletableA)//输出稀疏矩阵 { intresult[maxrow+1][maxrow+1]; intloop1,loop2; for(loop1=1;loop1<=A.mu;loop1++) for(loop2=1;loop2<=A.nu;loop2++) result[loop1][loop2]=0;//初始化为0 for(loop1=1;loop1<=A.tu;loop1++) result[A.data[loop1].row][A.data[loop1].col]=A.data[loop1].v; for(loop1=1;loop1<=A.mu;loop1++) { cout<<"|"; for(loop2=1;loop2<=A.nu;loop2++) cout< //输出所做运算的结果 cout<<"|"< } } intaddsmatrix(rtripletableM,rtripletableN)//矩阵相加 { if(M.mu! =N.mu)//行数相等才能相加 cout<<"出错"; rtripletableQ;Q.mu=M.mu;Q.nu=N.nu; intp,q,k; p=1;q=1;k=1; while(p<=M.tu&&q<=N.tu)//两个稀疏矩阵存在 { if(M.data[p].row==N.data[q].row)//两个稀疏矩阵的行数相等 { if(M.data[p].col==N.data[q].col)//两个稀疏矩阵的列数相等 { if(M.data[p].v+N.data[q].v! =0)//两个稀疏矩阵相加的结果不为0 { Q.data[k].row=M.data[p].row; Q.data[k].col=M.data[p].col; Q.data[k].v=M.data[p].v+N.data[q].v;++k; } ++q;++p; } elseif(M.data[p].col { Q.data[k]=M.data[p];//把M中的所有信息都赋给Q ++p;++k; } else //第一个稀疏矩阵列数大于第二个稀疏矩阵的列数 { Q.data[k]=N.data[q];++q;++k; } } elseif(M.data[p].row //第一个稀疏矩阵行列数小于第二个稀疏矩阵行数 { Q.data[k]=M.data[p];++p;++k; } else //第一个稀疏矩阵行列数小于第二个稀疏矩阵行数 { Q.data[k]=N.data[q];++q;++k; } } while(p<=M.tu)//只有M并且符合条件 { Q.data[k]=M.data[p];++p;++k; } while(q<=N.tu)//只有N并且符合条件 { Q.data[k]=N.data[q]; ++q;++k; } Q.tu=k-1; cout<<"加法结果为: "< print(Q);//调用print() returnOK; } intsubsmatrix(rtripletableM,rtripletableN)//稀疏矩阵相减 { if(M.mu! =N.mu)//行数相等才能相减 cout<<"出错"; rtripletableQ; Q.mu=M.mu; Q.nu=N.nu; intp,q,k; p=1;q=1;k=1; while(p<=M.tu&&q<=N.tu)//两个稀疏矩阵存在 { if(M.data[p].row==N.data[q].row)//两个稀疏矩阵的行数相等 { if(M.data[p].col==N.data[q].col)//两个稀疏矩阵的列数相等 { if(M.data[p].v-N.data[q].v! =0)//两个稀疏矩阵相减的结果不为0 { Q.data[k].row=M.data[p].row; Q.data[k].col=M.data[p].col; Q.data[k].v=M.data[p].v-N.data[q].v; ++k; } ++q;++p; } if(M.data[p].col //第一个稀疏矩阵列数小于第二个稀疏矩阵的列数 { Q.data[k]=M.data[p]; ++p;++k; } if(M.data[p].col>N.data[q].col) //第一个稀疏矩阵列数大于第二个稀疏矩阵的列 { Q.data[k].row=N.data[q].row; Q.data[k].col=N.data[q].col; Q.data[k].v=-N.data[q].v; ++q;++k; } } if(M.data[p].row //第一个稀疏矩阵行列数小于第二个稀疏矩阵行数 { Q.data[k]=M.data[p]; ++p;++k; } if(M.data[p].row>N.data[q].row) //第一个稀疏矩阵行列数大于第二个稀疏矩阵行数 { Q.data[k].row=N.data[q].row; Q.data[k].col=N.data[q].col; Q.data[k].v=-N.data[q].v;++q;++k; } } while(p<=M.tu)//只有M并且符合条件 { Q.data[k]=M.data[p];++p;++k; } while(q<=N.tu)//只有N并且符合条件 { Q.data[k].row=N.data[q].row; Q.data[k].col=N.data[q].col; Q.data[k].v=-N.data[q].v; ++q;++k; } Q.tu=k-1; cout<<"减法结果为: "< print(Q);//调用print() returnOK; } voidmultsmatrix(rtripletableM,rtripletableN,rtripletable&Q)//稀疏矩阵相乘 { intarow,brow; intp,q,tp,t; intccol; intctemp[maxrow+1];//定义累加器 if(M.nu! =N.mu)return; Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//Q初始化 if(M.tu*N.tu! =0){//Q是非零矩阵 for(arow=1;arow<=M.mu;arow++) //处理M的每一行 { for(p=1;p<=Q.nu;p++)//处理M的每一列 ctemp[p]=0;//当前行各元素累加器清零 Q.rowtab[arow]=Q.tu+1; if(arow elsetp=M.tu+1; for(p=M.rowtab[arow];p //对当前行中每一个非零元 { brow=M.data[p].col;//找到对应元N中的行号 if(brow elset=N.tu+1; for(q=N.rowtab[brow];q { ccol=N.data[q].col;//乘积元素在Q中列数 ctemp[ccol]+=M.data[p].v*N.data[q].v; } }//求得Q中第crow(=arow)行的非零元 for(ccol=1;ccol<=Q.nu;ccol++) //压缩存储该行非零元 { if(ctemp[ccol]) { if(++Q.tu>maxsize)return; Q.data[Q.tu].row=arow;//行数 Q.data[Q.tu].col=ccol;//列数 Q.data[Q.tu].v=ctemp[ccol]; //累加非零元素值 } } } } cout<<"乘法结果为: "< print(Q);//调用print() } voidmain() { charchoice; rtripletableA,B,Q; cout<<"--------------------------------------------------\n"; cout<<"|*****欢迎使用稀疏矩阵运算器******|\n"; cout<<"|=============================|\n"; cout<<"\n|A、输入矩阵1|\n"; cout<<"\n|B、输入矩阵2|\n"; cout<<"\n|C、矩阵相加|\n"; cout<<"\n|D、矩阵相减|\n"; cout<<"\n|E、矩阵相乘|\n"; cout<<"\n|F、退出本系统|\n"; cout<<"\n|-----------------------------------------------|\n"; cout<<"请选择所需要的操作功能(A,B,C,D,E,F): "; do{ cin>>choice; switch(choice){ case'A': creat(A);break; case'B': creat(B);break; case'C': addsmatrix(A,B);break; case'D': subsmatrix(A,B);break; case'E': multsmatrix(A,B,Q);break; case'F': exit(0); }cout<<"请选择所需要的操作功能(A,B,C,D,E,F): "; }while (1); } 运行与测试 实验总结: 调试程序时,应注意矩阵的调用。 比如,开始时没有注意将程序调用! 尽管实现了矩阵的转置和相加,但没有符合题意。 在调试时,才意识到是以前经常发的一个错误,就是在最后加了一个return0,这是错误的! 在编写程序时体会到了团队合作的精神,这是将来走进社会不可缺少的! 实验成绩 学号 姓名 课题小组自评分数 最后得分 093821029 093821033 093821034 093821036
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计