数据结构课程设计实践报告

数据结构实验报告实验名称________结构图_________________________提交文档学生姓名_______________________________提交文档学生学号________________________________同组成员名单___________________________________指导教师姓名top++;St[top]=G-adjlist[w].firstarc;break;p=p-nextarc;printf,,\n,;void BFSALGraph*G,int vArcNode*p;int queue[M AXV],front=0,rear=0;int visited[MAXV];int w,i;fori=0;iG-n;i4-+visited[i]=0;printfn%3dn,v;visited[v]=1;rear=rear+1%MAXV;queue[rear]=v;whilefront!=rear二front front+1%MAXV;w=queue[front];p=G-adjlist[w].firstarc;whilep!=NULL ifvisited[p-adjvex]==Oprintfn%3dn,p-adj vex;visited[p-adjvex]=1;rear=rear+1%MAXV;queue|rear|=p-adjvex;p=p-nextarc;printfn\nH;void MatToList1MGraph g,ALGraph*G voidMatToList1MGraph g,ALGraph*Gint i,j;ArcNode*p;二G ALGraph*mallocsizeofALGraph;fori=0;ivg.n;i++G-adjlist[i].firstarc=NULL;fori=0;ig.n;i++forj=g.n-l;j=O;j-ifg.edges[i][j]!=Og.edges[i][j]!=INF{p=ArcNode*mallocsizeof ArcNode;p-adjvex=j;p-info=g.edges[i]fj];p-nextarc=G-adj1ist[i].firs tare;G-adjlist[i].firstarc=p;G-n=g.n;G-e=g.e;void DispAdj1ALGraph*Gint i;ArcNode*p;fori=0;iG-n;i++p=G-adjlist[i].firstarc;printfn%3d:n,i;whilep!=NULLprintfn%3d%dn,p-adjvex,p-info;二p p-nextarc;printfn\nn;

二、对程序进行编译链接；

三、运行该程序，结果如图图G的邻接表01537124208593255643550341从顶点0开始的DFS（递归算法）01254;非递归算法）:从顶点0开始的DFS301254从顶点0开始的BFS013254实验

③源程序

一、输入如下所示程序;#include stdio.h#include malloc.h#include graph.hextern void MatToListMGraph,ALGraph*;extern void DispAdjALGraph*;int visited[MAXV];void DFSALLALGraph*G,int v,int path[],int dArcNode*p;visited[v]=1;path[d]=v;d++;ifd==G-nforint k=0;kd;k++printfn%2d,\path[k];printfn\nn;p=G-adjlist[v].firstarc;whilep!=NULL二p ArcNode^mallocsizeofArcNode;p-adjvex=j;p-nextarc=G-adjlist|i].firstarc;G-adjlistfi].firstarc=p;G-n=g.n;G-e=g.e;voidDispAdjALGraph*G{int i;ArcNode*p;fori=0;iG-n;i++p=G-adj list[i].firstarc;printfn%3d:n,i;whilep!=NULLprintfn%3dn,p-adjvex;p=p-nextarc;}printfn\nn;

二、对程序进行编译链接；

三、运行该程序，结果如图结构图

一、实验目的和要求

1、设计目的

1.掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义

2.重点掌握图的各种存储结构，包括邻接矩阵和邻接表等

3.重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等

4.掌握图的其他运算，包括最小生成树，最短路径，拓扑排序和关键路径等算法

5.灵活运用图这种数据结构解决一些综合应用问题

2、设计内容和要求

1、编写一个程序algo8-

1.cpp,实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-l.cpp实现如下功能

①建立如图1所示的有向图G的邻接矩阵，并输出；

②由有向图G的邻接矩阵产生邻接表，并输出；

③再由

②的邻接表产生对应的邻接矩阵，并输出5I

0342、编写一个程序algo8-

2.cpp,实现图的遍历运算，并在此基础上设计一个程序exp8-

2.cpp完成如下功能

①输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）；

②输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；

③输出图1所示的有向图G从顶点0开始的广度优先遍历序列

3、设计一个程序exp8-

3.cpp,采用邻接表存储图，并输出图

8.1（a）中从指定顶点1出发的所有深度优先遍历序列

二、运行环境（软、硬件环境）软件环境Visual C++

6.0运行平台Win32硬件普通个人pc机

三、实验过程描述文件中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下graph,h三个实验中都会使用到其代码如下#ifndef GRAPH_H_INCLUDED#define GRAPH H INCLUDEDtypedef intInfoType;〃最大顶点个数#define MAXV100表示无限大#define INF32767//INF〃以下定义邻接矩阵类型typedef structint no;InfoType info;JVertexType;typedef structint edges[MAXV][MAXV];int n,e;VertexType vexs[MAXV];JMGraph;〃以下定义邻接表类型typedef struct ANodeint adjvex;structANode*nextarc;InfoType info;JArcNode;typedef intVertex;typedef structVNode{Vertex data;ArcNode*firs tare;}VNode;typedef VNodeAdjList[MAXV];typedef structAdjListadjlist;intn,e;}ALGraph;#endif//GRAPHHINCLUDED实验

