三维数组不知哪里有问题

鹏城二少 发布于 2012/05/24 16:52
阅读 244
收藏 0

代码如下:

/***********************************
 *此程序功能是求50个顶点时,有三个点
 *作为车站时的最短路径
 ***********************************/

#include <stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 51                             //矩阵大小51*51,a[0][i]与a[i][0]不用
#define TRUE 1
#define FALSE 0
#define INFINITY 32767                                //用整型最大值代替∞
typedef int VERTYPE;
///////////////////////////////////////////////////////
//mgraph数据结构
typedef struct
{   
 VERTYPE  vexs[MAX_VERTEX_NUM];                   //顶点向量   
 int      arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   //邻接矩阵   
 int      vexnum,arcnum;                          //图的当前顶点数和弧数
}mgraph, * MGraph;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];

///////////////////////////////////////////////////////
//初始化图
void init_mgraph(MGraph &g) 
{   
 g=(MGraph)malloc(sizeof(mgraph));
    g->vexnum=50;  //初始顶点数位50 
 g->arcnum=0;  //初始弧数为0
 for(int i=1;i<=g->vexnum;i++)       
  g->vexs[i]= i; 
 
 for(i=1;i<=g->vexnum;i++)       
  for(int j=1;j<=g->vexnum;j++)          
   g->arcs[i][j] = (i == j ?0:INFINITY);
 //////////////////////////////////////////
 //无向图由两部分构成,即A--->B的有向图和//
 //B--->A的有向图                        //
 //////////////////////////////////////////

 /*下面首先构建A---->B的有向图*/
    g->arcs[1][2]   = 400;
 g->arcs[1][3]   = 450;
 g->arcs[2][4]   = 300;
 g->arcs[2][21]  = 230;
 g->arcs[2][47]  = 140;
 g->arcs[3][4]   = 600;
 g->arcs[4][5]   = 210;
 g->arcs[4][19]  = 310;
 g->arcs[5][6]   = 230;
 g->arcs[5][7]   = 200;
 g->arcs[6][7]   = 320;
 g->arcs[6][8]   = 340;
 g->arcs[7][8]   = 170;
 g->arcs[7][18]  = 160;
 g->arcs[8][9]   = 200;
 g->arcs[8][15]  = 285;
 g->arcs[9][10]  = 180;
 g->arcs[10][11] = 150;
 g->arcs[10][15] = 160;
 g->arcs[11][12] = 140;
 g->arcs[11][14] = 130;
    g->arcs[12][13] = 200;
 g->arcs[13][34] = 400;
 g->arcs[14][15] = 190;
 g->arcs[14][26] = 190;
 g->arcs[15][16] = 170;
 g->arcs[15][17] = 250;
 g->arcs[16][17] = 140;
 g->arcs[16][18] = 130;
 g->arcs[17][27] = 240;
 g->arcs[18][19] = 204;
 g->arcs[18][25] = 180;
 g->arcs[19][20] = 140;
 g->arcs[19][24] = 175;
 g->arcs[20][21] = 180;
 g->arcs[20][24] = 190; 
 g->arcs[21][22] = 300;
 g->arcs[21][23] = 270;
 g->arcs[21][47] = 350;
 g->arcs[22][44] = 160;
 g->arcs[22][45] = 270;
 g->arcs[22][48] = 180;
 g->arcs[23][24] = 240;
 g->arcs[23][29] = 210;
 g->arcs[23][30] = 290;
 g->arcs[23][44] = 150;
 g->arcs[24][25] = 170;
 g->arcs[24][28] = 130;
 g->arcs[26][27] = 140;
 g->arcs[26][34] = 320;
 g->arcs[27][28] = 190;
 g->arcs[28][29] = 260;
 g->arcs[29][31] = 190;
 g->arcs[30][31] = 240;
 g->arcs[30][42] = 130;
 g->arcs[30][43] = 210;
 g->arcs[31][32] = 230;
 g->arcs[31][36] = 260;
 g->arcs[31][50] = 210;
 g->arcs[32][33] = 190;
 g->arcs[32][35] = 140;
 g->arcs[32][36] = 240;
 g->arcs[33][34] = 210;
 g->arcs[35][37] = 160;
 g->arcs[36][39] = 180;
 g->arcs[36][40] = 190;
 g->arcs[37][38] = 135;
 g->arcs[38][39] = 130;
 g->arcs[39][41] = 310;
 g->arcs[40][41] = 140;
 g->arcs[40][50] = 190;
 g->arcs[42][50] = 200;
 g->arcs[43][44] = 260;
 g->arcs[43][45] = 210;
 g->arcs[45][46] = 240;
 g->arcs[46][48] = 280;
 g->arcs[48][49] = 200;
    /*构建B---->A的有向图*/
 g->arcs[2][1]   = 400;
 g->arcs[3][1]   = 450;
 g->arcs[4][2]   = 300;
 g->arcs[21][2]  = 230;
 g->arcs[47][2]  = 140;
 g->arcs[4][3]   = 600;
 g->arcs[5][4]   = 210;
 g->arcs[19][4]  = 310;
 g->arcs[6][5]   = 230;
 g->arcs[7][5]   = 200;
 g->arcs[7][6]   = 320;
 g->arcs[8][6]   = 340;
 g->arcs[8][7]   = 170;
 g->arcs[18][7]  = 160;
 g->arcs[9][8]   = 200;
 g->arcs[15][8]  = 285;
 g->arcs[10][9]  = 180;
 g->arcs[11][10] = 150;
 g->arcs[15][10] = 160;
 g->arcs[12][11] = 140;
 g->arcs[14][11] = 130;
 g->arcs[13][12] = 200;
 g->arcs[34][13] = 400;
 g->arcs[15][14] = 190;
 g->arcs[26][14] = 190;
 g->arcs[16][15] = 170;
 g->arcs[17][15] = 250;
 g->arcs[17][16] = 140;
 g->arcs[18][16] = 130;
 g->arcs[27][17] = 240;
 g->arcs[19][18] = 204;
 g->arcs[25][18] = 180;
 g->arcs[20][19] = 140;
 g->arcs[24][19] = 175;
 g->arcs[21][20] = 180;
 g->arcs[24][20] = 190; 
 g->arcs[22][21] = 300;
 g->arcs[23][21] = 270;
 g->arcs[47][21] = 350;
 g->arcs[44][22] = 160;
 g->arcs[45][22] = 270;
 g->arcs[48][22] = 180;
 g->arcs[24][23] = 240;
 g->arcs[29][23] = 210;
 g->arcs[30][23] = 290;
 g->arcs[44][23] = 150;
 g->arcs[25][24] = 170;
 g->arcs[28][24] = 130;
 g->arcs[27][26] = 140;
 g->arcs[34][26] = 320;
 g->arcs[28][27] = 190;
 g->arcs[29][28] = 260;
 g->arcs[31][29] = 190;
 g->arcs[31][30] = 240;
 g->arcs[42][30] = 130;
 g->arcs[43][30] = 210;
 g->arcs[32][31] = 230;
 g->arcs[36][31] = 260;
 g->arcs[50][31] = 210;
 g->arcs[33][32] = 190;
 g->arcs[35][32] = 140;
 g->arcs[36][32] = 240;
 g->arcs[34][33] = 210;
 g->arcs[37][35] = 160;
 g->arcs[39][36] = 180;
 g->arcs[40][36] = 190;
 g->arcs[38][37] = 135;
 g->arcs[39][38] = 130;
 g->arcs[41][39] = 310;
 g->arcs[41][40] = 140;
 g->arcs[50][40] = 190;
 g->arcs[50][42] = 200;
 g->arcs[44][43] = 260;
 g->arcs[45][43] = 210;
 g->arcs[46][45] = 240;
 g->arcs[48][46] = 280;
 g->arcs[49][48] = 200;
}

