数据结构课程设计：最少换车次数问题，求帮忙修改补充程序代码！不胜感激！！！
最少换车次数问题。问题描述: 设某城市有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 编辑 ]
