嵌套取消引用的成本可以忽略不计吗？

Question

我有一系列对树进行运算的大型递归函数。这些树是使用“多态性”定义的，就像这样

struct foo {
    enum abctype type;
    union {
        struct a ay;
        struct b bee;
        struct c cee;
    }
};

其中 struct a... c 都是树中的节点。树中的每个节点(即 struct a...c 类型的任何对象)都指向 struct foo 的对象。例如:

struct a {
    /* definitions */
    /*...*/
    struct foo *next;
};

因此，struct 取消引用最终变得非常嵌套，即使我的函数没有超出其目的。

在这种情况下，嵌套取消引用是不可避免的。仅仅为了摆脱 -> 而编写可爱的小包装函数是荒谬的。但是，我听说很多程序员说你不应该超过 3-4 次取消引用或你的“算法需要修复”。

那么，判决是什么？我的代码需要修复吗？ 嵌套取消引用是否效率低下？

编辑:这是我的数据结构更深入的样子(它们不是树，正如我被告知的那样，除非链表 == 树):

struct a {
    /* definitions */
    /*...*/
    struct foo *longitudinal;
};

struct b {
    /* definitions */
    /*...*/
    struct foo *longitudinal;
    struct b *transverse;
};

struct c {
    /* definitions */
    /*...*/
    struct foo *longitudinal;
    struct c *transverse;
};

基本上，数据结构是这样的，因为它们处理的数据是这样组织的(在我的脑海中)。我只是看不到将其转换为二叉树的方法。

Answer 1

单个指针不能构成树；它列了一个 list 。树至少需要两个指针。 (您可以在 Wikipedia 中找到描述的异常，但您不太可能(尽管并非不可能)打算将这样的组织用于您的树结构。)

我认为您的数据组织是……好吧，如果没有错，那么它至少是次优的。您几乎肯定会使用更像这样的结构:

struct tree
{
    struct tree *left;
    struct tree *right;
    enum abctype type;
    union {
        struct a aye;
        struct b bee;
        struct c cee;
    };
};

其中每个单字母结构类型仅包含相关(变体)数据而不包含任何与树相关的指针:

struct a
{
    /* definitions */
    /* …no struct tree *next; or anything similar… */
};

树的遍历现在很好而且统一了。比较过去需要的和现在需要的。鉴于旧的 struct foo *tp，您的原始代码(可能)需要做一些可怕的事情，例如:

if (tp->type == TYPE_A)
    process_next(tp->ay.next);
else if (tp->type == TYPE_B)
    process_next(tp->bee.next);
else if (tp->type == TYPE_C)
    process_next(tp->cee.next);
else
    …report error…

(与 prev 或 left 和 right 指针类似，或者您用来创建实际树结构的任何其他内容——即使作为一个列表，这不仅仅是一点点困惑)。

使用修改后的方案，给定一个 struct tree *tp;，您现在只需使用:

process_tree(tp->left);
process_data(tp);
process_tree(tp->right);

数据处理必须处理枚举和访问匿名 union 的适当部分。这与以前非常相似(除了您不需要使用树结构指针)。

---

工作代码

我观察到，由于您没有显示结构 a、b 和 c 的数据，我不得不猜测在什么可能是适当的。如果那种细节对你很重要，那么在人们回答之前把这些信息放在问题中是很重要的。 (这在一定程度上意味着，现在不要向结构中添加数据字段——您已经错失了指定其中内容的机会。)

此代码或多或少有效。内存管理没有内存访问错误，至少测试数据是这样。数据没有被释放；那是你可以玩的练习。并非所有应该存在的错误检查都存在；那是你的另一个练习。而且测试并不是那么全面——猜猜这是什么意思？

对于您的数据结构应该如何工作，可能会有一些混淆。我将其解释为:

• 您可以拥有一个任意顺序的(纵向)项目列表，类型为 A、B 或 C。它们通过 struct foo 存储，并使用匿名 union 完成。
• B 类项目可以有更多 B 类项目的横向列表。
• C 类项目可以有更多 C 类项目的横向列表。

下面是一些有效的代码:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct a
{
    char name[20];
};

struct b
{
    double x;
    double y;
    struct b *transverse;
};

struct c
{
    int height;
    int width;
    int depth;
    struct c *transverse;
};

enum abctype { TYPE_A, TYPE_B, TYPE_C };

struct foo
{
    struct foo *longitudinal;
    enum abctype type;
    union
    {
        struct a aye;
        struct b bee;
        struct c cee;
    };
};

static struct foo *add_a_long(struct foo *head, const char *name)
{
    struct foo *new_foo = malloc(sizeof(*new_foo));
    if (new_foo != 0)
    {
        strncpy(new_foo->aye.name, name, sizeof(new_foo->aye.name)-1);
        new_foo->aye.name[sizeof(new_foo->aye.name)-1] = '\0';
        new_foo->type = TYPE_A;
        new_foo->longitudinal = head;
    }
    return new_foo;
}

