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

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

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

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

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

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node_t {
    int value;
    struct Node_t* next;
    struct Node_t* prev;
}   Node;
 
typedef Node List;
 
//-----------------------------------------------------------------------------
List* add(List** list, Node* node) {
    if (*list) {
        node->next = (*list);
        node->prev = (*list)->prev;
 
        (*list)->prev->next = node;
        (*list)->prev = node;
    }
    else {
        node->next = node->prev = node;
        (*list) = node;
    }
    return (*list);
}
//-----------------------------------------------------------------------------
List* push(List** list, int value) {
    Node* node = malloc(sizeof(Node));
    node->value = value;
 
    return add(list, node);
}
//-----------------------------------------------------------------------------
void write(const List* list) {
    const Node* node = list;
 
    if (node) {
        while (node->next != list) {
            printf("%d ", node->value);
            node = node->next;
        }
        printf("%d\n", node->value);
    }
}
//-----------------------------------------------------------------------------
Node* findFirst(List* list, int value) {
    Node* node = list;
    for (; (node->next != list) && (node->value != value); node = node->next) { ; }
 
    return (node->value == value) ? node : NULL;
}
//-----------------------------------------------------------------------------
Node* findLast(List* list, int value) {
    Node* node = list;
    for (; (node->prev != list) && (node->value != value); node = node->prev) { ; }
 
    return (node->value == value) ? node : NULL;
}
//-----------------------------------------------------------------------------
List* reverseBetween(List* list, int value) {
    Node* first = findFirst(list, value);
    Node* last = findLast(list, value);
    Node* node, * tail, * tmp;
 
    if (first && (first != last) && (first->next != last) && (last->prev != first)) {
        tail = last->prev;
        tmp = first->next;
        while (tmp != tail) {
            node = tmp;
            tmp = tmp->next;
            last = add(&last, node)->prev;
        }
        tail->prev = first;
        first->next = tail;
    }
 
    return list;
}
//-----------------------------------------------------------------------------
 
int main() {
    List* list = NULL;
    int i;
 
    for (i = 0; i < 20; ++i) {
        push(&list, ((i + 5) % 10) + 1);
    }
 
    write(list);
 
    write(reverseBetween(list, 10));
 
    return 0;
}

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

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

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

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