Graph-Klasse
Lektion 3 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Die Klasse Graph ist um ein einzelnes Feld aufgebaut, vertices, welches die Adjazenzliste ist: eine Map von jedem Knotenschlüssel zur Liste seiner Nachbarn. Jede Operation, die wir später hinzufügen (Hinzufügen von Kanten, Auflisten von Nachbarn, Entfernen von Kanten), ist nur eine kleine Änderung an dieser Map.
Der Konstruktor startet den Graphen in seinem leeren Zustand: keine Knoten, keine Kanten. Die Map ist also nur eine leere Map. Die Methoden, die wir in den nächsten Lektionen hinzufügen, werden sie erweitern.
Aufgabe
EinfachSchreiben Sie eine Klasse Graph mit einem Konstruktor, der keine Eingabe erwartet.
Initialisieren Sie ein einzelnes Feld vertices als eine leere Map (oder das Äquivalent Ihrer Sprache für eine Key-to-List-Adjazenz-Map).
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
static int _cmp_int(const void* a, const void* b) {
int ai = *(const int*)a, bi = *(const int*)b;
return (ai > bi) - (ai < bi);
}
int main() {
Graph g;
Graph_init(&g);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "verticesEmpty") == 0) { printf("%s\n", g.vertexCount == 0 ? "true" : "false"); }
}
return 0;
}
Alle Lektionen in Graphen - Datenstrukturen-Serie #9
2Graph-Projekt
Graph-KlasseKnoten hinzufügenKante hinzufügenHat KanteNachbarn abrufenKante entfernenGröße