bec666 2019-10-15 22:44 采纳率: 88%
浏览 161
已结题

关于指针和引用的问题?

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */

typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

/* 构件图 */
void CreateMGraph(MGraph *G)
{
    int i, j;

    /* printf("请输入边数和顶点数:"); */
    G->numEdges=16;
    G->numVertexes=9;

    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        G->vexs[i]=i;
    }

    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITY;
        }
    }

    G->arc[0][1]=1;
    G->arc[0][2]=5; 
    G->arc[1][2]=3; 
    G->arc[1][3]=7; 
    G->arc[1][4]=5; 

    G->arc[2][4]=1; 
    G->arc[2][5]=7; 
    G->arc[3][4]=2; 
    G->arc[3][6]=3; 
    G->arc[4][5]=3;

    G->arc[4][6]=6;
    G->arc[4][7]=9; 
    G->arc[5][7]=5; 
    G->arc[6][7]=2; 
    G->arc[6][8]=7;

    G->arc[7][8]=4;


    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }

}

/* Floyd算法,求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */    
void ShortestPath_Floyd(MGraph G, Patharc &P, ShortPathTable *D)
{    
    int v,w,k;    
    for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */  
    {        
        for(w=0; w<G.numVertexes; ++w)  
        {
            (*D)[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */
            P[v][w]=w;              /* 初始化P */
        }
    }
    for(k=0; k<G.numVertexes; ++k)   
    {
        for(v=0; v<G.numVertexes; ++v)  
        {        
            for(w=0; w<G.numVertexes; ++w)    
            {
                if ((D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {/* 如果经过下标为k顶点路径比原两点间路径更短 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */
                    p[v][w]=P[v][k];/* 路径设置为经过下标为k的顶点 */
                }
            }
        }
    }
}

int main(void)
{    
    int v,w,k;  
    MGraph G;    

    Patharc P;    
    ShortPathTable D; /* 求某点到其余各点的最短路径 */   

    CreateMGraph(&G);

    ShortestPath_Floyd(G,P,&D);  

    printf("各顶点间最短路径如下:\n");    
    for(v=0; v<G.numVertexes; ++v)   
    {        
        for(w=v+1; w<G.numVertexes; w++)  
        {
            printf("v%d-v%d weight: %d ",v,w,D[v][w]);
            k=P[v][w];              /* 获得第一个路径顶点下标 */
            printf(" path: %d",v);  /* 打印源点 */
            while(k!=w)             /* 如果路径顶点下标不是终点 */
            {
                printf(" -> %d",k); /* 打印路径顶点 */
                k=P[k][w];          /* 获得下一个路径顶点下标 */
            }
            printf(" -> %d\n",w);   /* 打印终点 */
        }
        printf("\n");
    }

    printf("最短路径D\n");
    for(v=0; v<G.numVertexes; ++v)  
    {        
        for(w=0; w<G.numVertexes; ++w)    
        {
            printf("%d\t",D[v][w]);
        }
        printf("\n");
    }
    printf("最短路径P\n");
    for(v=0; v<G.numVertexes; ++v)  
    {        
        for(w=0; w<G.numVertexes; ++w)    
        {
            printf("%d ",P[v][w]);
        }
        printf("\n");
    }

    return 0;
}
_****_
  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题