הוספת קודקוד
שיעור 4 מתוך 14 בקורס גרפים – סדרת מבני נתונים מס' 9 של Coddy.
קודקוד הוא נקודה יחידה בגרף. הוספת קודקוד פירושה רישום המפתח שלו במיפוי vertices עם רשימת שכנים ריקה: הוא קיים, אבל עדיין אין לו חיבורים.
אם המפתח כבר נמצא במיפוי, לא עושים דבר. אנחנו לא רוצים למחוק את השכנים הקיימים של קודקוד רק מפני שמישהו קרא ל־addVertex שלו פעמיים. התנהגות אידמפוטנטית כזאת הופכת את השיטה לבטוחה לקריאה מתוך addEdge בהמשך.
בואו נכתוב את זה.
אתגר
קלהוסף מתודה 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 אונליין