实验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#includestruct linknodeint rows,cols;linknode *down,*right;union vnextint v;linknode *next;node;linknode *CreateMatlind() int i,j,maxlin;linknode *hm,*cp100,*p;printf(ntt请输入稀疏矩阵的行数，列数(用逗号隔开): );scanf(%d,%d,&i,&j);if (ij) maxlin=i;else maxlin=j;hm=new linknode;cp0=hm; for (int l=1;lrows=0;p-cols=0;p-down=p;p-right=p;cpl=p;cpl-1-node.next=p;cpmaxlin-node.next=hm;hm=new linknode;hm-rows=i;hm-cols=j;return hm; linknode *InputMatlind(linknode *hm,int s) linknode *cp100,*p,*q;int m,n,t;int i,j,k,maxlin;i=hm-rows;j=hm-cols;if (ij) maxlin=i;else maxlin=j;cp0=hm;for (int l=1;lrows=0;p-cols=0;p-down=p;p-right=p;cpl=p;cpl-1-node.next=p;cpmaxlin-node.next=hm;for (int x=0;xrows=m;p-cols=n;p-node.v=t;k=1;q=cpm;while (k)if (q-right=cpm) | (q-right-colsn)p-right=q-right;q-right=p;k=0;else if(q-right-cols=n)p-right=q-right-right;q-right=p;k=0;else if(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;else if (q-down-rows=m)p-down=q-down-down;q-down=p;k=0;else if (q-down-rowsdown;k=1;return hm;void ShowMatlind(linknode *hm) int m,n;linknode *p,*q;m=hm-rows;n=hm-cols;q=p=hm-node.next;p=p-right;coutendlendl;printf(ntt);for (int i=1;i=m;i+)for (int j=1;jrows=i) & (p-cols=j)printf(%8d,p-node.v);else printf(%8c,0);if (j=n) & (p-right=q)break;else if (p-right!=q)p=p-right;printf(nntt);p=q;q=p=p-node.next;p=p-right;void SearchMatlind(linknode *hm,int s) int m,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(ntt 行 列 值n);printf(ntt元素位置:%2d %2d %2dn,p-rows,p-cols,p-node.v);k=0;else if (p-right!=q)p=p-right;else p=q;q=p=p-node.next;if (p=hm)printf(ntt十字链表中无此元素! n);k=0;p=p-right;void main()int s,k,ch=1;linknode *hm=NULL;printf(tn新建十字链表:); hm=CreateMatlind(); do printf(ntt请输入非零元素个数: );scanf(%d,&s);if (s(hm-rows)*(hm-cols)printf(ntt元素个数超标! 应小于%d个n,hm-rows*hm-cols);k=1;elsek=0;while (k);hm=InputMatlind(hm,s); printf(n显示十字链表);if (hm=NULL)printf(ntt链表为空! n);elseShowMatlind(hm);printf(n查 找 元 素);if (hm=NULL)printf(ntt链表为空! n);elseprintf(ntt请输入您要查找的元素: );scanf(%d,&s);SearchMatlind(hm,s); 5、 测试数据与实验结果（可以抓图粘贴）6、 结果分析与实验体会实验结果基本达到了实验要求。用十字链表存储稀疏矩阵的基本思想是