グラフのデータ構造をCで...面倒..
#include <stdio.h> #include <stdlib.h> #include <stdarg.h> #include <stdbool.h> struct edge { int into; int weight; }; struct node { bool visitedp; int distance; struct graph *g; //Index in graph int id; struct edge **edges; }; struct edge* mk_edge(int into, int weight) { struct edge* new_edge; if((new_edge = (struct edge*)malloc(sizeof(struct edge))) == NULL) { fprintf(stderr, "Failed to allocate edge\n"); return NULL; } new_edge->into = into; new_edge->weight = weight; return new_edge; } void showEdge(struct edge* e) { printf("(%d, %d)", e->into, e->weight); } struct node* mk_node(int id, int ecount, ...) { struct node* new_node; if((new_node = (struct node*)malloc(sizeof(struct node))) == NULL) { fprintf(stderr, "Failed to allocate new node\n"); return NULL; } new_node->id = id; if((new_node->edges = (struct edge **)malloc(sizeof(struct edge*) * (ecount + 1))) == NULL) { fprintf(stderr, "Failed to allocate edge list\n"); free(new_node); return NULL; } va_list v_args; int i; va_start(v_args, ecount); for(i = 0; i < ecount; i++) { new_node->edges[i] = va_arg(v_args, struct edge*); } //NULLを最後のマークにつかう new_node->edges[i] = NULL; va_end(v_args); return new_node; } void free_node(struct node* n) { free(n->edges); free(n); } void showNode(struct node* n) { printf("id: %d edges: [", n->id); int i; for(i = 0; n->edges[i+1] != NULL; i++) { showEdge(n->edges[i]); putchar(','); } showEdge(n->edges[i]); printf("]\n"); } struct graph { struct node **nodes; int size; }; struct graph* mk_graph(int ncount, ...) { struct graph *new_graph; if((new_graph = (struct graph*)malloc(sizeof(struct graph))) == NULL) { fprintf(stderr, "Failed to allocate new graph\n"); return NULL; } if((new_graph->nodes = (struct node**)malloc(sizeof(struct node *) * ncount)) == NULL) { fprintf(stderr, "Failed to allocate node list\n"); return NULL; } new_graph->size = ncount; va_list v_args; int i; va_start(v_args, ncount); for(i = 0; i < ncount; i++) { new_graph->nodes[i] = va_arg(v_args, struct node*); } va_end(v_args); return new_graph; } void free_graph(struct graph* g) { int i; for(i = 0; i < g->size; i++) { free_node(g->nodes[i]); } free(g); } void showGraph(struct graph *g) { int i; for(i = 0; i < g->size; i++) { showNode(g->nodes[i]); } } int main() { struct graph *g; g = mk_graph(3, mk_node(1, 2, mk_edge(2, 1), mk_edge(3, 2)), mk_node(2, 1, mk_edge(1, 3)), mk_node(3, 2, mk_edge(1, 1), mk_edge(2, 2))); showGraph(g); free_graph(g); return 0; }
ちゃんと
./a.out id: 1 edges: [(2, 1),(3, 2)] id: 2 edges: [(1, 3)] id: 3 edges: [(1, 1),(2, 2)]
となります。