如何將C程序轉換爲類

Question

所以我一直在研究這個程序，它的目標是使用遞歸和鄰接矩陣來查找一個人可以通過一個地鐵系統而不需要經過多少條可能的路線跟蹤不止一次。對我來說，這是自我解釋，但現在我迷失在程序2上，它是從C++程序1中做同樣的問題，並使用三個類和遞歸。這些課程假定爲SubwaySystem，Station和Track。我真的不知道如何去從簡單的鄰接矩陣轉換到三個類？這似乎適得其反，因爲它似乎更復雜。我一直在研究它，並且似乎無法利用所有三個類。

我嘗試過的方法是：我的方法是我創建了1個帶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; 
      } 
     } 
    } 
} 

Answer 1

一種可能的方式將有超過所有站的地鐵系統保持控制。然後這些電臺將具有知道來源（他們來自哪個電臺）和目的地（他們可以去哪個電臺）的軌道。

鄰接矩陣將被分解，整個事物在地鐵系統內被表示，每個行/列在車站中被表示，並且每個1/0被軌道表示。沒有零的軌跡。

在車站層面將決定採取哪條路徑，哪些路段已被使用/目的地已經去過。軌道可能有一個財產，如果他們已經騎上了軌道。

Answer 2

如果您在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數據結構，而不是像我一樣簡單地內聯列表。

簡單的遞歸圖算法很好地映射到這些數據結構。

Answer 3

遞歸計數的想法有點難以得到，但讓我試着解釋至少那部分。

所以你知道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); 
} 

希望有幫助。查理伯恩斯可能是正確的，用圖表做一個好主意。

Answer 4

一般來說，我可以告訴你，在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, 

切切實實的，你可以「玩」與導線功能並將打印放置在其他地方， 選擇另一個末端遞歸條件等。

注意main（）方法是乾淨的。 你只是宣佈站和軌道和巫術發生。 添加更多曲目很簡單，只需描述鏈接即可，這是軌道「添加」到地鐵的功能。

應用程序的其他部分也很乾淨，因爲每個類都知道它應該是什麼，而不是更多。