实验6：稀疏矩阵十字链表的存储.doc

电子信息学院 实验报告书 课程名： 数据结构 题 目： 稀疏矩阵十字链表的存储 实验类别 设计 班 级： BX1001 学 号： 24 姓 名： 肖望龙 2011年 10 月 23 日 实验题目 掌握稀疏矩阵十字链表存储的方法。 掌握稀疏矩阵的显示、查找等基本方法。 实验内容 创建空的稀疏矩阵的十字链表存储结构。 稀疏矩阵十字链表的数据输入。 稀疏矩阵十字链表的数据显示。 稀疏矩阵十字链表的数据查找。 实验要求 利用C或c++语言完成算法设计和程序设计。 上机调试通过实验程序。 输入右侧矩阵A，检验程序运行结果。 给出具体的算法分析，包括时间复杂度和空间复杂度。 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。 实验步骤与源程序 ⑴ 实验步骤 建立一个空的十字链表 输入链表信息 输入链表元素 查找链表元素 显示链表元素 ⑵ 源代码 #includeiostream.h #includestdio.h #includeiomanip.h #includestdlib.h struct linknode { int rows,cols; linknode *down,*right; union vnext { int v; linknode *next; }node; }; linknode *CreateMatlind() { int i,j,maxlin; linknode *hm,*cp[100],*p; printf(\n\t\t请输入稀疏矩阵的行数，列数(用逗号隔开): ); scanf(%d,%d,i,j); if (ij) maxlin=i; else maxlin=j; hm=new linknode; cp[0]=hm; for (int l=1;l=maxlin;l++) { p=new linknode; 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=new linknode; hm-rows=i; hm-cols=j; return hm; } linknode *InputMatlind(linknode *hm,int s) { linknode *cp[100],*p,*q; int m,n,t; int i,j,k,maxlin; i=hm-rows; j=hm-cols; if (ij) maxlin=i; else maxlin=j; cp[0]=hm; for (int l=1;l=maxlin;l++) { p=new linknode; 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 (int x=0;xs;x++) { printf(\n\t\t请输入非零元的行号，列号和值(用逗号隔开): ); scanf(%d,%d,%d,m,n,t); p=new linknode; p-rows=m; p-cols=n; p-node.v=t; k=1; q=cp[m]; while (k) { if ((q-right==cp[m]) || (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-colsn) { q=q-right; k=1; } } k=1; q=cp[n]; while (k) { if ((q-down==cp[n]) || (q-down-ro