具有挑战性的递归问题 - 表示进程的树节点

Question

感谢您阅读此主题。我有一个关于使用树节点表示系统进程的挑战性问题。

下面是当以下进程的树节点已经连接如下时我的代码必须打印出来的内容，

1000
  1001
    100101
      10010101
        1001010101
  100102
    10010201
  1002
  1003
  1004

如您所见，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，如下所示，

1000
  1001
    100101
      10010101
        1001010101

但是，我当前的问题是如何处理下一个(邻居节点)，例如 1001 和 1002 是邻居，因为 1001 的 next_node 是 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;

}

同样，下面是我的代码必须在终端中生成的内容。

1000
  1001
    100101
      10010101
        1001010101
  100102
    10010201
  1002
  1003
  1004

感谢您阅读这个问题。

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。