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

Question

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

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

1000
nbsp 1001
nbsp nbsp 100101
nbsp nbsp nbsp 10010101
nbsp nbsp nbsp nbsp 1001010101
nbsp 100102
nbsp nbsp 10010201
nbsp 1002
nbsp 1003
nbsp 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，都是一个树节点。现在，我的代码可以从1000打印到1001010101，比如下面的

1000
nbsp 1001
nbsp nbsp 100101
nbsp nbsp nbsp 10010101
nbsp nbsp nbsp nbsp 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: %sn", 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
nbsp 1001
nbsp nbsp 100101
nbsp nbsp nbsp 10010101
nbsp nbsp nbsp nbsp 1001010101
nbsp 100102
nbsp nbsp 10010201
nbsp 1002
nbsp 1003
nbsp 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: %sn", 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。