Разбить список на 2 подсписка методом перераспределения - C (СИ)

Узнай цену своей работы

Формулировка задачи:

У меня есть односвязный список элементов, нужно разбить список на 2 методом перераспределения элементов по признаку четности. Прототип списка:
typedef struct Node {
    int value;
    struct Node *next;
} Node;
До этого я сделал методом переписи, но преподаватель говорит что так не годится, а как перераспределить элементы я не пойму.

Решение задачи: «Разбить список на 2 подсписка методом перераспределения»

textual
Листинг программы
#include <stdlib.h>
#include <stdio.h>
 
typedef struct Node 
{
  int value;
  struct Node *next;
} Node;
 
void split_even_odd(Node *list, Node **even_list, Node **odd_list)
{
  Node **even_next = even_list, **odd_next = odd_list;
 
  for (; list != NULL; list = list->next)
    if (list->value % 2 == 0)
    {
      *even_next = list;
      even_next = &(*even_next)->next;
    }
    else
    {
      *odd_next = list;
      odd_next = &(*odd_next)->next;
    }
 
  *even_next = *odd_next = NULL;
}
 
void print_list(const Node *list)
{
  for (; list != NULL; list = list->next)
    printf("%d ", list->value);
 
  printf("\n");
}
 
int main()
{
  Node *list = &(Node) { 8, &(Node) { 5, &(Node) { 9, &(Node) { 6, NULL }}}};
  print_list(list);
 
  Node *even_list, *odd_list;
  split_even_odd(list, &even_list, &odd_list);
 
  print_list(even_list);
  print_list(odd_list);
}

Объяснение кода листинга программы

  1. Создается структура данных узел (Node), которая содержит целочисленное значение и указатель на следующий узел в списке.
  2. Определяется функция split_even_odd, которая принимает указатель на начало списка, а также указатели на два подсписка (even_list и odd_list).
  3. В функции создаются два указателя even_next и odd_next, которые будут использоваться для перебора элементов списка и добавления их в соответствующие подсписки.
  4. Происходит итерация по всем элементам списка. Если значение элемента делится на 2 без остатка, то он добавляется в even_list, иначе в odd_list.
  5. После завершения цикла, указатели even_next и odd_next указывают на последний элемент в каждом из подсписков.
  6. Задается значение NULL для указателей even_next и odd_next, чтобы обозначить конец каждого из подсписков.
  7. В функции main создается список list, который содержит несколько подсписков.
  8. Вызывается функция print_list для вывода содержимого списка на экран.
  9. Создаются два указателя even_list и odd_list, которые будут использоваться для хранения подсписков even и odd.
  10. Вызывается функция split_even_odd, передавая ей указатель на список и указатели на even_list и odd_list.
  11. Выводится содержимое even_list и odd_list.
  12. В данном примере, после разделения списка на подсписки, выводится список [8, 5, 9, 6], состоящий из четных и нечетных чисел.

Оцени полезность:

11   голосов , оценка 4 из 5
Похожие ответы