附录:
#define Infinity 1000 #define MaxVertexNum 35 #define MAX 40 #include
typedef struct arcell //{
int adj; //}arcell,adjmatrix[MaxVertexNum][MaxVertexNum]; //
typedef struct vexsinfo //{
int position; // char name[32]; // char introduction[256]; //}vexsinfo;
typedef struct mgraph //{
vexsinfo vexs[MaxVertexNum]; // adjmatrix arcs; // int vexnum,arcnum; //}mgraph;
//全局变量
int visited[35]; //
int d[35]; //点编号
mgraph campus; //
// (1) 对图初始化
mgraph initgraph() {
边的权值信息 权值
图的邻接矩阵类型 顶点信息 景点的编号 景点的名称 景点的介绍 图结构信息 顶点向量(数组) 邻接矩阵
分别指定顶点数和边数 用于标志是否已经访问过 用于存放权值或存储路径顶图变量(大公园园)
int i=0,j=0; mgraph c;
c.vexnum =28; //顶点个数 c.arcnum =39; //边的个数
for(i=0;i strcpy(c.vexs[0].name ,\小西南门\ strcpy(c.vexs[0].introduction ,\离公交站近\strcpy(c.vexs[1].name ,\公园南正门\ strcpy(c.vexs[1].introduction ,\公园大门、公园班车进出口\strcpy(c.vexs[2].name ,\东坡亭\ strcpy(c.vexs[2].introduction ,\东坡亭,亭高3层\strcpy(c.vexs[3].name ,\西施坡\ strcpy(c.vexs[3].introduction ,\西施坡,风光优美\strcpy(c.vexs[4].name ,\黄蓉亭\ strcpy(c.vexs[4].introduction ,\黄蓉亭,名字来自于射雕英雄传\strcpy(c.vexs[5].name,\荷花塘\ strcpy(c.vexs[5].introduction ,\荷花塘,里面有很多荷花\strcpy(c.vexs[6].name ,\广场\ strcpy(c.vexs[6].introduction ,\很大的一块空地\strcpy(c.vexs[7].name,\花坛\ strcpy(c.vexs[7].introduction ,\里面有很多花\strcpy(c.vexs[8].name ,\长椅\ strcpy(c.vexs[8].introduction ,\这儿有很多椅子,有人可以做\strcpy(c.vexs[9].name, \慈悲庵\ strcpy(c.vexs[9].introduction , \慈悲庵,慈悲庵是创建于元代的古刹\strcpy(c.vexs[10].name ,\云绘楼\ strcpy(c.vexs[10].introduction ,\云绘楼是一座皇家园林建筑\strcpy(c.vexs[11].name ,\九龙壁\ strcpy(c.vexs[11].introduction ,\整壁用彩色琉璃瓦镶砌而成\strcpy(c.vexs[12].name ,\白塔\ strcpy(c.vexs[12].introduction ,\白塔,高5层\strcpy(c.vexs[13].name ,\游泳馆\ strcpy(c.vexs[13].introduction ,\室内小型游泳馆\strcpy(c.vexs[14].name ,\彩虹桥\ strcpy(c.vexs[14].introduction ,\彩虹桥,桥上有彩虹灯\strcpy(c.vexs[15].name ,\小木桥\ strcpy(c.vexs[15].introduction ,\小木桥,环境优雅\strcpy(c.vexs[16].name ,\沙滩\ strcpy(c.vexs[16].introduction ,\河边的沙滩\strcpy(c.vexs[17].name ,\奇石\ strcpy(c.vexs[17].introduction ,\奇石大石头\ strcpy(c.vexs[18].name ,\超市\ strcpy(c.vexs[18].introduction ,\超市\ strcpy(c.vexs[19].name ,\欧阳亭\ strcpy(c.vexs[19].introduction ,\亭高3楼\ strcpy(c.vexs[20].name ,\明光塔\ strcpy(c.vexs[20].introduction ,\明光塔\ strcpy(c.vexs[21].name ,\雷峰塔\ strcpy(c.vexs[21].introduction ,\雷锋塔\ strcpy(c.vexs[22].name ,\洞庭湖\ strcpy(c.vexs[22].introduction ,\洞庭湖\ strcpy(c.vexs[23].name ,\苏提\ strcpy(c.vexs[23].introduction ,\苏提\ strcpy(c.vexs[24].name ,\灯塔\ strcpy(c.vexs[24].introduction ,\灯塔\ strcpy(c.vexs[25].name ,\ strcpy(c.vexs[25].introduction ,\ strcpy(c.vexs[26].name ,\树林\ strcpy(c.vexs[26].introduction ,\有很多树\ strcpy(c.vexs[27].name ,\ strcpy(c.vexs[27].introduction ,\ //依次输入边上的权值信息 for(i=0;i c.arcs [i][j].adj =Infinity; //先初始化图的邻接矩阵 //部分弧长 c.arcs[0][2].adj=50; c.arcs[0][3].adj=60; c.arcs[1][4].adj=90; c.arcs[2][3].adj=60; c.arcs[2][8].adj=40; c.arcs[3][4].adj=60; c.arcs[3][6].adj=40; c.arcs[4][5].adj=70; c.arcs[4][9].adj=70; c.arcs[4][10].adj=80; c.arcs[4][17].adj=200; c.arcs[5][7].adj=70; c.arcs[6][9].adj=40; c.arcs[7][18].adj=190; c.arcs[8][11].adj=50; c.arcs[9][12].adj=40; c.arcs[10][18].adj=70; c.arcs[11][12].adj=60; c.arcs[11][14].adj=50; c.arcs[11][15].adj=50; c.arcs[12][16].adj=50; c.arcs[13][14].adj=40; c.arcs[13][22].adj=60; c.arcs[14][15].adj=50; c.arcs[14][20].adj=90; c.arcs[15][16].adj=60; c.arcs[15][21].adj=40; c.arcs[16][17].adj=60; c.arcs[17][18].adj=80; c.arcs[18][19].adj=60; c.arcs[20][21].adj=60; c.arcs[20][24].adj=80; c.arcs[22][23].adj=60; c.arcs[22][25].adj=80; c.arcs[23][24].adj=60; c.arcs[24][26].adj=100; c.arcs[24][27].adj=100; c.arcs[25][26].adj=90; c.arcs[26][27].adj=90; for(i=0;i for(j=0;j c.arcs[j][i].adj =c.arcs[i][j].adj ; return c; }//initgraph // (2) 查找景点在图中的序号 int locatevex(mgraph c,int v) { int i; for(i=0;i if(v==c.vexs[i].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(d[k]==n && k<8) //d[k]存储路径顶点。若d[k]是终点n且景点个数<=8,则输出该路径 { //递归出口,找到一条路径 for(s=0;s printf(\输出该路径。s=0 时为起点m printf(\输出最后一个景点名(即顶点n的名字,此时s==k) printf(\ } else { s=0; while(s if((c.arcs[d[k]][s].adj visited[s]=1; d[k+1]=s; //存储顶点编号s 至d[k+1]中 path(c,m,n,t); //求从下标为t=k+1的第d[t]个顶点开始的路径(递归调用),同时打印出一条m至n的路径
数据结构公园导游



