Wie man C Programm in Klassen

Question

umwandelt, also habe ich an diesem Programm gearbeitet und sein Ziel war Rekursion und eine Adjazenzmatrix zu verwenden, um zu finden, wie viele mögliche Wege eine Person nehmen könnte, um durch ein U-Bahn-System zu kommen, ohne ein zu gehen track mehr als einmal. Das war für mich selbsterklärend, aber jetzt bin ich auf Programm 2 verloren, das das gleiche Problem von Programm 1 in C++ und drei Klassen und Rekursion zu tun hat. Die Klassen sollen SubwaySystem, Station und Track sein. Ich weiß nicht wirklich, wie ich von einer einfachen Adjazenzmatrix in drei Klassen übergehen soll. Es scheint kontraproduktiv, da es komplizierter erscheint. Ich arbeite seit einiger Zeit daran und weiß, dass ich nicht alle drei Klassen nutzen kann.

Was ich versucht habe: Mein Ansatz war ich 1 Subway System mit 12 Stationen und jede Station mit einer Reihe von Tracks erstellt. Zum Beispiel hat Station A eine Station, zu der B gehen kann. In Station A gibt es eine Anordnung von 12 Spuren, aber nur eine Spur ist aktiviert. Ich laufe jedoch immer wieder auf Fehler, seit ich versucht habe, die Arrays in der Track-Klasse zu initialisieren und sie dann in der SubwaySystem-Klasse zu verwenden. Der Versuch, die Rekursion zu verwenden, um alle möglichen Routen zu erhalten, macht es viel schwieriger. Ich weiß wirklich nicht, wie ich das herausfinden soll.

Die Adjazenzmatrix im my-Code bildet ziemlich genau die gesamte Verbindung von Station zu Station ab. Die Stationen sind A - L, die jeder Reihe/Spalte entsprechen. Ich weiß nicht, wie ich dies in C++ ohne unter Verwendung einer Adjazenzmatrix darstellen soll.

Mein Code in C (Programm 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

Eine Möglichkeit wäre die U-Bahn-System halten, die Kontrolle über alle Stationen haben. Die Stationen würden dann Spuren haben, die den Ursprung (aus welcher Station sie kamen) und das Ziel (welche Station sie erreichen konnten) kannten.

Die Adjazenz-Matrix wäre aufgebrochen, das Ganze ist innerhalb der U-Bahn dargestellt, jede Zeile/Spalte ist in den Stationen vertreten, und jede 1/0 wird durch die Spuren repräsentiert. Es gäbe keine Spur für eine Null.

Welche Wege man einschlagen würde, wäre auf Stationsebene entschieden, mit der bereits genutzte/Zielorte befahren wurden. Die Spuren könnten eine Eigenschaft haben, die verfolgt, ob sie auf geritten wurden.

Answer 2

Wenn Sie in C tun dies waren, könnten Sie Strukturen haben wie diese einfach sein sollte

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

dass in Klassen zu verwandeln. Abgesehen davon, dass sie vielleicht wollen, dass Sie stl-Datenstrukturen verwenden, anstatt einfach die Listen zu inlinern, wie ich es getan habe.

Die einfachen rekursiven Graphalgorithmen bilden diese Datenstrukturen gut ab.

Answer 3

Die Idee der Rekursion zum Zählen ist ein bisschen schwer zu bekommen, aber lassen Sie mich versuchen, zumindest diesen Teil zu erklären.

Sie wissen also, wie strlen funktioniert, in C, oder? Sie gehen das Array und zählen Sie. Aber hier ist eine rekursive Version

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

Siehst du, wie das funktioniert? Nicht so nützlich beim Gehen in einem Array, wo Sie einen einfachen Zähler verwenden können, aber wenn Sie sich mit Problemen beschäftigen, bei denen es mehrere mögliche Kombinationen von Dingen gibt, oder mehrere Arten zu gehen, funktioniert es gut. Wenn Sie z. B. die Anzahl der Knoten in einem Binärbaum zählen möchten, können Sie etwas tun.

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

Hoffentlich hilft das. Charlie Burns hat wahrscheinlich Recht, dass es eine gute Idee ist, es mit einem Graphen zu machen.

Answer 4

Im Allgemeinen kann ich Ihnen sagen, dass in C++ insbesondere und in objektorientierten im Allgemeinen jedes Objekt seine einzigartige Rolle im System haben sollte. Jede beinhaltet ein Verhalten und ein Wissen, die ihre eigene und alleinige Verantwortung sind. Was Sie spezifisches Problem - ohne zu tief in das Problem zu bekommen, ich denke, die Idee wäre:

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

Der Ausgang dieses Sie

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


C-->D, 

ist Unwirscher kann ‚Spiel‘ mit der Traverse Funktion und legen Sie die Drucke an anderen Orten, wählen Sie eine andere Ende-Rekursion Bedingung usw.

Beachten Sie, wie sauber main() ist. Sie deklarieren einfach die Stationen und die Spuren und der Voodoo passiert. Hinzufügen von mehr Tracks ist einfach, beschreiben Sie einfach den Link und das ist alles, der Track wad "hinzugefügt" in der U-Bahn.

Andere Teile der Anwendungen sind auch sehr sauber, wie jede Klasse genau weiß, was es sollte und nichts mehr.