Перенести последний элемент списка в его начало - C (СИ)

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

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

Привет всем! Помогите выполнить задание на си: Создать список, содержащий целые числа. Перенести последний элемент списка в его начало. После завершения работы со списком освободить занимаемую им динамическую память.

Решение задачи: «Перенести последний элемент списка в его начало»

textual
Листинг программы
#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 очищает список, и он снова становится пустым.

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

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