///////////////////////////////////////////////////////
//Dijkstra算法
void ShortestPath_DIJ(MGraph &g, int v0, PathMatrix *P, ShortPathTable *D)
{   // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]。   
    // 若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。   
 // final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。   
 int v,w,i,j,min;   
 int final[MAX_VERTEX_NUM];   
 for(v=1; v<=g->vexnum; ++v)   
 {       
  final[v] = FALSE;       
  (*D)[v] = g->arcs[v0][v];
  for(w=1; w<=g->vexnum; ++w)           
   (*P)[v][w] = FALSE;        //设空路径       
  if((*D)[v] < INFINITY)         //v0可以直接到达的点v       
  {           
   (*P)[v][v0] = TRUE;        //v0是v0直接到达v的路径的始点           
      (*P)[v][v] = TRUE;         //v是v0直接到达v的路径的终点      
  }
 }  
 (*D)[v0] = 0;   
 final[v0] = TRUE;    //初始化,v0顶点属于S集       
 //开始主循环,每次求得v0到某个v顶点的最短路径,并加入v到S集   
 for(i=1; i<g->vexnum; i++)    //其余g.vexnum-1个顶点   
 {       
  min=INFINITY;             //当前所知离v0顶点的最近距离       
  for(w=1; w<=g->vexnum; w++)       
  {           
   if(!final[w] && (*D)[w]<min) //w顶点在V-S中           
   {                   
    v=w;                   
    min = (*D)[w];           //w顶点离v0顶点更近           
   }       
  }       
  final[v] = TRUE;                 //离v0顶点最近的v加入S集       
  for(w=1; w<=g->vexnum; w++)       
  {   //更新当前最短路径及距离           
   if(!final[w] && (min+g->arcs[v][w]<(*D)[w])) //如果经过v顶点的路径比现在这条路径的长度短的话           
   {   // 修改D[w]和P[w],w∈V-S               
    (*D)[w] = min + g->arcs[v][w];           //修改当前路径长度               
    for(j=1;j<=g->vexnum;++j) 
     (*P)[w][j]=(*P)[v][j];               //将经过v点的路径复制过来               
    (*P)[w][w]=TRUE;                         //最后的重点为TURE     
   }       
  }   
 }
}

