用C语言和数据结构中的无向图存储结构编一个校园导游图完全的程序代码.docx

#define Infinity 1000#define MaxVertexNum 35#define MAX 40#include#include#include#include#includetypedef struct arcell /边的权值信息 int adj; /权值arcell,adjmatrixMaxVertexNumMaxVertexNum; /图的邻接矩阵类型typedef struct vexsinfo /顶点信息 int position; /景点的编号 char name32; /景点的名称 char introduction256; /景点的介绍vexsinfo;typedef struct mgraph /图结构信息 vexsinfo vexsMaxVertexNum; /顶点向量(数组) adjmatrix arcs; /邻接矩阵 int vexnum,arcnum; /分别指定顶点数和边数mgraph;/全局变量int visited35; /用于标志是否已经访问过int d35; /用于存放权值或存储路径顶点编号mgraph campus; /图变量(大学校园)/ (1) 对图初始化mgraph initgraph() int i=0,j=0; mgraph c; c.vexnum =28; /顶点个数 c.arcnum =39; /边的个数 for(i=0;ic.vexnum ;i+) /依次设置顶点编号 c.vexsi.position =i; /依次输入顶点信息 strcpy( ,小西南门); strcpy(roduction ,离公交站近); strcpy( ,学校南正门); strcpy(roduction ,学校大门、学校班车进出口); strcpy( ,语言文化职业学院); strcpy(roduction ,语言文化职业学院办公楼，楼高6层); strcpy( ,艺术学院); strcpy(roduction ,音乐系、美术系，楼高4层); strcpy( ,行政楼); strcpy(roduction ,行政办公大楼，楼高5层); strcpy(,文学院); strcpy(roduction ,文学院，楼高6层); strcpy( ,体育场); strcpy(roduction ,室外标准田径场); strcpy(,教育科学学院); strcpy(roduction ,教心系、经管系，楼高5层); strcpy( ,南区学生宿舍); strcpy(roduction ,离西南门近); strcpy(, 数学与经济管理学院); strcpy(roduction , 数学与经济管理学院大楼，楼高4层); strcpy( ,中区学生宿舍); strcpy(roduction ,若干栋，离学生1、2食堂近); strcpy( ,职业学院教学大楼); strcpy(roduction ,职业学院教学大楼，楼高5层); strcpy( ,体育系); strcpy(roduction ,体育系，楼高5层); strcpy( ,游泳馆); strcpy(roduction ,室内小型游泳馆); strcpy( ,报告厅、阶梯教室); strcpy(roduction ,可举办中、大型学术会议。有大小报告厅16个、阶梯教室16个); strcpy( ,大礼堂、体育馆); strcpy(roduction ,文艺演出所在地、室内运动场); strcpy( ,1食堂); strcpy(roduction ,教工食堂及学生1食堂在此); strcpy( ,新图书馆); strcpy(roduction ,建筑面积46000平方米); strcpy( ,2食堂); strcpy(roduction ,学校东区，学生食堂); strcpy( ,东区学生宿舍); strcpy(roduction ,离学生2食堂近); strcpy( ,计算机学院); strcpy(roduction ,计算机学院大楼，楼高5层); strcpy( ,教工宿舍); strcpy(roduction ,学校青年教职工租住地); strcpy( ,西区学生宿舍); strcpy(roduction ,离学生3、4食堂近); strcpy( ,3食堂); strcpy(roduction ,学校西区，学生食堂); strcpy( ,外国语学院); strcpy(roduction ,外国语学院大楼，楼高5层); strcpy( ,4食堂); strcpy(roduction ,学校西区，学生食堂，人气较高); strcpy( ,校医院); strcpy(roduction ,看小病的地方); strcpy( ,实验楼); strcpy(roduction ,物电学院、化学与生命科学学院、机电系、建材系所在地，机房及多媒体教室若干); /依次输入边上的权值信息 for(i=0;ic.vexnum ;i+) for(j=0;jc.vexnum ;j+) c.arcs ij.adj =Infinity; /先初始化图的邻接矩阵 /部分弧长 c.arcs02.adj=50; c.arcs03.adj=60; c.arcs14.adj=90; c.arcs23.adj=60; c.arcs28.adj=40; c.arcs34.adj=60; c.arcs36.adj=40; c.arcs45.adj=70; c.arcs49.adj=70; c.arcs410.adj=80; c.arcs417.adj=200; c.arcs57.adj=70; c.arcs69.adj=40; c.arcs718.adj=190; c.arcs811.adj=50; c.arcs912.adj=40; c.arcs1018.adj=70; c.arcs1112.adj=60; c.arcs1114.adj=50; c.arcs1115.adj=50; c.arcs1216.adj=50; c.arcs1314.adj=40; c.arcs1322.adj=60; c.arcs1415.adj=50; c.arcs1420.adj=90; c.arcs1516.adj=60; c.arcs1521.adj=40; c.arcs1617.adj=60; c.arcs1718.adj=80; c.arcs1819.adj=60; c.arcs2021.adj=60; c.arcs2024.adj=80; c.arcs2223.adj=60; c.arcs2225.adj=80; c.arcs2324.adj=60; c.arcs2426.adj=100; c.arcs2427.adj=100; c.arcs2526.adj=90; c.arcs2627.adj=90; for(i=0;ic.vexnum ;i+) /邻接矩阵是对称矩阵，对称赋值 for(j=0;jc.vexnum ;j+) c.arcsji.adj =c.arcsij.adj ; return c;/initgraph/ (2) 查找景点在图中的序号int locatevex(mgraph c,int v) int i; for(i=0;ic.vexnum ;i+) if(v=c.vexsi.position) return i; /找到，返回顶点序号i return -1; /否则，返回-1/(3) 、(4) 求两景点间的所有路径/ (3) 打印序号为m,n景点间的长度不超过8个景点的路径void path(mgraph c, int m,int n,int k) int s,x=0; int t=k+1; /t 记载路径上下一个中间顶点在d数组中的下标 if(dk=n & k8) /dk存储路径顶点。若dk是终点n且景点个数=8，则输出该路径 /递归出口，找到一条路径 for(s=0;s,); /输出该路径。s=0 时为起点m printf(%s,); /输出最后一个景点名(即顶点n的名字，此时s=k) printf(nn); else s=0; while(sc.vexnum) /从第m个顶点，试探至所有顶点是否有路径 if(c.arcsdks.adjInfinity) & (visiteds=0) /初态：顶点m到顶点s有边，且未被访问 visiteds=1; dk+1=s; /存储顶点编号s 至dk+1中 path(c,m,n,t); /求从下标为t=k+1的第dt个顶点开始的路径(递归调用)，同时打印出一条m至n的路径 visiteds=0; /将找到的路径上顶点的访问标志重新设置为0，以用于试探新的路径 s+; /试探从下一个顶点 s 开始是否有到终点的路径 /endwhile /endelse/endpath/(4) 打印两景点间的景点个数不超过8的所有路径。调用(3)int allpath(mgraph c) int k,i,j,m,n; printf(nn请输入你要查询的两个景点编号:nn); scanf(%d%d,&i,&j); printf(nn); m=locatevex(c,i); /调用(2)，确定该顶点是否存在。若存在，返回该顶点编号 n=locatevex(c,j); d0=m; /存储路径起点m (int d数组是全局变量) for(k=0;kc.vexnum;k+) /全部顶点访问标志初值设为0 visitedk=0; visitedm=1; /第m个顶点访问标志设置为1 path(c,m,n,0); /调用(3)。k=0，对应起点d0=m。k为d数组下标 return 1;/ (5) 用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印void shortestpath_dij(mgraph c) /迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度dv /若pvw为1，则w是从v0到v的最短路经上的顶点 /finalv类型用于设置访问标志 int v,w,i,min,t=0,x,flag=1,v0; /vo为起始景点的编号 int final35,d35,p3535; printf(n请输入一个起始景点的编号：); scanf(%d,&v0); printf(nn); while(v0c.vexnum) printf(n你所输入的景点编号不存在n); printf(请重新输入：); scanf(%d,&v0); /while for(v=0;vc.vexnum ;v+) finalv=0; /初始化各顶点访问标志 dv=c.arcsv0v.adj; /v0 到各顶点 v 的权值赋值给dv for(w=0;wc.vexnum ;w+) /初始化p数组，各顶点间的路径全部设置为空路径0 pvw=0; if(dvInfinity) /v0 到v 有边相连，修改pvv0的值为1 pvv0=1; pvv=1; /各顶点自己到自己要连通 /for dv0=0; /自己到自己的权值设为0 finalv0=1; /v0的访问标志设为1，v 属于 s 集 for(i=1;ic.vexnum ;i+) /对其余c.vexnum-1个顶点w，依次求 v 到 w 的最短路径 min=Infinity; for(w=0;wc.vexnum ;w+) /在未被访问的顶点中，查找与 v0 最近的顶点v if(!finalw) if(dwmin) /v0 到 w (有边)的权值min v=w; min=dw; /if finalv=1; /v 的访问标志设置为1，v 属于s集 for(w=0;wc.vexnum ;w+) /修改v0 到其余各顶点w 的最短路径权值dw if(!finalw&(min+c.arcsvw.adj dw) /若w 不属于s，且v 到w 有边相连 dw=min+c.arcsvw.adj; /修改v0 到w 的权值dw for(x=0;xc.vexnum ;x+) /所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点 pwx=pvx; pww=1; /if /for for(v=0;vc.vexnum ;v+) /输出v0 到其它顶点v 的最短路径 if(v!=v0) printf(%s,); /输出景点v0 的景点名 for(w=0;w%s,); printf(-%s,); printf(n总路线长为%d米nn,dv); /for/shortestpath/(6)-(11)修改图的信息。包括建图、更新信息、删除、增加结点和边 /(6) 构造图的邻接矩阵 int creatgragh(mgraph &c) /建图。以图的邻接矩阵存储图 int i,j,m,n; int v0,v1; int distance; printf(请输入图的顶点数和边数: n); scanf(%d %d,&c.vexnum ,&c.arcnum ); printf(下面请输入景点的信息：n); for(i=0;ic.vexnum ;i+) /构造顶点向量(数组) printf(请输入景点的编号：); scanf(%d,c.vexsi.position ); printf(n请输入景点的名称：); scanf(%s, ); printf(n请输入景点的简介：); scanf(%s,roduction ); for(i=0;ic.arcnum ;i+) /初始化邻接矩阵 for(j=0;jc.arcnum ;j+) c.arcsij.adj =Infinity; printf(下面请输入图的边的信息：n);