Как работает рекурсия при вставке узлов в связанные списки?

Question

Мне сложно понять, как работают функции свертки и сопоставления (весь код размещен здесь: https://repl.it/@flowerplowedup / Int # main. c):

void insert(Node **head, void *data) {
  /* new node */
  Node *new = malloc(sizeof(Node));
  new->data = data;
  new->next = NULL;

  /* insertion */
  Node **ptr = head;
  fold(tail, &ptr, *head);
  *ptr = new;
}

void *fold(void (*func)(void *, Node *), void *accum, Node *head) {
  if (head == NULL) {
    return accum;
  } else {
    func(accum, head);
    return fold(func, accum, head->next);
  }
}

void map(void (*func)(Node *), Node *head) {
  if (head != NULL) {
    func(head);
    map(func, head->next);
  }
}

Answer 1

Было бы лучше, если вы разместите здесь весь код, а не просто разместите его часть.

Чтобы понять вставку узла в список, сначала вы должны попытаться понять - Что делает функция fold()?

Определение рекурсивной функции fold():

void *fold(void (*func)(void *, Node *), void *accum, Node *head) {
  if (head == NULL) {
    return accum;
  } else {
    func(accum, head);
    return fold(func, accum, head->next);
  }
}

Сначала разберитесь в параметрах функции fold():

• void (*func)(void *, Node *): указатель на функцию, который может указывать на любую функцию, которая принимает два параметра - первый имеет тип void *, а второй - тип Node * и ничего не возвращает.
• void *accum: accum - это указатель на тип void, он же generi c указатель, который может быть преобразован в любой другой тип указателя.
• Node *head: head - это указатель на тип Node.

Теперь давайте расшифруем определение функции fold():

      if (head == NULL) {
          return accum;
      .....
      .....

Это условие завершения рекурсии - когда head равно NULL return accum (т.е. a void указатель).

Если head не NULL, то

  } else {
    func(accum, head);
    .....
    .....

вызов func(accum, head), что означает вызов функции, переданной в fold() в качестве первого аргумента, и передачу accum и head в качестве аргументов.

В insert() вызов fold() как -

fold(tail, &ptr, *head);

• tail(): функция
• &ptr: Адрес указателя на указатель на Node тип
• *head: head указатель на список

Теперь проверьте определение tail() -

static void tail(void *accum, Node *node) {
  *(Node ***)accum = &(node->next);
}

Так как первый аргумент accum - это void указатель, на который &ptr - прошло, и мы знаем, что ptr содержит адрес типа Node **. Таким образом, мы можем преобразовать accum с (Node ***) и разыменование его даст указатель Node **. Тип node->next - struct node *, а Node - это псевдоним struct node, что означает, что node->next имеет тип Node *, а его адрес имеет тип Node **. Итак, мы можем присвоить &(node->next) accum. После присвоения accum будет содержать адрес next указателя на node, переданного на tail().

После вызова func() сам вызов fold() (рекурсивный вызов):

    return fold(func, accum, head->next);
 }
}

Обратите внимание, что теперь accum содержит адрес следующего указателя текущего обрабатываемого узла списка и передача head->next означает, что рекурсивный вызов обработает следующий узел списка, и этот рекурсивный вызов назначит адрес next узла передан на указатель accum. Имея такое понимание, теперь я могу сказать, что этот рекурсивный вызов в конечном итоге приведет к присвоению адреса next последнего узла списка accum.

Когда эта рекурсия завершится и вернется к insert(), ptr будет иметь адрес next последнего узла списка. После вызова fold() мы имеем следующее в insert():

*ptr = new;

, т.е. присвоение узла new указателю next последнего узла, что означает вставку вновь созданного узла в последний из списка. .

В аналогичных строках попробуйте декодировать функцию map и другую часть программы.