Come trasformare il programma C in classi

Question

quindi ho lavorato su questo programma e il suo obiettivo era usare la ricorsione e una matrice di adiacenza per trovare quanti percorsi possibili una persona poteva prendere per attraversare un sistema di metropolitana senza andare oltre un traccia più di una volta. Questo è stato auto esplicativo per me, ma ora mi sono perso sul programma 2 che è quello di fare lo stesso problema dal programma 1 in C++ e utilizzando tre classi e ricorsione. Le classi dovrebbero essere SubwaySystem, Station e Track. Non so davvero come procedere sulla transizione da una semplice matrice di adiacenza in tre classi? Sembra controproducente dal momento che sembra più complicato. Ci sto lavorando da un po 'e non riesco a utilizzare tutte e tre le classi.

Quello che ho provato: il mio approccio è stato quello di creare 1 sistema di metropolitana con 12 stazioni e ogni stazione con una serie di tracce. Ad esempio, la stazione A ha una stazione alla quale può andare B. La stazione A ha una matrice di 12 tracce, ma solo una traccia è attivata. Comunque continuo ad andare agli errori da quando ho provato a inizializzare gli array nella classe Track e quindi li uso nella classe SubwaySystem. Quindi provare a utilizzare la ricorsione per ottenere tutti i percorsi possibili lo rende molto più difficile. Non so davvero come capirlo.

La matrice di adiacenza nel mio codice mappa praticamente l'intera connessione da una stazione all'altra. Le stazioni sono A - L corrispondenti a ciascuna riga/colonna. Non so come rappresentarlo in C++ senza utilizzando una matrice di adiacenza.

Il mio codice in C (programma 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

Un modo possibile sarebbe di avere il controllo del sistema di metropolitana presa su tutte le stazioni. Le stazioni avrebbero quindi tracce che sapevano l'origine (da quale stazione provenivano) e la destinazione (a quale stazione potevano andare).

La matrice di adiacenza viene spezzata, il tutto è rappresentato all'interno del sistema di metropolitana, ogni riga/colonna è rappresentata nelle stazioni e ogni 1/0 è rappresentato dalle tracce. Non ci sarebbe traccia per uno zero.

Quali percorsi prendere è stato deciso a livello di stazione, con cui sono state utilizzate le tracce/destinazioni già utilizzate. Le tracce potrebbero avere una proprietà che tiene traccia se sono state cavalcate.

Answer 2

Se stavi facendo questo in C, si potrebbe avere strutture come questa

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; 
} 

trasformando in classi che dovrebbe essere facile. Tranne che potrebbero volere che tu usi le strutture di dati stl invece di semplicemente inserire le liste come ho fatto io.

Gli algoritmi di grafici ricorsivi semplici si adattano perfettamente a queste strutture di dati.

Answer 3

L'idea della ricorsione per il conteggio è un po 'difficile da ottenere, ma vorrei provare a spiegare almeno quella parte.

Quindi sai come funziona strlen, in C, giusto? Cammini la schiera e mantieni un conteggio. Ma ecco una versione ricorsiva

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

Vedete come funziona? Non è utile quando si cammina su un array in cui è possibile utilizzare un contatore semplice, ma quando si affrontano problemi in cui vi sono più combinazioni possibili di cose da fare o più modi di andare, funziona bene. Ad esempio, se si desidera contare il numero di nodi in un albero binario, si potrebbe fare qualcosa di simile.

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

Speriamo che questo aiuti. Probabilmente Charlie Burns ha ragione nel dire che farlo con un grafico è una buona idea.

Answer 4

In generale, posso dire che in C++ in particolare e in object oriented in generale, ogni oggetto deve avere il suo ruolo univoco nel sistema. Ciascuno sta incapsulando un comportamento e una conoscenza che sono di sua esclusiva responsabilità. Quanto a te problema specifico - Senza entrare troppo in profondità nel problema, penso che l'idea sarebbe:

#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); 
} 

L'uscita di questo è

A-->B,B-->C,C-->A,A-->E,C-->E, 


C-->D, 

Burbero si puo 'giocare' con il Traverse funzione e inserire le stampe in altre posizioni, selezionare un'altra condizione di ricorsione di estremità, ecc.

Nota come è pulito clean(). Devi solo dichiarare le stazioni e le tracce e il voodoo accade. L'aggiunta di più tracce è semplice, basta descrivere il collegamento e questo è tutto, il track wad 'aggiunto' alla metropolitana.

Altre parti delle applicazioni sono anche molto pulite, poiché ogni classe sa esattamente cosa dovrebbe e niente di più.