إضافة رأس (Vertex)
الدرس 4 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
الرأس (vertex) هو نقطة واحدة في الرسم البياني. إضافة رأس تعني تسجيل مفتاحه في الخريطة vertices مع قائمة جيران فارغة: إنه موجود، لكن ليس لديه اتصالات بعد.
إذا كان المفتاح موجوداً بالفعل في الخريطة، فلا تفعل شيئاً. لا نريد مسح الجيران الحاليين للرأس لمجرد أن شخصاً ما استدعى addVertex عليه مرتين. هذا النوع من السلوك الجمودي (idempotent) يجعل الطريقة آمنة للاستدعاء من 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
2مشروع الـ Graph
فئة الـ Graphإضافة رأس (Vertex)إضافة حافة (Edge)هل توجد حافةالحصول على الجيرانحذف حافةالحجم