数据结构实验---图的储存与遍历.doc

《数据结构实验---图的储存与遍历.doc》由会员分享，可在线阅读，更多相关《数据结构实验---图的储存与遍历.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程实验报告学号： 姓名： 实验日期： 2016.1.7实验名称： 图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS和BFS遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。测试数据：V0V1V4V3V2如图所示题目2：对以邻接表为存储结构的图进行DFS和BFS遍历问题描述：以邻接表为图的存储结构，实现图的DFS和BF

2、S遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS和BFS序列。测试数据：如图所示1 010 3 3 4 V0V1V2V3V4三、附录： 在此贴上调试好的程序。#include#include#include#define M 100 typedef struct node char vexM2; int edgeM M ; int n,e; Graph;int visitedM;Graph *Create_Graph() Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph);printf (请输入矩阵的顶点数和边数(用逗号

3、隔开)：n);scanf(%d,%d,&GA-n,&GA-e);printf (请输入矩阵顶点信息：n); for(i = 0;in;i+) scanf(%s,&(GA-vexi0),&(GA-vexi1); for (i = 0;in;i+) for (j = 0;jn;j+) GA-edgeij = 0; for (k = 0;ke;k+) printf (请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：,k+1); scanf (%d,%d,%d,&i,&j,&w); GA-edgeij = w; return(GA);void dfs(Graph *GA, int v) in

4、t i; printf(%c%cn,GA-vexv0,GA-vexv1); visitedv=1; for(i=0; in; i+) if (GA-edgevi=1 & visitedi=0) dfs(GA, i);void traver(Graph *GA) int i; for(i=0; in; i+) visitedi=0; for(i=0; in;i+) if(visitedi=0) dfs(GA, i);void bfs( Graph *GA, int v) int j,k,front=-1,rear=-1; int QM; printf(%c%cn,GA-vexv0,GA-vexv

5、1); visitedv=1; rear=rear+1; Qrear=v; while (front!=rear) front=front+1;k=Qfront; for (j=0; jn; j+) if (GA-edgekj=1 & visitedj=0) printf(%c%cn,GA-vexj0,GA-vexj1); visitedj=1; rear=rear+1; Qrear=j; void traver1(Graph *GA) int i; for (i=0; in;i+) visitedi=0; for (i=0; in; i+) if (visitedi=0) bfs(GA, i

6、); typedef struct NODE int adjvex; struct NODE *next; ENode;typedef struct NODE1 char vex2; ENode *first; VexNode;typedef struct FS1VexNode GLM;int bian,top;FS;FS *CreateGL( ) FS *kk=(FS *)malloc(sizeof(FS); int i,j,k; ENode *s; printf(请输入顶点数和边数(用逗号隔开)：n); scanf(%d,%d,&kk-top, &kk-bian); printf(请输入顶

7、点信息：n); for (i=0; itop; i+) scanf(%s,kk-GLi.vex); kk-GLi.first=NULL; printf(请输入边的信息(i,j)：n); for (k=0;kbian;k+) scanf(n%d,%d,&i,&j); s =(ENode*)malloc(sizeof(ENode); s-adjvex=j; s-next=kk-GLi.first; kk-GLi.first =s; return kk;void DFS(FS *kk, int v) ENode *w; int i; printf(%sn,kk-GLv.vex); visitedv=

8、1; w=kk-GLv.first ; while (w!=NULL) i=w-adjvex; if (visitedi=0) DFS(kk,i); w=w-next; void TRAVER(FS *kk) int i; for(i=0; itop;i+) visitedi=0; for(i=0; itop; i+) if(visitedi=0) DFS(kk, i); void BFS(FS *kk, int v) int QM, front=-1,rear=-1; ENode *w; int i, k; printf(%sn,kk-GLv.vex); visitedv=1; rear=r

9、ear+1; Qrear=v; while (front!=rear) front=front+1; k=Qfront; w=kk-GLk.first; while(w!=NULL) i=w-adjvex; if( visitedi=0) visitedi=1; printf(%s,kk-GLi.vex); rear=rear+1; Qrear=i; w=w-next; void TRAVER1(FS *kk) int i; for(i=0; itop;i+) visitedi=0; for(i=0; i top;i+) if(visitedi=0) BFS(kk,i); int main()

10、 int i=0; Graph *p; FS *q; while(i=1) /*建立菜单*/char jz30=1.创建邻接矩阵;char jd30=2.邻接矩阵DFS遍历;char jb30=3.邻接矩阵BFS遍历;char bg30=4.创建邻接表;char bd30=5.邻接表DFS遍历;char bb30=6.邻接表BFS遍历;char tc30=7.退出;char mn30=菜单;int l=strlen(jd);int o=strlen(mn);int m,n;printf(n);for(m=0;m=(2*l-o)/2;m+)printf( );printf(%s,mn);for(

11、m=0;m=(2*l-o)/2;m+)printf( );printf(n);for(m=0;m=2*l;m+)printf(*);printf(n);printf(* %s *n* %s *n* %s *n* %s *n* %s *n* %s *n* %s *n,jz,jd,jb,bg,bd,bb,tc);for(m=0;m=2*l;m+)printf(*);printf(n);/*选择功能*/printf(请输入所需功能序号：);scanf(%d,&n);switch(n) case 1: p=Create_Graph();break; case 2: traver(p);break; case 3: traver1(p);break; case 4: q=CreateGL();break; case 5: TRAVER(q);break; case 6: TRAVER1(q);break;case 7: return 0;default:printf(输入功能序号有误！n); return 0;四、运行结果：在此把运行结果从屏幕上拷下来贴在此五、心得体会：测试数据要注意现实中矩阵是从1开始，而数组里是从0开始。