《2022年数据结构实验八文件 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验八文件 .pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、实验目的 1.掌握图的存储结构和相关操作。2.能够熟练用计算机来表示图和进行图处理。二、实验环境 1.硬件：每个学生需配备计算机一台。操作系统：DOS或 Windows;2.软 件：DOS或Windows 操 作系 统+Turbo C;三、实验要求 1要求对于给定的图分别用邻接矩阵和邻接表示来存储。2对于存储好的图进行深度和广度优先遍历。3完成图的各种操作。四、实验内容1.现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。2.现在某网络公司的光纤连接结点如下图所示，请分别用邻接矩阵和邻接表将图存储到计算机中方便进行处理。五、代码如下第一个实验#
2、include#include using namespace std;#define MAX 20 typedef int AdjMAXMAX;typedef struct string 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
3、(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)名师资料总结-精品资料欢
4、迎下载-名师精心整理-第 1 页，共 4 页 -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 names
5、pace 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,arcnu
6、m;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-n
7、extarc=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)名师资料总结-精品资料欢迎下载-名师精心整
8、理-第 2 页，共 4 页 -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(LinkQueu
9、e&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.re
10、ar=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(vi
11、sitedw=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)coutad
12、jvexnextarc;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;六、运行结果截图第一个实验第二个实验名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -