Перенести последний элемент списка в его начало - 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 очищает список, и он снова становится пустым.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д