10_linked_list_tasks.md

Практика

Разминка

1. Создайте в своём репозитории 2022-polytech-%фамилия% директорию 10_list
2. Cоздайте пустой README.md файл
3. В директории 10_list/intro создайте cmake-проект
4. Дополните пример из лекции с обёрткой List:
   • конструктором из std::initializer_list
   • дестркуктором
   • запретом копирования списка
   • методом clone, который выполняет глубокое копирование списка
   • оператором вывода списка в cout << (пример вывода: 1->2->3->4)
   • методом вставки в произвольное место списка insert
   • методом вставки в начало списка push_front
   • методом удаления элемента списка по индексу delete
   • методом чтения элемента списка по индексу get
   • методом size, который возвращает число элементов в списке
5. Приведите тесты для всех методов с использованием библиотеки doctest
6. Отправьте решение на GitHub

Задание

1. Создайте в своём репозитории 2022-polytech-%фамилия% директорию 10_list
2. Cоздайте пустой README.md файл
3. В директории 10_list/reverse создайте cmake-проект
4. Используя заготовку ниже, добавьте функцию generate_random, которая создаёт связный список длины n, заполненный случайными целыми числами (см. генерацию случайных чисел в предыдущих заданиях)

struct Node 
{
    int data;
    Node* next;
};

Node* generate(int n)
{
    Node* ptr = nullptr;
    for(int i=n; i>0; --i)
    {
        Node* new_node = new Node{i, ptr};
        ptr = new_node;
    }
    return ptr;
}

5. Напишите функцию, которая переворачивает связный список: void reverse(Node** list)
6. Напишите другую функцию, которая переворачивает связный список с позиции left по позицию right: void reverse(Node** list, int left, int right)
7. Напищите тесты с помощью doctest
8. Отправьте решение на GitHub

Домашнее задание

1. Создайте в своём репозитории 2022-polytech-%фамилия% директорию 10_list
2. Cоздайте пустой README.md файл
3. В директории 10_list/queue создайте cmake-проект
4. Напишите очередь на связном списке. Оочередь — структура данных с двумя основными операциями: enqueue, которая помещает элемент в очередь, и dequeue, которая извлекает элемент из очереди. Эти операции операции работают по правилу FIFO: первый помещённый в очередь элемент должен быть первым же и извлечён из очереди
5. Напишите тесты с помощью doctest
6. Отправьте решение на GitHub

Комментарии

• В этом файле есть опечатки, вы можете их исправить через pull request.
• Всю работу удобно вести в отдельной ветке и затем влить готовый результат в основную ветку.