目前還不清楚如何在 C 中表達此 Haskell 類型：
data Tree = Leaf Int | Inner Tree Tree
與 Haskell 和 Rust 等語言不同，C 缺乏對
的內建支持
不相交的聯合。然而，如果我們願意做一些額外的輸入，它確實提供了代表它們所需的所有成分。
首先要認識到的是，不相交的並集包括：
在我們的二元樹範例中，我們有兩個變體：「葉子」和「內部」。葉變數儲存單一整數（其資料），內部變數儲存兩棵樹（代表其左子樹和右子樹）。
我們可以使用具有兩個字段的結構在 C 中表示這樣的動物：
使用枚舉定義不同的變體類型標籤很方便：
enum tree_type {
TREE_LEAF,
TREE_INNER,
};
儲存資料怎麼樣？這就是工會存在要解決的問題類型。
聯合只是一塊能夠儲存多種不同類型資料的記憶體。例如，這是一個可以儲存 32 位元 int 或 5 個字元數組的聯合。
union int_or_chars {
int num;
char letters[5];
};
類型為 union int_or_chars 的變數可以在任何特定時間保存 int 或 5 個字元的陣列（但不能同時儲存）：
union int_or_chars quux;
// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42
// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd
// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261
return 0;
像 union int_or_chars 這樣的聯合擁有足夠大的記憶體區塊可供使用，可以容納其最大的成員。這是顯示其工作原理的示意圖：
+ ---- + ---- + ---- + ---- + ---- + | byte | | | | | + ---- + ---- + ---- + ---- + ---- + |<-- int uses these 4 -->| |<-- array of chars uses all 5 -->|
這有助於解釋為什麼在我們在 quux 中儲存字元數組後列印 quux.num 會導致「垃圾」：它不是垃圾，而是字串「abcd」被解釋為整數。 （在我的機器上，quux.num 以十六進位列印為64636261。字元「a」的ASCII 值為0x61，「b」的值為0x62，「c」為0x63，「d」為0x64。由於我的處理器是小端字節序，所以順序顛倒了。
關於聯合的最後一點，您可能會對 sizeof 報告的大小感到驚訝：
printf("%ld\n", sizeof(union int_or_chars));
// => 8
返回二元樹
union tree_data {
int leaf;
struct inner_data inner;
};
struct inner_data {
struct tree *left;
struct tree *right;
};
指向其左子節點和右子節點的指標。間接是必要的，因為否則結構樹將沒有固定的大小。
這些部分就位後，我們就可以定義我們的樹類型了：
enum tree_type {
TREE_LEAF,
TREE_INNER,
};
struct tree;
struct inner_data {
struct tree *left;
struct tree *right;
};
union tree_data {
int leaf;
struct inner_data inner;
};
// A representation of a binary tree.
struct tree {
enum tree_type type;
union tree_data data;
};
// Construct a leaf node.
struct tree *leaf(int value) {
struct tree *t = malloc(sizeof(*t));
t->type = TREE_LEAF;
t->data.leaf = value;
return t;
}
// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
struct tree *t = malloc(sizeof(*t));
t->type = TREE_INNER;
t->data.inner.left = left;
t->data.inner.right = right;
return t;
}
void print_tree(struct tree *t) {
switch (t->type) {
case TREE_LEAF:
printf("%d", t->data.leaf);
return;
case TREE_INNER:
printf("(");
print_tree(t->data.inner.left);
printf(" ");
print_tree(t->data.inner.right);
printf(")");
return;
}
}
Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)
inner(inner(leaf(1), leaf(2)), leaf(3));
struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3)); print_tree(t); // => ((1 2) 3)
-- Check if a value is in a tree. search :: Int -> Tree -> Bool search v (Leaf w) = v == w search v (Inner l r) = search v l || search v r
// Check if a value is in a tree.
int search(int value, struct tree *t) {
switch (t->type) {
case TREE_LEAF:
return t->data.leaf == value;
case TREE_INNER:
return (
search(value, t->data.inner.left) ||
search(value, t->data.inner.right)
);
}
}
權衡
union tree_data {
int leaf;
struct inner_data inner;
};
union tree_data {
int leaf;
struct inner_data *inner;
// ^ The difference.
};
指標。因此，第一個聯合體稍大一些，為 16 字節，而我的機器上的指標版本為 8 個位元組。不幸的是，受影響的不僅僅是內部節點：葉節點使用相同的 16 位元組聯合，但僅儲存單一（4 位元組）int。感覺有點浪費。
然而，這並不是故事的全部。每次訪問內部節點的左子節點和右子節點時，我們都會為額外的間接尋址付出代價：讀取不一定便宜，特別是在指向的記憶體未快取的情況下。我懷疑這裡提出的主要方法在大多數情況下是一個更好的起點，並且嘗試削減一些字節（白色導致額外的讀取）是不值得的，直到它成為現實。
以上是C 中的不相交聯合的詳細內容。更多資訊請關注PHP中文網其他相關文章！
