《数据结构图实验报告,(2).docx》由会员分享，可在线阅读，更多相关《数据结构图实验报告,(2).docx（9页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑数据结构图实验报告,(2) 一、试验目得与要求 （1)把握图得相关概念，包括图,有向图,无向图，完全图，子图,连通图,度,入度，出度,简洁回路与环等定义. （2）重点把握图得各种存储结构，包括邻接矩阵与邻接表等。 (3）重点把握图得基本运算，包括创建图,输出图,深度优先遍历,广度优先遍历等. （4）把握图得其她运算 ,包括最小生成树,最短路径，拓扑排序与关键路径等算法。 (5)敏捷运用图这种数据结构解决一些综合应用问题。 二、试验内容与方法 （1）试验内容: 、编写一个程序 alo8-1、cpp，实现不带权图与带权图得邻接矩阵与邻接表得相互转换算法、输出邻接
2、矩阵与邻接表得算法，并在此基础上设计一个程序 exp8、cp实现如下功能: 建立如图 1 所示得有向图 G 得邻接矩阵,并输出; 由有向图得邻接矩阵产生邻接表,并输出; 再由得邻接表产生对应得邻接矩阵,并输出。 图 1 2、编写一个程序lgo82、cpp，实现图得遍历运算,并在此基础上设计一个程序xp82、cpp 完成如下功能： 输出图 1 所示得有向图从顶点 0 开头得深度优先遍历序列（递归算法）； 输出图所示得有向图 G 从顶点 0 开头得深度优先遍历序列（非递归算法); 输出图 1 所示得有向图 G 从顶点 0 开头得广度优先遍历序列。 、设计一个程序 exp83、cpp,采纳邻接表存储
3、图，并输出图 8、1(a）中从指定顶点 1动身得全部深度优先遍历序列。 (2)试验方法: 1、综合运用课本所学得学问，用不同得算法实现在不同得程序功能. 2、结合指导老师得指导，解决程序中得问题，正确解决实际中存在得特别状况，逐步改善功能。 3、依据试验内容，编译程序。 三、试验环境： Winows 7,Visul C+6、0 三、试验过程描述 文件raph、h 中定义了图得邻接矩阵表示类型与邻接表表示类型,该头文件在以下三个试验中都会使用到。其代码如下： 1 5 6 9 7 5 8 4 5 3 0 1 5 2 4 3 #ifndef GRAPH_H_INCLUDED #define GRAP
4、H_H_INCLUDED typedef int InfoType; #define MAXV 100 /最大顶点个数 #define INF 32767 /INF 表示无限大 VertexType vexsMAXV; MGraph; /以下定义邻接表类型 typedef struct ANode 试验 源程序。 一、输入如下所示程序; 二、编译并链接程序; 三、运行程序，结果如下图: 试验 错误! 源程序 一、输入如下所示程序; 二、对程序进行编译链接； 三、运行该程序,结果如图 /文件名:exp8-1、cpp #include stdio、h #include malloc、h #incl
5、ude graph、h extern void MatToList1(MGraph, ALGraph* ); extern void ListToMat1(ALGraph*, MGraph); extern void DispMat1(MGraph); extern void DispAdj1(ALGraph*); int main() int i,j; MGraph g,g1; ALGraph *G; int AMAXV6 = 0,5,INF,7,INF,INF,INF,0,4,INF,INF,INF, 8,INF,0,INF,INF,9,INF,INF,5,0,INF,6, INF,INF
6、,INF,5,0,INF,3,INF,INF,INF,1,0; g、n = 6; g、e = 10; for(i=0; ig、n; i+) for(j=0; jg、n; j+) g、edgesij = Aij; printf(有向图 G 得邻接矩阵:n); DispMat1(g); G = (ALGraph*)malloc(sizeof(ALGraph); printf(图 G 得邻接矩阵转换成邻接表:n); MatToList1(g,G); DispAdj1(G); printf(图 G 得邻接表转换成邻接矩阵:n); ListToMat1(G,g1); DispMat1(g1); retu
7、rn 0; /文件名:algo8-1、cpp #include stdio、h #include malloc、h #include graph、h /不带权图得算法 void MatToList(MGraph g, ALGraph *G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; ig、n; i+) for(j = g、n-1; j=0; j-) if(g、edgesij!=0) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-nextar
8、c = G-adjlisti、firstarc; G-adjlisti、firstarc = p; G-n = g、n; G-e = g、e; void ListToMat(ALGraph *G,MGraph g) int i,j; ArcNode *p; for(i=0; iG-n; i+) for(j=0; jG-n; j+) g、edgesij = 0; for(i=0; iG-n; i+) p = G-adjlisti、firstarc; while(p!=NULL) g、edgesip-adjvex = 1; p = p-nextarc; g、n = G-n; g、e = G-e;
9、void DispMat(MGraph g) int i,j; for(i=0; ig、n; i+) for(j=0; jg、n; j+) printf(%3d,g、edgesij); printf(n); void DispAdj1(ALGraph *G) int i; ArcNode *p; for(i=0; iG-n; i+) p = G-adjlisti、firstarc; printf(%3d:,i); while(p!=NULL) printf(%3d(%d),p-adjvex,p-info); p = p-nextarc; printf(n); /文件名:exp8-2、cpp #
10、include stdio、h #include malloc、h #include graph、h extern void MatToList1(MGraph, ALGraph *); extern void DispAdj1(ALGraph *G); extern void DFS(ALGraph *G,int v); extern void DFS1(ALGraph *G,int v); extern void DFS2(ALGraph *G,int v); extern void BFS(ALGraph *G,int v); int main() int i,j; MGraph g;
11、ALGraph *G; /文件名:algo8-2、cpp #include stdio、h #include malloc、h #include graph、h int visitedMAXV; void DFS(ALGraph *G,int v) /递归深度优先遍历 ArcNode *p; visitedv = 1; printf(%3d,v); p = G-adjlistv、firstarc; while(p!=NULL) if(visitedp-adjvex=0) top+; Sttop = G-adjlistw、firstarc; break; p = p-nextarc; print
12、f(n); void BFS(ALGraph *G,int v) ArcNode *p; int queueMAXV,front = 0,rear = 0; int visitedMAXV; void MatToList1(MGraph g, ALGraph *G) int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph); for(i=0; ig、n;i+) G-adjlisti、firstarc = NULL; for(i=0; ig、n; i+) for(j=g、n-1; j=0; j-) if(g、edgesij!=0 g、ed
13、gesij!=INF) p = (ArcNode*)malloc(sizeof(ArcNode); p-adjvex = j; p-info = g、edgesij; 试验 源程序。 一、输入如下所示程序; 二、对程序进行编译链接; 三、运行该程序，结果如图 #include stdio、h #include malloc、h #include graph、h extern void MatToList(MGraph,ALGraph *); extern void DispAdj(ALGraph *); int visitedMAXV; void DFSALL(ALGraph *G,int v,int path,int d) ArcNode *p;
