Блог

Главная - Вопросы по программированию - Парный обмен в списке ссылок в c

Парный обмен в списке ссылок в c

#c #pointers #linked-list

#c #указатели #связанный список

Вопрос:

 void pairWiseSwap(struct node *head)
{
// The task is to complete this method
   if(!head || (head amp;amp; head->next==NULL))
   return;

   if(head->next!=NULL)
   {
     int tmp = head->next->data;
     head->next->data = head->data;
     head->data = tmp;
     pairWiseSwap(head->next->next);
   }
 }

попарно меняйте местами элементы.
Как работает этот код?
Как работает вызов обратной рекурсии?

Комментарии:

1. Почему бы не std::swap ?

2. … потому что это C-код, а не C

3. Чего конкретно вы не понимаете в этом коде? Что он делает, чего вы не ожидаете, и чего вы ожидаете?

4. Примечание: Нет необходимости повторно проверять head в правой части || оператора. Стандарты C и C гарантируют, что если левая часть логического оператора OR принимает значение true, то правая часть не вычисляется. Поэтому (!head || head->next==NULL) безопасен, если только ваш компилятор не соответствует стандарту.

Ответ №1:

Как следует из названия функции, она меняет местами данные в каждой паре ячеек (не сами ячейки).

Обмен данными из одной ячейки со следующей очень заметен :

 int tmp = head->next->data;
head->next->data = head->data;
head->data = tmp;

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

вызов с pairWiseSwap(head->next->next); обходит пару ячеек, данные которых были заменены, чтобы повторить в следующих.

Давайте посмотрим пример с этим полным кодом :

 #include <stdio.h>
#include <stdlib.h>

struct node {
  struct node * next;
  int data;
};

void pairWiseSwap(struct node *head)
{
// The task is to complete this method
   if(!head || (head amp;amp; head->next==NULL))
     return;

   if(head->next!=NULL)
   {
     int tmp = head->next->data;
     head->next->data = head->data;
     head->data = tmp;
     pairWiseSwap(head->next->next);
   }
}

struct node * mk(int d, struct node * nx)
{
  struct node * n = malloc(sizeof(struct node));

  if (n != NULL) {
    n->data = d;
    n->next = nx;
  }

  return n;
}

void pr(struct node * head)
{
  while (head) {
    printf("%d ", head->data);
    head = head->next;
  }
}

int main()
{
  struct node * head = mk(0, mk(1, mk(2, mk(3, mk(4, mk(5, NULL))))));

  printf("before : ");
  pr(head);

  pairWiseSwap(head);
  printf("nafter:   ");
  pr(head);
  putchar('n');

  /* free resources */
  while (head) {
    struct node * n = head->next;

    free(head);
    head = n;
  }
}

Компиляция и выполнение :

 pi@raspberrypi:/tmp $ gcc -pedantic -Wextra h.c
pi@raspberrypi:/tmp $ ./a.out
before : 0 1 2 3 4 5 
after:   1 0 3 2 5 4

Примечание 

 if(!head || (head amp;amp; head->next==NULL))
  return;

может быть просто 

 if ((head == NULL) || (head->next==NULL))
  return;

поскольку, если head не равен нулю в левой части || , это бесполезно, проверьте еще раз, что в правой части он не равен нулю

Если рекурсия выполняется на head->next , а не head->next->next на, функция выполняет своего рода поворот, и результатом является 1 2 3 4 5 0