Thêm đỉnh
Bài học 4 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Đỉnh là một điểm đơn lẻ trong đồ thị. Thêm một đỉnh nghĩa là đăng ký khóa của nó trong bản đồ vertices với danh sách láng giềng rỗng: đỉnh đó tồn tại nhưng chưa có kết nối nào.
Nếu khóa đã có trong bản đồ, đừng làm gì cả. Ta không muốn xóa các đỉnh láng giềng hiện có chỉ vì ai đó gọi addVertex hai lần. Hành vi lũy đẳng như vậy giúp gọi phương thức này an toàn từ addEdge sau này.
Hãy viết hàm này.
Thử thách
DễThêm phương thức addVertex vào lớp Graph.
Phương thức này nhận một số nguyên key và:
- Nếu
keykhông có trongvertices, hãy thêm nó với danh sách láng giềng rỗng. - Nếu
keyđã có trongvertices, không làm gì cả.
Tự làm thử
#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;
}
Tất cả bài học trong Đồ thị, chuỗi cấu trúc dữ liệu #9
Tự luyện tập: Trình biên dịch C online