第六次数据结构上机实验报告

《第六次数据结构上机实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、南京航空航天大学第1页（共1页）《数据结构》上机实验报告年第学期第次上机上机日期：年月日班号学号姓名一、调试成功程序及说明1、题目：1.图的深度优先和广度优先遍历；算法思想：在G中任选一顶点v为初始出发点（源点），则深度优先遍历可定义如下：首先访问出发点v,并将其标记为己访问过；然后依次从v出发搜索v的每个邻接点Wo若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至阁中所有和源点V有路径相通的顶点（亦称为从源点可达的顶点）均己被访问为止。源程序：#include#inc

2、ludeSdefincmax100//最大顶点个数typedefstruct//以下定义临接矩阵类型{intnumber;//顶点编号intinfo;//顶点其他信息，边的权值}VertexType;//顶点类型typedefstruct//图的定义{intedges[max][max];//邻接矩阵intn,c;//顶点数和弧数VertexTypevexs[max];//存放定点信息}MGraph;//图的邻接矩阵类型AdjListadjlist;intn,e;}ALGrap

3、h;intvisitcd[max];voidDispMat(MGraphg)//定义邻接表类型typedefstructANode//弧的结点结构类型{intadjvcx;//弧的重点位置，就是放值的structANode*nextarc;//指向下一条弧的指针intinfo;//存放弧的信息（权值）}ArcNodc;typedefstructVnode{intdata;//邻接表头结点的的类型ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[

4、max];//AdjList是邻接表类型，把大表变成几个小的连接到一起typedefstruct//邻接表//图中顶点数和和边数//图的邻接表类型//全局数组用于判断后面节点是否被访问过//输出邻接矩阵inti，j;for(i=0;i〈g.n;i++)for(j=0;j

5、//将邻接矩陈g转换为邻接表inti,j;intn=g.n;//n为顶点数ArcNodc*p;//弧节点结构的类型G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i

6、rcNode));//新中请一个节点空间，就是后而的一段段小的节点p->adjvex=j;//这是小节点的放值的域，只要他的列值，链式表只要说明节点之间有关系就行，指终点位置p->info=g.edges[i][j];//存放边的权值p->ncxtarc=G->adjlistEi].firstarc;//将*卩连接到表后G->adjlist[i].firstarc=p;}G->c=g.e;G->n=g.n;}voidDispAdj(ALGraph*G)//输出邻接表{inti;ArcNode*p;

7、//弧的类型for(i=0;in;i++)p=G->adjlist[i].firstarc;if(p!=NULL)printfC%d:〃，i);//这是那个大链表的头while(p!=NULL)//顺着那个头向下查看{printf(〃％d〃，p->adjvex);//输出弧的终点p=p->ncxtarc;}printf("rT);}}voidchange(intvisitcd[],ALGraph*G)//给全局变量visited赋初值{inti;for(i=0;in;i++)vi

8、sited[i]=O;}voidListToMat(ALGraph*G，MGraphg)//将邻接表转换为邻接矩阵的形式{inti，j;intn=G-〉n;AreNode氺p;for(i=0;i〈n;i++)for(j=0;j〈n;j++)g.edges[i][j]=0;for(i=0;iadjlist[i].firstare;while(p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->ncxtarc;}}g.n=n