数据结构实验八

一、实验目的1. 掌握图的存储结构和相关操作。2. 能够熟练用计算机来表示图和进行 图处理。二、实验环境1. 硬件：每个学生需配备计算机一台。 操作系统：DOS或Windows;2. 软件：DOS或Windows操作系统 +Turbo C;三、实验要求五、代码如下第一个实验#include #include using namespace std;#define MAX 20typedef int AdjMAXMAX;typedef structstring vexsMAX; /顶点表Adj arcs;/邻接矩阵int vexnum,arcnum; /图的顶点和弧数 MGraph;int ylx_LocateVex(MGraph &G,string u); int ylx_CreateUDN(MGraph &G)int i,k,j;string v1,v2;cout请输入顶点数、弧数：；cinG.vexnumG.arcnum;cout输入顶点：；for(i=0;iG.vexsi； /构造顶点数for(i=0；iG.vexnum；i+) /构造邻接矩1要求对于给定的图分别用邻接矩阵 和邻接表示来存储。2对于存储好的图进行深度和广度优 先遍历。3完成图的各种操作。四、实验内容1. 现在某网络公司的光纤连接结点如 下图所示，请分别用邻接矩阵和邻接表将图 存储到计算机中方便进行处理。2. 现在某网络公司的光纤连接结点如 下图所示，请分别用邻接矩阵和邻接表将图 存储到计算机中方便进行处理。阵for(j=0；jG.vexnum；j+)G.arcsij=0；for(k=0；kG.arcnum；k+)coutv1v2；i=ylx_LocateVex(G,v1)；j=ylx_LocateVex(G,v2)；G.arcsij=1；G.arcsji=l; /置vl, v2的对称弧v2, v1return 0;int ylx_LocateVex(MGraph &G,string u)/确定u在G中序号int i;for (i=0;iG.vexnum;i+)if (u=G.vexsi)return i;if (i=G.vexnum)coutError u!endl;exit(1); return 0;void ylx_ShowG(MGraph &G)int i,j;for(i=0;iG.vexnum;i+)coutG.vexsi ; coutendl;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)coutG.arcsijcoutendl; main()MGraph A;int a;a=ylx_CreateUDN(A);ylx_ShowG(A);第二个实验#include# include # include # include using namespace std;int visited30;# define MAX_VERTEX_NUM 30# define OK 1/typedef int VertexType;typedef int InfoType;typedef struct ArcNode /弧 int adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNode/表头 int data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct/图 AdjList vertices;int vexnum,arcnum;int kind;ALGraph;void ylx_CreateDG(ALGraph &G) int k,i,v1;coutendl请输入结点个数：;cinG.vexnum;coutG.arcnum; for(i=l;i=G.vexnum;i+)/初使化表头 G.verticesi.data=i;G.verticesi.firstarc=NULL; for(k=1;k=G.vexnum;k+) /输入边 int v2;coutv2;coutv1;ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode); if(!p) exit(-1);p-adjvex=v1;p-nextarc=NULL;G.verticesk.firstarc=p;for(int i=1;iv2;i+) int m;cout请输入与第km;ArcNode *q;q=(ArcNode*)malloc(sizeof(ArcNode);/动态指针if(!q) exit(-1);q-adjvex=m; /顶点给 Pq-nextarc=NULL;p-nextarc=q;p=q;/free(q); /free(p); void ylx_DFS (ALGraph G,int v )/深度搜索 visitedv=1;coutG.verticesv.datanextarc) w=x-adjvex; if(visitedw=0) ylx_DFS(G,w); void ylx_DFSB (ALGraph G,int v)/ 深度搜索的 边集 visitedv=1;ArcNode *y; y=(ArcNode*)malloc(sizeof(ArcNode); if(!y) exit(-1);y=G.verticesv.firstarc;int u=G.verticesv.data;int w; for(;y;y=y-nextarc) w=y-adjvex;if(visitedw=0) coutuwnext=NULL;void ylx_EnQueue (LinkQueue & Q,int e)/进队 QNode *p;p=(QNode*)malloc(sizeof(QNode); if(!p) exit(-1);p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p;/free(p);int ylx_DeQueue (LinkQueue & Q,int & e)/ 出队 if(Q.front=Q.rear)return -1;QNode *p;p=(QNode*)malloc(sizeof(QNode);if(!p) exit(-1); p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return e;int ylx_QueueEmpty (LinkQueue Q)/判 断队列是 否为空 if(Q.front=Q.rear)return 1;return 0;void ylx_BFS(ALGraph G,int v)/广度搜索 int u;LinkQueue Q; InitQueue(Q);if(visitedv=0) visitedv=1; coutG.verticesv.dataadjvex;w=0;w=z-nextarc-adjvex)if(visitedw=0) visitedw=1; coutwnextarc) w=z-adjvex;if(visitedw=0)visitedw=1; coutwadjvex;if(visitedw=0) visitedw=1; coutuwendl;EnQueue(Q,w); int main() int i;ALGraph G;ylx_CreateDG(G);int x;coutx;cout邻接表为：endl;for(int j=l;j=x;j+) coutG.verticesj.data ;ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode);六、运行结果截图if(!p) exit(T);p=G.verticesj.firstarc;while(p) coutp-adjvex;p=p-nextarc; coutendl; cout请输入第一个要访问的结点序号: n;for( i=0;i30;i+)visitedi=0;cout广度搜索：endl;ylx_BFS(G,n);for( i=0;i30;i+)visitedi=0;coutendl;cout边集：endl;ylx_BFSB(G,n);for( i=0;i30;i+)visitedi=0;cout深度搜索：endl;ylx_DFS(G,n);for( i=0;i30;i+)visitedi=0;coutendl;cout边集：endl;ylx_DFSB(G,n); /system(pause);return 0;