Спецкурс C++. Дополнительные задачи на списки.

list-more-tereshin.cpp

#include <cstdio>
#include <cmath>

/**
 *  Use UTF-8 code page
 *
 *  За основу для экспериментов был выбран односвязный список без охранника и разделения
 *  структур на собственно список (хранящий указатель на голову/охранник (опционально последний
 *  элемент списка)) и узел списка - в учебных целях, ИМХО, оправдано.
 *
 */

struct List
{
    int value;
    List *next;
};

// Два перегруженных фабричных метода.
// Версия без аргумента вовсе не выделят память.
List *createList(int value)
{
    List *head = new List;
    head->next = NULL;
    head->value = value;

    return head;
}

List *createList()
{
    return NULL;
}

void eraseList(List *head)
{
    if (head)
    {
        eraseList(head->next);  // postorder-тип работы рекурсии - иначе операция ->
                                // применялась бы к структуре в уже освобожденном участке
                                // динамической памяти - опасно e.g. в мультизадачном окружении.
        // "Удаление" нулевого указателя безопасно, так что строку ниже
        // можно было и вынести из-под оператора условия.
        delete head;
    }
}

// Добавление элемента в начало списка с подменой, таким образом,
// указателя на текущую голову списка
void prepend(List* &head, int value)
{
    if (!head)  // Отсутствие охранника вынуждает в каждой функции проверять
    {           // список на пустоту.
        head = createList(value);
        return;
    }
        
    List *tmp = new List;
    tmp->value = value;

    tmp->next = head;
    head = tmp;
}

void printList(List *list)
{
    if (list)   // Условие выхода их рекурсии - достигнут нулевой next
    {           // (читай - конец списка)
        printf("%d ", list->value); // preorder-тип работы рекурсии - иначе печать
        printList(list->next);      // была бы инвертированной
    }
}

// Инвертирование списка in situ рекурсивной функцией.
// С точки зрения производительности, по всей видимости,
// нет выигрыша от якобы O(1)-асимптотики по памяти -
// вместо явного сохранения указателей по ходу списка
// они "складываются" на стек потока выполнения аж по паре
// штук на кадр (stackframe) (+ потери на вызовах, зато красиво :)).
List *reverse(List *parent, List *node)
{
    // Новая голова списка будет записана в статическую
    // переменную с тем, чтобы ее можно было потом на первом
    // уровне рекурсии "вытащить"
    static List *reverseHead = NULL;
    if (!node)
        return node;

    if (node->next)
        reverse(node, node->next);
    else  // win!
        reverseHead = node;

    node->next = parent;

    return reverseHead;
}

// Скрываем от пользователя ненужные детали
void reverse(List* &list)
{
    list = reverse(NULL, list);
}

List *copyReverse(List *list)
{
    List *res = createList();
    while (list)
    {
        prepend(res, list->value);
        list = list->next;
    }
    return res;
}

List *getLast(List *list)
{
    if (!list)
        return list;

    if (list->next)
        return getLast(list->next);
    return list;
}

// Асимтотика O(n). Решение проблемы - всегда хранить
// указатель на конец списка.
void append(List* &list, int value)
{
    List *last = getLast(list);
    if (!last)
    {   // Заодно потестим prepand, ибо в main'е это делать лениво :)
        prepend(list, value);
        return;
    }

    List *tmp = new List;
    tmp->next = NULL;
    tmp->value = value;

    last->next = tmp;
}

void insertAfter(List *list, int pos, int value)
{
    int i = 0;
    for (; list && i < pos; ++i)
        list = list->next;

    if (!list)
        return;
    prepend(list->next, value);
}



int main()
{

    List *list = createList();

    append(list, 1);
    append(list, 2);
    append(list, 3);

    // 1-ая задача
    insertAfter(list, 0, 10);
    insertAfter(list, 4, 100);  // нет такого элемента, ничего не делаем

    // 2-ая задача
    List *lastItem = getLast(list);
    lastItem->value = pow(lastItem->value, 2);

    printList(list);
    putchar('\n');

    // 3-ая задача
    List *copy = copyReverse(list);

    printList(copy);
    putchar('\n');

    // 4-ая задача
    reverse(copy);

    printList(copy);
    putchar('\n');

    eraseList(list);
    eraseList(copy);

    return 0;
}