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

《实验6：稀疏矩阵十字链表的存储.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、电子信息学院实验报告书课程名：数据结构题目：稀疏矩阵十字链表的存储实验类别设计班级：BX1001学号：24姓名：肖望龙2011年10月23日《算法设计与分析》实验报告-9-1、实验题目（1)掌握稀疏矩阵十字链表存储的方法。（2)掌握稀疏矩阵的显示、查找等基本方法。2、实验内容（1）创建空的稀疏矩阵的十字链表存储结构。（2）稀疏矩阵十字链表的数据输入。（3）稀疏矩阵十字链表的数据显示。（4）稀疏矩阵十字链表的数据查找。3、实验要求（1）利用C或c++语言完成算法设计和程序设计。（2）上机调试通过实验程序。（3）输入右侧矩阵A，检验程序运行结果。（4）给出具体的算法分

2、析，包括时间复杂度和空间复杂度。（5）撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序⑴实验步骤1、建立一个空的十字链表2、输入链表信息3、输入链表元素4、查找链表元素5、显示链表元素⑵源代码#include#include#include#includestructlinknode{introws,cols;linknode*down,*right;《算法设计与分析》实验报告-9-unionvnext{intv;linknode*next

3、;}node;};linknode*CreateMatlind(){inti,j,maxlin;linknode*hm,*cp[100],*p;printf("tt请输入稀疏矩阵的行数，列数(用逗号隔开):");scanf("%d,%d",&i,&j);if(i>j)maxlin=i;elsemaxlin=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]->nod

4、e.next=p;}cp[maxlin]->node.next=hm;hm=newlinknode;hm->rows=i;《算法设计与分析》实验报告-9-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;elsemaxlin=j;cp[0]=hm;for(intl=1;l<=maxlin;l++){p=newlinknode

5、;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;xrows=m;p->cols=n;p->node.v=t;k=1;q=cp[m];while(k){if((q->right==cp[m]

6、)

7、

8、(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->colsright;k=1;}}k=1;q=cp[n];while(k){if((q->down==cp[n])

9、

10、(q->down->rows>m)){《算法设计与分析》实验报告-9-p->down=q->down;q->down=p;k=0;}elseif(q->d

11、own->rows==m){p->down=q->down->down;q->down=p;k=0;}elseif(q->down->rowsdown;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<

12、j<=n;