// 先将最新写的代码贴出来，还没完全写完，在C 板块写了我的算法，大家却不能理解
// 我把代码写的具体了一些，在程序中设置了一个 vector 用于存放单一的 City Object ，每个City Object 拥有
// 两个个性：其名字，另外其邻居城市，其邻居城市也存放于一个 city vector 中。
// 目前程序一切正常。作为测试，将每个城市的邻居城市打印出来，完全正确。
// 接下来是由上至下建立 城市快，每个城市块只有一个起点城市。
// 从一个城市块的城市可以继续往下发展，直到出现这样的局面，即 V->......->...->H->....->....->V
// 也就是说从起点城市又回到了起点城市，当中只经过一次 H
// 这样我们便认为这条支路发展到了尽头。
// 我们必须有能力能够判断，是否某一条支路处于死循环，也就是说从 V 经过一些路径又回到了 V，
// 但永远不经过 H，如果这样则此题无解，这种可能性是存在的。
// 如果所有支路都最终完成，即从 V 出发，一次经过 H 又回到 V ，那么 我们 对所有 Road Object 作统计，
// 那条出现城市数最多的城市便是我们要求的解。
// 另外，我个人认为，动态开辟 2 维数组是一种很丑陋的代码，我个人不会使用。
// 建议使用 class 来模拟 2D Array，并使用 vector
// new 只有在实在不得已的情况下才使用。
// 以下是代码：
// header file: travel.h
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;
class City;
typedef vector<City> VCC;
class City
{
private:
string name;
VCC vcNeighborCity;
public:
City();
City(const string cityname); // initialize the object
string get_name();
VCC get_vcinfo();
void set_neighbor(const City & a_city); // add the neighborcity in the neighborcity vector
//.......
};
class Cityblock
{
private:
int depth;
City startcity;
VCC allcities_in_this_block;
public:
Cityblock();
Cityblock(int d, const City & start, VCC vc_allcities);
void add_city_in_block(const City & a_city);
//...
};
class Road
{
private:
VCC cities_for_a_road;
public:
void make_road(const City & a_city);
};
// city.cpp
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
#include "travel.h"
City::City()
{
name = " ";
}
City::City(const string cityname)
{
name = cityname;
}
string City::get_name()
{
return name;
}
void City::set_neighbor(const City & a_city)
{
vcNeighborCity.push_back(a_city);
}
VCC City::get_vcinfo()
{
return vcNeighborCity;
}
// cityblock.cpp
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
#include "travel.h"
Cityblock::Cityblock(){}
Cityblock::Cityblock(int d, const City & start, VCC vc_allcities)
{
depth = d;
startcity = start;
allcities_in_this_block = vc_allcities;
}
void Cityblock::add_city_in_block(const City & a_city)
{
allcities_in_this_block.push_back(a_city);
}
// road.cpp
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
#include "travel.h"
void Road::make_road(const City & a_city)
{
cities_for_a_road.push_back(a_city);
}
// travel.cpp
#include <iostream>
#include<fstream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
#include "travel.h"
int main()
{
int N,V;
//ÏÂÃæ´ò¿ªÎļþ£¬C++·½Ê½´ò¿ª
fstream file1;
file1.open("travel.txt");
file1>>N>>V; //È¡µ½³ÇÊÐÊýºÍͨµÀÊý
string city;
VCC vc_cities;
for(int i=0;i<N;i++)
{
file1>>city; //ÏȰѵ¥¸ö³ÇÊÐÃû´¢´æ£¬stringÊý×é
vc_cities.push_back(City(city)); // set all cities in a city container
}
string city1, city2;
for(int j=0;j<V;j++)
{
file1>>city1>>city2;
int find = 0;
// check all cities in container, wenn we find one then set him a neighborcity
if(city1 != city2)
{
for(int k = 0; k<vc_cities.size() && find<2; k++)
{
if(vc_cities.at(k).get_name() == city1)
{
find++;
vc_cities.at(k).set_neighbor(City(city2));
}
else if(vc_cities.at(k).get_name() == city2)
{
find++;
vc_cities.at(k).set_neighbor(City(city1));
}
}
}
}
file1.close(); //¹Ø±ÕÎļþ£¬C++·½Ê½
// till now, we have all cities in container, and we have also
// set the neighborcity for every city in container.
// just to check
for(int a = 0; a<vc_cities.size(); a++)
{
VCC temp = vc_cities[a].get_vcinfo();
for(int b = 0; b<temp.size(); b++)
{
cout<<temp[b].get_name()<<" ";
}
cout<<endl;
}
// code will be continued;
// cityblock will be created
// for this problem,
// depth 0 just a city V
// depth 1 we have 1 cityblock : (E,C) with startcity V
// depth 2 we have 2 cityblock : (V, M, Y, C) with startcity E
// and (V, W, E) with startcity C
// depth 3 we have 7 cityblock : (E, C) with startcity V
// (H, E) with startcity M
// (E) with startcity Y
// (V, W, E) with startcity C
// (E,C) with startcity V
// (C,T) with startcity W
// (V, M, Y, C) with startcity E
// depth 4 we have 16 cityblock : ...
// e.t.c
//
return 0;
}
// 程序还没完全完成，另外局部代码还将改动
[此贴子已经被作者于2004-11-22 11:55:54编辑过]
