Как распечатать вложенный связанный список довольно

Question

Существует такая структура:

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

И есть много объектов с этой структурой, и они связаны как дети и друзья

Так что я могу получить доступ ко всем из них, если знаюпервый адрес

Первый объект такой:

struct a start;

И я собираюсь установить все значения в этих объектах сразу после того, как они будут сгенерированы

Так что еслиу них нет ни ребенка, ни друга, их переменные-члены child и friend будут равны нулю

И я хочу напечатать все эти объекты следующим образом:

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

Я действительноизвините за этот ужасный рисунок

Итак, a - это имя start, а aa - это имя ребенка start, а ab, ac - друзья aa.Примерно так.

Я знаю, как печатать эти специальные символы

Проблема в том, что объекты определяются во время выполнения

Так что мне нужен алгоритм для такой печатиВот так:

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

Но это далеко от того, что я хочу

Я действительно не знаю, как это сделать

Возможно ли это?Если нет, я хочу получить некоторую помощь о том, как напечатать такую ​​структуру довольно

Answer 1

Как правило, этот тип печати дерева довольно прост: добавьте поле depth и напечатайте пробелы в дочерних отступах, чтобы соответствовать их уровню вложенности.

Добавление символа └ также возможно с логическим флагом, чтобы сообщить узлу, является ли он дочерним или нет, и, если это так, добавьте символ угла непосредственно перед печатью.

Тем не менее, добавление дочернего бара | добавляет немного рывков в работу. Теперь нам нужно сохранить состояние для каждого родительского узла, чтобы определить, есть ли у него дочерние элементы, которые еще не были напечатаны. Для этого мы можем создать массив флагов и включить или отключить их в зависимости от наличия детей на определенной глубине. Это должен быть расширяемый массив, так как мы не можем быть уверены, насколько глубока структура.

Вот пример кода:

#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

Попробуйте!