| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 597 人关注过本帖, 1 人收藏
标题:数据结构校园导航的问题,求高手帮忙
只看楼主 加入收藏
geass50
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2011-12-23
收藏(1)
 问题点数:0 回复次数:0 
数据结构校园导航的问题,求高手帮忙
#include "stdafx.h"
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <iostream.h>


#define GRAPH_MAXVERTEX 30
#define GRAPH_MAXWEIGHT 99

typedef int weighttype;
typedef char vertextype;

typedef struct
{
    weighttype matrix[GRAPH_MAXVERTEX][GRAPH_MAXVERTEX];
    vertextype vertex[GRAPH_MAXVERTEX];
    int vertices;
}AdjMatrix;

int CreateGraph(AdjMatrix *G,vertextype v[],weighttype w[][GRAPH_MAXVERTEX],int n)
{
    int i,j;
    G->vertices=n;
    for(i=0;i<n;i++)
    {
        G->vertex[i]=v[i];
        for(j=0;j<n;j++)
        G->matrix[i][j]=w[i][j];
    }
    return 0;
}



struct v
{

    char name();
    int dist();
}

int PrintGraph(AdjMatrix *G)
{
    int i,j;
    for(i=0;j<G->vertices;i++)
    {
        printf("%s:\t",G->vertex[i].name);//输出顶点名称
        for(j=0;j<G->vertices;j++)//输出该顶点的所有邻接顶点
        {
            if(G->matrix[i][j]==GRAPH_MAXWEIGHT)
                continue;
            printf("->%s(%d),\t",G->vertex[j].name,G->matrix[i][j]);//邻接顶点及权
        }
        printf("\n");
    }
    return 0;
}


void DispPath(AdjMartix *G,int path[],int dist[],int start,int end)
{
    int i=-1,k;
    vertextype vex[GRAPH_MAXVERTEX];//顶点信息

    k=path[end];//终点
    while(k!=start)//取得起点到终点的顶点信息
    {
        vex[++i]=G->vertex[k];//顶点信息
        k=path[k];//下一个顶点
    }

    vex[++j]=G->vertex[start];//起始顶点
    while(i!=-1)//一次输出顶点信息
        printf("%s->",ver[i--].name);    //输出终点的顶点信息
        printf("最短路径为%d公里\n,dist[end]");  //输出距离
}

void Dijkstra(AdjMatrix *G,int v,int path[],weighttype dist[])
{
    int i,j,k,vset[GRAPH_MAXVERTEX];//v集合
    weighttype MinDist;//最短路径
   
    for(i=0;i<G->vertices;i++)
    {
        vset[i]=1;//1表示在集合中,0表示在S集合中
        dist[i]=G->matrix[v][i];//数组dis存储v到u的最短距离,初始为v到u的弧的距离
        path[i]=dist[i]<GRAPH_MAXVERTEX?v:-1;
    }
    vset[v]=0,path[v]=0;//顶点v加入到集合s
    for(i=1;i<G->vertices;i++)
    {
        MinDist=GRAPH_MAXWEIGHT;
        for(j=0;j<->vertices;j++)//在集合v中找距离v最近的顶点
            if(vset[j]&&dist[j]<MinDist)
                k=j,MinDist=dist[j];//记录顶点和最短距离

            vset[k]=0;//将距离v最近的顶点加入到s集合中
            for(j=0;j<G->vertices;j++)
                if(vset[j]&&(dist[j]>dist[k]+G->matrix[k][j]))//更新v到其他顶点的距离
                    dist[j]=dist[k]+G->martix[k][j],path[j]=k;
                }
}

int main()
{
    int i,s,d;
    AdjMatrix G;
    int path[GRAPH_MAXVERTEX];
    weighttpye dist[GRAPH_MAXVERTEX];
    vertextye v[]={"南门","教学楼","行政楼","大礼堂","学生活动中心","一期饭堂","体育馆","二期饭堂","宿舍区","北门"};
    weighttype w[][GRAPH_MAXVERTEX]=
    {             //顶点间的距离
        {999,174,27,999,999,999,999,999,999,999},
        {174,999,999,999,63,999,999,999,999,999},
        {27,999,999,80,999,67,999,999,999,999},
        {999,999,80,999,64,999,999,999,999,999},
        {999,63,999,64,999,999,999,999,999,999},
        {999,999,67,999,999,999,86,225,999,999},
        {999,999,999,145,999,86,999,999,96,105},
        {999,999,999,999,999,225,999,999,110,999},
        {999,999,999,999,999,999,96,110,999,69},
        {999,999,999,999,999,999,105,999,69,999}
    };

    printf("\n>构造图的顶点信息:\n");
    for(i=0;i<10;i++);
    {
        printf("%d:%s,",i+1,v[i].name);
        if((i+1)&5==0)
            printf("\n");
    }

    printf("\n构造图的邻接信息:\n");
    CreatGraph(&G,v,w,10);//构造图的玲姐矩阵
    printGraph(&G);//打印图的结构

    //shortestdistance  p4
printf("\n>输入出发地和目的地的建筑物编号(s->e):");
scanf("%d->%d",&s,&d);//读取出发地和目的地的编号

      printf("\n>从(%s)到(%s)的最佳行驶方案为:\n",v[--s].name,v[--d].name);
Dijkstra(&G,s,path,dist);//从出发点到各顶点的最短路径
DispPath(&G,path,dist,s,d);//输出路径信息




    return 0;
}
这个程序应该怎么样改?
搜索更多相关主题的帖子: 导航 include matrix 校园 
2011-12-25 15:22
快速回复:数据结构校园导航的问题,求高手帮忙
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026403 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved