《数据结构大纲答案》由会员分享，可在线阅读，更多相关《数据结构大纲答案（14页珍藏版）》请在金锄头文库上搜索。
1、实验编号：6 四川师大数据结构实验报告 2015年 12 月 25 日计算机科学学院 2014 级 1 班 实验名称：图及其应用 姓名： 陈元玲 学号： 指导老师： 刘芳 实验成绩：_ _一.目的要求：（1） 通过完成本实验，掌握图的两种基本的存储结构（邻接矩阵、邻接表），以及图的基本算法实现（建立、遍历），并能运用图结构分析解决一些实际问题。（2） 本实验训练的要点是：图的两种基本存储结构，及各种操作的算法实现（建立、遍历、图的典型应用）。二.实验内容：（1） 建立无向图和有向图的邻接矩阵存储，计算顶点的度，并输出图的基本信息。/1.h#include #include #include #
2、include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 typedef int Status;/2.h#define INIFINITY 1000 / 最大值#define MAX_VERTEX_NUM 20 /最大顶点数typedef enumDG,DN,UDG,UDN GraphKind; /图的四种类型typedef char VertexType;typedef struct VertexType vexsMAX_VERTEX_NU
3、M; /顶点向量 int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵 int vexnum,arcnum;/顶点数和弧的数目 GraphKind kind;/图的种类MGraph;/3.hint LovateVex(MGraph G,VertexType v) for (int i=0;G.vexsi!=v;i+); return i;Status CreateUDN(MGraph &G)int i,j,k; VertexType v1,v2;int w;coutendlG.vexnumG.arcnum; coutendl输入图的顶点信息：; for (i=0
4、;iG.vexsi; for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) G.arcsij=INIFINITY; coutendl输入边的信息 v1,v2,wendl; for (k=0;kv1; cinv2; cinw; i=LovateVex(G,v1); j=LovateVex(G,v2); G.arcsij=w; G.arcsji=G.arcsij;/for k return OK; /CreateUDNStatus CreateDN(MGraph &G)int i,j,k; VertexType v1,v2;int w;coutendlG.ve
5、xnumG.arcnum; coutendl输入图的顶点信息：; for (i=0;iG.vexsi; for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) G.arcsij=INIFINITY; coutendl输入边的信息 v1,v2,wendl; for (k=0;kv1; cinv2; cinw; i=LovateVex(G,v1); j=LovateVex(G,v2); G.arcsij=w; /for k return OK; /CreateDNStatus CreateUDG(MGraph &G)int i,j,k; VertexType v
6、1,v2;int w;coutendlG.vexnumG.arcnum; coutendl输入图的顶点信息：; for (i=0;iG.vexsi; for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) G.arcsij=0; coutendl输入边的信息 v1,v2endl; for (k=0;kv1; cinv2; i=LovateVex(G,v1); j=LovateVex(G,v2); G.arcsij=1; G.arcsji=G.arcsij;/for k return OK; /CreateUDGStatus CreateDG(MGraph &
7、G)int i,j,k; VertexType v1,v2;int w;coutendlG.vexnumG.arcnum; coutendl输入图的顶点信息：; for (i=0;iG.vexsi; for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) G.arcsij=0; coutendl输入边的信息 v1,v2endl; for (k=0;kv1; cinv2; i=LovateVex(G,v1); j=LovateVex(G,v2); G.arcsij=1; /for k return OK; /CreateDGStatus CreateGraph
8、(MGraph &G) int kind; coutendl输入图的类型：0-DG,1-DN,2-UDG,3-UDN:kind; G.kind=(GraphKind)kind; switch (G.kind) case DG:return CreateDG(G); case DN:return CreateDN(G); case UDG:return CreateUDG(G); case UDN:return CreateUDN(G); default :return ERROR; /CreateGraphvoid PrintGraph(MGraph G) int i,j;coutendl图的
9、顶点数和边数：; coutsetw(3)G.vexnumsetw(3)G.arcnum; coutendl图的顶点信息：endl; for (i=0;iG.vexnum;i+) coutsetw(3)G.vexsi; coutendl图的邻接矩阵：endl; for (i=0;iG.vexnum;i+)coutendl;for (j=0;jG.vexnum;j+) if (G.arcsij=INIFINITY)coutsetw(5); else coutsetw(5)G.arcsij;/for icoutendl;void GraphDegree(MGraph G) int indegreeM
10、AX_VERTEX_NUM=0,outdegreeMAX_VERTEX_NUM=0; int i; switch (G.kind) case DN: case DG:FindIndegree(G,indegree); for (i=0;iG.vexnum;i+) coutendlG.vexsi的入度为 indegreei; coutendl; FindOutdegree(G,outdegree); for (i=0;iG.vexnum;i+) coutendlG.vexsi的出度为 outdegreei; break; case UDN: case UDG:FindOutdegree(G,outdegree); for (i=0;iG.vexnum;i+) coutendlG.vexsi的度为 outdegreei; break; coutendl;/GraphDegree/main.cpp#include 1.h#include 2.h#include 3.hvoid main() MGraph G; CreateGraph(G);/创建图 PrintGraph(G);/输出图 GraphDegree(G); /计算图中顶点的度，并输出 coutendl;（2） 建立有向图的邻接表存储表示，并根据存储计算顶点的出
