c - 挑战性递归问题-代表过程的树节点

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

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

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-> 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;

}

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

1000
1001
    100101
      10010101
         1001010101
100102
      10010201
1002
1003
1004

感谢您阅读此问题。

最佳答案

您可以简化和扩展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。