不用树，用图，你想想，如果是树，那么当有几个城市连成一个循环路线时，树就无限延伸下去了，所以用图，你数据结构不好，没所谓，我学得也不好，其实就是用矩阵表示图，当城市间连通，该元素就赋1值。

kai的思路很好，但是你想思路，有时有些实现方面的问题也难，代码的实现是一个难题，由于本题必定用到递归(否则循环very复杂)，所以很难控制变量间操作，尤其是我用动态申请数组。

我也想了思路，卡在代码实现上，我不知道怎么递归下去。。。

[此贴子已经被作者于2004-12-02 02:13:33编辑过]

呵呵……写得很好，也很乱，看到最后一句我郁闷。在C中的poppush函数，在C++中的STL中有vector向量解决，比较方便，不用自己处理。

不过麻烦，你写的字符串比较太深了，不如用化成数字表示的办法还方便一点(你看了我的代码没有？)，动态申请内存用惯了new不好意思，感觉记忆起来方便……

if(!(strcmp(temp,route[i].to))&&route[i].flag==1) //这句想看懂要看很久~~~

还好，注释写的中文，kai大哥的英文看得我辛苦，我4级都还没过啊，郁闷~~~

[此贴子已经被作者于2004-12-02 02:15:57编辑过]

live41,

告诉你一个好消息，程序写完了。基本验证真确。这个程序是从周六开始写的。周六已经完成，本想让你高兴高兴的。可是一调试，有逻辑错误，修补错误可比从头开始写还难。星期天也在修改代码。今天下午回到家，一直忙，忙到现在，总算对了。惭愧惭愧，让你等了这么久。

下面是这个程序的原代码。

程序采用分开编译的方式。

一个头文件，六个cpp 文件。

// headfile travel.h

#include <iostream> #include <vector> #include <string> #include <cstdlib> using namespace std;

class City; class Cityblock; class Road; typedef vector<string> VCSTR; typedef vector<City> VCC; typedef vector<Cityblock *> VCPCB; typedef vector<Road *> VCPR;

class FileForThisProblem { private: bool state; string filename; VCC vccAllcities; static string urstartcity; static string turnning; public: FileForThisProblem(const char * fn); bool isAllright(); VCC get_allcities_info(); void display(); friend class City; friend class Cityblock; };

