Menu
Coddy logo textTech

הוספת קודקוד

שיעור 4 מתוך 14 בקורס גרפים – סדרת מבני נתונים מס' 9 של Coddy.

קודקוד הוא נקודה יחידה בגרף. הוספת קודקוד פירושה רישום המפתח שלו במיפוי vertices עם רשימת שכנים ריקה: הוא קיים, אבל עדיין אין לו חיבורים.

אם המפתח כבר נמצא במיפוי, לא עושים דבר. אנחנו לא רוצים למחוק את השכנים הקיימים של קודקוד רק מפני שמישהו קרא ל־addVertex שלו פעמיים. התנהגות אידמפוטנטית כזאת הופכת את השיטה לבטוחה לקריאה מתוך addEdge בהמשך.

בואו נכתוב את זה.

challenge icon

אתגר

קל

הוסף מתודה addVertex למחלקה Graph.

היא מקבלת מספר שלם key ו:

  • אם key לא נמצא ב־vertices, הוסף אותו עם רשימת שכנים ריקה.
  • אם key כבר נמצא ב־vertices, אל תעשה דבר.

נסו בעצמכם

#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"); }
        if (strcmp(cmd, "hasVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Graph_indexOf(&g, atoi(arg)) != -1 ? "true" : "false"); }
        if (strcmp(cmd, "addVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Graph_addVertex(&g, atoi(arg)); }
    }
    return 0;
}

כל השיעורים ביחידה גרפים – סדרת מבני נתונים מס' 9

תרגלו בעצמכם: קומפיילר C אונליין