所以我一直在研究这个程序,它的目标是使用递归和邻接矩阵来找出一个人可以采取多少条可能的路线来通过地铁系统而不会超过一次轨道。这对我来说是不言自明的,但现在我在程序 2 上迷路了,它是用 C++ 解决程序 1 中的相同问题并使用三个类和递归。这些类假定为 SubwaySystem、Station 和 Track。我真的不知道如何从一个简单的邻接矩阵过渡到三个类?这似乎适得其反,因为它看起来更复杂。我已经研究了一段时间,但我似乎无法利用所有三个类(class)。
我尝试过的方法:我的方法是创建一个包含 12 个车站的地铁系统,每个车站都有一组轨道。例如,A 站有一个可以去的站,B 站。在 A 站有 12 个轨道阵列,但只有 1 个轨道被激活。但是,由于我尝试在 Track 类中初始化数组,然后在 SubwaySystem 类中使用它们,因此我一直遇到错误。然后尝试使用递归来获取所有可能的路径会使它变得更加困难。我真的不知道如何解决这个问题。
我的代码中的邻接矩阵几乎映射出了站与站之间的整个连接。车站是 A - L 对应于每一行/列。我不知道如何在 c++ 中不使用邻接矩阵来表示它。
我的 C 代码(程序 1):
#include <stdio.h>
void routesFinder(int row, int col);
char station[13] = "ABCDEFGHIJKL";
char order[25] = "A";
int subway[12][12] = {{0,1,0,0,0,0,0,0,0,0,0,0},
{1,0,1,1,1,1,0,0,0,0,0,0},
{0,1,0,0,1,0,0,0,0,0,0,0},
{0,1,0,0,1,0,0,0,0,0,0,0},
{0,1,1,1,0,0,1,1,0,0,0,0},
{0,1,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,1,0},
{0,0,0,0,1,1,0,0,1,1,1,0},
{0,0,0,0,0,0,0,1,0,0,1,0},
{0,0,0,0,0,0,0,1,0,0,1,0},
{0,0,0,0,0,0,1,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,0}};
int paths = 0, i = 1;
int main(){
routesFinder(0, 0); //start with first station row, first column
printf("\n%d days before repeating a route.\n", paths);
return 0;
}
void routesFinder(int row, int col) {
while (col < 12) { //go through columns of a row
if (subway[row][col] == 0) { // if no station is found in row
if (row == 11) { // station found
paths++;
printf("Route %d: %s.\n", paths, order);
return;
}
col++;
if (row != 11 && col == 12) { //backtracking from deadend
return;
}
}
if (subway[row][col] == 1) {
order[i] = station[col]; //add station to route
i++; //increment, prepare for next route
subway[row][col] = 0; //no track forward
subway[col][row] = 0; // or backward
routesFinder(col, 0); //recursion, look for path in new row
order[i] = '\0'; //remove route
i--; //decrement, prepare for next route
subway[row][col] = 1; //restore path
subway[col][row] = 1; // restore path
col++; //returning from deadend, check for next open path
if (row != 11 && col == 12) { //return from deadend
return;
}
}
}
}
最佳答案
总的来说,我可以告诉你,特别是在 C++ 和一般的面向对象中, 每个对象在系统中都应该有其独特的作用。每一个都封装了一种行为和一种知识,这是它自己和唯一的责任。 至于你的具体问题 - 在不深入研究问题的情况下,我认为这个想法是:
#include <iostream>
#include <string>
#include <vector>
class Track;
typedef std::vector<Track*> TrackList;
class Station
{
public:
Station( std::string name ) : _name( name ){};
~Station(){}
public:
const std::string& GetName() const
{ return _name; }
TrackList& GetTrackList()
{ return _trackList; }
void AddTrack( Track& track )
{ _trackList.push_back( &track ); }
private:
std::string _name;
TrackList _trackList;
};
class Track
{
public:
Track( Station& edgeA, Station& edgeB )
:
_edgeA( edgeA ),
_edgeB( edgeB ),
_wasVisited( false )
{
edgeA.AddTrack( *this );
edgeB.AddTrack( *this );
}
~Track(){}
public:
bool WasVisited() const
{ return _wasVisited; }
void SetVisited()
{ _wasVisited = true; }
public:
Station& GetEdgeA()
{ return _edgeA; }
Station& GetEdgeB()
{ return _edgeB; }
private:
Station& _edgeA;
Station& _edgeB;
bool _wasVisited;
};
class SubwaySystem
{
public:
SubwaySystem() {}
~SubwaySystem() {}
public:
void Traverse( Station& start )
{
TrackList& tracks = start.GetTrackList();
TrackList::iterator it = tracks.begin();
while ( it != tracks.end() )
{
if ( ! (*it)->WasVisited() )
{
std::cout << (*it)->GetEdgeA().GetName() << "-->" << (*it)->GetEdgeB().GetName() << ",";
(*it)->SetVisited();
Traverse( (*it)->GetEdgeB() );
}
++ it;
}
std::cout << std::endl;
}
};
int main()
{
Station A( "A" );
Station B( "B" );
Station C( "C" );
Station D( "D" );
Station E( "E" );
Track AB( A, B );
Track BC( B, C );
Track CA( C, A );
Track CD( C, D );
Track CE( C, E );
Track AE( A, E );
SubwaySystem subway;
subway.Traverse( A );
}
这个的输出是
A-->B,B-->C,C-->A,A-->E,C-->E,
C-->D,
Surly 您可以“玩”遍历功能并将打印品放在其他地方, 选择另一个结束递归条件等。
注意 main() 是多么干净。 您只需声明 Stations 和 Tracks,巫术就会发生。 添加更多轨道很简单,只需描述链接即可,将轨道“添加”到地铁。
应用程序的其他部分也非常干净,因为每个类都确切地知道它应该做什么,仅此而已。
关于c++ - 如何将 C 程序转换为类,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19439917/