Сложный вопрос о рекурсии - древовидные узлы, представляющие процессы

Question

Спасибо, что прочитали эту ветку.У меня сложный вопрос, касающийся использования узлов дерева для представления системных процессов.

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

1000100110010110010101100101010110010210010201100210031004

Как видите, 1000 является корневым процессом, он имеет 4 дочерних процесса, 1001, 1002, 1003 и 1004. Процессы 100101 являются дочерними 1001, 10010101 является дочерними 100101, а 1001010101 дочерними процессами.из 10010101.

Несмотря на то, что root имеет 4 дочерних процесса, чтобы перейти от root к первому дочернему процессу, это root-> child_node.Дочерний процесс 1001 имеет «следующий» процесс 1002, а 1002 имеет следующий процесс 1003, и он имеет 1004 в качестве следующего процесса 1003.Следовательно, чтобы перейти к каждому дочернему процессу на том же уровне, он должен перейти от одного дочернего процесса к следующему дочернему процессу, используя next_node.

Ниже приведен результат, который генерирует мой код.Каждый процесс, такой как 1000, является TreeNode.Прямо сейчас мой код может печатать от 1000 до 1001010101, например, ниже,

10001001100101100101011001010101

Тем не менее, моя текущая проблема заключается в том, как мне обрабатывать следующий (соседний узел), например, 1001 и 1002 являются соседями, потому что next_node 1001 - 1002.

// Узел дерева.

struct TreeNode {
    pid_t pid;
    char *name;
    struct TreeNode *child_node;     // A list of child processes
    struct TreeNode *next_node;    // A link to the next sibling processes.

};

// Мой метод print_processes.

void print_processes(struct TreeNode *root, int space_level, int level_limit) {

    int i;

    for (i = 0; i < space_level; i++) {
        sleep(1);
        printf("  ");
    }

    printf("%d: %s\n", root->pid, root->name);

    struct TreeNode *node;

    while ((node = root->child_node) != NULL && level_limit != 0) {
        print_processes(node, space_level + 1, level_limit - 1);

    }

    //printf("hoho");
    exit(0);
}

int main(int argc, char **argv) {

struct TreeNode *root = malloc (sizeof (struct TreeNode));
root->pid = 1000;
root->name = "sshd";
root->child_node = NULL;
root->next_node = NULL;

struct TreeNode *c1 = malloc (sizeof (struct TreeNode));
c1->pid = 1001;
c1->name = "sshd";
c1->child_node = NULL;
c1->next_node = NULL;

struct TreeNode *c2 = malloc (sizeof (struct TreeNode));
c2->pid = 1002;
c2->name = "bash";
c2->child_node = NULL;
c2->next_node = NULL;

struct TreeNode *c3 = malloc (sizeof (struct TreeNode));
c3->pid = 1003;
c3->name = "sshd";
c3->child_node = NULL;
c3->next_node = NULL;

struct TreeNode *c4 = malloc (sizeof (struct TreeNode));
c4->pid = 1004;
c4->name = "sshd";
c4->child_node = NULL;
c4->next_node = NULL;

struct TreeNode *c5 = malloc (sizeof (struct TreeNode));
c5->pid = 1005;
c5->name = "bash";
c5->child_node = NULL;
c5->next_node = NULL;

struct TreeNode *n1 = malloc (sizeof (struct TreeNode));
n1->pid = 1011;
n1->name = "bash";
n1->child_node = NULL;
n1->next_node = NULL;

c4->child_node = c5;
c3->child_node = c4;
c2->child_node = c3;
c1->child_node = c2;
c1->next_node = n1;
root->child_node = c1;

print_processes(root, 0, 3);

return 0;

}

Опять же, ниже то, что мой код должен генерировать в терминале.

1000100110010110010101100101010110010210010201100210031004

Спасибо, что прочитали этот вопрос.

Answer 1

Вы можете значительно упростить и расширить print_processes(), и, безусловно, сделать функцию main() намного короче:

#include <stdio.h>

struct TreeNode
{
    int    pid;
    char  *name;
    struct TreeNode *child_node;     // A list of child processes
    struct TreeNode *next_node;    // A link to the next sibling processes.
};

static
void print_processes(struct TreeNode *root, int space_level, int level_limit)
{
    for (int i = 0; i < space_level; i++)
        printf("  ");

    printf("%d: %s\n", root->pid, root->name);

    if (root->child_node != NULL && level_limit > 0)
        print_processes(root->child_node, space_level + 1, level_limit - 1);
    if (root->next_node != NULL)
        print_processes(root->next_node, space_level, level_limit);
}

int main(void)
{
    struct TreeNode n1   = { 1011, "bash",   NULL, NULL };
    struct TreeNode c5   = { 1005, "bash",   NULL, NULL };
    struct TreeNode c4   = { 1004, "sshd-3", &c5,  NULL };
    struct TreeNode c3   = { 1003, "sshd-2", &c4,  NULL };
    struct TreeNode c2   = { 1002, "bash",   &c3,  NULL };
    struct TreeNode c1   = { 1001, "sshd-1", &c2,  &n1  };
    struct TreeNode root = { 1000, "sshd",   &c1,  NULL };

    print_processes(&root, 0, 3);

    return 0;
}

Вывод:

1000: sshd
  1001: sshd-1
    1002: bash
      1003: sshd-2
  1011: bash

Дляради уменьшения #include строк до 1, я изменил pid_t в int.