《数据结构实验 - 图的储存与遍历(最新编写）-修订编选》由会员分享，可在线阅读，更多相关《数据结构实验 - 图的储存与遍历(最新编写）-修订编选（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程实验报告数据结构课程实验报告 学号学号： 姓名姓名： 实验日期实验日期： 2016.1.7 实验名称：实验名称： 图的存贮与遍历图的存贮与遍历 一、实验目的一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示， 以及在此两 种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤二、实验内容与实验步骤 题目题目 1：对以邻接矩阵为存储结构的图进行：对以邻接矩阵为存储结构的图进行 DFS 和和 BFS 遍历遍历 问题描述：问题描述：以邻接矩阵为图的存储结构，实现图的 DFS 和 BFS 遍历。 基本要求：基本要求：建立一个图的
2、邻接矩阵表示，输出顶点的一种 DFS 和 BFS 序列。 测试数据：测试数据：如图所示 题目题目 2：对以邻接表为存储结构的图进行：对以邻接表为存储结构的图进行 DFS 和和 BFS 遍历遍历 问题描述：问题描述：以邻接表为图的存储结构，实现图的 DFS 和 BFS 遍历。 基本要求：基本要求：建立一个图的邻接表存贮，输出顶点的一种 DFS 和 BFS 序列。 测试数据：测试数据：如图所示 V0 V1 V2 V3 V4 三、附录：三、附录： 在此贴上调试好的程序。在此贴上调试好的程序。 #include #include #include V0V1 V4V3 V2 01000 00001 01
3、010 10001 00010 A 1 0 1 0 3 3 4 #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 (请输入矩阵的顶点数和边数请输入矩阵的顶点数和边数(用逗号隔开用逗号隔开)：n); scanf(%d,%d, printf (请输入矩阵顶点信息：请输入矩阵顶点信息：n); for(i
4、 = 0;in;i+) scanf(%s, 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, GA-edgeij = w; return(GA); void dfs(Graph *GA, int v) int i; printf(%c%cn,GA-vexv0,GA-vexv1); visitedv=1; for(i=0; in; i+) if (
5、GA-edgevi=1 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-vexv1); visitedv=1; rear=rear+1; Qrear=v; while (front!=rear) front=front+1;k=Qfront; for (j=0; jn;
6、 j+) if (GA-edgekj=1 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); typedef struct NODE int adjvex; struct NODE *next; ENode; typedef struct NODE1 char vex2; ENode *first; VexNode; typedef struct FS1 VexNode
7、 GLM; int bian,top; FS; FS *CreateGL( ) FS *kk=(FS *)malloc(sizeof(FS); int i,j,k; ENode *s; printf(请输入顶点数和边数请输入顶点数和边数(用逗号隔开用逗号隔开)：n); scanf(%d,%d, printf(请输入顶点信息：请输入顶点信息：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,
8、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=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+) vi
9、sitedi=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=rear+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;
10、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() int i=0; Graph *p; FS *q; while(i=1) /*建立菜单建立菜单*/ char jz30=1.创建邻接矩阵创建邻接矩阵; char jd30=2.邻接矩阵邻接矩阵 DFS 遍历遍历; char jb30=3.邻接矩阵邻接矩阵 BFS
11、 遍历遍历; 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(m=0;m=(2*l-o)/2;m+) printf( ); printf(n); for(m=0;m=2*l;m+) printf(
12、*); 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, 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 开始。开始。
