README.md

Лабораторная работа 6. Линейный односвязный список.

Информационная часть элемента списка представлена указателем на void. Список формируется на основе данных, которые читаются из текстового файла. В качестве данных может, например, выступать информация о студенте: фамилия и год рождения. Область данных выбирается самостоятельно и отличается от указанного примера. Элементы списка данными "не владеют", т.е. хранят лишь указатель на них. При удалении элемента из списка данные не удаляются. Для решения некоторых задач требуется функция сравнения элементов. Сравнение элементов реализуется как отдельная функция. Функции, нуждающиеся в сравнении элементов, получают в качестве параметра указатель на функцию сравнения. Имена файлов, выполняемая операция и т.п. указываются через параметры командной строки, результаты работы записываются в файл. Условная сложность каждой задачи указанна в скобках после условия задачи. Модульные тесты и отчет Doctor Memory обязательны. Списывание карается.

🔴 Задачи на работу с одним элементом списка

Необходимо решить любые две задачи.

1. ✅ Напишите функцию поиска элемента в списке (нужна функция сравнения элементов). (1)
2. Напишите функцию pop_front, которая возвращает указатель на данные из элемента, который расположен в "голове" списка. При этом из списка сам элемент удаляется. (1)
3. Напишите функцию pop_end, которая возвращает указатель на данные из элемента, который расположен в "хвосте" списка. При этом из списка сам элемент удаляется. (1)
4. ✅ Напишите функцию insert, которая вставляет элемент перед указанным элементом списка (в качетсве параметров указываются адреса обоих элементов). (2)

🔴 Задачи на работу с целым списком

Необходимо решить одну любую задачу.

1. Напишите функцию copy, которая по указанному списку создает его копию (данные при этом не копируются). (1)
2. Напишите функцию append, которая получает два списка а и b, добавляет список b в конец a. Список b при этом оказывается пустым. (1)
3. Напишите функцию remove_duplicates, которая получает упорядоченный список и оставляет в нем лишь первые вхождения каждого элемента. Совпадение определяется с помощью функции сравнения элементов. При удалении элемента списка данные не удаляются. (2)
4. ✅ Напишите функцию reverse, которая обращает список.

Идеи реализации:

• Использование pop_front и двух списков. (1)
• Использование 3-х указателей на соседние элементы списка. (2)
• Рекурсия. (2)

🔴 Сортировка списка

Необходимо реализовать одну из двух сортировок.

1. Сортировка вставками ✅

• Напишите функцию sorted_insert, которая получает упорядоченный список, и элемент, который нужно вставить в этот список, чтобы не нарушить его упорядоченности.

• Напишите функцию insert_sort, которая получает список и упорядочивает его по возрастанию, используя функцию sorted_insert. (3)

2. Сортировка слиянием

• Напишите функцию front_back_split, которая получает список и делит его на две половины. Если в списке нечетное число элементов, "серединный" элемент должен попасть в первую половину.

• Напишите функцию sorted_merge, которая получает два упорядоченных списка и объединяет их в один.

• Используя функции front_back_split и sorted_merge напишите функцию merge_sort, которая реализует рекурсивный алгоритм сортировки слиянием. (4)