class City { private: enum{UrStartCity, TurnningCity, NormalCity, // status for a city LastOneWithARoad, LastOneWithoutARoad}; string name; // every city has his name. City * start; // point to his startcity. int depth; // his level int status; // to indicate, in which status he is. VCSTR vcStrNeighborCity; // a container to keep the names of the neighborcity VCSTR vcStrAllStartCityAbove; // a container to keep the names of all startcities above in the chain. VCC vccVisitcities; // a container to keep all his childrenCities VCSTR get_allStartCityAbove(); int find_city_in_citylist(VCSTR & vcStrCityList, const string & turnningCity, const string & a_city); public: City(){} // default constructor City(const City & a_city); // copy constructor City(const string & cityname); // initialize the object with the name int get_depth(); // in this City_Tree, every city will be located in position(in a level) string get_name(); // we want know, what is his name. VCSTR get_Neighborinfo(); //for every city there are some neighborcity belong to him. City * get_startCity(); // we want know, what is his startcity. int get_status(); // tell us a city's status VCC get_visitcities_info(); // to report all visitcities bool is_theLastOneWithARoad(); // the city should tell us, whether he is the last one in a road. bool is_theLastOneWithoutARoad(); // the city should tell us, whether he is the last one without a road. bool is_TurnningCity(); // the city should also tell us, whether he is a turnningcity bool is_UrStartCity(); // the city should tell us, whether he is a Urstartcity void set_as_startcity(); // in this program, we have a Urstartcity void set_as_turnningcity(); // and a turnningcity, void set_depth(); // to decide which level belong to him, we ask first, if you are the urstartcity, // when yes, your depth is 0, otherwise, your depth is a step more than your startcity. void set_neighbor(const string & a_city); // add the name of neighborcity in the neighborcity vector void set_startcity(City * startcity); void set_status(const int some_status); void set_visitcity(FileForThisProblem & fftp); // this method is very import, every city has his neighborcity, // but it doesn't mean, all his neighborcity would be his visitcity. // only the city, who has not appear in the road, or the urstartcity. // because the urstartcity can be at begin, can also be at the end. friend class Cityblock; // in a cityblock will save all the cities, that belong to a same level. friend class CityTree; friend class Road; };

class Cityblock { private: int depth; bool extendable; Cityblock * cityblock_above; VCC allcities_in_this_block; void set_depth(Cityblock * above); void add_all_cities_from_last_Block(Cityblock * above); void work_with_all_cities_in_this_block(FileForThisProblem & fftp); void set_status_of_extendable(); public: Cityblock(Cityblock * above, FileForThisProblem & fftp); int get_depth(); VCC get_allcities_info(); void add_city_in_this_block(const City & city); bool is_extendable(); friend class CityTree; };

class CityTree { private: VCPCB all_cityblocks; VCPR all_roads; void get_all_roads(); public: CityTree(); void build_CityTree(FileForThisProblem & fftp); bool there_is_a_road(City & a_city); void create_this_road(City & a_city); void get_langest_road_and_display(); ~CityTree(); friend class Road; };

class Road { private: int nCityAmount; VCSTR cities_for_a_road; public: Road(); void create_a_road(City & a_city); int get_cityAmount(); void display(); };

// city.cpp

#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <algorithm> using namespace std;

#include "travel.h"

City::City(const string & cityname) { name = cityname; }

City::City(const City & a_city) { this->depth = a_city.depth; this->name = a_city.name; this->start = a_city.start; this->status = a_city.status; this->vcStrAllStartCityAbove = a_city.vcStrAllStartCityAbove; this->vcStrNeighborCity = a_city.vcStrNeighborCity; this->vccVisitcities = a_city.vccVisitcities; }

int City::find_city_in_citylist(VCSTR & vcStrCityList, const string & turnningCity, const string & a_city) { vector <string>::iterator iter_begin = NULL, iter_end = NULL, iter_result = NULL; iter_begin = vcStrCityList.begin(); iter_end = vcStrCityList.end();

// to find the turnningcity in the list iter_result = find(iter_begin, iter_end, turnningCity); // if iterator point to the end of the container, then // it mean, we have not found the turnning city in the list // otherwise, we found it. bool withTurnningCity = (iter_result == iter_end)? false:true;

// to find this city in the citynamelist iter_result = find(iter_begin, iter_end, a_city); // if iterator point to the end of the container, then // it mean, we have not found this city in the list // otherwise, we found it. bool found = (iter_result == iter_end)? false:true;

if(!found) return NormalCity; // it is our positive answer, because the city is not in the cityList else { // when the city is the last element in the container, then it mean, // this city has the same name like as our urstartcity. // it is also ok, but we must find also turnningcity in the citylist // then this city is the end of a road. // otherwise, it is not ok. if((a_city == FileForThisProblem::urstartcity) && (iter_result == iter_end - 1) && withTurnningCity) return LastOneWithARoad; // it is ok, and we find a road else return LastOneWithoutARoad; // it is not the visit city. } }

VCSTR City::get_allStartCityAbove() { City * temp_start = this->start; while(temp_start != NULL) //this mean, this city should not be urstartcity { vcStrAllStartCityAbove.push_back(temp_start->get_name()); temp_start = temp_start->get_startCity(); } return vcStrAllStartCityAbove; }

int City::get_depth() { return this->depth; }

string City::get_name() { return name; }

VCSTR City::get_Neighborinfo() { return vcStrNeighborCity; }

City * City::get_startCity() { return start; }

int City::get_status() { return status; }

VCC City::get_visitcities_info() { return vccVisitcities; }

bool City::is_theLastOneWithARoad() { return status == LastOneWithARoad; }

bool City::is_theLastOneWithoutARoad() { return status == LastOneWithoutARoad; }

bool City::is_TurnningCity() { return status == TurnningCity; }

bool City::is_UrStartCity() { return status == UrStartCity; }

void City::set_as_startcity() { status = UrStartCity; }

void City::set_as_turnningcity() { status = TurnningCity; }

void City::set_depth() { if(status == UrStartCity) depth = 0; else { depth = start->get_depth() + 1; } }

void City::set_neighbor(const string & a_city) { vcStrNeighborCity.push_back(a_city); }

void City::set_startcity(City * startcity) { this->start = startcity; }

void City::set_status(const int some_status) { status = some_status; }

void City::set_visitcity(FileForThisProblem & fftp) { int state = get_status(); if(status != LastOneWithoutARoad && status != LastOneWithARoad) { // first we want know all his startcities above. this->get_allStartCityAbove(); // now we check their name. int size1 = vcStrNeighborCity.size(); for(int i = 0; i<size1; i++) { string city_name = vcStrNeighborCity.at(i); state = find_city_in_citylist(vcStrAllStartCityAbove, FileForThisProblem::turnning, city_name); int size2 = fftp.vccAllcities.size(); for(int j = 0; j<size2; j++) { if(city_name == fftp.vccAllcities.at(j).get_name()) { this->vccVisitcities.push_back(City(fftp.vccAllcities.at(j))); vector <City>::iterator iter_City = vccVisitcities.end() - 1; iter_City->set_startcity(this); iter_City->set_status(state); iter_City->set_depth(); break; } } } } }

// continued

// cityblock.cpp

#include <iostream> #include <string> #include <vector> #include <cstdlib> using namespace std;

#include "travel.h"

void Cityblock::add_all_cities_from_last_Block(Cityblock * above) { if(above->is_extendable()) { for(int i = 0; i<above->get_allcities_info().size(); i++) { City temp = above->get_allcities_info().at(i); for(int j = 0; j<temp.get_visitcities_info().size(); j++) { this->add_city_in_this_block(temp.get_visitcities_info().at(j)); } } } } void Cityblock::add_city_in_this_block(const City & city) { this->allcities_in_this_block.push_back(city); }

Cityblock::Cityblock(Cityblock * above, FileForThisProblem & fftp) { cityblock_above = above; if(cityblock_above == NULL) { depth = 0; // take the first element from the container of fftp // and save it in the first Cityblock // parameter: UrstartCity this->add_city_in_this_block(City(fftp.get_allcities_info().at(0))); // working with this element City * pC = &(allcities_in_this_block.at(0)); pC->set_startcity(NULL); pC->set_status(City::UrStartCity); pC->set_depth(); pC->set_visitcity(fftp); this->set_status_of_extendable(); } else // otherwise, this block is not the first block { // first we check, whether the block is extendable, // when yes, we work continue if(above->is_extendable()) { // first set depth for this block this->set_depth(above); // add all cities in this block, // here all cities mean, they are the visit cities // for individual cities in Cityblock above this->add_all_cities_from_last_Block(above); // now work with all these cities in block // so that their information of individual City // will be full, and can be continuously worked in // next block this->work_with_all_cities_in_this_block(fftp); this->set_status_of_extendable(); } } }

int Cityblock::get_depth() { return depth; }

bool Cityblock::is_extendable() { return extendable; }

void Cityblock::set_depth(Cityblock * above) { if(above == NULL) depth = 0; else depth = above->get_depth() + 1; }

void Cityblock::set_status_of_extendable() { for(int i = 0; i<allcities_in_this_block.size(); i++) { City * pC = &(allcities_in_this_block.at(i)); int state = pC->get_status(); if(state != City::LastOneWithARoad && state != City::LastOneWithoutARoad) { this->extendable = true; break; } else { this->extendable = false; continue; } } }

void Cityblock::work_with_all_cities_in_this_block(FileForThisProblem & fftp) { for(int i = 0; i<this->allcities_in_this_block.size(); i++) { City * pC = &(this->allcities_in_this_block.at(i)); // this city should know, who are his neighborcity // and he must also know, who will be his visitcity in the future // but how? With helping from the file, he can know, who his neighbor are // and with comparing with the all startcity from him above, he can also // know, who his visitcity in the future will be. pC->set_visitcity(fftp); } }

VCC Cityblock::get_allcities_info() { return allcities_in_this_block; }

// citytree.cpp

#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <algorithm> using namespace std;

#include "travel.h"

CityTree::CityTree(){}

void CityTree::build_CityTree(FileForThisProblem & fftp) { if(fftp.isAllright()) { // creat first cityblock, just save our urstartcity // this block has no startblock, Cityblock * pCb = new Cityblock(NULL, fftp); // add Cb in all_cityblocks all_cityblocks.push_back(pCb);

// check out whether the block above is extendable // when yes, continue, when no break our work while(pCb->is_extendable()) { // establish next block pCb = new Cityblock(pCb, fftp); all_cityblocks.push_back(pCb); } } }

CityTree::~CityTree() { for(int i = 0; i<all_cityblocks.size(); i++) { delete all_cityblocks.at(i); } for(int j = 0; j<all_roads.size(); j++) { delete all_roads.at(j); } }

void CityTree::create_this_road(City & a_city) { Road * pR = new Road(); pR->create_a_road(a_city); all_roads.push_back(pR); }

void CityTree::get_all_roads() { vector<Cityblock *>::iterator iter = all_cityblocks.end() - 1; for(; iter>=all_cityblocks.begin(); iter--) { for(int i = 0; i<(*iter)->get_allcities_info().size(); i++) { if((*iter)->get_allcities_info().at(i).get_status() == City::LastOneWithARoad) { this->create_this_road((*iter)->get_allcities_info().at(i)); } } } }

void CityTree::get_langest_road_and_display() { // first we get all roads this->get_all_roads(); // we find out our langest road, it can be two or more // when they have same city amount in a road. Road * pR = all_roads.at(0); int max = pR->get_cityAmount(); VCPR vcprMax; //vcprMax.push_back(pR); for(int i = 0; i<all_roads.size(); i++) { pR = all_roads.at(i); if(pR->get_cityAmount()>max) { max = pR->get_cityAmount(); vcprMax.clear(); vcprMax.push_back(pR); } else if(pR->get_cityAmount() == max) { vcprMax.push_back(pR); } } for(int j = 0; j<vcprMax.size(); j++) { vcprMax.at(j)->display(); } }

bool CityTree::there_is_a_road(City & a_city) { return (a_city.get_status() == City::LastOneWithARoad); }

// fileforthisproblem.cpp

#include <iostream> #include <fstream> #include <string> #include <vector> #include <cstdlib> #include <algorithm> using namespace std;

#include "travel.h"

string FileForThisProblem::turnning = " "; string FileForThisProblem::urstartcity = " "; VCC FileForThisProblem::get_allcities_info();

FileForThisProblem::FileForThisProblem(const char * fn) { filename = fn; fstream file1; file1.open(fn); int N, V; file1>>N>>V; //È¡µ½³ÇÊÐÊýºÍͨµÀÊý string city;

for(int i=0;i<N;i++) { file1>>city; //ÏȰѵ¥¸ö³ÇÊÐÃû´¢´æ£¬stringÊý×é vccAllcities.push_back(City(city)); // set all cities in a city's container } urstartcity = vccAllcities.at(0).get_name(); turnning = vccAllcities.at(N-1).get_name();

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<vccAllcities.size() && find<2; k++) { if(vccAllcities.at(k).get_name() == city1) { find++; this->vccAllcities.at(k).set_neighbor(city2); } else if(vccAllcities.at(k).get_name() == city2) { find++; this->vccAllcities.at(k).set_neighbor(city1); } } } } file1.close(); //¹Ø±ÕÎļþ£¬C++·½Ê½ // till now, we have all cities in container, and we have also // set the neighborcity for every city in container. state = true; }

VCC FileForThisProblem::get_allcities_info() { return vccAllcities; }

bool FileForThisProblem::isAllright() { return state; }

void FileForThisProblem::display() { vector<City>::iterator iter; vector<string>::iterator iter_str; cout<<"The file name is: "<<filename<<endl; for(iter = vccAllcities.begin(); iter<vccAllcities.end(); iter++) { cout<<iter->get_name()<<" has neighborcities: "<<endl; VCSTR vcstrNB = iter->get_Neighborinfo(); for(iter_str = vcstrNB.begin(); iter_str<vcstrNB.end(); iter_str++) { cout<<*iter_str<<" "; } cout<<endl; } cout<<"Our urstartcity is: "<<urstartcity<<endl; cout<<"Our turnningcity is: "<<turnning<<endl; City temp; temp = City(*(vccAllcities.begin()+2)); cout<<temp.get_depth()<<endl; cout<<temp.get_name()<<endl; for(int i = 0; i<temp.get_Neighborinfo().size(); i++) { cout<<temp.get_Neighborinfo().at(i); }

City * pcity = temp.get_startCity(); if(pcity) cout<<pcity->get_name()<<endl; cout<<temp.get_status()<<endl; }

// road.cpp

#include <iostream> #include <string> #include <vector> #include <cstdlib> using namespace std;

#include "travel.h"

Road::Road() { nCityAmount = 0; }

void Road::create_a_road(City & a_city) { City temp; City * pC = &a_city; while(pC) { cities_for_a_road.push_back(pC->get_name()); nCityAmount++; pC = pC->get_startCity(); } }

void Road::display() { cout<<"A road: \n"; for(int i = this->cities_for_a_road.size() - 1; i>=0; i--) { string cityname = cities_for_a_road.at(i); if(i) cout<<cityname<<"->"; else cout<<cityname<<endl; }

}

int Road::get_cityAmount() { return nCityAmount; }

// travel.cpp

#include <iostream> #include <fstream> #include <string> #include <vector> #include <cstdlib> #include <algorithm> using namespace std;

#include "travel.h"

int main() { // work with the file // FileForThisProblem myfile("001.txt"); FileForThisProblem myfile("travel.txt"); // establish our city tree // meanwhile we get our road, when there is a road // and we save our road in road container CityTree myCityTree; myCityTree.build_CityTree(myfile); myCityTree.get_langest_road_and_display();

// show the result,

return 0; }

// 程序运行完毕，输出最长的路径。如果两条或多条路径具有等同的城市数，将一并输出。

// viel Spass

下载此题的源代码请点击：

哈哈，强得令我流汗啊！！！！！

原来就我们班的题难，其他班的题和我们不同的。

强得令我也流汗……