static struct foo *add_b_long(struct foo *head, double x, double y)
{
    struct foo *new_foo = malloc(sizeof(*new_foo));
    if (new_foo != 0)
    {
        new_foo->bee.x = x;
        new_foo->bee.y = y;
        new_foo->bee.transverse = 0;
        new_foo->type = TYPE_B;
        new_foo->longitudinal = head;
    }
    return new_foo;
}

static struct foo *add_c_long(struct foo *head, int height, int width, int depth)
{
    struct foo *new_foo = malloc(sizeof(*new_foo));
    if (new_foo != 0)
    {
        new_foo->cee.height = height;
        new_foo->cee.width = width;
        new_foo->cee.depth = depth;
        new_foo->cee.transverse = 0;
        new_foo->type = TYPE_C;
        new_foo->longitudinal = head;
    }
    return new_foo;
}

static void add_b_trans(struct b *b, double x, double y)
{
    struct b *new_b = malloc(sizeof(*new_b));
    if (new_b != 0)
    {
        new_b->x = x;
        new_b->y = y;
        new_b->transverse = 0;
        while (b->transverse != 0)
            b = b->transverse;
        b->transverse = new_b;
    }
}

static void add_c_trans(struct c *c, int height, int width, int depth)
{
    struct c *new_c = malloc(sizeof(*new_c));
    if (new_c != 0)
    {
        new_c->height = height;
        new_c->width = width;
        new_c->depth = depth;
        new_c->transverse = 0;
        while (c->transverse != 0)
            c = c->transverse;
        c->transverse = new_c;
    }
}

static void print_foo(const char *tag, const struct foo *head)
{
    printf("\n%s:\n", tag);
    while (head != 0)
    {
        switch (head->type)
        {
        case TYPE_A:
            printf("A: %s\n", head->aye.name);
            break;
        case TYPE_B:
            {
            const struct b *bp = &head->bee;
            printf("B-main:  (%f,%f)\n", bp->x, bp->y);
            while ((bp = bp->transverse) != 0)
                printf("B-trans: (%f,%f)\n", bp->x, bp->y);
            }
            break;
        case TYPE_C:
            {
            const struct c *cp = &head->cee;
            printf("C-main:  (%d,%d,%d)\n", cp->height, cp->width, cp->depth);
            while ((cp = cp->transverse) != 0)
                printf("C-trans: (%d,%d,%d)\n", cp->height, cp->width, cp->depth);
            }
            break;
        }
        head = head->longitudinal;
    }
}

int main(void)
{
    struct foo *head = 0;
    head = add_a_long(head, "Caterpillar");
    print_foo("1 item", head);
    head = add_a_long(head, "Ununtrium");
    print_foo("2 items", head);
    head = add_b_long(head, 1.00000, 1.00000);
    head = add_b_long(head, 3.14159, 2.78128);
    print_foo("4 items", head);
    assert(head->type == TYPE_B);
    add_b_trans(&head->bee, 1.2345, 2.3456);
    add_b_trans(&head->bee, 9.8765, 6.5432);
    print_foo("4 items, 2 transverse B", head);
    head = add_a_long(head, "Ununpentium");
    head = add_c_long(head, 3, 4, 5);
    head = add_c_long(head, 5, 12, 13);
    print_foo("6 items", head);
    assert(head->type == TYPE_C);
    add_c_trans(&head->cee, 7, 20, 27);
    add_c_trans(&head->cee, 9, 35, 36);
    head = add_a_long(head, "Ununseptium");
    head = add_a_long(head, "Ununoctium");
    print_foo("Final", head);
    return 0;
}

这是我得到的示例输出:

1 item:
A: Caterpillar

2 items:
A: Ununtrium
A: Caterpillar

4 items:
B-main:  (3.141590,2.781280)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar

4 items, 2 transverse B:
B-main:  (3.141590,2.781280)
B-trans: (1.234500,2.345600)
B-trans: (9.876500,6.543200)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar

6 items:
C-main:  (5,12,13)
C-main:  (3,4,5)
A: Ununpentium
B-main:  (3.141590,2.781280)
B-trans: (1.234500,2.345600)
B-trans: (9.876500,6.543200)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar

Final:
A: Ununoctium
A: Ununseptium
C-main:  (5,12,13)
C-trans: (7,20,27)
C-trans: (9,35,36)
C-main:  (3,4,5)
A: Ununpentium
B-main:  (3.141590,2.781280)
B-trans: (1.234500,2.345600)
B-trans: (9.876500,6.543200)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar