数据图 Word 文档 .doc

《数据图 Word 文档 .doc》由会员分享，可在线阅读，更多相关《数据图 Word 文档 .doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程名称 数据结构实验 成绩 实验项目 图 指导教师 曹东燕 学生姓名 董晓亚 学号 0 班级专业 电子信息工程 实验地点 综合楼236 实验日期 2012年12月15日 实习七 图一、实习目的熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。关于各种典型著名的复杂算法，在上机实习方面不做基本要求。更适合于安排大型课程设计。二、实习题1. 阅读理解上面第一个关于图的邻接矩阵的程序，做下列题目。（1） 根据教科书P157页的G2图（无向图），输入数据运行程序。（2） 再适当修改上述程序，使它适用于G1图（有向图），输

2、入数据运行程序。 提示：无向图的邻接矩阵是对称的，而有向图的邻接矩阵是非对称的。（3） 继续修改程序使之可以表示存储以下网（边上带权值的图）。62041235529815521554615298340石家庄西安郑州太原济南北京大同379283提示：城市名暂时用代号（1，2，）表示，在程序中以数组的下标表示城市名。62041235529815521554615298340石家庄西安郑州太原济南北京大同379283 它的邻接矩阵如下： 北京 郑州 大同 太原 石家庄 济南 西安 1 北京 0 329 283 470 2 郑州 0 412 615 620 3 大同 329 0 355 4 太原 35

3、5 0 345 1154 5 石家庄 283 412 345 0 298 1552 6 济南 470 615 298 0 7 西安 620 1154 1552 02. 调试运行上面第二个程序，即图的邻接链表存储的程序。解决下列问题。（1） 根据教科书P157页的G2图（无向图），输入数据运行程序。（2） 再适当修改程序使它适用于G1图（有向图），输入数据运行程序。 提示：有向图的邻接链表分为正邻接链表和逆邻接链表。3. 设计一个程序，建立图的邻接矩阵，并且进行图的深度优先遍历。结合第2题的图运行调试程序。图的一章中由各种典型、著名的复杂算法，在上机练习方面不做基本要求。更适合于安排大型课程设计

4、。学生只要彻底搞清基本概念、基本存储结构，经过努力是可以完成的。三、程序及运行结果无向图程序：# include # include # define MAX 20typedef int VexType;typedef VexType MgraphMAXMAX; /* Mgraph是二维数组类型标识符 */* 函数原形声明 */void creat_mg(Mgraph G);void out_mg(Mgraph G);Mgraph G1; /* G1是邻接矩阵的二维数组名 */int n,e,v0;/* 主函数 */void main() creat_mg(G1); out_mg(G1); /

5、* main */* 建立邻接矩阵 */void creat_mg(Mgraph G) int i,j,k; printf(n n,e=?); scanf(%d,%d, &n,&e); /* 输入顶点数n，边数e */ for(i=1; i=n;i+) for(j=1;j=n;j+) Gij=0; /* 如果是网，Gij=0该为Gij=32767（无穷）*/ for(k=1;k=e;k+) /* 组织边数的循环 */ printf(n vi,vj=?); scanf(%d,%d, &i,&j); /* 输入一条边的两个顶点编号i,j */ Gij=1; Gji=1; /* 无向图的邻接矩阵是对

6、称矩阵 */ /* 如果是网，还要输入边的权值w，再让Gij=w */ /* creat_mg */* 邻接矩阵简单输出，为了检查输入是否正确 */ void out_mg(Mgraph G) int i,j; char ch; for(i=1; i=n;i+) /* 矩阵原样输出 */ printf(n ); for(j=1;j=n;j+) printf(%5d,Gij); /* 输出所存在的边 */ for(i=1; i=n;i+) for(j=1;j=n;j+) if(Gij=1)printf(n 存在边,i,j); printf(nn 打回车键，继续。); ch=getchar();

7、/* out_mg */有向图程序# include # include # define MAX 20typedef int VexType;typedef VexType MgraphMAXMAX; /* Mgraph是二维数组类型标识符 */* 函数原形声明 */void creat_mg(Mgraph G);void out_mg(Mgraph G);Mgraph G1; /* G1是邻接矩阵的二维数组名 */int n,e,v0;/* 主函数 */void main() creat_mg(G1); out_mg(G1); /* main */* 建立邻接矩阵 */void creat

8、_mg(Mgraph G) int i,j,k; printf(n n,e=?); scanf(%d,%d, &n,&e); /* 输入顶点数n，边数e */ for(i=1; i=n;i+) for(j=1;j=n;j+) Gij=0; /* 如果是网，Gij=0该为Gij=32767（无穷）*/ for(k=1;k=e;k+) /* 组织边数的循环 */ printf(n =?); scanf(%d,%d, &i,&j); /* 输入一条边的两个顶点编号i,j */ Gij=1; /* 有向图的邻接矩阵是非对称矩阵 */ /* 如果是网，还要输入边的权值w，再让Gij=w */ /* cr

9、eat_mg */* 邻接矩阵简单输出，为了检查输入是否正确 */ void out_mg(Mgraph G) int i,j; char ch; for(i=1; i=n;i+) /* 矩阵原样输出 */ printf(n ); for(j=1;j=n;j+) printf(%5d,Gij); /* 输出所存在的边 */ for(i=1; i=n;i+) for(j=1;j=n;j+) if(Gij=1)printf(n 存在边,i,j); printf(nn 打回车键，继续。); ch=getchar(); /* out_mg */无向图运行结果： 有向图运行结果：# include #

10、include # define MAX 20typedef int VexType;typedef VexType MgraphMAXMAX; /* Mgraph是二维数组类型标识符 */* 函数原形声明 */void creat_mg(Mgraph G);void out_mg(Mgraph G);Mgraph G1; /* G1是邻接矩阵的二维数组名 */int n,e,v0;/* 主函数 */void main() creat_mg(G1); out_mg(G1); /* main */* 建立邻接矩阵 */void creat_mg(Mgraph G) int i,j,k,w; pr

11、intf(n n,e=?); scanf(%d,%d, &n,&e); /* 输入顶点数n，边数e */ for(i=1; i=n;i+) for(j=1;j=n;j+) Gij=32767; /* 如果是网，Gij=0该为Gij=32767（无穷）*/ for(k=1;k=e;k+) /* 组织边数的循环 */ printf(n vi,vj,w=？); scanf(%d,%d,%d, &i,&j,&w); /* 输入一条边的两个顶点编号i,j */ Gij=w; Gji=w; /* 无向图的邻接矩阵是对称矩阵 */ /* 如果是网，还要输入边的权值w，再让Gij=w */ /* creat_

12、mg */* 邻接矩阵简单输出，为了检查输入是否正确 */ void out_mg(Mgraph G) int i,j; char ch; for(i=1; i=n;i+) /* 矩阵原样输出 */ printf(n ); for(j=1;j=n;j+) printf(%5d,Gij); /* 输出所存在的边 */ for(i=1; i=n;i+) for(j=1;j=n;j+) if(Gij=1)printf(n 存在边,i,j); printf(nn 打回车键，继续。); ch=getchar(); /* out_mg */（2）实习二与实习三的程序及结果# include # inclu

13、de # define MAX 20typedef int VexType;typedef struct Vnode VexType data; struct Vnode *next; Vnode; /* Vnode是顶点的结点结构 */typedef Vnode LgraphMAX; /* Lgraph是一维数组类型标识符 */* 函数原形声明 */void creat_L(Lgraph G);void out_L(Lgraph G);void dfsL(Lgraph G,int v);int n,e,z,visMAX; Lgraph Ga; /* Ga是邻接链表的表头数组名 */* 主函数

14、 */void main() int v1,i; char ch; do printf(nn 1. 无向链表邻接矩阵); printf(nn 2. 有向链表邻接矩阵); printf(nn 3. 有向链表逆邻接矩阵); printf(nn 4. 结束程序运行); printf(nn 请输入您的选择 (1,2,3,4); scanf(%d,&z);if(z=1|z=2|z=3) for(i=0;iMAX;i+) visi=0; /* 顶点访问的标志数组 */creat_L(Ga); /* 建立图邻接链表Ga */ out_L(Ga); /* 输出邻接链表Ga */ printf(n ); pri

15、ntf(所要开始遍历的顶点v1=?); scanf(%d,&v1);dfsL(Ga,v1); /* 从顶点v1开始，对图Ga进行深度优先遍历 */printf(n=);while(z=1|z=2|z=3); printf(nn 打回车键，继续。); ch=getchar(); /* main */* 建立邻接链表 */void creat_L(Lgraph G) Vnode *p,*q; int i,j,k; printf(输入 n,e=?); scanf(%d,%d,&n,&e); for(i=1; i=n; i+) Gi.data=i; Gi.next=NULL; for(k=1;kdat

16、a=i; p-next=Gj.next; Gj.next=p; /* p结点链接到第j条链 */ if(z=1|z=2) q=(Vnode *)malloc(sizeof(Vnode); q-data=j; q-next=Gi.next; Gi.next=q; /* q结点链接到第i条链 */ /* creat_L */* 邻接链表的简单输出，为了检查输入是否正确 */void out_L(Lgraph G) int i; Vnode *p; for (i=1; idata); p=p-next; /* out_L */* 深度优先遍历图 */void dfsL(Lgraph G,int v) Vnode *p; int u=1; printf(%3d,Gv.data); visv=1; /* 顶点v被访问，标志置1 */ p=Gv.next; while(p) v=p-data; u+; if(visv=0) dfsL(G,v); /* 顶点v未被访问时继续遍历 */ p=p-next; if(un) for(v=1;v=n;v+) if(visv!=1)dfsL(G,v);break; return;/* dfs */3、执行过程