В списке переставить в обратном порядке элементы между первым и последним вхождением элемента - C (СИ)

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

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

Пусть L обозначает кольцевой двунаправленный список с заглавным звеном. Описать функцию или процедуру, которая в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если Е входит в L не менее двух раз.

Решение задачи: «В списке переставить в обратном порядке элементы между первым и последним вхождением элемента»

textual
Листинг программы
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct Node_t {
  5.     int value;
  6.     struct Node_t* next;
  7.     struct Node_t* prev;
  8. }   Node;
  9.  
  10. typedef Node List;
  11.  
  12. //-----------------------------------------------------------------------------
  13. List* add(List** list, Node* node) {
  14.     if (*list) {
  15.         node->next = (*list);
  16.         node->prev = (*list)->prev;
  17.  
  18.         (*list)->prev->next = node;
  19.         (*list)->prev = node;
  20.     }
  21.     else {
  22.         node->next = node->prev = node;
  23.         (*list) = node;
  24.     }
  25.     return (*list);
  26. }
  27. //-----------------------------------------------------------------------------
  28. List* push(List** list, int value) {
  29.     Node* node = malloc(sizeof(Node));
  30.     node->value = value;
  31.  
  32.     return add(list, node);
  33. }
  34. //-----------------------------------------------------------------------------
  35. void write(const List* list) {
  36.     const Node* node = list;
  37.  
  38.     if (node) {
  39.         while (node->next != list) {
  40.             printf("%d ", node->value);
  41.             node = node->next;
  42.         }
  43.         printf("%d\n", node->value);
  44.     }
  45. }
  46. //-----------------------------------------------------------------------------
  47. Node* findFirst(List* list, int value) {
  48.     Node* node = list;
  49.     for (; (node->next != list) && (node->value != value); node = node->next) { ; }
  50.  
  51.     return (node->value == value) ? node : NULL;
  52. }
  53. //-----------------------------------------------------------------------------
  54. Node* findLast(List* list, int value) {
  55.     Node* node = list;
  56.     for (; (node->prev != list) && (node->value != value); node = node->prev) { ; }
  57.  
  58.     return (node->value == value) ? node : NULL;
  59. }
  60. //-----------------------------------------------------------------------------
  61. List* reverseBetween(List* list, int value) {
  62.     Node* first = findFirst(list, value);
  63.     Node* last = findLast(list, value);
  64.     Node* node, * tail, * tmp;
  65.  
  66.     if (first && (first != last) && (first->next != last) && (last->prev != first)) {
  67.         tail = last->prev;
  68.         tmp = first->next;
  69.         while (tmp != tail) {
  70.             node = tmp;
  71.             tmp = tmp->next;
  72.             last = add(&last, node)->prev;
  73.         }
  74.         tail->prev = first;
  75.         first->next = tail;
  76.     }
  77.  
  78.     return list;
  79. }
  80. //-----------------------------------------------------------------------------
  81.  
  82. int main() {
  83.     List* list = NULL;
  84.     int i;
  85.  
  86.     for (i = 0; i < 20; ++i) {
  87.         push(&list, ((i + 5) % 10) + 1);
  88.     }
  89.  
  90.     write(list);
  91.  
  92.     write(reverseBetween(list, 10));
  93.  
  94.     return 0;
  95. }

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

Код представляет собой реализацию односвязного списка в языке C. Структура списка реализована с помощью указателя на первый элемент в списке (list), а также с помощью указателей на предыдущий и следующий элементы в списке (prev и next, соответственно). Функция add добавляет новый элемент в список, вставляя его между текущим и предыдущим элементом. Если список пуст, новый элемент становится первым элементом списка. Функция push добавляет новый элемент в список, используя функцию add. Она также выводит значение нового элемента. Функция write проходит по всем элементам списка и выводит их значения. Функции findFirst и findLast ищут первый и последний элемент в списке с заданным значением. Они возвращают указатель на соответствующий элемент, или NULL, если элемент не найден. Функция reverseBetween переворачивает список, начиная с элемента с заданным значением и до предпоследнего элемента списка. Если список не содержит элементов с заданным значением, функция возвращает исходный список без изменений. В функции main создается список из 20 элементов со значениями от 1 до 10, с шагом 5. Затем список выводится на экран. После этого список переворачируется, и его вывод также отображается на экране.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

14   голосов , оценка 4 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы