中南大学数据结构实验报告(五)

中南大学数据结构试验报告题目实验五学生姓名王云鹏学号8213180228指导老师郑瑾学院计算机学院专业班级物联网1802完成时间2020.6指导老师评定签名实验1.需求分析的任意结点之间的两个数据元素都可以相关。本实验希望读者理解图的数据结构，掌握图的邻接表存储结构，建立邻接表的算法，以及如何应用图解决具体问题（即原理与应用的结合）等。1．从键盘输入的数据建立图，并进行深度优先搜索和广度优先搜索（验证性实验）问题描述很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个程序，演示无向图的遍历操作。在主程序中提供下列菜单：(1)“1”代表图的建立；(2)“2”代表深度优先遍历图；(3)“3”代表广度优先遍历图；(4)“0”代表结束。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。实现提示设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的所有边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。2．利用最小生成树算法解决通信网的总造价最低问题（设计性实验）问题描述若在n个城市之间建通信网络，只需架设n1条线路即可。如何以最低的经济代价建设这个通信网是一个网的最小生成树问题。基本要求以邻接表为存储结构，利用Prim算法或Kruskal算法求网的最小生成树。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。实现提示设通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见，图的顶点数不超过10，网中边的权值设置成小于100。4．导游问题（综合性实验）问题描述给出一张某公园的导游图，游客通过终端询问可知：(1)从某一景点到另一个景点的最短路径；(2)游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。基本要求(1)将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。(2)为游客提供图中任意景点相关信息的查询。(3)为游客提供任意两个景点之间最短的简单路径。(4)为游客选择最佳游览路径。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。实现提示以邻接表为存储结构，利用Dijkstra算法或Floyd算法求最短路径，利用搜索求最佳路径2.概要设计验证性实验函数：设计性实验函数：综合性实验函数：3.详细设计验证性实验#includestdio.h#includestdlib.h#includestring.h#defineMAX_VERTEX_NUM30//图的最大顶点数目//队列#defineok0#definefail1#defineunderflow-1typedefintQElemType;typedefstructQNode{//节点QElemTypedata;structQNode*next;//链队列}QNode;typedefstruct{QNode*front;//头指针，带空头节点QNode*rear;//尾节点}LinkQueue;intInitQueue(LinkQueue*q){//初始化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;}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(underflow\n);returnunderflow;}QNode*p=q-front-next;//需要删除的节点*e=p-data;//用e带出删掉的值q-front-next=p-next;//将要删除的节点从链中断开if(q-rear=p){//加入原来队中只有一个节点q-rear=q-front;//删完后为空队，头节点与尾节点指到一起}free(p);returnok;}#defineempty0#definenotempty1intisempty(LinkQueueq){if(q.front==q.rear){returnempty;}else{returnnotempty;}}//图typedefcharvertexType;//顶点数据类型typedefenum{DG,DN,UDG,UDN}GraphKind;//图的类型typedefstructarcNode{//边intadjvex;//边上数据，指向其父节点下一个邻接点在顶点数组中的位置structarcNode*nextarc;//指向下一条边}arcNode;typedefstructvnode{//顶点vertexTypevexData;//顶点数据arcNode*firstarc;//指向第一个邻接点的边}vnode;typedefstruct{//图vnode*vertices;//顶点数组intvexnum,arcnum;//顶点数目，边的数目GraphKindkind;//图类型}alGraph;voidprintVertices(alGraph*g){//打印邻接表for(inti=0;ig-vexnum;i++){//遍历顶点数组printf(%c,g-vertices[i].vexData);//遍历每个顶点的所有边arcNode*a=(arcNode*)malloc(sizeof(arcNode));a=g-vertices[i].firstarc;while(a!=NULL){printf(%d,a-adjvex);a=a-nextarc;}printf(\n);}}intlocateVex(alGraph*g,charvex){//确定点vex在邻接表中的位置for(inti=0;ig-vexnum;i++){//遍历比较if(g-vertices[i].vexData==vex){returni;}}printf(vexnotexistinlocateVex:%c\n,vex);return-1;//没找到返回-1}voidCreateGraph(alGraph*g){//先序输入图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;ig-vexnum;i++){printf(第%d个顶点：\n,i+1);getchar();//清掉回车g-vertices[i].vexData=getchar();//putchar(g-vertices[i].vexData);g-vertices[i].firstarc=NULL;//尾部置空}//printVertices(g);printf(输入边\n);for(inti=0;ig-arcnum;i++){charsv;chartv;getchar();//清掉回车printf(第%d条边：\n,i+1);scanf(%c%c,&sv,&tv);//printf(%c,%c\n,sv,tv);ints=locateVex(g,sv);intt=locateVex(g,tv);arcNode*pi=(arcNode*)malloc(sizeof(arcNode));pi-adjvex=t;pi-nextarc=g-vertices[s].firstarc;//头插法g-vertices[s].firstarc=pi;if(g-kind==UDG||g-kind==UDN){//若是无向图或无向网，在边的另一端也要加入边arcNode*pj=(arcNode*)malloc(sizeof(arcNode));pj-adjvex=s;pj-nextarc=g-vertices[t].firstarc;//头插法g-vertices[t].firstarc=pj;}}//printVertices(g);}int*createVisted(intsize){//返回一个size大小的置0数组int*visited=(int*)malloc(size*sizeof(int));memset(visited,0,size*sizeof(int));returnvisited;}voidvisit(vertexTypev){//访问顶点数据printf(%c,v);}intfirstAdjVex(alGraph*g,intv){//返回某顶点的第一个邻接点if(g-vertices[v].firstarc==NULL)return-1;//无邻接点时，返回-1returng-vertices[v].firstarc-adjvex;}intnextAdjVex(alGraph*g,intv,intw){//返回某顶点的w之后的一个邻接点，v是当前父节点,w为上一个访问的邻接点arcNode*a=(arcNode*)malloc(sizeof(arcNode));a=g-vertices[v].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){//深度优先遍历visited[v]=1;//已访问，置1visit(g-vertices[v].vexData);for(intw=firstAdjVex(g,v);w!=-1;w=nextAdjVex(g,v,w)){//遍历所有邻接点，深度优先访问它们//printf(#%d#,w);if(visited[w]==0){DFS(g,w,visited);}}}voidDFS_unconnected(alGraph*g,intv,int*visited){//非连通图的深度优先遍历for(inti=0;ig-vexnum;i++){//遍历该图所有点，对未访问的顶点，深度优先遍历//printf(%d,i);if(visited[i]==0){DFS(g,i,visited);}//printf