数据结构实验指导书07

《数据结构实验指导书07》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验七图7.1实验目的：（1）熟悉图的邻接矩阵、邻接表的表示；（2）掌握建立图的邻接矩阵和邻接表的算法；（3）熟悉对图的邻接矩阵和邻接表表示分别进行深度和广度优先搜索遍历的算法。7.2实验要求：（1）复习课本中有关图的存储结构、深度和广度优先搜索遍历算法的知识；（2）用C语言完成算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括吋间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必耍吋给出多种可能的输入数据和运行结果）。7.3基础实验［实验1］图的邻接矩阵结构转换为邻接表结构实验内容与要求：编写一•个程序实现图的邻接

2、矩阵结构和邻接表结构的转换。分析：编写函数实现图的邻接矩阵结构，然麻编写函数实现转换。参考程序:#defineVEXTYPEint#defineADJTYPEint#defineMAXLEN40#include#includetypedefstruct{VEXTYPEvexsfMAXLENl;ADJTYPEarcs[MAXLEN][MAXLEN];intvexnum,arcnum;intkind;}MGRAPH;typedefstructnodc3{intadjvex;structnode3*next;}EDGENODE;typedefstruct{V

3、EXTYPEvertex;EDGENODE*link;intid;}VEXNODE;typedefstmctadjlist[MAXLENJ;vexnum,arcnum;kind;{VEXNODEintint}ADJGRAPH;MGRAPHcreate_mgraph(){/*建立图的邻接矩阵*/inti,j,k;MGRAPHmg;mg.kind=2;printf("输入顶点数和边数(用逗号隔开):");scanf(,,%d,%d,,,&i,&j);fflush(stdin);mg.vexnum=i;mg.arcnum=j;printf("H);for(i=();i

4、xnum;i++){printf(”输入顶点%d的值:”,i+1);scanf("%dH,&mg.vexs[i]);fflush(stdin);}for(i=0;img.vexnumlljmg.vexnum){printfC*输入错，重新输入:“)；

5、scanf(”％d,%d“,&i,&j);}mg.arcsli-lj[j-lj=l;mg.arcs[j-l][i-l]=l;}returnmg;}ADJGRAPHmg_to_adjg(MGRAPHmg){inti,j,n;ADJGRAPHadjg;EDGENODE*p：n=mg.vexnum;adjg.vexnum=mg.vexnum;adjg.arcnum=mg.arcnum;for(i=0;i

6、cs[i][j]==l){p=malloc(sizcof(EDGENODE));p->adjvex=j;p->next=adjg.adjlist[ij.link;adjg.adjlist[i].link=p;}}returnadjg;main(){MGRAPHmg;ADJGRAPHadjg;inti,j,n;EDGENODE*p;printf(M建立图的邻接矩阵并转换为图的邻接链表“);/*建立图的邻接矩阵*//*图的邻接矩阵显示*//*图的邻接矩阵结构转换为图的/*图的邻接链表显示*/mg=create_mgraph();printf("图的邻接矩阵显示:'*);n=

7、mg.vexnum;for(i=0;i[%d]”,i+1,j+1,mg.arcs[i][j]);printf(,,H);}adjg=mg_to_adjg(mg);邻接链表*/printfC^n");printf("图的邻接链表显示:");for(i=0;i%d,r,i,adjg.adjl