c - 如何漂亮地打印嵌套链表

Question

有一个这样的结构:

struct a{
  char name[10];
  struct a* child;
  struct a* friend;
};

有很多具有这种结构的对象，它们作为 child 和 friend 联系在一起

如果我知道第一个地址，我就可以访问所有这些

第一个对象是这样的:

struct a start;

我将在这些对象生成后立即设置它们中的所有值

所以如果他们没有 child 或 friend ，他们的 child 和 friend 的成员变量将为零

我想打印所有这些对象，如下所示:

a
└ aa
  └ aaa
  │  └ aaaa
  ab
  ac
  └ aca
    acb
    acc

对于这张糟糕的图画我真的很抱歉

所以a是start和aa的名称 是 start 的 child 名字，ab、ac 是 aa 的 friend 。像这样的东西。

我知道如何打印那些特殊字符

问题在于对象是在运行时确定的

所以我需要一个算法来像这样打印 像这样:

void print(struct a* b)
{
    if(b)
    {
        printf(”%s\n”, b->name);
        print(b->child);
        print(b->friend);
    }
}

但是离我想要的还很远

我真的不知道该怎么做

这可能吗？ 如果没有，我想获得一些关于如何漂亮地打印这种结构的帮助

Answer 1

通常，这种类型的树打印非常简单:添加一个深度字段并打印空格以缩进子级以匹配其嵌套级别。

添加 └ 字符也可以使用 bool 标志来告诉节点它是否是子节点，如果是，则在打印自身之前放置一个角度字符。

但是，子栏 | 的添加给工作带来了一些麻烦。现在，我们需要保留每个父节点的状态，以确定它是否有尚未打印的子节点。为此，我们可以创建一个标志数组，并根据一定深度的子项的存在情况来打开或关闭它们。它应该是一个可扩展的数组，因为我们无法确定该结构有多深。

这是一些示例代码:

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

typedef struct node {
    char name[10];
    struct node* child;
    struct node* friend;
} node;

void print(node *root, int depth, bool *notch_locs, 
          size_t notch_locs_capacity, bool friend) {
    if (root) {
        for (int i = 0; i < depth * 2; i++) {
            if (friend && depth * 2 - 2 == i) {
                printf("└");
            }
            else if (i % 2 == 0 && notch_locs[i/2]) {
                printf("│");
            }
            else {
                printf(" ");
            }
        }

        if (depth >= notch_locs_capacity) {
            notch_locs_capacity *= 2;
            size_t size = sizeof(bool) * notch_locs_capacity;
            notch_locs = realloc(notch_locs, size);
        }

        notch_locs[depth] = root->child ? true : false;  
        printf("%s\n", root->name);
        print(root->friend, depth + 1, 
              notch_locs, notch_locs_capacity, true);
        print(root->child, depth, notch_locs, 
              notch_locs_capacity, false);
    }
}

void pprint(node *root) {
    bool *notch_locs = malloc(sizeof(bool));
    memset(notch_locs, false, sizeof(bool));
    print(root, 0, notch_locs, 1, false);
    free(notch_locs);
}

node *rand_chain() {
    int i = 0;
    node *root = malloc(sizeof(*root));
    memset(root, 0, sizeof(*root));
    sprintf(root->name, "%c", i + 97);
    i = (i + 1) % 25;

    while (rand() % 12) {
        node *curr = root;

        while (rand() % 5) {
            if (rand() % 2) {
                if (!curr->child) {
                    curr->child = malloc(sizeof(*curr));
                    memset(curr->child, 0, sizeof(*curr));   
                    sprintf(curr->child->name, "%c", i + 97);
                    i = (i + 1) % 25;
                }
                
                curr = curr->child;
            }
            else {
                if (!curr->friend) {
                    curr->friend = malloc(sizeof(*curr));
                    memset(curr->friend, 0, sizeof(*curr));
                    sprintf(curr->friend->name, "%c", i + 97);
                    i = (i + 1) % 25;
                }
                
                curr = curr->friend;
            }
        }
    }

    return root;
}

void free_chain(node *root) {
    if (root) {
        free_chain(root->child);
        free_chain(root->friend);
        free(root);
    }
}

int main(void) {
    /*
    a
    └ aa
      └ aaa
      │  └ aaaa
      ab
      ac
      └ aca
        acb
        acc
    */
    node acc = {"acc", NULL, NULL};
    node acb = {"acb", &acc, NULL};
    node aca = {"aca", &acb, NULL};
    node aaaa = {"aaaa", NULL, NULL};
    node aaa = {"aaa", NULL, &aaaa};
    node ac = {"ac", NULL, &aca};
    node ab = {"ab", &ac, NULL};
    node aa = {"aa", &ab, &aaa};
    node a = {"a", NULL, &aa};
    pprint(&a);

    node *root = rand_chain();
    pprint(root);
    free_chain(root);
    return 0;
}

输出:

a
└ aa
  └ aaa
  │ └ aaaa
  ab
  ac
  └ aca
    acb
    acc

a
└ k
│ └ t
│ │ u
│ │ └ v
│ │   └ w
│ l
│ └ p
│ │ q
│ │ r
│ │ └ s
│ │   └ t
│ │     u
│ │     └ v
│ │       └ w
│ │         x
│ m
│ └ f
│ │ └ g
│ │   └ n
│ │     └ o
│ n
│ o
│ p
│ └ q
│   └ r
│     s
b
└ c
│ └ d
│ │ e
│ │ └ f
│ │ │ └ g
│ │ │   h
│ │ │   i
│ │ │   └ j
│ │ c
│ │ d
│ h
│ └ i
│   └ j
│     k
│     l
│     └ m
x
└ e
y
└ z
  b