В списке переставить в обратном порядке элементы между первым и последним вхождением элемента - C (СИ)
Формулировка задачи:
Решение задачи: «В списке переставить в обратном порядке элементы между первым и последним вхождением элемента»
#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. Затем список выводится на экран. После этого список переворачируется, и его вывод также отображается на экране.