数据结构课程设计稀疏矩阵.docx
- 文档编号:18012818
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:43
- 大小:311.91KB
数据结构课程设计稀疏矩阵.docx
《数据结构课程设计稀疏矩阵.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计稀疏矩阵.docx(43页珍藏版)》请在冰点文库上搜索。
数据结构课程设计稀疏矩阵
稀疏矩阵应用
摘要本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵,并对稀疏矩阵进行转置,相加,相乘操作,最后输出运算后的结果。
在程序设计中,考虑到方法的难易程度,采用了先用三元组实现稀疏矩阵的输入,输出,及其转置,相加,相乘操作的方法,再在十字链表下实现。
程序通过调试运行,结果与预期一样,初步实现了设计目标。
关键词程序设计;稀疏矩阵;三元组;十字链表
1引言
1.1课程设计任务
本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵,并对稀疏矩阵进行转置,相加,相乘操作,最后输出运算后的结果。
稀疏矩阵采用三元组和十字链表表示,并在两种不同的存储结构下,求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C,并输出C;求出A的转置矩阵D,输出D;求两个稀疏矩阵A和B的相乘矩阵E,并输出E。
1.2课程设计性质
数据结构课程设计是重要地实践性教学环节。
在进行了程序设计语言课和《数据结构》课程教学的基础上,设计实现相关的数据结构经典问题,有助于加深对数据结构课程的认识。
本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现,包括在三元组和十字链表下存储稀疏矩阵,并对输入的稀疏矩阵进行转置,相加,相乘等操作,最后把运算结果输出。
此课程设计要求对数组存储结构和链表存储结构非常熟悉,并能熟练使用它们。
1.3课程设计目的
其目的是让我们在学习完C、数据结构等课程基础上,掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置,相加,相乘等基本操作,并用不同的方法输出结果,进一步掌握设计、实现较大系统的完整过程,包括系统分析、编码设计、系统集成、以及调试分析,熟练掌握数据结构的选择、设计、实现以及操作方法,为进一步的应用开发打好基础。
2需求分析
2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值
本模块要求设计函数建立稀疏矩阵并初始化,包括在三元组结构下和十字链表结构下。
首先要定义两种不同的结构体类型,在创建稀疏矩阵时,需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵,在输入出现错误时,能够对错误进行判别处理,初始化稀疏矩阵都为空值,特别注意在十字链表下,对变量进行动态的地址分配。
在设计输出稀疏矩阵的值的函数时,也要针对两种不同的情况,分别编制函数,才能准确的输出稀疏矩阵。
在对稀疏矩阵进行初始化及输出值时,均只输出非零元素的值和它所在的所在行及所在列。
2.2构造函数进行稀疏矩阵的转置并输出结果
本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果,由于对稀疏函数的转置只对一个矩阵进行操作,所以实现起来难度不是很大,函数也比较容易编写。
在编写函数时,要先定义一个相应的结构体变量用于存放转置后的矩阵,最后把此矩阵输出。
2.3构造函数进行两个稀疏矩阵相加及相乘并输出最终的稀疏矩阵
本模块要求设计相加和相乘函数对两个矩阵进行运算,并输出最终的稀疏矩阵,在进行运算前,要对两个矩阵进行检查,看是不是相同类型的矩阵,因为两个矩阵相加要求两个矩阵一定是同一类型的矩阵,定义相应的矩阵类型用于存放两个矩阵相加相乘后的结果矩阵,这个结果矩阵的行数列数需要综合多方面情况来确定。
这四个函数也是整个程序的难点,需要灵活运用数组及指针的特点。
2.4退出系统
本模块要求设置选项能随时结束程序的运行,本程序中采用exit(0)函数。
程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中需要的相关信息及命令。
3概要设计
3.1主界面设计
为了实现在两种存储结构下对稀疏矩阵的多种算法功能的管理,首先设计一个含有多
个菜单项的主控菜单子程序以链接系统的各项子功能,方便用户交互式使用本系统。
本系
统主控菜单运行界面如图1所示。
图1主界面图
3.2存储结构设计
本系统采用三元组结构和十字链表结构存储稀疏矩阵的具体信息。
其中:
在三元组中,所有元素的信息用数组表示,每个数组元素中包含有行下标(i),列下标(j)和对应的数值(e),它们是整型数据,全部的信息用在十字链表中,全部结点的信息用结构体(TSMatrix)包含,包括用数组(Tripledata[MAXSIZE])和总共的行数(mu),列数(nu)以及非零元素的个数(tu)。
在十字链表下,头结点为指针数组的十字链表存储;每个结点里面包含行下标(i),列下标(j)和对应的数值(e),它们是整型数据,还有两个指针(right)、(down),属于OLNode结构体。
全部的信息用结构体(crosslist)包含,包括指针数组(OLink*rhead和*chead)和总共的行数(mu),列数(nu)以及非零元素的个数(tu)。
三元组结构体定义:
typedefstruct{
inti,j;
inte;
}Triple;
typedefstruct{
Tripledata[MAXSIZE];
intrpos[MAXSIZE+1];
intnu,mu,tu;
}TSMatrix;
十字链表结构体定义:
typedefstructOLNode{
inti,j;
inte;
structOLNode*right,*down;
}OLNode,*OLink;
typedefstruct{
intmu,nu,tu;
OLink*rhead,*chead;
}CrossList;
3.3系统功能设计
本系统除了要完成分别在三元组存储结构以及在十字链表下实现稀疏矩阵的初始化功能外还设置了4个子功能菜单。
稀疏矩阵的建立及初始化在三元组存储结构下,由函数voidCreateSMatrix(TSMatrix&M)实现,在十字链表存储结构下,由函数voidCreateSMatix_OL(CrossList&M)依据读入的行数和列数以及非零元素的个数,分别设定每个非零元素的信息。
4个子功能的设计描述如下。
(1)稀疏矩阵的转置:
此功能在三元组存储结构下,由函数voidTransposeSMatrix(TSMatrixM,TSMatrix&T)实现,在十字链表存储结构下,由函数voidTurnSMatrix_OL(CrossList&M)实现。
当用户选择该功能,系统提示用户初始化一个矩阵,然后进行转置,最终输出结果。
(2)稀疏矩阵的加法:
此功能在三元组存储结构下,由函数voidAddTMatix(TSMatrixM,TSMatrixT,TSMatrix&S)实现,在十字链表存储结构下,由函数intSMatrix_ADD(CrossList*A,CrossList*B)实现。
当用户选择该功能,系统即提示用户初始化要进行加法的两个矩阵的信息。
然后进行加法,最后输出结果。
(3)稀疏矩阵的乘法:
此功能在三元组存储结构下,由函数intMultSMatrix(TSMatrixM,TSMatrixN,TSMatrix&Q)实现。
在十字链表存储结构下,由函数intMultSMatrix_OL(CrossListM,CrossListN,CrossList&Q)实现。
当用户选择该功能,系统提示输入要进行相乘的两个矩阵的详细信息。
然后进行相乘,最后得到结果。
(4)退出:
即退出稀疏矩阵的应用系统,由exit(0)函数实现。
当用户选择该功能,则退出该稀疏矩阵的应用系统。
4详细设计
4.1数据类型定义
三元组结构体定义:
typedefstruct{//三元组结构体
inti,j;//行标、列表
inte;//值
}Triple;
typedefstruct{
Tripledata[MAXSIZE];//三元组表
intrpos[MAXSIZE+1];
intnu,mu,tu;//行数、列数、非零元个数
}TSMatrix;
十字链表结构体定义:
typedefstructOLNode{//结点结构
inti,j;//行标、列标
inte;//值
structOLNode*right,*down;//同一行、列的下一个结点
}OLNode,*OLink;
typedefstruct{
intmu,nu,tu;//行数、列数、非零元个数
OLink*rhead,*chead;//行、列指针基指
}CrossList;
4.2系统主要子程序详细设计
A.主程序模块设计:
voidmain(){
intn,i;
TSMatrixM,T,S;//声明三个三元组数组
CrossListMM,TT,SS;//声明三个十字链表
printf("***稀疏矩阵应用***");
printf("\n请你选择创建稀疏矩阵的方法:
\n1:
用三元组创建稀疏矩阵\n2:
用十字链表创建稀疏矩阵\n3:
退出程序");
printf("\n");
scanf("%d",&n);
switch(n){
case1:
CreateSMatrix(M);//创建三元组矩阵
printf("您输入的稀疏矩阵为(只列出非零元素):
\n行列大小\n");
ShowTMatrix(M);//显示三元组矩阵
printf("已经选择三元组创建稀疏矩阵,请选择操作:
\n1:
稀疏矩阵转置\n2:
稀疏矩阵相加\n3:
稀疏矩阵相乘\n4:
退出程序\n");
scanf("%d",&i);
switch(i){
case1:
TransposeSMatrix(M,T);//对三元组矩阵进行转置
printf("转置后的矩阵为(只列出非零元素):
\n行列大小\n");
ShowTMatrix(T);
break;
case2:
printf("请你输入另一个稀疏矩阵:
");
CreateSMatrix(T);
AddTMatix(M,T,S);//两个三元组矩阵相加
printf("相加后的矩阵为(只列出非零元素):
\n行列大小\n");
ShowTMatrix(S);
break;
case3:
printf("请你输入另一个稀疏矩阵:
");
CreateSMatrix(T);
MultSMatrix(M,T,S);//两个三元组矩阵相乘
printf("相乘后的矩阵为(只列出非零元素):
\n行列大小\n");
ShowTMatrix(S);
break;
case4:
exit(0);};break;
case2:
{CreateSMatix_OL(MM);//创建十字链表矩阵
printf("您输入的稀疏矩阵为(只列出非零元素):
\n行列大小\n");
ShowMAtrix(&MM);//显示十字链表矩阵
printf("已经选择十字链表创建稀疏矩阵,请选择操作:
1:
稀疏矩阵转置\n2:
稀疏矩阵相加\n3:
稀疏矩阵相乘\n4:
退出程序\n");
scanf("%d",&i);
switch(i){
case1:
TurnSMatrix_OL(MM);//十字链表矩阵转置
printf("转置后的矩阵为(只列出非零元素):
\n行列大小\n");
ShowMAtrix(&MM);
break;
case2:
printf("请你输入另一个稀疏矩阵:
");
CreateSMatix_OL(TT);
SMatrix_ADD(&MM,&TT);//两个十字链表矩阵相加
printf("相加后的矩阵为(只列出非零元素):
\n行列大小\n");
ShowMAtrix(&MM);break;
case3:
printf("请你输入另一个稀疏矩阵:
");
CreateSMatix_OL(TT);
MultSMatrix_OL(MM,TT,SS);//两个十字链表矩阵相乘
printf("相乘后的矩阵为(只列出非零元素):
\n行列大小\n");
ShowMAtrix(&SS);break;
case4:
exit(0);
}};break;
case3:
exit(0);
default:
printf("erorr");
}
}
B.稀疏矩阵操作各子函数的定义:
(1)建立与初始化稀疏矩阵:
voidCreateSMatrix(TSMatrix&M){//采用三元组顺序表存储表示,创建稀疏矩阵M
printf("请输入稀疏矩阵的行数、列数和非零元个数:
");
scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(M.tu>M.mu*M.nu))
//判断行值、列值、元素个数是否合法
printf("输入有误!
");
for(inti=1;i<=M.tu;i++){//输入稀疏矩阵元素
printf("请输入元素坐标(所在行,所在列)及大小:
");
scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);
if((M.data[i].i<=0)||(M.data[i].j<=0)){
printf("输入错误,请重新输入");
scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);
}
}
intnum[100];
if(M.tu)
{inti;
for(i=1;i<=M.mu;i++)num[i]=0;//初始化
for(intt=1;t<=M.tu;t++)++num[M.data[t].i];
//求M中每一行含非零元素个数
//求rpos
M.rpos[1]=1;
for(i=2;i<=M.mu;i++)M.rpos[i]=M.rpos[i-1]+num[i-1];
}
}//创建三元组
intCreateSMatix_OL(CrossList&M){
inti,j,e;
OLinkq;
OLinkp;
printf("请输入稀疏矩阵的行数,列数,非零元素的个数");//矩阵行数,列数下标均从开始;
scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
M.rhead=(OLink*)malloc((M.mu+1)*sizeof(OLNode));//分配内存空间
M.chead=(OLink*)malloc((M.nu+1)*sizeof(OLNode));//分配内存空间
for(i=1;i<=M.mu;i++)M.rhead[i]=NULL;//把矩阵每个元素置空值
for(i=1;i<=M.nu;i++)M.chead[i]=NULL;
printf("请输入稀疏矩阵,如果行为,则退出\n");
scanf("%d%d%d",&i,&j,&e);
while(i!
=0){
p=(OLink)malloc(sizeof(OLNode));
p->i=i;p->j=j;p->e=e;
if(M.rhead[i]==NULL||M.rhead[i]->j>j){p->right=M.rhead[i];M.rhead[i]=p;}
else{
q=M.rhead[i];
while(q->right&&q->right->j
p->right=q->right;
q->right=p;}
if(M.chead[j]==NULL||M.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}
else{
q=M.chead[j];
while(q->down&&q->down->idown;
p->down=q->down;
q->down=p;
}
scanf("%d%d%d",&i,&j,&e);
}
return1;
}//创建十字链表
(2)输出稀疏矩阵:
voidShowTMatrix(TSMatrixM){
for(intcol=1;col<=M.mu;col++)
//通过双重循环,把稀疏矩阵中不为零的元素的行数、列数和值显示出来
for(intp=1;p<=M.tu;p++)
if(M.data[p].i==col)printf("%4d%4d%4d\n",M.data[p].i,M.data[p].j,M.data[p].e);
}//三元组显示
intShowMAtrix(CrossList*A){
intcol;
OLinkp;
for(col=1;col<=A->mu;col++)if(A->rhead[col]){p=A->rhead[col];
//通过循环,把A结点的rhead[col]赋给p
while(p){printf("%3d%3d%3d\n",p->i,p->j,p->e);p=p->right;}
}
return1;
}//十字链表显示
(3)实现矩阵的转置:
voidTransposeSMatrix(TSMatrixM,TSMatrix&T){
T.nu=M.mu;//T矩阵存放转置后的矩阵
T.mu=M.nu;
T.tu=M.tu;
intq=1;
for(intcol=1;col<=M.nu;col++)//通过循环,把非零元素的行数与列数进行交换,实现转置
for(intp=1;p<=M.tu;p++)
if(M.data[p].j==col){
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
q++;
}
}//三元组转置
voidTurnSMatrix_OL(CrossList&M){
intcol,row;//定义循环变量
OLinkp,q;//定义OLink结构类型变量
for(col=1;col<=M.mu;col++)//通过循环,把非零元素的行数与列数进行交换,实现转置
{q=p=M.rhead[col];
while(q){
row=p->i;
p->i=p->j;
p->j=row;
q=p->right;
p->right=p->down;
p->down=q;
}
}
}//十字链表转置
(4)实现两个矩阵的相加:
voidAddTMatix(TSMatrixM,TSMatrixT,TSMatrix&S){
//矩阵S存放相加后的矩阵
S.mu=M.mu>T.mu?
M.mu:
T.mu;//对S矩阵的行数赋值
S.nu=M.nu>T.nu?
M.nu:
T.nu;//对S矩阵的列数赋值
S.tu=0;
intce;
intq=1;intmcount=1,tcount=1;
while(mcount<=M.tu&&tcount<=T.tu){
switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data[tcount].j))
//用switch分支语句,用compare函数对需要相加的两个矩阵的某元素行数列数进行比较
{case-1:
S.data[q].e=M.data[mcount].e;//当M.data[mcount].i S.data[q].i=M.data[mcount].i; S.data[q].j=M.data[mcount].j; //把第一个矩阵的行数i,列数j赋值给S矩阵的行数i,列数j q++; mcount++; break; case1: S.data[q].e=T.data[tcount].e;//当M.data[mcount].i>T.data[tcount].i或M.data[mcount].j>T.data[tcount].j S.data[q].i=T.data[tcount].i; S.data[q].j=T.data[tcount].j; //把第二个矩阵的行数i,列数j赋值给S矩阵的行数i,列数j q++; tcount++; break; case0: ce=M.data[mcount].e+T.data[tcount].e; //其他情况下把两个矩阵的值相加 if(ce){S.data[q].e=ce; S.data[q].i=M.data[mcount].i; S.data[q].j=M.data[mcount].j; q++; mcount++; tcount++;} else{mcount++; tcount++;} break; }} while(mcount<=M.tu){ S.data[q].e=M.data[mcount].e; S.data[q].i=M.data[mcount].i; S.data[q].j=M.data[mcount].j; q++; mcount++;}//在case=-1的情况下对S矩阵的非零值,行数,列数进行赋值 while(tcount<=M.tu){ S.data[q].e=T.data[tcount].e; S.data[q].i=T.data[tcount].i; S.data[q].j=T.data[tcount].j; q++; tcount++; }//在case=1的情况下对S矩阵的非零值,行数,列数进行赋值 S.tu=q-1; }//三元组相加 intSMatrix_ADD(CrossList*A,CrossList*B){ OLNode*pa,*pb,*pre,*p,*cp[100];//定义OLNode类型的变量 inti,j,t; t=A->tu+B->tu; for(j=1;j<=A->nu;j++)cp[j]=A->chead[j];//将A矩阵的列表头指针赋给cp数组 for(i=1;i<=A->mu;i++){ pa=A->rhead[i]; pb=B->rhead[i];//将A,B矩阵的行表头指针分别赋给pa,pb pre=NULL; while(pb){//当pb不等于零 if(pa==NULL||pa->j>pb->j){ p=(OLink)malloc(sizeof(OLNode));//给p动态分配空间 if(! pre)A->rhead[i]=p; elsepre->right=p; p->right=pa; pre=p; p->i=i;p->j=pb->j;p->e=pb->e; if(! A->chead[p->j]){ A->chead[p->j]=cp[p->j]=p; p->down=NULL; }//如果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 稀疏 矩阵