稀疏矩阵十字链表的存储.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、结果分析与实验体会
本次试验是稀疏矩阵十字链表的存储，通过这个实验，我们可以更好的掌握稀疏矩阵十字链表存储的方法，以及稀疏矩阵的显示，查找等一些基本算法。
在实验中我们先定义对要定义的子函数进行声明，后建立新的存储结构，再后定义不同的子函数来实现稀疏矩阵十字链表的建立、显示、输入数据、查找等基本运算。
在实验编程中，我遇到了很多问题，因为课上有些内容老师还没有仔细的分析，所以有部分内容还是很生疏，自己看的效率也没有听老师接受的多，经过网上搜索和同学讨论等途径，才勉强把问题解决了，通过这次试验编程，也让我了解到了好好听老师课的重要性，还有课前预习，预习中剩下的还有的不明白得地方，在上课老师讲课过程中可以更加有取舍的听。
升级会员 