稀疏矩阵十字链表的存储

1、电子信息学院实验报告书课程名：数据结构题目：稀疏矩阵十字链表的存储实验类别：设计班级：BX1001学号：41姓名：赵艳2011年10月24日实验题目（1）掌握稀疏矩阵十字链表存储的方法。（2）掌握稀疏矩阵的显示，查找等基本算法。实验内容（1）创建空的稀疏矩阵十字链表存储结构。（2）稀疏矩阵十字链表的数据输入。（3）稀疏矩阵十字链表的数据显示。（4）稀疏矩阵十字链表的数据查找。实验要求利用C（C+）语言完成算法设计和程序设计。上机调试通过实验程序。输入右侧矩阵A，检验程序运行结果。给出具体的算法分析，包括时间复杂度和空间复杂度等。撰写实验报告。实验步骤与源程序实验步骤先定义各个需要的函数组成部分

2、，然后依次构建四个子函数，分别是新建十字链表、显示十字链表、输入链表元素、查找链表元素；然后是通过主函数对各个子函数的调用，来实现题目的目的。整个程序中主要用到指针定位，for循环，还有switch选择语句。其中对指针的运用很难，很难定位指针，而且指针太多，繁杂。源代码#include#include#include#includestructlinknodeintrows,cols;linknode*down,*right;unionvnextintv;linknode*next;node;；linknode*CreateMatlind();linknode*InputMatlind(lin

3、knode,int);voidShowMatlind(linknode);voidSearchMatlind(linknode*hm,ints);linknode*CreateMatlind()inti,j,maxlin;linknode*hm,*cp100,*p;printf(ntt请输入稀疏矩阵的行数，列数(用逗号隔开):);scanf(%d,%d,&i,&j);if(ij)maxlin=i;elsemaxlin=j;hm=newlinknode;cp0=hm;for(intl=1;lrows=0;p-cols=0;p-down=p;p-right=p;cpl=p;cpl-1-=p;cpm

4、axlin-=hm;hm=newlinknode;hm-rows=i;hm-cols=j;returnhm;linknode*InputMatlind(linknode*hm,ints)linknode*cp100,*p,*q;intm,n,t;inti,j,k,maxlin;i=hm-rows;j=hm-cols;if(ij)maxlin=i;elsemaxlin=j;cp0=hm;for(intl=1;lrows=0;p-cols=0;p-down=p;p-right=p;cpl=p;cpl-1-=p;cpmaxlin-=hm;for(intx=0;xrows=m;p-cols=n;p-=

5、t;k=1;q=cpm;while(k)(if(q-right=cpm)|(q-right-colsn)(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-colsright;k=1;k=1;q=cpn;while(k)if(q-down=cpn)|(q-down-rowsm)(p-down=q-down;q-down=p;k=0;elseif(q-down-rows=m)(p-down=q-down-down;q-down=p;k=0;

6、elseif(q-down-rowsdown;k=1;returnhm;voidShowMatlind(linknode*hm)(intm,n;linknode*p,*q;m=hm-rows;n=hm-cols;q=p=hm-;p=p-right;coutendlendl;printf(ntt);for(inti=1;i=m;i+)(for(intj=1;jrows=i)&(p-cols=j)(printf(%8d,p-;elseprintf(%8c,0);if(j=n)&(p-right=q)break;elseif(p-right!=q)p=p-right;printf(HnnttH);p

7、=q;q=p=p-;p=p-right;voidSearchMatlind(linknode*hm,ints)(intm,n,k;linknode*p,*q;m=hm-rows;n=hm-cols;q=p=hm-;p=p-right;k=1;while(k)if(p-=s)printf(ntt行歹U值n);printf(ntt元素位置:第2d行第2d列2dn,p-rows,p-cols,p-;k=0;elseif(p-right!=q)p=p-right;elsep=q;q=p=p-；if(p=hm)printf(ntt十字链表中无此元素!n);k=0;p=p-right;voidmain()

8、ints,k,ch=1;intchoice;linknode*hm=NULL;while(ch)printf(n);printf（ntt稀疏矩阵的十字链表存储系统n）;printf(ntt*);TOC o 1-5 h zprintf(ntt*1-新建十字链表*);printf(ntt*2显示十字链表*);printf(ntt*3查找元素*);printf(ntt*0退出*);printf(nttprintf(nntt请输入菜单号:);scanf(%d,&choice);switch(choice)hm=CreateMatlind();doprintf（ntt请输入稀疏矩阵的非零元素个数:）;s

9、canf（%d,&s）;if(s(hm-rows)*(hm-cols)printf(ntt元素个数错误！应小于或等于djn,hm-rows*hm-cols);k=1;elsek=0;while(k);hm=InputMatlind(hm,s);break;if(hm=NULL)printf(ntt链表为空!n);break;elseShowMatlind(hm);break;if(hm=NULL)printf(ntt链表为空!n);break;elseprintf(ntt请输入您要查找的元素:);scanf(%d,&s);SearchMatlind(hm,s);break;case0:ch=0

10、;break;if(choice=1|choice=2|choice=3)printf(ntt);system(pause);system(cls);测试数据与实验结果（可以抓图粘贴）TOC o 1-5 h z2显示十宝铸哀*3喜般元素*0退出*请输入菜单号：1请输入稀疏矩阵的行数，列数（用逗号隔开4八请输入稀疏矩阵的非零元素个数,4请输入非零元素的行号，列号和值（用逗号隔开工1,1,2请输入非零元素的行号，列号和值（用逗号隔开3：2,2,3请输入非零元素的行号，列号和值用逗号隔开X3,3,4请输入非零元素的行号，列号和值（用逗号隔开”4,4,5请输入菜单号二3请输入您要查找的元素二3行列值元素位置;第2行第2列3请按任意键继续.6、结果分析与实验体会本次试验是稀疏矩阵十字链表的存储，通过这个实验，我们可以更好的掌握稀疏矩阵十字链表存储的方法，以及稀疏矩阵的显示，查找等一些基本算法。在实验中我们先定义对要定义的子函数进行声明，后建立新的存储结构，再后定义不同的子函数来实现稀疏矩阵十字链表的建立、显示、输入数据、查找