如何寫一個foreach般的宏來訪問圖形

假設我有以下節點圖的所有節點：如何寫一個foreach般的宏來訪問圖形

typedef struct node node_t; 
struct node { 
    size_t adjacent_node_count; 
    node_t **adjacent_nodes; 
    void* data; 
};

該圖表示爲一個指向其中一個節點（即，我沒有所有節點的單個列表，但是每個節點都保證可以從這個「根」節點到達）。

現在，我需要訪問此圖中的每個節點，並將其中的每個節點的data只應用一次函數一次。我想最簡單的方法就是DFS。

讓我們添加一些的Fileds到node簡化實施

typedef struct node node_t; 
struct node { 
    size_t adjacent_node_count; 
    node_t **adjacent_nodes; 
    void* data; 
    node_t *dfs_stack_next; 
    bool dfs_visited; 
};

而且穿越本身就是

void dfs(node_t *root, void* context, void (*function)(void* context, void* data)) { 
    node_t *stack_top = root; 
    while (stack_top != NULL) { 
     node_t *current_node = stack_top; 
     stack_top = stack_top->dfs_stack_next; 
     if (!current_node->dfs_visited) { 
      current_node->dfs_visited = true; 
      for (int i = 0; i < current_node->adjacent_node_count; ++i) { 
       node_t *adjacent_node = current_node->adjacent_nodes[i]; 
       adjacent_node->dfs_stack_next = stack_top; 
       stack_top = adjacent_node; 
      } 
      function(context, current_node->data); 
     } 
    } 
}

這是failry簡單。但是寫功能和結構包裹當地情況變得痛苦快，所以我想在foreach樣宏來包裝這個：

for_each_node(n, root) { 
    // do stuff with n->data 
}

我在循環中部分入門頂級節點從堆棧

#define for_each_node(current_node, root) \ 
    for (state_t *current_node, *stack_top = root; \ 
     stack_top \ 
      ? (current_node = stack_top, stack_top = stack_top->dfs_stack_next, stack_top) \ 
      : stack_top; \ 
    ) /* ??? */

現在我被卡住了。我意識到，這是相當簡單的寫了兩個部分的宏，像

for_each_node_begin(n, root) 
    // do stuff with n->data 
for_each_node_end(n, root)

，將簡單的兩線與function通話分裂dfs，但是我發現，相當難看。

那麼，我該如何去執行for_each_node？這是否可能？它不需要是DFS，任何訂單都可以，只要data被處理一次。

來源

2014-01-06 yuri kilochek

如果你想要一些語法糖只是一個宏前綴的塊，並避免你有一個「結束」的宏，這可以通過使用「dummy」for系統完成，一旦。寫作這樣的事情有點討厭，但根據我的經驗，它使代碼使用它更容易掌握。

P99有很多幫助宏可以簡化這些宏的編程。 P99_GUARDED_BLOCK似乎適合您的使用情況。

來源

2014-01-06 13:51:22

訣竅是寫一個函數next_node。接收節點並使用dfs/bfs/whatever返回下一個節點的函數。

宏將是：

for_each_node(n, root) \ 
    for (struct node* n = root; n != NULL; n = next_node(n))

注意，一個節點必須指向其父和兒童這個工作。還假定該圖是一個DAG。帶圓圈的非定向圖需要不同的處理。

來源

2014-01-06 14:27:30 egur

如何寫一個foreach般的宏來訪問圖形

回答

相關問題