5

所以我一直在研究这个程序，它的目标是使用递归和邻接矩阵来找出一个人可以通过多少条可能的路线来通过地铁系统而无需多次穿越轨道。这对我来说是不言自明的，但现在我迷失在程序 2 上，这是用 C++ 和程序 1 做同样的问题，并使用三个类和递归。假设这些类是 SubwaySystem、Station 和 Track。我真的不知道如何从简单的邻接矩阵过渡到三个类？这似乎适得其反，因为它似乎更复杂。我已经研究了一段时间了，但我似乎无法利用所有三个课程。

我尝试过的方法是：我创建了一个包含 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;
            }
         }
     }
}
4

4 回答 4

2

总的来说，我可以告诉你，特别是在 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 您可以“玩” Traverse 功能并将打印件放在其他地方，选择另一个结束递归条件等。

注意 main() 是多么干净。您只需声明车站和轨道，巫毒就会发生。添加更多轨道很简单，只需描述链接即可，轨道就“添加”到了地铁中。

应用程序的其他部分也非常干净，因为每个类都知道它应该做什么，仅此而已。

于 2013-10-27T21:36:36.020 回答
0

一种可能的方法是让地铁系统控制所有车站。然后，这些车站将拥有知道起点（他们来自哪个车站）和目的地（他们可以去哪个车站）的轨道。

邻接矩阵将被分解，整个事物在地铁系统内部表示，每一行/列在车站中表示，每个 1/0 由轨道表示。没有零的踪迹。

采取哪些路径将在车站级别决定，哪些轨道正在使用/目的地已经到达。轨道可能有一个属性，如果它们被骑过，可以跟踪它们。

于 2013-10-18T01:14:44.247 回答
0

如果您在 C 中执行此操作，您可能会有这样的结构

typedef struct node node; 
typedef struct edge edge;
typedef struct graph graph;

struct graph { // subway system
    node *nodes; // stations
};
struct node { // station 
    char *name;
    edge *edges; // tracks connected to this station
    node *next; // next node in graph
    bool visited;
}
struct edge { // track
   node *src;  // from station
   node *dst;  // to station
   edge *next; // next track, this station
   bool visited; 
}

将其转换为类应该很容易。除了他们可能希望您使用 stl 数据结构，而不是像我那样简单地内联列表。

简单的递归图算法很好地映射到这些数据结构。

于 2013-10-18T01:31:36.840 回答
0

计数递归的想法有点难以理解，但让我尝试至少解释一下这部分。

所以你知道 strlen 在 C 中是如何工作的，对吧？你走阵列并保持计数。但这是一个递归版本

unsigned int strlen(const char * string) {
  if (*string == '\0') { return 0; }
  else return 1 + strlen(string + 1);
}

你明白它是如何工作的吗？在遍历可以使用简单计数器的数组时并不是那么有用，但是当您处理存在多种可能的做事组合或多种方式的问题时，它可以很好地工作。例如，如果您想计算二叉树中的节点数，您可能会执行类似的操作。

unsigned int treecount(NODE * node) {
    if (node == NULL) { return 0;}
    else return 1 + treecount(node->left) + treecount(node->right);
}

希望这会有所帮助。查理伯恩斯可能是对的，用图表来做是个好主意。

于 2013-10-18T01:34:19.890 回答