数据结构---校园导游有点问题

阮文明 发布于 2012/12/16 13:41
阅读 358
收藏 0

谁给我解释下void ShortestPath_DIJ(MGraph * G)和void Floyd(MGraph *G)这两个函数各个参数是什么意思,最后加上注释,特别是二维数组p是什么意思啊,看不懂

#define INFINITY      10000       /*无穷大*/
#define MAX_VERTEX_NUM      40
#define MAX 40
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>
typedef struct ArCell
{
 int adj;    //路径长度
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct   //图中顶点表示主要景点,存放景点的编号、名称、简介等信息,
{
 char name[30];
 int num;
 char introduction[200];//简介
}infotype;
typedef struct
{
 infotype vexs[MAX_VERTEX_NUM];//景点
 AdjMatrix arcs;//路径数组
 int vexnum,arcnum;//景点数,路径长度记录
}MGraph;
MGraph b;//全局变量
void cmd(void);//在主函数中用来调用其他应用子函数的函数声明
MGraph InitGraph(void);//用来构造学校地图的子函数 返回MGraph类型
void Menu(void);//菜单函数;
void Browser(MGraph *G);//调用MGraph类型的地址,进行
void ShortestPath_DIJ(MGraph * G);//迪杰斯特拉算法求最短路径的子函数
void Floyd(MGraph *G);//佛洛伊德算法
void Search(MGraph *G);//寻找要查询的景点,并输出该景点的信息

 

/******************************************************/
int main(void)
{
 system("color 1f");//设置调试窗口背景和字体颜色
 system("mode con: cols=140 lines=130");//设置调试窗口的大小
 cmd();//用该函数来调用其他需要用到的函数
}
/******************************************************/
void cmd(void)//用来调用其他需要用到的函数的子函数
{
 int i;
 b=InitGraph();//构造校园地图
 Menu();//调用菜单函数
 scanf("%d",&i);
 while(i!=5)
 {
  switch(i)
  {
  case 1:system("cls");Browser(&b);Menu();break;
  case 2:system("cls");ShortestPath_DIJ(&b);Menu();break;
  case 3:system("cls");Floyd(&b);Menu();break;
  case 4:system("cls");Search(&b);Menu();break;
  case 5:exit(1);break;
  default:break;
  }
  scanf("%d",&i);
 }
}
//************************************************************************
MGraph InitGraph(void)//构造校园地图
{
 MGraph G;
 int i,j;
 G.vexnum=10;//景点数量
 G.arcnum=14;//路径数量
 for(i=0;i<G.vexnum;i++)
  G.vexs[i].num=i;//对景点进行对应编号
 /*对对应的景点编号进行命名,输入简介*/
 strcpy(G.vexs[0].name,"行政楼");
       strcpy(G.vexs[0].introduction,"学校的行政机构");
 strcpy(G.vexs[1].name,"图书馆");
 strcpy(G.vexs[1].introduction,"藏书200万册,设施良好,环境幽雅");
 strcpy(G.vexs[2].name,"新理科楼");
 strcpy(G.vexs[2].introduction,"学校最气派的教学楼,里面的设施比较好");
      strcpy(G.vexs[3].name,"川味府");
 strcpy(G.vexs[3].introduction,"里面有南方各种美食,就餐环境幽雅");
 strcpy(G.vexs[4].name,"洗浴中心");
 strcpy(G.vexs[4].introduction,"学校唯一的澡堂,在川味府旁边");
 strcpy(G.vexs[5].name,"中心体育场");
 strcpy(G.vexs[5].introduction,"化塑胶跑道,人造草坪,适宜锻炼身体的场所");
 strcpy(G.vexs[6].name,"会堂");
 strcpy(G.vexs[6].introduction,"学校有大型的晚会都在这里举行");
 strcpy(G.vexs[7].name,"钟楼广场");
 strcpy(G.vexs[7].introduction,"是连大学子展现才华的地方,旁有邮局");
 strcpy(G.vexs[8].name,"新文科楼");
 strcpy(G.vexs[8].introduction,"里面包含几个学院");
 strcpy(G.vexs[9].name,"清缘超市");
 strcpy(G.vexs[9].introduction,"学校最大的超市,里面有很多学生使用的商品");
//对有路的各景点之间的路径长度进行设置,没路的设置为无穷大
 for(i=0;i<G.vexnum;i++)
     for(j=0;j<G.vexnum;j++)
  G.arcs[i][j].adj=INFINITY;
  G.arcs[0][1].adj=100;
  G.arcs[0][2].adj=150;
  G.arcs[0][6].adj=200;
  G.arcs[1][7].adj=150;
  G.arcs[2][3].adj=50;
  G.arcs[3][6].adj=50;
  G.arcs[3][4].adj=20;
  G.arcs[4][5].adj=200;
  G.arcs[4][9].adj=150;
  G.arcs[5][9].adj=350;
  G.arcs[6][7].adj=60;
  G.arcs[6][9].adj=80;
  G.arcs[7][8].adj=50;
  G.arcs[8][9].adj=20;
//无向图的路径是相互的
 for(i=0;i<G.vexnum;i++)
 for(j=0;j<G.vexnum;j++)
  G.arcs[j][i].adj=G.arcs[i][j].adj;
    return G;
}//InitGraph end
//*****************************************************************************
//菜单函数,打印出导游项目菜单
void Menu()
{
 printf("\n                                      大连大学校园导游图\n");
 printf("                          ┏━━━━━━━━━━━━━━━━━━━━┓\n");
 printf("                          ┃   1.浏览校园全景                       ┃\n");
 printf("                          ┃   2.查看所有游览路线                   ┃\n");
 printf("                          ┃   3.选择出发点和目的地                 ┃\n");
 printf("                          ┃   4.查看景点信息                       ┃\n");
 printf("                          ┃   5.退出系统                           ┃\n");
 printf("                          ┗━━━━━━━━━━━━━━━━━━━━┛\n");
 printf("Option-->:");
}
//********************************************************************************
//输出所有景点信息
void Browser(MGraph *G)
{
 int v;
 printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
 printf("┃编号┃景点名称        ┃简介                                                      ┃\n");
 for(v=0;v<G->vexnum;v++)
 printf("┃%-4d┃%-16s┃%-58s┃\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction);
 printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
}
//***********************************************************************************
// 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点
void ShortestPath_DIJ(MGraph * G)
{
 int v,w,i,min,t=0,x,flag=1,v0;
    int final[20], D[20], p[20][20];

 while(flag)
 {
  printf("请输入一个起始景点编号:");
  scanf("%d",&v0);
  if(v0<0||v0>G->vexnum)
  {
   printf("景点编号不存在!请重新输入景点编号:");
   scanf("%d",&v0);
  }
  if(v0>=0&&v0<G->vexnum)
  flag=0;
 }

 for(v=0;v<G->vexnum;v++)
 {
  final[v]=0;
  D[v]=G->arcs[v0][v].adj;

  for(w=0;w<G->vexnum;w++)
   p[v][w]=0;
  if(D[v]<INFINITY)
  {
   p[v][v0]=1;p[v][v]=1;
  }
 }

 D[v0]=0;final[v0]=1;
 for(i=1;i<G->vexnum;i++)
 {
  min=INFINITY;
  for(w=0;w<G->vexnum;w++)
   if(!final[w])
    if(D[w]<min){v=w;min=D[w];}
     final[v]=1;
  for(w=0;w<G->vexnum;w++)
   if(!final[w]&&(min+G->arcs[v][w].adj<D[w]))
   {
    D[w]=min+G->arcs[v][w].adj;
    for(x=0;x<G->vexnum;x++)
     p[w][x]=p[v][x];
    p[w][w]=1;
   }
 }
 for(v=0;v<G->vexnum;v++)
 {
  if(v0!=v) printf("%s",G->vexs[v0].name);
  for(w=0;w<G->vexnum;w++)
  {
   if(p[v][w]&&w!=v0)  printf("-->%s",G->vexs[w].name);
   t++;
  }
  if(t>G->vexnum-1&&v0!=v)printf("       总路线长%dm\n\n",D[v]);
 }

}//ShortestPath_DIJ  end

//*********************************************************************

void Floyd(MGraph *G)
{
 int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
 for(v=0;v<G->vexnum;v++)
  for(w=0;w<G->vexnum;w++)
  {
   D[v][w]=G->arcs[v][w].adj;
   for(u=0;u<G->vexnum;u++)
    p[v][w][u]=0;
   if(D[v][w]<INFINITY)
   {
    p[v][w][v]=1;p[v][w][w]=1;
   }
  }
 for(u=0;u<G->vexnum;u++)
  for(v=0;v<G->vexnum;v++)
   for(w=0;w<G->vexnum;w++)
    if(D[v][u]+D[u][w]<D[v][w])
    {
     D[v][w]=D[v][u]+D[u][w];
     for(i=0;i<G->vexnum;i++)
      p[v][w][i]=p[v][u][i]||p[u][w][i];
    }

 while(flag)
 {
  printf("请输入出发点和目的地的编号:");
  scanf("%d%d",&k,&j);
  if(k<0||k>G->vexnum||j<0||j>G->vexnum)
  {
   printf("景点编号不存在!请重新输入出发点和目的地的编号:");
   scanf("%d%d",&k,&j);
  }
  if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)
  flag=0;
 }
 printf("%s",G->vexs[k].name);
 for(u=0;u<G->vexnum;u++)
  if(p[k][j][u]&&k!=u&&j!=u)
   printf("-->%s",G->vexs[u].name);
 printf("-->%s",G->vexs[j].name);
 printf(" 总路线长%dm\n",D[k][j]);
}//Floyd end
//****************************************************************
//寻找要查询的景点,并输出该景点的信息
void Search(MGraph *G)
{
 int k,flag=1;
 while(flag)
 {
  printf("请输入要查询的景点编号:");
  scanf("%d",&k);
  if(k<0||k>G->vexnum)
  {
   printf("景点编号不存在!请重新输入景点编号:");
   scanf("%d",&k);
  }
  if(k>=0&&k<G->vexnum)
  flag=0;
 }
 printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
 printf("┃编号┃景点名称        ┃简介                                                    ┃\n");
 printf("┃%-4d┃%-16s┃%-56s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);
 printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");

}//Search end

加载中
0
cut
cut

Floyd是全路径最短路径寻路算法,计算复杂度是O(N^3),ShortestPath_DIJ 是迪杰斯特拉单源最短路径算法,常用的路由算法,计算复杂度是O(N^2),计算复杂度高,其实不适合实时地图寻路,一般做法应该是先用全路径最短路径寻路做一个数据库,然后建立索引,查地点。或者使用发散算法A*搞单源查找,然后缓存路径之类的。不过A*算法复杂度在于你F(N) = G(N) + H(N)中的算法设定,算法最坏的情况复杂度是O(N^2)

 

参数MGraph*就是传入一个图的含所有节点的指针,这个你去看看你的数据结构课本就很容易理解
阮文明
阮文明
看下咯 我加你qq吧 你qq多少啊 我郁闷 其他的都懂 就是不知道那个数组p是代表什么东西啊
阮文明
阮文明
那个函数形参我知道啊,我是说里面的那个的那些参数是代表什么特别是那个二维数组P和三位数组P分别是用来干嘛的
cut
cut
看样子是路径的节点,没细看,命名太恶心,建议你对着课本看
阮文明
阮文明
我知道,我只是想问下那两个函数里面的二维数组P和三位数组P是代表什么啊,他们代表的意思是什么,看不太懂
0
雨翔河
雨翔河

这是一个图,void ShortestPath_DIJ(MGraph * G),其中MGraph是图的结构体名称,用指针的意思就是表示G这个数据在函数里面会改变值,它不想用函数返回来带回他的值,就用指针来带回。

第二,p的用处,代码有点乱,我没仔细看,在图里面有一个记录是否曾经访问过的点的数组,估计p就是这个数组。

雨翔河
雨翔河
回复 @阮文明 : 771297972,一般是webqq在线
阮文明
阮文明
我也是江西的
阮文明
阮文明
好像不是啊,可以加qq说不
雨翔河
雨翔河
回复 @阮文明 : 那么p就应该是记录以前有没有访问过该点的数组了。一般情况下1就是曾经访问过,0就是没有访问过。因为用邻接矩阵表示的时候,深度和广度优先搜索都有用到过那个记录是否扫描过的数组。
阮文明
阮文明
他那有三个数组啊 D数组记录的是路径长度,final[v]数组表示已经找到v0到v的最短路径,就是不知道p数组是干嘛的,后面一个函数还用到三维数组p
下一页
0
雨翔河
雨翔河
771297972,一般是webqq在线
返回顶部
顶部