①源程序

一、输入如下所示程序；//文件名exp8-l.cpp#include stdio.h#include malloc.h#include graph.hextern voidMatToList1MGraph,ALGraph*;extern voidListToMat1ALGraph*,MGraph;extern voidDispMat1MGraph;extern voidDispAdj1ALGraph*;int mainint i,j;MGraph g,gl;ALGraph*G;intA[MAXV]

[6]={{0,5,INF,7,INF,INF,{INF,0,4JNF,INF,INF},』{8,INF,0,INF,INF,9},{INF,INF,5,0NF,6},{INFJNF,INF,5,0,INF},{3,INFJNF,INF,l,0}};g.n=6;g.e=10;fori=0;ig.n;i++forj=0;jg,n;j++g.edges[i][j]=A[i][j];有向图的邻接矩阵；printf G\n”DispMatlg;G=ALGraph*mallocsizeofALGraph;”图的邻接矩阵转换成邻接表printf G\nMatToList lg,G;DispAdj1G;”图的邻接表转换成邻接矩阵；printf G\nListToMat lG,gl;DispMatlgl;return0;//文件名:algo8-l.cpp#include stdio.h#include malloc.h#include graph.h〃不带权图的算法叩voidMatToListMGrh g,ALGraph*G int ij;ArcNode*p;G=ALGraph*mallocsizeof ALGraph;fori=0;ig.n;i++forj=g.n-l;j=O;j-ifg.edges[i][j]!=O p=ArcNode*mallocsizeofArcNode;p-adjvex=j;p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;G-n=g.n;G-e=g.e;void ListToMatALGraph*G,MGraph g{inti,j;ArcNode*p;fori=0;iG-n;i++forj=0;jG-n;j++g.edges[i][j]=0;fori=0;iG-n;i++p=G-adjlist[i].firstarc;whilep!=NULLg.edges[i]lp-adjvexj=1;p=p-nextarc;g.n=G-n;g.e=G-e;void DispMatMGraph g；inti,jvoid DispAdj1ALGraph*G血i;ArcNode*p;fori=0;iG-n;i++{p=G-adjlist[i].firstarc;printfn%3d:n,i;whilep!=NULL printfn%3d%dn,p-adjvex,p-info;p=p-nextarc;printfn\nn;、编译并链接程序;

三、运行程序，结果如下图:有向图G的邻接矩阵:00CO7884088CO888COCO co08CO888031图G的邻接矩阵转换成邻接表:0153712459208562543541503图G的邻接表转换成邻接矩阵:0CO7804088CO888888CO08CO800CO13实验

②源程序

一、输入如下所示程序;extern voidMatToListl MGraph,ALGraph*;extern voidDispAdj1ALGraph*G;extern void DFSALGraph*Gint v;extern void DFS1ALGraph*G,int v;extern voidDFS2ALGraph*G,int v;extern voidBFSALGraph*G,int v;int mainintij;MGraphg;ALGraph*G;intA[MAXV]

[6]={{0,5,INF,7,INF,INF},{INF,0,4JNFJNFJNF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};g.n=6;g.e=10;fori=0;ig.n;i++forj=0;jg,n;j++g.edges[i][j]=A[i][j];二G ALGraph*manocsizeofALGniph;MatToListlg,G;printf”图G的邻接表:\nn;DispAdj1G;printf“从顶点0开始的DFS递归算法:\nn;；DFSGOprintfn\nn;printf从顶点0开始的DFS非递归算法:\nn;；DFS1GOprintfn\nn;printf从顶点0开始的BFS\nn;BFSG,0;；printf\nint visited|MAXV];//递归深度优先遍历voidDFSALGraph*G,int vArcNode*p;visited[v]=1;printfn%3dn,v;p=G-adj list[v].firstarc;whilep!=NULLifvisited|p-adjvex]==0DFSG,p-adjvex;p=p-nextarc;〃非递归深度优先遍历voidDFS1ALGraph*G,int vArcNode*p;ArcNode*St[MAXV];int top=〈〉fori=0;i G-n;i++visitedfi]=0;printfH%3dn,v;visited[v]=1;top++;St[top]=G-adjlist[v].firstarc;whiletop-lP=St[top];top-;whilep!=NULL w=p-adjvex;ifvisited[w]==0printfn%3dn,w;visited[w]=1;。