稀疏矩阵十字链表的存储

1、精选优质文档-倾情为你奉上电子信息学院实验报告书课程名： 数据结构 题 目： 稀疏矩阵十字链表的存储 实验类别： 设计 班 级： BX1001 学 号： 41 姓 名： 赵艳 2011年 10月 24日专心-专注-专业1、 实验题目（1）掌握稀疏矩阵十字链表存储的方法。（2）掌握稀疏矩阵的显示，查找等基本算法。2、 实验内容（1） 创建空的稀疏矩阵十字链表存储结构。（2） 稀疏矩阵十字链表的数据输入。（3） 稀疏矩阵十字链表的数据显示。（4） 稀疏矩阵十字链表的数据查找。3、 实验要求（1） 利用C（C+）语言完成算法设计和程序设计。（2） 上机调试通过实验程序。（3） 输入右侧矩阵A，检验程

2、序运行结果。（4） 给出具体的算法分析，包括时间复杂度和空间复杂度等。（5） 撰写实验报告。4、 实验步骤与源程序 实验步骤先定义各个需要的函数组成部分，然后依次构建四个子函数，分别是新建十字链表、显示十字链表、输入链表元素、查找链表元素；然后是通过主函数对各个子函数的调用，来实现题目的目的。整个程序中主要用到指针定位，for循环，还有switch选择语句。其中对指针的运用很难，很难定位指针，而且指针太多，繁杂。 源代码#include<iostream.h>#include<stdio.h>#include<iomanip.h>#include<st

3、dlib.h>struct linknodeint rows,cols;linknode *down,*right;union vnextint v;linknode *next;node;linknode *CreateMatlind(); linknode *InputMatlind(linknode,int);void ShowMatlind(linknode);void SearchMatlind(linknode *hm,int s);linknode *CreateMatlind() int i,j,maxlin;linknode *hm,*cp100,*p;printf(&

4、quot;ntt请输入稀疏矩阵的行数，列数(用逗号隔开): ");scanf("%d,%d",&i,&j);if (i>j) maxlin=i;else maxlin=j;hm=new linknode;cp0=hm; for (int l=1;l<=maxlin;l+)p=new linknode;p->rows=0;p->cols=0;p->down=p;p->right=p;cpl=p;cpl-1->node.next=p;cpmaxlin->node.next=hm;hm=new linkno

5、de;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 (i>j) maxlin=i;else maxlin=j;cp0=hm;for (int l=1;l<=maxlin;l+)p=new linknode;p->rows=0;p->cols=0;p->down=p;p->right=p

6、;cpl=p;cpl-1->node.next=p;cpmaxlin->node.next=hm;for (int x=0;x<s;x+)printf("ntt请输入非零元素的行号，列号和值(用逗号隔开): ");scanf("%d,%d,%d",&m,&n,&t);p=new linknode;p->rows=m;p->cols=n;p->node.v=t;k=1;q=cpm;while (k)if (q->right=cpm) | (q->right->cols>n)

7、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->cols<n)q=q->right;k=1;k=1;q=cpn;while (k)if (q->down=cpn) | (q->down->rows>m)p->down=q->down;q->down=p;k=0;else if (q->do

8、wn->rows=m)p->down=q->down->down;q->down=p;k=0;else if (q->down->rows<m)q=q->down;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;cout<<endl<<endl;printf("ntt");for (in

9、t i=1;i<=m;i+)for (int j=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;else if (p->right!=q)p=p->right;printf("nntt");p=q;q=p=p->node.next;p=p->ri

10、ght;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

11、)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;int choice;linknode *hm=NULL;while (ch)printf("n");printf("ntt 稀疏矩阵的十字链表存储系统n");printf("ntt*");printf("ntt* 1-新建十字链表 *");printf(&

12、quot;ntt* 2-显示十字链表 *");printf("ntt* 3-查 找 元 素 *");printf("ntt* 0-退 出 *");printf("ntt*");printf("nntt 请输入菜单号: ");scanf("%d",&choice);switch(choice)case 1:hm=CreateMatlind(); doprintf("ntt请输入稀疏矩阵的非零元素个数: ");scanf("%d",&

13、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); break;case 2:if (hm=NULL)printf("ntt链表为空! n");break;elseShowMatlind(hm);break;case 3:if (hm=NULL)printf("ntt链表为空! n");break;elsep

14、rintf("ntt请输入您要查找的元素: ");scanf("%d",&s);SearchMatlind(hm,s); break;case 0:ch=0;break;if (choice=1 | choice=2 | choice=3)printf("ntt");system("pause");system("cls");5、 测试数据与实验结果（可以抓图粘贴）6、 结果分析与实验体会本次试验是稀疏矩阵十字链表的存储，通过这个实验，我们可以更好的掌握稀疏矩阵十字链表存储的方法，以及稀疏矩阵的显示，查找等一些基本算法。在实验中我们先定义对要