数据结构实验八.doc

一、实验目的 1.掌握图的存储结构和相关操作。 2.能够熟练用计算机来表示图和进行图处理。二、实验环境 1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows; 2.软件：DOS或Windows操作系统+Turbo C;三、实验要求 1要求对于给定的图分别用邻接矩阵和邻接表示来存储。 2对于存储好的图进行深度和广度优先遍历。 3完成图的各种操作。四、实验内容1.现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。2.现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。五、代码如下第一个实验#include#includeusing 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;coutG.vexnumG.arcnum;cout输入顶点:;for(i=0;iG.vexsi; /构造顶点数for(i=0;iG.vexnum;i+) /构造邻接矩阵for(j=0;jG.vexnum;j+)G.arcsij=0;for(k=0;kG.arcnum;k+)cout输入第k+1v1v2;i=ylx_LocateVex(G,v1); j=ylx_LocateVex(G,v2);G.arcsij=1;G.arcsji=1; /置的对称弧return 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.arcsij ;coutendl; 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; coutendlG.vexnum; coutG.arcnum; for(i=1;i=G.vexnum;i+)/初使化表头 G.verticesi.data=i; G.verticesi.firstarc=NULL; for(k=1;k=G.vexnum;k+) /输入边 int v2; cout请输入与结点kv2; cout请输入与第kv1; 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; /顶点给P q-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; coutwnextarc) w=r-adjvex; 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=1;j=x;j+) coutG.verticesj.data ; ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode);if(!p) exit(-1); p=G.verticesj.firstarc; while(p) coutadjvexnextarc; 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;