实验6稀疏矩阵十字链表的存储.docx
- 文档编号:4335364
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:11
- 大小:52.26KB
实验6稀疏矩阵十字链表的存储.docx
《实验6稀疏矩阵十字链表的存储.docx》由会员分享,可在线阅读,更多相关《实验6稀疏矩阵十字链表的存储.docx(11页珍藏版)》请在冰点文库上搜索。
实验6稀疏矩阵十字链表的存储
电子信息学院
实验报告书
课程名:
数据结构
题目:
稀疏矩阵十字链表的存储
实验类别设计
班级:
BX1001
学号:
24
姓名:
肖望龙
2011年10月23日
1、实验题目
(1)掌握稀疏矩阵十字链表存储的方法。
(2)掌握稀疏矩阵的显示、查找等基本方法。
2、实验内容
(1)创建空的稀疏矩阵的十字链表存储结构。
(2)稀疏矩阵十字链表的数据输入。
(3)稀疏矩阵十字链表的数据显示。
(4)稀疏矩阵十字链表的数据查找。
3、实验要求
(1)利用C或c++语言完成算法设计和程序设计。
(2)上机调试通过实验程序。
(3)输入右侧矩阵A,检验程序运行结果。
(4)给出具体的算法分析,包括时间复杂度和空间复杂度。
(5)撰写实验报告(把输入实验数据及运行结果用抓图的形式粘贴到实验报告上)。
4、实验步骤与源程序
实验步骤
1、建立一个空的十字链表
2、输入链表信息
3、输入链表元素
4、查找链表元素
5、显示链表元素
源代码
#include
#include
#include
#include
structlinknode
{
introws,cols;
linknode*down,*right;
unionvnext
{
intv;
linknode*next;
}node;
};
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; linknode*hm=NULL; printf("\t\n新建十字链表: "); 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); printf("\n显示十字链表"); if(hm==NULL) printf("\n\t\t链表为空! \n"); else ShowMatlind(hm); printf("\n查找元素"); if(hm==NULL) printf("\n\t\t链表为空! \n"); else { printf("\n\t\t请输入您要查找的元素: "); scanf("%d",&s); SearchMatlind(hm,s); } 5、测试数据与实验结果(可以抓图粘贴) 6、结果分析与实验体会 实验结果基本达到了实验要求。 用十字链表存储稀疏矩阵的基本思想是: 把每个非零元素作为一个节点存储,节点中除了表示元素的行、列、值的三元组(I,j,v)以外还增加了俩个指针域: 列指针域down用来指向本列的下一个非零元素;行指针域指向本行的下一个非零元素‘ 知道了这些,实验就方便了,虽然还有很多不完善。 但多做练习才能更加熟练的使用稀疏矩阵。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 稀疏 矩阵 十字 存储