实验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用来指向本列的下一个非零元素；行指针域指向本行的下一个非零元素‘
知道了这些，实验就方便了，虽然还有很多不完善。
但多做练习才能更加熟练的使用稀疏矩阵。
升级会员 