《中南大学数据结构实验报告(五)(共38页).docx》由会员分享，可在线阅读，更多相关《中南大学数据结构实验报告(五)(共38页).docx（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上中南大学数据结构试验报告题 目 实验五 学生姓名 王云鹏 学 号 指导老师 郑 瑾 学 院 计算机学院 专业班级 物联网1802 完成时间 2020.6 指导老师评定 签名 实验1. 需求分析的任意结点之间的两个数据元素都可以相关。本实验希望读者理解图的数据结构，掌握图的邻接表存 储结构，建立邻接表的算法，以及如何应用图解决具体问题（即原理与应用的结合）等。 1从键盘输入的数据建立图，并进行深度优先搜索和广度优先搜索（验证性实验） 问题描述 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个程序，演示无向图的遍历 操作。 在主程序中提供下列菜单： (1)“1
2、”代表图的建立； (2)“2”代表深度优先遍历图； (3)“3”代表广度优先遍历图； (4)“0”代表结束。 基本要求 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点， 分别输出每种遍历下的结点访问序列和相应生成树的边集。 测试数据 由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。 实现提示 设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别 为1, 2, , n）。通过输入图的所有边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种 限制。注意，生成树的边是有向边，端点顺序不能颠倒。 2利用最小
3、生成树算法解决通信网的总造价最低问题（设计性实验） 问题描述 若在n个城市之间建通信网络，只需架设n1条线路即可。如何以最低的经济代价建设这个通信网 是一个网的最小生成树问题。 基本要求 以邻接表为存储结构，利用Prim算法或Kruskal算法求网的最小生成树。 测试数据 由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。 实现提示 设通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见， 图的顶点数不超过10，网中边的权值设置成小于100。4导游问题（综合性实验） 问题描述 给出一张某公园的导游图，游客通过终端询问可知： (1) 从某一景点到另一
4、个景点的最短路径； (2) 游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。 基本要求 (1) 将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上 的权值表示距离，选择适当的数据结构。 (2) 为游客提供图中任意景点相关信息的查询。 (3) 为游客提供任意两个景点之间最短的简单路径。 (4) 为游客选择最佳游览路径。测试数据 由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。 实现提示 以邻接表为存储结构，利用Dijkstra算法或Floyd算法求最短路径，利用搜索求最佳路径2. 概要设计n 验证性实验函数：n 设
5、计性实验函数：n 综合性实验函数：3. 详细设计n 验证性实验#include#include#include#defineMAX_VERTEX_NUM30/图的最大顶点数目/队列#defineok0#definefail1#defineunderflow-1typedefintQElemType;typedefstructQNode/节点QElemTypedata;structQNode*next;/链队列QNode;typedefstructQNode*front;/头指针，带空头节点QNode*rear;/尾节点LinkQueue;intInitQueue(LinkQueue*q)/初始
6、化q-front=q-rear=(QNode*)malloc(sizeof(QNode);/申请空间，front指向头节点（空的）if(q-front=NULL)/若是申请失败printf(mallocfailinInitQueue);returnfail;q-front-next=NULL;/空队的头节点下一个自然为空returnok;intEnQueue(LinkQueue*q,QElemTypee)/插入QNode*p=(QNode*)malloc(sizeof(QNode);/将要插入的节点if(p=NULL)printf(mallocfailinEnQueue);returnfail
7、;p-data=e;/p的值为ep-next=NULL;/在尾部插入，其下一个为空q-rear-next=p;/接到尾节点的下一个q-rear=p;/p为新的尾节点returnok;intDeQueue(LinkQueue*q,QElemType*e)/删除if(q-front=q-rear)/空队无法删除printf(underflown);returnunderflow;QNode*p=q-front-next;/需要删除的节点*e=p-data;/用e带出删掉的值q-front-next=p-next;/将要删除的节点从链中断开if(q-rear=p)/加入原来队中只有一个节点q-rea
8、r=q-front;/删完后为空队，头节点与尾节点指到一起free(p);returnok;#defineempty0#definenotempty1intisempty(LinkQueueq)if(q.front=q.rear)returnempty;elsereturnnotempty;/图typedefcharvertexType;/顶点数据类型typedefenumDG,DN,UDG,UDNGraphKind;/图的类型typedefstructarcNode/边intadjvex;/边上数据，指向其父节点下一个邻接点在顶点数组中的位置structarcNode*nextarc;/指向
9、下一条边arcNode;typedefstructvnode/顶点vertexTypevexData;/顶点数据arcNode*firstarc;/指向第一个邻接点的边vnode;typedefstruct/图vnode*vertices;/顶点数组intvexnum,arcnum;/顶点数目，边的数目GraphKindkind;/图类型alGraph;voidprintVertices(alGraph*g)/打印邻接表for(inti=0;ivexnum;i+)/遍历顶点数组printf(%c,g-verticesi.vexData);/遍历每个顶点的所有边arcNode*a=(arcNod
10、e*)malloc(sizeof(arcNode);a=g-verticesi.firstarc;while(a!=NULL)printf(%d,a-adjvex);a=a-nextarc;printf(n);intlocateVex(alGraph*g,charvex)/确定点vex在邻接表中的位置for(inti=0;ivexnum;i+)/遍历比较if(g-verticesi.vexData=vex)returni;printf(vexnotexistinlocateVex:%cn,vex);return-1;/没找到返回-1voidCreateGraph(alGraph*g)/先序输入
11、图printf(输入顶点数，边数和图类n);scanf(%d%d%d,&(g-vexnum),&(g-arcnum),&(g-kind);g-vertices=(vnode*)malloc(g-vexnum*sizeof(vnode);/printf(%d%d%d,g-vexnum,g-arcnum,g-kind);printf(输入顶点n);for(inti=0;ivexnum;i+)printf(第%d个顶点：n,i+1);getchar();/清掉回车g-verticesi.vexData=getchar();/putchar(g-verticesi.vexData);g-vertice
12、si.firstarc=NULL;/尾部置空/printVertices(g);printf(输入边n);for(inti=0;iarcnum;i+)charsv;chartv;getchar();/清掉回车printf(第%d条边：n,i+1);scanf(%c%c,&sv,&tv);/printf(%c,%cn,sv,tv);ints=locateVex(g,sv);intt=locateVex(g,tv);arcNode*pi=(arcNode*)malloc(sizeof(arcNode);pi-adjvex=t;pi-nextarc=g-verticess.firstarc;/头插法
13、g-verticess.firstarc=pi;if(g-kind=UDG|g-kind=UDN)/若是无向图或无向网，在边的另一端也要加入边arcNode*pj=(arcNode*)malloc(sizeof(arcNode);pj-adjvex=s;pj-nextarc=g-verticest.firstarc;/头插法g-verticest.firstarc=pj;/printVertices(g);int*createVisted(intsize)/返回一个size大小的置0数组int*visited=(int*)malloc(size*sizeof(int);memset(visit
14、ed,0,size*sizeof(int);returnvisited;voidvisit(vertexTypev)/访问顶点数据printf(%c,v);intfirstAdjVex(alGraph*g,intv)/返回某顶点的第一个邻接点if(g-verticesv.firstarc=NULL)return-1;/无邻接点时，返回-1returng-verticesv.firstarc-adjvex;intnextAdjVex(alGraph*g,intv,intw)/返回某顶点的w之后的一个邻接点，v是当前父节点,w为上一个访问的邻接点arcNode*a=(arcNode*)malloc
15、(sizeof(arcNode);a=g-verticesv.firstarc;if(a=NULL)return-1;while(a-adjvex!=w)/遍历寻找wif(a=NULL)return-1;/到底返回-1a=a-nextarc;if(a-nextarc=NULL)return-1;/若是最后一个点，返回-1returna-nextarc-adjvex;/找到就返回下一个邻接点voidDFS(alGraph*g,intv,int*visited)/深度优先遍历visitedv=1;/已访问，置1visit(g-verticesv.vexData);for(intw=firstAdj
16、Vex(g,v);w!=-1;w=nextAdjVex(g,v,w)/遍历所有邻接点，深度优先访问它们/printf(#%d#,w);if(visitedw=0)DFS(g,w,visited);voidDFS_unconnected(alGraph*g,intv,int*visited)/非连通图的深度优先遍历for(inti=0;ivexnum;i+)/遍历该图所有点，对未访问的顶点，深度优先遍历/printf(%d,i);if(visitedi=0)DFS(g,i,visited);/printf(hhh);printf(n);voidBFS(alGraph*g,intv,int*vis
17、ited,LinkQueue*q)/广度优先遍历visitedv=1;visit(g-verticesv.vexData);EnQueue(q,v);/入队要访问的顶点while(isempty(*q)=notempty)/当队列不为空时intu;DeQueue(q,&u);/从队列取出要访问的点，置为ufor(intw=firstAdjVex(g,u);w!=-1;w=nextAdjVex(g,u,w)/遍历u的所有邻接点if(visitedw=0)/若未访问就访问visitedw=1;visit(g-verticesw.vexData);EnQueue(q,w);/将u的邻接点入队void
18、BFS_unconnected(alGraph*g,intv,int*visited)/非连通图的广度优先遍历LinkQueue*q=(LinkQueue*)malloc(sizeof(LinkQueue);/设置一个队列，用来存放将要访问的顶点InitQueue(q);for(intv=0;vvexnum;v+)/遍历该图所有点，广度优先访问if(visitedv=0)BFS(g,v,visited,q);intmain()/测试alGraph*g=(alGraph*)malloc(sizeof(alGraph);if(g=NULL)printf(mallocfailinmainforgn)
19、;return-1;CreateGraph(g);/printVertices(g);/查看邻接表printf(输入遍历起点：n);getchar();/清掉回车charstart=getchar();printf(深度优先遍历结果：n);/DFS(g,locateVex(g,start),createVisted(g-vexnum);DFS_unconnected(g,locateVex(g,start),createVisted(g-vexnum);printf(广度优先遍历结果：n);/BFS(g,locateVex(g,start),createVisted(g-vexnum);BFS
20、_unconnected(g,locateVex(g,start),createVisted(g-vexnum);return0;n 设计性实验#include#include#includeusingnamespacestd;#defineMAX_VERTEX_NUM30/图的最大顶点数目/图typedefcharvertexType;/顶点数据类型typedefenumDG,DN,UDG,UDNGraphKind;/定义图的类型有向图,有向网,无向图,无向网typedefstructarcNode/边intadjvex;/边上数据，指向其父节点下一个邻接点在顶点数组中的位置intweigh
21、t;/边权重structarcNode*nextarc;/指向下一条边arcNode;typedefstructvnode/顶点vertexTypevexData;/顶点数据arcNode*firstarc;/指向第一个邻接点的边vnode;typedefstruct/图vnode*vertices;/顶点数组intvexnum,arcnum;/顶点数目，边的数目GraphKindkind;/图类型alGraph;voidprintVertices(alGraph*g)/打印邻接表for(inti=0;ivexnum;i+)/遍历顶点数组printf(%c,g-verticesi.vexDat
22、a);/遍历每个顶点的所有边arcNode*a=(arcNode*)malloc(sizeof(arcNode);a=g-verticesi.firstarc;while(a!=NULL)printf(%d&%d,a-adjvex,a-weight);a=a-nextarc;printf(n);intlocateVex(alGraph*g,charvex)/确定点vex在邻接表中的位置for(inti=0;ivexnum;i+)/遍历比较if(g-verticesi.vexData=vex)returni;printf(vexnotexistinlocateVex:%cn,vex);retur
23、n-1;/没找到返回-1voidCreateGraph(alGraph*g)/先序输入图printf(输入顶点数，边数和图类n);scanf(%d%d%d,&(g-vexnum),&(g-arcnum),&(g-kind);g-vertices=(vnode*)malloc(g-vexnum*sizeof(vnode);printf(输入顶点n);for(inti=0;ivexnum;i+)printf(第%d个顶点：n,i+1);getchar();/清掉回车g-verticesi.vexData=getchar();g-verticesi.firstarc=NULL;/尾部置空printf
24、(输入边和权重n);for(inti=0;iarcnum;i+)charsv;chartv;intw;getchar();/清掉回车printf(第%d条边和权重：n,i+1);scanf(%c%c,&sv,&tv);scanf(%d,&w);ints=locateVex(g,sv);intt=locateVex(g,tv);arcNode*pi=(arcNode*)malloc(sizeof(arcNode);pi-adjvex=t;pi-weight=w;pi-nextarc=g-verticess.firstarc;/头插法g-verticess.firstarc=pi;if(g-kin
25、d=UDG|g-kind=UDN)/若是无向图或无向网，在边的另一端也要加入边arcNode*pj=(arcNode*)malloc(sizeof(arcNode);pj-adjvex=s;pj-weight=w;pj-nextarc=g-verticest.firstarc;/头插法g-verticest.firstarc=pj;voidvisit(vertexTypev)/访问顶点数据printf(%c,v);intfind_element_in_array(chardest,vnodearray,intarray_size)/在数组中寻找元素位置，找到返回，没找到返回-1for(inti
26、=0;iarray_size;i+)if(dest=arrayi.vexData)returni;/coutfailtofindelementvexnum*sizeof(vnode);p.vertices0.vexData=start;p.vertices0.firstarc=NULL;p.vexnum=1;p.arcnum=0;p.kind=UDN;while(true)if(p.vexnum=g-vexnum)break;/Vnew更新完则退出循环intmin_weight=100;/假设所有边权重不超过100intmin_index=0;intmin_index_source=0;for
27、(inti=0;ivertices,g-vexnum);/coutindex_findverticesindex_find.firstarc;if(a=NULL)continue;while(true)if(a=NULL)break;if(a-weightverticesa-adjvex.vexData,p.vertices,p.vexnum)=-1)/若找到更小权值的边（该边另一端点不在Vnew中）min_weight=a-weight;min_index=a-adjvex;min_index_source=i;a=a-nextarc;/找到权重最小的之后，更新Vnew和Enewp.vert
28、icesp.vexnum.vexData=g-verticesmin_index.vexData;p.verticesp.vexnum.firstarc=NULL;arcNode*pi=(arcNode*)malloc(sizeof(arcNode);pi-adjvex=p.vexnum;pi-weight=min_weight;pi-nextarc=p.verticesmin_index_source.firstarc;/头插法p.verticesmin_index_source.firstarc=pi;if(p.kind=UDG|p.kind=UDN)/若是无向图或无向网，在边的另一端也要
29、加入边arcNode*pj=(arcNode*)malloc(sizeof(arcNode);pj-adjvex=min_index_source;pj-weight=min_weight;pj-nextarc=p.verticesp.vexnum.firstarc;/头插法p.verticesp.vexnum.firstarc=pj;p.vexnum+;/printVertices(&p);printVertices(&p);intmain()/测试alGraph*g=(alGraph*)malloc(sizeof(alGraph);if(g=NULL)printf(mallocfailin
30、mainforgn);return-1;CreateGraph(g);printVertices(g);/查看邻接表printf(输入起点：n);getchar();/清掉回车charstart=getchar();cout该图最小生成树为：endl;prim(g,start);return0;#include#include#includeusingnamespacestd;#defineMAX_VERTEX_NUM30/图的最大顶点数目/图typedefcharvertexType;/顶点数据类型typedefenumDG,DN,UDG,UDNGraphKind;/定义图的类型有向图,有向
31、网,无向图,无向网typedefstructarcNode/边intadjvex;/边上数据，指向其父节点下一个邻接点在顶点数组中的位置intweight;/边权重structarcNode*nextarc;/指向下一条边arcNode;typedefstructvnode/顶点vertexTypevexData;/顶点数据stringinfo;/顶点信息arcNode*firstarc;/指向第一个邻接点的边vnode;typedefstruct/图vnode*vertices;/顶点数组intvexnum,arcnum;/顶点数目，边的数目GraphKindkind;/图类型alGraph;voidprintVertices(alGraph*g)/打印邻接表for(inti=0;ivexnum;i+)/遍历顶点数组printf(%c,g-verticesi.vexData);/遍历每个顶点的所有边arcNode*a=(arcNode*)malloc(sizeof(arcNode);a=g-verticesi.firstarc;while(a!=NULL)printf(%d&%d,a-adjvex,a-weight);a=a-nextarc;printf(n);intlocateVex(alGraph*g,charvex)/确定点vex在邻接表中的位置