稀疏矩阵十字链表的存储.docx
- 文档编号:10765064
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:13
- 大小:39.64KB
稀疏矩阵十字链表的存储.docx
《稀疏矩阵十字链表的存储.docx》由会员分享,可在线阅读,更多相关《稀疏矩阵十字链表的存储.docx(13页珍藏版)》请在冰点文库上搜索。
稀疏矩阵十字链表的存储
电子信息学院
实验报告书
课程名:
数据结构
题目:
稀疏矩阵十字链表的存储
实验类别:
设计
班级:
BX1001
学号:
41
姓名:
赵艳
2011年10月24日
1、实验题目
(1)掌握稀疏矩阵十字链表存储的方法。
(2)掌握稀疏矩阵的显示,查找等基本算法。
2、实验内容
(1)创建空的稀疏矩阵十字链表存储结构。
(2)稀疏矩阵十字链表的数据输入。
(3)稀疏矩阵十字链表的数据显示。
(4)稀疏矩阵十字链表的数据查找。
3、实验要求
(1)利用C(C++)语言完成算法设计和程序设计。
(2)上机调试通过实验程序。
(3)输入右侧矩阵A,检验程序运行结果。
(4)给出具体的算法分析,包括时间复杂度和空间复杂度等。
(5)撰写实验报告。
4、实验步骤与源程序
实验步骤
先定义各个需要的函数组成部分,然后依次构建四个子函数,分别是新建十字链表、显示十字链表、输入链表元素、查找链表元素;然后是通过主函数对各个子函数的调用,来实现题目的目的。
整个程序中主要用到指针定位,for循环,还有switch选择语句。
其中对指针的运用很难,很难定位指针,而且指针太多,繁杂。
源代码
#include
#include
#include
#include
structlinknode
{
introws,cols;
linknode*down,*right;
unionvnext
{
intv;
linknode*next;
}node;
};
linknode*CreateMatlind();
linknode*InputMatlind(linknode,int);
voidShowMatlind(linknode);
voidSearchMatlind(linknode*hm,ints);
linknode*CreateMatlind()
{
inti,j,maxlin;
linknode*hm,*cp[100],*p;
printf("\n\t\t请输入稀疏矩阵的行数,列数(用逗号隔开):
");
scanf("%d,%d",&i,&j);
if(i>j)
maxlin=i;
else
maxlin=j;
hm=newlinknode;
cp[0]=hm;
for(intl=1;l<=maxlin;l++)
{
p=newlinknode;
p->rows=0;
p->cols=0;
p->down=p;
p->right=p;
cp[l]=p;
cp[l-1]->node.next=p;
}
cp[maxlin]->node.next=hm;
hm=newlinknode;
hm->rows=i;
hm->cols=j;
returnhm;
}
linknode*InputMatlind(linknode*hm,ints)
{
linknode*cp[100],*p,*q;
intm,n,t;
inti,j,k,maxlin;
i=hm->rows;
j=hm->cols;
if(i>j)
maxlin=i;
else
maxlin=j;
cp[0]=hm;
for(intl=1;l<=maxlin;l++)
{
p=newlinknode;
p->rows=0;
p->cols=0;
p->down=p;
p->right=p;
cp[l]=p;
cp[l-1]->node.next=p;
}
cp[maxlin]->node.next=hm;
for(intx=0;x
{
printf("\n\t\t请输入非零元素的行号,列号和值(用逗号隔开):
");
scanf("%d,%d,%d",&m,&n,&t);
p=newlinknode;
p->rows=m;
p->cols=n;
p->node.v=t;
k=1;
q=cp[m];
while(k)
{
if((q->right==cp[m])||(q->right->cols>n))
{
p->right=q->right;
q->right=p;
k=0;
}
elseif(q->right->cols==n)
{
p->right=q->right->right;
q->right=p;
k=0;
}
elseif(q->right->cols { q=q->right; k=1; } } k=1; q=cp[n]; while(k) { if((q->down==cp[n])||(q->down->rows>m)) { p->down=q->down; q->down=p; k=0; } elseif(q->down->rows==m) { p->down=q->down->down; q->down=p; k=0; } elseif(q->down->rows { q=q->down; k=1; } } } returnhm; } voidShowMatlind(linknode*hm) { intm,n; linknode*p,*q; m=hm->rows; n=hm->cols; q=p=hm->node.next; p=p->right; cout< printf("\n\t\t"); for(inti=1;i<=m;i++) { for(intj=1;j<=n;j++) { if((p->rows==i)&&(p->cols==j)) { printf("%8d",p->node.v); } else printf("%8c",'0'); if((j==n)&&(p->right==q)) break; elseif(p->right! =q) p=p->right; } printf("\n\n\t\t"); p=q; q=p=p->node.next; p=p->right; } } voidSearchMatlind(linknode*hm,ints) { intm,n,k; linknode*p,*q; m=hm->rows;n=hm->cols; q=p=hm->node.next; p=p->right; k=1; while(k) { if((p->node.v)==s) { printf("\n\t\t行列值\n"); printf("\n\t\t元素位置: 第%2d行第%2d列%2d\n",p->rows,p->cols,p->node.v); k=0; } elseif(p->right! =q) p=p->right; else { p=q; q=p=p->node.next; if(p==hm) { printf("\n\t\t十字链表中无此元素! \n"); k=0; } p=p->right; } } } voidmain() { ints,k,ch=1; intchoice; linknode*hm=NULL; while(ch) { printf("\n"); printf("\n\t\t稀疏矩阵的十字链表存储系统\n"); printf("\n\t\t********************************************"); printf("\n\t\t*1-----新建十字链表*"); printf("\n\t\t*2-----显示十字链表*"); printf("\n\t\t*3-----查找元素*"); printf("\n\t\t*0-----退出*"); printf("\n\t\t********************************************"); printf("\n\n\t\t请输入菜单号: "); scanf("%d",&choice); switch(choice) { case1: hm=CreateMatlind(); do { printf("\n\t\t请输入稀疏矩阵的非零元素个数: "); scanf("%d",&s); if(s>((hm->rows)*(hm->cols))) { printf("\n\t\t元素个数错误! 应小于或等于%d个\n",hm->rows*hm->cols); k=1; } else k=0; }while(k); hm=InputMatlind(hm,s); break; case2: if(hm==NULL) { printf("\n\t\t链表为空! \n"); break; } else { ShowMatlind(hm); break; } case3: if(hm==NULL) { printf("\n\t\t链表为空! \n"); break; } else { printf("\n\t\t请输入您要查找的元素: "); scanf("%d",&s); SearchMatlind(hm,s); break; } case0: ch=0; break; } if(choice==1||choice==2||choice==3) { printf("\n\t\t"); system("pause"); system("cls"); } } } 5、测试数据与实验结果(可以抓图粘贴) 6、结果分析与实验体会 本次试验是稀疏矩阵十字链表的存储,通过这个实验,我们可以更好的掌握稀疏矩阵十字链表存储的方法,以及稀疏矩阵的显示,查找等一些基本算法。 在实验中我们先定义对要定义的子函数进行声明,后建立新的存储结构,再后定义不同的子函数来实现稀疏矩阵十字链表的建立、显示、输入数据、查找等基本运算。 在实验编程中,我遇到了很多问题,因为课上有些内容老师还没有仔细的分析,所以有部分内容还是很生疏,自己看的效率也没有听老师接受的多,经过网上搜索和同学讨论等途径,才勉强把问题解决了,通过这次试验编程,也让我了解到了好好听老师课的重要性,还有课前预习,预习中剩下的还有的不明白得地方,在上课老师讲课过程中可以更加有取舍的听。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 稀疏 矩阵 十字 存储