使用fork()以广度优先顺序打印序列 [英] Printing the sequence in breadth first order using fork()

问题描述

给出一个进程树

             A
           /   \
          /     \
         B       C
        / \     / \
       D   E   F   G

我被要求按BFS顺序打印序列，即使用fork()系统调用进行ABCDEFG的打印，其中每个节点代表一个具有与树所示相同的父子构造的进程(即A是B和C的父， B是D和E的父母).

I am asked to print the sequence in BFS order, i.e A-B-C-D-E-F-G using fork() system call, where each node represents a process with the same parent-child construct as shown in tree(i.e A is parent of B and C, B is parent of D and E like that).

我想出了这个解决方案，但是我真的不明白如何递归打印它.

I figured out this solution, but I really don't understand how to make it print recursively.

static int count;
char *msg[] = {"A", "B", "C", "D", "E", "F", "G"};
main(){
  if(!fork()){ //Child 1
    printf("%s\t\t%d\t\t%d\n", msg[count++], (int)getpid(), (int)getppid());
  }
  else{
    if(!fork()){ //Child 2
        printf("%s\t\t%d\t\t%d\n", msg[count++], (int)getpid(), (int)getppid());
    }
  } 
}

此逻辑仅打印A-B-C，如何使其递归以使其打印到G? 请帮忙.谢谢.

This logic prints only A-B-C, How to make it recursive so that it will print till G? Please help. Thanks.

推荐答案

以下代码可以满足您的需求，但不能保证首先打印哪个叶子(相同级别的打印顺序).

Following code does what you need but does not guarantee which leaf will be printed first (print order of the same level).

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <linux/wait.h>

typedef struct node {
  char data;
  struct node *left;
  struct node *right;
} node;

void pretty_print(node *nodes[], int size)
{
  int fork_cnt = 0;

  for (int i=0; i < size; i++) {
    if (fork() == 0) {
      // Child path.
      printf("%c (pid: %d, parent: %d)\n", nodes[i]->data, (int)getpid(), (int)getppid());
      node *children_nodes[256];
      int children_sizes = 0;
      if (nodes[i]->left)
    children_nodes[children_sizes++] = nodes[i]->left;
      if (nodes[i]->right)
    children_nodes[children_sizes++] = nodes[i]->right;
      if (children_sizes) {
    if (fork() == 0) {
      pretty_print(children_nodes, children_sizes);
      return;
    }
      }
      return;
    } else {
      // Parent path.
      fork_cnt++;
    }
  }

  for (int i=0; i < fork_cnt; i++) {
    // wait all children.
    int status;
    wait(&status);
  }
}

int main(void) 
{
  node g = {'G', NULL, NULL};
  node f = {'F', NULL, NULL};
  node e = {'E', NULL, NULL};
  node d = {'D', NULL, NULL};
  node b = {'B', &d, &e};
  node c = {'C', &f, &g};
  node a = {'A', &b, &c};

  node *root[1] = {&a};
  pretty_print(root, 1);
  return 0;
}

这篇关于使用fork()以广度优先顺序打印序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！