| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1079 人关注过本帖
标题:数据结构课程设计:最少换车次数问题,求帮忙修改补充程序代码!不胜感激! ...
只看楼主 加入收藏
嗨、你的益达
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2011-6-11
收藏
 问题点数:0 回复次数:6 
数据结构课程设计:最少换车次数问题,求帮忙修改补充程序代码!不胜感激!!!
最少换车次数问题。
问题描述: 设某城市有n个车站,并有m条公交线路连接这些车站。设这些公交车
都是单向的,这n个车站被顺序编号为0-n-1。编号程序,输入该城市的公交线路数,
车站个数,以及各公交线路上的各站编号。
    实现要求:求得从站0出发乘公交车至站n一1的最少换车次数。
    程序设计思路:利用输入信息构建一张有向图G(用邻接短阵g表示),有向图的顶
点是车站,若有某条公交线路经i站能到达j站,就在顶点i到顶点j之间设置一条权为
1的有向边<i,j)。这样,从站x至站y的最少上车次数便对应于图G中从点x至点y
的最短路径长度。而程序要求的换车次数就是上车次数减1
/*
问题描述: 设某城市有n个车站,并有m条公交线路连接这些车站。设这些公交车
都是单向的,这n个车站被顺序编号为0-n-1。编号程序,输入该城市的公交线路数,
车站个数,以及各公交线路上的各站编号。
    实现要求:求得从站0出发乘公交车至站n一1的最少换车次数。
    程序设计思路:利用输入信息构建一张有向图G(用邻接短阵g表示),有向图的顶
点是车站,若有某条公交线路经i站能到达j站,就在顶点i到顶点j之间设置一条权为
1的有向边<i,j)。这样,从站x至站y的最少上车次数便对应于图G中从点x至点y
的最短路径长度。而程序要求的换车次数就是上车次数减1。
*/

#include <stdio.h>
#include <string.h>
#define MAX 100000

struct Node
{
    char v;
    bool isinS;
    int way_long;
};

class Graph
{
public:
    Graph();
    void LoadMessage(char *filename,int n);
    void FindMinWay(int begin,char path[][100]);
    int GraphSize()
    {return sum;}
    Node vec[50];
private:
    int sum;
    int matix[50][50];   
};

Graph::Graph()
{
    sum = 0;
    memset(matix,0,sizeof(matix));
    memset(vec,0,sizeof(vec));
}

void Graph::LoadMessage(char *filename,int n)
{
    this->sum = n;
    int i,j,k;
    FILE *fp = fopen(filename,"r");
    for(i = 0;i<n;i++)
        fscanf(fp,"%c ",&vec[i].v);

    for(i = 0;i<n;i++)
        for(j = 0;j<n;j++)
        {
            fscanf(fp,"%d",&matix[i][j]);
            if(i != j && matix[i][j] == 0)
                matix[i][j] = MAX;
        }
}

void Graph::FindMinWay(int begin,char path[][100])
{
    begin -= 1;
    int i,j,k;
    vec[begin].isinS = true;
    for(i = 0;i<sum;i++)
    {
        path[i][begin] = true;
        vec[i].way_long = this->matix[begin][i];
    }

    for(i = 0;i<sum;i++)
    {
        int min = MAX;
        int pmin = 0;
        for(j = 0;j<sum;j++)
            if(!vec[j].isinS && vec[j].way_long < min)
            {
                min = vec[j].way_long;
                pmin = j;
            }
        vec[pmin].isinS = true;
        for(j = 0;j<sum;j++)
        {
            if(!vec[j].isinS && vec[j].way_long > vec[pmin].way_long + matix[pmin][j])
            {
                strcpy(path[j],path[pmin]);
                path[j][pmin] = true;
                vec[j].way_long = vec[pmin].way_long + matix[pmin][j];
            }
        }
        path[i][i] = true;
    }
}

int main()
{
    char path[50][100] = {false};
    char filename[] = "迪杰特斯拉.txt";
    Graph g;
    g.LoadMessage(filename,5);
    g.FindMinWay(1,path);
    int i,j,k;
    for(i = 0;i<g.GraphSize();i++)
    {
        printf("到%c的最短路径为",g.vec[i].v);
        for(j = 0;j<100;j++)
        {
            if(path[i][j])
            {
                printf("%c ",g.vec[j].v);
            }
        }
        printf("长度为%d\n",g.vec[i].way_long);
    }
    return 0;
}希望帮我改进下


或者用以下代码补充:
#include <vector>
#include <iostream>
using namespace std;
typedef struct Nearest {
    int i ;
     Nearest * next;
} Near;

int main()
{
 vector<Near *> test;
 int iNumOfStations = 0;
 int iNumNearStations =0;
 int station =0;
 Near* temp = NULL;
 Near* next = NULL;
 Near* head = NULL;
 cout<<"pleaase enter the number of stations"<<endl;
 cin>>iNumOfStations;
 for(int i=1;i<=iNumOfStations;i++) {
   
   cout<<"please input the " <<i<<"th has how many nearest stations"<<endl;
   cin>>iNumNearStations;

   for(int j=1;j<=iNumNearStations;j++) {
       temp = new Near();
       cout<<"please input the" <<j<< " station "<<endl;
       cin>>station;
       temp->i = station;
       temp->next = next;
       next = temp;
      
   }
   head = temp;
   test.push_back(head);
   next = NULL;
   head = NULL;
   temp = NULL;
   
 }
 return 0;
 }
小弟不胜感激

[ 本帖最后由 嗨、你的益达 于 2011-6-12 13:18 编辑 ]
搜索更多相关主题的帖子: 不胜感激 公交车 公交线路 车站 
2011-06-11 20:17
灿烂烟火
Rank: 2
来 自:湖北武汉
等 级:论坛游民
帖 子:12
专家分:36
注 册:2011-5-10
收藏
得分:0 
C++看不懂
2011-06-13 22:01
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
最少换车次数
    和两点间的最短路径有什么关系?
2011-06-14 21:39
finalken
Rank: 2
等 级:论坛游民
威 望:1
帖 子:30
专家分:94
注 册:2007-10-2
收藏
得分:0 
换车次数就是最短路径减1么。
就是个单源最短路径的实现。
连个输入数据说明也没有。。。。。。。。。。
2011-06-15 12:01
jiashibo
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2011-5-24
收藏
得分:0 
是acm题吗?我帮你看看?
2011-06-28 09:18
司林林
Rank: 2
等 级:论坛游民
帖 子:7
专家分:12
注 册:2011-6-16
收藏
得分:0 
《数字技术与应用》8月份征稿。QQ:973530901
2011-06-28 09:45
嗨、你的益达
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2011-6-11
收藏
得分:0 
不是,解决了,谢谢
2011-07-15 15:33
快速回复:数据结构课程设计:最少换车次数问题,求帮忙修改补充程序代码!不胜感 ...
数据加载中...
 
   



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

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