课程设计实验报告-稀疏矩阵应用.docx
- 文档编号:1898383
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:11
- 大小:48.80KB
课程设计实验报告-稀疏矩阵应用.docx
《课程设计实验报告-稀疏矩阵应用.docx》由会员分享,可在线阅读,更多相关《课程设计实验报告-稀疏矩阵应用.docx(11页珍藏版)》请在冰点文库上搜索。
数据结构课程设计
《数据结构》课程设计
一.题目:
稀疏矩阵应用(限1人完成)
要求:
实现三元组,十字链表下的稀疏矩阵的加、转、乘的实现。
(1)稀疏矩阵的存储
(2)稀疏矩阵加法
(3)矩阵乘法
(4)矩阵转置
二.算法思想描述:
1.算法概述:
首先用两个结构体来定义十字链表元素:
typedefstructOLNode{
inti,j;inte;
structOLNode*right,*down;
}OLNode,*OLink;
OLNode结构为链表结点,i,j,e分别表示稀疏矩阵中元素的行,列和值。
typedefstruct{
intmu,nu,tu; //行数mu,列数nu,非零元素的个数tuOLink*rhead,*chead;
}CrossList;
CrossList结构用于连接起各个结点,mu,nu,tu分别表示整个矩阵的行数列数和非零元素的个数。
整个程序包含CreateSMatix_OL(用于创建十字链表),SMatrix_ADD(十字链表相加),ShowMAtrix(十字链表显示),MultSMatrix_OL(十字链表相乘),TurnSMatrix_OL(十字链表转置),DestroySMatrix_OL(十字链表销毁)六个函数。
CreateSMatix_OL的功能如下:
首先输入稀疏矩阵的行数,列数,非零元素的个数,为*rhead和*chead分配内存空间,并将十字链表中节点初始化为NULL。
然后依次输入非零元素的行,列,值,以000为结尾结束链表的连接和while循环。
SMatrix_ADD的功能如下:
在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵,连接结束后SMatrix_ADD函数以循环的方式比较非零元素是否为同一行列,如果是则两值相加,如果不是则把第二个元素加入链表中。
ShowMAtrix的功能如下:
逐一输出链表的行,列,值三个元素知道达到表尾的NULL。
MultSMatrix_OL的功能如下:
1
2
与相加类似,在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵,连接结束后MultSMatrix_OL函数以循环的方式比较非零元素是否为同一行列,如果是则两值相乘,如果不是则修改原来的元素值为0。
TurnSMatrix_OL的功能如下:
逐一查找十字链表中各个元素,将他们的i,j值对调已达到转置的目的.
2.算法具体分析
(1)、输入需要执行的操作:
1为创建稀疏矩阵,调用CreateSMatix_OL函数,输入稀疏矩阵的行数列数和非零元素的个数(如221,中间以空格分开)CreateSMatix_OL函数会将各个元素的信息保存在十字链表的结点中并连接起来。
2为退出程序。
(2)、选择接下来要执行的操作:
1为稀疏矩阵转置调用TurnSMatrix_OL函数逐一查找十字链表中各个元素,将他们的i,j值对调已达到转置的目的。
2为稀疏矩阵相加,调用SMatrix_ADD函数创建另一个稀疏矩阵并且将两矩阵中的非零元素相加。
3为稀疏矩阵相乘,调用MultSMatrix_OL函数创建另一个稀疏矩阵并且将两矩阵中的同行列的非零元素项相乘,其余项修改为0。
4为退出。
(3)、程序显示操作结果,运行正常,结果正确。
三、程序结构
ShowMAtrix()
函数
TurnSMatrix_OL()函数
SMatrix_ADD
();函数
ShowMAtrix()
函数
ShowMAtrix()
函数
MultSMatrix_OL()函数
CreateSMatix
_OL()函数
CreateSMatix
_OL();函数
exit()函数
Switch()函数
退出
CreateSMatix
_OL()函数
Switch()函数
main()函数
四、实验结果与分析
上述程序在VisualC++6.0环境下加以实现,经过多次的测试,程序运行正确。
例如:
输入1,再输入221接着输入非零元素为第2行第1列值为9(219).运行结果如图2,图中创建十字链表成功可以选择后续操作稀疏矩阵转置,稀疏矩阵相加,稀疏矩阵相乘。
图2
选择稀疏矩阵相加实验,输入2,再输入222创建另一个稀疏矩阵,接着输入119和21
1两个非零元素,SMatrix_ADD函数会将两个矩阵的非零元素相比较,在同行列的值相加,不在同行列的为十字链表添加结点,计算结果如图3,可以看到第一行第一列的元素9被加入到链表中,而第2行第1列的两个元素9和1相加得到10,程序运行成功。
11
图3
五.体会
通过这次课程设计,我有很深的体会,具体如下:
1.十字链表的建立,和使用有了更深层次的理解。
2.各种循环语句的使用和switch语句的应用比较熟悉了。
3.把各个功能写在不同的函数体里,分工明确,条理清晰,这样不但语句简洁,而且十分明了。
4.从用户角度出发来编写程序,使结果尽量简洁明了。
附代码:
#include
#defineMAXSIZE100intnum[100];
typedefstructOLNode{inti,j;
inte;
structOLNode*right,*down;
}OLNode,*OLink;
typedefstruct{
intmu,nu,tu; //行数mu,列数nu,非零元素的个数tuOLink*rhead,*chead;
}CrossList;
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("请输入元素的行列值。
最后输入000为结束\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
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;
}//创建十字链表
intCompare(inta1,intb1,inta2,intb2){if(a1>a2)return1;
elseif(a1 elseif(b1>b2)return1; if(b1 elsereturn0; } intSMatrix_ADD(CrossList*A,CrossList*B){OLNode*pa,*pb,*pre,*p,*cp[100]; inti,j,t;t=A->tu+B->tu; for(j=1;j<=A->nu;j++)cp[j]=A->chead[j];for(i=1;i<=A->mu;i++){ pa=A->rhead[i];pb=B->rhead[i];pre=NULL;while(pb){ if(pa==NULL||pa->j>pb->j){p=(OLink)malloc(sizeof(OLNode));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; } else{ cp[p->j]->down=p;cp[p->j]=p; } pb=pb->right; } elseif(pa->j elseif(pa->e+pb->e){t--; pa->e+=pb->e;pre=pa;pa=pa->right; pb=pb->right;}else{ t=t-2; if(! pre)A->rhead[i]=pa->right;elsepre->right=pa->right; p=pa;pa=pa->right; if(A->chead[p->j]==p)A->chead[p->j]=cp[p->j]=p->down;elsecp[p->j]->down=p->down; free(p);pb=pb->right; } } } A->mu=A->mu>B->mu? A->mu: B->mu;A->nu=A->nu>B->nu? A->nu: B->nu;return1; }//十字链表相加 intShowMAtrix(CrossList*A){intcol; OLinkp; for(col=1;col<=A->mu;col++)if(A->rhead[col]){p=A->rhead[col];while(p){printf("%3d%3d%3d\n",p->i,p->j,p->e);p=p->right;} } return1; }//十字链表显示 intMultSMatrix_OL(CrossListM,CrossListN,CrossList&Q) { inti,j,e; //中间变量 OLinkp0,q0,p,pl,pla; //中间变量 //检查稀疏矩阵M的列数和N的行数是否对应相等if(M.nu! =N.mu) { printf( "稀疏矩阵A的列数和B的行数不相等,不能相乘。 \n");return0; } Q.mu=M.mu,Q.nu=N.nu,Q.tu=0; if(! (Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink))))exit(-2); if(! (Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink))))exit(-2);for(i=1;i<=Q.mu;i++)Q.rhead[i]=NULL; for(i=1;i<=Q.nu;i++)Q.chead[i]=NULL; //相乘 for(i=1;i<=Q.mu;i++)for(j=1;j<=Q.nu;j++) { p0=M.rhead[i],q0=N.chead[j],e=0;while(p0&&q0)//M第i行和N第j列有元素 { 列指针后移行指针右移 if(p0->j>q0->i)q0=q0->down; //M的列大于N的行,则N的elseif(p0->j else{//M的行等于N的列 e+=p0->e*q0->e; //乘积累加q0=q0->down,p0=p0->right;//移动指针 } } if(e)//乘积不为0 { 赋值,指针后移 if(! (p=(OLink)malloc(sizeof(OLNode))))exit(-2); Q.tu++;//非零元素增加 p->i=i,p->j=j,p->e=e,p->right=NULL,p->down=NULL;// //将p插入十字链表 //行插入 if(Q.rhead[i]==NULL) //若p为该行的第1个结点Q.rhead[i]=pl=p; //p插在该行的表头且pl指 向p(该行的最后一个结点) elsepl->right=p,pl=p; //插在pl所指结点之后, pl右移 //列插入 if(Q.chead[j]==NULL) //若p为该列的第一个结点Q.chead[j]=p; //该列的表头指向p else{//插在列表尾 pla=Q.chead[j];//pla指向j行的第1个结点 while(pla->down)pla=pla->down;//pla指向j行最后一个结点pla->down=p; } } } return1; }//十字链表相乘 void TurnSMatrix_OL(CrossList&M){intcol,row; OLinkp,q;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; } } }//十字链表转置 intDestroySMatrix_OL(CrossList&M) { inti;//中间变量OLinkp,q;//中间变量 if(! M.rhead||! M.chead)return1;//M不存在else{//M存在 if(M.chead)//所有列链表头指针置为空for(i=1;i<=M.nu;i++)M.chead[i]=NULL; if(M.rhead)//按行释放节点for(i=1;i<=M.mu;i++) { p=M.rhead[i];while(p) { q=p,p=p->right;free(q); } } } }//十字链表销毁 voidmain(){ intn,i; //释放行和列链表头指针指向基址free(M.rhead); free(M.chead); //返回return1; //TSMatrixM,T,S;CrossListMM,TT,SS; printf("请你选择操作: \n1: 用十字建表创建稀疏矩阵。 \n2: 退出\n(1|2): ");scanf("%d",&n); switch(n){ case1: {CreateSMatix_OL(MM); printf("已经选择十字链表创建稀疏矩阵,请选择操作\n1: 稀疏矩阵转置\n2: 稀疏矩阵相加\n3: 稀疏矩阵相乘\n4: 退出\n(1|2|3|4): "); scanf("%d",&i);switch(i){case1: TurnSMatrix_OL(MM);ShowMAtrix(&MM);break; case2: printf("请你输入另一个稀疏矩阵: ");CreateSMatix_OL(TT);SMatrix_ADD(&MM,&TT);ShowMAtrix(&MM);break; case3: printf("请你输入另一个稀疏矩阵: ");CreateSMatix_OL(TT);MultSMatrix_OL(MM,TT,SS);ShowMAtrix(&SS);break; case4: exit(0); }};break; case2: exit(0); default: printf("erorr"); } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课程设计 实验 报告 稀疏 矩阵 应用