Перенести последний элемент списка в его начало - C (СИ)
Формулировка задачи:
Решение задачи: «Перенести последний элемент списка в его начало»
#include <stdio.h>
#include <stdlib.h>
// Описание узла списка
typedef struct _TNode
{
int value;
struct _TNode* next;
} TNode;
// Описание самого списка
typedef struct _TList
{
TNode* head; // Вершина списка
TNode* tail; // Конец списка
} TList;
//-----------------------------------------------------------------------------
// Функция добавляет элемент в конец списка
TList* PushBack(TList* list, int value)
{
// Создаём новый узел
TNode* node = malloc(sizeof(TNode));
// Присваиваем узлу значение
node->value = value;
// Т.к. добавление осуществляется в конец, то
// следовательно за ним ничего не будет
node->next = NULL;
// В случае если в списке присутствует хотя бы один
// параметр ...
if (list->head && list->tail)
{
// Последний элемент списка ссылается
// на созданный
list->tail->next = node;
// Хвостом теперь является добавленный элемент
list->tail = node;
}
else
{
// Т.к. список был пуст, то теперь и вершиной
// и хвостом списка является созданный элемент
list->head = list->tail = node;
}
// Возвращаем наш список
return list;
}
//-----------------------------------------------------------------------------
// Функция добавляет элемент в начало списка
TList* PushFront(TList* list, int value)
{
// Создаём новый узел
TNode* node = malloc(sizeof(TNode));
// Присваиваем узлу значение
node->value = value;
// Т.к. добавление осуществляется в начало
// то следовательно он должен ссылаться на первый
node->next = list->head;
// Вершину списка перемещаем на созданный элемент
list->head = node;
// В том случае если список был пуст и хвост
// ни на что не указывал, то задаём хвосту адрес
// на созданный элемент
if (list->tail == NULL)
{
list->tail = node;
}
// Возвращаем наш список
return list;
}
//-----------------------------------------------------------------------------
// Извлечение элемента с начала списка
int PopFront(TList* list)
{
// Сохраняем указатель на первый (удаляемый) элемент
TNode* node = list->head;
// Также сохраняем его значение
int value = node->value;
// Указатель на вершину списка спускаем
// на уровень ниже
list->head = node->next;
// Если при перемещении указателя вершины списка
// он стал равным NULL, то список теперь пуст и соответственно
// значение хвоста тоже равно NULL
if (list->head == NULL)
{
list->tail = NULL;
}
// Удаляем бывший первый элемент
free(node);
// Возвращаем значение удалённого элемента
return value;
}
//-----------------------------------------------------------------------------
// Извлечение элемента с конца списка
int PopBack(TList* list)
{
// Копируем адрес начала списка, этой переменной будем пользоваться
// при переборе элементов, для достижения хвоста.
TNode* node = list->head;
// Сохраняем значение удаляемого элемента
int value = list->tail->value;
// Если в списке всего один элемент, то
// пользуемся функцией PopFront и не заморачиваемся
if (list->head == list->tail)
{
PopFront(list);
}
else
{
// Да, мы знаем где последний элемент, но мы не знаем
// предыдущий. Ведь у предыдущего next должен быть теперь
// задан в NULL. Поэтому перебираем начиная с головы весь список
// пока следующим не станет последний (хвостовой) элемент
while (node->next != list->tail)
{
node = node->next;
}
// node теперь есть предыдущий list->tail
// Удаляем последний. Можно было бы записать и так:
// free(list->tail);
free(node->next);
// Предыдущий делаем последним, соответственно
// next теперь равен NULL ...
node->next = NULL;
// ... а хвост явно перемещаем на node
list->tail = node;
}
// Возвращаем значение удалённого элемента
return value;
}
//-----------------------------------------------------------------------------
// Функция проверяет является ли список пустым
int IsEmpty(const TList* list)
{
return ((list->head == NULL) && (list->tail == NULL));
}
//-----------------------------------------------------------------------------
// Функция удаляет все элемент списка
TList* Clear(TList* list)
{
// Пока список не пуст
while (!IsEmpty(list))
{
// Извлекаем очередной элемент списка
PopFront(list);
}
return list;
}
//-----------------------------------------------------------------------------
// Функция выводит в стандартный поток вывода значение всех
// элементов списка
void Print(const TList* list)
{
// Используем вспомогательную переменную для перебора
const TNode* node = list->head;
// Пока node указывает на элемент списка
while (node)
{
// Выводим в stdout очередное значение
printf("%d ", node->value);
// Переходим к следующиму элементу списка
node = node->next;
}
printf("\n");
}
//-----------------------------------------------------------------------------
int main()
{
// Объявляем новый пустой список
TList list = {NULL, NULL};
// Количество добавляемых элементов
int i = 10;
// Пока i != 0 декрементируем его и ...
while (i--)
{
// ... заносим в список
PushFront(&list, i + 1);
}
// Выводим сформированный список
Print(&list);
// Извлекаем элемент с хвоста списка и добавляем
// его в начало этого же списка
PushFront(&list, PopBack(&list));
// Выводим получившийся список
Print(&list);
// Удаляем все элементы списка
Clear(&list);
return EXIT_SUCCESS;
}
Объяснение кода листинга программы
Код представляет собой реализацию односвязного списка на языке C. Он содержит функции для добавления элемента в начало и конец списка, извлечения элемента из начала и конца списка, проверки пустоты списка и очистки списка. В функции main создается пустой список, в который последовательно добавляются 10 элементов с помощью функции PushFront. Затем из последнего элемента списка с помощью функции PopBack извлекается значение, которое добавляется в начало списка с помощью функции PushFront. После этого выводится обновленный список. В конце программы список очищается с помощью функции Clear. Список изначально пуст, поэтому первый вызов функции PushFront добавляет элемент 1 в начало списка и делает его хвостом. Затем добавляются остальные элементы. После добавления всех элементов список выглядит так: 1 2 3 4 5 6 7 8 9 10. Затем из последнего элемента списка с помощью функции PopBack извлекается значение 10, которое добавляется в начало списка с помощью функции PushFront. После этого список выглядит так: 10 1 2 3 4 5 6 7 8 9. После этого выводится обновленный список: 10 1 2 3 4 5 6 7 8 9. Затем функция Clear очищает список, и он снова становится пустым.