///////////////////////////////////////////////////////
//main主函数
void main()
{   int i, j, k, l;
 int num = 0;              //num用于换行
 MGraph G;   
 init_mgraph(G);           //初始化图  
 PathMatrix P[51];         //p[0]不用 
 ShortPathTable D[51];     //求某点到其余各点的最短路径,D[0]不用     
 int v[51];                //v[0]不用
 for(i=1;i<=G->vexnum;++i) //求50个点到其余个点的最短距离
 {
  v[i] = i; 
  ShortestPath_DIJ(G, v[i], &P[i], &D[i]); 
 }   
 

    printf("各源点到各顶点的最短路径长度矩阵如下:\n");
    for(i=1;i<=G->vexnum;++i) 
 {
      printf("%d    ", i);
  for(j=1;j<=G->vexnum;++j)
   printf("%-4d ", D[i][j]);
  printf("\n");
 }
/*********************************
 *这个程序从这里开始就有问题了,
 *但是不知道这个三维数组加到里
 *面后,为什么就有问题?
 *********************************/
 int min;
 int sum[51][51][51];

 for(i=1;i<=G->vexnum-2;++i)
  for(j=i+1;j<=G->vexnum-1;++j)
   for(k=j+1;k<=G->vexnum;++k)
    sum[i][j][k] = 0;
    
 for(i=1;i<=G->vexnum-2;++i)
  for(j=i+1;j<=G->vexnum-1;++j)
   for(k=j+1;k<=G->vexnum;++k)
    for(l=1;l<=G->vexnum;++l)
    {
     min = (((D[i][l]<D[j][l]) ? D[i][l]:D[j][l]) < D[k][l]) ? ((D[i][l]<D[j][l]) ? D[i][l]:D[j][l]) : D[k][l];
     sum[i][j][k] += min;
    }

 int MIN = sum[1][2][3];
 for(i=1;i<=G->vexnum-2;++i)
  for(j=i+1;j<=G->vexnum-1;++j)
   for(k=j+1;k<=G->vexnum;++k)
    if(MIN > sum[i][j][k])
     MIN = sum[i][j][k];
    
 printf("\n最短距离:%d", MIN);
 for(i=1;i<=G->vexnum-2;++i)
  for(j=i+1;j<=G->vexnum-1;++j)
   for(k=j+1;k<=G->vexnum;++k)
    if(MIN == sum[i][j][k])
    {
     printf("\ni=%d,j=%d,k=%d\n", i, j, k);
     break;
    }
}

以下是问题补充:

@鹏城二少:错误在main中,里面的那个三位数组有问题,但不知道哪里有问题,求大哥大姐指出!感激不尽! (2012/05/24 16:54)
@鹏城二少:错误在main中,里面的那个三位数组有问题,但不知道哪里有问题,求大哥大姐指出!感激不尽! (2012/05/24 16:54)
加载中
0
中山野鬼
中山野鬼
什么类型的错。同时你把for 循环的花括号全部打上。
鹏城二少
鹏城二少
我已经知道是什么错了,属于指针数组乱用问题
中山野鬼
中山野鬼
回复 @李玉林 : 我没跑你的代码,你编译链接没错吗?
鹏城二少
鹏城二少
大哥,什么类型错了啊???能说明白一点不?那个for循环好像不用{}也可以啊? 叩拜!!!
返回顶部
顶部