二叉樹的通用C

我開始寫一個平衡樹（替罪羊，splay，aa等）的集合，並找到很多共同點。示例是下面的破壞函數。

這樣的函數和類似的函數可以用void指針定義而不會導致「解除引用void *指針錯誤」嗎？

例破壞功能

void splay_node_linked_destroy(SplayNode **this) { 
72 if(*this == NULL) { 
73  return; 
74 } 
75 SplayNode *root = (*this)->root, *previous, *next; 
76 while(root) { 
77  if(previous == root->parent) { 
78  // todo use funcs for comparisons for generic 
79  if(root->left) { 
80   next = root->left; 
81  } else if(root->right) { 
82   next = root->right; 
83  } else { 
84   next = root->parent; 
85  } 
86  } else if(previous == root->left) { 
87  if(root->right) { 
88   next = root->right; 
89  } else { 
90   next = root->parent; 
91  } 
92  } else { 
93  next = root->parent; 
94  } 
95  previous = root; 
96  if(next == root->parent) { 
97  splay_node_destroy(&root); 
98  // todo use callback here to make generic 
99  } 
100  root = next; 
101 } 
102 }

來源

2015-05-19 php--

一般來說，可悲的是，答案是否定的。至少在標準的C，如果你不使用UB ... – Mints97

這裏是一個通用的樹的例子破壞：

// GenericTree.h 

void genericTreeDestroy(void *treeNode, void (*fUserFree)(void *)); 

// GenericTree.c 
typedef struct TREE_NODE { 
    struct TREE_NODE *left; 
    struct TREE_NODE *right; 
}; 
void genericTreeDestroy(struct TREE_NODE *treeNode, void (*fUserFree)(void *)) 
{ 
    if (treeNode->left) genericTreeDestroy(treeNode->left, fUserFree); 
    if (treeNode->right) genericTreeDestroy(treeNode->right, fUserFree); 
    if (fUserFree) fUserFree(treeNode); 
    free(treeNode); 
} 

// UserStuff.c 
#include "GenericTree.h" 
typedef struct MY_TREE_NODE { 
    struct MY_TREE_NODE *left; 
    struct MY_TREE_NODE *right; 
    int some_value; 
    char *name; 
}; 
void my_freedata(struct MY_TREE_NODE *node); 

void main(void) 
{ 
    struct MY_TREE_NODE *myTree= calloc(1,sizeof(struct MY_TREE_NODE)); 
    myTree->name= malloc(strlen("Hello world")+1); 
    genericTreeDestroy(myTree, my_freedata); 
} 

void my_freedata(struct MY_TREE_NODE *node) 
{ 
    free(node->name); 
}

訣竅是所有的樹必須從左邊和右邊的成員開始。 .h文件用void *參數定義了genericTreeDestroy，而.c文件將其定義爲struct TREE_NODE *。用這種方式，用戶可以傳遞任何樹節點類型。

接下來，用戶可以定義任何樹節點類型（只要它與左邊和右邊的成員在一起）並調用通用函數來銷燬它。泛型函數可以被賦予一個函數來完成用戶定義的節點類型的清理，或者如果不需要，則爲null。

以同樣的方式你可以定義其他功能。這裏是一個搜索功能：

// .h 
void *generic_tree_search (void *tree, void *value, int (*fUserCmp)(void *value, void *node)); 

// .c 
void *generic_tree_search (struct TREE_NODE *treeNode, void *value, int (*fUserCmp)(void *value, void *node)) 
{ 
    while (treeNode) { 
     switch (fUserCmp(value,treeNode) { 
     case -1: if (treeNode->left) treeNode= treeNode->left; else return(0); break; 
     case 0: return(treeNode); 
     case +1: if (treeNode->right) treeNode= treeNode->right; else return(0); break; 
     } 
    } 
    return(0); 
}

來源

2015-05-20 16:30:35

其實這是相當可能的，而且相當容易，寫它處理「任意」 C函數對於給定的算法（通用）的數據類型。

一個訣竅是使用void指針並設計API，以便使用包裝函數將指針轉換爲其實際類型，從而受益於C允許的類型檢查和安全性。唯一困難的部分是編譯器通常不會幫助您將類型信息傳遞給您的實現，儘管一些編譯器確實支持typeof()擴展，這使得可以編寫將爲您完成工作的包裝宏。

一些例子：

這個例子出現在我建議的方式來使用typeof()：https://github.com/troydhanson/uthash/tree/master/src

這是標準模板庫啓發了一個有趣的預處理器基於宏庫：http://sglib.sourceforge.net/

這也許是C語言中泛型類型的通用算法最完整的例子之一，雖然它有點醜陋，很羅嗦，也許效率不高：http://home.gna.org/gdsl/

這個答案給出了很好的建議，雖然它使用嵌入式union而不是void指針。一個union是理想的，如果你事先知道所有可能的數據類型是什麼：
https://stackoverflow.com/a/2891570/816536

另一個有趣的方式來建立高層次的結構（如列表）進行通用數據結構是什麼可能被描述作爲裏面的技術（我也喜歡這個！）。我認爲這種內向外技術的規範實現可以在4中找到。4BSD queue(3)這裏tree(3)宏一些更可讀的解釋和例子：

這個答案描述預處理器非常依賴技術，但它要求您要麼事先知道所有對象類型是什麼，要麼強制用戶爲其特定數據類型編寫中間標題：https://stackoverflow.com/a/10430893/816536

又見這些問題的答案：

來源

2015-05-19 21:35:07

你能舉個例子嗎？ –

二叉樹的通用C

回答

相關問題